Papers for
game theory software developers
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.
Core nonemptiness holds for two thirds convex cooperative games
Core nonemptiness for $2/3$-convex games
Abstract: We study the core of $2/3$-convex games, a class of transferable-utility (TU) games that generalizes convex games, which requires at least two of any three distinct coalitions satisfy the supermodular inequality. We show that every $2/3$-convex game admits a marginal worth vector in the core, and hence has a nonempty core. Our proof is constructive and yields a linear-time algorithm for finding such a core allocation. We also show that $2/3$-convexity does not imply permutational convexity in general, while the implication holds under an additional superadditivity condition on pairs of singletons. As an application, we introduce a TU model motivated by the OSCE's consensus-minus-two procedure and show that the resulting game is $2/3$-convex but need not be convex.
Mediator learns and guides decisions in games with limited feedback
Learning and Steering in Incomplete-Information Games
Abstract: In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of $\widetilde O(\varepsilon^{-2})$ that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learning, equilibrium computation, and steering toward mediator-optimal extensive-form correlated equilibria (EFCE). With high probability, the Learn-Compute-Steer algorithm achieves a directness gap and an optimality gap of $\widetilde O(T^{-1/4})$, while time-average payments are of $\widetilde O(T^{-1/8})$.
Algorithm computes exact proper equilibria in two-player games
Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
Abstract: We give a deterministic polynomial-time algorithm for computing an exact extensive-form proper equilibrium in a finite two-player zero-sum extensive-form game with perfect recall and rational data. Properness is understood in the agent normal form: an action at an information set is penalized relative to a better action while all other local behavioral choices, including the player's own future actions, remain fixed. Our algorithm assigns each information set a geometric permutahedron of allowable action probabilities. A scaled doubly stochastic representation embeds these restrictions in a polynomial-size sequence-form polytope; a saddle point then satisfies the local $\varepsilon$-properness inequalities. To obtain an exact equilibrium rather than a solution at an arbitrarily small numerical perturbation, we establish sign stability of a parametric linear system, construct a persistent feasible basis, and extract the limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.
Subexponential algorithm improves solving contraction fixed points
A Decomposition Theorem and a Simple Algorithm for Contraction Fixed Points
Abstract: We prove a decomposition theorem for the problem of computing an approximate fixed point of a contraction map $f\colon [0,1]^k \to [0,1]^k$ under the $\ell_{\infty}$-norm. After a preliminary version of the decomposition theorem appeared on arXiv [CLY26], Feodorov and Haslebacher [FH26] gave a striking application of the theorem, showing that it can be used to convert any $\operatorname{poly}(k,\log(1/\varepsilon))$-query algorithm with running time $(k\log(1/\varepsilon))^{O(k)}$ into an algorithm with running time $(k\log(1/\varepsilon))^{O(\sqrt{k})}$. They instantiated this framework with an $O(k^2\log(1/\varepsilon))$-query algorithm with the desired running time, thereby obtaining the first subexponential-time algorithm for contraction fixed points under the $\ell_{\infty}$-norm and, via well-known reductions, the first deterministic subexponential-time algorithm for simple stochastic games and mean-payoff games. In addition to the decomposition theorem, as our second main result in this paper, we show that the $O(k\log(1/\varepsilon))$-query algorithm of [CLY25] can be implemented in time $(k\log(1/\varepsilon))^{O(k)}$; our algorithm may be viewed as conceptually simpler compared to the algorithm of [FH26]. A key observation here is that the function constructed in [CLY25], whose fixed points are used as the next query points, turns out to be nonexpansive under the $\ell_{\infty}$-norm, so the brute-force procedure can be replaced by known algorithms for contraction fixed points.
Computing the nucleon allocation efficiently in matching games and variants
Computing the Nucleon of Matching Games
Abstract: The nucleon is the multiplicative counterpart of the nucleolus: it lexicographically maximizes the fraction of its stand-alone value that each coalition receives. We study exact nucleon computation in matching games and in two extensions: $b$-matching games, in which players may have several partners, and partitioned matching games, in which one player may own several vertices. We resolve three open problems from a recent survey. For ordinary matching games with nonnegative rational weights, we give a polynomial-time combinatorial algorithm using maximum-weight matching, shortest paths, and minimum-cost flow, ; it returns both a nucleon allocation and a compact description of the full nucleon. In contrast, computing any nucleon allocation is NP-hard for unit-weight $b$-matching games with capacities at most three and for unit-weight partitioned matching games of width at most three. Finally, for the unresolved capacity-two case, we show that exact nucleon computation is polynomial-time Turing reducible to SHORTEST NON-ZERO CYCLE.
Computing approximate Nash equilibria with few players takes quasipolynomial time
Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players
Abstract: For every fixed $\varepsilon\in(0,1)$ and $η\in[0,1)$, we prove that computing an $(\varepsilon,η)$-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH, even in symmetric binary-payoff games with a constant number of players. The games are given by complete payoff tables, and the player count depends only on the tolerances. The weak approximate Nash equilibrium allows at most an $η$ fraction of players to gain more than $\varepsilon$ by deviating unilaterally. The main technical result is an unconditional error-amplification reduction from bimatrix games. For every fixed $δ\in(0,1)$, it transforms a rational bimatrix game with payoffs in $[0,1]$ into a symmetric binary-payoff game with a polynomial-size complete table and a player count depending only on $δ,\varepsilon,η$. Every $(\varepsilon,η)$-weak approximate equilibrium of the constructed game yields a $δ$-approximate Nash equilibrium of the bimatrix game. Construction and recovery take polynomial time in their explicit inputs. Combining this reduction with the bimatrix hardness result of Rubinstein [FOCS 16] gives a deterministic worst-case running-time lower bound of $N^{(\log N)^{1-o(1)}}$, where $N$ is the constructed table's binary encoding length.
Fictitious play can converge arbitrarily slowly in zero sum games
Arbitrarily Slow Polynomial Convergence of Fictitious Play
Abstract: We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer $k \ge 2$, we construct a payoff matrix with $(k+1)^2 - 5$ actions per player for which the duality gap of the empirical strategies decays as $Θ(t^{-1/k})$ after $t$ steps. The family starts from the standard rock-paper-scissors matrix, with each higher-order game constructed recursively from the preceding one. After a prescribed common initial action, every subsequent best response under fictitious play is unique. For $k \ge 3$, these games give counterexamples to Karlin's conjectured $O(t^{-1/2})$ convergence rate, and they extend the recent $Θ(t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.
Metric design guides equilibrium choice in multiplayer games
Metric-Based Equilibrium Selection in Noncooperative Differentiable Games
Abstract: Metric conditioning can change which equilibrium attracts learning dynamics without moving the equilibria of a differentiable game. We study how to use state-dependent symmetric positive-definite (SPD) metrics to select among known equilibria by keeping a designated equilibrium attracting while making a rival unstable. Building on classical results on matrix stability under positive-definite multiplication, we characterize when such destabilization is possible and show how restricting the metric to act independently on each player limits the stability changes that can be achieved at differential Nash equilibria. We then combine a stabilizing metric at the selected equilibrium with a destabilizing metric at the rival through smooth interpolation, yielding a single metric field that preserves every equilibrium of the game while assigning the desired local stability types. We also derive a step-size condition for implementing the method in discrete time. The approach is validated on a continuous-commitment stag hunt and an entropy-regularized iterated prisoner's dilemma, where it selects the desired equilibrium in both settings.
Distributed methods find best potential approximations in multiplayer games
Distributed Algorithms for $α$-Potential Functions in General-Sum Games
Abstract: We study the problem of computing the tightest \(α\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal--dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy--computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical \(α\)-potential constructions.
Scaling regret matching converges fast to equilibrium in zero sum games
Why Last-Iterate Scale-Invariant Regret Matching Converges Linearly?
Abstract: IREG-PRM+ normalizes the cumulative regret vector by its own norm and attains optimal regret without knowledge of the payoff scale. Run unmodified on zero-sum matrix games, it converges linearly in the last iterate, and no analysis explains why. The obstacle is that the algorithm has no fixed step size to analyze: the step size is a state variable, the inverse of a regret norm that the trajectory itself moves. Every proved linear rate for regret-matching dynamics comes from restarting or modifying the update. We identify the mechanism as norm saturation: the regret norm rises to a finite limit and freezes the step size. We prove that it always does, with an explicit bound, and that saturation forces the last-iterate Nash gap to vanish on every matrix game; pointwise convergence follows whenever the equilibrium is unique. Near a unique strictly complementary equilibrium the active support freezes in one step, and the one-round Jacobian on that support has a closed form. The last-iterate then converges linearly at a closed-form rate, provided one scale-invariant quantity stays below one: the saturated step size times the largest singular value of the value-centered payoff submatrix on the support. On the $216$-instance testbed, the $184$ instances with a resolvable limit all satisfy it. The same analysis gives a ratio certificate: observable norm-increment ratios bound the unobservable Nash-gap ratio up to a constant that enters once and does not accumulate with the iteration count. Its slope-two law holds on $96.1\%$ of the instances where the slope is measurable, and the same increment monitors progress in extensive-form games, where best-response passes can be scheduled sparsely. The code is available at https://github.com/lbn187/NormCert.
Complexity rises in multiplayer Blotto games with player-specific values
The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values
Abstract: We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.
Complexity of predicting winners in plurality voting with abstentions
Subgame-Perfect Nash Equilibria of Plurality Voting with Abstention: a PSPACE-Completeness Result for Restricted Ballots
Abstract: We consider sequential Plurality elections in which each voter may abstain or vote for a single candidate. Each voter assigns utilities to all candidates; for each voter, this induces a (weak) order over the candidates. Ties are resolved uniformly at random, and voting has a small positive cost, so that a voter prefers to abstain when their vote cannot change the election outcome. We consider a variant of this model where, for each voter, we additionally specify a prefix of her ranking, so that she is only allowed to vote for a candidate from that prefix (or abstain). We prove that for this variant of the model, deciding whether a designated candidate is among the election winners in a subgame-perfect equilibrium of the associated extensive-form game is PSPACE-complete. This partially resolves an open problem from the work of Desmedt and Elkind [2010].
Finding specific Nash equilibria in games is computationally hard
Finding a Positive Index Nash Equilibrium is PPADS-Complete
Abstract: Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].