Combinatorics of Correlated Equilibria

Abstract

We study the correlated equilibrium polytope P_G of a game G from a combinatorial point of view. We introduce the region of full-dimensionality for this class of polytopes and prove that it is a semialgebraic set for any game. Using a stratification via oriented matroids, we propose a structured method for describing the possible combinatorial types of P_G, and show that for $(2\times n)$-games, the algebraic boundary of the stratification is a union of coordinate hyperplanes and binomial hypersurfaces. Finally, we provide a computational proof that there exists a unique combinatorial type of maximal dimension for generic $(2\times 3)$-games.

KEYWORDS:

• correlated equilibrium
• combinatorial type
• convex polytope
• oriented matroid strata
• semialgebraic set

MATHEMATICS SUBJECT CLASSIFICATION:

• 14P10
• 52B05
• 52B40
• 52C40
• 91A05
• 91A10

1 Introduction

In 1950, Nash published a very influential two-page article [12] proving the existence of a Nash equilibrium for any finite game. This opened many new fronts, not only in game theory, but also in areas such as economics, computer science, evolutionary biology, quantum mechanics, and the social sciences. To study Nash equilibria one assumes that the actions of the players are independent and completely separated from any exterior influence. Moreover, these can be described as a system of multilinear equations [20, Section 6]. However, there exist cases where a Nash equilibrium fails to predict the most beneficial outcome (e.g. Pareto optimality) for all players. There are several approaches, rooted in the concept of a dependency equilibrium, which generalize Nash equilibria by imposing dependencies between the actions of players. This class of equilibria has been studied from the point of view of algebraic statistics and computational algebraic geometry [15–17, 19]. On the other hand, Aumann introduced the concept of a correlated equilibrium, which assumes that there is an external correlation device such as a mediator or some other physical source. The resulting correlated equilibria are probability distributions of recommended joint strategies [1, 2]. In contrast to Nash equilibria and dependency equilibria, correlated equilibria are significantly less computationally expensive, since they only require solving a linear program [14]. In other words, the set of such equilibria can be described by linear inequalities in the probability simplex and thus form a convex polytope called the correlated equilibrium polytope. In this article, we study combinatorial properties of correlated equilibrium polytopes with methods from convex geometry and real algebraic geometry.

We illustrate the concept of correlated equilibrium in an example: Two cars meet at a crossing. Both drivers would like to continue to drive, but, even more importantly, would also like to avoid a car crash. Thus, each of the drivers prefers not to drive in case the other chooses to drive. We assume that both drivers are unable to communicate with each other. This is a classic game in game theory known as the Chicken game or Hawk-Dove game, and we formalize this in Examples 2.1, 2.3, 2.6 and 5.1. However, this situation changes drastically if there is a traffic light installed at this crossing. We can view the traffic light as a neutral exterior party, that gives a recommendation to each player in showing green or red lights; here we assume that each driver only knows their own given recommendation. If a fixed driver is given such a recommendation (for example a red light), the driver now ponders about deviating from this recommendation in benefit of their own (selfish) good, assuming that the other player adheres to their own given recommendation. If both drivers decide not to deviate from the recommendation given by the traffic lights, a correlated equilibrium is achieved.

Fig. 1 The correlated equilibrium polytope of the Traffic Lights example is a bipyramid where three of its vertices are Nash equilibria. Its f-vector is $(1,5,9,6,1)$ and its face lattice can be seen on the right.

Fig. 3 A 3-dimensional correlated equilibrium polytope (green) inside the probability simplex ${\Delta }_3$ (yellow) for a $(2\times 2)$-game. Its Nash equilibria (black) are the intersection with the Segre variety (red). This picture applies to the Traffic Lights example (Examples 2.1, 2.3, 2.6) as well as the Hawk-Dove game (Example 5.1).

To our knowledge, there are no articles concerning the combinatorics of correlated equilibrium polytopes in the language of convex geometry up to this date, despite the fact that the concept of correlated equilibria is a topic of extensive research in economics and game theory. In this article, we study this class of polytopes from a combinatorial perspective. In general, the correlated equilibrium polytope can exhibit a great variety of distinct combinatorial structures. This is not surprising as it is proven that any convex polytope can be realized as the correlated equilibrium payoffs of an n-player game [8]. Even classifying necessary conditions under which the correlated equilibrium polytope is of maximal dimension is highly nontrivial [21]. This is also an interesting question from a game theoretical perspective, in particular for the computation of Nash equilibria which is PPAD-complete [6]. In this case, Nash equilibria lie on the relative boundary of the correlated equilibrium polytope (Proposition 2.7). However, there are examples of games where the correlated equilibrium polytope is not full dimensional and Nash equilibria lie in the relative interior [11, Proposition 2]. To study full-dimensional correlated equilibrium polytopes, we introduce the region of full-dimensionality, a set that classifies under which conditions the correlated equilibrium polytope has maximal dimension.

Theorem 4.2.

The region of full-dimensionality is a semialgebraic set and can be explicitly described.

The full description of this semialgebraic set can be found on 7. We continue the study of the combinatorial structure of correlated equilibrium polytopes by introducing a linear space called the correlated equilibrium space, and consider an oriented matroid stratification inside this space. This is a stratification of the linear space, in which regions give rise to the different combinatorial types of correlated equilibrium polytopes. We study the algebraic boundary of the stratification for $(2\times n)$-games, which turns out to be generated by binomials corresponding to $(2\times 2)$-minors and $(4\times 4)$-minors of a certain matrix (Theorem 5.8). These investigations yield novel insights into the possible combinatorial types of generic $(2\times 3)$-games. The term generic games is used in relation to the algebraic boundary explained in Theorem 5.8.

Theorem 5.9.

Let G be a generic $(2\times 3)$-game and P_G be the associated correlated equilibrium polytope. Then one of the following holds:

• P_G is a point,

• P_G is of maximal dimension 5 and of a unique combinatorial type,

• There exists a $(2\times 2)$-game $G\prime$ such that $P_{G\prime }$ has maximal dimension 3 and is combinatorially equivalent to P_G.

Supported by the above theorem and our computations [9] for generic $(2\times n)$-games G (where $n\le 5$), we conjecture that if P_G is not of maximal dimension, then there exists a smaller $(2\times k)$-game $G\prime$ with k < n such that $P_{G\prime }$ is a full-dimensional polytope and P_G is combinatorially equivalent to $P_{G\prime }$ (Conjecture 5.1).

Overview

We first provide a short introduction for the necessary concepts from game theory in Section 2, including correlated equilibria and Nash equilibria. In Section 3 we describe the correlated equilibrium cone, a convex polyhedral cone which captures the geometry of the correlated equilibrium polytope, and describe the correlated equilibrium space. We study the region of full-dimensionality in Section 4. Finally, we consider the possible combinatorial types through the oriented matroid stratification in Section 5. All results are illustrated with examples for games of types $(2\times 2),(2\times 3)$ and, whenever possible, games of type $(2\times 2\times 2)$. All referenced code and a detailed study of some examples with visualizations can be found on MathRepo [9]:

https://mathrepo.mis.mpg.de/correlated-equilibrium

2 The correlated equilibrium polytope

Let n be the number of players in a normal-form game. Each player $i\in [n]$ has a fixed set of pure strategies $s_1^{(i)},\dots s_{d_i}^{(i)},d_i\in \mathbb{N}$. It is practical to think of each strategy as a single move that a player can play, and all players perform their single move simultaneously. Afterward, the game is over, so the choices of the possible moves can be seen as the outcome of the game. A pure joint strategy is a tuple $s_{j_1\dots j_n}=(s_{j_1}^{(1)},\dots ,s_{j_n}^{(n)})$ of strategies, where each player $i\in [n]$ chooses to play a fixed strategy $s_{j_i}^{(i)}$ with $j_i\in [d_i],i\in [n]$. The payoff $X_{j_1\dots j_n}^{(i)}\in \mathbb{R}$ of player i at $s_{j_1\dots j_n}$ is the quantity of how beneficial player i values the combination $(s_{j_1}^{(1)},\dots ,s_{j_n}^{(n)})$ of strategies as outcome of the game. A mixed strategy of a single player i is an action with probability $p^{(i)}=(p_{j_1}^{(i)},\dots ,p_{j_{d_i}}^{(i)})$, i.e. $p_{j_1}^{(i)},\dots ,p_{j_{d_i}}^{(i)}\ge 0$ and ${\sum }_{k=1}^{d_i}{p}_{j_k}^{(i)}=1$. We can view this geometrically as a point in the $(d_i-1)$-dimensional probability simplex ${\Delta }_{d_i-1}$.

