Past exam of the computer science course of the University of Oxford / 2019 / Computational game theory (A15684W1)

Source paper: released Oxford examination archive, member 2018/T/a15684w1.pdf. The actual cover identifies the Second Public Examination, Trinity Term 2019, Monday 3 June. Its printed time is 9:30 am–12:30 am, including the apparent end-time typo; this is not silently changed to noon. All three questions are solved. Part 2(c) includes the necessary qualification of its literal premise.

The players are the two chains, each with the set of pure strategies $\{1,2,3,4,5\}$. A strategy profile $(x,y)$ gives the sites of $S$ and $C$. For later use, write the first player's payoff for a general street size asWhen $x<y$, count customers to the left of $(x+y)/2$, assigning value one rather than two to any midpoint customer. This gives $x+y-1$ whether the midpoint is an occupied building or lies between buildings. The other player receives $2k-u(x,y)$. At co-location, every customer's value is split, giving $k$ each.

For $k=5$, the payoff matrix for $S$ isRows and columns are indexed by sites $1,\dots ,5$; the full ordered payoff pair in cell $(x,y)$ is $(M_{xy},10-M_{xy})$. This discrete location game is a constant-sum game.

Neither player has a weakly dominant strategy among its pure strategies. Against an opponent at site one, the unique best response is site two, yielding $2k-2$. Co-location yields only $k$, and moving further right reduces one's payoff. Against an opponent at site $k$, the unique best response is $k-1$, by reflection. For $k\ge 4$, these two sites differ. No single pure strategy can therefore be a best response to both opposing actions, as a weakly dominant strategy would require.

Yes to both questions, for both players. Site one is strictly dominated by site two. Against opposing site $y$, the payoff difference isEvery difference is positive for $k\ge 4$. By reflection, site $k$ is strictly dominated by site $k-1$. These endpoint actions are therefore also weakly dominated strategies, since strict dominance is stronger than the requirement of being no worse everywhere and better somewhere.

If a player chooses site $x$, the opponent can co-locate and hold its payoff to $k$. Among opposing sites to its right, the lowest payoff is obtained against $x+1$, giving $2x$. Among opposing sites to its left, the lowest is against $x-1$, giving $2(k-x+1)$. Thus the pure-action security level payoff isThe expression remains valid at an endpoint, where the missing-side term is redundant. It reaches its largest possible value $k$ exactly when $k/2\le x\le k/2+1$. Hence the pure maxmin strategies areReflection gives the same answer for the other player.

Both players can guarantee $k$ by part (d), so at any Nash equilibrium each must receive at least $k$. Their payoffs sum to $2k$, forcing both equilibrium payoffs to equal $k$.

Moreover, an equilibrium action must itself have the maxmin guarantee $k$. If a player's chosen action allowed an opposing response that reduced its payoff below $k$, that response would give the opponent more than $k$, a profitable unilateral deviation. Thus both equilibrium sites belong to the central set identified in part (d).

Conversely, if both choose from that central set, each chosen action guarantees $k$. Neither can improve above $k$, because the other player's fixed central action still guarantees the other player $k$. Consequently, all pure Nash equilibria areFor even $k$, this includes both co-located central profiles and both orders of the two distinct central sites.

There is no pure Nash equilibrium. If the firms choose different sites, $S$ serves at least its own building, so $C$ receives less than $2k$. By moving onto $S$'s site, $C$ makes every customer equidistant from the two shops and wins every tie, obtaining $2k$. Thus any separated profile has a profitable unilateral deviation by $C$.

At any co-located profile, $S$ receives zero. It can move to a different site and capture at least that site's customers, obtaining at least two. Thus every co-located profile also has a profitable unilateral deviation. These cases exhaust all pure strategy profiles.

Write $k=2m+1$, where $m\ge 2$. For three distinct sites $a<b<c$, the left, middle and right firms receive respectivelyThese follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy $\ell <r$, the final entrant compares $2(\ell -1)$ at $\ell -1$, $2(k-r)$ at $r+1$, and $r-\ell$ at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.

First suppose $C$ opens at the central site $m+1$. If $S$ chooses $s\le m$, the final entrant's best possible payoffs on the left, right and interior are at most $2m-2$, exactly $2m$, and at most $m$, respectively. Hence $N$'s unique best response is $m+2$. The resulting payoff to $S$ is $m+s$, uniquely maximized on that side at $s=m$. Reflection gives the other optimal choice $s=m+2$, followed by $N=m$. Under either choice, $C$ receives only $2$. Any mixture of the tied optimal second-mover choices has the same consequence.

Now let $C$ deviate to $c=m$. If $S$ chooses $s<m$, the unique final best response is $m+1$, yielding $S$ at most $2m-2$. If $S$ chooses $m+1$, the unique final best response is $m+2$, yielding $S$ only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:

