Papers for

game theorists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Balanced n player games linked to complex equilibrium geometry

Nashtopes and their A-discriminants

Abstract: An $n$-player game in normal form is said to be of format $\boldsymbol{d} = (d_1, \dots, d_n)$ if the $i$-th player has $d_i$ options for $1 \le i \le n$, and is said to be balanced if $d_n - 1 \le \sum_{i=1}^{n-1}(d_i - 1)$. The Nash equilibria of the game correspond to solutions of the system of indifference equations for the game, with payoff differences as coefficients and strategy probabilities as variables. As such, the mixed discriminant of this system gives some information about which games could have an unusual number of totally mixed Nash equilibria. This mixed discriminant can be regarded as an $\mathcal{A}$-discriminant for some matrix $\mathcal{A}$ in the sense of [Gelfand--Kapranov--Zelevinsky 1994], and the convex hull of the columns of $\mathcal{A}$ is a polytope, which we call the Nashtope. We study this $\mathcal{A}$-discriminant for each balanced game format with at least three players. This discriminant is a subset of the Nash discriminant variety introduced in [Abo--Portakal--Sodomaco 2026]. We compute the codimension and degree of this discriminant for all balanced game formats, including on-boundary formats, using the Euler obstruction formula in [Matsui--Takeuchi 2011]. Our $\mathcal{A}$-discriminant locus corresponds to a special multigraded Hurwitz locus studied in [Pratt--Sodomaco--Sturmfels 2026]. As a consequence of [Pokidkin 2026], we obtain the codimensions and degrees of the irreducible components of the Nash discriminant variety for each balanced game format with at least three players, fully resolving Problem 3.8 of [Abo--Portakal--Sodomaco 2026].

Wed 21 OctComputer Science and Game Theory
The gist
The paper studies a special way to understand games where each player can choose from several options. The authors look at the mathematical shapes connected to where players’ best choices balance out in a mixed strategy. These shapes, called Nashtopes, help describe when games have unexpected numbers of balanced outcomes. They also calculate important properties of these shapes for many types of games with three or more players. This work solves a previously open problem about these game shapes and their mathematical signatures.
Open → 2610.29889v1

Efficient algorithm finds normal-form correlated equilibria in markov games

Normal-Form Correlation in Markov Games

Abstract: There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $ε$-NFCE in time $S(AH/ε)^{O(n)}$. This is the first algorithm polynomial in $1/ε$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.

Fri 2 OctComputer Science and Game TheoryComputational ComplexityData Structures and Algorithms
The gist
Finding ways for players to coordinate strategies in complex multi-step games has been a tough problem. The authors developed the first efficient method to compute a specific form of equilibrium called a normal-form correlated equilibrium in games that unfold over multiple stages with a fixed number of players. Their approach uses a new idea of constant-expectation correlated equilibria to break down the problem into simpler parts solvable by linear programming. They also show certain versions of the problem are computationally as hard as finding Nash equilibria, connecting the difficulty of these solution concepts.
Open → 2610.03621v1

Polyhedral methods clarify complexity of cooperative game problems

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

Abstract: We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

Mon 21 SeptComputer Science and Game TheoryComputational Complexity
The gist
Cooperative games involve many players working together and require a huge amount of information, making computations very hard. The authors study special cases where the input size is smaller, called k-additive games, and find efficient ways to solve key problems in these cases. They also prove that for certain games, these problems remain very hard to solve, explaining why some game properties are difficult to understand. Their work builds bridges between geometry and game theory to better understand when cooperative game computations are feasible.
Open → 2609.24593v1

Stable coexistence patterns found in ecological and game systems

Stable Coexistence in Ecologies and Games

Abstract: We study feasible stable equilibria of Lotka-Volterra systems and their higher-order extensions. We complete the classification of impossible ecological interaction networks with at most four species and extend several of these impossibility results to families with arbitrarily many species. We then show that these sign-pattern obstructions are specific to the pairwise Lotka-Volterra model: arbitrary prescribed growth rates and pairwise coefficients can be supplemented by higher-order interactions so as to admit a feasible asymptotically stable equilibrium. Through the correspondence with replicator dynamics, we interpret feasible equilibria of higher-order Lotka-Volterra systems as totally mixed symmetric Nash equilibria of symmetric multiplayer games, derive bounds on their number, and study their robustness under perturbations of the payoff tensors. We conclude by showing that every impossible ecology determines a nonempty open class of symmetric two-player games with no totally mixed evolutionarily stable strategy.

