Past exam of the MSc in advanced computer science course of the University of Oxford

Source release: www.whatdotheyknow.com/request/ba_computer_science_past_papers/response/2577745/attach/2/202402%20183%20CS%20Papers.zip?cookie_passthrough=1

All three questions have the same mathematical content as combinatorial optimisation, where all 29 answer parts are solved. This MSc version has a three-hour duration and different answer instructions and mark allocations; the undergraduate version has a two-hour duration. Their formal paper codes and cover metadata differ.

Solutions to all four questions and all ten marked lettered parts of the University of Oxford examination held on 1 June 2023. Every unlabelled bullet task within those parts is covered. Source release: released examination archive, member 2022/T/a15684w1.pdf; the cover identifies the paper as Trinity Term 2023. Question statements and original diagrams are omitted. Necessary conventions about finite representations, repeated-game payoffs and empty-coalition normalization are stated at the affected parts.

Under the expected utility hypothesis, use positive affine uniqueness of affine preference representations to normalize the extreme outcomes to $u({\omega }_1)=1$ and $u({\omega }_4)=0$. The stated indifference relations then giveThe two lotteries have expected utilitiesHence ${\ell }_2\succ {\ell }_1$, with normalized expected utility difference $3/100$. Equivalently, substitution reduces them to lotteries with probabilities $0.45$ and $0.48$ of the better extreme outcome. The inference uses the independence axiom for lottery preferences; the three displayed outcome comparisons alone would not determine preferences over all compound lotteries without the expected utility hypothesis.

Yes: the stated order has an expected utility representation. For outcomes whose monetary amounts are $1,2,4$, respectively, chooseThenSince $12/5>9/5>3/2>4/5$, this utility function gives exactly the required strict preferences.

The distinction is that the expected utility hypothesis does not by itself require the utility function to increase with monetary amount. This nonmonotone monetary utility ranks the outcome paying 2 below the outcome paying 1. If increasing monetary utility were imposed as an additional assumption, the stated order would fail: ${\ell }_3\succ {\ell }_4$ requires $u(1)>u(2)$ becauseThat additional monotonicity assumption is not printed in this part.

For the intended finite representation, put $m=|S|<\infty$. For each $T\subseteq S$, form the mintermA Boolean valuation satisfies ${\chi }_T$ exactly when its selected subset is $T$. Therefore the weighted formula utility representationrepresents $u$ exactly: at the Boolean valuation for $T$, only that minterm contributes, with weight $u(T)$. This proves completeness and the bound of $2^{|S|}$ rules simultaneously. Zero-weight rules may be omitted. The bound counts rules; writing each minterm also requires $O(m)$ symbols in Big O notation.

For the computational question, assume rule weights are rational numbers encoded in binary. This makes exact equality of sums a finite computational task. With this conventional encoding, equivalence of weighted formula utility representations is co-NP-complete.

For membership, the complement has a short witness: a Boolean valuation on the variables occurring in either rule base. Evaluate each propositional formula, sum the weights of satisfied rules, and accept the witness if the sums differ. Propositional formula evaluation takes polynomial time. Exact sums of binary rational numbers also have polynomially bounded bit lengths: the product of their denominators has bit length at most the sum of the input denominator lengths. Thus non-equivalence lies in NP, and equivalence lies in co-NP.

For hardness, take a Boolean satisfiability problem instance $\theta$ and constructThe first utility function is one at satisfying Boolean valuations and zero elsewhere, while the second is always zero. ConsequentlyThe unsatisfiable Boolean formula problem is co-NP-complete, as the complement of the NP-complete Boolean satisfiability problem. The construction is a polynomial-time reduction, proving hardness even with the single weight $1$.