Accordingly, in every subgame perfect equilibrium continuation after $C=m$, the second mover must choose a site $s\ge m+2$. This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.

For any such $s$, every legal final site gives $C$ at least three. If $N$ lies left of $m$, then $C$ is the middle firm and receives $s-N\ge 3$. If $N$ lies right of $m$, then $C$ is the left firm and receives $m+\min (s,N)-1\ge 2m\ge 4$. Thus the deviation gives $C$ at least $3$, against every subgame-perfect continuation, whereas the central opening gives it $2$.

In this original example, a final-mover tie produces the line segment for $S=6$: its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing $S=7$, so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.

A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have $C$ open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.

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.

For a fixed finite player set $N$ and characteristic function $v$ with $v(\varnothing )=0$, let $\psi (v)$ be the allocated payoff vector. A standard four-axiom characterization is:

Cooperative-game efficiency: ${\sum }_{i\in N}{\psi }_i(v)=v(N)$.

Cooperative-game symmetry: if $v(S\cup \{i\})=v(S\cup \{j\})$ for every $S\subseteq N\setminus \{i,j\}$, then ${\psi }_i(v)={\psi }_j(v)$.

The null player axiom: if $v(S\cup \{i\})=v(S)$ for every $S\subseteq N\setminus \{i\}$, then ${\psi }_i(v)=0$.

Cooperative-game additivity: for games $v,w$ on the same $N$, ${\psi }_i(v+w)={\psi }_i(v)+{\psi }_i(w)$, where $(v+w)(S)=v(S)+w(S)$.

These axioms uniquely specify the Shapley value. This is the zero-marginal null-player convention. The original work combines some requirements into an equivalent formulation.^[ref]

Use the inclusive quota: a coalition wins at weight at least $25$. For each player, count losing predecessor coalitions that become winning when that player joins. Group these swing counts by predecessor cardinality $t=0,1,2,3$:

For example, player one is pivotal for predecessor coalitions $\{2\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$ and $\{2,3,4\}$. Player three is pivotal only for $\{1,4\}$; player four has the symmetric counterpart.

Each swing contributes $1/8$ to the probabilistic Banzhaf index. For the Shapley value, a swing with $t$ predecessors contributes $t!(3-t)!/4!$, which is $1/4,1/12,1/12,1/4$ for the four possible sizes. Applying these weights to the table givesThe Shapley values sum to one. The unnormalized Banzhaf indices sum to $5/4$; they must not be replaced by normalized shares in this part.

Fix distinct players $i,j$ and write $Ti=T\cup \{i\}$, with analogous notation for $Tj$ and $Tij$. Splitting sampled coalitions according to whether they contain the other player givesSubtracting yields the Banzhaf difference identity,In a weighted voting game, $w_j>w_i$ means that $Tj$ has greater total weight than $Ti$. Thus $v(Tj)\ge v(Ti)$ for every $T$: if the lighter coalition reaches the quota, the heavier one does too. Every summand is nonnegative, proving ${\beta }_i(v)\le {\beta }_j(v)$. Equality remains possible even when the weights differ.

The probabilistic Banzhaf index satisfies cooperative-game symmetry, the null player axiom and cooperative-game additivity, but not cooperative-game efficiency.

For cooperative-game symmetry, interchangeable players have $v(Ti)=v(Tj)$ for every $T$ omitting them. The Banzhaf difference identity therefore gives equal indices. For a null player, every marginal contribution in the defining average is zero, so its index is zero.

For cooperative-game additivity, each marginal contribution is additive:Averaging both sides over the same $2^{n-1}$ coalitions gives ${\beta }_i(v+w)={\beta }_i(v)+{\beta }_i(w)$.

For failure of cooperative-game efficiency, the indices computed in part (b) sum to $5/4$, whereas the grand-coalition value is one. This is already a counterexample. Independently, a three-player majority game gives each player index $1/2$, also exceeding the total value when summed. Pivotality averaged over independently chosen coalitions does not telescope in the way the ordering-average Shapley value does.

Where its denominator is nonzero, normalization enforces cooperative-game efficiency and preserves cooperative-game symmetry and the null player axiom. The violated axiom is cooperative-game additivity.

For an exact counterexample on three players, let $v$ be the majority game, and let $w$ be the dictatorship in which a coalition wins precisely when it contains player one. Their probabilistic Banzhaf indices arewith $v(N)=w(N)=1$. HenceUnnormalized indices add, so $\beta (v+w)=(3/2,1/2,1/2)$. Their sum is $5/2$, while $(v+w)(N)=2$. ThereforeThe sum game is a valid transferable utility game, although it is not binary; that is the natural domain of the additivity axiom. The failure comes from a game-dependent scaling factor. A zero denominator, as for the zero game, makes the displayed normalization undefined unless a separate convention is supplied; none of the counterexample's denominators vanish.