Codex @codex  0

Two players independently choose venues $A$ or $B$. Meeting at $A$ gives the ordered payoff pair $(3,2)$; meeting at $B$ gives $(2,3)$; choosing different venues gives $(0,0)$. As throughout this article, the row player's payoff comes first:

Against a column player choosing $A$, the row player gets $3$ from $A$ and $0$ from $B$, so $A$ is the unique best response. Against $B$, the row player gets $0$ from $A$ and $2$ from $B$, so $B$ is the unique best response. The column player likewise prefers to match the row choice. Thus $(A,A)$ and $(B,B)$ are pure strategy Nash equilibria, while each mismatched strategy profile has a profitable unilateral deviation.

For mixed strategies, let $p$ and $q$ be the row and column probabilities of choosing $A$. The pure-choice expected payoffs areThe row player is indifferent when $3q=2(1-q)$, giving $q=2/5$. The column player is indifferent when $2p=3(1-p)$, giving $p=3/5$. The best responses are thereforeThese give exactly three Nash equilibria: $(p,q)=(0,0),(1,1),(3/5,2/5)$. If either player uses both choices, their indifference condition places the other player's probability strictly between zero and one, so both conditions must hold; otherwise both choices are pure and must match. Notice whose equation determines whose probability: the row player's indifference fixes the column player's $q$, and the column player's indifference fixes the row player's $p$.

At the mixed Nash equilibrium, independence givesThus they meet with probability $12/25$, and each receives expected payoff $3(6/25)+2(6/25)=6/5$. Holding $q=2/5$ fixed, every row deviation $p^{\prime }$ gives $p^{\prime }(6/5)+(1-p^{\prime })(6/5)=6/5$; holding $p=3/5$ fixed, every column deviation $q^{\prime }$ gives $q^{\prime }(6/5)+(1-q^{\prime })(6/5)=6/5$. This directly verifies the Nash equilibrium inequalities.

Both coordinated pure strategy outcomes strictly improve both players' expected payoffs over $(6/5,6/5)$: $(3,2)$ and $(2,3)$ each do so. The mixed Nash equilibrium therefore fails Pareto efficiency, even though no unilateral deviation helps. Switching together can help when switching alone cannot. Neither coordinated outcome improves both players over the other, and both are Pareto efficient, even when a lottery over joint action profiles is allowed: any positive weight on another outcome reduces the payoff of the player receiving $3$.

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.

A finite game represented succinctly by propositional logic. Each player controls a disjoint collection of Boolean variables and chooses their truth values. Together those choices determine a Boolean valuation. A player's goal is a propositional formula, with payoff one if satisfied and zero otherwise. The control sets normally form a set partition of all variables.

A pure strategy strategy profile is a Nash equilibrium if every unsatisfied player remains unsatisfied after every change to that player's controlled variables. Checking a candidate can therefore require solving a Boolean satisfiability problem, even though evaluating its current payoffs is easy.

Given a succinct Boolean game and a complete pure strategy strategy profile, determine whether it is a Nash equilibrium. The problem is co-NP-complete for goal propositional formulas, even with one player. This differs from existential equilibrium checking in a Boolean game, which searches for some qualifying Nash equilibrium.

A negative instance has a short complexity certificate: a currently unsatisfied player and new truth values for that player's controlled Boolean variables that make the goal true. Evaluating the current and changed propositional formulas takes polynomial time, proving membership in co-NP.

For hardness, given a propositional formula $F(X)$, let one player control $X$ and a fresh variable $z$, with goal $z\wedge F(X)$. The all-false candidate has payoff zero. It is a Nash equilibrium exactly when $F$ is an unsatisfiable Boolean formula, since any satisfying assignment permits an improvement by also setting $z$ true. This is a polynomial-time many-one reduction from unsatisfiability. The fresh guard ensures that the candidate loses independently of the input formula's value there.

In a two-player constant-sum game, the sum of the two payoffs is the same constant $K$ at every strategy profile. Replacing each player's payoff by $u_i-K/2$ gives a zero-sum game without changing best responses or Nash equilibria. If both players can guarantee $K/2$, then any Nash equilibrium gives each that value. An equilibrium in pure strategies must use pure strategies with that guarantee: otherwise the opponent could improve on $K/2$ by a unilateral deviation.

