-
Do LLMs Take Care of Their Own? Similarity Signals Can Induce Cooperation
Authors:
Akash Kundu,
Emanuel Tewolde,
Ratip Emin Berker,
Samuel F. Brown,
Vincent Conitzer
Abstract:
As LLM-based agents with user-instructed goals are becoming widely deployed, they increasingly encounter each other in strategic interactions, and face challenges of finding mutually beneficial outcomes. Prior literature has argued that cooperation problems such as the Prisoner's Dilemma are resolvable in settings where agents know they follow very similar decision making patterns, as for example…
▽ More
As LLM-based agents with user-instructed goals are becoming widely deployed, they increasingly encounter each other in strategic interactions, and face challenges of finding mutually beneficial outcomes. Prior literature has argued that cooperation problems such as the Prisoner's Dilemma are resolvable in settings where agents know they follow very similar decision making patterns, as for example in monocultural AI ecosystems. Following that line of work, this paper introduces the first framework for evaluating LLM decision making when agents are provided with graded similarity signals.
Among our findings, we establish that different LLM models vary drastically in how they navigate similarity signals, with some modern models showing consistent behavior across cooperation problems, payoff structures, and prompt framing. Perhaps surprisingly, our experiments also show that the dataset based on which the similarity signal is computed has small to no impact on induced cooperation, and that LLM models systematically self-identify as highly similar when asked to evaluate another model's chain-of-thought reasoning by themselves. Finally, we develop an LLM-behavioral-game-theoretic model that captures some of their reasoning rationale, and show that it can support cooperative outcomes in equilibrium under sufficiently high similarity scores.
△ Less
Submitted 12 August, 2026;
originally announced August 2026.
-
The Memory Curse: How Expanded Recall Erodes Cooperative Intent in LLM Agents
Authors:
Jiayuan Liu,
Tianqin Li,
Shiyi Du,
Xin Luo,
Haoxuan Zeng,
Emanuel Tewolde,
Tai Sing Lee,
Tonghan Wang,
Carl Kingsford,
Vincent Conitzer
Abstract:
Context window expansion is often treated as a straightforward capability upgrade for LLMs, but we find it systematically fails in multi-agent social dilemmas. Across 7 LLMs and 4 games over 500 rounds, expanding accessible history degrades cooperation in 18 of 28 model--game settings, a pattern we term the memory curse. We isolate the underlying mechanism through three analyses. First, lexical an…
▽ More
Context window expansion is often treated as a straightforward capability upgrade for LLMs, but we find it systematically fails in multi-agent social dilemmas. Across 7 LLMs and 4 games over 500 rounds, expanding accessible history degrades cooperation in 18 of 28 model--game settings, a pattern we term the memory curse. We isolate the underlying mechanism through three analyses. First, lexical analysis of 378,000 reasoning traces associates this breakdown with eroding forward-looking intent rather than rising paranoia. We validate this using targeted fine-tuning as a cognitive probe: a LoRA adapter trained exclusively on forward-looking traces mitigates the decay and transfers zero-shot to distinct games. Second, memory sanitization holds prompt length fixed while replacing visible history with synthetic cooperative records, which restores cooperation substantially, proving the trigger is memory content, not length alone. Finally, ablating explicit Chain-of-Thought reasoning often reduces the collapse, showing that deliberation paradoxically amplifies the memory curse. Together, these results recast memory as an active determinant of multi-agent behavior: longer recall can either destabilize or support cooperation depending on the reasoning patterns it elicits.
△ Less
Submitted 8 May, 2026;
originally announced May 2026.
-
CoopEval: Benchmarking Cooperation-Sustaining Mechanisms and LLM Agents in Social Dilemmas
Authors:
Emanuel Tewolde,
Xiao Zhang,
David Guzman Piedrahita,
Vincent Conitzer,
Zhijing Jin
Abstract:
It is increasingly important that LLM agents interact effectively and safely with other goal-pursuing agents, yet, recent works report the opposite trend: LLMs with stronger reasoning capabilities behave _less_ cooperatively in mixed-motive games such as the prisoner's dilemma and public goods settings. Indeed, our experiments show that recent models -- with or without reasoning enabled -- consist…
▽ More
It is increasingly important that LLM agents interact effectively and safely with other goal-pursuing agents, yet, recent works report the opposite trend: LLMs with stronger reasoning capabilities behave _less_ cooperatively in mixed-motive games such as the prisoner's dilemma and public goods settings. Indeed, our experiments show that recent models -- with or without reasoning enabled -- consistently defect in single-shot social dilemmas.
To tackle this safety concern, we present the first comparative study of game-theoretic mechanisms designed to enable cooperative outcomes between rational agents _in equilibrium_. Across four social dilemmas testing distinct components of robust cooperation, we evaluate four families of mechanisms: (1) repeating the game for many rounds, (2) reputation systems, (3) third-party mediators to delegate decision making to, and (4) contract agreements for outcome-conditional payments between players. Among our findings, we establish that contracting and mediation are most effective in achieving cooperative outcomes between capable LLM models, and that repetition-induced cooperation deteriorates drastically when co-players vary. Moreover, we demonstrate that the mechanisms become _more effective_ under evolutionary pressures to maximize individual payoffs.
△ Less
Submitted 4 July, 2026; v1 submitted 16 April, 2026;
originally announced April 2026.
-
Decision Making under Imperfect Recall: Algorithms and Benchmarks
Authors:
Emanuel Tewolde,
Brian Hu Zhang,
Ioannis Anagnostides,
Tuomas Sandholm,
Vincent Conitzer
Abstract:
In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy…
▽ More
In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems.
△ Less
Submitted 16 February, 2026;
originally announced February 2026.
-
AIRS-Bench: a Suite of Tasks for Frontier AI Research Science Agents
Authors:
Alisia Lupidi,
Bhavul Gauri,
Thomas Simon Foster,
Bassel Al Omari,
Despoina Magka,
Alberto Pepe,
Alexis Audran-Reiss,
Muna Aghamelu,
Nicolas Baldwin,
Lucia Cipolina-Kun,
Jean-Christophe Gagnon-Audet,
Chee Hau Leow,
Sandra Lefdal,
Hossam Mossalam,
Abhinav Moudgil,
Saba Nazir,
Emanuel Tewolde,
Isabel Urrego,
Jordi Armengol Estape,
Amar Budhiraja,
Gaurav Chaurasia,
Abhishek Charnalia,
Derek Dunfield,
Karen Hambardzumyan,
Daniel Izcovich
, et al. (12 additional authors not shown)
Abstract:
LLM agents hold significant promise for advancing scientific research. To accelerate this progress, we introduce AIRS-Bench (the AI Research Science Benchmark), a suite of 20 tasks sourced from state-of-the-art machine learning papers. These tasks span diverse domains, including language modeling, mathematics, bioinformatics, and time series forecasting. AIRS-Bench tasks assess agentic capabilitie…
▽ More
LLM agents hold significant promise for advancing scientific research. To accelerate this progress, we introduce AIRS-Bench (the AI Research Science Benchmark), a suite of 20 tasks sourced from state-of-the-art machine learning papers. These tasks span diverse domains, including language modeling, mathematics, bioinformatics, and time series forecasting. AIRS-Bench tasks assess agentic capabilities over the full research lifecycle -- including idea generation, experiment analysis and iterative refinement -- without providing baseline code. The AIRS-Bench task format is versatile, enabling easy integration of new tasks and rigorous comparison across different agentic frameworks. We establish baselines using frontier models paired with both sequential and parallel scaffolds. Our results show that agents exceed human SOTA in four tasks but fail to match it in sixteen others. Even when agents surpass human benchmarks, they do not reach the theoretical performance ceiling for the underlying tasks. These findings indicate that AIRS-Bench is far from saturated and offers substantial room for improvement. We open-source the AIRS-Bench task definitions and evaluation code to catalyze further development in autonomous scientific research.
△ Less
Submitted 16 February, 2026; v1 submitted 6 February, 2026;
originally announced February 2026.
-
On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting
Authors:
Ratip Emin Berker,
Emanuel Tewolde,
Vincent Conitzer,
Mingyu Guo,
Marijn Heule,
Lirong Xia
Abstract:
Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear prog…
▽ More
Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear programming for deciding whether and when core-stable committees are guaranteed to exist. In contrast to SAT-based approaches popular in computational social choice, our method can produce proofs for a specific number of candidates independent of the number of voters. In addition to these computational gains, our program lends itself to a novel duality-based reformulation of the core stability problem, from which we obtain new existence results in special cases. Further, we use our framework to reveal previously unknown relationships between core stability and other desirable properties, such as notions of priceability.
△ Less
Submitted 18 December, 2025;
originally announced December 2025.
-
Evaluating Generalization Capabilities of LLM-Based Agents in Mixed-Motive Scenarios Using Concordia
Authors:
Chandler Smith,
Marwa Abdulhai,
Manfred Diaz,
Marko Tesic,
Rakshit S. Trivedi,
Alexander Sasha Vezhnevets,
Lewis Hammond,
Jesse Clifton,
Minsuk Chang,
Edgar A. Duéñez-Guzmán,
John P. Agapiou,
Jayd Matyas,
Danny Karmon,
Akash Kundu,
Aliaksei Korshuk,
Ananya Ananya,
Arrasy Rahman,
Avinaash Anand Kulandaivel,
Bain McHale,
Beining Zhang,
Buyantuev Alexander,
Carlos Saith Rodriguez Rojas,
Caroline Wang,
Chetan Talele,
Chenao Liu
, et al. (61 additional authors not shown)
Abstract:
Large Language Model (LLM) agents have demonstrated impressive capabilities for social interaction and are increasingly being deployed in situations where they might engage with both human and artificial agents. These interactions represent a critical frontier for LLM-based agents, yet existing evaluation methods fail to measure how well these capabilities generalize to novel social situations. In…
▽ More
Large Language Model (LLM) agents have demonstrated impressive capabilities for social interaction and are increasingly being deployed in situations where they might engage with both human and artificial agents. These interactions represent a critical frontier for LLM-based agents, yet existing evaluation methods fail to measure how well these capabilities generalize to novel social situations. In this paper, we introduce a method for evaluating the ability of LLM-based agents to cooperate in zero-shot, mixed-motive environments using Concordia, a natural language multi-agent simulation environment. Our method measures general cooperative intelligence by testing an agent's ability to identify and exploit opportunities for mutual gain across diverse partners and contexts. We present empirical results from the NeurIPS 2024 Concordia Contest, where agents were evaluated on their ability to achieve mutual gains across a suite of diverse scenarios ranging from negotiation to collective action problems. Our findings reveal significant gaps between current agent capabilities and the robust generalization required for reliable cooperation, particularly in scenarios demanding persuasion and norm enforcement.
△ Less
Submitted 2 December, 2025;
originally announced December 2025.
-
What Does It Take to Be a Good AI Research Agent? Studying the Role of Ideation Diversity
Authors:
Alexis Audran-Reiss,
Jordi Armengol-Estapé,
Karen Hambardzumyan,
Amar Budhiraja,
Martin Josifoski,
Edan Toledo,
Rishi Hazra,
Despoina Magka,
Michael Shvartsman,
Parth Pathak,
Justine T Kao,
Lucia Cipolina-Kun,
Bhavul Gauri,
Jean-Christophe Gagnon-Audet,
Emanuel Tewolde,
Jenny Zhang,
Taco Cohen,
Yossi Adi,
Tatiana Shavrina,
Yoram Bachrach
Abstract:
AI research agents offer the promise to accelerate scientific progress by automating the design, implementation, and training of machine learning models. However, the field is still in its infancy, and the key factors driving the success or failure of agent trajectories are not fully understood. We examine the role that ideation diversity plays in agent performance. First, we analyse agent traject…
▽ More
AI research agents offer the promise to accelerate scientific progress by automating the design, implementation, and training of machine learning models. However, the field is still in its infancy, and the key factors driving the success or failure of agent trajectories are not fully understood. We examine the role that ideation diversity plays in agent performance. First, we analyse agent trajectories on MLE-bench, a well-known benchmark to evaluate AI research agents, across different models and agent scaffolds. Our analysis reveals that different models and agent scaffolds yield varying degrees of ideation diversity, and that higher-performing agents tend to have increased ideation diversity. Further, we run a controlled experiment where we modify the degree of ideation diversity, demonstrating that higher ideation diversity results in stronger performance. Finally, we strengthen our results by examining additional evaluation metrics beyond the standard medal-based scoring of MLE-bench, showing that our findings still hold across other agent performance metrics.
△ Less
Submitted 9 December, 2025; v1 submitted 19 November, 2025;
originally announced November 2025.
-
The Complexity of Equilibrium Refinements in Potential Games
Authors:
Ioannis Anagnostides,
Maria-Florina Balcan,
Kiriaki Fragkia,
Tuomas Sandholm,
Emanuel Tewolde,
Brian Hu Zhang
Abstract:
The complexity of computing equilibrium refinements has been at the forefront of algorithmic game theory research, but it has remained open in the seminal class of potential games; we close this fundamental gap in this paper.
We first show that computing a pure(-strategy) perfect or proper equilibrium is $\mathsf{PLS}$-complete in concise potential games in normal form. For pure perfect equilibr…
▽ More
The complexity of computing equilibrium refinements has been at the forefront of algorithmic game theory research, but it has remained open in the seminal class of potential games; we close this fundamental gap in this paper.
We first show that computing a pure(-strategy) perfect or proper equilibrium is $\mathsf{PLS}$-complete in concise potential games in normal form. For pure perfect equilibria, we extend this result to general polytope games, which includes extensive-form games. We next turn to more structured classes of games, namely symmetric network congestion and symmetric matroid congestion games. For both classes, we show that a pure perfect equilibrium can be computed in polynomial time, strengthening the existing results for pure Nash equilibria. More broadly, we make a connection between strongly polynomial-time algorithms and efficient perturbed optimization using fractional interpolation. On the other hand, we establish that, for a certain class of potential games, there is an exponential separation in the length of the best-response path between perfect and Nash equilibria. Finally, for mixed strategies, we prove that computing a point geometrically near a perfect equilibrium requires a doubly exponentially small perturbation even in $3$-player potential games in normal form. As a byproduct, this significantly strengthens and simplifies a seminal result of Etessami and Yannakakis (FOCS '07). On the flip side, in the special case of polymatrix potential games, we show that equilibrium refinements are amenable to perturbed gradient descent dynamics, thereby belonging to the complexity class $\mathsf{CLS}$. This provides a principled and practical way of refining the landscape of gradient descent in constrained optimization.
△ Less
Submitted 10 February, 2026; v1 submitted 5 November, 2025;
originally announced November 2025.
-
Convergence of Regret Matching in Potential Games and Constrained Optimization
Authors:
Ioannis Anagnostides,
Emanuel Tewolde,
Brian Hu Zhang,
Ioannis Panageas,
Vincent Conitzer,
Tuomas Sandholm
Abstract:
Regret matching (RM) -- and its modern variants -- is a foundational online algorithm that has been at the heart of many AI breakthrough results in solving benchmark zero-sum games, such as poker. Yet, surprisingly little is known so far in theory about its convergence beyond two-player zero-sum games. For example, whether regret matching converges to Nash equilibria in potential games has been an…
▽ More
Regret matching (RM) -- and its modern variants -- is a foundational online algorithm that has been at the heart of many AI breakthrough results in solving benchmark zero-sum games, such as poker. Yet, surprisingly little is known so far in theory about its convergence beyond two-player zero-sum games. For example, whether regret matching converges to Nash equilibria in potential games has been an open problem for two decades. Even beyond games, one could try to use RM variants for general constrained optimization problems. Recent empirical evidence suggests that they -- particularly regret matching$^+$ (RM$^+$) -- attain strong performance on benchmark constrained optimization problems, outperforming traditional gradient descent-type algorithms.
We show that RM$^+$ converges to an $ε$-KKT point after $O_ε(1/ε^4)$ iterations, establishing for the first time that it is a sound and fast first-order optimizer. Our argument relates the KKT gap to the accumulated regret, two quantities that are entirely disparate in general but interact in an intriguing way in our setting, so much so that when regrets are bounded, our complexity bound improves all the way to $O_ε(1/ε^2)$. From a technical standpoint, while RM$^+$ does not have the usual one-step improvement property in general, we show that it does in a certain region that the algorithm will quickly reach and remain in thereafter. In sharp contrast, our second main result establishes a lower bound: RM, with or without alternation, can take an exponential number of iterations to reach a crude approximate solution even in two-player potential games. This represents the first worst-case separation between RM and RM$^+$. Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.
△ Less
Submitted 17 November, 2025; v1 submitted 19 October, 2025;
originally announced October 2025.
-
When Ethics and Payoffs Diverge: LLM Agents in Morally Charged Social Dilemmas
Authors:
Steffen Backmann,
David Guzman Piedrahita,
Terry Jingchen Zhang,
Emanuel Tewolde,
Rada Mihalcea,
Bernhard Schölkopf,
Zhijing Jin
Abstract:
Recent advances in LLMs have enabled their use in complex agentic roles, involving decision-making with humans or other agents, making ethical alignment a critical concern. While prior work has examined LLMs' moral judgment and strategic behavior separately, there is limited understanding of how they act when moral imperatives directly conflict with profit incentives. We introduce \msimfull (\msim…
▽ More
Recent advances in LLMs have enabled their use in complex agentic roles, involving decision-making with humans or other agents, making ethical alignment a critical concern. While prior work has examined LLMs' moral judgment and strategic behavior separately, there is limited understanding of how they act when moral imperatives directly conflict with profit incentives. We introduce \msimfull (\msim) to evaluate how LLMs behave in the prisoner's dilemma and public goods game embedded in morally charged contexts, varying moral framing, opponent behavior, and survival pressure across nine models. Beyond measuring behavior, we estimate the causal effect of each factor via average treatment effects (ATEs) and analyze agents' own reasoning traces to characterize the motives behind their choices. We find that no model remains consistently moral, with cooperation rates ranging from 7.9\% to 76.3\%. Game structure and moral framing are the strongest causal drivers of moral behavior, while reasoning-trace analysis reveals distinct motive profiles across models, ranging from predominantly payoff-maximizing to moral- and reputation-oriented. Together, these results expose the situational brittleness of current LLMs' moral behavior and the risk of deploying them where profit incentives conflict with ethical guidelines.
△ Less
Submitted 24 July, 2026; v1 submitted 25 May, 2025;
originally announced May 2025.
-
Expected Variational Inequalities
Authors:
Brian Hu Zhang,
Ioannis Anagnostides,
Emanuel Tewolde,
Ratip Emin Berker,
Gabriele Farina,
Vincent Conitzer,
Tuomas Sandholm
Abstract:
Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation -- which we refer to as expected variational inequalities (EVIs) -- where the goal is to find a distrib…
▽ More
Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation -- which we refer to as expected variational inequalities (EVIs) -- where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.
△ Less
Submitted 27 February, 2025; v1 submitted 25 February, 2025;
originally announced February 2025.
-
Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability
Authors:
Brian Hu Zhang,
Ioannis Anagnostides,
Emanuel Tewolde,
Ratip Emin Berker,
Gabriele Farina,
Vincent Conitzer,
Tuomas Sandholm
Abstract:
$Φ$-equilibria -- and the associated notion of $Φ$-regret -- are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations $Φ$ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '24) -- abbreviated as DFFPS -- settled the existence of efficient algorithms when $Φ…
▽ More
$Φ$-equilibria -- and the associated notion of $Φ$-regret -- are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations $Φ$ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '24) -- abbreviated as DFFPS -- settled the existence of efficient algorithms when $Φ$ contains only linear maps under a general, $d$-dimensional convex constraint set $\mathcal{X}$. In this paper, we significantly extend their work by resolving the case where $Φ$ is $k$-dimensional; degree-$\ell$ polynomials constitute a canonical such example with $k = d^{O(\ell)}$. In particular, positing only oracle access to $\mathcal{X}$, we obtain two main positive results: i) a $\text{poly}(n, d, k, \text{log}(1/ε))$-time algorithm for computing $ε$-approximate $Φ$-equilibria in $n$-player multilinear games, and ii) an efficient online algorithm that incurs average $Φ$-regret at most $ε$ using $\text{poly}(d, k)/ε^2$ rounds.
We also show nearly matching lower bounds in the online learning setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Φ$-regret.
From a technical standpoint, we extend the framework of DFFPS from linear maps to the more challenging case of maps with polynomial dimension. At the heart of our approach is a polynomial-time algorithm for computing an expected fixed point of any $φ: \mathcal{X} \to \mathcal{X}$ based on the ellipsoid against hope (EAH) algorithm of Papadimitriou and Roughgarden (JACM '08). In particular, our algorithm for computing $Φ$-equilibria is based on executing EAH in a nested fashion -- each step of EAH itself being implemented by invoking a separate call to EAH.
△ Less
Submitted 12 December, 2025; v1 submitted 25 February, 2025;
originally announced February 2025.
-
Computing Game Symmetries and Equilibria That Respect Them
Authors:
Emanuel Tewolde,
Brian Hu Zhang,
Caspar Oesterheld,
Tuomas Sandholm,
Vincent Conitzer
Abstract:
Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetr…
▽ More
Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game. On the other hand, we also show that the problem becomes polynomial-time solvable when we restrict the consideration of actions in one of two ways.
Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively -- that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.
△ Less
Submitted 27 February, 2025; v1 submitted 15 January, 2025;
originally announced January 2025.
-
The Value of Recall in Extensive-Form Games
Authors:
Ratip Emin Berker,
Emanuel Tewolde,
Ioannis Anagnostides,
Tuomas Sandholm,
Vincent Conitzer
Abstract:
Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various ga…
▽ More
Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize VoR in a broad class of games.
△ Less
Submitted 27 December, 2024;
originally announced December 2024.
-
Imperfect-Recall Games: Equilibrium Concepts and Their Complexity
Authors:
Emanuel Tewolde,
Brian Hu Zhang,
Caspar Oesterheld,
Manolis Zampetakis,
Tuomas Sandholm,
Paul W. Goldberg,
Vincent Conitzer
Abstract:
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer se…
▽ More
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes P, PPAD, PLS, $Σ_2^P$ , $\exists$R, and $\exists \forall$R.
△ Less
Submitted 22 June, 2024;
originally announced June 2024.
-
Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback
Authors:
Vincent Conitzer,
Rachel Freedman,
Jobst Heitzig,
Wesley H. Holliday,
Bob M. Jacobs,
Nathan Lambert,
Milan Mossé,
Eric Pacuit,
Stuart Russell,
Hailey Schoelkopf,
Emanuel Tewolde,
William S. Zwicker
Abstract:
Foundation models such as GPT-4 are fine-tuned to avoid unsafe or otherwise problematic behavior, such as helping to commit crimes or producing racist text. One approach to fine-tuning, called reinforcement learning from human feedback, learns from humans' expressed preferences over multiple outputs. Another approach is constitutional AI, in which the input from humans is a list of high-level prin…
▽ More
Foundation models such as GPT-4 are fine-tuned to avoid unsafe or otherwise problematic behavior, such as helping to commit crimes or producing racist text. One approach to fine-tuning, called reinforcement learning from human feedback, learns from humans' expressed preferences over multiple outputs. Another approach is constitutional AI, in which the input from humans is a list of high-level principles. But how do we deal with potentially diverging input from humans? How can we aggregate the input into consistent data about "collective" preferences or otherwise use it to make collective choices about model behavior? In this paper, we argue that the field of social choice is well positioned to address these questions, and we discuss ways forward for this agenda, drawing on discussions in a recent workshop on Social Choice for AI Ethics and Safety held in Berkeley, CA, USA in December 2023.
△ Less
Submitted 4 June, 2024; v1 submitted 15 April, 2024;
originally announced April 2024.
-
The Computational Complexity of Single-Player Imperfect-Recall Games
Authors:
Emanuel Tewolde,
Caspar Oesterheld,
Vincent Conitzer,
Paul W. Goldberg
Abstract:
We study single-player extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absentminded Driver game. For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality. One equilibrium concept uses generalized double halving (GDH) as a belief system and evidential decision theory (EDT), and another one uses…
▽ More
We study single-player extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absentminded Driver game. For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality. One equilibrium concept uses generalized double halving (GDH) as a belief system and evidential decision theory (EDT), and another one uses generalized thirding (GT) as a belief system and causal decision theory (CDT). Our findings relate those three solution concepts of a game to solution concepts of a polynomial maximization problem: global optima, optimal points with respect to subsets of variables and Karush-Kuhn-Tucker (KKT) points. Based on these correspondences, we are able to settle various complexity-theoretic questions on the computation of such strategies. For ex-ante optimality and (EDT,GDH)-equilibria, we obtain NP-hardness and inapproximability, and for (CDT,GT)-equilibria we obtain CLS-completeness results.
△ Less
Submitted 28 May, 2023;
originally announced May 2023.
-
Game Transformations That Preserve Nash Equilibria or Best-Response Sets
Authors:
Emanuel Tewolde,
Vincent Conitzer
Abstract:
In this paper, we investigate under which conditions normal-form games are (guaranteed to be) strategically equivalent. First, we show for N-player games (N >= 3) that
(A) it is NP-hard to decide whether a given strategy is a best response to some strategy profile of the opponents, and that
(B) it is co-NP-hard to decide whether two games have the same best-response sets.
Combining that with…
▽ More
In this paper, we investigate under which conditions normal-form games are (guaranteed to be) strategically equivalent. First, we show for N-player games (N >= 3) that
(A) it is NP-hard to decide whether a given strategy is a best response to some strategy profile of the opponents, and that
(B) it is co-NP-hard to decide whether two games have the same best-response sets.
Combining that with known results from the literature, we move our attention to equivalence-preserving game transformations.
It is a widely used fact that a positive affine (linear) transformation of the utility payoffs neither changes the best-response sets nor the Nash equilibrium set. We investigate which other game transformations also possess either of the following two properties when being applied to an arbitrary N-player game (N >= 2):
(i) The Nash equilibrium set stays the same;
(ii) The best-response sets stay the same.
For game transformations that operate player-wise and strategy-wise, we prove that (i) implies (ii) and that transformations with property (ii) must be positive affine. The resulting equivalence chain highlights the special status of positive affine transformations among all the transformation procedures that preserve key game-theoretic characteristics.
△ Less
Submitted 22 June, 2024; v1 submitted 29 October, 2021;
originally announced November 2021.