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

Source paper: released examination archive, member 2019/T/a15684w1.pdf. The dated cover identifies the undergraduate Second Public Examination, Trinity Term 2020, Friday 5 June, opening at 09:30 BST. The archive directory is misleading. The cover allows four hours for completion and upload; all printed parts are solved below.

Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are $b$ and $nb$; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization $M=1$. The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is $n/2$ to each initial dataset.

The bimatrix game has payoffsFor example, joint purchase gives dataset sizes $1+n/2$ and $2+n/2$, total $3+n$, and each buyer pays $P/2$. A sole buyer gets the full corpus and pays $P$. The total payoff is $1-P$ whenever a purchase occurs and $1$ when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.

For the following calculations, setThe payoff differences “buy minus do not buy,” with the other player's action held fixed, areThese four differences give all the best response comparisons without mixing up row and column payoffs.

A weakly dominant strategy must be a best response to either opponent action. For X this requiresThe first is stronger because $t>0$. ThusFor Y the comparisons are $t/3-P\ge 0$ and $(t-P)/2\ge 0$, givingBelow each upper endpoint the corresponding strategy is strictly better against both opponent actions; at the endpoint one comparison ties and the other is strict. Thus the answers also satisfy the convention that weak dominance requires a strict advantage somewhere. Since expected payoffs are linear in the opponent's mixing probability, checking both opponent pure strategies suffices for every opponent mixed strategy.

At joint purchase, each player's gain from continuing to buy rather than deviating to $nb$ is $(t-P)/2$. Both actions are best responses exactly when this is nonnegative. ThereforeAt equality both players are indifferent to their individual unilateral deviations, which is permitted in a Nash equilibrium. The condition is less restrictive than requiring either player's action to be a weakly dominant strategy: only the opponent's actual action needs to be considered.

When neither buys, X's unilateral deviation gains $2t/3-P$, while Y's gains $t/3-P$. For both to be nonpositive, $P$ must exceed the larger threshold. HenceEquality is included because a zero-gain deviation does not violate a Nash equilibrium. Consequently both joint-purchase and joint-nonpurchase Nash equilibria exist throughout $2t/3\le P\le t$, a coordination region.

Neither asymmetric purchase outcome is a Nash equilibrium for any permitted $P>0,n>0$. At $(b,nb)$, X's chosen purchase requires $P\le 2t/3$, but Y's chosen nonpurchase, against X buying, requires $P\ge t$. These requirements are incompatible because $2t/3<t$.

At $(nb,b)$, Y's chosen purchase requires $P\le t/3$, whereas X's nonpurchase against a buying Y requires $P\ge t$. Again the inequalities are incompatible. Thus every Nash equilibrium in pure strategies has both players taking the same action; the conclusion is stronger than merely observing symmetry in their available actions, since their original market shares differ.

Write $P=999/1000$. Ifthen both players prefer buying against a buyer, since $(t-P)/2>0$. Both prefer not buying against a nonbuyer: $2t/3<2/3<P$ and $t/3<1/3<P$. These strict opposite best responses give the interior crossing of a coordination game.

An explicit fully mixed Nash equilibrium follows from indifference. Let $p$ be X's probability of buying and $q$ Y's. X is indifferent whenand Y is indifferent whenSolving givesBoth numerators and denominators are positive. For $p<1$ the required inequality is $2P-2t/3<P+t/3$, equivalent to $P<t$; the same comparison for $q<1$ again reduces to $P<t$. Thus $p,q\in (0,1)$, and the equations make both actions best responses for each player. By linearity of expected payoff, neither player can profit by any other mixed strategy. At $n=2997$ these formulas reach $p=q=1$ and are not fully mixed; the strict threshold matters.

The assignment is Pareto optimal. Write $a_i$ for the room selected by the $i$th student. Suppose another assignment $a^{\prime }$ makes every student at least as well off. The first student already selected their uniquely most valuable room, so $a_1^{\prime }=a_1$. Once the rooms of students $1,\dots ,i-1$ are fixed, the rooms available to student $i$ in the original serial dictatorship are exactly the rooms that remain after those fixed assignments. Student $i$ chose the unique maximum among them, so weak improvement requires $a_i^{\prime }=a_i$.

