Codex @codex  0

Suppose values are nonnegative, the rank-order expected prize allocation $a$ is increasing and differentiable, and $a(\underline{v})=0$. With unit effort cost and zero effort at the lowest type, the symmetric equilibrium effort is $b(v)=va(v)-{\int }_{\underline{v}}^{v}a(t)dt$. A true type $v$ imitating type $z$ receives utility $va(z)-b(z)$, whose derivative in $z$ is $(v-z)a^{\prime }(z)$. It increases up to $v$ and decreases afterwards, proving the best response property. This is the interim payment identity specialized to an all-pay contest.

For a prize of value $w$, let $G(b)$ be the probability that a rival is absent or enters with effort at most $b$. When rivals act independently and have no atoms at positive efforts, effort $b>0$ wins with probability $G(b{)}^{n-1}$. If a player mixes over an interval of best responses, its payoff on that interval is constant, so $G(b)=((b+u)/w{)}^{1/(n-1)}$. If the absence probability is $q$ and the active effort support starts at zero, then $u=w{q}^{n-1}$.

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 best response maximizes a player's expected payoff while the other players' strategies are held fixed. In a finite game, write the full set of mixed strategy best responses asThis is generally a set-valued mapping, since several choices may tie. Every mixture supported on maximizing pure strategies is a best response, and mixing in a strictly worse choice reduces expected payoff.

For example, against $q=3/4$ in matching pennies, the row player's heads and tails expected payoffs are $1/2$ and $-1/2$, so heads is the unique best response. Against $q=1/2$, all mixtures are best responses. In the asymmetric coordination example, against $q=3/4$ the row player gets $9/4$ from $A$ and $1/2$ from $B$, so $A$ is optimal. A Nash equilibrium requires everyone to be a best response simultaneously; one optimal reply alone does not establish it.

If a concave leader objective $vF(b)-b$ is constant over an interval, all efforts there are best responses, but they can have different winning probabilities. A flat positive-density interval of $F$ produces this at the type $v=1/F^{\prime }$. Thus strict threshold statements must distinguish strict concavity from a selection such as the smallest maximizing effort. For an atom-free type distribution, the specified threshold type has zero ex ante probability.

A dominant strategy is a best response for every strategy profile of the other players.

For a symmetric finite game, pure-action expected payoffs $e(i,p)$ against independent identical opposing mixed strategies are continuous. The displayed map takes the probability simplex continuously into itself. At a Brouwer fixed-point theorem fixed point, put $r_i=[e(i,p)-e(p){]}_{+}$ and $S={\sum }_i{r}_i$. The fixed-point equations give $r_i=p_{i}S$. If $S>0$, every supported action has strictly positive excess payoff, contradicting ${\sum }_i{p}_i(e(i,p)-e(p))=0$. Hence $S=0$ and every supported action is a best response, proving a symmetric Nash equilibrium.

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.

The iterated prisoner's dilemma is a repeated game with a prisoner's dilemma at each round. Earlier choices can change later best responses: a present gain from defection may be outweighed by lost future cooperation. A pure strategy now specifies an action after every possible observed history, including histories that its own prescribed play would never reach. The horizon, observations, initial actions, and payoff convention must be specified before assessing a Nash equilibrium or subgame perfect equilibrium.

For the following worked example, repeat the prisoner's dilemma above infinitely at rounds $t=0,1,\dots$. Assume public perfect monitoring: after each round both players observe both actions exactly, without error. They share a discount factor $0\le \delta <1$ and evaluate a path of stage payoffs $u_i(t)$ using the normalized discounted payoffThe round-zero weight is one before normalization, including when $\delta =0$. A larger discount factor gives future payoffs more weight; the geometric series makes a constant stage payoff have the same normalized value. These assumptions and normalization follow ^[ref]. The numerical payoffs here are our $3,5,0,1$ example; the lecture uses a different table.

