# Elliptic curves come to date night

Willa is an economist and Cara is a mathematician, so together they have decided to turn the problem of which game to play into a separate meta-game. Because they both love numbers, Willa and Cara start by creating matrices...

# Elliptic curves come to date night

Ursula Whitcher
Mathematical Reviews (AMS)

In game theory, the Nash equilibrium describes a situation where neither player will benefit from changing strategies. Recently, two experts in applied geometry, İrem Portakal and Bernd Sturmfels, showed that a different notion of equilibrium has an intriguing geometric structure. Let's explore the shape of decision-making in the context of a simple cooperative game: what to do for date night.

İrem Portakal at Oberwolfach (photo used by permission from Portakal)

Bernd Sturmfels at Oberwolfach (CC BY-SA 2.0 DE DEED, cropped for display)

## Board games for date night

Imagine a couple, Willa and Cara, who like to play board games on Friday night. Willa's favorite game is Wingspan, a game where players learn about different kinds of birds. Cara's favorite is the city-building game Carcassonne. Willa works from home on Fridays, while Cara spends all day on campus, so the pair has agreed that Willa will clear the table and set up a game, while Cara brings home a suitable dessert: Belgian waffle fixings for Wingspan, or delicate cookies from their favorite French bakery for Carcassonne. However, Friday mornings are busy, and sometimes the pair doesn't communicate effectively: Willa might set up Wingspan while Cara grabs cookies, or Willa might try to please her partner by setting up Carcassonne while Cara is choosing ice cream and fruit to top waffles. This isn't the end of the world, but both women agree that date night is better when everything goes according to plan.

A Wingspan accessory shaped like a bird feeder (Pongrácz Zsolt, CC BY-SA 3.0 DEED)

Willa is an economist and Cara is a mathematician, so together they have decided to turn the problem of which game to play into a separate meta-game. Because they both love numbers, Willa and Cara start by creating matrices called "payoff matrices" to quantify exactly how happy they are in each situation. The rows represent the choice of board game (Wingspan or Carcassonne), while the columns represent the night's dessert (waffles or cookies). Here's Willa's matrix:

$\begin{pmatrix}7 & 0 \\ 0 & 3 \end{pmatrix}$

