Game theory

From Glossary

Jump to: navigation, search

In general, a (mathematical) game can be played by one player, such as a puzzle, but its main connection with mathematical programming is if there are at least two players, and they are in conflict. Each player chooses a strategy that maximizes his payoff. If 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, LaTeX: A, is given where LaTeX: A_{ij} is the payoff to player 1, and the loss to player 2, if player 1 uses strategy i and player 2 uses strategy j. In this representation each row of LaTeX: A corresponds to a strategy of player 1, and each column corresponds to a strategy of player 2. If LaTeX: A is LaTeX: m \times n, this means player 1 has m strategies, and player 2 has n strategies. Here is an example of a LaTeX: 2 \times 3 payoff matrix:

A = \left[ \begin{array}{rrr}
10 & -5 & 20 \\ -15 & 5 & -15
\end{array} \right]

A primary connection with mathematical programming is duality. Suppose LaTeX: (x_1, x_2, \ldots, x_m) and LaTeX: (y_1, y_2, \ldots, y_n) are strategy probability vectors chosen by the two players, i.e. in a particular play, LaTeX: x_i is the probability player 1 chooses strategy i and LaTeX: y_j is the probability player 2 chooses strategy j. Then, the value, LaTeX: v of the game is the expected payoff:

v = x A y^T = \sum_{ij} x_i A_{ij} y_j

where player 1 seeks to maximize LaTeX: v and player 2 seeks to minimize LaTeX: v. A pure strategy is a unit vector. For example, if LaTeX: x = (1, 0, 0, \ldots, 0), then player 1 is using his first strategy 100% of the time; if LaTeX: y = (0, 1, 0, 0, \ldots, 0), player 2 is using his second strategy 100% of the time. The expected payoff is simply the cell entry, LaTeX: A_{12}, which is -5 in the example (player 2 pays 5 units to player 1). The strategies that are not pure are called mixed. For example, LaTeX: x = (1/2, 1/2) means player 1 plays each of the two strategies 50% of the time (flipping a coin on each play); LaTeX: y =(1/4, 3/4, 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, see the supplement on mathematical programming duals,

provides the equivalent primal-dual formulation:

Player 1 is Player 2 is
Primal Dual

LaTeX:  \max v : x \ge 0, \; \sum_i x_i = 1,          LaTeX:  \min v : y \ge 0, \; \sum_j y_j = 1,
LaTeX: v \le \sum_i x_i A_{ij} \; \forall j LaTeX: v \ge \sum_j A_{ij}y_j \; \forall i

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.

Personal tools