The paper introduces fixed sets, a relaxation of fixed points: a nonempty finite set S with S ⊆ conv f(S).
Computing approximate correlated equilibria is as hard as computing Nash equilibria.
The authors prove PPAD-hardness for correlated equilibria in two-player concave games using a new fixed set notion.
Top University
Ioannis Anagnostides · Constantinos Daskalakis · Gabriele Farina · Noah Golowich · Tuomas Sandholm · Brian Hu Zhang
Carnegie Mellon University · Massachusetts Institute of Technology · University of Texas, Austin · Strategy Robot, Inc. · Strategic Machine, Inc.
Research Digest··3 min read
The authors show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, making it polynomial-time equivalent to finding a Nash equilibrium.
§