Mathematical induction fixes every student's room. Thus $a^{\prime }=a$ and nobody can be strictly better off, contradicting the definition of a Pareto improvement. Strict room rankings and the absence of allocation externalities are the essential assumptions: a student's utility is determined solely by their own room.^[ref]

No: arbitrary ties can produce an assignment that is not Pareto optimal. A two-student counterexample suffices. Give the first student value $1$ for both rooms; give the second student value $1$ for $r_1$ and $0$ for $r_2$. If the first student breaks the tie by taking $r_1$, the second must take $r_2$, and the utility vector is $(1,0)$.

Swapping the rooms gives utility vector $(1,1)$, so it is a Pareto improvement. Both choices in the original run maximized the corresponding student's available room value. The strict-ranking argument from (a) fails because the first student's utility need not decrease when that student's room changes.

The equilibrium assignment is $(S_1,S_2,S_3,S_4)\mapsto (r_2,r_3,r_4,r_1)$, with utility vector $(0.7,0.7,0.9,0.4)$. Apply backward induction to the finite perfect-information game, accounting for the two friendship pairs in every terminal assignment. Student $S_4$ receives the last room and has no remaining choice. Given the first two rooms, $S_3$ chooses the remaining room maximizing their own room value plus $0.4$ if adjacent to $S_2$.

The following complete third-stage comparisons summarize the continuations. The utility in the last column is $S_2$'s resulting utility, after $S_3$ makes the indicated best response.

For example, after $S_1$ takes $r_2$ and $S_2$ takes $r_3$, student $S_3$ compares $r_1$, giving $0$, with $r_4$, giving $0.5+0.4=0.9$. Choosing $r_4$ also gives $S_2$ the adjacency bonus, making $U_2=0.3+0.4=0.7$. The last room $r_1$ is adjacent to $S_1$'s $r_2$.

The table makes $S_2$ choose $r_3,r_3,r_2,r_2$ after first-stage choices $r_1,r_2,r_3,r_4$, respectively. Their resulting consequences for $S_1$ are $0.5,0.7,0$, and either $0$ or $0.4$. Thus $S_1$ strictly prefers $r_2$, proving the displayed outcome.

There is an off-path tie for $S_3$ after $(r_4,r_2)$, so the entire subgame perfect equilibrium strategy profile need not be unique. Either choice, or any mixture of them, gives $S_1$ at most $0.4$ after choosing $r_4$, below $0.7$. The equilibrium assignment on the played path is therefore unaffected by this tie. Specifying these optimal continuations at every history, including the unplayed ones, supplies a subgame perfect equilibrium rather than merely a proposed path.

No. Strict room values do not remove the allocation externalities generated by friends. Consider the following new instance, with the same friendship pairs $\{S_1,S_4\}$ and $\{S_2,S_3\}$ and friendship bonus $0.4$ for each student:Each row is strictly ranked and every room value is positive. In picking order $S_1,S_2,S_3,S_4$, backward induction gives the following continuations. Room numbers in a tuple are listed in student order.To check $S_2$'s incentives behind these continuations, the resulting utilities for their available choices, in ascending room order, are respectively $(0.50,0.70,0.02)$, $(0.01,0.70,0.42)$, $(0.41,0.50,0.02)$ and $(0.41,0.90,0.70)$. Student $S_3$'s own best responses determine those figures, and $S_4$ again takes the remaining room. All comparisons selecting these continuations are strict.

Hence $S_1$ chooses $r_2$ and the subgame perfect equilibrium outcome isBut the feasible assignmentstrictly improves $S_1$ and $S_4$ and leaves $S_2,S_3$ unchanged. Thus $a$ is not Pareto optimal. This is compatible with equilibrium: a Pareto improvement can require several players' actions to change. If $S_1$ alone takes $r_1$, the later best responses lead to $(r_1,r_3,r_2,r_4)$, not to $a^{\prime }$; anticipating that reaction gives $S_1$ only $0.50$.

