Past exam of the MSc in advanced computer science course of the University of Oxford / 2021 / Computational game theory (A15684W1, A16016W1)

Source paper: released examination archive.

${\ell }_2\succ {\ell }_1$. The distinction is small but strict: their normalized expected utilities are $18/25$ and $7/10$, respectively.

By the Von Neumann-Morgenstern utility theorem, use a representing utility function and apply a positive affine function to set $u({\omega }_1)=1$ and $u({\omega }_4)=0$. This is possible because the given strict preference implies $u({\omega }_1)>u({\omega }_4)$. The two specified indifference relations then giveTaking the expected utility of each lottery yieldsTheir difference is $1/50>0$, establishing the stated strict preference. These numbers measure utility, not monetary reward or an assumed ordering of the subscripts.

Here is the underlying argument directly in terms of the axioms. The independence axiom for lottery preferences permits substitution of indifferent lotteries inside a common mixture. Replacing ${\omega }_3$ by its given mixture of ${\omega }_1,{\omega }_4$, and then replacing ${\omega }_2$, followed by reduction of compound lotteries, givesand consequentlyThe transitive relation axiom combines the successive substitutions. Finally, mixture monotonicity says that among mixtures of a strictly better and a strictly worse outcome, the greater probability of the better outcome is strictly preferred; this follows from the independence axiom for lottery preferences and transitivity. Since $18/25>7/10$ and ${\omega }_1\succ {\omega }_4$, the comparison follows. Complete lottery preferences and continuity of lottery preferences are part of the representation theorem's hypotheses; the direct substitution calculation uses the already supplied indifferences and does not need to invoke continuity of lottery preferences again.^[ref]

No: these two strict comparisons violate the independence axiom for lottery preferences. Let $z$ denote the certain zero-money lottery. Reduction of compound lotteries givesFor example, the second expression assigns probability $(1/4)(4/5)=1/5$ to the nonzero reward and $4/5$ to zero. The claimed ${\ell }_3\succ {\ell }_4$ must therefore implywhich is ${\ell }_1\succ {\ell }_2$, contradicting the other claimed strict preference.

The same obstruction is visible in any proposed expected utility representation. Subtract $u(0)$ from the utility function, and write $a=u(3000)-u(0)$ and $b=u(4000)-u(0)$. The first comparison requires $(1/5)b>(1/4)a$, hence $(4/5)b>a$, whereas the second requires $a>(4/5)b$. No real $a,b$ satisfy both. This argument requires neither risk neutrality nor an assumption that the utility function is increasing in money.

Put $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$, so the complementary probabilities are $1-p$ and $1-q$. All four expressions are the row player's expected payoff, including those indexed by a column action. Direct expected value calculations giveThe column player's expected payoff is the negative of the row player's because this is a zero-sum game.

The bold black curve is the pointwise minimum of the two opposing-column expected payoff functions. It is the row player's security level payoff at the specified mixed strategy:The lines meet where $3p-1=1-4p$, hence at $p=2/7$. The first branch increases with slope $3$ and the second decreases with slope $-4$, so their intersection is the unique global maximum of the lower envelope:The endpoint values are $g(0)=-1$ and $g(1)=-3$, both smaller. Since an opposing mixed strategy forms a convex combination of the two pure-column expected payoffs, it cannot make the row player's expected payoff lower than this envelope.

The bold black curve is now the pointwise maximum of the two pure-row expected payoff functions:It measures the largest expected payoff that the row player can achieve against column mixed strategy $q$. The column player minimizes this quantity because its own payoff has the opposite sign. Equality of the two lines gives $5q-3=1-2q$, or $q=4/7$. The envelope decreases before that point and increases afterwards, givingThe endpoint values $h(0)=1$ and $h(1)=2$ are both larger. A row mixed strategy cannot exceed the greatest pure-row expected payoff, because its expected payoff is a convex combination of those two values.

The first graph solves the row player's max–min optimization: choose a mixed strategy guaranteeing the greatest possible worst-case expected payoff. The second solves the column player's min–max optimization: choose a mixed strategy placing the smallest upper bound on the row player's expected payoff. Their optimal heights agree, illustrating the minimax theorem.

There is also a direct Nash equilibrium certificate, so the conclusion does not depend on reading coordinates from a plot. At $p^{\ast }=2/7$, both opposing pure columns give row expected payoff $-1/7$; at $q^{\ast }=4/7$, both pure rows give row expected payoff $-1/7$. By linearity, every unilateral deviation, including an arbitrary mixed strategy, leaves the deviator's expected payoff unchanged against the fixed opposing equilibrium mixture. Neither player can improve it. This is a mixed-strategy optimality certificate for a matrix game.

The equilibrium outcome is a probability distribution over cells, rather than one deterministic cell. Independent randomization givesThe resulting row expected payoff is $(16-18-20+15)/49=-1/7$. Finally, each envelope has a unique optimum, so any Nash equilibrium must use the displayed optimal mixed strategies. In particular there is no pure strategy Nash equilibrium.