(Willa's zero represents "fine": Wingspan and cookies is OK, she reasons, but Wingspan and waffles is so much better.)

Cara enjoys the local bakery's cookies even when they don't match the game, so her matrix looks a little different:

$\begin{pmatrix}3 & 1 \\ 0 & 6 \end{pmatrix}$

(Game theory experts may notice that Willa and Cara's date night scenario is similar to a standard example game called "Bach or Stravinsky?" The Willa and Cara example uses slightly less special payoff matrices. It's also easy to imagine playing the same board game over and over, while only a few lucky couples live in towns where they can choose between full Bach and Stravinsky concerts on a regular basis.)

Willa and Cara could solve their communication problem by always defaulting to waffles and Wingspan. This way, nobody has to make a decision, and everyone always has positive happiness. There is no incentive for Cara to cheat by bringing home cookies instead, since she knows Willa is already setting up Wingspan; similarly, there's no reason for Willa to back out of the agreement and start setting up Carcassonne when she already knows that Cara is buying waffle fixings. "Always waffles and Wingspan" is an example of a Nash equilibrium point. There's another equilibrium point for "always cookies and Carcassonne".

Although always choosing the same game and dessert combination leads to happiness in the short term, over time the partner who never gets to play her favorite game may begin to feel misused. Willa and Cara could try to address this problem using probability. Perhaps Willa reasons that $7/10$ of her possible happiness comes from setting up Wingspan, so she should do so $70\%$ of the time. Similarly, Cara notices that $1/10 + 6/10 = 7/10$ of her possible happiness comes from buying cookies, so she decides to buy cookies $70\%$ of the time. This kind of probabilistic approach is called a "mixed strategy" in the economics literature.

What happens when Willa and Cara implement their $70\%$ strategies simultaneously? We can represent the possible outcomes using a probability matrix with entries $p_{ij}$. Again, rows represent the choice of game, while columns represent the choice of dessert. We use the index 1 for Willa's favorites, and the index 2 for Cara's favorites.

$\begin{pmatrix}p_{11} & p_{12} \\ p_{21} & p_{22} \end{pmatrix} = \begin{pmatrix}21/100 & 49/100 \\ 9/100 & 21/100 \end{pmatrix}$

We see $p_{12} = 49/100$. That means Willa and Cara will end up with Wingspan and cookies, nobody's favorite outcome, almost half the time!

If Willa and Cara can coordinate their random choices, other solutions emerge. For example, they could flip a coin on Friday mornings and choose Wingspan and waffles for heads but Carcassonne and cookies for tails. Here's the resulting, much simpler probability matrix:

$\begin{pmatrix}1/2 & 0 \\ 0 & 1/2 \end{pmatrix}$

One way to compare the coin-flip strategy with the uncoordinated $70\%$ strategy is to multiply each probability by the corresponding entries in the payoff matrices to compute an expected payoff. For the uncoordinated strategies, we have:

$(7\cdot\frac{21}{100} + 0 \cdot \frac{49}{100} + 0 \cdot \frac{9}{100} + 3 \cdot \frac{21}{100}) + (3\cdot\frac{21}{100} + 1 \cdot \frac{49}{100} + 0 \cdot \frac{9}{100} + 6 \cdot \frac{21}{100}) = 4.48.$

For the coordinated coin-flip strategy, we have

$(7\cdot\frac{1}{2} + 0 \cdot 0 + 0 \cdot 0 + 3 \cdot \frac{1}{2}) + (3\cdot\frac{1}{2} + 1 \cdot 0 + 0 \cdot 0 + 6 \cdot \frac{1}{2}) = 9.5.$

That's a quantifiably massive increase in happiness!

## A different type of equilibrium

İrem Portakal and Bernd Sturmfels are interested in a notion of game-theoretic equilibrium developed by the German philosopher Wolfgang Spohn. The idea is to use conditional expected payoff. These are the payoffs players can anticipate when they happen to make a specific choice. For example, the total probability that Willa will choose Wingspan is $p_{11} + p_{12}$. That means her conditional expected payoff from Wingspan is:

$7\cdot \frac{p_{11}}{p_{11} + p_{12}} + 0 \cdot \frac{p_{12}}{p_{11}+ p_{12}}.$

If we use the values for the probability matrix from the simultaneous $70\%$ strategies, that makes Willa's conditional expected payoff from Wingspan

$7\cdot \frac{21/100}{21/100+49/100} + 0 \cdot \frac{49/100}{21/100+49/100} = 2.1.$

Using the same values, her conditional expected payoff from Carcassonne is

$0\cdot \frac{p_{21}}{p_{21} + p_{22}} + 3 \cdot \frac{p_{22}}{p_{21}+ p_{22}} =$
$0 \cdot \frac{9/100}{9/100+21/100} + 3 \cdot \frac{21/100}{9/100+21/100} = 2.1.$

Since Willa's conditional expected payoff is the same for either game, she has no incentive to push for a probability matrix where Wingspan happens slightly more often or slightly less often.

Spohn defines a mixed strategy (for us, a probability matrix) to be a dependency equilibrium if every player has the same conditional expected payoff for each choice they can make. This style of analysis sounds a lot like the Nash equilibrium, and indeed, every Nash equilibrium point is also a dependency equilibrium. (This claim needs one caveat: it only works when the notion of dependency equilibrium is defined. Because we can't divide by zero, conditional expected payoff doesn't make sense when there are choices that a player never makes. If we want to analyze scenarios like the "always waffles and Wingspan" strategy described above, we'll need to use other methods; Spohn suggests using a limit argument.)

Nash equilibrium points are typically isolated: unless the payoff matrices are very special, they form a finite set. In contrast, there can be many dependency equilibrium points. For Willa and Cara's payoff matrices, to find all of the dependency equilibria, we need to solve the system of simultaneous equations

$7\cdot \frac{p_{11}}{p_{11} + p_{12}} + 0 \cdot \frac{p_{12}}{p_{11}+ p_{12}} = 0\cdot \frac{p_{21}}{p_{21} + p_{22}} + 3 \cdot \frac{p_{22}}{p_{21}+ p_{22}}$

and

$3\cdot \frac{p_{11}}{p_{11} + p_{21}} + 0 \cdot \frac{p_{21}}{p_{11}+ p_{21}} = 1\cdot \frac{p_{12}}{p_{12} + p_{22}} + 6 \cdot \frac{p_{22}}{p_{12}+ p_{22}}$

for the probabilities $p_{11}$, $p_{12}$, $p_{21}$, and $p_{22}$. (As usual, Willa's choices correspond to rows, while Cara's choices correspond to columns.)

Portakal and Sturmfels point out that if we clear denominators, we can transform the system to a simpler-looking matrix problem. For Willa's equation, we use the matrix

$M_W = \begin{pmatrix} p_{11} + p_{12} & 7 p_{11} + 0 p_{12} \\ p_{21}+ p_{22} & 0 p_{21} + 3p_{22} \end{pmatrix}.$

For Cara's equation, we use the matrix

$M_C = \begin{pmatrix} p_{11} + p_{21} & 3 p_{11} + 0 p_{21} \\ p_{12}+ p_{22} & 1 p_{12}+ 6 p_{22} \end{pmatrix}.$

The dependency equilibria are given by values of $p_{11}$, $p_{12}$, $p_{21}$, and $p_{22}$ such that $\det M_W = \det M_C = 0$. For Spohn, the algebraic intricacy of the set of all dependency equilibria is a drawback. For Portakal and Sturmfels, it's an exciting opportunity to apply the geometry of polynomials.

## A geometric space for probabilities

We want to describe the set of all dependency equilibria for Willa and Cara's game night game. But before we do so, we need to describe the set they live in: the space of all possible probability matrices for a game. There are several ways to go from a probability matrix to a point in a geometric space. For our two-player, two-outcome game, a simple way to find a point in a geometric space would be to think of the four possible probabilities, $p_{11}$, $p_{12}$, $p_{21}$, and $p_{22}$, as coordinates of a vector $(p_{11}, p_{12}, p_{21}, p_{22})$ in $\mathbb{R}^4$. We know each individual probability must be greater than or equal to zero, and we have the constraint that $p_{11} + p_{12} + p_{21} + p_{22} =1$. Thus, the possible probability vectors lie inside a region in $\mathbb{R}^4$ bounded by the hyperplane $p_{11} + p_{12} + p_{21} + p_{22} =1$ and the four coordinate hyperplanes. The shape of this region is called a simplex; simplices are higher-dimensional generalizations of triangles and tetrahedra.

Portakal and Sturmfels use a different strategy. Their method is a bit more involved, but it will allow us to lean on three-dimensional geometric intuition. We start by observing that if we have a list of any four positive numbers $(a,b,c,d)$, we can convert to a legal probability four-tuple by dividing by their sum: we get $(\frac{a}{a+b+c+d},\frac{b}{a+b+c+d},\frac{c}{a+b+c+d},\frac{d}{a+b+c+d})$, which satisfies the equation

$\frac{a}{a+b+c+d}+\frac{b}{a+b+c+d}+\frac{c}{a+b+c+d}+\frac{d}{a+b+c+d} = 1.$

Of course, $(2a,2b,2c,2d)$ would yield the same probability four-tuple, because the 2s in the numerator and denominator would cancel. In fact, multiplying $a$, $b$, $c$, and $d$ by any positive number results in the same probability four-tuple.

This equivalence is reminiscent of a famous geometric space, the real projective space $\mathbb{R}\mathbb{P}^3$. We can build $\mathbb{R}\mathbb{P}^3$ by starting with the four-dimensional space $\mathbb{R}^4$, removing the origin $(0,0,0,0)$, and imposing the rule that scalar multiples of the remaining points are equivalent. That is, $(a,b,c,d)$ and $(ka,kb,kc,kd)$ are equivalent for any $k \in \mathbb{R} - 0$.

Thinking about the shape of all of real projective space at once can be mind-bending. But $\mathbb{R}\mathbb{P}^3$ contains a friendly copy of $\mathbb{R}^3$: as long as $d \neq 0$, we can multiply all the points by $\frac{1}{d}$, yielding a subspace containing points of the form $(a,b,c,1)$. Portakal and Sturmfels focus on probability four-tuples where all four probabilities are positive. They view these four-tuples $(p_{11}, p_{12}, p_{21}, p_{22})$ as points inside the region of $\mathbb{R}\mathbb{P}^3$ where all coordinates are positive. If we like, we can divide through by the last coordinate and view probability four-tuples as specifying points in $\mathbb{R}^3$ where all the coordinates are positive. If we do end up in a situation where we need to allow some coordinate to be zero, we can always take a limit.

## The geometry of dependency equilibria

Now we're ready to visualize the dependency equilibria for Willa and Cara's game! Remember, we're considering the points where $\det M_W = \det M_C = 0$. Let's divide through by the last coordinate as we discussed above, setting $a = p_{11}/p_{22}$, $b=p_{12}/p_{22}$, and $c = p_{21}/p_{22}$. That means we're looking at solutions to the system of equations $-7ac - 4a + 3b = -2ab + bc + 3a + 6b = 0$. The result is a curve called the Spohn curve, realized as the intersection of two surfaces in $\mathbb{R}^3$.

The red and blue surfaces intersect in the Spohn curve for Willa and Cara's game.

Portakal and Sturmfels show that every $2 \times 2$ game—that is, every game with two players, each of whom has two choices— has a Spohn curve of a very special type: it's an elliptic curve. If we look at solutions to their equations over the complex numbers, elliptic curves have the topology of a torus—that is, a donut shape. For Spohn curves, we're only considering a real slice.

A mathematical torus

Elliptic curves are famous for their multitude of applications. In elliptic curve cryptography, points on specific elliptic curves are used to build systems for encrypting and decrypting messages. Loyal readers of the Feature Column may also recall that elliptic curves also appear in physics problems involving Feynman diagrams.

Maybe it's time for Willa and Cara to consider adding donuts to their date night rotation!