Formally, a $(d_1\times \cdots \times d_n)$-game in normal form is a tuple $G=(n,S,X)$, where $S=(S^{(1)},\dots ,S^{(n)})$ is the collection of strategies $S^{(i)}=(s_1^{(i)},\dots ,s_{d_i}^{(i)})$ of all players, and $X=(X^{(1)},\dots ,X^{(n)})$ is the collection of all $(d_1\times \cdots \times d_n)$-payoff tensors. In particular, if n = 2, then each $X^{(i)}$ is a $(d_1\times d_2)$-matrix and called the payoff matrix of player i.

Example 2.1

(Traffic Lights). Recall the example from the introduction, in which two cars meet at a crossing and would like to avoid a car crash. Formally, each player $i\in [2]$ has the strategies $s_1^{(i)}=$ “go” and $s_2^{(i)}=$ “stop”. The bimatrix below shows the payoffs of both players simultaneously, where each entry is a tuple $(X_{j_1{j}_2}^{(1)},X_{j_1{j}_2}^{(2)})$ of the payoff of each player for the tuple of strategies $(s_{j_1}^{(1)},s_{j_2}^{(2)}),j_1,j_2\in [2]$ as the expected outcome of the game.

Table

		Player 2
		go	stop
Player 1	go	$(-99,-99)$	(1, 0)
	stop	(0, 1)	0, 0

We may interpret the given payoffs such that each of the players prefers to go (with payoff $X_{12}^{(1)}=X_{21}^{(2)}=1$), if the other driver stops. However, both drivers choosing to drive is the worst possible outcome for each of the players individually (with payoff $X_{11}^{(i)}=-99$ for both players). Since there is no interaction between the players, and the payoffs of a car crash are very negative, the players are very likely not to risk a move, although this is not optimal for either of these players ($X_{22}^{(i)}=0$ for both players). This is the motivation for introducing the concept of correlated equilibrium, in which the assumptions allow a dependence on the moves of the players by the suggestion of an external party e.g. a traffic light. We continue with this in Examples 2.3 and 2.6.

We now allow a third, independent party to influence the game from the outside. Let $\tilde{S}=\left\{s_{j_1\dots j_n}\right|j_i\in [d_i],i\in [n]\}$ be the set of all pure joint strategies of the game. The external party draws such a pure joint strategy with probability $p_{j_1\dots j_n}\ge 0$, called a mixed joint strategy. Such a joint probability distribution is a vector (or a tensor) $p=(p_{j_1\dots j_n}|j_i\in [d_i],i\in [n])$, such that ${\sum }_{j_1=1}^{d_1}\cdots {\sum }_{j_n=1}^{d_n}{p}_{j_1\dots j_n}=1$. The set of all joint probability distributions is the probability simplex ${\Delta }_{d_1\cdots d_n-1}$.

Definition 2.2

(Correlated Equilibrium). Let G be a game with payoffs $X=(X^{(1)},\dots ,X^{(n)})$. A point $p\in {\Delta }_{d_1\cdots d_n-1}$ is a correlated equilibrium if and only if (2.1) $$\sum _{j_1=1}^{d_1}\cdots \widehat{\sum _{j_i=1}^{d_i}}\cdots \sum _{j_n=1}^{d_n}\left(X_{j_1\cdots j_{i-1}k{j}_{i+1}\cdots j_n}^{(i)}-X_{j_1\cdots j_{i-1}l{j}_{i+1}\cdots ,j_n}^{(i)}\right)p_{j_1\cdots j_{i-1}k{j}_{i+1}\cdots j_n}\ge 0.$$(2.1) for all $k,l\in [d_i]$, and for all $i\in [n]$. The linear inequalities in (2.1) together with the linear constraints $$p_{j_1\dots j_n}\ge 0\text{ for }{j}_i\in \left[d_i\right],i\in \left[n\right],\text{ and }\sum _{j_1=1}^{d_1}\cdots \sum _{j_n=1}^{d_n}{p}_{j_1\dots j_n}=1$$ define the set of all correlated equilibria of the game. The set of all such equilibria is the correlated equilibrium polytope P_G of the game G.

The ambient space of the polytope P_G has dimension $d_1\cdots d_n$. By definition, the maximal dimension that P_G can achieve is $d_1\cdots d_n-1$. In the literature, in this case, P_G is often called full-dimensional. To avoid confusion with conventions in convex geometry, we refer to P_G as having maximal dimension.

Example 2.3

(Traffic Lights). We continue with Example 2.1. Here, the third party is given by a traffic light at the crossing. The traffic light gives the recommendation “go” to a driver if it turns green, and “stop” if it turns red. The traffic light draws randomly from one of the combinations of strategies. Let $p_{j_1{j}_2}$ be the probability with which the traffic light draws the pure joint strategy $s_{j_1{j}_2}$. The point $p=(p_{11},p_{12},p_{21},p_{22})$ is a correlated equilibrium if and only if $p_{j_1{j}_2}\ge 0,p_{11}+p_{12}+p_{21}+p_{22}=1$ and $$\begin{array}{c}(X_{22}^{(1)}-X_{12}^{(1)})p_{22}+(X_{21}^{(1)}-X_{11}^{(1)})p_{21}\ge 0,\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}(X_{12}^{(1)}-X_{22}^{(1)})p_{12}+(X_{11}^{(1)}-X_{21}^{(1)})p_{11}\ge 0,\\ (X_{22}^{(2)}-X_{21}^{(2)})p_{22}+(X_{12}^{(2)}-X_{11}^{(2)})p_{12}\ge 0,\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}(X_{21}^{(2)}-X_{22}^{(2)})p_{21}+(X_{11}^{(2)}-X_{12}^{(2)})p_{11}\ge 0.\end{array}$$

With the payoffs as given in the bimatrix in Example 2.1 these inequalities evaluate to $$\begin{array}{c}-p_{22}+99p_{21}\ge 0,p_{12}-99p_{11}\ge 0,\\ -p_{22}+99p_{12}\ge 0p_{21}-99p_{11}\ge 0.\end{array}$$

The correlated equilibrium polytope, i.e. the points p that satisfy these inequalities, has 5 vertices with coordinates $(0,0,1,0),$ $(0,1,0,0),$ $(\frac{1}{10000},\frac{99}{10000},\frac{99}{10000},\frac{9801}{10000}),$ $(0,\frac{1}{101},\frac{1}{101},\frac{99}{101}),$ $(\frac{1}{199},\frac{99}{199},\frac{99}{199},0)$. This polytope is depicted in Figure 2.

Fig. 2 The vertices of the correlated equilibrium polytope for the Traffic Lights example (Example 2.3).

The next proposition shows that two affinely dependent games define the same correlated equilibrium polytope.

Proposition 2.4.

Any affine linear transformation of the payoff tensors $X^{(i)}$ with positive scalars leaves the polytope P_G invariant. More precisely, let $G=(n,S,X)$ be a game. For each $i\in [n]$, fix $t_i\in \mathbb{R},{\lambda }_i\in {\mathbb{R}}_{>0}$ and let ${\tilde{X}}_{j_1\dots j_n}^{(i)}={\lambda }_i{X}_{j_1\dots j_n}^{(i)}+t_i$ for all $j_k\in [d_k],k\in [n]$. Then for the game $\tilde{G}=(n,\tilde{X},S)$ with $\tilde{X}=({\tilde{X}}^{(1)},\dots ,{\tilde{X}}^{(n)})$ it holds that $P_G=P_{\tilde{G}}$.

Proof.