Two qualifications matter in the literal wording. First, unrestricted real weights have no specified finite encoding, so a standard bit-complexity classification needs the encoding assumption above. Second, the problem says only that $S$ is nonempty. If infinite $S$ is allowed while rule bases remain finite, its completeness claim is false. For $S=\mathbb{N}$, take $u(T)=1$ when $T$ is infinite and $u(T)=0$ when $T$ is finite. A finite rule base mentions only a finite subset $F$ of the variables. The Boolean valuations for $\varnothing$ and $\mathbb{N}\setminus F$ agree on all those variables but have different required values. No such rule base represents this $u$. Thus the construction answers the intended finite-set question and identifies the missing hypothesis in the unrestricted statement.

Read the lower-left entry of each cell as player 1's payoff and the upper-right entry as player 2's payoff, as indicated by the source diagram. Against $L$, player 1 strictly prefers $B$ because $2\pi >1$; against $R$, player 1 strictly prefers $T$ because $3>2$. Against $T$, player 2 strictly prefers $R$ because $6>0$; against $B$, player 2 strictly prefers $L$ because $2\sqrt{2}>2$. Thus the pure strategy Nash equilibria are

For a fully mixed strategy Nash equilibrium, write $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$. Player 1's expected payoffs from the two pure strategies areEquality, required when both pure strategies have positive probability, givesPlayer 2's corresponding expected payoffs areso equality givesBoth probabilities lie strictly between zero and one. Hence the unique fully mixed strategy Nash equilibrium iswith complementary probabilities on $B$ and $R$. Its expected payoffs are

These are all three Nash equilibria. There are no equilibria with just one player genuinely mixing: against each opposing pure strategy, the other player's best response is unique, so that player cannot mix. When both players mix, the two linear indifference equations have the unique solution just obtained. This is support enumeration for a bimatrix game with all possible supports checked.

The definition in this part uses a single Boolean valuation, so the relevant Nash equilibria are pure strategy equilibria of a Boolean game. Use its standard convention that the players' control sets form a set partition of the variables.

Membership follows from an existential choice of a strategy profile and a universal check of all unilateral deviations. Assign payoff one to satisfying a player's goal and zero otherwise. A strategy profile $\sigma$ is a Nash equilibrium precisely when, for every player $i$ and every alternative Boolean valuation ${\tau }_i$ of that player's variables,is true: either the goal is already satisfied or no deviation can satisfy it. Thus the requested property isThe strings encoding $\sigma$, $i$ and ${\tau }_i$ have polynomial length, and evaluating the bracketed propositional formulas takes polynomial time. Invalid encodings of a player index can simply be ignored by the test. This is the existential second level of the polynomial hierarchy, ${\Sigma }_2^{\mathrm{P}}$.

For hardness, reduce the canonical complete problem of deciding a two-block quantified Boolean formulaMake a two-player Boolean game: player 1 controls $X$ and has goal ${\gamma }_1=\top$; player 2 controls $Y$ and has goal ${\gamma }_2=\neg \psi$. Set the query formula to $\varphi =\psi$. The construction has size linear in the input formula.

If an assignment $x$ satisfies $\forall Y\psi (x,Y)$, combine it with any assignment $y$. Player 1 already satisfies its goal, and player 2 cannot satisfy $\neg \psi$ by any unilateral deviation. Thus $(x,y)$ is a Nash equilibrium satisfying the query.

Conversely, let $(x,y)$ be a Nash equilibrium satisfying $\psi$. Player 2 currently has payoff zero. If some alternative $y^{\prime }$ made $\psi (x,y^{\prime })$ false, that deviation would satisfy player 2's goal and increase its payoff to one. The Nash equilibrium condition therefore implies $\forall Y\psi (x,Y)$. This proves the required equivalence and the polynomial-time reduction.

Together, membership and hardness prove ${\Sigma }_2^{\mathrm{P}}$-completeness of existential equilibrium checking in a Boolean game. The reduction works with only two players and one constant goal.

Measure all payoffs in millions of dollars, in the order (Ann, Bob). Since both players maximize expected money, those numbers are already their expected utility scale.

In the extensive-form game, Ann moves first. Staying out terminates at $(2,6)$. Entering leads to Bob's observed decision between fighting, with terminal payoffs $(1,1)$, and acquiescing, with terminal payoffs $(3,3)$. Each decision node is its own information set, so this is a perfect-information game.

