Cover Image

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cheval, Vincent, Horn, Florian, Paul, Soumyajit, Shirmohammadi, Mahsa
Format:	Preprint
Published:	2025
Subjects:	Computer Science and Game Theory Computational Complexity F.2.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Simple Stochastic Stopping Games: A Generator and Benchmark Library
by: Rudich, Avi, et al.
Published: (2024)

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, et al.
Published: (2025)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
by: Hansen, Kristoffer Arnsfelt, et al.
Published: (2025)

Equilibrium Computation in the Hotelling-Downs Model of Spatial Competition
by: Bhaskar, Umang, et al.
Published: (2024)

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

The Computational Complexity of Variational Inequalities and Applications in Game Theory
by: Kapron, Bruce M., et al.
Published: (2024)

Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework
by: Luberisse, Joshua
Published: (2025)

On the Complexity of Learning Nash Equilibria
by: Biggar, Oliver, et al.
Published: (2026)

Efficiently Computing Equilibria in Budget-Aggregation Games
by: Becker, Patrick, et al.
Published: (2025)

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

Tight Inapproximability of Nash Equilibria in Public Goods Games
by: Dinh, Jérémi Do, et al.
Published: (2024)

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
by: Li, Tongyang, et al.
Published: (2025)

Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity
by: Caragiannis, Ioannis, et al.
Published: (2024)

Choosing What Game to Play without Selecting Equilibria: Inferring Safe (Pareto) Improvements in Binary Constraint Structures
by: Oesterheld, Caspar, et al.
Published: (2025)

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

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

The Degree of Fairness in Efficient House Allocation
by: Hosseini, Hadi, et al.
Published: (2024)

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

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

A Characterization of Complexity in Public Goods Games
by: Gilboa, Matan
Published: (2023)

Hardness of Approximate Hylland-Zeckhauser Equilibria
by: Braverman, Mark, et al.
Published: (2026)

On the Computation of Equilibria in Discrete First-Price Auctions
by: Filos-Ratsikas, Aris, 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)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
by: Ghosh, Abheek, et al.
Published: (2024)

The Complexity of Strategic Behavior in Primary Elections
by: Cleveland, Colin, et al.
Published: (2026)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
by: Chen, Xi, et al.
Published: (2025)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Skating System Unveiled: Exploring Preference Aggregation in Ballroom Tournaments
by: Horn, Laryssa, et al.
Published: (2025)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
by: Bhaduri, Purandar
Published: (2025)

Modelling Network Resilience: The Complexity of Some Graph Division Games
by: Gutowski, Grzegorz, et al.
Published: (2026)

Characterization and Computation of Normal-Form Proper Equilibria in Extensive-Form Games via the Sequence-Form Representation
by: Hou, Yuqing, et al.
Published: (2026)

Robust Stackelberg Equilibria
by: Gan, Jiarui, et al.
Published: (2023)

The Complexity of Correlated Equilibria in Generalized Games
by: Bernasconi, Martino, et al.
Published: (2025)

Computation as a Game
by: Bilokon, Paul Alexander
Published: (2025)

Anyone but Him: The Complexity of Precluding an Alternative
by: Hemaspaandra, Edith, et al.
Published: (2005)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
by: Chen, Yanlin, et al.
Published: (2023)

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

A Sequence-Form Characterization and Differentiable Path-Following Method for Computing Normal-Form Perfect Equilibria in Extensive-Form Games
by: Hou, Yuqing, et al.
Published: (2025)