For each player $i\in [n]$ let $X^{(i)}$ be their payoff tensor, fix $t_i\in \mathbb{R},{\lambda }_i\in {\mathbb{R}}_{>0}$, and consider the affine transformation ${\tilde{X}}_{j_1\dots j_n}^{(i)}={\lambda }_i{X}_{j_1\dots j_n}^{(i)}+t_i$. Then $$\begin{array}{c}\sum _{j_1=1}^{d_1}\dots \widehat{\sum _{j_i=1}^{d_i}}\dots \sum _{j_n=1}^{d_n}\left({\tilde{X}}_{j_1\dots j_{i-1}k{j}_{i+1}\dots j_n}^{(i)}-{\tilde{X}}_{j_1\dots j_{i-1}l{j}_{i+1}\dots j_n}^{(i)}\right)p_{j_1\dots j_{i-1}k{j}_{i+1}\dots j_n}\\ =\sum _{j_1=1}^{d_1}\dots \widehat{\sum _{j_i=1}^{d_i}}\dots \sum _{j_n=1}^{d_n}\left({\lambda }_i{X}_{j_1\dots j_{i-1}k{j}_{i+1}\dots j_n}^{(i)}+t_i-{\lambda }_i{X}_{j_1\dots j_{i-1}l{j}_{i+1}\dots j_n}^{(i)}-t_i\right)p_{j_1\dots j_{i-1}k{j}_{i+1}\dots j_n}\\ ={\lambda }_i\sum _{j_1=1}^{d_1}\dots \widehat{\sum _{j_i=1}^{d_i}}\dots \sum _{j_n=1}^{d_n}\left(X_{j_1\dots j_{i-1}k{j}_{i+1}\dots j_n}^{(i)}-X_{j_1\dots j_{i-1}l{j}_{i+1}\dots j_n}^{(i)}\right)p_{j_1\dots j_{i-1}k{j}_{i+1}\dots j_n}\ge 0.\end{array}$$

Since ${\lambda }_i>0$, this is equivalent to (2.1) being nonnegative. □

Definition 2.5

(Nash Equilibrium). Let G be a game. A Nash equilibrium of G is a point $p\in P_G$ that is a tensor of rank one. More specifically, the set of Nash equilibria are those points in P_G that are also contained in the image of the product map $$\begin{array}{c}\phi :{\Delta }_{d_1-1}\times \cdots \times {\Delta }_{d_n-1}\to {\Delta }_{d_1\cdots d_n-1}\\ (p^{(1)},\dots ,p^{(n)})\mapsto p_{j_1}^{(1)}·\dots ·p_{j_n}^{(n)}\end{array}$$

The image of this map is the Segre variety inside ${\Delta }_{d_1\cdots d_n-1}$.

Figure 3 shows a 3-dimensional correlated equilibrium polytope of a $(2\times 2)$-game together with the Segre variety inside the simplex ${\Delta }_3$. We illustrate this in more detail in the following example.

Example 2.6

