Source-linked AI summary
Nash Loci
Luca Sodomaco, Julian Weigert
TL;DR
The paper studies games whose Nash equilibria must satisfy predetermined algebraic constraints. It defines Nash loci, computes their dimensions, multidegrees, and equations, and relates them to Grassmannian-based multigraded associated varieties. The resulting framework covers two-player and small multi-player games and connects Nash loci with multigraded Cayley–Chow constructions.
Problem
The paper addresses how to characterize games having totally mixed Nash equilibria compatible with fixed algebraic constraints on players’ strategies.
Method
The authors define Nash loci from intersections between Nash equilibrium schemes and subvarieties of multiprojective strategy spaces, then use intersection theory, multilinear equations, Segre embeddings, and Grassmannian coordinates.
Results
The paper determines Nash-locus codimensions and multidegrees, gives equations for two-player and small multi-player games, and relates Nash loci to multigraded associated varieties.
Takeaways & Limitations
Nash loci provide an algebraic framework for studying constrained totally mixed equilibria and for expressing the resulting conditions through Grassmannians and Plücker coordinates.
Takeaways & Limitations
The analysis restricts attention to totally mixed Nash equilibria and uses genericity and nondegeneracy assumptions for some scheme and locus statements.
Abstract
from arXiv · showhide
In the study of Nash equilibria of finite-player games, one often seeks equilibria that are compatible with predetermined constraints, either determined by the players or by an external agent. We discuss the algebraic loci, called Nash loci, of games whose Nash equilibrium scheme intersects a fixed algebraic variety in a product of projective spaces. We determine their dimensions and multidegrees in multiprojective space, and their equations for two-player games and for small multiple-player games. The multilinear equations defining the Nash equilibrium scheme allow us to describe Nash loci in the language of Grassmannians and Plücker coordinates. Motivated by this fact, we relate Nash loci to multigraded associated varieties, which are subvarieties in products of Grassmannians that generalize the multigraded Cayley-Chow hypersurfaces of Osserman and Trager.
1 Introduction
The paper asks which games have totally mixed Nash equilibria satisfying algebraic constraints, then develops Nash loci to characterize these games and their geometry.
- Motivation: The paper asks for games having a totally mixed Nash equilibrium whose players use equal components, generalizing the Rock, Paper, and Scissors example.It then broadens the question to arbitrary algebraic constraints in multiprojective strategy spaces.
- Main results: The paper computes codimensions and multidegrees of arbitrary Nash loci and derives determinantal equations for two-player and selected multi-player games.These results use intersection theory in multiprojective spaces.
- Nash loci: Nash loci encode games whose Nash equilibrium scheme intersects a fixed algebraic variety in multiprojective strategy space.The framework accommodates multihomogeneous polynomial constraints on mixed strategies.
- Grassmannian formulation: Multilinearity becomes linear after a mixed Segre embedding, allowing Nash loci to be expressed through products of linear spaces and Grassmannian Plücker coordinates.This reformulation motivates the introduction of multigraded associated varieties.
- Software: The authors implement Macaulay2 functions for computing Nash loci and their degrees, with scripts and documentation publicly available on Zenodo.Computational examples throughout the paper use the NashLoci.m2 file.
2 Definition and first examples of Nash Loci
This section defines Nash loci algebraically from Nash equilibrium schemes intersecting constrained strategy varieties and illustrates the construction through point, hyperplane, and conic examples.
- Setup: An n-player game is encoded by payoff tensors, while mixed strategies form points in the multiprojective strategy space Pd.Expected payoffs are multilinear contractions of the players’ strategy vectors with the payoff tensors.
- Nash equilibrium schemes: A totally mixed Nash equilibrium is represented by a point of Pd lying in the Nash equilibrium scheme ZG defined by multihomogeneous polynomial equations.The scheme is the zero scheme of a global section of a vector bundle whose component equations are multilinear in the strategy variables.
- Nash equilibrium schemes: For a generic global section, ZG is zero-dimensional and reduced, with cardinality given by the top Chern-class degree c(d).This supplies the generic count of complex Nash-equilibrium points in the scheme.
- Definition: For a subvariety Y of Pd, the Nash locus N(Y) consists of projective games whose Nash equilibrium scheme intersects Y.The variety Y can be the Zariski closure of a proper semialgebraic family of allowed probability distributions.
- Examples: When Y is a single point, N(Y) is linear of codimension Σ_i(d_i−1), while a hyperplane constraint for one player yields a hypersurface of bidegree (0,d−1).A conic constraint for a three-strategy player produces a hypersurface with a bidegree-(0,4) equation having 54 terms in the second player’s game variables.
3 Codimensions and degrees of Nash loci
The paper determines codimensions and multidegrees of Nash loci via incidence varieties and intersection theory, then derives equations for two-player and selected multi-player cases.
- Dimension and irreducibility: N(Y) is irreducible and has the same codimension c as Y under the stated format assumption.The proof uses irreducibility of Y, birationality of the second projection, and finiteness.
- Multidegrees: The multidegree of N(Y) is obtained from the coefficient of the corresponding h-monomial in the intersection-theoretic class calculation.The push-pull formula transfers coefficients from the incidence variety to the Nash locus because the projection is birational.
- Incidence construction: The incidence variety projects onto Y and N(Y), with constant-dimensional linear fibers over Y.This realizes the Nash locus through games whose Nash equilibrium scheme intersects the constraint variety.
- Two-player equations: For two-player games, the paper gives a specialization in terms of the multidegree of Y and determinantal equations for arbitrary irreducible constraints.The construction uses payoff matrices, Cramer’s rule, saturation, and additional semialgebraic conditions for real totally mixed equilibria.
- Examples: For the diagonal constraint, N(Y) is described by maximal minors, and Rock, Paper and Scissors belongs to this Nash locus through its unique totally mixed equilibrium.The diagonal case is also supported by the multidegree computation and the determinantal formulation.
- Examples: The supplied examples include hypersurfaces of bidegree (0, d −1), bidegree (0, 4), and tridegree (1, 1, 1), alongside Macaulay2 verification scripts.These computations illustrate how the degree formulas and determinantal identities are checked in software.
4 Nash loci and multigraded associated varieties
The paper recasts Nash loci as multigraded incidence varieties in products of Grassmannians, using the mixed Segre embedding to translate Nash equations into linear-space intersection problems. It establishes expected-codimension criteria, dimensions, irreducibility, multidegrees, and computational examples.
- Associated varieties: Multigraded associated varieties generalize classical associated varieties and multigraded Cayley-Chow hypersurfaces to incidence loci of arbitrary codimension.When |α| = c−1, the associated locus is expected to be a hypersurface under suitable nondegeneracy hypotheses.
- Grassmannian interpretation: The mixed Segre embedding transforms the multilinear Nash equilibrium equations into linear equations in separate vector-variable groups.The resulting linear spaces have dimensions determined by the game format.
- Grassmannian interpretation: Nash loci correspond to products of linear spaces intersecting the mixed Segre embedding of the constrained strategy variety.This identifies Nash loci with multigraded associated varieties in products of Grassmannians.
- Nash-locus strata: Nash loci decompose into strata indexed by α, with the extremal stratum dense and, under additional inequalities, fibers isomorphic to products of general linear groups.For equal-format games and the diagonal constraint, the dense stratum maps onto an associated variety with fibers (GL(d^n−1−d))^n.
- Dimensions and codimension: Under the projection conditions of Proposition 4.6, Chα(X) has the expected codimension e = |β| − r and is irreducible whenever X is irreducible.The criterion is equivalent to the existence of a product of linear spaces with finite nonempty intersection with X.
- Exceptions: The unbalanced (2,2,4) Nash resultant example shows that expected codimension can fail when no admissible product of linear spaces meets X in a finite nonempty set.Here every candidate intersection contains a line, so the actual codimension is unexpected.
- Computational examples: Examples compute explicit multidegrees and equations, including a two-codimensional three-factor associated variety and a conormal-quadric example generated by three quadrics and ten quartics.The conormal-quadric computation is verified with the supplementary Macaulay2 software.