Supernash Project

This figure represents the main method of the Supernash Project. One finds a Nash equilibrium in the Memory 1 Infinitely Repeated Game by finding a strategy that puts the blue dot into the dark region in the plane.

Introduction

We consider the infinitely repeated game. In each round, players can choose either to cooperate or defect. A strategy belongs to the Memory 1 space if it conditions its next move solely on the previous round. In our case, the strategy is parameterized by four probabilities representing the outcomes of the last round:

{CC, CD, DC, DD}

where the first character is the move of the first player and the second is that of the second player. These probabilities form the strategy {p_CC, p_CD, p_DC, p_DD}.

Goal

We define a Nash strategy x as one that satisfies:

π(y, x) < π(x, x)

for all strategies y, where π(y, x) is the long-run average payoff of strategy y against strategy x. It is given by the long-run frequencies of the repeated game:

π(x, y) = R · v_CC + S · v_CD + T · v_DC + P · v_DD

At first, checking every possible strategy y against a candidate strategy x seems daunting. However, a neat trick simplifies the process. Since the first player can choose to be on either side—{CC, CD} or {DC, DD}—the space of long-run frequencies is constrained to a two-dimensional subspace defined solely by the first player. Because the payoff is linear in these frequencies, the decision boundary for Nash equilibria becomes clear: a strategy can only be Nash if its self-payoff lies at an extreme of this linear function. Once a game {R, S, T, P} is set, we can adjust the strategy vector and visually determine if it is Nash!

This idea can be formulated analytically, yielding simple decision boundaries. For the full classification of all Nash Equilibria, see [WIP].