(Traffic Lights). We continue with the Traffic Lights example from Examples 2.1 and 2.3. The Nash equilibria of this game occur as vertices of the correlated equilibrium polytope P_G. More precisely, they occur as the images of the points $(p^{(1)},p^{(2)})\in {\Delta }_2\times {\Delta }_2$ with coordinates $((1,0),(0,1)),((0,1),(1,0))$ and $((\frac{1}{100},\frac{99}{100}),((\frac{1}{100},\frac{99}{100}))$ under the product map $\phi$ from Definition 2.5, which correspond to the three black vertices in Figure 2. With indexing $p=(p_{11},p_{12},p_{21},p_{22})$ the images of the first two points are $p=(0,1,0,0)$ and $(0,0,1,0)$. These are the probability distributions which correspond to the pure joint strategies in which one of the players drives, while the other one stops. The point $p=(\frac{1}{10000},\frac{99}{10000},\frac{99}{10000},\frac{9801}{10000})$ is a probability distribution in which it is most likely that both players stop.

By Definition 2.5, the set of Nash equilibria is a subset of the correlated equilibrium polytope. However, characterizing Nash equilibria is computationally difficult. Therefore, it is of interest to understand where the Nash equilibria lie relative to the correlated equilibrium polytope [13]. A game G is called non-trivial if $X_{j_1\dots j_{i-1}k{j}_{i+1},\dots j_n}^{(i)}\ne X_{j_1\dots j_{i-1}l{j}_{i+1},\dots j_n}^{(i)}$ for some player $i\in [n]$ and $k,l\in [d_i]$ with $k\ne l$. The next result states that if P_G is of maximal dimension, then any Nash equilibrium lies on a proper face of P_G.

Proposition 2.7.

[11, Proposition 1] Let G be a non-trivial game. Then the Nash equilibria lie on a face of the correlated equilibrium polytope P_G of dimension at most $d_1\cdots d_n-2$. In particular, if P_G has maximal dimension $d_1\cdots d_n-1$, then the Nash equilibria lie on the relative boundary of P_G.

In order to locate the possible positions of Nash equilibria, it is thus helpful to understand the conditions under which P_G is of maximal dimension. In Section 4 we study the region of full-dimensionality, which formalizes these conditions.

3 The correlated equilibrium cone

The combinatorics of the correlated equilibrium polytope is completely determined by the cone given by the inequality constraints (2.1), intersected with the nonnegative orthant. The correlated equilibrium cone $C_G\subseteq {\mathbb{R}}^{d_1\cdots d_n}$ is the polyhedral cone defined by inequalities $p_{j_1\dots j_n}\ge 0$ and (3.1) $$\sum _{j_1=1}^{d_1}\cdots \widehat{\sum _{j_i=1}^{d_i}}\cdots \sum _{j_n=1}^{d_n}\left(X_{j_1\cdots j_{i-1}k{j}_{i+1}\cdots j_n}^{(i)}-X_{j_1\cdots j_{i-1}l{j}_{i+1}\cdots j_n}^{(i)}\right)p_{j_1\cdots j_{i-1}k{j}_{i+1}\cdots j_n}\ge 0.$$(3.1) for all $k,l\in [d_i]$, and for all $i\in [n]$. For each player $i\in [n]$ this defines $d_i(d_i-1)$ nontrivial inequalities of type (3.1). The cone C_G is a convex pointed polyhedral cone. The correlated equilibrium polytope P_G is the intersection of the cone with the hyperplane where the sum of all coordinates equals 1. Therefore, a facet of P_G is in bijection with a facet of C_G, and a vertex of P_G is in bijection with an extremal ray of C_G.

We make a substitution of the coefficients in (3.1). For each $i\in [n],j_1\in [d_1],\dots ,j_{i-1}\in [d_{i-1}],k,l\in [d_i],j_{i+1}\in [d_{i+1}],\dots ,j_n\in [d_n]$ we define $$Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(k,l)=X_{j_1\cdots j_{i-1}k{j}_{i+1}\cdots j_n}^{(i)}-X_{j_1\cdots j_{i-1}l{j}_{i+1}\cdots j_n}^{(i)}.$$

Note that $Y_{j_1\dots \widehat{j_i}\dots j_n}^{(i)}(k,l)=-Y_{j_1\dots \widehat{j_i}\dots j_n}^{(i)}(l,k)$. Thus, for each player $i\in [n]$ this defines $(\begin{array}{c}{d}_i\\ 2\end{array})\prod _{\stackrel{k\in [n]}{k\ne i}}{d}_k$ distinct variables, so in total this defines $$M=\sum _{i=1}^n\left(\begin{array}{c}{d}_i\\ 2\end{array}\right)\prod _{\stackrel{k\in \left[n\right]}{k\ne i}}{d}_k$$many variables. Under this substitution, the above inequality becomes (3.2) $$\sum _{j_1=1}^{d_1}\cdots \widehat{\sum _{j_i=1}^{d_i}}\cdots \sum _{j_n=1}^{d_n}{Y}_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(k,l)p_{j_1\cdots j_{i-1}k{j}_{i+1}\cdots j_n}\ge 0.$$(3.2)

For fixed $i\in [n],k,l\in [d_i]$, let $U_{\mathit{\text{kl}}}^{(i)}\in {\mathbb{R}}^{d_1\cdots d_n}$ be the vector with entries $${(U_{\mathit{\text{kl}}}^{(i)})}_{j_1\dots j_i\dots j_n}=\{\begin{array}{cc}{Y}_{j_1\dots \widehat{j_i}\dots j_n}^{(i)}(k,l)\hfill & \text{if }{j}_i=k\text{ and }k<l\hfill \\ -Y_{j_1\dots \widehat{j_i}\dots j_n}^{(i)}(k,l)\hfill & \text{if }{j}_i=k\text{ and }k>l\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$for each coordinate indexed by $j_1\in [d_1],\dots ,j_i\in [d_i],\dots ,j_n\in [d_n]$. Using the same indexing of coordinates for $p\in {\mathbb{R}}^{d_1·\dots ·d_n}$, the inequalities (3.2) can be expressed as the inner product $〈U_{\mathit{\text{kl}}}^{(i)},p〉\ge 0$.

Example 3.1

($(2\times 2)$-games). Consider a 2-player game with $d_1=d_2=2$. We fix the indexing $p=(p_{11},p_{12},p_{21},p_{22})$. Recall that the inequalities are $$\begin{array}{c}(X_{11}^{(1)}-X_{21}^{(1)})p_{11}+(X_{12}^{(1)}-X_{22}^{(1)})p_{12}=Y_1^{(1)}(1,2)p_{11}+Y_2^{(1)}(1,2)p_{12}\ge 0\\ (X_{21}^{(1)}-X_{11}^{(1)})p_{21}+(X_{22}^{(1)}-X_{12}^{(1)})p_{22}=-Y_1^{(1)}(1,2)p_{21}-Y_2^{(1)}(1,2)p_{22}\ge 0\\ (X_{21}^{(2)}-X_{22}^{(2)})p_{21}+(X_{11}^{(2)}-X_{12}^{(2)})p_{11}=Y_2^{(2)}(1,2)p_{21}+Y_1^{(2)}(1,2)p_{11}\ge 0\\ (X_{22}^{(2)}-X_{21}^{(2)})p_{22}+(X_{12}^{(2)}-X_{11}^{(2)})p_{12}=-Y_2^{(2)}(1,2)p_{22}-Y_1^{(2)}(1,2)p_{12}\ge 0.\end{array}$$

The vectors $U_{\mathit{\text{kl}}}^{(i)}$ have entries in the 4 unknowns $Y_1^{(1)}(1,2),Y_2^{(1)}(1,2),Y_1^{(2)}(1,2),Y_2^{(2)}(1,2)$. More specifically, $$\begin{array}{c}{U}_{12}^{(1)}=(Y_1^{(1)}(1,2),Y_2^{(1)}(1,2),0,0)\\ U_{21}^{(1)}=-(0,0,Y_1^{(1)}(1,2),Y_2^{(1)}(1,2))\\ U_{12}^{(2)}=(Y_1^{(2)}(1,2),0,Y_2^{(2)}(1,2),0)\\ U_{21}^{(2)}=-(0,Y_1^{(2)}(1,2),0,Y_2^{(2)}(1,2)).\end{array}$$

The cone C_G is defined by the inequalities $〈U_{\mathit{\text{kl}}}^{(i)},p〉\ge 0$ for $i\in [2]$, and $k,l\in [2],k\ne l$, and the inequalities $〈e_i,p〉\ge 0$, where e_i denote the standard basis vectors of ${\mathbb{R}}^4$.

Recall that the number of variables defined above is $M={\sum }_{i=1}^n(\begin{array}{c}{d}_i\\ 2\end{array})\prod _{\stackrel{k\in [n]}{k\ne i}}{d}_k$. The ambient dimension of the correlated equilibrium polytope and cone is $D={\prod }_{i=1}^n{d}_i$, and the number of linear inequalities of the form (3.2) is $N={\sum }_{i=1}^n{d}_i(d_i-1)$. Let $U=U(Y)\in {\mathbb{R}}^{N\times D}$ be the matrix with rows $U_{\mathit{\text{kl}}}^{(i)}$ for $i\in [n],k,l\in [d_i],k\ne l$, and let $A(Y)\in {\mathbb{R}}^{(D+N)\times D}$ be the block matrix $$A(Y)=\left(\begin{array}{c}U\\ I{d}_D\end{array}\right).$$

By (3.2), the cone $C_G=C(Y)$ is given by $$C(Y)=\{p\in {\mathbb{R}}^D|A(Y)p\ge 0\}.$$

The matrix A(Y) has full rank D, and so C(Y) is a pointed cone.

For $(d_1\times \cdots \times d_n)$-games, where $d_i\ge 3$ for some $i\in [n]$, we have additional relations (3.3) $$Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(k,l)+Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(l,t)=Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(k,t)$$(3.3) for $j_1\in [d_1],\dots ,j_{i-1}\in [d_{i-1}],k,l,t\in [d_i],j_{i+1}\in [d_{i+1}],\dots ,j_n\in [d_n]$. A vector $Y\in {\mathbb{R}}^M$ corresponds to a certain game G if and only if these relations hold. Geometrically, these relations define a linear space inside ${\mathbb{R}}^M$. We thus make the following definition.

Definition 3.2.

The correlated equilibrium space $\mathcal{S}\subseteq {\mathbb{R}}^M$ of $(d_1\times \cdots \times d_n)$-games is the linear space defined by the equations (3.3)(3.3) $$Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(k,l)+Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(l,t)=Y_{j_1\cdots \widehat{j_i}\cdots j_n}^{(i)}(k,t)$$(3.3) , where $i\in [n]$ ranges over all players with at least 3 strategies $d_i\ge 3$. If all players have at most 2 strategies, then no such relation among the variables holds, and the correlated equilibrium space is the entire ambient space $\mathcal{S}={\mathbb{R}}^M$.

Example 3.3

($\mathcal{S}$ for $(2\times 3)$-games). In a $(2\times 3)$-game, there are nine variables $$\begin{array}{c}{Y}_1^{(1)}(1,2)=X_{11}^{(1)}-X_{21}^{(1)},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_2^{(1)}(1,2)=X_{12}^{(1)}-X_{22}^{(1)},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_3^{(1)}(1,2)=X_{13}^{(1)}-X_{23}^{(1)},\\ Y_1^{(2)}(1,2)=X_{11}^{(2)}-X_{12}^{(2)},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_1^{(2)}(1,3)=X_{11}^{(2)}-X_{13}^{(2)},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_1^{(2)}(2,3)=X_{12}^{(2)}-X_{13}^{(2)},\\ Y_2^{(2)}(1,2)=X_{21}^{(2)}-X_{22}^{(2)},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_2^{(2)}(1,3)=X_{21}^{(2)}-X_{23}^{(2)},\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_2^{(2)}(2,3)=X_{22}^{(2)}-X_{23}^{(2)}.\end{array}$$

The relations among these variables are $$Y_1^{(2)}(1,2)+Y_1^{(2)}(2,3)=Y_1^{(2)}(1,3),\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{Y}_2^{(2)}(1,2)+Y_2^{(2)}(2,3)=Y_2^{(2)}(1,3).$$

These relations cut out the correlated equilibrium space $\mathcal{S}$ for $(2\times 3)$-games. For any game $(2\times 3)$-games G the correlated equilibrium polytope is nonempty, a point $Y\in {\mathbb{R}}^9$ defines a correlated equilibrium cone if and only if it satisfies the above relations.

Remark 3.4.

In the following sections, we will classify correlated equilibrium polytopes and cones with respect to the variables Y instead of the payoff tensors X. We note that this is not a significant restriction, as this is a linear change of coordinates and thus does not change the geometry of the objects described in what follows, provided one restricts to the correlated equilibrium space $\mathcal{S}$.

4 The region of full-dimensionality

In this section, we introduce the region of full-dimensionality for a type of game. For fixed $d_i\in \mathbb{N},i\in [n]$, this region classifies for which $(d_1\times \cdots \times d_n)$-games the polytope P_G is of maximal dimension $D-1=d_1\cdots d_n-1$. The connections between full-dimensionality and elementary games are discussed in [21, Section 3]. The game is elementary if and only if none of the incentive constraints is vacuous and P_G has full dimension. In general, it is not understood under which conditions P_G has maximal dimension (i.e. G is a full game), though there are some partial results on forbidden dimensions [22, Proposition 7]. Exploring full-dimensional correlated equilibrium polytopes provides valuable insights from a game theoretical perspective as in this case, Nash equilibria lie on the relative boundary of P_G (Proposition 2.7). Since computing Nash equilibria is PPAD-complete [6] and correlated equilibria are computationally less expensive, it is a meaningful pursuit to study the combinatorial properties of full-dimensional P_G.

Let $Y\in \mathcal{S}\subseteq {\mathbb{R}}^M$ be a vector of indeterminates, as described in Section 3. We consider $A=A(Y)$ as a matrix with indeterminates, where each choice of $Y\in {\mathbb{R}}^M$ uniquely defines a correlated equilibrium cone $$C(Y)=\{p\in {\mathbb{R}}^N|A(Y)p\ge 0\}.$$

Recall that the correlated equilibrium polytope $P_G(Y)$ is of maximal dimension if and only if C(Y) is full-dimensional. Thus, we are interested in the region of full-dimensionality $$\mathcal{D}=\{Y\in \mathcal{S}\subseteq {\mathbb{R}}^M|\mathrm{\text{dim}}(C(Y))=D\}.$$

Definition 4.1.

A semialgebraic set is a subset of ${\mathbb{R}}^M$ defined by a boolean combination of finitely many polynomial inequalities.

Theorem 4.2.

The region $\mathcal{D}$ of full-dimensionality is the semialgebraic set $${\pi }_Y(\{(x,Y)\in {\mathbb{R}}^{D+M}|A(Y)x>0\})\cap \mathcal{S}$$where π_Y is the coordinate projection onto the last M coordinates.

Proof.

The cone C(Y) is full-dimensional if and only if it has nonempty interior, i.e. if there exists some $p\in {\mathbb{R}}^D$ such that $A(Y)p>0$. Let $x=(x_{j_1\cdots j_n}|i\in [n],j_i\in [d_i])$ be a vector of D indeterminates. Consider the set $$\{(x,Y)\in {\mathbb{R}}^{D+M}|A(Y)x>0\}.$$

The expression $A(Y)x$ defines a $(D+N)$-dimensional vector, where each coordinate is a polynomial in variables x and Y. Hence, the set $\{(x,Y)\in {\mathbb{R}}^{D+M}|A(Y)x>0\}$ is defined by D + N polynomial inequalities, and is thus a (basic) semialgebraic set. The region $\mathcal{D}$ of full-dimensionality is the intersection of the correlated equilibrium space $\mathcal{S}$ with a coordinate projection of this set, which can be obtained by projecting away the x-coordinates. The Tarski-Seidenberg theorem implies that the coordinate projection is semialgebraic, and hence $\mathcal{D}$ is a semialgebraic set. □

Example 4.3

($\mathcal{D}$ for $(2\times 2)$-games). Consider a $(2\times 2)$-game. In this case, the ambient dimension of the correlated equilibrium polytope is D = 4, the number of incentive constraints is N = 4 (so the number of inequalities that define the polytope is $D+N=8$) and the ambient dimension of $\mathcal{D}\subseteq \mathcal{S}={\mathbb{R}}^M$ is M = 4. The different combinatorial types, in this case, have been fully classified in [5]. Here, $\mathcal{D}\subseteq {\mathbb{R}}^4$ is the union of two open orthants: $$\begin{array}{c}a)Y_1^{(1)}(1,2)>0,Y_2^{(1)}(1,2)<0,Y_1^{(2)}(1,2)>0,Y_2^{(2)}(1,2)<0\\ b)Y_1^{(1)}(1,2)<0,Y_2^{(1)}(1,2)>0,Y_1^{(2)}(1,2)<0,Y_2^{(2)}(1,2)>0\end{array}$$

