Codex @codex  0

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.

Game theory studies decisions whose consequences depend on what other decision makers choose. A bidder's gain depends on competing bids in an auction; a driver's travel time depends on other drivers in a congestion game. This strategic interdependence makes choosing well a different problem from optimization against a fixed environment: each participant's best response depends on the others' choices.

A normal-form game specifies the players, their available pure strategies, and their payoffs for each strategy profile. Larger payoffs mean more preferred outcomes for that player. Unless stated otherwise, a two-player table below lists $(u_1,u_2)$: the row player's payoff first, the column player's second. Each player maximizes their own expected utility; the numbers need not represent money, and comparing different players' numerical scales is unnecessary.

The central question is whether everyone's choices fit together. A Nash equilibrium consists of mutual best responses: no unilateral deviation improves a player's expected payoff. It can involve definite choices, or mixed strategies that deliberately randomize. Matching pennies shows why randomization can be essential; the coordination game shows how players can share an interest in coordinating while disagreeing over which outcome to choose. Such shared gains are absent from a two-player zero-sum game, where one player's gain is exactly the other's loss.

These ideas are useful both for analyzing incentives and for designing them. Mechanism design asks how changing the rules changes participants' best responses; evolutionary game theory studies how successful strategies spread. The mathematical appeal is that local comparisons of payoffs can reveal a globally consistent pattern of choices. Consistency alone does not imply Pareto efficiency, uniqueness, or that actual play will converge to a Nash equilibrium.

John Nash's ^[ref] established existence of a mixed strategy Nash equilibrium for every finite game. His ^[ref] developed the theory beyond two-player zero-sum games. The distinction between conflicting and shared interests is fundamental to the subject.

A transferable utility game represented by a weighted undirected graph, with one player per graph vertex. A coalition receives the sum of weights of the graph edges in its induced subgraph; absent edges have weight zero. Singleton and empty coalitions have value zero. This is a representation of a transferable utility game, distinct from a graphical description of local payoffs in a normal-form game.

Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are $b$ and $nb$; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization $M=1$. The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is $n/2$ to each initial dataset.

The bimatrix game has payoffsFor example, joint purchase gives dataset sizes $1+n/2$ and $2+n/2$, total $3+n$, and each buyer pays $P/2$. A sole buyer gets the full corpus and pays $P$. The total payoff is $1-P$ whenever a purchase occurs and $1$ when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.

For the following calculations, setThe payoff differences “buy minus do not buy,” with the other player's action held fixed, areThese four differences give all the best response comparisons without mixing up row and column payoffs.

Use net monetary gain as payoff and order each player's pure strategies as $1,2,4$. The payoff matrix for the first player isThe second player's matrix is $-A$. Equal choices return both stakes, so the diagonal is zero; when the first player wins, their net gain is the other's stake, and when they lose it is minus their own stake. This is a matrix game, hence a zero-sum game and a normal-form game.

Measure all payoffs in millions of dollars, in the order (Ann, Bob). Since both players maximize expected money, those numbers are already their expected utility scale.

In the extensive-form game, Ann moves first. Staying out terminates at $(2,6)$. Entering leads to Bob's observed decision between fighting, with terminal payoffs $(1,1)$, and acquiescing, with terminal payoffs $(3,3)$. Each decision node is its own information set, so this is a perfect-information game.

The corresponding normal-form game gives Ann the pure strategies $O$ (stay out) and $E$ (enter), and Bob the complete contingent pure strategies $F$ (fight if entry occurs) and $A$ (acquiesce if entry occurs). The payoff matrix isThe pure strategy Nash equilibria are $(O,F)$ and $(E,A)$. Against $F$, Ann prefers $O$; against $A$, Ann prefers $E$. When Ann stays out, Bob's contingent response does not affect his payoff, so $F$ is a best response there.

There is exactly one subgame perfect equilibrium, $(E,A)$. In the subgame following entry, Bob strictly prefers $3$ to $1$, so backward induction selects acquiescence; Ann then strictly prefers entering for $3$ to staying out for $2$. The threat supporting $(O,F)$ is not optimal in that one-shot subgame.

For infinite repetition, the paper specifies no discount factor. First take the long-run average payoff convention, with all past actions observed. The feasible payoff set is the convex hullAnn can guarantee $2$ in every stage by staying out; Bob can guarantee at least $3$ in every stage by acquiescing whenever entry occurs. These guarantees are also their minmax payoffs: fighting holds Ann's best possible stage payoff to $2$, and entering holds Bob's best possible stage payoff to $3$.

Therefore the sustainable Nash equilibrium average payoffs are exactly the feasible, weakly individually rational payoffs in a repeated game:This is the closed triangle with vertices $(2,3),(2,6),(3,3)$.

