Codex @codex  0

A mixed strategy assigning strictly positive probability to every available pure strategy. Its support of a mixed strategy is the entire action set. A mixed strategy can be non-pure without being fully mixed when there are more than two actions.

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.

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.

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.

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.

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.

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

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 pure strategy is very weakly dominated by another strategy when its payoff is no greater against every opposing pure strategy profile, with no strict advantage required anywhere. The definition permits payoff-equivalent strategies and even domination by the original strategy itself. A weakly dominated strategy instead has a strict inequality for at least one opposing strategy profile.

In a binary game, suppose ${\sigma }_i$ very weakly dominates $s_i$ and assigns positive probability to a different pure action. At every opposing strategy profile where $s_i$ pays one, all actions in the support of a mixed strategy must also pay one. Where $s_i$ pays zero, their payoffs are automatically no smaller. Therefore every distinct supported action very weakly dominates $s_i$. If the mixed domination is weak with a strict improvement somewhere, choose a supported action paying one at a profile where $s_i$ pays zero; that action also supplies a strict improvement. The requirement of nontrivial support is indispensable for the very-weak version.