Cover Image

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zhang, Brian Hu, Anagnostides, Ioannis, Tewolde, Emanuel, Berker, Ratip Emin, Farina, Gabriele, Conitzer, Vincent, Sandholm, Tuomas
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Expected Variational Inequalities
by: Zhang, Brian Hu, et al.
Published: (2025)

On the Interplay between Social Welfare and Tractability of Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2023)

The Value of Recall in Extensive-Form Games
by: Berker, Ratip Emin, et al.
Published: (2024)

Computing Optimal Equilibria in Repeated Games with Restarts
by: Berker, Ratip Emin, et al.
Published: (2024)

Convergence of Regret Matching in Potential Games and Constrained Optimization
by: Anagnostides, Ioannis, et al.
Published: (2025)

Efficient $Φ$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2024)

A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
by: Anagnostides, Ioannis, et al.
Published: (2025)

On the Complexity of Correlated Equilibria Beyond Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2026)

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2023)

Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
by: Zhang, Brian Hu, et al.
Published: (2025)

Computational Lower Bounds for Regret Minimization in Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2024)

Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2023)

Barriers to Welfare Maximization with No-Regret Learning
by: Anagnostides, Ioannis, et al.
Published: (2024)

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
by: Zhang, Brian Hu, et al.
Published: (2022)

Convergence of $\text{log}(1/ε)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
by: Anagnostides, Ioannis, et al.
Published: (2024)

The Complexity of Equilibrium Refinements in Potential Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Decision Making under Imperfect Recall: Algorithms and Benchmarks
by: Tewolde, Emanuel, et al.
Published: (2026)

Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
by: Zhang, Brian, et al.
Published: (2022)

Computing Game Symmetries and Equilibria That Respect Them
by: Tewolde, Emanuel, et al.
Published: (2025)

Game Transformations That Preserve Nash Equilibria or Best-Response Sets
by: Tewolde, Emanuel, et al.
Published: (2021)

Polynomial-Time Computation of Exact $Φ$-Equilibria in Polyhedral Games
by: Farina, Gabriele, et al.
Published: (2024)

On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria
by: Zhang, Brian Hu, et al.
Published: (2024)

(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
by: Anagnostides, Ioannis, et al.
Published: (2026)

On Tractable $Φ$-Equilibria in Non-Concave Games
by: Cai, Yang, et al.
Published: (2024)

Position: Machine Learning for Heart Transplant Allocation Policy Optimization Should Account for Incentives
by: Anagnostides, Ioannis, et al.
Published: (2026)

Steering No-Regret Learners to a Desired Equilibrium
by: Zhang, Brian Hu, et al.
Published: (2023)

The Complexity of Computing Robust Mediated Equilibria in Ordinal Games
by: Conitzer, Vincent
Published: (2024)

On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting
by: Berker, Ratip Emin, et al.
Published: (2025)

The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
by: Zhang, Brian Hu, et al.
Published: (2026)

Hidden-Role Games: Equilibrium Concepts and Computation
by: Carminati, Luca, et al.
Published: (2023)

Obvious Independence of Clones
by: Berker, Ratip Emin, et al.
Published: (2022)

How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
by: Berker, Ratip Emin, et al.
Published: (2026)

A Lower Bound on Swap Regret in Extensive-Form Games
by: Daskalakis, Constantinos, et al.
Published: (2024)

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections
by: Zilberstein, Itai, et al.
Published: (2026)

Designing Rules to Pick a Rule: Aggregation by Consistency
by: Berker, Ratip Emin, et al.
Published: (2025)

Beyond Symmetry in Repeated Games with Restarts
by: Fleischmann, Henry, et al.
Published: (2025)

Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games
by: Zhang, Brian Hu, et al.
Published: (2024)

An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$-Regret Minimization
by: Farina, Gabriele, et al.
Published: (2026)

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2026)