The file dimensions2x2.nb in [9] contains Mathematica code [23] which also computes these inequalities.

Example 4.4

($\mathcal{D}$ for $(2\times 3)$-games). The coordinate projection of the set $\{(x,Y)\in {\mathbb{R}}^{D+M}|A(Y)x>0\}$ onto ${\mathbb{R}}^M$ is the union of basic semialgebraic sets, where each piece is the intersection of an orthant with a binomial inequality. One of the pieces is $$\begin{array}{c}{Y}_1^{(1)}(1,2)>0,Y_2^{(1)}(1,2)>0,Y_3^{(1)}(1,2)<0,\\ Y_1^{(2)}(1,2)<0,Y_1^{(2)}(1,3)<0,Y_1^{(2)}(2,3)>0,Y_2^{(2)}(1,2)>0,Y_2^{(2)}(1,3)>0,Y_2^{(2)}(2,3)<0,\\ Y_2^{(2)}(1,3)Y_1^{(2)}(2,3)<Y_1^{(2)}(1,3)Y_2^{(2)}(2,3).\end{array}$$

The region $\mathcal{D}$ of full-dimensionality for $(2\times 3)$-games consists of the intersection of the above mentioned pieces with the correlated equilibrium space $\mathcal{S}$. The Mathematica file dimensions2x3.nb in [9] contains our code for computing all of the components of this semialgebraic set. We note that the orthants appearing in $\mathcal{D}$ seem highly structured.

Remark 4.5.

The structured behavior of the regions of full-dimensionality that we see in $(2\times 3)$-games arises more generally for arbitrary $(2\times n)$-games. Exploiting the structure of the matrix A(Y), the region $\mathcal{D}$ of full-dimensionality for $(2\times n)$-games cannot satisfy any of the following conditions:

• $Y_k^{(1)}(1,2)>0$, for all $k\in [n]$.

• $Y_k^{(1)}(1,2)<0$, for all $k\in [n]$.

• $Y_1^{(2)}(k,n)>0$ and $Y_2^{(2)}(k,n)>0$, for all $k\in [n]$

• $Y_1^{(2)}(k,n)<0$ and $Y_2^{(2)}(k,n)<0$, for all $k\in [n]$.

While this approach could theoretically be used to obtain inequalities for larger games, this is extremely difficult in practice since the required algebraic methods do not scale well as the number of variables involved increases. For example, we were unable to carry out this computation for $(2\times 2\times 2)$-games since we must compute the coordinate projection of a semialgebraic set that lives in $D+M=20$-dimensional space.

5 Combinatorial types of correlated equilibrium polytopes

In this section, we consider how to systematically classify combinatorial types of polytopes arising as a correlated equilibrium polytope. The face lattice of a polytope P is the poset of all the faces of P, partially ordered by inclusion. Two polytopes have the same combinatorial type if there exists an isomorphism between their face lattices.

First, we present a systematic approach for classifying the possible combinatorial types for arbitrary games by describing the stratification by oriented matroids. Even for small examples, the explicit computation of the oriented matroid strata is beyond the current scope, but we introduce algebraic methods for understanding the oriented matroid strata via their algebraic boundaries. We use this technique to completely classify the combinatorial types of P_G for $(2\times 3)$-games (Theorem 5.9). We then show that for all $(2\times n)$-games the irreducible components of the algebraic boundary of the oriented matroid stratification are coordinate hyperplanes, $(2\times 2)$-minors and $(4\times 4)$-minors of the matrix A(Y) (Theorem 5.8).

Example 5.1

(Hawk-Dove game). This game models a scenario of a competition for a shared resource. Both players can choose between conflict (hawk) or conciliation (dove). This game is a generalization of the Traffic Lights example (Examples 2.1, 2.3, and 2.6). The inequalities for general $(2\times 2)$-games are given in Example 3.1. In the Hawk-Dove game, each of the two players has two strategies $s_1^{(i)}$=“hawk” or $s_2^{(i)}$=“dove”.

Table

		Player 2
		Hawk	Dove
Player 1	Hawk	$\left(\frac{V-C}{2},\frac{V-C}{2}\right)$	$(V,0)$
	Dove	$(0,V)$	$\left(\frac{V}{2},\frac{V}{2}\right)$