Exactly $(T,L)$, $(M,C)$ and $(B,R)$ can be sustained as constant stage game outcomes. Their long-run average payoffs are $(6,6)$, $(4,4)$ and $(0,0)$, respectively. We assume the usual repeated game monitoring convention: both players observe each completed joint action before the next round. The source's colour convention puts the blue lower-left row payoff first and the red upper-right column payoff second.

For necessity, row action $B$ earns $(8,5,0)$ against $(L,C,R)$, so playing it forever guarantees a nonnegative long-run average payoff against every opposing pure strategy. Similarly, column action $R$ earns $(8,5,0)$ against $(T,M,B)$ and guarantees zero or more. Conversely, column action $R$ holds the row player's best possible stage payoff to $0$, and row action $B$ holds the column player's to $0$. Thus each player's minmax payoff is exactly $0$.

Any Nash equilibrium must give both players at least zero, an individually rational payoff in a repeated game. Every off-diagonal cell has a negative payoff for one player: $(T,C)$ and $(T,R)$ hurt row, $(M,L)$ and $(B,L)$ hurt column, $(M,R)$ hurts row and $(B,C)$ hurts column. Repeating any such cell forever therefore permits a profitable unilateral deviation to the zero-guaranteeing action. The three diagonal cells pass this necessary test.

For sufficiency, fix target $a^{\ast }=(T,L)$ or $(M,C)$. Each player's finite-state strategy has initial state $F$ and an absorbing state $P$. In $F$, output the player's component of $a^{\ast }$; remain in $F$ if the completed joint action equals $a^{\ast }$, and otherwise move to $P$. In $P$, row always outputs $B$ and column always outputs $R$, regardless of further observations. These are two-state grim trigger strategies; the separate machines are drawn below. The input is the observed joint action, so after any off-path history the prescribed continuation states agree.

If neither player deviates, the target is repeated forever. If a player first deviates at a finite round $\tau$, the opponent enters $P$ for all later rounds. Against column action $R$, every row action earns at most zero; against row action $B$, every column action earns at most zero. All payoffs are bounded, so the total reward before and at $\tau$, divided by the horizon, tends to zero. The deviator's upper limiting average is therefore at most $0$, below either target payoff $6$ or $4$. This proof tests arbitrary future deviations, not merely a single changed action. It also rules out improvement by deviations whose averages fail to converge, if the criterion is extended by an upper or lower limit.

For target $(B,R)$, one-state machines outputting $B$ and $R$ forever suffice: each is a best response to the other in every round. Their long-run average payoffs are zero and no unilateral deviation can improve them. In fact, the punishment is credible because $(B,R)$ is a stage Nash equilibrium, so the two positive-target constructions are also subgame perfect equilibria under the stated monitoring assumption. The general punishment mechanism is described in ^[ref].

“Outcomes of the stage game” here means a fixed action pair repeated forever. Allowing time sharing also sustains some average payoff vectors that are not stage cells: for example, a deterministic alternating cycle $(T,L),(M,C)$ gives $(5,5)$, with a two-phase finite-state strategy and the same permanent punishment. An off-diagonal cell may occur in a sustainable cycle; the impossibility above concerns its constant repetition, not every appearance on an equilibrium path. With finite-state pure strategies, an undisturbed path is eventually periodic, so its limiting cell frequencies are rational numbers.

Use the standard repeated game convention that the first round's joint action is observed before round two. The following original game tree represents simultaneous moves by making row move first in each round while hiding that current move from column. Terminal labels are total payoffs over both rounds, ordered row then column.

Formally, round one starts at a row decision with actions $T,B$. The two ensuing column nodes form one information set $I_2^0$, with available actions $L,R$; column cannot tell which current row action occurred. The four completed first-round histories are $H=\{TL,TR,BL,BR\}$. At each $h\in H$, round two begins at a separate row node. Its two successors, after row's current $T$ or $B$, form a column information set $I_2^h$. Distinct $h$ have distinct information sets: both players know the whole first-round outcome. There are sixteen terminal histories $(h,k)\in H^2$, whose total payoff is $u(h)+u(k)$, as displayed in the tree.

The row player's five information sets are the initial singleton and the four singleton round-two nodes, one per $h$. The column player's five information sets are $I_2^0$ and the four two-node sets $I_2^h$. Thus each player must specify one binary choice at each of five information sets, including histories that its own first choice might prevent:Counting only the four possible two-round action sequences would miss the distinct contingent responses to the opponent's first action.

For a concrete pair of complete pure strategies, order the second-round histories as $(TL,TR,BL,BR)$ and useThe first entry is the initial action, and the four remaining entries prescribe the action after each first-round history. This induces the unique path $TL$ in round one followed by $BR$ in round two. Hence the total payoff isThe off-path entries are part of each pure strategy, even though this pair does not reach them.