The corresponding normal-form game gives Ann the pure strategies $O$ (stay out) and $E$ (enter), and Bob the complete contingent pure strategies $F$ (fight if entry occurs) and $A$ (acquiesce if entry occurs). The payoff matrix isThe pure strategy Nash equilibria are $(O,F)$ and $(E,A)$. Against $F$, Ann prefers $O$; against $A$, Ann prefers $E$. When Ann stays out, Bob's contingent response does not affect his payoff, so $F$ is a best response there.

There is exactly one subgame perfect equilibrium, $(E,A)$. In the subgame following entry, Bob strictly prefers $3$ to $1$, so backward induction selects acquiescence; Ann then strictly prefers entering for $3$ to staying out for $2$. The threat supporting $(O,F)$ is not optimal in that one-shot subgame.

For infinite repetition, the paper specifies no discount factor. First take the long-run average payoff convention, with all past actions observed. The feasible payoff set is the convex hullAnn can guarantee $2$ in every stage by staying out; Bob can guarantee at least $3$ in every stage by acquiescing whenever entry occurs. These guarantees are also their minmax payoffs: fighting holds Ann's best possible stage payoff to $2$, and entering holds Bob's best possible stage payoff to $3$.

Therefore the sustainable Nash equilibrium average payoffs are exactly the feasible, weakly individually rational payoffs in a repeated game:This is the closed triangle with vertices $(2,3),(2,6),(3,3)$.

Here is a direct sufficiency argument for this particular game. Choose a publicly known sequence of stage outcomes whose frequencies give the target point. Before any observed deviation, follow that sequence. After an Ann deviation, Bob fights forever, so Ann can thereafter obtain at most $2$ per stage. After a Bob deviation, Ann enters forever, so Bob can thereafter obtain at most $3$ per stage. A finite prefix has no effect on long-run average payoff, so no unilateral deviation improves a target with $a\ge 2,b\ge 3$. Rational frequencies can be implemented periodically; arbitrary real frequencies can be implemented by a deterministic sequence with convergent frequencies. Thus even the weak boundary is covered here. In particular, staying out forever and entry followed by acquiescence forever are sustainable; fighting forever is not.

For discounted payoffs $(1-\delta ){\sum }_{t\ge 0}{\delta }^t{u}_i^t$, the folk theorem for repeated games instead gives the usual patience qualification: every feasible point with $a>2,b>3$ can be sustained for all sufficiently large $\delta <1$. It does not classify the whole region for an unspecified fixed $\delta$. The two one-shot Nash equilibrium outcomes remain sustainable for every $\delta$.^[ref]

Finally consider the particular history-dependent pair in the paper. Initially Bob has never acquiesced, so Ann stays out. That preserves the same condition forever, giving payoffs $(2,6)$. The pair is a Nash equilibrium. Holding Bob's strategy fixed, Ann cannot induce an acquiescence: he fights whenever she enters, and his rule never changes unless he has previously acquiesced. Every entry would give her $1$ instead of $2$, so no unilateral deviation helps. Holding Ann's strategy fixed, Bob never reaches a decision node because she stays out; changing his strategy alone cannot create a history in which he actually acquiesces. Hence he also cannot improve.

This direct argument works for both discounted and long-run average payoffs. The outcome gives Ann exactly her minmax payoff and Bob more than his, so it is compatible with the folk theorem for repeated games. A version requiring strict gains above both minmax payoffs is a sufficient condition, and cannot be used to rule out this boundary example.

This is an absent-minded decision problem: the two decision nodes belong to the same information set. A behavioural strategy must therefore use the same probability at both visits. Put $p=\mathrm{Pr}(D)$ and $1-p=\mathrm{Pr}(R)$; fresh randomization occurs independently at each visit.

The terminal probabilities are $1-p$ for stopping immediately, $p(1-p)$ for going down once and then right, and $p^2$ for going down twice. Thus the expected payoff isThis expression gives the unique global maximum on $[0,1]$:

