Game theory
From Glossary
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, , is given where 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 corresponds to a strategy of player 1, and each column corresponds to a strategy of player 2. If is , this means player 1 has m strategies, and player 2 has n strategies. Here is an example of a payoff matrix:
A primary connection with mathematical programming is duality. Suppose and are strategy probability vectors chosen by the two players, i.e. in a particular play, is the probability player 1 chooses strategy i and is the probability player 2 chooses strategy j. Then, the value, of the game is the expected payoff:
where player 1 seeks to maximize and player 2 seeks to minimize . A pure strategy is a unit vector. For example, if , then player 1 is using his first strategy 100% of the time; if , player 2 is using his second strategy 100% of the time. The expected payoff is simply the cell entry, , 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, means player 1 plays each of the two strategies 50% of the time (flipping a coin on each play); 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 primaldual formulation:Player 1 is  Player 2 is  
Primal  Dual  




This is the simplest 2person 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 noncooperative.
A combinatorial game is a cooperative game with restrictions on the formation of coalitions that induce a combinatorial structure, such as a matroid.