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

Solutions to all four questions of the 3 June 2022 paper, including every marked part. Both examination codes identify this same shared undergraduate and MSc paper. Source release: released examination archive. The cover date controls despite the archive member's misleading 2021 directory.

Let $X$ denote the monetary reward. Its expected value and expected utility are different quantities:Thus indifference to a sure nonnegative reward requires $k^2=10.89$, giving $k=3.30$ dollars. This is the certainty equivalent, hence the lottery's monetary value in the question's comparison with a sure reward. The utility function $u(x)=x^2$ is increasing and strictly convex on nonnegative monetary amounts. Its certainty equivalent exceeds its expected value, $3.30>1.89$, demonstrating risk seeking; the same conclusion follows from the Jensen inequality.

The wording about paying an entry fee needs a qualification. A certainty equivalent compares a gross lottery with a sure gross reward; a literal utility indifference price also accounts for the fee's effect on wealth. If $u$ instead describes final wealth, with initial wealth $w$ and fee $c$, the comparison is $\mathbb{E}[(w-c+X{)}^2]=w^2$, on a domain where the utility function is increasing. Here $\mathrm{Var}(X)=7.3179$, so the nonnegative-wealth branch gives $c=w+1.89-\sqrt{w^2-7.3179}$ whenever that branch is admissible. An initial wealth and an admissible payment domain are not specified. Therefore $3.30$ is the determined certainty equivalent, while a literal wealth-dependent maximum fee is not uniquely determined. This is the distinction in certainty equivalent and willingness to pay. If negative rewards were allowed without requiring an increasing utility function, the equation for $k$ also has the algebraic root $-3.30$; the usual nonnegative-reward interpretation selects the positive root.

Write $A$ and $B$ for the two deterministic outcomes. Under the expected utility hypothesis, indifference between them implies $u(A)=u(B)=c$. The expected utility of the fair lottery is consequentlyIt must therefore be indifferent to each deterministic outcome, contradicting the asserted strict preference. These preferences do not admit an expected utility representation over the stated outcomes. Equivalently, affine utility on probability measures preserves this indifference under mixing, as required by the independence axiom for lottery preferences.

A concern for the fairness of the procedure can be perfectly intelligible. It would require enlarging the outcome description to include the procedure; it cannot be represented by an expected utility over only the two final gift recipients while retaining the stated strict preference.

First evaluate the inner lottery: $U({\ell }_1)=12p+3(1-p)=3+9p$. By reduction of compound lotteries, the outer expected utility isSince $4/9$ lies in the permitted real interval, the square is minimized there. The unique maximizer and maximum expected utility are $p=4/9$ and $U({\ell }_2)=43/9$. Directly flattening the lottery gives probabilities $p(1-p)$, $(1-p{)}^2$ and $p$ for the three outcomes; these sum to one and give the same expression.

Reading the lower-left number in each source cell as player 1's payoff, against an opponent playing $A$ the player's own payoffs from $A,B$ are $y,0$; against $B$ they are $x,x/2$. For $x>0$, identify $A$ with aggressive defection and $B$ with yielding cooperation. The standard payoffs then have valuesThe prisoner's dilemma ordering $T>R>P>S$ holds precisely for $x>0$ and $0<y<x/2$ with this labeling. For example, $x=4,y=1$ gives $T=4,R=2,P=1,S=0$. Each player then has the strictly dominant strategy $A$, although $(B,B)$ gives both a larger payoff than $(A,A)$. Here $2R=T+S$ as well, so the optional weak aggregate-payoff condition is met with equality.

For the Chicken payoff ordering, the collision outcome must be worse than yielding to an aggressive opponent: $T>R>S>P$. This holds for $x>0$ and $y<0$, for example $x=4,y=-1$. Against $B$, the best response is $A$ because $x>x/2$; against $A$, it is $B$ because $0>y$. Consequently $(A,B)$ and $(B,A)$ are the two pure strategy Nash equilibria, and mutual aggression is the worst outcome for both.

If action names may be exchanged, there is another prisoner's dilemma region: take $A$ as cooperation and $B$ as defection. Then $(T,R,P,S)=(0,y,x/2,x)$, so $x<0$ and $x/2<y<0$ also work, for example $x=-4,y=-1$. This relabeling explains why the first displayed region is not a necessary condition without an action convention. Equality at any of these boundaries destroys the strict ordering.

Represent satisfied and unsatisfied goals by payoffs one and zero. The second player's goal is an exclusive or: it is true precisely when $q\ne r$, independently of $p$. The first goal is false only when all three Boolean variables are false. The resulting payoff matrix is below; each boxed entry marks that player's best response to the opposing pure strategy, including ties:For player 1, choosing $r$ satisfies the goal against every opposing pure strategy. Choosing $\bar{r}$ does equally well except against $\bar{p}\bar{q}$, where it does worse. Thus $r$ is player 1's unique dominant strategy in the weak sense, and there is no strictly dominant strategy. The ties are why most first-player entries in both rows are boxed.

