GAME THEORY

Game theory - In general, a (mathematical) game can be played by one player, such as a puzzle, but its main connection with mathematical programming is when there are at least two players, and they are in conflict. Each player chooses a strategy that maximizes his payoff. When there are exactly two players and one player's loss is the other's gain, the game is called zero sum. In this case, a payoff matrix, A, is given where A_ij is the payoff to player 1, and the loss to player 2, when player 1 uses strategy i and player 2 uses strategy j. In this representation each row of A corresponds to a strategy of player 1, and each column corresponds to a strategy of player 2. If A is m × n, this means player 1 has m strategies, and player 2 has n strategies. Here is an example of a 2 × 3 payoff matrix:

A =. A primary connection with mathematical programming is duality. Suppose x=(x₁ ... x_m) and y=(y₁ ... y_n) are strategy probability vectors chosen by the two players –  i.e., in a particular play, x_i = probability player 1 chooses strategy i and y_j = probability player 2 chooses strategy j. Then, the value   (v) of the game is the expected payoff:

v = xAy = _i,j x_iA_ijy_j , where player 1 seeks to maximize v and player 2 seeks to minimize v. A pure strategy is a unit vector. For example, if x = (1, 0), player 1 is using his first strategy 100% of the time; if y = (0, 1, 0), player 2 is using his second strategy 100% of the time. The expected payoff is simply the cell entry, A₁₂, which is –5 (player 2 pays 5 units to player 1). The strategies that are not pure are called mixed. For example, x = (½, ½) means player 1 plays each of the two strategies 50% of the time (flipping a coin on each play); y = (¼, ¾, 0) means player 2 plays his first strategy 25% of the time and his second the remaining 75%. The expected payoff is –5/8. The fundamental duality theorem of linear programming provides the equivalent primal-dual formulation:

This is the simplest 2-person game; more generally, there can be n persons, and subsets of the players can form cooperative agreements. If this is not allowed, the game is called non-cooperative. A combinatorial game is a cooperative game with restrictions on the formation of coalitions that induce a combinatorial structure, such as a matroid .