Past exam of the MSc in advanced computer science course of the University of Oxford / 2022 / Computational game theory / 2

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.