26 papers · 1 filter
What You Earn from What You Learn: Characterization and Complexity of the Value of Information
Ratip Emin Berker, Ioannis Anagnostides, Emanuel Tewolde +3
We examine the value of information in extensive-form decision problems: the largest multiplicative gain that a decision maker can obtain from an information refinement, taken over…
Normal-Form Correlation in Markov Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
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…
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
Ioannis Anagnostides, Weiqiang Zheng
A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by…
From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +3
Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly…
Compensation Design
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +5
We introduce compensation design, the problem of designing payment rules that incentivize high-quality contributions in decentralized environments. Here, a budget-constrained princ…
The Computational Complexity of Team Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm +1
A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side c…
On the Complexity of Correlated Equilibria Beyond Normal-Form Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
Correlated equilibria are a fundamental solution concept in game theory. However, despite decades of research, the complexity beyond games of polynomial type -- such as extensive-f…
Decision Making under Imperfect Recall: Algorithms and Benchmarks
Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2
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'' a…
The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
Brian Hu Zhang, Ioannis Anagnostides, Kiriaki Fragkia +2
The proper equilibrium, introduced by Myerson (1978), is a classic refinement of the Nash equilibrium that has been referred to as the "mother of all refinements." For normal-form…
(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris +1
Follow the regularized leader FTRL is the premier algorithm for online optimization. However, despite decades of research on its convergence in constrained optimization -- and pote…
Convergence of Regret Matching in Potential Games and Constrained Optimization
Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang +3
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…
The Complexity of Equilibrium Refinements in Potential Games
Ioannis Anagnostides, Maria-Florina Balcan, Kiriaki Fragkia +3
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;…
Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
Brian Hu Zhang, Ioannis Anagnostides, Tuomas Sandholm
A considerable chasm has been looming for decades between theory and practice in zero-sum game solving through first-order methods. Although a convergence rate of has long…
Expected Variational Inequalities
Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde +4
Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressi…
The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm +1
We consider the problem of computing stationary points in min-max optimization, with a particular focus on the special case of computing Nash equilibria in (two-)team zero-sum game…
The Value of Recall in Extensive-Form Games
Ratip Emin Berker, Emanuel Tewolde, Ioannis Anagnostides +2
Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testin…
Computational Lower Bounds for Regret Minimization in Normal-Form Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated connection in the interface of online learning and game theory establishes that players minimizing swap regret converge to correlated equilibria (CE) -- a seminal game…
Barriers to Welfare Maximization with No-Regret Learning
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE)…
Convergence of for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
Ioannis Anagnostides, Tuomas Sandholm
Gradient-based algorithms have shown great promise in solving large (two-player) zero-sum games. However, their success has been mostly confined to the low-precision regime since t…
Efficient -Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina +1
Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most swap regret…
Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina +1
Policy gradient methods enjoy strong practical performance in numerous tasks in reinforcement learning. Their theoretical understanding in multiagent settings, however, remains lim…
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm +1
Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have reveal…
On the Interplay between Social Welfare and Tractability of Equilibria
Ioannis Anagnostides, Tuomas Sandholm
Computational tractability and social welfare (aka. efficiency) of equilibria are two fundamental but in general orthogonal considerations in algorithmic game theory. Nevertheless,…
Steering No-Regret Learners to a Desired Equilibrium
Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides +7
A mediator observes no-regret learners playing an extensive-form game repeatedly across rounds. The mediator attempts to steer players toward some desirable predetermined equil…