For randomization, a mixed strategy is a probability distribution over the $32$ complete plans, with $31$ free probabilities in a general distribution. A behavioural strategy instead gives one binary-action probability at each of five information sets, requiring five parameters. This game has perfect recall: a player never forgets a previous own action or a first-round observation, and the only concealed action is the opponent's current simultaneous choice. Consequently neither kind of randomization has a greater attainable-payoff advantage: Kuhn's theorem gives realization-equivalent strategies against every fixed opposing strategy.^[ref]

The equivalence can be verified directly here. Given a behavioural strategy, sample all five contingent actions independently before play; the resulting product probability distribution over complete plans is an equivalent mixed strategy. Conversely, let $\mu$ be a mixed strategy for player $i$. Use its marginal probability for the initial action. At history $h$ containing own first action $a_i$, choose second action $b_i$ with conditional probabilitywhenever the denominator is positive; if it is zero, choose arbitrarily at that unreachable history. The opponent's first-round action is simultaneous and cannot depend on the sampled hidden plan beyond the chosen first action. Thus conditioning on $h$ preserves exactly these conditional probabilities of actions, and multiplying the first- and second-round factors reproduces each terminal probability. Correlations between prescriptions at mutually exclusive second-round histories have no further observable effect. Behavioural strategies offer the more compact representation, while mixed strategies describe a single random choice of a full plan. Imperfect information here does not mean imperfect recall.

If the core is nonempty, it is exactly the singleton allocation $p_j=v(\{j\})$ for every $j$. Take any $p$ in the core of a cooperative game and write $p(C)={\sum }_{j\in C}{p}_j$. Core membership gives efficiency of the imputation, $p(N)=v(N)$, and the coalition inequalitiesUsing the given complementary-coalition equality in this constant-sum cooperative game, the second inequality yieldsCombining upper and lower bounds gives $p(C)=v(C)$ for every coalition $C$. In particular,Since this holds for any core member and at least one exists by hypothesis, the displayed allocation is in the core and is its only member. The argument also shows why nonemptiness is restrictive: it forces $v(C)={\sum }_{j\in C}v(\{j\})$ for every coalition, so the characteristic function of a coalitional game must be additive. No superadditive coalitional game or monotonicity assumption is needed.

In an induced subgraph game, players are graph vertices and a coalition receives the sum of the weights of graph edges whose two endpoints lie in it. Therefore each two-player coalition determines the corresponding edge weight. For $G_1$ these weights would have to be $2,6,3$, making the grand coalition worth $2+6+3=11$, whereas its actual value is $15$. No other edge weights can repair that discrepancy without changing a two-player coalition's value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.

For $G_2$, the stated weighted graph triangle has grand coalition value $2+3+3=8$ and reproduces all three pair values. Empty and singleton coalitions contain no graph edges, so their values are zero. This verifies all eight coalitions and supplies the complete representation.

To compute the Shapley value, reveal players in a uniformly random permutation. An edge's weight contributes to an endpoint's marginal contribution precisely when the other endpoint appeared earlier. Each endpoint is later with probability $1/2$, independently of where the third player appears. Linearity of the expected value therefore splits each edge weight equally between its two endpoints:The values sum to $8=v_2(N)$, as required by the Shapley value's efficiency property. This is the general Shapley value of an induced subgraph game formula, not an assumption that all three players are symmetric: player $3$ has a different incident-weight total.

The core is the singleton $\{(1/2,1/2,1/2,1/2)\}$. Here the characteristic function of a coalitional game is $v(C)=\lfloor |C|/2\rfloor$, the two-person instance of the core of the miners game calculation.

Let $x$ be in the core. Efficiency requires $x_1+x_2+x_3+x_4=2$, and every pair coalition requires $x_i+x_j\ge 1$. Summing the six pair inequalities counts each coordinate three times, giving $3{\sum }_i{x}_i\ge 6$. Efficiency makes this an equality; since every individual slack is nonnegative, all six pair inequalities must be equalities. In particular $x_1+x_2=x_1+x_3=x_1+x_4=1$ forces $x_2=x_3=x_4$, and comparison with $x_2+x_3=1$ gives every $x_i=1/2$.

Conversely, for the uniform allocation every coalition satisfiesand its total is $2=v(N)$. It is therefore a core member, completing both existence and uniqueness. In particular, a three-player coalition receives $3/2\ge 1$; the pair constraints are the tight ones.

The core is empty. Efficiency would require $x_1+x_2+x_3=v(N)=1$. Each two-player coalition has value $1$, so core membership would also requireAdding gives $2(x_1+x_2+x_3)\ge 3$, contradicting efficiency, which makes the left side $2$. Thus no allocation can meet all coalition demands. The obstruction uses only pair coalitions and the grand coalition; imposing individual rationality cannot remove it. The equal allocation $(1/3,1/3,1/3)$ is efficient but gives each pair only $2/3<1$, so symmetry does not supply a core allocation.