Past exam of the computer science course of the University of Oxford / 2019 / Computational game theory / 1

The players are the two chains, each with the set of pure strategies $\{1,2,3,4,5\}$. A strategy profile $(x,y)$ gives the sites of $S$ and $C$. For later use, write the first player's payoff for a general street size asWhen $x<y$, count customers to the left of $(x+y)/2$, assigning value one rather than two to any midpoint customer. This gives $x+y-1$ whether the midpoint is an occupied building or lies between buildings. The other player receives $2k-u(x,y)$. At co-location, every customer's value is split, giving $k$ each.

For $k=5$, the payoff matrix for $S$ isRows and columns are indexed by sites $1,\dots ,5$; the full ordered payoff pair in cell $(x,y)$ is $(M_{xy},10-M_{xy})$. This discrete location game is a constant-sum game.

Neither player has a weakly dominant strategy among its pure strategies. Against an opponent at site one, the unique best response is site two, yielding $2k-2$. Co-location yields only $k$, and moving further right reduces one's payoff. Against an opponent at site $k$, the unique best response is $k-1$, by reflection. For $k\ge 4$, these two sites differ. No single pure strategy can therefore be a best response to both opposing actions, as a weakly dominant strategy would require.

Yes to both questions, for both players. Site one is strictly dominated by site two. Against opposing site $y$, the payoff difference isEvery difference is positive for $k\ge 4$. By reflection, site $k$ is strictly dominated by site $k-1$. These endpoint actions are therefore also weakly dominated strategies, since strict dominance is stronger than the requirement of being no worse everywhere and better somewhere.

If a player chooses site $x$, the opponent can co-locate and hold its payoff to $k$. Among opposing sites to its right, the lowest payoff is obtained against $x+1$, giving $2x$. Among opposing sites to its left, the lowest is against $x-1$, giving $2(k-x+1)$. Thus the pure-action security level payoff isThe expression remains valid at an endpoint, where the missing-side term is redundant. It reaches its largest possible value $k$ exactly when $k/2\le x\le k/2+1$. Hence the pure maxmin strategies areReflection gives the same answer for the other player.

Both players can guarantee $k$ by part (d), so at any Nash equilibrium each must receive at least $k$. Their payoffs sum to $2k$, forcing both equilibrium payoffs to equal $k$.

Moreover, an equilibrium action must itself have the maxmin guarantee $k$. If a player's chosen action allowed an opposing response that reduced its payoff below $k$, that response would give the opponent more than $k$, a profitable unilateral deviation. Thus both equilibrium sites belong to the central set identified in part (d).

Conversely, if both choose from that central set, each chosen action guarantees $k$. Neither can improve above $k$, because the other player's fixed central action still guarantees the other player $k$. Consequently, all pure Nash equilibria areFor even $k$, this includes both co-located central profiles and both orders of the two distinct central sites.

There is no pure Nash equilibrium. If the firms choose different sites, $S$ serves at least its own building, so $C$ receives less than $2k$. By moving onto $S$'s site, $C$ makes every customer equidistant from the two shops and wins every tie, obtaining $2k$. Thus any separated profile has a profitable unilateral deviation by $C$.

At any co-located profile, $S$ receives zero. It can move to a different site and capture at least that site's customers, obtaining at least two. Thus every co-located profile also has a profitable unilateral deviation. These cases exhaust all pure strategy profiles.

Write $k=2m+1$, where $m\ge 2$. For three distinct sites $a<b<c$, the left, middle and right firms receive respectivelyThese follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy $\ell <r$, the final entrant compares $2(\ell -1)$ at $\ell -1$, $2(k-r)$ at $r+1$, and $r-\ell$ at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.

First suppose $C$ opens at the central site $m+1$. If $S$ chooses $s\le m$, the final entrant's best possible payoffs on the left, right and interior are at most $2m-2$, exactly $2m$, and at most $m$, respectively. Hence $N$'s unique best response is $m+2$. The resulting payoff to $S$ is $m+s$, uniquely maximized on that side at $s=m$. Reflection gives the other optimal choice $s=m+2$, followed by $N=m$. Under either choice, $C$ receives only $2$. Any mixture of the tied optimal second-mover choices has the same consequence.

Now let $C$ deviate to $c=m$. If $S$ chooses $s<m$, the unique final best response is $m+1$, yielding $S$ at most $2m-2$. If $S$ chooses $m+1$, the unique final best response is $m+2$, yielding $S$ only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:

Accordingly, in every subgame perfect equilibrium continuation after $C=m$, the second mover must choose a site $s\ge m+2$. This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.

For any such $s$, every legal final site gives $C$ at least three. If $N$ lies left of $m$, then $C$ is the middle firm and receives $s-N\ge 3$. If $N$ lies right of $m$, then $C$ is the left firm and receives $m+\min (s,N)-1\ge 2m\ge 4$. Thus the deviation gives $C$ at least $3$, against every subgame-perfect continuation, whereas the central opening gives it $2$.

In this original example, a final-mover tie produces the line segment for $S=6$: its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing $S=7$, so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.

A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have $C$ open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.