Game Theory is a package for several equilibrium concepts in game theory. It constructs the algebro-geometric and combinatorial models for Nash, correlated, dependency, and conditional independence equilibria. The latter three notions of equilibria are all generalizations of Nash equilibria. An $n$-player game in normal form is defined by $n$-tensors of format $d_1 \times d_2 \times \cdots \times d_n$, where $d_i$ is the number of pure strategies of player $i$. The entry $\{j_1, j_2, \cdots, j_n\}$ of the $i$-th (payoff) tensor for player $i$ is the payoff when player $1$ chooses strategy $j_1$, player $2$ chooses strategy $j_2$, and so on. One can define a specific game or a random game, e.g., a list with random tensors.
|
|
|
|
|
|
The notion of Nash equilibria is one of the central topics in game theory. nashEquilibriumIdeal computes a square system of $d_1 + \cdots + d_n$ polynomials that algebraically model the set of totally mixed Nash equilibria. In the case where the dimension of this ideal is zero (commonly referred to as a generic game), one can use the mixed volume of the Newton polytopes of each polynomial in the system to obtain an upper bound on the number of totally mixed Nash equilibria. The list of these Newton polytopes is provided by deltaList. The mixed volume of these polytopes equals the number of certain block derangements. The method numberTMNE is typically faster than mixedVolume in this case.
|
|
|
|
|
|
|
|
The set of correlated equilibria of a game forms a convex polytope inside the (probability) simplex which is the standard simplex of dimension $d_1 \cdots d_n -1$. Thus, the variables are taken from probabilityRing. In particular, the map from nashEquilibriumRing to probabilityRing is the Segre embedding.
|
|
|
|
|
|
The algebro-geometric model of dependency equilibria is called Spohn variety. Its defining ideal is given by rank one conditions on Spohn matrices. One can also define Konstanz matrices which is crucial to understand the projection of dependency equilibria to the payoff region.
|
|
|
|
|
The algebro-geometric model of conditional independence equilibria is obtained by intersecting the Spohn variety with the conditional independence model of a given set of conditional independence statements, followed by the removal of certain components. The set of conditional independence statements can be generated via graphical models.
|
|
|
|
|
|
|
We thank Ben Hollering<https://sites.google.com/view/benhollering> and Mahrud Sayrafi<https://www-users.cse.umn.edu/~mahrud/> for their support during the Macaulay2 in the Sciences Workshop<https://www.mis.mpg.de/de/events/series/macaulay2-in-the-sciences> where the development of this package began.
The following people have generously contributed their time and effort to this project: Luca Sodomaco<https://sites.google.com/view/luca-sodomaco/home>.
This package is based on the following papers:
- Nash Equilibria: [H. Abo, I. Portakal, and L. Sodomaco: A vector bundle approach to Nash equilibria] available on arXiv.
- Correlated Equilibria: [M.-C. Brandenburg, B. Hollering, I. Portakal: Combinatorics of Correlated Equilibria] Experimental Mathematics, 2024.
- Dependency Equilibria: [I. Portakal and B. Sturmfels: Geometry of dependency equilibria] published in Rend. Istit. Mat. Univ. Trieste 54 (Art. No. 5), 2022, 13, 2022.
- Conditional Independence Equilibria: [I. Portakal and J. Sendra-Arranz: Game theory of undirected graphical models] Journal of Algebra, Volume 666, 2025.
GameTheory uses Polyhedra.m2 for the methods of correlated equilibria and GraphicalModels.m2 for the methods of conditional independence equilibria. Throughout the package, we followed Macaulay2's convention of zero-based indexing. This can be seen e.g., in the methods of nashEquilibriumRing and probabilityRing. In particular, for an $n$-player game, the players are labeled $0, \ldots, n-1$, and if player $i$ has $d_i$ pure strategies, they are labeled $0, \ldots, d_i-1$.
This documentation describes version 1.0 of GameTheory.
If you have used this package in your research, please cite it as follows:
|
The object GameTheory is a package, defined in GameTheory.m2.
The source of this document is in GameTheory.m2:914:0.