In this bimatrix game, V represents the value of the resource and C represents the cost of the escalated fight. It is mostly assumed that $C>V>0$. The correlated equilibria polytope P_G is full-dimensional with 5 vertices and 6 facets. In the case $V\ge C>0$, the game becomes an example for Prisoner’s Dilemma, in which case P_G is a single point.

As seen in the previous example, for fixed $d_1,\dots ,d_n\in \mathbb{N}$, different choices of the payoffs for the players in a $(d_1\times \cdots \times d_n)$-game can result in different combinatorial types of correlated equilibria. We would thus like to classify the regions of the correlated equilibrium space $\mathcal{S}\subseteq {\mathbb{R}}^M$ such that $$\{Y\in \mathcal{S}|C(Y)\text{ has a fixed combinatorial type}\}.$$

We now explain how the combinatorial type of C(Y) is completely determined by the underlying oriented matroid defined by the matrix A(Y). The combinatorial type of C(Y) is the incidence structure of rays and facets of C(Y). Equivalently, we can classify the incidence structure of facets and rays of the dual cone $C{(Y)}^{\ast }$. The dual of the cone C(Y) is defined as $$C{(Y)}^{*}=\{q\in {\mathbb{R}}^{d_1\cdots d_n}|〈p,q〉\ge 0,\forall p\in C(Y)\}.$$

By definition, the (inner) facet normals of C(Y) are generators of extremal rays of $C{(Y)}^{*}$ and vice versa. Let $h\in [D+N]$ and $A_h(Y)$ be a row of A(Y). Seen as a linear functional, this row uniquely selects a face $$F_h=\{p\in C(Y)|〈A_h(Y),p〉=0\}.$$

Note that this is not necessarily a facet of C(Y), but all facets of C(Y) arise in this way. For the dual cone $C{(Y)}^{\ast }$ this implies that $r_h=A_h(Y){\mathbb{R}}_{\ge 0}$ is an extremal ray of $C{(Y)}^{*}$ if and only if F_h is a facet of C. If C(Y) is not full-dimensional, then there is some $h\in [D+N]$ such that $F_h=C(Y)$. The set of all such vectors span the lineality space $$\mathcal{L}=C{(Y)}^{*}\cap (-C{(Y)}^{*})=\text{span}(\{A_h|F_h=C(Y)\})$$of $C{(Y)}^{*}$. In this case, extremal rays of $C{(Y)}^{*}$ are to be considered in $C{(Y)}^{*}/\mathcal{L}$.

We want to understand the incidence structure of extremal rays and facets of C(Y). Each such ray of C(Y) is contained in at least D – 1 facets. Thus, we seek to understand which subsets of D – 1 faces F_h of C(Y) intersect in a single point. Equivalently, we want to understand which subsets of D – 1 rays r_h of $C{(Y)}^{*}$ are contained in a common face. Let $H\subseteq [D+N]$ such that $\left|H\right|=D-1$, and denote by $A_H(Y)$ the submatrix of A(Y) with rows indexed by H. If $\left\{r_h\right|h\in H\}$ lie on a common face, then these rays all lie on the hyperplane given by the rowspan of $A_H(Y)$. Additionally, let $h\prime \in [D+N]\setminus H$. Then all $r_{h\prime }$ lie on the same side of the hyperplane. This implies that the sign of $\mathrm{\text{det}}(A_{H\cup h\prime })$ is uniquely determined for all $h\prime \in [D+N]\setminus H$. The collection $\mathcal{R}$ of all regions in which the maximal minors of A(Y) satisfy a certain sign pattern is known as the oriented matroid stratification of ${\mathbb{R}}^M$. Each cell gives rise to a fixed sign pattern of A(Y), i.e. the underlying oriented matroid. Restricting the oriented matroid strata to the correlated equilibrium space $\mathcal{S}$ yields a subdivision of $\mathcal{S}$ in which distinct combinatorial types lie in distinct regions.

Definition 5.2.

Let $S\subseteq {\mathbb{R}}^M$ be a semialgebraic set. The algebraic boundary ${\partial }_{a}S$ is the Zariski closure of the topological (euclidean) boundary $\partial S$, i.e. the smallest algebraic variety containing $\partial S$ (over $\mathbb{C}$).

Construction 5.3 (Algebraic Boundary). For every $H\subseteq [D+N],\left|H\right|=D$ the minor $\mathrm{\text{det}}(A_H)$ is a polynomial in variables Y of degree at most D, and $\text{sgn}(\mathrm{\text{det}}(A_H))\in \{-1,0,1\}$ is a polynomial inequality. Let $s=(s_H|H\subseteq (\begin{array}{c}[D+N]\\ D\end{array})),s_H\in \{1,-1\}$ be a sign vector. Each maximal open region in the oriented matroid stratification is of the form $${\mathcal{R}}_s^{°}=\left\{Y\in {\mathbb{R}}^M|\text{sgn}(\mathrm{\text{det}}(A_H(Y)))=s_H\text{ for all }H\in \left(\begin{array}{c}[D+N]\\ D\end{array}\right)\right\}.$$

Let ${\mathcal{R}}_s$ denote the Euclidean closure of such an open maximal region, which is a closed basic semialgebraic set. We define the algebraic boundary of the oriented matroid stratification ${\partial }_a\mathcal{R}$ as the union of the algebraic boundaries of all such closed regions, i.e. $${\partial }_a\mathcal{R}=\underset{s}{\cup }{\partial }_a{\mathcal{R}}_s=\underset{H\in \left(\begin{array}{c}[D+N]\\ D\end{array}\right)}{\cup }\mathcal{V}(\mathrm{\text{det}}(A_H(Y))),$$

where the first union ranges over all sign vectors s such that ${\mathcal{R}}_s^{°}$ is maximal, and $$\mathcal{V}(\mathrm{\text{det}}(A_H(Y)))=\{Y\in R^M|\mathrm{\text{det}}(A_H(Y))=0\}.$$

In the second union we only consider $H\in (\begin{array}{c}[D+N]\\ D\end{array})$ such that $A_H(Y)$ contains at least one variable. Recall that $A(Y)=(\begin{array}{c}U\\ I{d}_N\end{array})$ where the matrix U has no zero rows and all nonzero entries are variables. Thus, the only minor of A(Y) that does not contain a variable is the determinant of Id_N, so the number of such minors is $(\begin{array}{c}D+N\\ D\end{array})-1$. We note that the minors may not be irreducible polynomials, so they do not necessarily define the irreducible components of the variety ${\partial }_a\mathcal{R}$. In total, this defines $(\begin{array}{c}D+N\\ D\end{array})-1$ hypersurfaces, whose defining polynomials are of degree at most D.

Applying [4] and [3, Theorem 4] to this setup yields a general bound on the number of strata on the oriented matroid stratification.

Proposition 5.4.

Let δ be the maximum degree of all $\beta \le (\begin{array}{c}D+N\\ D\end{array})-1$ defining polynomials. Then $\delta \le D$ and the number of strata in the oriented matroid stratification is at most $$\delta {(2\delta -1)}^{M-1}(1+3\beta ).$$

The following three examples illustrate this construction for small games.

Example 5.5

(${\partial }_a\mathcal{R}$ for $(2\times 2)$-games). In a $(2\times 2)$-game we have D = 4, N = 4 and M = 4. The number of irreducible components of ${\partial }_a\mathcal{R}$ is β = 4, and these are the 4 coordinate hyperplanes. Indeed, the classification in [5] shows that in each open orthant, the combinatorial type is fixed, and in the two orthants described in Example 4.3 there is a unique combinatorial type of maximal dimension. The file orientedMatroidStrata2x2.m2 in [9] contains Macaulay2 code [7] which explicitly computes these irreducible components.

Example 5.6

