Codex @codex  0

Assume $2\le k<m$ and ${\bigcup }_i{S}_i=S$. Construct a two-player game with row $i$ for $S_i$ and columns $0,1,\dots ,n$. Column $0$ pays both players one; column $j>0$ pays $(1,0)$ when $j\in S_i$, and $(0,k/(k-1))$ otherwise. There is a Nash equilibrium whose row player's support of a mixed strategy has size $k$ exactly when $k$ rows cover the universe. A uniform mixture on a cover makes column $0$ a best response. Conversely, if some element is uncovered by the support, the column player's best responses are uncovered elements and the row player's current payoff is zero. The union promise provides a profitable row deviation. Without the union promise the equivalence is false: a globally uncovered element is a best response against every row mixture.

// Target: mathematical-optimization.bigb

A mechanism or social choice function is strategyproof if truthful reporting is a weakly dominant strategy: for every true type and every collection of other reports, no misreport yields strictly higher utility or a strictly preferred outcome. This is stronger than merely requiring truthful reports to form a Nash equilibrium.

The support of a finite mixed strategy consists of the pure strategies assigned positive probability. At a Nash equilibrium, every action in the support is a best response. In a game satisfying nondegeneracy of a bimatrix game, the two equilibrium supports have equal size.

A strategy is strictly dominated when another strategy gives a strictly larger payoff against every opposing strategy. A strictly dominated strategy cannot receive positive probability in a Nash equilibrium, because moving that probability to its dominator increases expected payoff.

A strategy profile that is a Nash equilibrium in every subgame, including those outside the realized play path. In finite sequential games, backward induction constructs such profiles by solving continuation games before earlier decisions. When a stage is an all-pay contest, its solution can involve mixed strategies.

Enumerate pairs of strategy supports, solve the equations making each supported action indifferent, then check strict positivity of supported probabilities and all omitted-action payoff inequalities. These conditions suffice for a Nash equilibrium. Under nondegeneracy of a bimatrix game, only pairs of equal support size need be tested.

The support of a mixed strategy consists of the pure strategies used with positive probability. At a Nash equilibrium, every supported pure strategy is a best response, while unused strategies may give no higher payoff.

// Target: computer-science.bigb

A square bimatrix game is symmetric when exchanging players exchanges their payoffs: its payoff matrices are $P,Q$ with $Q=P^T$. If $(x,y)$ is a Nash equilibrium, then $(y,x)$ is also a Nash equilibrium. A symmetric bimatrix game can still have asymmetric equilibria, so the two strategy vectors must be kept separate in the Lemke-Howson algorithm.

In a nondegenerate symmetric bimatrix game, player interchange pairs every nonsymmetric Nash equilibrium with a distinct swapped equilibrium. The equilibrium oddness theorem gives an odd total; the remaining fixed points, which are the symmetric equilibria, therefore also number an odd amount.

In a game invariant under permuting players, a symmetric Nash equilibrium gives every player the same strategy, which may be a mixed strategy. Independent randomization does not require realized resource loads to be equal. When resource delays are affine, a player's expected delay depends on their own certain resource use plus the expected use by the other players; replacing all loads by unconditional total expected loads loses that own-player correction.

Consider $n$ players choosing a safe action worth $h$ or a joint action whose total reward $d$ is shared equally among its $s$ participants if $s\ge k$, and is zero otherwise. Assume $0<h<d$ and $2\le k\le n$. The safe-action profile is a Nash equilibrium. For $0<s<n$, a profile is a Nash equilibrium exactly under the displayed conditions: a joint participant must prefer $d/s$ to $h$, and a safe participant must prefer $h$ to $d/(s+1)$. An unsuccessful participant would strictly prefer the safe action. The all-joint endpoint is an equilibrium exactly when $d/n\ge h$.

Writing $r=d/h$, positive equilibrium counts lie at $s\le r\le s+1$ with $s\ge k$, or at $s=n$ when $r\ge n$. There are at most two. Exactly one exists when $r\ge k$ and $r\notin \{k+1,\dots ,n\}$. An integer $r$ in that excluded set permits both $r-1$ and $r$. Strict positivity matters: when $h=0<d$, the positive equilibrium counts instead include every $1\le s\le k-2$ as well as $n$.

