2.9k citations · 2.9k across the 22 of their papers we have counts for
12 papers · 1 filter
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…
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…
General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess
Brian Hu Zhang, Tuomas Sandholm
Since the advent of AI, games have served as progress benchmarks. Meanwhile, imperfect-information variants of chess have existed for over a century, present extreme challenges, an…
Learning a Game by Paying the Agents
Brian Hu Zhang, Tao Lin, Yiling Chen +1
We study the problem of learning the utility functions of no-regret learning agents in a repeated normal-form game. Differing from most prior literature, we introduce a principal w…
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…
Computing Game Symmetries and Equilibria That Respect Them
Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld +2
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…
Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games
Brian Hu Zhang, Tuomas Sandholm
For common notions of correlated equilibrium in extensive-form games, computing an optimal (e.g., welfare-maximizing) equilibrium is NP-hard. Other equilibrium notions -- communica…
Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
Brian Zhang, Gabriele Farina, Andrea Celli +1
We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse cor…
Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions
Brian Hu Zhang, Tuomas Sandholm
Despite the many recent practical and theoretical breakthroughs in computational game theory, equilibrium finding in extensive-form team games remains a significant challenge. Whil…