 # 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 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: $LaTeX: 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: $LaTeX: 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:

Primal Dual Player 1 is Player 2 is $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.