For player 2, either pure strategy with $q=0$ is a best response against $r$, while either with $q=1$ is a best response against $\bar{r}$. No one choice of $q$ works against both rows, so player 2 has no dominant strategy, and there is no dominant-strategy equilibrium. The value of $p$ does not affect player 2's own payoff.

The cells with both entries boxed give exactly four pure strategy Nash equilibria:All four give payoffs $(1,1)$. In particular, the weakly dominated choice $\bar{r}$ can occur in a Nash equilibrium because player 1 is already satisfied there and cannot strictly improve.

The succinct input is the players' variable-control sets, their goal propositional formulas, and a complete candidate Boolean valuation; an exponentially expanded payoff matrix is not part of the input. This representation is essential to candidate equilibrium checking in a Boolean game.

For membership in co-NP, consider the complement: the candidate is not a Nash equilibrium. A complexity certificate consists of a player $i$ and an alternative Boolean valuation of that player's controlled Boolean variables. Evaluate the current goal and the goal after this unilateral deviation, keeping every other player's variables fixed. A profitable unilateral deviation exists precisely when the current goal is false and the new goal is true. The certificate has at most the number of input variables plus the player index, and both propositional formula evaluations take polynomial time. Thus the complement belongs to NP, and the original decision problem belongs to co-NP.

For hardness, start with a propositional formula $F(X)$ and introduce a fresh Boolean variable $z$. Construct a one-player Boolean game in which that player controls $X\cup \{z\}$ and has goalChoose the candidate pure strategy assigning every variable false. Its payoff is zero because $z$ is false, regardless of $F$. If $F$ has a satisfying assignment, changing $X$ to that assignment and $z$ to true is a profitable unilateral deviation. If $F$ is an unsatisfiable Boolean formula, no unilateral deviation can satisfy the goal. ThereforeThe construction increases the formula length by only a constant and writes a candidate of linear length, so it is a polynomial-time many-one reduction. Unsatisfiability is co-NP-complete; combining hardness and membership proves that candidate Nash equilibrium checking for Boolean games is co-NP-complete. If a convention requires at least two players, add a player controlling a fresh unused variable and having the always-true goal; this changes neither direction of the proof.

There is no perfect recall. Player 1's later information set joins histories following both of her initial actions, so she has forgotten whether she chose $L$ or $R$. It also hides player 2's intervening action, but failure to observe another player's action is imperfect information, whereas forgetting one's own earlier action is the particular violation of perfect recall. Player 2's two nodes form a single information set because player 2 does not observe the initial choice.

For a behavioural strategy, let $p$ be player 1's initial probability of $L$ and $r$ her later probability of $L$. These are separate information sets, so $p$ and $r$ need not be equal; their random draws are independent. Name player 2's unlabeled branches left and right, and let $q$ be the probability of taking the left branch. The only unit-payoff paths are left–left–left and right–right–right. ConsequentlyBecause this is a zero-sum game, the natural meaning of the claimed best behavioural strategy is its maximum guaranteed expected payoff. Player 2 can choose either branch, so the guarantee at $(p,r)$ isFor nonnegative numbers, their minimum is at most their geometric mean. Also $p(1-p)\le 1/4$ and $r(1-r)\le 1/4$, henceTaking $p=r=1/2$ makes both possible branch-conditioned success probabilities $1/4$, so this upper bound is attained against every $q$. Thus the optimal guaranteed behavioural strategy success probability is $1/4$.

A mixed strategy can instead select the complete plan $LL$ with probability $1/2$ and the complete plan $RR$ with probability $1/2$. The two choices within a sampled plan are correlated. If player 2 chooses left, exactly the sampled plan $LL$ succeeds; if player 2 chooses right, exactly $RR$ succeeds. Therefore the success probability isagainst every opposing mixed strategy. It is optimal among mixed strategies too: player 2's uniform mixture gives success probability $1/2$ to each of $LL,RR$ and zero to $LR,RL$, so no mixture of the four plans can exceed $1/2$ against that opponent. This establishes mixed and behavioural security levels without perfect recall directly.

The guarantee qualification matters: if player 2's branch were known to be left, the deterministic plan $LL$ would succeed with probability one. The number $1/4$ is not an upper bound against every fixed opposing choice separately.

Against Tit for tat, let $a_t$ be an arbitrary deviator's action at round $t$, and set $a_{-1}=C$ to encode the opponent's initial cooperation. The opponent then plays $a_{t-1}$. Define $h(C)=0$ and $h(D)=3$. The four possible transitions giveThus every stage payoff is at most $3+h(a_t)-h(a_{t-1})$. The telescoping sum yields the uniform payoff bound against Tit for tat:After division by $T$, no long-run average payoff can exceed three. The bound applies to every action sequence, so in particular it covers every finite-state machine representing a unilateral deviation. Mutual Tit for tat produces $C,C$ in every round and gives each player three. Neither player can improve, proving $(\mathrm{TFT},\mathrm{TFT})$ is a Nash equilibrium.

