Past exam of the computer science course of the University of Oxford / 2019 / Computational game theory / 2

Let $p$ be the row player's probability of $T$. Its expected payoffs against $L$ and $R$ are $6-5p$ and $2+p$. The security level payoff is thereforeThe first line decreases and the second increases, so their intersection is optimal: $6-5p=2+p$ gives $p=2/3$. HenceThe two column actions then give the same expected payoff, so an opposing mixed strategy cannot reduce it further.

The row player's unique best response to $L$ is $B$ and to $R$ is $T$. The column player's unique best response to $T$ is $R$ and to $B$ is $L$. Thus the pure Nash equilibria are $(T,R)$ and $(B,L)$.

For a fully mixed equilibrium, let $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$. Row-player indifference requiresColumn-player indifference requiresBoth probabilities lie strictly between zero and one, so these indifference conditions make both supported actions best responses. Hence the remaining equilibrium isIts expected payoffs are $(8/3,18/7)$. There are no other partly mixed equilibria: if either player is pure, the other's best response is unique, forcing both to be pure. If both mix, the displayed linear indifference equations uniquely determine their probabilities. The row player's equilibrium mixture differs from its maxmin mixture in part (a); these are different optimization criteria in this non-zero-sum game.

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.

Write column $j$ as $((a_j,c_j),(b_j,d_j){)}^T$, where the row player's binary payoff is first. Suppose, for a contradiction, there is no pure Nash equilibrium.

The column player's maximum payoff in the top row must be one. Otherwise every column would be its best response there. To avoid a top-row equilibrium, every column would then need $a_j=0,b_j=1$. But a column maximizing $d_j$ would immediately give a bottom-row equilibrium. The same reasoning with rows exchanged shows that the maximum bottom-row column payoff is also one.

Choose a column with $c_j=1$. To avoid a top-row equilibrium, it must have $a_j=0,b_j=1$. It cannot also have $d_j=1$, because its bottom cell would then be an equilibrium. Hence this column is $((0,1),(1,0){)}^T$, the specified second column type. Exchanging rows forces a column $((1,0),(0,1){)}^T$, the specified first type.

Thus absence of a pure equilibrium forces both forbidden column types to occur. If the given game omits them, this is a contradiction, proving existence of a pure Nash equilibrium. The argument actually proves the stronger statement that omitting either one of the two types suffices.

Compute $C={\max }_j{c}_j$ and $D={\max }_j{d}_j$ in one pass. Scan the columns again: return the top cell of column $j$ if $c_j=C$ and $a_j\ge b_j$, or its bottom cell if $d_j=D$ and $b_j\ge a_j$. Each test is exactly mutual best response, so any returned cell is a pure Nash equilibrium.

If none is found, part (e) supplies columnsLocate one of each and mix with probability $1/2$ on each of those two columns, while the row player mixes $1/2$ on each row. The two row actions then both have expected payoff $1/2$.

To check all opposing deviations, observe that no column can have $(c_j,d_j)=(1,1)$. Such a column would maximize the column player's payoff in either row; choosing a row-player best response within it would give a pure equilibrium, contrary to the failed scan. Therefore every column has $c_j+d_j\le 1$, and against the equal row mixture its expected payoff is at most $1/2$. The two supported columns attain that bound.

Hence the returned half-half profile is a Nash equilibrium against every column, not only the two supported ones. A constant number of scans takes $O(n)$ running time, with constant auxiliary storage if the output mixture is represented by its two supported column indices and probabilities. This is the construction in equilibrium in a two-row binary game.