Every subgame perfect equilibrium outcome is Pareto optimal under the stated consecutive-friend and bonus conditions. Partition the choosing order into blocks: a single student without a friend, or two friends who choose consecutively. Their slots in the choosing order are adjacent; the proof must separately establish when their allocated rooms will be adjacent.

Let $R$ be the rooms remaining before a friend block, with leader $i$ and follower $j$. Because $0\le v_{i,r},v_{j,r}\le 1$ and $f_i,f_j>1$, each friend strictly prefers every adjacent-to-friend allocation to every nonadjacent one. After leader $i$ takes room $r$ with an available adjacent room, follower $j$ therefore takes their uniquely highest-valued room among the available neighbors of $r$. The leader consequently knows they will receive the adjacency bonus.

If $R$ contains at least one pair of adjacent rooms, let $E(R)$ be its nonisolated rooms: the rooms having an available neighbor. Leader $i$ must choose from $E(R)$, because choosing there guarantees utility greater than $1$, whereas an isolated choice gives at most $1$. Since the bonus is then fixed and room values are distinct, the leader chooses their unique maximum-value room in $E(R)$. The follower chooses their unique best neighbor. Later students cannot change either allocated room, so later play cannot alter these two students' utilities.

If $R$ contains no adjacent pair, neither friend can obtain the bonus under any allocation of rooms from $R$. Both simply choose their uniquely most valuable remaining room in turn. Removing rooms cannot create a new physical adjacency, so no hidden later move can change that conclusion. A one-student block likewise chooses their unique best available room.

Now compare the equilibrium assignment $a$ with any proposed Pareto improvement $a^{\prime }$. Induct over these blocks, assuming earlier blocks' rooms are already fixed. Thus $a$ and $a^{\prime }$ have the same remaining set $R$ at the present block. A lone student's room must stay fixed by strict preferences.

For a friend block obtaining adjacency in $a$, both students must retain adjacency in $a^{\prime }$: losing a bonus larger than $1$ cannot be compensated by any room-value increase. The leader's room in $a^{\prime }$ must therefore belong to $E(R)$. It cannot differ from the unique highest-valued room the leader selected there without reducing that leader's utility. Once the leader's room is fixed, the follower likewise must retain the uniquely best available neighbor. If $R$ has no adjacent pair, both rooms stay fixed by the ordinary strict-ranking argument.

Thus every block's rooms are unchanged. The only assignment weakly improving all students is $a$ itself, so no strict improvement is possible. This proves Pareto efficiency of serial dictatorship with consecutive friends. The proof applies to every subgame perfect equilibrium, since the required choices at each block are strict best responses determined by the available rooms.

A simple cooperative game is a transferable utility game $(N,v)$ withA coalition of value $1$ is a winning coalition; a value-$0$ coalition loses. The displayed definition uses the usual monotone, nontrivial convention: the empty coalition loses and the grand coalition wins.

An induced subgraph game is a transferable utility game represented by a weighted undirected graph with one vertex per player; a coalition's value is the sum of the edge weights in its induced subgraph. With no self-loops,where each unordered pair is counted once and an absent edge has weight zero. Weights may have either sign. In an induced subgraph game with self-loops, write the loop weight at $i$ as ${\ell }_i$ and add ${\sum }_{i\in S}{\ell }_i$, counting each loop once. In particular, $v(\{i\})={\ell }_i$ when loops are allowed and is zero otherwise.^[ref]

No representation exists, even allowing arbitrary signed weights and self-loops. Every singleton coalition loses, so each loop weight must be ${\ell }_i=v(\{i\})=0$. Every two-player coalition wins, which then forcesThe represented grand-coalition value would consequently becontradicting its required value $1$. The obstruction is the additive edge representation, not a restriction that weights be nonnegative: the singleton and pair values already determine every relevant weight.