(${\partial }_a\mathcal{R}$ for $(2\times 3)$-games). In a $(2\times 3)$-game, we have $D=6,N=8$, and M = 9. The number of minors of $A_H(Y)$ that contain at least one variable is $(\begin{array}{c}12\\ 6\end{array})-1=934$, but the number of irreducible components is only β = 12. All of these polynomials are homogeneous, and the maximum degree is δ = 2. In fact, the irreducible components are the 9 coordinate hyperplanes, together with the 3 binomials $$\begin{array}{c}{Y}_2^{(2)}(1,2)Y_1^{(2)}(1,3)-Y_1^{(2)}(1,2)Y_2^{(2)}(1,3)\\ Y_2^{(2)}(1,2)Y_1^{(2)}(2,3)-Y_1^{(2)}(1,2)Y_2^{(2)}(2,3)\\ Y_2^{(2)}(1,3)Y_1^{(2)}(2,3)-Y_1^{(2)}(1,3)Y_2^{(2)}(2,3).\end{array}$$

Thus, Proposition 5.4 implies that the number of strata in the oriented matroid stratification is at most $2·3^8(1+3·12)=485514.$ However, as we will show in Theorem 5.9, it turns out that there are precisely 3 distinct combinatorial types. Note that the three binomials above are precisely the binomials intersecting the orthants in Example 4.4. The file orientedMatroidStrata2x3.m2 in [9] contains Macaulay2 code which explicitly computes these polynomials.

Example 5.7

(${\partial }_a\mathcal{R}$ for $(2\times 2\times 2)$-games). In a $(2\times 2\times 2)$-game, we have $D=8,N=6$ and M = 12. The number of minors of $A_H(Y)$ that contain at least one variable is $(\begin{array}{c}14\\ 8\end{array})-1=3003$, but the number of irreducible components is only 194. All of these polynomials are homogeneous, and the maximum degree is 6. The file orientedMatroidStrata2x2x2.m2 in [9] contains Macaulay2 code which explicitly computes these polynomials. Proposition 5.4 implies that the number of strata of the oriented matroid stratification is at most $$6·{11}^{11}(1+3·194)=998020223797278>{10}^{14}.$$

The previous examples illustrate that the algebraic boundary of the oriented matroid stratification is quite nice for $(2\times n)$-games but becomes significantly more complicated even for $(2\times 2\times 2)$-games. The following theorem shows that the nice structure we see for $(2\times 3)$-games holds for all $(2\times n)$-games.

Theorem 5.8.

Consider a $(2\times n)$-game, i.e. a 2-player game with $d_1=2,d_2=n\in \mathbb{N}$. Then the irreducible components of ${\partial }_a\mathcal{R}$ are given by

• the coordinate hyperplanes,

• hypersurfaces defined by quadratic binomials that are given by certain $(2\times 2)$-minors and $(4\times 4)$-minors of the matrix A(Y).

Proof.

We prove by induction on n. For n = 2 after reordering the rows and columns, the matrix $A(Y)=A^2(Y)$ has the following representation: $$\left(\begin{array}{cccc}{Y}_1^{(1)}(1,2)& & Y_2^{(1)}(1,2)& \\ & -Y_1^{(1)}(1,2)& & -Y_2^{(1)}(1,2)\\ Y_1^{(2)}(1,2)& Y_2^{(2)}(1,2)& & \\ & & Y_1^{(2)}(2,1)& Y_1^{(2)}(2,1)\\ & I{d}_4& & \end{array}\right)$$

For n = 3 the columns and rows can be arranged to $A(Y)=A^3(Y)$: $$\left(\begin{array}{cccccc}{Y}_1^{(1)}(1,2)& & Y_2^{(1)}(1,2)& & Y_3^{(1)}(1,2)& \\ & -Y_1^{(1)}(1,2)& & -Y_2^{(1)}(1,2)& & -Y_3^{(1)}(1,2)\\ Y_1^{(2)}(1,2)& Y_2^{(2)}(1,2)& & & & \\ Y_1^{(2)}(1,3)& Y_2^{(2)}(1,3)& & & & \\ & & Y_1^{(2)}(2,1)& Y_2^{(2)}(2,1)& & \\ & & Y_1^{(2)}(2,3)& Y_2^{(2)}(2,3)& & \\ & & & & Y_1^{(2)}(3,1)& Y_2^{(2)}(3,1)\\ & & & & Y_1^{(2)}(3,2)& Y_2^{(2)}(3,2)\\ & & I{d}_6& & & \end{array}.\right)$$

In both cases, the statement holds by Examples 5.5 and 5.6. First, we describe the general block matrix structure of $A(Y)=A^n(Y)$ for fixed $n\in \mathbb{N}$. Recall that $A^n(Y)$ is a $((D+N)\times D)$-matrix, where $D=2n$ and $N=2+n(n-1)$. As in the case n = 2, 3, we can arrange the rows and columns of $A^n(Y)$ such that the first two rows consist of n blocks of size $(2\times 2)$, which are of the form $\left[\begin{array}{cc}{Y}_k^{(1)}(1,2)& \\ & -Y_k^{(1)}(1,2)\end{array}\right]$ for $k\in [n]$. The following $n(n-1)$ rows form a block diagonal matrix, with n blocks of size $((n-1)\times 2)$ of the form $$b_k=\left[\begin{array}{cc}{Y}_1^{(2)}(k,1)& Y_2^{(2)}(k,1)\\ ⋮& ⋮\\ Y_1^{(2)}(k,n)& Y_2^{(2)}(k,n)\end{array}\right]$$for each $k\in [n]$, where the row $[Y_1^{(2)}(k,k)Y_1^{(2)}(k,k)]$ is omitted. Finally, the last 2n rows consist of the identity matrix $I{d}_{2n}$.

We want to show that the maximal minors of the matrix $A^n(Y)$ are either monomials, binomials, or zero. Note that every maximal minor of $A^n(Y)$ that involves a row from the identity matrix corresponds to a smaller minor of the remaining matrix. We thus consider all $(m\times m)$-minors of the submatrix of $A^n(Y)$ that consists of the first $2+(n-1)n$ rows, for $m\le 2n$. Let M be such a $(m\times m)$-submatrix.

If M contains a row or column which has at most one entry, then computing $\mathrm{\text{det}}(M)$ by expanding this row or column implies the statement by induction on m. Thus, suppose that M has at least 2 nonzero entries in each row and column. If M contains at least 3 rows from one block of the block diagonal matrix, then these 3 rows are linearly dependent (since each block only consists of 2 columns), in which case $\mathrm{\text{det}}(M)=0$. On the other hand, if M contains at most 2 rows from each block, and neither the first nor the second row, then M either contains a zero row, a zero column, or is a block-diagonal matrix with blocks of sizes $(2\times 2)$ and $(1\times 1)$, so $\mathrm{\text{det}}(M)$ is a product of binomials and monomials.

We are left with the case in which each row and column contains at least 2 non-zero entries, and M contains the first or second row. We first argue that M must contain both the first and second rows to meet these requirements. Let $M_{*j}$ be a column of M. Since $M_{*j}$ contains at least two nonzero entries, at least one entry M_ij is neither in the first nor second row of $A^n(Y)$. Thus, there exists a block $b_k,k\in [n]$ containing M_ij. Recall that the columns of $A^n(Y)$ containing the block b_k are the columns with index $2k-1$ and 2k. Since each row of M contains at least two nonzero entries, M must contain both of these columns. Following this argument for all columns of M implies that m is even.

If only one of the first two rows is contained in M, then by the Pigeonhole principle there is at least one block such that M has an odd number of rows from this block. As we have already covered the case in which M has at least three rows from one block, we can assume there is a block b_k of which M contains precisely one row $M_{i*}$ with precisely two nonzero entries M_ij and $M_{i,j+1}$. However, then either the column $M_{*j}$ or $M_{*j+1}$ contain only a single nonzero entry, so M does not meet our assumptions. Thus, we can assume that M contains both the first and second row of $A^n(Y)$, and m – 2 rows from blocks of the block diagonal.

We have seen that the assumption of having at least 2 nonzero entries in each row implies that M contains either 0 or 2 columns from each block b_k. The matrix M thus contains m – 2 rows from $\frac{m}{2}$ blocks in total, with at least 1 and at most 2 rows per block. This implies that there are precisely 2 blocks which contribute a single row, while M contains 2 rows of the remaining $\frac{m}{2}-2$ blocks.