A strategy profile in which each player uses a dominant strategy. Every such profile is a Nash equilibrium, since each prescribed choice is a best response to the actual opposing choices in particular. The converse fails: a Nash equilibrium only requires a best response to those actual choices. With the weak convention for dominant strategy, ties are allowed; a strictly dominant strategy requires strict improvement over every alternative against every opposing profile.

For a finite game, let $s=(s_1,\dots ,s_n)$ range over all pure strategy strategy profiles, and let ${\sigma }_j(s_j)$ be player $j$'s probability of choosing $s_j$. Under independent mixed strategies, the probability of $s$ is ${\prod }_j{\sigma }_j(s_j)$. The displayed sum is the expected value of player $i$'s payoff. Holding everyone else's mixed strategy fixed makes $U_i$ a linear function of ${\sigma }_i$; this is why checking pure strategy deviations suffices to check all mixed strategy deviations.

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.

Both players choose heads $H$ or tails $T$ without seeing the other's choice. The row player receives $1$ when the choices match and $-1$ when they differ; the column player receives the opposite payoff. Thus matching pennies is a zero-sum game, with ordered payoff pairs:

At $(H,H)$ the column player improves by switching to $T$; at $(H,T)$ the row player improves by switching to $T$; at $(T,H)$ the row player improves by switching to $H$; at $(T,T)$ the column player improves by switching to $H$. Every pure strategy strategy profile therefore has a profitable unilateral deviation, so none is a Nash equilibrium.

Let $p$ be the row player's probability of heads and $q$ the column player's probability of heads. Their random choices are independent. Against fixed $q$, the row player's pure-choice expected payoffs areAgainst fixed $p$, the column player's pure-choice expected payoffs areConsequently the best responses, expressed as allowed heads probabilities, areHere $[0,1]$ means every mixture is a best response, including both pure strategies. If $q>1/2$, the row player must choose $p=1$, which makes the column player's best response $q=0$, a contradiction. If $q<1/2$, the row player must choose $p=0$, which forces $q=1$, also a contradiction. Hence $q=1/2$; for the column player to mix at this $q$, the two column payoffs must tie, forcing $p=1/2$. The unique Nash equilibrium is thereforeIndeed, for any $p,q$, $U_1(p,q)=(2p-1)(2q-1)$ and $U_2(p,q)=-U_1(p,q)$. Holding $q=1/2$ gives the row player zero for every deviation $p^{\prime }$; holding $p=1/2$ gives the column player zero for every deviation $q^{\prime }$. A player is indifferent against the equilibrium mixture, but choosing an arbitrary best response to it need not preserve the opponent's best response. This is why that indifference does not produce additional Nash equilibria.

For a teaching treatment with the same payoff convention, see MIT 17.810, lecture 3, slides 29–38, on mixed strategies and matching pennies.

A Nash equilibrium is a strategy profile in which every player's strategy is a best response to the others. For a finite game and mixed strategies, its precise condition isThe opponents' strategies ${\sigma }_{-i}^{\ast }$ are held fixed while testing each unilateral deviation. Equality is allowed: a player may have other equally good best responses. Because expected payoff is a linear function of the player's own mixture, it suffices to test every pure strategy. Equivalently, every choice in the support of a mixed strategy must attain the largest pure-choice expected payoff, and no unused choice may exceed it.

The two worked examples illustrate different uses of this condition. Matching pennies has no pure strategy Nash equilibrium, but its unique mixed strategy Nash equilibrium removes each player's vulnerability to predictable play. The asymmetric coordination example has three Nash equilibria, and its mixed one fails Pareto efficiency. A Nash equilibrium tests individual incentives, whereas Pareto efficiency compares feasible outcomes that may require several players to change together. In the prisoner's dilemma, for example, mutual defection is a Nash equilibrium even though mutual cooperation gives both players a larger payoff because $R>P$.

Existence in a finite game is guaranteed by Nash's theorem. The theorem does not select one Nash equilibrium, promise Pareto efficiency, or assert convergence of a learning process. Nash's ^[ref] used the Kakutani fixed-point theorem; his ^[ref] gave a proof using the Brouwer fixed-point theorem. The connection to a fixed point captures the idea of choices that remain mutually optimal when considered together.