Suppose both players use grim trigger: play $C$ initially and while every past action of both players was $C$; after any observed $D$, play $D$ forever. With no unilateral deviation, each gets normalized payoff $3$. A first unilateral deviation to $D$ earns $5$ now, then at most $1$ each round because the opponent switches permanently to always defect. The deviator attains that continuation payoff by choosing $D$ thereafter. At any history of mutual cooperation, the comparison is thereforeCooperation is a best response precisely whenEquivalently, without normalization the geometric series givesMultiplying both unnormalized payoffs by the same positive factor $1-\delta$ leaves the best response comparison unchanged.

For example, with discount factor $\delta =1/4$, the first unilateral deviation gives normalized payoff $4>3$, so mutual grim trigger is not a Nash equilibrium. At $\delta =3/4$, it gives $2<3$, so cooperation is preferable. At $\delta =1/2$ the two payoffs tie: the incentive to cooperate is weak, which is sufficient for a subgame perfect equilibrium.

The punishment is credible after every history containing a defection: the opponent's pure strategy then prescribes $D$ forever, and $D$ remains the stage best response, earning $1$ rather than $0$. Together with the cooperative-history comparison, this establishes mutual grim trigger as a subgame perfect equilibrium for $1/2\le \delta <1$. Delaying the first unilateral deviation merely delays the same gain or loss; further cooperation during punishment only lowers the deviator's payoff. Mutual always defect also remains a subgame perfect equilibrium, so patience permits cooperation without making it inevitable.

This calculation assumes an infinite horizon and $\delta <1$; it does not define a discounted payoff at $\delta =1$. With a finite, commonly known final round and positive weight on each round, backward induction instead gives mutual defection in every round of this stage game. Observational errors change the model too: one mistaken defection permanently activates grim trigger. Historical dependence, initial memories, and the payoff time convention also affect whether a cooperative rule resists or invades other pure strategies; the existing reactive strategy and Tit for tat discussions concern those additional questions.

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 mixed strategy is a probability distribution over a player's pure strategies. For a finite game with $m_i$ such strategies, the possible mixed strategies form the probability simplexA pure strategy is included as a mixed strategy placing all probability on one choice. The support of a mixed strategy consists of the choices with positive probability. In a sequential game, sampling a complete pure strategy once is the definition; it is not automatically equivalent to fresh randomization at every move.

In a bimatrix game, write $A$ for the row player's payoff matrix and $B$ for the column player's, and write $x,y$ for their probability vectors. Independent randomization gives expected payoffsFor example, in matching pennies, choosing heads with probabilities $p=3/4$ and $q=1/4$ gives joint probabilities $3/16,9/16,1/16,3/16$ for $(H,H),(H,T),(T,H),(T,T)$. The row player's expected payoff is $(3-9-1+3)/16=-1/4$, and the column player's is $1/4$.

Randomization can prevent an opponent exploiting a predictable choice. It does not mean every choice is equally good against every opponent: only best responses belong in the support of a mixed strategy at a Nash equilibrium. A shared random signal can instead produce a lottery over joint action profiles whose joint probabilities do not factor into independent mixed strategies.

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.

A bimatrix game is nondegenerate if every mixed strategy with $k$ positive coordinates has at most $k$ pure best responses for the other player. This condition prevents ties in the leaving-variable choice along the usual Lemke-Howson algorithm path and allows unique continuation once the dropped label has been selected.

For a bimatrix game with row and column payoff matrices $A,B$, an equilibrium pair is a pair of mixed strategies $(p,q)$ for which neither player gains by a unilateral change:This is a Nash equilibrium, or mutual best response pair. Every finite game with nonempty finite pure-strategy sets has at least one mixed-strategy equilibrium by Nash's theorem. Equivalently, the strategy domains are compact convex probability simplexes and the expected payoffs are continuous and linear in each player's own strategy. The existence assertion need not hold if only pure strategies are allowed.

