Past exam of the computer science course of the University of Oxford / 2018 / Computational game theory / 2

A game tree is a rooted tree representing successive histories. A nonterminal vertex specifies the player who moves, its outgoing edges are the available actions, and each leaf specifies a terminal payoff for every player. A pure strategy specifies an action at every decision point belonging to that player, including decision points not reached by the eventual play.

For a perfect-information game, each player observes the exact preceding history. An extensive-form game with imperfect information additionally groups indistinguishable decision points into information sets, with compatible available actions. Chance moves, if present, carry specified probabilities; the displayed game has none. A subgame perfect equilibrium must prescribe a Nash equilibrium in every proper subgame as well as in the whole game.

Apply backward induction in games, or Zermelo's algorithm, from the terminal decision points. At node 4, player 1 chooses $R_4$ because $6>3$, giving continuation payoffs $(6,9)$. At node 5, player 1 chooses $L_5$ because $4>2$, giving $(4,6)$. At node 3, player 2 compares its continuation payoffs nine and six, so chooses $L_3$. At node 2, player 2 chooses $R_2$, receiving four rather than two.

At the root, player 1 consequently receives six from either action: $L_1$ leads to $(6,4)$ and $R_1$ to $(6,9)$. Thus there are two pure subgame perfect equilibria, with strategiesThe semicolon separates the players, and each list specifies the player's action at every one of its decision points. All four non-root choices are strict. If mixed strategies are included, every mixture between $L_1$ and $R_1$ at the root is also an equilibrium, with those other actions fixed. There are no further mixtures at the strict decision points.

For each history of the first two votes, voter 3 selects its favourite achievable winner. Writing rows for voter 1's vote and columns for voter 2's vote, the resulting continuation winners areFor example, after votes $B,C$, voter 3 can make either $B$ or $C$ win, and prefers $B$; a vote for $A$ would instead produce the tie-break winner $A$.

Voter 2 prefers $C$ to $B$ to $A$. Optimizing each row therefore gives continuation winners $C,B,C$ after voter 1's respective choices $A,B,C$. Voter 1 prefers $B$ to $C$ and therefore votes $B$, giving winner $B$ in every subgame perfect equilibrium.

Some histories admit several equally good votes, but they produce the same winning candidate. Since each voter strictly ranks the three possible winners, unique outcome under strict outcome preferences makes this winner independent of those action ties. This is backward induction over outcomes, not a claim that the entire equilibrium strategy profile is unique.

Yes: let the order be voter 2, then voter 3, then voter 1. When voter 1 moves last, it makes $A$ win whenever that is possible; otherwise it prefers $B$ to $C$. For the first two votes in this new order, its optimal continuation winners areRows now record voter 2's initial choice and columns voter 3's choice. In a three-way split, the specified tie-break produces $A$, which explains, for example, the off-diagonal $B,C$ entry.

Voter 3 optimizes its ranking $B\succ C\succ A$ in each row, giving the continuation winners $A,B,C$. Voter 2 then chooses $C$, its favourite of the three. The winner is therefore $C$ in every subgame perfect equilibrium, again by unique outcome under strict outcome preferences. In particular, if voter 2 starts with $C$, voter 3 must also vote $C$: either other vote lets the last voter force $A$.

In the final round, player 1 strictly accepts every $q_2>0$. In any subgame perfect equilibrium it must also accept $q_2=0$ with probability one. Otherwise, if that acceptance probability were $a<1$, offering zero would give player 2 only $a\alpha$. A sufficiently small positive offer would be accepted and yield more. No positive offer maximizes player 2's payoff either, because a smaller positive offer improves it. The same supremum argument rules out a mixed offer distribution attaining the missing maximum. Thus the final-round equilibrium uniquely has $q_2=0$, accepted, with payoffs $(0,\alpha )$.

In round one, player 2 therefore rejects $q_1<\alpha$ and accepts $q_1>\alpha$. At $q_1=\alpha$ it is indifferent, but equilibrium again forces acceptance with probability one: if acceptance were less likely, player 1 could improve on any proposed optimum with an offer just above $\alpha$. Since $\alpha <1$, player 1 strictly prefers the resulting positive payoff to rejection.

Consequently the unique equilibrium outcome is immediate agreement at $q_1=\alpha$, giving payoffs $(1-\alpha ,\alpha )$. The full strategies are: player 1 offers $\alpha$ initially and accepts every nonnegative final offer; player 2 accepts initial offers at least $\alpha$, rejects smaller ones, and offers zero in every reached final-round subgame. These prescriptions cover off-path histories too. Acceptance at indifference follows from the continuous-offer bargaining acceptance lemma, rather than an arbitrary tie-breaking convention.

Let $P_k$ be the initial proposer's share, measured as a fraction of the pie currently available, with $k$ rounds remaining. The last-round argument in part (e) gives $P_1=1$. Rejecting an offer leaves the responder as next proposer with a pie smaller by factor $\alpha$, so its continuation value is $\alpha P_{k-1}$. The current proposer offers exactly that amount, which is accepted by the continuous-offer bargaining acceptance lemma. HenceThe formula follows by summing a finite geometric series, or by induction in the recurrence. Agreement is immediate in every subgame, so this share is player 1's actual initial payoff.

For odd $k$, $P_k=(1+{\alpha }^k)/(1+\alpha )$ lies above $1/(1+\alpha )$ and decreases with $k$. For even $k$, $P_k=(1-{\alpha }^k)/(1+\alpha )$ lies below that value and increases with $k$. Thus prefer odd to even, fewer rounds among odd choices, and more rounds among even choices. For the given $k_1<k_2$, this simplifies to choose $k_1$ if $k_1$ is odd, and choose $k_2$ if $k_1$ is even. All comparisons are strict because $0<\alpha <1$. This is the finite-horizon bargaining parity effect.