Another pair is $(\mathrm{TFT},\text{grim trigger})$. Here grim trigger initially cooperates and continues cooperating until the opponent first defects, after which it defects forever. Both strategies are two-state finite-state machines: Tit for tat records the opponent's previous action, while grim trigger records whether defection has ever occurred. Their prescribed play again consists entirely of cooperation and gives $(3,3)$.

The player using grim trigger faces Tit for tat, so every unilateral deviation is bounded by the same telescoping sum and cannot improve on three. The player using Tit for tat faces grim trigger. If that player never defects, the payoff remains three. If the first defection occurs at a finite round $\tau$, it gives a one-time payoff six; thereafter the opponent always defects, against which each subsequent payoff is at most one. Any finite initial prefix has zero contribution to the long-run average payoff, so such a unilateral deviation has limiting upper average at most one. It cannot improve on three either. Both players are therefore best responses, proving the second claimed Nash equilibrium.

For deterministic finite-state machines, the joint state path is eventually periodic, so the displayed averages have a limit. The first bound also controls the limiting upper average for arbitrary action sequences, making the no-improvement argument stronger than an enumeration of finite-state deviations. Notice that equality in the bound permits alternating exploitation to average three: equilibrium requires absence of a strict improvement, not uniqueness of a best response.

Write $x(S)={\sum }_{i\in S}{x}_i$. The core of a cooperative game isTake any $x,y\in C(v)$ and $\alpha \in [0,1]$, and form the convex combination $z=\alpha x+(1-\alpha )y$. Its total payoff is $z(N)=\alpha v(N)+(1-\alpha )v(N)=v(N)$. For every coalition $S$,Hence $z$ remains in the core. The core is a convex set, even when the transferable utility game is not a convex cooperative game. An empty core is a convex set vacuously; the argument does not claim nonemptiness. Geometrically, the same conclusion follows because the constraints intersect an affine hyperplane with closed half-spaces.

Assume the standard empty-coalition normalization $v(\varnothing )=0$. A convex cooperative game has increasing marginal contributions: whenever $A\subseteq B$ and $i\notin B$,This follows from the supermodular inequality applied to $A\cup \{i\}$ and $B$. Fix a permutation $\pi$ of all players, let $P_i$ be the players preceding $i$, and form its marginal contribution vectorSumming along the full permutation is a telescoping sum, so ${\sum }_{i\in N}{m}_i^{\pi }=v(N)$. For an arbitrary coalition $S$, list its members in their induced order $i_1,\dots ,i_k$, and put $S_j=\{i_1,\dots ,i_j\}$. Since $S_{j-1}\subseteq P_{i_j}$, increasing marginal contributions giveThus every marginal contribution vector belongs to the core. The vector of Shapley values is exactly their uniform average over the $n!$ permutations, hence a convex combination. By the preceding part, that average is in the core. This proves that the Shapley value allocation belongs to the core of a convex cooperative game, including every coalition constraint. It is the result Shapley value belongs to the core of a convex game.

Yes. Use the simple cooperative game in which a coalition wins exactly when it contains at least two players. In every permutation, precisely the second arrival changes a losing coalition into a winning one. Each player is second in two of the six permutations, so each Shapley value is $2/6=1/3$. This constructs the required vector while verifying that singleton coalitions lose and the grand coalition wins.

No. In a simple cooperative game, a player's marginal contribution along any permutation is zero or one. With three players there are six equally likely permutations, so every Shapley value is an integer multiple of $1/6$, by the Shapley value denominator in a simple game. But $6(5/12)=5/2$ and $6(3/12)=3/2$ are not integers. The vector sums to one, but fails this necessary denominator condition.

Yes. Give players $1,2,3$ weights $1,1,2$, respectively, and let the quota be three. This weighted voting game is a simple cooperative game whose minimal winning coalitions are $\{1,3\}$ and $\{2,3\}$. In orders $123,132,213,231$, player 3 supplies the winning marginal contribution. In order $312$ player 1 does, and in order $321$ player 2 does. Averaging the six marginal contribution vectors gives exactly $(1/6,1/6,4/6)$ as the vector of Shapley values.

No. The denominator test from part ii is satisfied here, so a stronger obstruction is needed. Put $a_i=v(\{i\})$ and $b_{ij}=v(\{i,j\})$. In a three-player simple cooperative game, the Shapley value formula gives, for distinct $i,j,k$,Subtract the corresponding expression for ${\varphi }_j$:Each coalition value is zero or one, so this difference must be an integer multiple of $1/2$. This is the obstruction from pairwise Shapley differences in a three-player simple game. The proposed first two coordinates differ by $1/6$, which is not an integer multiple of $1/2$. Therefore the vector cannot occur, even though each coordinate separately passes the $1/6$ denominator test.