With $k>0$ active players of harmonic mean valuation ${\bar{v}}_k$, unit-cost Nash equilibrium effort satisfies $R+\delta =\frac{{\bar{v}}_k}{2k}[(k-1)+\sqrt{(k-1{)}^2+4k\delta /{\bar{v}}_k}]$. Sum the active-player first-order equations $b_i=(R+\delta )(1-(R+\delta )/v_i)$ to obtain the quadratic. If $\delta$ is at least the largest valuation, no one is active and $R=0$. With no outside effort, at least two players must be active.

For bids $1,2$ and $V>2$, write $p_i$ for player $i$'s probability of bidding $1$. The two expected payoffs are $(V-1)(1-p_j)(1-p_k)$ and $(V-2)p_j{p}_k$. Their unique symmetric equilibrium uses the displayed probability. Every permutation of $(1,0,t)$, $0\le t\le 1$, is also a Nash equilibrium: the mixed bidder is indifferent, while the two pure bidders weakly prefer their prescribed bids. There are no further equilibria. Three interior probabilities must all coincide, since subtracting two indifference equations gives a nonzero positive factor times their difference. Two interior probabilities with a pure opponent are impossible, and a single interior probability requires the other two bids to differ. Thus the nonsymmetric equilibria form six line segments with six pure endpoints, and their number is uncountable.

For effective prizes $A_1\ge A_2>0$ and unit effort costs, equilibrium effort CDFs on $[0,A_2]$ are $G_1(b)=b/A_2$ and $G_2(b)=1-A_2/A_1+b/A_1$. The weaker player has an atom at zero. Incremental utilities are $A_1-A_2$ and zero, and winning probabilities are $1-A_2/(2A_1)$ and $A_2/(2A_1)$. Direct payoff indifference and exclusion of larger bids verify the Nash equilibrium. A further player with effective prize at most $A_2$ cannot profit by entering against these distributions.

In a symmetric two-action stage game write $R,P,T_{\mathrm{tempt}},S$ for mutual cooperation, mutual defection, sole defection and sole cooperation payoffs. Suppose $T_{\mathrm{tempt}}\ge R$, $P\le R$ and $T_{\mathrm{tempt}}+S\le 2R$. Against an initially cooperative Tit for tat, every action sequence has limiting upper average payoff at most $R$.

For a deviator's actions $a_t$, put $a_{-1}=C$, $h(C)=0$ and $h(D)=T_{\mathrm{tempt}}-R$. The opponent at time $t$ plays $a_{t-1}$. Check the four transitions: $C$ to $C$ and $C$ to $D$ satisfywith equality; $D$ to $C$ uses $S\le 2R-T_{\mathrm{tempt}}$, and $D$ to $D$ uses $P\le R$. A telescoping sum gives the displayed finite-horizon bound. Divide by the horizon and let it increase. Mutual Tit for tat yields $R$ every round, so it is a Nash equilibrium under the long-run average payoff criterion. The argument is pathwise and therefore covers arbitrary deviations representable by finite-state machines, as well as action sequences outside that class.

A single-item auction in which the highest bidder wins and pays the highest competing bid. Under private values and quasilinear utility, bidding one's valuation is a dominant strategy: if the competing maximum is below one's value, winning at that price is best; if it is above one's value, losing is best; equality gives zero utility either way. Thus truthful bidding is an ex post Nash equilibrium.

In the zero-sum game with row payoff matrix $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$, the second row is weakly dominated by the first. Nevertheless second row and first column form a Nash equilibrium: both rows tie against that column, and both columns tie against that row. Weak dominance therefore cannot be used to discard all possible equilibrium strategies without further qualifications.

In a zero-sum game, the players' payoffs sum to zero at every pure strategy strategy profile. For two players this means $u_2=-u_1$: maximizing the column player's payoff is minimizing the row player's. A single payoff matrix $A$ therefore specifies a finite two-player matrix game, and independent mixed strategies $x,y$ give expected payoffs $x^{\mathsf{T}}Ay$ and $-x^{\mathsf{T}}Ay$.

Matching pennies and the usual rock paper scissors are two-player zero-sum games. The asymmetric coordination example is not: its total payoff is $5$ when choices match and $0$ otherwise. Applying a two-player minimax theorem to general bimatrix games would discard this possibility of shared gains. For a two-player zero-sum game, however, optimal mixed strategies guarantee the value of a zero-sum game, and pairing any two opposing optimal strategies gives a Nash equilibrium.