  It is a well-known fact that correlated equilibria can be computed in
polynomial time in a large class of concisely represented games using the
celebrated Ellipsoid Against Hope algorithm (Papadimitriou and Roughgarden,
2008; Jiang and Leyton-Brown, 2015). However, the landscape of efficiently
computable equilibria in sequential (extensive-form) games remains unknown. The
Ellipsoid Against Hope does not apply directly to these games, because they do
not have the required "polynomial type" property. Despite this barrier, Huang
and von Stengel (2008) altered the algorithm to compute exact extensive-form
correlated equilibria.
  In this paper, we generalize the Ellipsoid Against Hope and develop a simple
algorithmic framework for efficiently computing saddle-points in bilinear
zero-sum games, even when one of the dimensions is exponentially large.
Moreover, the framework only requires a "good-enough-response" oracle, which is
a weakened notion of a best-response oracle.
  Using this machinery, we develop a general algorithmic framework for
computing exact linear $\Phi$-equilibria in any polyhedral game (under mild
assumptions), including correlated equilibria in normal-form games, and
extensive-form correlated equilibria in extensive-form games. This enables us
to give the first polynomial-time algorithm for computing exact
linear-deviation correlated equilibria in extensive-form games, thus resolving
an open question by Farina and Pipis (2023). Furthermore, even for the cases
for which a polynomial time algorithm for exact equilibria was already known,
our framework provides a conceptually simpler solution.
