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

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.