The independence of repeated randomizations is essential. A mixed strategy choosing once between the two deterministic plans “always $R$” and “always $D$” gives at most $1$, since their payoffs are $0$ and $1$. It cannot arrange “$D$ first, then $R$” as a deterministic plan respecting this information set. The failure of perfect recall is exactly why mixed strategies and behavioural strategies need not have the same attainable outcome distributions here.

It suffices to take four players. Both two-player coalitions $\{1,2\}$ and $\{3,4\}$ win, because two is a prime number, while the empty coalition and the four-player coalition lose.

Suppose real weights and quota $q$ represented this game. The empty coalition loses, so $0<q$. The two winning coalitions requireAdding givesso the four-player coalition must win, a contradiction. Hence prime-cardinality games cannot in general be represented as weighted voting games. The same four-player obstruction appears inside every such game with at least four players.

This proof permits negative individual weights, as the printed definition does. An argument based solely on monotonicity would require a nonnegative-weight assumption and would not suffice for that definition.

Let $W(C)={\sum }_{i\in C}{w}_i$. If the two disjoint winning coalitions exchange players, the aggregate weight is conserved:If both resulting coalitions lost, each weight would be strictly below $q$, making their sum strictly below $2q$. This is impossible. Thus every weighted voting game has swap robustness for disjoint winning coalitions, even when the weights or quota are negative.

The converse is false. The four-player prime-cardinality game from part (a) has swap robustness for disjoint winning coalitions: swapping one player each way preserves each coalition's cardinality, so in fact both winning coalitions remain winning. Part (a) proves it is not a weighted voting game.

Even imposing monotonicity would not repair the converse under the printed disjointness restriction. As a stronger counterexample, use five players and declare a coalition winning exactly when it contains player $1$ and contains either both $2,3$ or both $4,5$. This is a simple cooperative game, and all its winning coalitions contain player $1$, so no two are disjoint; the stated swap condition holds vacuously.

Nevertheless $\{1,2,3\}$ and $\{1,4,5\}$ win, while $\{1,2,4\}$ and $\{1,3,5\}$ lose. Both pairs contain every player the same total number of times. A weighted representation would therefore givea contradiction. This is a trade obstruction to weighted voting and pinpoints how weak the disjoint-only swap requirement is.

Use the usual empty-coalition normalization $v(\varnothing )=0$ for a transferable utility game. Write $P_i=\{1,\dots ,i-1\}$, so the proposed payoff is the marginal contributionThe vector is the marginal contribution vector for the natural player order.

First, convex cooperative games have increasing marginal contributions. If $A\subseteq B$ and $i\notin B$, apply the defining supermodular set function inequality to $A\cup \{i\}$ and $B$:Rearranging gives

The vector is efficient by a telescoping sum:Now fix any coalition $T$. For each $i\in T$, its earlier members are $T\cap P_i\subseteq P_i$. Increasing marginal contributions therefore giveSum over the members of $T$ in increasing order. The right-hand side is another telescoping sum, now along the growing coalition $T$:Efficiency and these inequalities for every coalition are exactly the defining requirements of the core of a cooperative game. Thus $x$ belongs to the core. The same proof works for any player ordering, not only the natural order.

The normalization is essential to the literal statement: the printed part does not explicitly state it. Without $v(\varnothing )=0$, take the constant characteristic function of a coalitional game $v(T)=1$. It satisfies the displayed convex cooperative game inequality with equality, but every proposed $x_i$ is zero, so efficiency fails when $N$ is nonempty. Under the standard normalized definition, the proof above establishes the intended result.

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.

Solutions to the single paper shared by the two printed routes, dated 8 June 2021. Oxford examination source release. The probabilistic programming calculations below use only information supplied in the paper. Question 2 contains two notation or naming issues, identified at the affected parts; Question 3 requires an explicit choice of prior distribution.