For a finite normal-form game, a mixed strategy ${\sigma }_i$ is a probability distribution over player $i$'s pure strategies. Independent randomization by the players defines an expected payoff $u_i(\sigma )$. A strategy profile $\sigma$ is a Nash equilibrium iffor every player $i$ and every alternative mixed strategy ${\tau }_i$. By linearity in a player's own distribution, it is enough to check all pure deviations. Equivalently, every pure strategy in the support of a mixed strategy must be a best response to the other players' choices.

Under the intended positive rewards $0<h<d$, a hunter at the all-hare strategy profile receives $h$. A unilateral switch to deer leaves only one participant. Since the integer threshold satisfies $k>n/2$ with $n\ge 3$, we have $k\ge 2$, so that deer hunt fails and pays zero. Thus no player can gain by switching, and the all-hare profile is a Nash equilibrium. At $h=0$ it remains an equilibrium through indifference; negative $h$ would invalidate the claim.

The players are the two chains, each with the set of pure strategies $\{1,2,3,4,5\}$. A strategy profile $(x,y)$ gives the sites of $S$ and $C$. For later use, write the first player's payoff for a general street size asWhen $x<y$, count customers to the left of $(x+y)/2$, assigning value one rather than two to any midpoint customer. This gives $x+y-1$ whether the midpoint is an occupied building or lies between buildings. The other player receives $2k-u(x,y)$. At co-location, every customer's value is split, giving $k$ each.

For $k=5$, the payoff matrix for $S$ isRows and columns are indexed by sites $1,\dots ,5$; the full ordered payoff pair in cell $(x,y)$ is $(M_{xy},10-M_{xy})$. This discrete location game is a constant-sum game.

There is no pure Nash equilibrium. If the firms choose different sites, $S$ serves at least its own building, so $C$ receives less than $2k$. By moving onto $S$'s site, $C$ makes every customer equidistant from the two shops and wins every tie, obtaining $2k$. Thus any separated profile has a profitable unilateral deviation by $C$.

At any co-located profile, $S$ receives zero. It can move to a different site and capture at least that site's customers, obtaining at least two. Thus every co-located profile also has a profitable unilateral deviation. These cases exhaust all pure strategy profiles.

As literally stated, the claim is false. Give player one two pure actions, with payoffs one and zero against every opposing action. A mixed strategy assigning probability one to the first action has exactly that action's payoffs, so very weakly dominates it under the printed non-strict inequality. The other pure action nevertheless fails to dominate it.

The intended statement becomes true if the mixture gives positive probability to some distinct action, equivalently $p_i<1$. Fix any opposing pure strategy profile at which $s_i$ pays one. Since all payoffs are in $\{0,1\}$,Equality forces every positive-probability supported action to pay one there. At a profile where $s_i$ pays zero, every other action already pays at least zero. Therefore every action in the support of a mixed strategy is no worse than $s_i$ against every opposing profile. Choosing a distinct supported action proves the corrected conclusion: nontrivial mixed very weak dominance implies very weak domination by a distinct pure action. This proof does not insert the missing support condition silently.

A pure action is weakly dominated by a mixture when the mixture's expected payoff is at least as high against every opposing pure strategy profile, and strictly higher against at least one. The latter condition automatically rules out the mixture concentrated on the original action.

Yes: the pure-domination conclusion remains true for this weak version. The argument in part (c) shows that every positively supported action is no worse than the original everywhere. At a profile with strict mixed improvement, the original binary payoff must be zero and the mixed expected payoff positive. Some positively supported action therefore pays one there. It is distinct from the original, very weakly dominates it everywhere, and improves strictly at that profile. Thus it weakly dominates the original pure action. Not every supported action must improve strictly somewhere; selecting one from an actual strict-improvement profile is essential.

The equilibrium assignment is $(S_1,S_2,S_3,S_4)\mapsto (r_2,r_3,r_4,r_1)$, with utility vector $(0.7,0.7,0.9,0.4)$. Apply backward induction to the finite perfect-information game, accounting for the two friendship pairs in every terminal assignment. Student $S_4$ receives the last room and has no remaining choice. Given the first two rooms, $S_3$ chooses the remaining room maximizing their own room value plus $0.4$ if adjacent to $S_2$.

The following complete third-stage comparisons summarize the continuations. The utility in the last column is $S_2$'s resulting utility, after $S_3$ makes the indicated best response.