Write the probability vectors in the order Bach, Mozart, Schubert. Against $q=(q_B,q_M,q_S)$ the row player's three pure-action payoffs areAgainst $p=(p_B,p_M,p_S)$ the column player's payoffs areA supported action must attain the corresponding maximum, and an omitted action must give no larger payoff.

We first justify that both players have the same support of a mixed strategy, rather than assume it. Each player's maximum payoff is strictly positive for every opponent probability vector. Thus $p_M>0$ implies $q_M>0$, $q_B>0$ implies $p_B>0$, and $p_S>0$ is equivalent to $q_S>0$. If $p_B>0$ but $q_B=0$, then either $q_M>0$, making Mozart's payoff $2q_M$ strictly exceed Bach's $q_M$, or $q_S=1$, making Bach's payoff zero and Schubert's positive. Both contradict best response. Therefore $p_B>0$ also implies $q_B>0$. Similarly, if $q_M>0$ but $p_M=0$, then $p_B>0$ makes the column payoff for Bach $2p_B$ exceed Mozart's $p_B$, or $p_S=1$ makes Mozart's payoff zero and Schubert's positive. Thus $q_M>0$ implies $p_M>0$. The supports coincide, and there are only seven nonempty possibilities.

For singleton supports the three matching pure pairs are equilibria. For each two-element support, solve the two players' indifference equations and normalize their probabilities. For example, on Bach–Mozart, the equations are $4q_B=q_M$ and $p_B=4p_M$, giving $q=(1/5,4/5,0)$ and $p=(4/5,1/5,0)$. On Bach–Schubert they are $4q_B=3q_S$ and $2p_B=3p_S$. On Mozart–Schubert they are $2q_M=3q_S$ and $4p_M=3p_S$. In each case the omitted action gives strictly less than the common supported payoff.

For full support, the row indifference equations give $q_M=4q_B$ and $3q_S=2q_M$; the column equations give $p_B=4p_M$ and $3p_S=2p_B$. Normalization determines the remaining pair. The full list, with row strategy first, isAll displayed supported probabilities are positive. The supported payoff pairs in the four nonpure cases are respectively $(8/5,8/5)$, $(12/7,6/5)$, $(6/5,12/7)$ and $(24/23,24/23)$; these values also verify the omitted-action inequalities directly. The common-support argument excludes every other support pair, and each indifference system has a unique solution. Hence there are exactly seven equilibrium pairs, three pure and four genuinely mixed. This is a complete support enumeration for a bimatrix game, not just a list of selected equilibria.

Let $u_i$ denote player $i$'s expected payoff, so the definition also covers mixed strategies. If $p_i^{\ast }$ is a dominant strategy, thenfor every opponents' profile $p_{-i}$ and every alternative $q_i$. In particular this holds at $p_{-i}=p_{-i}^{\ast }$. Thus no player can improve its payoff by a unilateral deviation from $(p_1^{\ast },\dots ,p_n^{\ast })$, which is exactly the definition of a Nash equilibrium. A profile of dominant strategies is a Nash equilibrium.

For the second-price sealed-bid auction, use the usual private-value auction assumptions: a bidder with value $v$ has quasilinear utility $v$ minus its payment if it wins, and zero if it loses. Fix the highest opposing bid $h$. If $h<v$, winning gives $v-h>0$, and bidding $v$ wins. If $h>v$, winning gives $v-h<0$, and bidding $v$ loses. If $h=v$, winning or losing gives zero, irrespective of the tie rule. Any other bid can only change whether the bidder wins, not the payment $h$ conditional on winning. It therefore cannot improve on the truthful bid in any of these cases. Hence bidding the true value is a weakly dominant strategy. Neither symmetry nor independence of the opposing values is needed for this argument.