Assume $0<Z={\sum }_{x}r(x)<\infty$, and work on the support $S=\{x:r(x)>0\}$. In rejection sampling, choose a normalized proposal probability mass function $g$ and a known finite constant $M$ satisfying $r(x)\le Mg(x)$ everywhere. Draw independent random variables $Y\sim g$ and $U\sim \mathrm{Unif}(0,1)$, accepting $Y$ when $U\le r(Y)/(Mg(Y))$. The joint probability of proposing and accepting $x$ is $r(x)/M$, so the overall acceptance probability is $Z/M$ and the accepted value has probability mass function $r(x)/Z$. Fresh trials therefore produce independent and identically distributed random variables with the desired probability distribution. For a fixed positive number $N$ of accepted values, the sample average $N^{-1}{\sum }_{i=1}^{N}f(Y_i)$ is an unbiased estimator of the expectation when that expectation is finite. Its variance is ${\mathrm{Var}}_p(f)/N$ if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance probability makes the method expensive.

For the Metropolis–Hastings algorithm, choose a proposal transition matrix $q$ and, at the current state $x$, propose $y\sim q(x,\cdot )$. Accept with the Metropolis–Hastings acceptance probabilityA proposal outside $S$ is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at $x$. This constructs a Markov chain satisfying detailed balance with $p$, without computing $Z$ or a global envelope. Estimate the expectation by averaging $f(X_i)$ over iterations, including repeated states after rejections. Keeping only accepted jumps generally changes the stationary distribution of the recorded process.

The Metropolis–Hastings algorithm produces dependent samples, so the variance of its average includes autocovariances; starting outside stationarity can also cause finite-run bias. With Markov chain irreducibility, suitable recurrence and an integrable $f$, the countable-state Markov chain ergodic theorem gives consistency. Aperiodicity is additionally needed for the usual convergence of one-time probability distributions. In contrast, accepted rejection sampling values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and mixing time of the Markov chain. Nonnegativity of $f$ alone does not guarantee a finite expectation or variance.

Here $q(x,y)=p(y)$, with fresh proposal randomness independent of the past. For $x,y\in S$, the Metropolis–Hastings acceptance probability isThus $P(x,y)=p(y)$ is independent of $x$, and $X_1,\dots ,X_N$ are independent and identically distributed random variables with probability distribution $p$, even if $X_0$ was chosen arbitrarily in $S$. The method becomes ordinary Monte Carlo method sampling from $p$. The average of $f(X_1),\dots ,f(X_N)$ is an unbiased estimator, with the variance stated in part (a). Including an arbitrary initial state would spoil this finite-sample property. This is the independent stationary proposal lemma.

Neither Markov chain irreducibility nor fast convergence follows from detailed balance. On two states, the identity transition matrix satisfies detailed balance for the uniform probability distribution, but neither state can reach the other.

Even after imposing Markov chain irreducibility and aperiodicity, considerIt satisfies detailed balance for $\pi =(1/2,1/2)$. Its nontrivial eigenvalue is $1-2\epsilon$, and, from state zero, its total variation distance from $\pi$ after $n$ steps is $\frac{1}{2}(1-2\epsilon {)}^n$. This approaches zero arbitrarily slowly as $\epsilon$ decreases. Detailed balance without rapid convergence separates correctness of a stationary distribution from reachability and speed.

Put $a=p(x)q(x,y)$ and $b=p(y)q(y,x)$. For $a+b>0$, the off-diagonal probability flux of the proposed rule isIf $a=b=0$, define both acceptance probabilities to be zero; both fluxes are zero. The diagonal detailed balance equations hold automatically, including the probability of rejected proposals. Summing the detailed balance equations over $x$ gives stationarity:The alternative rule therefore preserves $p$. The unknown normalizing constant cancels after replacing $p$ by $r$. This Barker acceptance probability is no larger than the Metropolis–Hastings acceptance probability for the same proposed move: if $t=b/a>0$, then $t/(1+t)\le \min (1,t)$. Preservation of $p$ still requires separate Markov chain irreducibility and convergence checks before it guarantees useful sampling.