For example, after $S_1$ takes $r_2$ and $S_2$ takes $r_3$, student $S_3$ compares $r_1$, giving $0$, with $r_4$, giving $0.5+0.4=0.9$. Choosing $r_4$ also gives $S_2$ the adjacency bonus, making $U_2=0.3+0.4=0.7$. The last room $r_1$ is adjacent to $S_1$'s $r_2$.

The table makes $S_2$ choose $r_3,r_3,r_2,r_2$ after first-stage choices $r_1,r_2,r_3,r_4$, respectively. Their resulting consequences for $S_1$ are $0.5,0.7,0$, and either $0$ or $0.4$. Thus $S_1$ strictly prefers $r_2$, proving the displayed outcome.

There is an off-path tie for $S_3$ after $(r_4,r_2)$, so the entire subgame perfect equilibrium strategy profile need not be unique. Either choice, or any mixture of them, gives $S_1$ at most $0.4$ after choosing $r_4$, below $0.7$. The equilibrium assignment on the played path is therefore unaffected by this tie. Specifying these optimal continuations at every history, including the unplayed ones, supplies a subgame perfect equilibrium rather than merely a proposed path.

The definition in this part uses a single Boolean valuation, so the relevant Nash equilibria are pure strategy equilibria of a Boolean game. Use its standard convention that the players' control sets form a set partition of the variables.

Membership follows from an existential choice of a strategy profile and a universal check of all unilateral deviations. Assign payoff one to satisfying a player's goal and zero otherwise. A strategy profile $\sigma$ is a Nash equilibrium precisely when, for every player $i$ and every alternative Boolean valuation ${\tau }_i$ of that player's variables,is true: either the goal is already satisfied or no deviation can satisfy it. Thus the requested property isThe strings encoding $\sigma$, $i$ and ${\tau }_i$ have polynomial length, and evaluating the bracketed propositional formulas takes polynomial time. Invalid encodings of a player index can simply be ignored by the test. This is the existential second level of the polynomial hierarchy, ${\Sigma }_2^{\mathrm{P}}$.

For hardness, reduce the canonical complete problem of deciding a two-block quantified Boolean formulaMake a two-player Boolean game: player 1 controls $X$ and has goal ${\gamma }_1=\top$; player 2 controls $Y$ and has goal ${\gamma }_2=\neg \psi$. Set the query formula to $\varphi =\psi$. The construction has size linear in the input formula.

If an assignment $x$ satisfies $\forall Y\psi (x,Y)$, combine it with any assignment $y$. Player 1 already satisfies its goal, and player 2 cannot satisfy $\neg \psi$ by any unilateral deviation. Thus $(x,y)$ is a Nash equilibrium satisfying the query.

Conversely, let $(x,y)$ be a Nash equilibrium satisfying $\psi$. Player 2 currently has payoff zero. If some alternative $y^{\prime }$ made $\psi (x,y^{\prime })$ false, that deviation would satisfy player 2's goal and increase its payoff to one. The Nash equilibrium condition therefore implies $\forall Y\psi (x,Y)$. This proves the required equivalence and the polynomial-time reduction.

Together, membership and hardness prove ${\Sigma }_2^{\mathrm{P}}$-completeness of existential equilibrium checking in a Boolean game. The reduction works with only two players and one constant goal.

A payoff is the number assigned to a player's outcome at a strategy profile, with larger numbers preferred. In the usual expected utility model, expected payoffs are probability-weighted averages of these numbers. If a payoff is specified as money and a player has preferences involving risk, first apply the relevant utility function; maximizing expected money assumes risk neutrality. In a two-player zero-sum game, one player's payoff is the negative of the other's. General bimatrix games instead require a payoff matrix for each player.

A pure strategy is a definite, complete plan for a player's choices. In a game with one simultaneous choice, it selects one available action with certainty: heads or tails in matching pennies, for example. In a sequential game it specifies an action at every situation where that player could be called upon to move, including situations never reached when the plan is followed. The plan can use only information available to the player: indistinguishable decision situations must prescribe the same action. An action at one such situation is only part of the plan.

If $S_i$ is player $i$'s set of pure strategies, the payoff $u_i(s_i,s_{-i})$ depends on the whole strategy profile. Thus the same pure strategy can be a best response against one opposing choice and perform poorly against another. A dominant strategy is the stronger case in which it is a best response against every opposing strategy profile.