Normal-form game

A normal-form game specifies each player's strategy set and their payoff for every strategy profile. In a finite two-player game these data form a bimatrix game; if the two payoffs always sum to zero, one payoff matrix describes the matrix game. The representation specifies choices and incentives, without a temporal order of observed moves.

A binary game is a finite normal-form game in which each player's payoff at every pure strategy profile is either zero or one. This describes the numerical payoffs, not the number of players or available actions. A mixed strategy can have an intermediate expected payoff. If a weighted average of binary payoffs is at least one, every positive-weight term must equal one; this observation makes pure-by-mixed domination unusually simple in binary games.

Write column $j$ of a two-row binary game as $((a_j,c_j),(b_j,d_j){)}^T$, with the row player's payoff first. If there is no pure Nash equilibrium, the column player's maximum payoff in each row must be one. Otherwise every column would be a best response in a zero-payoff row, and excluding an equilibrium there would force the opposite row to dominate in every column, giving an equilibrium in that opposite row.

A column maximizing the column player's top-row payoff must then have $(a_j,b_j)=(0,1)$, or its top cell would be an equilibrium. Its bottom column-player payoff must be zero, or its bottom cell would be one. Thus a column $((0,1),(1,0){)}^T$ occurs. The same argument for the bottom row produces $((1,0),(0,1){)}^T$. No column can give the column player payoffs $(1,1)$, since a row-player best response within that column would be a pure equilibrium.

Consequently, if neither pure equilibrium is found, mix equally over the two rows and equally over those two special columns. The row player's two expected payoffs are $1/2$; every column gives the column player at most $1/2$, and the supported columns achieve $1/2$. This is a Nash equilibrium. Computing the two row maxima, scanning for pure equilibria and locating the two special columns takes $O(n)$ running time for $n$ columns.

A discrete location game can model firms choosing sites from $\{1,\dots ,k\}$ while customers at those sites choose a nearest firm. The customer masses, distance rule, permission to share a location and rule for ties are part of the model. For two firms, customer value two per site and equal splitting of ties, the payoff to a firm at $x$ against one at $y$ isFor $x<y$, counting sites strictly left of the midpoint and assigning half of an equidistant site's value gives $x+y-1$, whether $x+y$ is even or odd. The other firm receives the remainder, so this is a constant-sum game with total $2k$. Changing tie priority can fundamentally change its Nash equilibria, especially when co-location is permitted.

For $k\ge 3$, suppose two distinct occupied sites are $\ell <r$, a final firm must choose a different site, customers have value two per site and nearest-firm ties are split equally. A final firm left of both incumbents maximizes its payoff uniquely at $\ell -1$, when that site exists, obtaining $2(\ell -1)$. To the right it maximizes uniquely at $r+1$, obtaining $2(k-r)$. At every available interior site it obtains the same payoff $r-\ell$. Thus all best responses are obtained by comparing these three values, omitting regions with no available site and retaining every tied maximizing choice.

More generally, three distinct locations $a<b<c$ give their left, middle and right firms payoffs $a+b-1$, $c-a$ and $2k-b-c+1$. Counting the two midpoint boundaries proves these formulas; the middle firm's demand is the difference between the cumulative demands at the two boundaries. The formulas retain all even/odd midpoint ties automatically.

A strategy profile specifies one strategy for every player. A pure strategy strategy profile lies in the Cartesian product $S_1\times \cdots \times S_n$ of the players' strategy sets. A mixed strategy strategy profile specifies one probability distribution ${\sigma }_i$ over each $S_i$. Write $s_{-i}$ or ${\sigma }_{-i}$ for the choices of all players except player $i$.

A unilateral deviation changes only one player's strategy, holding the other players' strategies fixed. It is profitable if it strictly increases that player's payoff, or expected payoff for mixed strategies. The comparison does not allow the opponents to adjust in response to the deviation. In a sequential game, however, holding an opponent's complete pure strategy fixed still allows their prescribed actions to differ after different observed histories.