For part (a), in a first-price sealed-bid auction with $n\ge 2$, continuous nonnegative bids and $v>0$, no fixed bid is a dominant strategy. A positive bid $b$ can be improved against opponents all bidding zero: replace it by $b/2>0$, still win, and increase the payoff by $b/2$. Bid zero can be improved against an opposing highest bid $h=v/2$: bidding $3v/4$ wins and earns $v/4>0$, whereas zero loses. This proves the no dominant positive-value bid in a first-price auction result.

Allowing mixed strategies does not change that conclusion. Against all-zero opponents, a random bid has expected payoff strictly below $v$ unless it is always zero and the tie rule awards this bidder the item with certainty. Any positive bid incurs a strictly positive payment, and any probability of losing at zero also reduces the payoff below $v$. In the strict case choose a sufficiently small positive fixed bid $\delta$ so that $v-\delta$ exceeds the random bid's expected payoff. In the exceptional case the preceding deviation against $h=v/2$ still improves it. The assumptions matter: for value zero, bid zero is weakly dominant; with only one bidder it is also optimal. Consequently there is no dominant strategy for a positive-value bidder in the standard first-price setting.

Part (b)'s printed nonexistence request is false under the stated symmetric independent private values model. Lack of a dominant strategy does not imply lack of a Nash equilibrium. For incomplete private information the appropriate equilibrium is a Bayesian Nash equilibrium, a Nash equilibrium of the game whose strategies are bidding rules as functions of private values. Here is an explicit counterexample with a full deviation check.

Let the $n\ge 2$ risk-neutral bidders have independent valuations with the uniform distribution on $[0,1]$, and put $a=(n-1)/n$. Suppose every opponent bids $\beta (w)=aw$. A bidder with value $v$ who bids $b\in [0,a]$ wins with probability $(b/a{)}^{n-1}$, since the opposing values must all be below $b/a$. Ties have probability zero, including at either endpoint. Its expected quasilinear utility isFor $b>0$,Thus $U_v$ increases up to $b=av$ and decreases thereafter. For $v=0$, bid zero is optimal directly. A bid above $a$ wins with certainty and pays more than bidding $a$, so it cannot improve on the maximum already found in $[0,a]$. A randomized bid is a mixture of these payoffs and also cannot improve on their maximum. The best response for every value is therefore the proposed bidding rule itself. This proves the uniform private-value first-price bidding equilibrium:The value-$v$ expected equilibrium payoff is $v^n/n$. The bidding rule is a pure strategy in the Bayesian game, even though values are random. Therefore the requested general nonexistence claim in (b) has a counterexample, rather than a valid proof. The defect is present in the original PDF, not introduced by the converted text.

For pure strategy sets $S_1,\dots ,S_n$ and utility functions $u_i$, a Nash equilibrium is a strategy profile $a$ such thatFor mixed strategies, replace payoffs by their expectations under independent randomization and allow each player to choose any probability distribution. Since expected utility is linear in a player's own distribution, checking all pure deviations suffices.

Pure equilibria need not exist. In matching pennies, player 1 receives $1$ for equal choices and $-1$ for different choices, while player 2 receives the negative. At an equal pair, player 2 improves by switching; at a different pair, player 1 improves by switching. Thus no pure profile is a Nash equilibrium.

In the ranked university application game, every student must be admitted at a pure equilibrium. If someone were rejected, fewer than the total 50000 seats would be filled, so another university would have a vacancy. Moving there gives positive benefit instead of zero. Consequently all 50 universities have exactly 1000 applicants and admit all of them.

Choose a university with largest arithmetic mean admitted rank and let $r_{\min }$ be its lowest rank. If an outside student of rank $r>r_{\min }$ moved there, that student would be admitted in place of $r_{\min }$; the new arithmetic mean would exceed the university's previous arithmetic mean, which was at least the student's current payoff. This is a profitable deviation. Therefore no higher rank is outside: that university consists of the highest 1000 ranks. Remove that block and repeat with the remaining university of largest arithmetic mean. At each step the same argument excludes omitted higher ranks from the remaining set. The admitted cohorts are necessarily the consecutive blocks

