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.

Thu 12 NovComputer Science and Game Theory
The gist
Some cooperative situations in math called games can be hard to share fairly. The authors study a special class called two thirds convex games, which relaxes previous fairness rules. They prove these games always have a stable way to distribute value so no group wants to break away. They also provide a fast method to find such fair divisions and link this to a real-world voting method called consensus-minus-two.
Open → 2611.16207v1

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})$.

Thu 5 NovComputer Science and Game TheoryArtificial IntelligenceMachine Learning
The gist
This work studies how a mediator can influence the decisions of several players in a strategic game when they do not know the players' preferences but only see the final results of interactions. The mediator learns how the players value different outcomes by observing the outcomes of repeated plays and gradually adjusts payments and suggestions to steer the game to outcomes that benefit her. The authors develop algorithms that efficiently learn from limited feedback and use this to guide players toward equilibria that satisfy the mediator's objectives. These algorithms come with theoretical guarantees on how quickly they learn and steer outcomes over time.
Open → 2611.07589v1

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.

Wed 4 NovComputer Science and Game TheoryArtificial IntelligenceMultiagent Systems
The gist
Finding a balanced way for two players to make choices where neither can gain by changing their strategy is important for game theory. The authors provide a method to compute a specific balanced solution called an extensive-form proper equilibrium efficiently and exactly, even in complex games with many possible moves. This method deals with how to assign probabilities to moves carefully, ensuring the solution is mathematically stable and precise without relying on approximate guesses. Their approach advances the ability to analyze such strategic games with guaranteed exactness and manageable calculation time.
Open → 2611.07089v1

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.

Sat 31 OctComputational ComplexityData Structures and Algorithms
The gist
Finding fixed points in math functions is a common problem in computer science. This paper presents a way to break down such problems into simpler parts, making it easier to find approximate fixed points efficiently. The authors also show a new method to speed up existing algorithms, making them much faster for high-dimensional problems. As a bonus, their approach helps solve related game theory problems that were previously harder to tackle quickly.
Open → 2611.01302v1

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.

Wed 21 OctComputer Science and Game Theory
The gist
Certain kinds of games called matching games involve players forming partnerships to share rewards. The authors study a way of fairly dividing rewards called the nucleon, which balances how much value each group of players gets compared to what they could gain alone. They develop a practical algorithm to find nucleon allocations quickly for basic matching games but show that it is very hard (NP-hard) to do so for more complex versions. For a specific intermediate case, they connect the problem to finding special cycles in graphs, providing a new perspective.
Open → 2610.29731v1

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.

Mon 19 OctComputer Science and Game TheoryComputational Complexity
The gist
Finding approximate solutions where players in a game have little incentive to change strategy is important but can be very hard. This paper shows that even when there are only a few players and simple payoffs, solving a certain kind of approximate equilibrium problem is still very complex and requires quasipolynomial time, assuming a standard computational hardness hypothesis. The authors provide a new way to translate difficult problems from two-player games to games with more players, preserving the hardness. This helps better understand the limits of how fast we can compute these game solutions.
Open → 2610.25608v1

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.

Tue 6 OctComputer Science and Game Theory
The gist
This paper shows that a common learning process called fictitious play, used in games where two players compete with opposite interests, can sometimes take a very long time to settle into a stable pattern. The authors build a series of special games where the speed at which the players' strategies improve slows down dramatically in a predictable way. This challenges previous beliefs that the process always speeds up at a certain rate. Their results generalize earlier examples and reveal that convergence can be much slower than expected.
Open → 2610.08768v1

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.

Mon 5 OctComputer Science and Game Theory
The gist
In some games where players make decisions independently, several stable outcomes can happen. The authors study how to use special mathematical tools called metrics to steer which outcome the players settle on without changing the outcomes themselves. They show how to make one desired outcome stable and a rival outcome unstable, so learning tends to lead to the preferred result. They test this approach on classic game scenarios like the stag hunt and prisoner's dilemma and demonstrate it selects the intended equilibrium.
Open → 2610.07307v1

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.

Sun 4 OctMultiagent SystemsComputer Science and Game Theory
The gist
In games where many players pick actions and their outcomes depend on everyone’s choices, it’s hard to find simple functions that capture how players influence each other. This paper studies how to compute the best simple approximation from each player’s perspective, even when players only know their own benefits. The authors develop methods that split the problem into parts players can solve locally and parts that search globally for the best overall solution. Their techniques balance accuracy with computational effort, helping to improve models used to study strategic behavior.
Open → 2610.05516v1

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.

Tue 29 SeptComputer Science and Game Theory
The gist
This paper explains why a particular algorithm called IREG-PRM+ quickly finds the best strategy in zero-sum games without knowing how large the payoffs are. The authors show that the algorithm’s step size naturally stabilizes because the cumulative regret it tracks hits a limit, causing the process to lock in a steady pace. They prove this stabilization always happens and that it guarantees the algorithm’s decisions get steadily closer to the game’s perfect balance point. The paper also provides a way to monitor progress by observing certain measurable ratios, making it easier to track performance even in more complex games.
Open → 2609.38162v1

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.

Thu 24 SeptComputer Science and Game TheoryComputational Complexity
The gist
This paper looks at how hard it is to find stable strategies in a complex game where players allocate limited resources across battlefields. When only two players compete with the same values, finding these strategies is easier and fast. But when there are many players and each values battlefields differently, figuring out stable strategies becomes much harder. The authors prove that even small approximations of solutions are very difficult to compute in these multiplayer, personalized settings. However, for some simple cases with very limited resources, stable solutions can still be found efficiently.
Open → 2609.30019v1

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].

Mon 21 SeptComputer Science and Game Theory
The gist
This paper looks at a type of voting where people vote one after another and may choose not to vote at all. Each voter has a list of favorite candidates and can only vote for some of the top ones in their list or abstain. The authors study how hard it is to figure out whether a certain candidate can win if everyone votes strategically, thinking about how others will vote. They find that this problem is very complex and belongs to a class called PSPACE-complete, meaning it is generally tough to solve with a computer. This answers a question left open by earlier work on voting strategy.
Open → 2609.24292v1

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].

Sun 20 SeptComputational ComplexityComputer Science and Game Theory
The gist
The paper shows that finding a special type of stable outcome called a Nash equilibrium with a positive index in certain two-player games is computationally difficult. Every such game has equilibria whose indices sum to one, but identifying exactly one with index +1 is proven to be hard. The authors’ result settles a previously open question by proving this problem is complete for a complexity class known as PPADS. This means that solving these games in this precise way is as hard as the hardest problems in that class.
Open → 2609.23879v1