Here is a direct sufficiency argument for this particular game. Choose a publicly known sequence of stage outcomes whose frequencies give the target point. Before any observed deviation, follow that sequence. After an Ann deviation, Bob fights forever, so Ann can thereafter obtain at most $2$ per stage. After a Bob deviation, Ann enters forever, so Bob can thereafter obtain at most $3$ per stage. A finite prefix has no effect on long-run average payoff, so no unilateral deviation improves a target with $a\ge 2,b\ge 3$. Rational frequencies can be implemented periodically; arbitrary real frequencies can be implemented by a deterministic sequence with convergent frequencies. Thus even the weak boundary is covered here. In particular, staying out forever and entry followed by acquiescence forever are sustainable; fighting forever is not.

For discounted payoffs $(1-\delta ){\sum }_{t\ge 0}{\delta }^t{u}_i^t$, the folk theorem for repeated games instead gives the usual patience qualification: every feasible point with $a>2,b>3$ can be sustained for all sufficiently large $\delta <1$. It does not classify the whole region for an unspecified fixed $\delta$. The two one-shot Nash equilibrium outcomes remain sustainable for every $\delta$.^[ref]

Finally consider the particular history-dependent pair in the paper. Initially Bob has never acquiesced, so Ann stays out. That preserves the same condition forever, giving payoffs $(2,6)$. The pair is a Nash equilibrium. Holding Bob's strategy fixed, Ann cannot induce an acquiescence: he fights whenever she enters, and his rule never changes unless he has previously acquiesced. Every entry would give her $1$ instead of $2$, so no unilateral deviation helps. Holding Ann's strategy fixed, Bob never reaches a decision node because she stays out; changing his strategy alone cannot create a history in which he actually acquiesces. Hence he also cannot improve.

This direct argument works for both discounted and long-run average payoffs. The outcome gives Ann exactly her minmax payoff and Bob more than his, so it is compatible with the folk theorem for repeated games. A version requiring strict gains above both minmax payoffs is a sufficient condition, and cannot be used to rule out this boundary example.

Two people can each have a clear incentive to choose an outcome that leaves both worse off. The prisoner's dilemma isolates this tension between individual best responses and Pareto efficiency. For example, two partners can each save effort by withholding a promised contribution, yet both would prefer a successful joint project to mutual withholding. The model applies when each person's payoffs really have the ordering below; the names “cooperate” and “defect” alone do not establish a prisoner's dilemma.

In the symmetric two-player normal-form game, each player chooses cooperation $C$ or defection $D$ simultaneously, without observing the other's current choice. The four payoffs are the mutual-cooperation reward $R$, mutual-defection punishment $P$, sole-defector temptation $T$, and sole-cooperator payoff $S$, with $T>R>P>S$. Defection is a strictly dominant strategy: it beats cooperation against either opposing pure strategy. This definition and the resulting one-shot Nash equilibrium are discussed in Steven Kuhn, Prisoner's Dilemma, Stanford Encyclopedia of Philosophy, section 1.

Take the concrete payoffs $T=5$, $R=3$, $P=1$, $S=0$. Each entry below gives the row player's payoff followed by the column player's payoff:

For the row player, switching from $C$ to $D$ improves the payoff from $3$ to $5$ against $C$, and from $0$ to $1$ against $D$. The column player has the same comparisons, so $D$ is a strictly dominant strategy for each. Even against a mixed strategy choosing $C$ with probability $q$, the expected payoff advantage is $2q+(1-q)=1+q>0$. Thus cooperation cannot appear with positive probability in a best response, and $(D,D)$ is the unique one-shot Nash equilibrium, including mixed strategies.

At $(D,D)$, a unilateral deviation to $C$ lowers the deviator's payoff from $1$ to $0$. A joint change to $(C,C)$ instead raises both payoffs from $1$ to $3$: mutual cooperation Pareto dominates mutual defection, making the Nash equilibrium fail Pareto efficiency. A Nash equilibrium tests unilateral deviations, so it need not maximize shared gains. This is the useful lesson: improving the available outcome may require changing incentives, rather than telling each participant to choose a better best response.

The additional inequality $2R\ge T+S$ says that mutual cooperation gives each player at least as much average payoff as equal-time alternation between the two asymmetric outcomes. It is a further assumption, not a consequence of $T>R>P>S$. Here it holds strictly: $6>5$, and alternating exploitation gives each player average payoff $5/2<3$. This comparison concerns equal-time averages, not every discounted sequence. See Kuhn, section 3, on the additional cardinal-payoff condition.

The normal-form game played once in each round of a repeated game. Its actions and payoffs are distinct from the repeated interaction's history-dependent pure strategies and aggregate payoffs. The same stage game can produce different incentive constraints under a finite sum, discounting or long-run average payoff criterion.