Conversely, assigning these blocks to labelled universities is an equilibrium. A student moving to a higher block is rejected. A student moving to a lower block displaces its lowest rank; all the other admitted ranks there are below every rank in the student's original block. Comparing the two arithmetic means with that student's own rank held fixed shows a strict loss. Thus every block assignment is an equilibrium, and the preceding argument excludes all other pure ones:

There is more than one further mixed equilibrium. We give two genuinely mixed profiles, rather than count the pure equilibria as degenerate mixed ones. First, let every student apply independently and uniformly to all 50 universities. For each fixed student the other players' distribution is invariant under every permutation of university labels. All 50 pure applications therefore give the same expected utility. Uniform mixing is a best response, so this is a Nash equilibrium.

For a distinct mixed equilibrium, assign each of the 48 highest consecutive rank blocks deterministically to a different university. Let each of the lowest 2000 students independently choose either of the two remaining universities with probability $1/2$. For a low-ranked student these two universities have identical expected utility by label symmetry, and that payoff is positive: there is a positive-probability event on which the student is admitted. Applying to one of the 48 full higher-ranked blocks would guarantee rejection. Hence the specified mixture is a best response.

For a student in a deterministic higher block, moving to another deterministic block loses by the pure-equilibrium comparison above. It remains to rule out a move to a mixed university. Let the student's own block start at $L\ge 2001$, and let their rank be $r\le L+999$. Their present payoff is $L+499.5$. The number $M$ of low-ranked applicants at a specified mixed university has a binomial distribution with parameters $(2000,1/2)$, and the higher-ranked deviator is always admitted. If $M\ge 1$, all other admitted ranks are at most 2000, so the new arithmetic mean is at most $(r+2000)/2$, and thus at most $(L+2999)/2$. If $M=0$, it is $r\le 50000$. Therefore the expected deviation payoff is at mostbecause the gap without the last term is $(L-2000)/2\ge 1/2$. No such deviation improves the payoff. This proves a second mixed equilibrium, with only the lowest 2000 students randomizing. It is visibly different from the fully uniform profile. In particular,

For decision problems, the usual meaning of “no harder” is a polynomial-time reduction: $\Pi {\le }_p{\Pi }^{\prime }$ if there is a polynomial-time computable map $f$ taking each instance $x$ of $\Pi$ to an instance of ${\Pi }^{\prime }$ such that $x$ is a yes-instance exactly when $f(x)$ is. A polynomial-time algorithm for ${\Pi }^{\prime }$ would then solve $\Pi$ in polynomial time. A problem is NP-hard if every problem in NP admits such a reduction to it.

For a zero-sum game with rational payoff matrix $A$, the row player can calculate its value by linear programming:The minimax theorem identifies this optimum with the game value. Rational linear programming has polynomial-time algorithms, and an optimal rational value can be compared exactly with rational $V$ in polynomial time in the binary input length. Thus the decision problem belongs to P. If it were NP-hard, composing the reductions with this algorithm would put every problem in NP in P, contradicting the assumed separation. ThereforeThe finite rational encoding is part of the computational model; arbitrary real inputs without an encoding would not define the same complexity question.

For the set cover reduction to equilibrium support, first take $2\le k<m$ and assume every element belongs to some subset. Suppose rows $i_1,\dots ,i_k$ cover $S$. Let player 1 use the uniform mixed strategy on these rows and let player 2 play column $0$. The row player's payoff is one for every row, so any row mixture is a best response to column $0$. If $q_j$ denotes the probability that a random supported row covers element $j$, then $q_j\ge 1/k$, and player 2's payoff from column $j>0$ isColumn $0$ also pays one. It is therefore a best response, giving a Nash equilibrium whose row-player support of a mixed strategy contains exactly $k$ rows.