To summarize, the matrix M is of the shape $$\left(\begin{array}{ccccccccc}\ast \hfill & \hfill & \ast \hfill & \hfill & \ast \hfill & \hfill & \dots \hfill & \ast \hfill & \hfill \\ \hfill & \ast \hfill & \hfill & \ast \hfill & \hfill & \ast \hfill & \hfill & \hfill & \ast \hfill \\ \ast \hfill & \ast \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill \\ \hfill & \hfill & \ast \hfill & \ast \hfill & \hfill & \hfill & \hfill & \hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & \ast \hfill & \ast \hfill & \hfill & \hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & \ast \hfill & \ast \hfill & \hfill & \hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \ddots \hfill & \hfill & \hfill \\ \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \ast \hfill & \ast \hfill \\ \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \ast \hfill & \ast \hfill \end{array}\right),$$where * denotes a non-zero entry, i.e. below the first two rows M is a block matrix with 2 blocks of size $(1\times 2)$ and $\frac{m}{2}-2$ blocks of size $(2\times 2)$. We now proceed by induction on the (even) size m of the matrix M. If m = 4 then M does not contain any $(2\times 2)$-block and it can be computed that $\mathrm{\text{det}}(M)$ is the difference of two monomials of degree 3. For general even m, note that we can consider M as a block matrix of the form $M=(\begin{array}{cc}B& C\\ 0& D\end{array})$, where B is a matrix of size $(m-2)\times (m-2)$ and D a $(2\times 2)$-block. Recall that for such upper triangular block matrices holds $\mathrm{\text{det}}(M)=\mathrm{\text{det}}(B)\mathrm{\text{det}}(D)$. By induction, $\mathrm{\text{det}}(B)$ is a product of monomials and binomials, and $\mathrm{\text{det}}(D)$ is a binomial since D is a $(2\times 2)$-block. Throughout the above arguments, the binomials in the product always arose as determinants of $(2\times 2)$-submatrices of a block or from $(4\times 4)$-submatrices involving two columns of even index, two columns of odd index, the first two rows and two rows from distinct blocks. Finally, the statement follows. □

We now show how the oriented matroid stratification of $(2\times 3)$-games can be used to completely determine the possible combinatorial types of the polytope for payoffs Y which are generic with respect to the algebraic boundary described in Theorem 5.8. In other words, none of the polynomials described in Theorem 5.8 vanish on Y.

Theorem 5.9.

Let G be a $(2\times 3)$-game with generic payoffs $Y\in \mathcal{S}\subseteq {\mathbb{R}}^9$ and let $P_G=P(Y)$ be its associated correlated equilibrium polytope. Then one of the following holds

• P_G is a point,

• P_G is of maximal dimensional and of a unique combinatorial type,

• There exists a $(2\times 2)$-game $G\prime$ such that $P_{G\prime }$ is full-dimensional and combinatorially equivalent to P_G.

Proof.

First recall that the combinatorial type is fully determined by the sign patterns of the maximal minors of A(Y), i.e. the oriented matroid of A(Y). For $(2\times 3)$-games the matrix A(Y) has 1206 nonzero maximal minors for generic Y, since 1797 of the $(\begin{array}{c}14\\ 6\end{array})=3003$ maximal minors are identically zero. The signs of these 1206 maximal minors are completely determined by the signs of the irreducible components of $\mathrm{\text{det}}(A{(Y)}_B)$ for each $B\in (\begin{array}{c}[14]\\ 6\end{array})$. As in Theorem 5.8 and Example 5.6, there are 12 such irreducible components $f_1,\dots ,f_{12}$, which are given by the 9 coordinate hyperplanes and the 3 binomials listed in the example. This means that once we fix a sign pattern $s\in {\{1,-1\}}^{12}$ of the f_i the signs of all maximal minors of A(Y) are uniquely determined. Thus, to compute all possible combinatorial types, we compute the combinatorial type of the polytope once for each possible sign pattern s of the $f_i(Y)$.

We do this computationally, using the software Mathematica 13.0 and SageMath 9.6 [18, 23]. We first use Mathematica to find a payoff $Y\in \mathcal{S}$ such that $s_i{f}_i(Y)>0$ for all $i=1,\dots ,12$. We then compute the corresponding combinatorial type of the polytope in SageMath. These computations can be found in the files $\mathtt{\text{combinatorialTypes}}\mathtt{2x3}.\mathtt{\text{nb}}$ and $\mathtt{\text{combinatorialTypes}}\mathtt{2x3}.\mathtt{\text{ipynb}}$ on MathRepo [9], respectively.

As a result, we obtain 3 different possible combinatorial types, which are a single point, the unique combinatorial type of full-dimensions of $(2\times 2)$-games (a bipyramid over a triangle), and a new unique full-dimensional combinatorial type. This polytope has f-vector $(1,11,32,40,25,8,1)$, and the graph of this 5-dimensional polytope is depicted in Figure 4. A full description of this polytope can be found in $\mathtt{\text{combinatorialTypes}}\mathtt{2x3}.\mathtt{\text{ipynb}}$ on our MathRepo page [9]. □

Fig. 4 The graph of the combinatorially unique 5-dimensional polytope that arises as the correlated equilibrium polytope of a $(2\times 3)$-game, as described in Theorem 5.9.

Example 5.10

(Combinatorial types of $(2\times 3)$-games). By Theorem 5.9, for generic $(2\times 3)$-games there is a unique combinatorial type of full-dimension. This is a 5-dimensional polytope with f-vector $(1,11,32,40,25,8,1)$ and its graph is depicted in Figure 4.

Theorem 5.8 shows, that in $(2\times 3)$-games all correlated equilibrium polytopes that are not of maximal dimension appear as the maximal polytope of a smaller game. This gives rise to the following conjecture.

Conjecture 5.1. Let G be a $(2\times n)$-game with generic payoff matrices and let P_G be its correlated equilibrium polytope. If P_G is not of maximal dimension, then there exists a $(2\times k)$-game $G\prime$ where k < n such that $P_{G\prime }$ has maximal dimension and P_G and $P_{G\prime }$ are combinatorially equivalent.

A relevant study to this conjecture is the dual reduction process of finite games. An iterative dual reduction reduces a finite game G to a lower-dimensional elementary game $G\prime$, for which $P_{G\prime }$ is full-dimensional, by deleting certain pure strategies or merging several pure strategies into a single one. Any correlated equilibrium of the reduced game $G\prime$ is a correlated equilibrium of the original game G, however, the opposite is not always true [10, Section 5]. Conjecture 5.1 is supported by our computations thus far. To test this conjecture, we sampled $100,000$ random payoff matrices X for $(2\times n)$-games for n = 4, 5. The results are summarized in Table 1, which shows the number of unique combinatorial types of a given dimension that we found for each $(2\times n)$-game. In all of our computations, Conjecture 5.1 holds. The supporting code can be found on [9].

Table 1 The number of unique combinatorial types of P_G of each dimension for a $(2\times n)$-game in a random sampling of size $100000$.

Unique combinatorial types by dimension
Dimension	0	3	5	7	9
$(2\times 2)$	1	1	0	0	0
$(2\times 3)$	1	1	1	0	0
$(2\times 4)$	1	1	1	3	0
$(2\times 5)$	1	1	1	3	4

In contrast to the $(2\times n)$-case, $(2\times 2\times 2)$-games exhibit a much wider variety of distinct combinatorial types. In a sample of $100,000$ random payoff matrices for $(2\times 2\times 2)$-games, we found 14,949 distinct combinatorial types which are of maximal dimension. Amongst these 7-dimensional polytopes, the number of vertices can range from 8 to 119, the number of facets from 8 to 14, and the number of total faces from 256 to 2338. Examples of f-vectors achieving these bounds are $$\begin{array}{c}{f}_{P_{G_1}}=(1,8,28,56,70,56,28,8,1)\\ f_{P_{G_2}}=(1,119,458,728,616,302,87,14,1),\\ f_{P_{G_3}}=(1,119,460,733,620,303,87,14,1).\end{array}$$

Acknowledgments

The authors would like to thank Rainer Sinn and Bernd Sturmfels for several helpful discussions.