Abstract
We study the correlated equilibrium polytope PG 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 PG, and show that for -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 -games.
1 Introduction
In 1950, Nash published a very influential two-page article [Citation12] 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 [Citation20, 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 [Citation15–17, Citation19]. 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 [Citation1, Citation2]. In contrast to Nash equilibria and dependency equilibria, correlated equilibria are significantly less computationally expensive, since they only require solving a linear program [Citation14]. 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.
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 [Citation8]. Even classifying necessary conditions under which the correlated equilibrium polytope is of maximal dimension is highly nontrivial [Citation21]. This is also an interesting question from a game theoretical perspective, in particular for the computation of Nash equilibria which is PPAD-complete [Citation6]. 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 [Citation11, 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 -games, which turns out to be generated by binomials corresponding to -minors and -minors of a certain matrix (Theorem 5.8). These investigations yield novel insights into the possible combinatorial types of generic -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 -game and PG be the associated correlated equilibrium polytope. Then one of the following holds:
PG is a point,
PG is of maximal dimension 5 and of a unique combinatorial type,
There exists a -game such that has maximal dimension 3 and is combinatorially equivalent to PG.
Supported by the above theorem and our computations [Citation9] for generic -games G (where ), we conjecture that if PG is not of maximal dimension, then there exists a smaller -game with k < n such that is a full-dimensional polytope and PG is combinatorially equivalent to (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 and, whenever possible, games of type . All referenced code and a detailed study of some examples with visualizations can be found on MathRepo [Citation9]:
2 The correlated equilibrium polytope
Let n be the number of players in a normal-form game. Each player has a fixed set of pure strategies . 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 of strategies, where each player chooses to play a fixed strategy with . The payoff of player i at is the quantity of how beneficial player i values the combination of strategies as outcome of the game. A mixed strategy of a single player i is an action with probability , i.e. and . We can view this geometrically as a point in the -dimensional probability simplex .
Formally, a -game in normal form is a tuple , where is the collection of strategies of all players, and is the collection of all -payoff tensors. In particular, if n = 2, then each is a -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 has the strategies “go” and “stop”. The bimatrix below shows the payoffs of both players simultaneously, where each entry is a tuple of the payoff of each player for the tuple of strategies as the expected outcome of the game.
Table
We may interpret the given payoffs such that each of the players prefers to go (with payoff ), if the other driver stops. However, both drivers choosing to drive is the worst possible outcome for each of the players individually (with payoff 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 ( 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 be the set of all pure joint strategies of the game. The external party draws such a pure joint strategy with probability , called a mixed joint strategy. Such a joint probability distribution is a vector (or a tensor) , such that . The set of all joint probability distributions is the probability simplex .
Definition 2.2
(Correlated Equilibrium). Let G be a game with payoffs . A point is a correlated equilibrium if and only if (2.1) (2.1) for all , and for all . The linear inequalities in (2.1) together with the linear constraints define the set of all correlated equilibria of the game. The set of all such equilibria is the correlated equilibrium polytope PG of the game G.
The ambient space of the polytope PG has dimension . By definition, the maximal dimension that PG can achieve is . In the literature, in this case, PG is often called full-dimensional. To avoid confusion with conventions in convex geometry, we refer to PG 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 be the probability with which the traffic light draws the pure joint strategy . The point is a correlated equilibrium if and only if and
With the payoffs as given in the bimatrix in Example 2.1 these inequalities evaluate to
The correlated equilibrium polytope, i.e. the points p that satisfy these inequalities, has 5 vertices with coordinates . This polytope is depicted in .
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 with positive scalars leaves the polytope PG invariant. More precisely, let be a game. For each , fix and let for all . Then for the game with it holds that .
Proof.
For each player let be their payoff tensor, fix , and consider the affine transformation . Then
Since , 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 that is a tensor of rank one. More specifically, the set of Nash equilibria are those points in PG that are also contained in the image of the product map
The image of this map is the Segre variety inside .
shows a 3-dimensional correlated equilibrium polytope of a -game together with the Segre variety inside the simplex . 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 PG. More precisely, they occur as the images of the points with coordinates and under the product map from Definition 2.5, which correspond to the three black vertices in . With indexing the images of the first two points are and . 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 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 [Citation13]. A game G is called non-trivial if for some player and with . The next result states that if PG is of maximal dimension, then any Nash equilibrium lies on a proper face of PG.
Proposition 2.7.
[Citation11, Proposition 1] Let G be a non-trivial game. Then the Nash equilibria lie on a face of the correlated equilibrium polytope PG of dimension at most . In particular, if PG has maximal dimension , then the Nash equilibria lie on the relative boundary of PG.
In order to locate the possible positions of Nash equilibria, it is thus helpful to understand the conditions under which PG 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 is the polyhedral cone defined by inequalities and (3.1) (3.1) for all , and for all . For each player this defines nontrivial inequalities of type (3.1). The cone CG is a convex pointed polyhedral cone. The correlated equilibrium polytope PG is the intersection of the cone with the hyperplane where the sum of all coordinates equals 1. Therefore, a facet of PG is in bijection with a facet of CG, and a vertex of PG is in bijection with an extremal ray of CG.
We make a substitution of the coefficients in (3.1). For each we define
Note that . Thus, for each player this defines distinct variables, so in total this defines many variables. Under this substitution, the above inequality becomes (3.2) (3.2)
For fixed , let be the vector with entries for each coordinate indexed by . Using the same indexing of coordinates for , the inequalities (3.2) can be expressed as the inner product .
Example 3.1
(-games). Consider a 2-player game with . We fix the indexing . Recall that the inequalities are
The vectors have entries in the 4 unknowns . More specifically,
The cone CG is defined by the inequalities for , and , and the inequalities , where ei denote the standard basis vectors of .
Recall that the number of variables defined above is . The ambient dimension of the correlated equilibrium polytope and cone is , and the number of linear inequalities of the form (3.2) is . Let be the matrix with rows for , and let be the block matrix
By (3.2), the cone is given by
The matrix A(Y) has full rank D, and so C(Y) is a pointed cone.
For -games, where for some , we have additional relations (3.3) (3.3) for . A vector corresponds to a certain game G if and only if these relations hold. Geometrically, these relations define a linear space inside . We thus make the following definition.
Definition 3.2.
The correlated equilibrium space of -games is the linear space defined by the Equationequations (3.3)(3.3) (3.3) , where ranges over all players with at least 3 strategies . 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 .
Example 3.3
( for -games). In a -game, there are nine variables
The relations among these variables are
These relations cut out the correlated equilibrium space for -games. For any game -games G the correlated equilibrium polytope is nonempty, a point 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 .
4 The region of full-dimensionality
In this section, we introduce the region of full-dimensionality for a type of game. For fixed , this region classifies for which -games the polytope PG is of maximal dimension . The connections between full-dimensionality and elementary games are discussed in [Citation21, Section 3]. The game is elementary if and only if none of the incentive constraints is vacuous and PG has full dimension. In general, it is not understood under which conditions PG has maximal dimension (i.e. G is a full game), though there are some partial results on forbidden dimensions [Citation22, 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 PG (Proposition 2.7). Since computing Nash equilibria is PPAD-complete [Citation6] and correlated equilibria are computationally less expensive, it is a meaningful pursuit to study the combinatorial properties of full-dimensional PG.
Let be a vector of indeterminates, as described in Section 3. We consider as a matrix with indeterminates, where each choice of uniquely defines a correlated equilibrium cone
Recall that the correlated equilibrium polytope is of maximal dimension if and only if C(Y) is full-dimensional. Thus, we are interested in the region of full-dimensionality
Definition 4.1.
A semialgebraic set is a subset of defined by a boolean combination of finitely many polynomial inequalities.
Theorem 4.2.
The region of full-dimensionality is the semialgebraic set 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 such that . Let be a vector of D indeterminates. Consider the set
The expression defines a -dimensional vector, where each coordinate is a polynomial in variables x and Y. Hence, the set is defined by D + N polynomial inequalities, and is thus a (basic) semialgebraic set. The region of full-dimensionality is the intersection of the correlated equilibrium space 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 is a semialgebraic set. □
Example 4.3
( for -games). Consider a -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 ) and the ambient dimension of is M = 4. The different combinatorial types, in this case, have been fully classified in [Citation5]. Here, is the union of two open orthants:
The file dimensions2x2.nb in [Citation9] contains Mathematica code [Citation23] which also computes these inequalities.
Example 4.4
( for -games). The coordinate projection of the set onto 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
The region of full-dimensionality for -games consists of the intersection of the above mentioned pieces with the correlated equilibrium space . The Mathematica file dimensions2x3.nb in [Citation9] contains our code for computing all of the components of this semialgebraic set. We note that the orthants appearing in seem highly structured.
Remark 4.5.
The structured behavior of the regions of full-dimensionality that we see in -games arises more generally for arbitrary -games. Exploiting the structure of the matrix A(Y), the region of full-dimensionality for -games cannot satisfy any of the following conditions:
, for all .
, for all .
and , for all
and , for all .
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 -games since we must compute the coordinate projection of a semialgebraic set that lives in -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 PG for -games (Theorem 5.9). We then show that for all -games the irreducible components of the algebraic boundary of the oriented matroid stratification are coordinate hyperplanes, -minors and -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 -games are given in Example 3.1. In the Hawk-Dove game, each of the two players has two strategies =“hawk” or =“dove”.
Table
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 . The correlated equilibria polytope PG is full-dimensional with 5 vertices and 6 facets. In the case , the game becomes an example for Prisoner’s Dilemma, in which case PG is a single point.
As seen in the previous example, for fixed , different choices of the payoffs for the players in a -game can result in different combinatorial types of correlated equilibria. We would thus like to classify the regions of the correlated equilibrium space such that
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 . The dual of the cone C(Y) is defined as
By definition, the (inner) facet normals of C(Y) are generators of extremal rays of and vice versa. Let and be a row of A(Y). Seen as a linear functional, this row uniquely selects a face
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 this implies that is an extremal ray of if and only if Fh is a facet of C. If C(Y) is not full-dimensional, then there is some such that . The set of all such vectors span the lineality space of . In this case, extremal rays of are to be considered in .
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 Fh of C(Y) intersect in a single point. Equivalently, we want to understand which subsets of D – 1 rays rh of are contained in a common face. Let such that , and denote by the submatrix of A(Y) with rows indexed by H. If lie on a common face, then these rays all lie on the hyperplane given by the rowspan of . Additionally, let . Then all lie on the same side of the hyperplane. This implies that the sign of is uniquely determined for all . The collection of all regions in which the maximal minors of A(Y) satisfy a certain sign pattern is known as the oriented matroid stratification of . 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 yields a subdivision of in which distinct combinatorial types lie in distinct regions.
Definition 5.2.
Let be a semialgebraic set. The algebraic boundary is the Zariski closure of the topological (euclidean) boundary , i.e. the smallest algebraic variety containing (over ).
Construction 5.3 (Algebraic Boundary). For every the minor is a polynomial in variables Y of degree at most D, and is a polynomial inequality. Let be a sign vector. Each maximal open region in the oriented matroid stratification is of the form
Let 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 as the union of the algebraic boundaries of all such closed regions, i.e.
where the first union ranges over all sign vectors s such that is maximal, and
In the second union we only consider such that contains at least one variable. Recall that 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 IdN, so the number of such minors is . We note that the minors may not be irreducible polynomials, so they do not necessarily define the irreducible components of the variety . In total, this defines hypersurfaces, whose defining polynomials are of degree at most D.
Applying [Citation4] and [Citation3, 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 defining polynomials. Then and the number of strata in the oriented matroid stratification is at most
The following three examples illustrate this construction for small games.
Example 5.5
( for -games). In a -game we have D = 4, N = 4 and M = 4. The number of irreducible components of is β = 4, and these are the 4 coordinate hyperplanes. Indeed, the classification in [Citation5] 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 [Citation9] contains Macaulay2 code [Citation7] which explicitly computes these irreducible components.
Example 5.6
( for -games). In a -game, we have , and M = 9. The number of minors of that contain at least one variable is , 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
Thus, Proposition 5.4 implies that the number of strata in the oriented matroid stratification is at most 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 [Citation9] contains Macaulay2 code which explicitly computes these polynomials.
Example 5.7
( for -games). In a -game, we have and M = 12. The number of minors of that contain at least one variable is , 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 [Citation9] 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
The previous examples illustrate that the algebraic boundary of the oriented matroid stratification is quite nice for -games but becomes significantly more complicated even for -games. The following theorem shows that the nice structure we see for -games holds for all -games.
Theorem 5.8.
Consider a -game, i.e. a 2-player game with . Then the irreducible components of are given by
the coordinate hyperplanes,
hypersurfaces defined by quadratic binomials that are given by certain -minors and -minors of the matrix A(Y).
Proof.
We prove by induction on n. For n = 2 after reordering the rows and columns, the matrix has the following representation:
For n = 3 the columns and rows can be arranged to :
In both cases, the statement holds by Examples 5.5 and 5.6. First, we describe the general block matrix structure of for fixed . Recall that is a -matrix, where and . As in the case n = 2, 3, we can arrange the rows and columns of such that the first two rows consist of n blocks of size , which are of the form for . The following rows form a block diagonal matrix, with n blocks of size of the form for each , where the row is omitted. Finally, the last 2n rows consist of the identity matrix .
We want to show that the maximal minors of the matrix are either monomials, binomials, or zero. Note that every maximal minor of that involves a row from the identity matrix corresponds to a smaller minor of the remaining matrix. We thus consider all -minors of the submatrix of that consists of the first rows, for . Let M be such a -submatrix.
If M contains a row or column which has at most one entry, then computing 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 . 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 and , so 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 be a column of M. Since contains at least two nonzero entries, at least one entry Mij is neither in the first nor second row of . Thus, there exists a block containing Mij. Recall that the columns of containing the block bk are the columns with index 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 bk of which M contains precisely one row with precisely two nonzero entries Mij and . However, then either the column or 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 , 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 bk. The matrix M thus contains m – 2 rows from 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 blocks.
To summarize, the matrix M is of the shape where * denotes a non-zero entry, i.e. below the first two rows M is a block matrix with 2 blocks of size and blocks of size . We now proceed by induction on the (even) size m of the matrix M. If m = 4 then M does not contain any -block and it can be computed that 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 , where B is a matrix of size and D a -block. Recall that for such upper triangular block matrices holds . By induction, is a product of monomials and binomials, and is a binomial since D is a -block. Throughout the above arguments, the binomials in the product always arose as determinants of -submatrices of a block or from -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 -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 -game with generic payoffs and let be its associated correlated equilibrium polytope. Then one of the following holds
PG is a point,
PG is of maximal dimensional and of a unique combinatorial type,
There exists a -game such that is full-dimensional and combinatorially equivalent to PG.
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 -games the matrix A(Y) has 1206 nonzero maximal minors for generic Y, since 1797 of the maximal minors are identically zero. The signs of these 1206 maximal minors are completely determined by the signs of the irreducible components of for each . As in Theorem 5.8 and Example 5.6, there are 12 such irreducible components , 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 of the fi 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 .
We do this computationally, using the software Mathematica 13.0 and SageMath 9.6 [Citation18, Citation23]. We first use Mathematica to find a payoff such that for all . We then compute the corresponding combinatorial type of the polytope in SageMath. These computations can be found in the files and on MathRepo [Citation9], respectively.
As a result, we obtain 3 different possible combinatorial types, which are a single point, the unique combinatorial type of full-dimensions of -games (a bipyramid over a triangle), and a new unique full-dimensional combinatorial type. This polytope has f-vector , and the graph of this 5-dimensional polytope is depicted in . A full description of this polytope can be found in on our MathRepo page [Citation9]. □
Example 5.10
(Combinatorial types of -games). By Theorem 5.9, for generic -games there is a unique combinatorial type of full-dimension. This is a 5-dimensional polytope with f-vector and its graph is depicted in .
Theorem 5.8 shows, that in -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 -game with generic payoff matrices and let PG be its correlated equilibrium polytope. If PG is not of maximal dimension, then there exists a -game where k < n such that has maximal dimension and PG and 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 , for which is full-dimensional, by deleting certain pure strategies or merging several pure strategies into a single one. Any correlated equilibrium of the reduced game is a correlated equilibrium of the original game G, however, the opposite is not always true [Citation10, Section 5]. Conjecture 5.1 is supported by our computations thus far. To test this conjecture, we sampled random payoff matrices X for -games for n = 4, 5. The results are summarized in , which shows the number of unique combinatorial types of a given dimension that we found for each -game. In all of our computations, Conjecture 5.1 holds. The supporting code can be found on [Citation9].
In contrast to the -case, -games exhibit a much wider variety of distinct combinatorial types. In a sample of random payoff matrices for -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
Acknowledgments
The authors would like to thank Rainer Sinn and Bernd Sturmfels for several helpful discussions.
References
- Aumann, R. J. (1974). Subjectivity and correlation in randomized strategies. J. Math. Econ. 1(1): 67–96. 10.1016/0304-4068(74)90037-8
- Aumann, R. J. (1987). Correlated equilibrium as an expression of Bayesian rationality. Econometrica 55(1): 1–18. 10.2307/1911154
- Basu, S. (2003). Different bounds on the different betti numbers of semi-algebraic sets. Discrete Comput. Geom. 30(1): 65–85. 10.1007/s00454-003-2922-9
- Basu, S., Lerario, A., Natarajan, A. (2022). Betti numbers of random hypersurface arrangements. J. London Math. Soc. 106(4): 3134–3161. 10.1112/jlms.12658
- Calvó-Armengol, A. (2003). The set of correlated equilibria of 2 x 2 games. Preprint.
- Daskalakis, C., Goldberg, P. W., Papadimitriou, C. H. (2009). The complexity of computing a nash equilibrium. Commun. ACM 52(2): 89–97. 10.1145/1461928.1461951
- Grayson, D. R., Stillman, M. E. (2022). Macaulay2, Version 1.20. http://www.math.uiuc.edu/Macaulay2/.
- Lehrer, E., Solan, E., Viossat, Y. (2011). Equilibrium payoffs of finite games. J. Math. Econ. 47: 48–53. 10.1016/j.jmateco.2010.10.007
- MATHREPO Mathematical Data and Software. (2022). https://mathrepo.mis.mpg.de/correlated-equilibrium. [Online; accessed 21 September 2022].
- Myerson, R. B. (1997). Dual reduction and elementary games. Games Econ. Behav. 21(1): 183–202. 10.1006/game.1997.0573
- Nau, R., Canovas, S. G., and Hansen, P. (2004). On the geometry of nash equilibria and correlated equilibria. Int. J. Games Theory 32(4): 443–453.
- Nash Jr., J. F. (1950). Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36(1): 48–49. 10.1073/pnas.36.1.48
- Papadimitriou, C. H., Roughgarden, T. (2005). Computing equilibria in multi-player games. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press, pp. 82–91.
- Papadimitriou, C. H., Roughgarden, T. (2008). Computing correlated equilibria in multi-player games. J. ACM 55(3): 1–29. 10.1145/1379759.1379762
- Portakal, I., Sturmfels, B. (2022). Geometry of dependency equilibria. Rend. Istit. Mat. Univ. Trieste 54: Art. No. 5.
- Portakal, I., Sendra-Arranz, J. (2024). Game theory of undirected graphical models. arXiv preprint arXiv:2402.13246.
- Portakal, I., Sendra-Arranz, J. (2024). Nash conditional independence curve. J. Symbolic Comput. 122: 102255. 10.1016/j.jsc.2023.102255
- The Sage Developers. (2022). SageMath, the Sage Mathematics Software System (Version 9.6). https://www.sagemath.org.
- Spohn, W. (2003). Dependency equilibria and the causal structure of decision and game situation. Homo Oeconomicus 20: 195–255.
- Sturmfels, B. (2002). Solving systems of polynomial equations. In: American Mathematical Society, CBMS Regional Conferences Series, No 97.
- Viossat, Y. (2003). Elementary games and games whose correlated equilibrium polytope has full dimension. Preprint.
- Viossat, Y. (2010). Properties and applications of dual reduction. Economic Theory 44(1): 53–68. 10.1007/s00199-009-0477-6
- Wolfram Research, Inc. (2022). Mathematica, Version 13.0.