Past exam of the computer science course of the University of Oxford / 2018 / Computational game theory / 1

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.

With rows and columns ordered Head, Tail, the payoff matrix of ordered pairs isThis is a zero-sum game. There is no pure Nash equilibrium: when the coins match, player 1 gains by switching to a mismatch; when they do not match, player 2 gains by making them match. Since $X,Y>0$, these improvements are strict.

Let $p$ and $q$ be the respective probabilities that players 1 and 2 choose Head. Player 1's payoffs from Head and Tail are $X-(X+2)q$ and $(Y+2)q-2$. Player 2 is indifferent when the corresponding player-1 payoffs against its two pure actions, $Y-(Y+2)p$ and $(X+2)p-2$, agree. The resulting unique fully mixed Nash equilibrium isBoth numbers lie strictly between zero and one. If either player instead used a pure action, the other's unique best response would force the pure-action cycle above, so there are no additional partly mixed equilibria. Substitution gives player 1's expected payoff $(XY-4)/(X+Y+4)$ and its negative for player 2.

For $X=1,Y=3$, the best response correspondences areTheir intersection is $(p,q)=(5/8,3/8)$, with expected payoffs $(-1/8,1/8)$.

Yes: choose $Y=4/X$. The equilibrium expected payoffs are opposite because this is a zero-sum game. They are equal exactly when both are zero. Part (b)'s value vanishes exactly when $XY=4$, and $4/X>0$ for every allowed $X>0$. This establishes both existence and the unique suitable positive choice of $Y$.

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.

Assume $0<h<d$ and the feasible threshold $2\le k\le n$. An unsuccessful deer hunter would gain by switching to hare, so an equilibrium with deer participants must have $s\ge k$. A deer hunter then earns $d/s$ and must not gain by changing to hare; this requires $d/s\ge h$. A hare hunter who joins would earn $d/(s+1)$, so staying with hare requires $h\ge d/(s+1)$. Hence the necessary and sufficient conditions for the stated range $0<s<n$ areThese conditions check every possible unilateral change in this two-action game, so they also prove sufficiency. Equality is allowed because a Nash equilibrium rules out strict improvements, not indifferent deviations. The endpoint $s=n$ has no hare hunter to check; it is an equilibrium exactly when $d/n\ge h$.

Continue with $0<h<d$ and set $r=d/h$. Part (e) requires an interior count to satisfy $s\le r\le s+1$ with $s\ge k$; the all-deer endpoint $s=n$ is allowed when $r\ge n$. If $r$ is nonintegral and $k\le r<n$, only $s=\lfloor r\rfloor$ works. If $r=m$ is an integer with $k+1\le m\le n$, both $s=m-1$ and $s=m$ work. At $r=k$ only $s=k$ remains, while $r>n$ permits only $s=n$. When $r<k$, there is no positive equilibrium count.

Thus there are at most two positive counts, and exactly one precisely whenThis includes $k=n$, when the excluded set is empty. It counts numbers of deer hunters, not the many choices of which hunters participate. The argument is the threshold stag-hunt equilibrium count.

The original paper states only $h<d$ explicitly. Its assertion needs the usual strict positivity of the hare reward. If zero is included, take $n=6,k=4,d=1,h=0$. Counts $s=1$ and $s=2$ both give unsuccessful hunters zero, and one additional deer hunter still cannot reach the threshold; all unilateral alternatives also pay zero. The count $s=6$ is an equilibrium as well. These are three positive equilibrium counts, contradicting an unrestricted reading. More generally, for $h=0<d$, the positive counts are $1,\dots ,k-2$ and $n$.