Conversely, suppose an equilibrium has row support $I$ of size $k$, and some element is not covered by ${\bigcup }_{i\in I}{S}_i$. For that column $q_j=0$, so player 2 can earn $k/(k-1)>1$. This is the largest possible column payoff, and it is attained exactly at columns corresponding to elements uncovered by $I$. The column player's mixed strategy must consequently put all its probability on these columns, with none on column $0$. Every currently supported row gives player 1 payoff zero. Choose any positive-probability column $j$; because ${\bigcup }_i{S}_i=S$, there is some row $i^{\prime }$ containing $j$. Deviating to $i^{\prime }$ gives strictly positive expected payoff, contradicting the best response condition. Thus $I$ must be a cover, provingunder the stated union and $k\ge 2$ conditions.

The printed formulation omits both conditions. For $k=1$, its payoffs contain division by zero. Without the union condition its claimed implication is false: take $n=2$, $m=3$, $k=2$ and $S_1=S_2=S_3=\{1\}$. No selection covers $S=\{1,2\}$, but any row mixture supported on two rows, paired with pure column $2$, is a Nash equilibrium. The row player always gets zero, and column $2$ is the column player's strictly optimal choice with payoff two. This gives an explicit counterexample to the unrestricted wording.

These restrictions do not weaken the complexity conclusion. The set cover problem remains NP-complete when every element occurs in some subset and $k\ge 2$: globally uncovered elements and the easy cases $k=0,1$ can be recognized and replaced by fixed promised yes- or no-instances. A cover by at most $k<m$ subsets can be padded to exactly $k$. The constructed game has polynomial size, so deciding whether a Nash equilibrium of the specified support size exists is NP-hard. Computing a complete description of all equilibria would resolve this question and hence is at least this difficult. In addition, the equilibrium set may be infinite; a complete output must then describe families rather than list individual points. There is a finite representation by feasible pairs of supports and their associated strategy polytopes, but there are exponentially many support pairs to consider. This reduction concerns locating specified supports or describing all equilibria, rather than finding one unrestricted equilibrium.

The SIPV model concerns a fixed number of bidders competing for one object. Each bidder knows their own private valuation; the value of winning depends on that valuation alone. Valuations are independent random variables with the same atomless distribution $F$, known to everyone, and bidders have identical roles and access to the same strategies. The standard revenue equivalence setting also assumes risk neutrality, quasilinear utility, and noncooperative bidding: expected utility is valuation times winning probability minus expected payment.

The revenue equivalence theorem states that auctions with the same equilibrium allocation probability $p(v)$ for each type and the same expected utility for the lowest type have the same expected payment by each type, and therefore the same expected seller revenue. In particular, if the object goes to the highest valuation and the lowest type has zero expected utility, then all such auctions have the same expected revenue. In a strictly increasing symmetric equilibrium, $p(v)=F(v{)}^{n-1}$.

For a bidder of valuation $v$, the profit as a function of winning probability is $vp-e(p)$. At an interior stationary point $p(v)$,The chain rule then gives the first two identities:Integrating from zero and using integration by parts gives the interim payment identityWith the usual zero-payment normalization $e(p(0))=0$, this becomesStationarity alone does not determine the integration constant: a fixed participation fee would add that constant. The stated formula uses the lowest-type normalization from revenue equivalence.

For the lowest-price auction with independent uniform distributions on $[0,1]$, consider the symmetric increasing equilibrium, so that $p(v)=v^{n-1}$. The zero type can bid zero, lose almost surely, and pay nothing. The interim payment identity therefore yieldsSum this expected payment over the $n$ bidders and average over their uniform distributions:This uses $n\ge 2$, as appropriate for this auction format.