Tue 8 SeptComputer Science and Game Theory
The gist
This paper looks at how groups of species or players interact in stable and balanced ways, focusing on models that describe these relationships. The authors figured out exactly which small groups of species cannot coexist stably, and showed that adding more complex interactions can allow stability even when the simpler models fail. They also showed how these ecological models relate to game theory, helping us understand stable strategies in games with many players. Finally, they connect impossible ecological scenarios to games where no universally stable strategy exists.
Open → 2609.09286v1

Risk attitudes influence long-term outcomes in coordination games

Entropic Risk-Sensitive Evolutionary Learning and Equilibrium Selection in Coordination Games

Abstract: We study risk-sensitive evolutionary learning dynamics and their long-run equilibrium selection behaviors in coordination games. Agents' risk attitudes enter through the classical entropic risk measure, which evaluates opponent-induced payoff uncertainty and feeds into noisy best responses under two standard revision protocols: best response with mutations and logit choice. We first analyze $2\times 2$ coordination games in both single-population symmetric and two-population asymmetric settings. In the single-population setting, unlike the risk-neutral case where the dynamics are known to favor the risk-dominant equilibrium, we show that risk sensitivity can change the stochastically stable outcome: a greater risk-seeking attitude favors the payoff-dominant equilibrium, while a greater risk-averse attitude favors the maximin equilibrium. Thus, the population's risk attitude may act as a control knob for long-run equilibrium selection. In both population settings, we also identify a robust regime: any super-dominant equilibrium is stochastically stable for all risk attitudes, under both protocols, and across populations. We further extend the single-population analysis to symmetric $k$-action games, which include symmetric $k$-action coordination games as a special case, under risk-sensitive best response with mutations. In this setting, we show that, for sufficiently large populations, sufficiently risk-seeking agents uniquely select the strongly payoff-dominant equilibrium when it exists, whereas sufficiently risk-averse agents uniquely select the strongly maximin equilibrium when it exists. These results show that entropic risk sensitivity may serve as a systematic mechanism for steering equilibrium selection in evolutionary games, beyond the classical risk-neutral benchmark.

Tue 8 SeptComputer Science and Game TheoryMultiagent Systems
The gist
Sometimes people or groups have to choose together between different options that benefit them differently. This study looks at how being more or less worried about risk changes which shared choice is made over time. The authors show that when players are more risk-seeking, they tend to pick the option with the highest reward, but when they are more risk-averse, they prefer the safest option. These results suggest that how people feel about risk acts like a control that can steer which outcome becomes stable in repeated decisions.
Open → 2609.08677v1

Strategy model selection improves stability in multi-agent games

Rank Without an Oracle: Deviation-Aware Interaction-Rank Selection from Offline Multi-Agent Logs

Abstract: Offline multi-agent payoff models are estimated under a logging distribution but used on distributions induced by learned solutions and unilateral deviations. Standard held-out loss can therefore favor an interaction class that predicts logged play well while distorting strategic incentives. We introduce Selective Interaction-Rank Validation (SIRV) for finite games with known logging distributions. A training split fits nested payoff models and constructs a common union of all candidate deployment and unilateral-replacement distributions; an independent calibration split evaluates every candidate on this same union. SIRV returns the smallest rank whose simultaneous upper worst-target risk is within tolerance of the best upper score, and abstains when a declared target is unsupported or too imprecisely estimated. A common coverage event yields a finite-candidate target-risk bound and a candidate-specific coarse correlated equilibrium (CCE) gap certificate. We also isolate an exact two-point off-support non-identifiability result. In a controlled factorial study with 2,048 independent games per family, empirical-Bernstein bounds reduce the median CCE-gap certificate by 42.5% relative to Hoeffding bounds on common returns, with a 1.36-point reduction in supported return. Under paired rank misspecification and in a separately generated congestion family, the SIRV-EB fallback rule lowers mean true candidate-selection CCE regret relative to ID-Mean, while retaining game-level losses. Across 384 games at $N=3,5,8$, ID-Mean-relative mean CCE-regret effects stay positive while certified return falls sharply under weak coverage. These results separate certifiable model selection from universal strategic improvement.

Tue 8 SeptMultiagent SystemsComputer Science and Game Theory
The gist
Predicting how multiple decision-makers interact often uses data from past play, but this can mislead if the situation changes. The authors offer a method called SIRV that better chooses models by checking how well they predict outcomes including possible player changes. This approach helps find models that keep strategic incentives accurate and avoids selecting models that only fit past data well. The method provides guarantees about prediction quality and identifies when data is insufficient, tested on thousands of simulated games.
Open → 2609.08358v1