Yes; without self-loops, such a nontrivial simple cooperative game has exactly one positive edge, of weight $1$. For each pair,because singleton and loop contributions are zero. Summing all edge weights gives $v(N)=1$, so precisely one unordered pair $\{a,b\}$ has weight $1$, and all other pairs have weight zero.

Thus the winning coalitions are exactly those containing both $a$ and $b$. For any $0\le \lambda \le 1$, setThis payoff vector is efficient, since ${\sum }_i{x}_i=v(N)=1$. Every winning coalition receives $1$ and every losing coalition receives a nonnegative total, so all inequalities $x(S)\ge v(S)$ hold. Hence it belongs to the core of a cooperative game.

In fact these are all core allocations. Singleton conditions require $x_i\ge 0$, and the winning pair requires $x_a+x_b\ge 1$; efficiency then forces equality and zero payoffs outside the pair. The endpoints are both veto players, consistent with the general characterization of the core of a simple cooperative game.

No. Two positive self-loops and one negative edge give a simple cooperative game with an empty core of a cooperative game. Give players $1,2$ loop weights ${\ell }_1={\ell }_2=1$, put $w_{12}=-1$, and give every other loop and edge weight zero. For a coalition $S$,Thus a coalition wins exactly when it contains player $1$ or player $2$. This is monotone, has values in $\{0,1\}$, and satisfies $v(\varnothing )=0,v(N)=1$. Extra players for any $n\ge 3$ do not alter any coalition value.

The core singleton inequalities would require $x_1\ge 1$, $x_2\ge 1$ and $x_i\ge 0$ for every other player, while efficiency requires ${\sum }_i{x}_i=1$. These requirements are inconsistent. Equivalently, the two disjoint winning singleton coalitions leave no veto player. Signed weights are essential to this particular representation and are permitted in the induced subgraph game model.

A loop-free induced subgraph game is a convex cooperative game if and only if every edge weight is nonnegative. Necessity follows by applying the supermodular inequality to $S=\{i\}$ and $T=\{j\}$. Since both singleton values and the empty value are zero,

Conversely, direct cancellation of common edge contributions gives, for any coalitions $S,T$,Every summand is nonnegative, proving that $v$ is a supermodular set function and hence convexity. Equivalently, a player's marginal contribution to $S$ is ${\Delta }_i(S)={\sum }_{j\in S}{w}_{ij}$, which cannot decrease as $S$ grows. This establishes the convexity criterion for an induced subgraph game directly.^[ref]

There is exactly one such nontrivial game for every $n\ge 1$: the unanimity game requiring every player. PutIt is a simple cooperative game, and permuting players preserves every coalition value. Thus it has the required symmetry of players in a cooperative game. It is also a convex cooperative game: if both $S,T$ are winning, all four terms in the supermodular inequality have value $1$; if exactly one is winning, their union is $N$ and their intersection loses, giving equality $1=1$; if neither wins, the right-hand side is zero and the inequality follows from nonnegativity. For $n=1$ the same definition gives the sole player value $1$.

To prove uniqueness, first establish that convex simple games are unanimity games. If $S,T$ are winning coalitions, the supermodular inequality givesso their intersection is also winning. The family of winning coalitions is finite and nonempty. Its intersection $K$ is therefore winning and nonempty, since the empty coalition loses. Every winning coalition contains $K$, and monotonicity makes every superset of $K$ winning. Hence $v=u_K$.

If $K$ were a proper nonempty subset of $N$, take $i\in K$ and $j\notin K$, and let $T=N\setminus \{i,j\}$. Then $T\cup \{i\}=N\setminus \{j\}$ contains $K$ and wins, whereas $T\cup \{j\}=N\setminus \{i\}$ loses. This violates symmetry of players in a cooperative game, which requires those two coalition values to agree. Thus $K=N$, proving the claimed count. The “nontrivial” convention excludes the identically zero game; if that degenerate game were also called simple, it would supply one additional symmetric convex example.