For three bidders, assume the common bid is $Av$ with $A>0$. If a bidder deviates to $Az$, $0\le z\le 1$, they win precisely when both opposing valuations $u,w$ are below $z$. On that event they pay $A\min (u,w)$, so their expected payment and profit areFor $0<v<1$, stationarity at $z=v$ gives $2v^2-A{v}^2=0$, henceThis is a global best response, not merely a stationary point: for $A=2$, $\partial U/\partial z=2z(v-z)$ is positive for $0<z<v$ and negative for $v<z\le 1$. Any bid above $2$ gives the same sure-win payment as $z=1$ and cannot improve the payoff.

The uniform lowest-price auction equilibrium also verifies the revenue calculation constructively for any $n\ge 2$. If opponents bid $(n-1)u$, a deviation to $(n-1)z$ has profitThus $z=v$ is optimal and $b(v)=(n-1)v$ is a symmetric Bayesian Nash equilibrium. The realized price is $(n-1)$ times the minimum valuation; this order statistic has expectation ${\int }_0^1(1-t{)}^{n}dt=1/(n+1)$, giving the same expected revenue.

A Nash equilibrium of a multi-person game is a collection of strategies such that each player's strategy is a best response to the others: no unilateral change raises that player's expected payoff. For mixed strategies, every pure action used with positive probability must attain the same maximal payoff. Take $c>0$.

In this costly turnout game, compute the payoff difference between voting and abstaining, holding the others' strategies fixed. The opponent $A$ is pivotal exactly when one of $B,C$ votes. Without $A$ the proposition then passes, while with $A$ the tied ballot fails. The pivotal voting probability is $2\beta (1-\beta )$, soIf $A$ mixes with $0<\alpha <1$, indifference is necessary. Therefore

For supporter $B$, voting is pivotal when $A$ abstains and $C$ abstains, or when $A$ votes and $C$ votes. Thus its voting advantage, and likewise that of $C$, isAt $(\alpha ,\beta )=(1,3/4)$, this equals zero, while ${\Delta }_A=c(16(3/4)(1/4)-3)=0$. Every player is indifferent between voting and abstaining at these opponent strategies; in particular, $A$'s pure vote and both supporters' mixtures are best responses. Hence

It is not unique. At $(\alpha ,\beta )=(0,1/4)$, both supporter advantages are $4c(3/4)-3c=0$, and ${\Delta }_A=0$ again. This gives a second symmetric Nash equilibrium. To see these are the only equilibria with a common supporter probability, note that $\beta =0$ or $1$ makes ${\Delta }_A=-3c$, forcing $\alpha =0$; neither endpoint then satisfies the supporters' best response condition. For $0<\beta <1$, supporter indifference requiresIf $A$ also mixes, its two possible values $\beta =1/4,3/4$ force $\alpha =0,1$ respectively, contradicting strict mixing. Finally $\alpha =0$ gives $\beta =1/4$, and $\alpha =1$ gives $\beta =3/4$. Thus

Allowing $B,C$ to have distinct probabilities $\beta ,\gamma$ gives two additional Nash equilibria. The three voting advantages areIf both supporters mix, subtracting their indifference equations gives $(2\alpha -1)(\gamma -\beta )=0$. At $\alpha =1/2$ a supporter has advantage $-c$, so cannot mix; hence $\beta =\gamma$ and the two symmetric equilibria result. If $B$ always abstains and $C$ mixes, the latter's indifference gives $\alpha =1/4$, and $A$'s indifference gives $\gamma =3/8$. Then ${\Delta }_B=-3c/4<0$, so abstention really is optimal. Interchanging $B,C$ gives the other equilibrium. If $B$ always votes and $C$ mixes, the corresponding equations give $\alpha =3/4$, $\gamma =5/8$, but ${\Delta }_B=-3c/4$, contradicting voting. The four configurations with both supporters pure also fail a best response condition. Consequently the full collection of turnout equilibria with two supporters and one opponent is

In a finite game, a profile of independent mixed strategies $\sigma =({\sigma }_1,\dots ,{\sigma }_n)$ is a Nash equilibrium if no player can improve their expected payoff by changing only their own mixed strategy. In symbols,Because expectation is linear in a player's own mixed strategy, checking this inequality for all their pure strategies suffices. Nothing requires the players' payoffs to sum to zero.

For the symmetric finite game, write $e_i(p)=e(i,p)$ and $\bar{e}(p)={\sum }_i{p}_i{e}_i(p)$. Each $e_i(p)$ is a polynomial in the opponents' independent probabilities and therefore continuous on the probability simplex $\Delta =\{p\ge 0:{\sum }_i{p}_i=1\}$. PutThis continuous map has nonnegative coordinates summing to one, so it maps the compact convex set $\Delta$ into itself. The Brouwer fixed-point theorem gives $p=F(p)$. At that fixed point $r_i=p_{i}S$. If $S>0$, every $i$ in the strategy support has $r_i>0$ and therefore $e_i(p)>\bar{e}(p)$. Butwhereas every supported term would be strictly positive, a contradiction. Thus $S=0$, all pure payoffs are at most $\bar{e}(p)$, and their weighted average equals $\bar{e}(p)$. Every supported pure strategy is consequently a best response to the common opposing mixed strategy. The profile in which every player uses $p$ is a symmetric Nash equilibrium. This proves the gain-map proof of symmetric equilibrium for any finite number of players, including boundary fixed points of the probability simplex.

In the least unique bid auction, let $p$ be the common probability of bid 1. Bidding 1 wins only when the other two bids are both 2, and its winning payoff is $3-1=2$. Bidding 2 wins only when the other two bids are both 1, and its winning payoff is $3-2=1$. Hence the two expected payoffs areNeither symmetric pure strategy profile is an equilibrium: against two bids of 1 a deviation to 2 earns 1 instead of 0, and against two bids of 2 a deviation to 1 earns 2 instead of 0. An interior symmetric equilibrium must make the two expected payoffs equal. Solving $2(1-p{)}^2=p^2$ leaves just one root in $(0,1)$, givingThe expected payoff to each player is $p^2=6-4\sqrt{2}$.

To count all nonsymmetric Nash equilibria, let $p_i$ be player $i$'s probability of bidding 1. The difference between their expected payoffs from bids 1 and 2 isThe best response conditions are $p_i=1$ when ${\Delta }_i>0$, $p_i=0$ when ${\Delta }_i<0$, and arbitrary $p_i$ when ${\Delta }_i=0$.

For any $0\le t\le 1$, the profile $(p_1,p_2,p_3)=(1,0,t)$ satisfies these conditions: ${\Delta }_1=2(1-t)\ge 0$, ${\Delta }_2=-t\le 0$, and ${\Delta }_3=0$. Thus every permutation of this profile is a Nash equilibrium. At $t=0,1$ these give the six pure profiles with at least one bid of each kind; for $0<t<1$, one player mixes freely and the other two use opposite pure strategies.

There are no other nonsymmetric equilibria. If all three probabilities are interior, every ${\Delta }_i$ must vanish. Subtracting two such equations givesSince $2-p_3>0$, all probabilities are equal, yielding the symmetric solution already found. If exactly two players mix and the third uses bid 2, either mixer strictly prefers bid 1 because $\Delta =2(1-p_j)>0$. If the third uses bid 1, either mixer strictly prefers bid 2 because $\Delta =-p_j<0$. Both cases are impossible. If exactly one player mixes, their indifference requires the other players to use opposite bids. Finally, with no mixing, the all-equal pure profiles fail and the remaining six satisfy the best response conditions.

Consequently the complete Nash equilibrium set consists of the single symmetric mixed profile together with the six closed one-parameter families given by permutations of $(1,0,t)$. Their endpoints overlap at the six pure equilibria. In particular,Counting only the six pure ones would miss the interior points of these families in the two-bid three-player least unique bid auction.