# The complexity of approximate (coarse) correlated equilibrium for incomplete
information games

Binghui Peng
Columbia University
<EMAIL_ADDRESS>Aviad Rubinstein
Stanford University
<EMAIL_ADDRESS>
###### Abstract

We study the iteration complexity of decentralized learning of approximate
correlated equilibria in incomplete information games.

On the negative side, we prove that in extensive-form games, assuming
$\PPAD\not\subset\TIME(n^{\polylog(n)})$, any polynomial-time learning
algorithms must take at least $2^{\log_{2}^{1-o(1)}(|\mathcal{I}|)}$
iterations to converge to the set of $\epsilon$-approximate correlated
equilibrium, where $|\mathcal{I}|$ is the number of nodes in the game and
$\epsilon>0$ is an absolute constant. This nearly matches, up to the $o(1)$
term, the algorithms of [PR24, DDFG24] for learning $\epsilon$-approximate
correlated equilibrium, and resolves an open question of Anagnostides,
Kalavasis, Sandholm, and Zampetakis [AKSZ24]. Our lower bound holds even for
the easier solution concept of $\epsilon$-approximate coarse correlated
equilibrium

On the positive side, we give uncoupled dynamics that reach
$\epsilon$-approximate correlated equilibria of a Bayesian game in
polylogarithmic iterations, without any dependence of the number of types.
This demonstrates a separation between Bayesian games and extensive-form
games.

##  1 Introduction

Our work considers fundamental questions on modeling and designing agents who
learn to interact in settings with incomplete information. From an online
learning perspective, we want agents that achieve low external
regret111Definitions of external and swap regret, Bayesian and extensive-form
games, and various notions of equilibria are deferred to Section 2., ideally
also satisfying the stronger notion of low swap regret. From a game theory
perspective, we consider agents that learn to play in games of incomplete
information; we ask whether they can efficiently converge to the set of
approximate coarse coarse correlated (CCE) equilibria, ideally also satisfying
the stronger notion of approximate correlated equilibria (CE). The connection
between online learning and equilibrium computation is well-known (e.g. see
[BM07]): If each agent runs an online learning algorithm with low external
regret, then the empirical distribution converges to the set of approximate
CCE; if it further satisfies low swap regret, then the distribution converges
to the set of approximate CE .

Correlated equilibria (specifically, normal-form correlated equilibria,
NFCE222Different variants of CCE and CE have been considered for games of
incomplete information. In what is arguably the most natural and desired
variant, normal-form CE (NFCE), the correlation can be implemented by a
correlating device sending each player a signal ex-ante, i.e. one signal that
is independent of their type (in Bayesian game) or node in the game tree (in
an extensive-form game). Motivated primarily by the conjecture that NFCE are
intractable, several other variants have been considered [VSF08, Fuj23].) have
long been conjectured intractable [VSF08], until recently [DDFG24, PR24] gave
algorithms that, for both Bayesian games and more general extensive-form
games, compute $\epsilon$-NFCE in $(|\mathcal{I}|\log(n))^{O(1/\epsilon)}$
iterations of uncoupled dynamics, where $|\mathcal{I}|$ is the size of the
game (number of types or game nodes) and $n$ is the number of actions. Put in
the language of online learning, agents can achieve $\epsilon$-swap regret
after $(|\mathcal{I}|\log(n))^{O(1/\epsilon)}$ iterations. While this is
polynomial in the full description of the game, the dependence on
$|\mathcal{I}|$ (which is often combinatorial in natural game parameters) is
undesirable.

A natural question is whether the algorithms of [DDFG24, PR24] can be
improved. Our results show that the answer depends on whether we have a
Bayesian game or an extensive-form game:

##### A lower bound on (poly-time) external regret in extensive-form games

Recent work of [AKSZ24] showed that even with only three players, and even if
one settles for the weaker desiderata of low external regret or approximate
coarse correlated equilibrium, they cannot be achieved in extensive-form games
by polynomial-time agents running for fewer than
$2^{\log_{2}^{1/2-o(1)}(|\mathcal{I}|)}$ iterations, assuming the “ETH for ”
[BPR16]. In this work we give an improved reduction that:

  * •

Raises the lower bound on the number of iterations to
$2^{\log_{2}^{1-o(1)}(|\mathcal{I}|)}$; notice that this is almost tight as
$2^{\log_{2}^{1+o(1)}(|\mathcal{I}|)}$ is already sufficient by [DDFG24,
PR24].

  * •

Weakens the complexity assumption from
$\PPAD\not\subset\TIME(2^{\tilde{\Omega}(n)})$ to
$\PPAD\not\subset\TIME(n^{\polylog(n)})$; this lower bound is almost tight
since if $\PPAD=\FP$ players can simply compute and play a Nash equilibrium.

######  Theorem 1.1.

Let $\epsilon>0$ be an absolute constant. Assuming
$\PPAD\not\subset\TIME(n^{\polylog(n)})$, there is no polynomial time learning
dynamics that guarantee to converge to the set of $\epsilon$-CCE of a three
player extensive-form game in $2^{\log_{2}^{1-o(1)}(|\mathcal{I}|)}$
iterations.

This resolves an open question of [AKSZ24] on the iteration complexity of CCE
in extensive-form games, up to the $o(1)$ term in the exponential.

##### An algorithm for swap regret minimization in Bayesian games

Our second result shows that for Bayesian games, there is a much better
learning dynamics: it runs in time polynomial in the game description, and
achieves $\epsilon$-swap regret (equivalently, $\epsilon$-CE), using only
$(\log(n)/\epsilon^{2})^{O(1/\epsilon)}$ iterations; in particular there is no
dependence whatsoever on the number of types!

######  Theorem 1.2.

Let $\epsilon>0$ and $n$ be the number of actions. There is an uncoupled
dynamic that converges to the set of $\epsilon$-CE of a Bayesian game in
$(\log(n)/\epsilon^{2})^{O(1/\epsilon)}$ iterations.

This separates the complexity of computing $\epsilon$-CE in Bayesian and
extensive-form games.

###  1.1 A brief overview of our approach

####  1.1.1 Lower bound for extensive-form game

We first review the previous lower bound of [AKSZ24], which is based on a
framework of [FGK23]. Then we give a high level overview of our new ideas.

##### Previous approach

Recent work of [FGK23] gives a new framework for lower bounding the number of
iterations for obtaining approximate CCE; [FGK23] originally used this idea to
Markov games, and [AKSZ24] very recently applied it to extensive form games.
These reductions -as well as ours- are based on three key ideas:

Low rank CCE

We say that a correlated distribution is low rank (called “sparse” in previous
work333We believe that “low rank” is a better term to distinguish from
distributions with sparse supports.) if it can be written as a mixture of a
small number of product distributions. Uncoupled learning dynamics where
agents independently update their strategies based on the history of play
induce correlated distributions whose rank is at most the number of
iterations. The reductions prove hardness results for the problem of computing
low-rank approximate CCE; as a corollary, computationally efficient uncoupled
dynamics cannot approach approximate CCE / low external regret.

Repeated game

At a high level, the reductions in [FGK23, AKSZ24] begin with a normal-form
game where (approximate) Nash equilibrium is hard to find. The reductions
construct an extensive form (or Markov) game which sequentially repeats the
hard normal-form game $H$ times. Even though it is easy to find an
(approximate) CCE in the normal-form game, recall that it is crucial that each
player only observes their signal. However if the CCE is low rank, the players
can learn each other’s signals from their strategies in previous repetitions,
breaking the correlation.

Kibitzer player

The downside of sequentially repeating the normal-form games is that it brings
spurious equilibria which don’t exist in the single-shot game; in particular,
equilibria where players may be incentivized to play low-payoff actions with
threats of retaliations in future repetitions of the game. To circumvent these
artifacts of extensive-form games, we would like to re-normalize the payoff of
each player in each repetition with respect to other players’ strategies, then
players are incentivized to play myopically because any (dis)advantage they
could obtain in future repetitions will be normalized away anyway. To
correctly compute this normalization, [BCI+08] introduce an additional player,
the Kibitzer: starting from the original game between Alice and Bob, in each
iteration the Kibitzer competes with one player, say Alice ; both Kibitzer and
Alice are scored relative to each other’s strategy when measured against the
same Bob strategies.

##### Our approach

In this work, we improve over the reduction from [AKSZ24] in both complexity
assumption and lower bound on the number of iterations (in our reduction, both
are nearly tight). The key to obtaining a better reduction is that we start
from $\epsilon$-Bayesian Nash equilibrium ($\epsilon$-BNE444Specifically, we
reduce from what we call (every-type-$\epsilon$)-BNE, where each player can,
at any type, gain at most $\epsilon$, by deviating from its current strategy.
A formal definition is shown in Definition 2.2, followed by a detailed
discussion.) for a one-shot Bayesian game instead of $\epsilon$-NE of a
normal-form complete information game. The advantage of starting the reduction
from $\epsilon$-BNE is that it is a much harder problem than $\epsilon$-NE:
While $\epsilon$-NE can be found in quasipolynomial time [LMM03],
$\epsilon$-BNE is -complete [Rub18].

The reduction from $\epsilon$-BNE becomes more delicate because it is possible
that even off-equilibrium players only have an $\epsilon$-improving deviation
for one type, while for a random/average type their strategy is approximately
optimal555This would not be an issue if we start the reduction from what we
call (ex-ante-$\epsilon$)-BNE, however this more relaxed solution concept is
not known to be -hard. Here we give another application of the Kibitzer
player: we let Kibitzer find a type that admits an $\epsilon$-improving
deviation. Specifically, for each repetition of the Bayesian game, the
Kibitzer first chooses a player, say Alice. Then Kibitzer chooses a type
$\theta$ for Alice. Kibitzer’s goal is to outperform Alice, on the type it
chooses and the action it plays. Nature (the “chance” player) then samples the
type $\theta^{\prime}$ of Bob, conditioning on type $\theta$ for Alice.
Crucially, this way Kibitzer does not know $\theta^{\prime}$. Finally,
Kibitzer and Alice choose actions for type $\theta$, and Bob chooses an action
for type $\theta^{\prime}$.

####  1.1.2 Algorithm for Bayesian games

Our algorithm is based on the swap-to-external regret reduction of [PR24,
DDFG24]. The idea is to run multiple instance of low-external-regret
algorithms, each instance restarts and updates in different frequency. [PR24,
DDFG24] prove that as long as the low-external-regret algorithm guarantees at
most $\epsilon$-external regret in $H$ iterations, the overall algorithm has
$\epsilon$-swap regret in $H^{O(1/\epsilon)}$ iterations. In a Bayesian game,
if each player has $K$ types and $n$ actions, the entire strategy space has
size $n^{K}$. By running MWU over the strategy space, it takes
$H=O(\log(n^{K})/\epsilon^{2})=O(K\log(n)/\epsilon^{2})$ iterations to
guarantee $\epsilon$-external regret, and therefore, a total number of
$(K\log(n)/\epsilon^{2})^{O(1/\epsilon)}$ iterations.

Recall the number of iterations in Theorem 1.2 is independent of the number of
types $K$. Our key idea is, instead of running MWU over the entire strategy
space, we run MWU over each type and the final strategy is taken as the
product at each type666This is equivalent to running MWU over the entire
strategy space, but assigning different learning rates to each type. The key
observation is, the appearance probability of each type is fixed during no-
regret learning, so after taking the product over other types, the external
regret guarantee continues to hold (for every type). One can then apply the
swap-to-external regret analysis of [PR24, DDFG24].

###  1.2 Related work

##### Decentralized learning in games

There is a long line of work regard learning in games [FS97, FS99, FV97, FV98,
FV99, HMC00, HMC01, CBL03, SL05, BM07, SL07, PR08, HM10, HMC13, SALS15,
FLL+16, CP20, DFG21, ADF+22, AFK+22, PR23, PR24, DDFG24].

Our work focuses on incomplete information games – Bayesian games and
extensive-form games – a central topic in the literature [For93, HST15, Fuj23,
VSF08, FCMG22, ZJBP07, LWZB09, FLFS19, FKS19, FLLK22, BJM+22, AFS23, PR24,
DDFG24] with important real-world applications [BBJT15, BS18, BS19, BLGS19].
For CCE, there are decentralized learning algorithms (e.g [FLLK22]) that
converge to the set of $\epsilon$-CCE of extensive-form games (resp. Bayesian
game) in $O(|\mathcal{I}|\log(n))$ iterations (for constant $\epsilon>0$). Our
lower bound (Theorem 1.1) gives a near matching lower bound. For the stronger
notion of NFCE, it was often conjectured intractable (e.g. see [VSF08]). The
recent work [PR24, DDFG24] refute this conjecture for constant $\epsilon>0$
and give an algorithm that converges to an $\epsilon$-NFCE in
$(|\mathcal{I}|\log(n)/\epsilon^{2})^{O(1/\epsilon)}$ iterations. Our work
builds upon the framework of [PR24, DDFG24] but improves the number of
iterations to $(\log(n)/\epsilon^{2})^{O(1/\epsilon)}$ for Bayesian games,
which are completely independent of the number of types.

##### Lower bounds for games

The complexity class of (Polynomial Parity Arguments on Directed graphs) was
first introduced by Papadimitriou [Pap94] to capture a particular genre of
total search functions. Since then, a variety of important problems were shown
to be -hard [CDDT09, VY11, CPY13, OPR16, Rub18, Rub19, FRGH+21, DSZ21, PP21,
DFHM22, CCPY22, CP23, DGZ23, JMS23], a well-known example is the complexity of
Nash equilibrium in normal-form games [CDT09, DGP09].

A recent line of work [FGK23, AKSZ24] studied the complexity of decentralized
learning for coarse correlated equilibrium, by examining the computational
complexity of finding a low rank coarse correlated equilibrium. [FGK23]
initiated this line of work and showed it is -hard to find an $\epsilon$-CCE
in Markov game with polynomial rank, for inverse polynomially small
$\epsilon$777[FGK23] also showed a lower bound for constant $\epsilon$ under
ETH for . [AKSZ24] studied the extensive-form game and proved that there is no
polynomial time algorithm for finding
rank-$2^{\log_{2}^{1/2-o(1)}|\mathcal{I}|}$ $\epsilon$-CCE in extensive-form
game for some constant $\epsilon>0$, under the exponential time hypothesis
(ETH) for . Here ETH for is a refinement of the $\P\neq\PPAD$ conjecture,
which asserts that the -complete problem End-of-Line requires exponential
time. This conjecture was motivated by the exponential lower bound in the
black box model and it was used in the work of [Rub16] to rule out polynomial
time algorithms for finding approximate Nash equilibrium in normal-form games.
In our work, we use a substantial weaker conjecture, i.e., we only need to
assume the complete problem in does not have quasipolynomial time algorithms.

##  2 Preliminary

##### Notation

Throughout the paper, we write $[n]=\\{1,2,\ldots,n\\}$ and
$[n_{1}:n_{2}]=\\{n_{1},n_{1}+1,\ldots,n_{2}\\}$. For any finite set $S$, we
use $\Delta(S)$ to denote probability distributions over $S$. For any
distribution $p,q$, we use $\mathsf{TV}(p;q)$ to denote the total variation
distance between $p$ and $q$.

###  2.1 Bayesian game

In an $m$-player Bayesian game, let $\Theta_{i}$ $(|\Theta_{i}|=K)$ be the set
of types and let $A_{i}$ ($|A_{i}|=n$) be the set of actions for player $i$.
Let $\Theta=\Theta_{1}\times\cdots\times\Theta_{m}$ be the set of type
profiles of all players. The type profile $\theta\in\Theta$ is generated from
a prior distribution $\rho\in\Delta(\Theta)$. Let $A=A_{1}\times\cdots\times
A_{m}$ be the action profiles of all players. The utility function
$u_{i}:\Theta\times A\rightarrow[0,1]$ of player $i$ maps a type profile and
an action profile to a payoff value. A strategy $s_{i}:\Theta_{i}\rightarrow
A_{i}$ determines the action $s_{i}(\theta_{i})\in A_{i}$ to be selected when
player $i$ has private type $\theta_{i}\in\Theta_{i}$. Let
$S_{i}=A_{i}^{\Theta_{i}}$ be the set of pure strategies of player $i$ and
$S=S_{1}\times\cdots\times S_{m}$ be the entire strategy space. We use
$\Delta(S_{i})$ to denote the set of mixed strategies, and
$X_{i}:=\prod_{\theta_{i}\in\Theta_{i}}\Delta(A_{i})$ to denote the set of
behaviour strategies.

A normal-form correlated equilibrium (also known as strategic-form correlated
equilibrium) is a joint distribution $\mu\in\Delta(S)$ over the strategy
space, such that no player can gain from deviating from the recommend
strategy. Formally

######  Definition 2.1 (Normal-form correlated equilibrium).

A distribution $\mu\in\Delta(S)$ is a normal-form correlated equilibrium if
for every player $i\in[m]$ and all swap function $\phi:S_{i}\rightarrow
S_{i}$,

$\displaystyle\mathbb{E}_{\theta\sim\rho}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;s(\theta))]\geq\mathbb{E}_{\theta\sim\rho}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;\phi(s_{i})(\theta_{i}),s_{-i}(\theta_{-i}))].$

A Bayesian Nash equilibrium (BNE) is the special case of NFCE where $\mu$ is a
product distribution, i.e. each player samples their action independently.
More generally, we consider low-rank distributions that interpolate between a
product distribution (rank 1) and general correlated distribution (unbounded
rank).

Two natural ways of extending NFCE and BNE to approximate equilibrium have
been considered in the literature; the differences are subtle but important
for our purpose. The first notion of approximate equilibrium, which we call
ex-ante-approximate, considers the potential benefit for a player from
deviating from the recommended strategy in expectation over the Bayesian prior
over types. The second, stricter notion, which we call every-type-approximate
considers the potential benefit for a player from deviating – maximized over
her types and in expectation over all other players’ types. This distinction
is similar (but orthogonal) to approximate Nash equilibrium and well-supported
Nash equilibrium in normal-form games (e.g. [DGP09]).

######  Definition 2.2 (Notions of approximate equilibria).

  * •

We say that a distribution $\mu$ is an (ex-ante-$\epsilon$)-NFCE (or (ex-
ante-$\epsilon$)-BNE when $\mu$ is a product distribution) if for every player
$i\in[m]$ and every swap function $\phi:S_{i}\rightarrow S_{i}$,

$\displaystyle\mathbb{E}_{\theta\sim\rho}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;s(\theta))]\geq\mathbb{E}_{\theta\sim\rho}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;\phi(s_{i})(\theta_{i}),s_{-i}(\theta_{-i}))]-\epsilon.$

  * •

We say that a distribution $\mu$ is an (every-type-$\epsilon$)-NFCE (or
(every-type-$\epsilon$)-BNE when $\mu$ is a product distribution) if for every
player $i\in[m]$, every swap function $\phi:S_{i}\rightarrow S_{i}$, and for
every type $k\in\Theta_{i}$,

$\mathbb{E}_{\theta_{-i}\sim(\rho|\theta_{i}=k)}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;s(\theta))]\geq\mathbb{E}_{\theta_{-i}\sim(\rho|\theta_{i}=k)}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;\phi(s_{i})(\theta_{i}),s_{-i}(\theta_{-i}))]-\epsilon.$

Our algorithm for Bayesian games gives an every-type-approximate NFCE, which
is another improvement over [DGZ23, PR24] that compute ex-ante-approximate
NFCE. Meanwhile, our hardness for extensive-form games holds also with respect
to the more lenient notion of ex-ante approximation. A detailed discussions on
different notions of correlated equilibrium in Bayesian games can be found at
[Fuj23].

###  2.2 Extensive-form game

The extensive-form game extends Bayesian game by incorporating both incomplete
information and sequentiality. An $m$-player extensive-form game can be
formulated as a directed game tree $\Gamma$. Let $\mathcal{N}$ be all nodes of
$\Gamma$, the nodes of the game tree are partitioned into decision nodes and
chance nodes
$\mathcal{N}=\mathcal{N}_{1}\cup\cdots\mathcal{N}_{m}\cup\mathcal{N}_{c}$.
Here $\mathcal{N}_{i}$ ($i\in[m]$) is the set of nodes where player $i$ takes
actions and $\mathcal{N}_{c}$ are chance nodes. The function of a chance node
is to assign an outcome of a chance event, and each outgoing edge represents
one possible outcome of that chance event as well as the probability of the
event. At a decision node, the edges represent actions and the successor
states the result from the player taking those actions. Player $i$’s decision
nodes $\mathcal{N}_{i}$ are further partitioned into a family
$\mathcal{I}_{i}$ of information sets; for each information set
$I\in\mathcal{I}_{i}$, Player $i$ chooses an action from $A_{i}$. We consider
perfect recall extensive-form games so that each player remembers the history
action sequence leads to each information set. We use
$|\mathcal{I}|=\sum_{i\in[m]}|\mathcal{I}_{i}|$ to denote the total number of
information sets. Let
$S^{\mathsf{EFG}}_{i}=\prod_{I\in\mathcal{I}_{i}}A_{i}=(A_{i})^{\mathcal{I}_{i}}$
be the set of pure strategies of player $i$, and the entire strategy space is
$S^{\mathsf{EFG}}=\prod_{i\in[m]}S^{\mathsf{EFG}}_{i}$.

Let $\Delta(S^{\mathsf{EFG}}_{i})$ be the set of mixed strategies. Note that
this notion of mixed strategies is very general in that it allows a player to
correlate their actions across information sets that cannot simultaneously
occur in the same play of the game. We also consider a slightly more
restricted notion of behaviour strategies that do not account for such
correlations; formally the set of Player $i$’s behaviour strategies is given
by $X^{\mathsf{EFG}}_{i}=\prod_{I\in\mathcal{I}_{i}}\Delta(A_{i})$. Given a
strategy distribution $\mu\in\Delta(S^{\mathsf{EFG}})$, we use
$u_{i}(\mu)\in[0,1]$ to denote the expected utility of player $i$ under $\mu$.

In a coarse correlated equilibrium, no player can gain by switching to another
fixed strategy888This definition is also known as normal-form coarse
correlated equilibrium (NFCCE) in the literature.

######  Definition 2.3 (Coarse correlated equilibrium).

Let $\epsilon>0$, a distribution $\mu\in\Delta(S^{\mathsf{EFG}})$ is an
$\epsilon$-approximate coarse correlated equilibrium ($\epsilon$-CCE) of an
extensive-form game, if for all player $i\in[m]$ and strategy $s_{i}\in
S^{\mathsf{EFG}}_{i}$,

$u_{i}(\mu)\geq u_{i}(s_{i},\mu_{-i})-\epsilon.$

######  Remark 2.4 (Mixed strategy, behaviour strategy and rank).

In the literature of Bayesian and extensive-form game, a mixed strategy places
a distribution over the set of pure strategies, while a behaviour strategy
places a distribution over the action set at each information set. The Kuhn’s
Theorem [Kuh53], a fundamental result of imperfect information game, states
that the behaviour strategy is equivalent to the mixed strategy, in the sense
that for any mixed strategy $p_{i}\in\Delta(S^{\mathsf{EFG}}_{i})$, one can
find a behaviour strategy $x_{i}\in\prod_{\mathcal{I}_{i}}\Delta(A_{i})$, such
that the probability of reaching any terminal node is the same. This means
that:

  * •

CCE <-> behaviour strategies: When considering the rank of a coarse correlated
equilibrium, it suffices to define the rank with respect to behaviour strategy
– one can always replace a mixed strategy with a behaviour strategy and the
utility remains the same999This notion of rank/sparsity is used in the
previous work of [FGK23, AKSZ24]..

  * •

CE <-> mixed strategies: Meanwhile, when considering decentralized learning of
correlated equilibrium, we should still stick with mixed strategies. The
reason is that, after replacing a mixed strategy with a behaviour strategy,
even though the utility received by each agent is the same, the hypothetical
utility after swapping the strategy is not the same! See Appendix A for an
example.

Formally, we define the rank of a joint distribution as follows.

######  Definition 2.5 (Rank).

Let $\mu\in\Delta(S^{\mathsf{EFG}})$ be a joint distribution. When considering
CE, we say $\mu$ is of rank $T$, if it can be written as
$\mu=\frac{1}{T}\sum_{t=1}^{T}\bigotimes_{i\in[m]}p_{i}^{(t)}$ where
$p_{i}^{(t)}\in\Delta(S_{i})$ is a mixed strategy; When considering CCE, we
say $\mu$ is of rank $T$ if it can be written as
$\mu=\frac{1}{T}\sum_{t=1}^{T}\bigotimes_{i\in[m]}x_{i}^{(t)}$, where
$x_{i}^{(t)}\in X_{i}^{\mathsf{EFG}}$ is a behaviour strategy.

Note we define the rank of a distribution as the number of uniform mixture of
product distributions. This is wlog – if the distribution can be written as
$k$ non-uniform mixture of production distributions, then one can approximate
it with $O(k)$ uniform mixture.

###  2.3 Useful tools

##### No-regret learning

We make use of the classic algorithm of Multiplicative Weights Update (MWU)
for regret minimization [LW94].

Algorithm 1 MWU

1:Input parameters $T$ (number of rounds), $n$ (number of actions), $B$ (bound
on payoff)

2:for $t=1,2,\ldots,T$ do

3: Compute $p_{t}\in\Delta_{n}$ over experts such that
$p_{t}(i)\propto\exp(\eta\sum_{\tau=1}^{t-1}r_{\tau}(i))$ for $i\in[n]$

4: Play $p_{t}$ and observes $r_{t}\in[0,B]^{n}$

5:end for

######  Lemma 2.6 ([AHK12]).

Let $n,T\geq 1$ and the reward $r_{t}\in[0,B]^{n}$ ($t\in[T]$). If one takes
$\eta=\sqrt{\log(n)/T}/B$, then the MWU algorithm guarantees an external
regret of at most

$\displaystyle\max_{i^{*}\in[n]}\sum_{t\in[T]}r_{t}(i^{*})-\sum_{t\in[T]}\langle
p_{t},r_{t}\rangle\leq\frac{\log(n)}{\eta}+\eta TB^{2}\leq 2B\sqrt{T\log(n)}.$

##### Online density estimation

We make use of the online density estimation algorithm [Vov90]. In the task of
online density estimation, there is a set of outcomes $O$ and a set of
possible contexts $C$. The task proceeds in $H$ rounds, and at each round
$h\in[H]$,

  * •

Nature first reveals a context $c_{h}\in C$

  * •

The learner predicts a distribution $p_{h}\in\Delta(O)$ over outcomes based on
the context $c_{h}$; and

  * •

Nature chooses an outcome $o_{h}\in O$

The learner has access to a set of experts $\\{p^{(i)}\\}_{i\in[n]}$, where
each expert is a fixed function from context to distribution of outcome. That
is, for any context $c\in C$, $p^{(i)}_{c}\in\Delta(O)$ is a distribution of
outcome, and $p^{(i)}_{c}(o)$ is the probability of outcome $o\in O$. Vovk’s
algorithm (see Algorithm 2) places a distribution over experts at each round,
by running MWU over the logarithmic loss function.

Algorithm 2 Vovk’s aggregating algorithm

1:for $h=1,2,\ldots,H$ do

2: Observe the context $c_{h}$

3: Compute a distribution $q_{h}\in\Delta_{n}$ over experts $[n]$
$q_{h}(i)=\frac{\exp\left(-\sum_{\nu=1}^{h-1}\log\left(\frac{1}{p^{(i)}_{c_{\nu}}(o_{\nu})}\right)\right)}{\sum_{i^{\prime}\in[n]}\exp\left(-\sum_{\nu=1}^{h-1}\log\left(\frac{1}{p^{(i^{\prime})}_{c_{\nu}}(o_{\nu})}\right)\right)}\quad\forall
i\in[n]$

4: Aggregate predictions from experts $p_{h}=\mathbb{E}_{i\sim
q_{h}}[p^{(i)}_{c_{h}}]\in\Delta(O)$ and observe the outcome $o_{h}\in O$

5:end for

######  Lemma 2.7 ([Vov90]).

Suppose the distribution of outcomes is realizable under the set of expert
$[n]$, i.e., there exists $i^{*}\in[n]$ such that $o_{h}\sim
p^{(i^{*})}_{c_{h}}$ for each $h\in[H]$. Then Vovk’s aggregating rule
(Algorithm 2) satisfies

$\displaystyle\frac{1}{H}\sum_{h=1}^{H}\mathbb{E}[\mathsf{TV}(p_{h};p^{(i^{*})}_{c_{h}})]\leq\sqrt{\frac{\log(n)}{H}}.$

##### The complexity of Bayesian Nash equilibrium

We make use of the following hardness result of BNE.

######  Theorem 2.8 ([Rub18]).

It is PPAD-hard to find an (every-type-$\epsilon$)-BNE of a two-player,
$n$-type, $2$-action Bayesian game for some absolute constant $\epsilon>0$.

##  3 Lower bound for extensive-form game

Theorem 1.1 is a direct corollary of the following hardness result on
computing low rank CCE.

######  Theorem 3.1.

Let $\epsilon>0$ be an absolute constant. Assuming
$\PPAD\not\subset\TIME(n^{\polylog(n)})$, there is no polynomial time
algorithm that can find a rank-$2^{\log_{2}^{1-o(1)}(|\mathcal{I}|)}$
$\epsilon$-CCE of a three player extensive-form game.

###  3.1 Construction

We reduce (every-type-$\epsilon$)-BNE to low rank CCE of extensive-form game.
Given a two-player Bayesian game $\mathcal{G}$, with type space
$\Theta=\Theta_{1}\times\Theta_{2}$, action space $A=A_{1}\times A_{2}$ and
prior distribution $\rho$, we construct a three-player extensive-form game
$\Gamma$.

##### Gadget

We first construct a three-player extensive-form game gadget that incorporates
the Bayesian game. Among the first two players, we use $i\in[2]$ to represent
a player and we use $i^{\prime}$ to denote the other player than $i$, i.e.,
$i^{\prime}=3-i\in[2]$. We use the special symbol $\K=3$ to represent the
third player Kibitzer.

The extensive-form game proceeds as follows. Kibitzer first picks a player
$i\in[2]$, a type $\theta_{i}\in\Theta_{i}$ as well as an action
$\widetilde{a}_{i}\in A_{i}$, that is, the action set $A_{\K}$ is defined as

$A_{\K}=\\{(i,\theta_{i},\widetilde{a}_{i}),i\in[2],\theta_{i}\in\Theta_{i},\widetilde{a}_{i}\in
A_{i}\\}.$

Nature then samples $\theta_{i^{\prime}}$ from $\rho$ conditioning on
$\theta_{i}$. Then player $i$ (resp. $i^{\prime}$) observes its private type
$\theta_{i}$ (resp. $\theta_{i^{\prime}}$) and plays action $a_{i}$ (resp.
$a_{i^{\prime}}$). We use $O=A_{1}\times A_{2}\times
A_{\K}\times\Theta_{1}\times\Theta_{2}$ to denote the outcome space of the
gadget.

When Kibitzer plays $a_{\K}=(1,\theta_{1},\widetilde{a}_{1})$, then the
utility of player $j\in[3]$ equals

$\displaystyle
u_{j}(a_{1},a_{2},a_{\K},\theta_{1},\theta_{2})=\left\\{\begin{matrix}u_{1}(\theta_{1},\theta_{2};a_{1},a_{2})-u_{1}(\theta_{1},\theta_{2};\widetilde{a}_{1},a_{2})&j=1\\\
0&j=2\\\
u_{1}(\theta_{1},\theta_{2};\widetilde{a}_{1},a_{2})-u_{1}(\theta_{1},\theta_{2};a_{1},a_{2})&j=K\\\
\end{matrix}\right..$ (1)

When Kibitzer plays $a_{\K}=(2,\theta_{2},\widetilde{a}_{2})$, the utility of
player $j\in[3]$ is defined similarly

$\displaystyle
u_{j}(a_{1},a_{2},a_{\K},\theta_{1},\theta_{2})=\left\\{\begin{matrix}0&j=1\\\
u_{2}(\theta_{1},\theta_{2};a_{1},a_{2})-u_{2}(\theta_{1},\theta_{2};a_{1},\widetilde{a}_{2})&j=2\\\
u_{2}(\theta_{1},\theta_{2};a_{1},\widetilde{a}_{2})-u_{2}(\theta_{1},\theta_{2};a_{1},a_{2})&j=K\\\
\end{matrix}\right..$ (2)

##### Final construction

Let $T$ be the rank of the CCE. The final extensive-form game $\Gamma$ is
constructed by repeating the gadget for $H\geq\frac{\log(T)}{\epsilon^{2}}$
times. For each repetition $h\in[H]$, let $N_{h}$ be the collection of gadgets
at the $h$-th repetition, corresponding to different paths of play in earlier
repetition. For any gadget $n_{h}\in N_{h}$, let
$o_{h}=(a_{1,h},a_{2,h},a_{\K,h},\theta_{1,h},\theta_{2,h})\in O$ be the
outcome of the $h$-th repetition. The utility of each of the three players is
determined by the average over the gadget utilities defined Eq. (1)(2),
averaged across the $H$ repetitions; we denote them as
$(u_{j,n_{h}})_{j\in[3]}$.

##### Notation

A gadget $n_{h}\in N_{h}$ is uniquely determined by its history
$\sigma(n_{h})=(n_{1},o_{1},\ldots,n_{h-1},o_{h-1})$, where $n_{\tau}\in
N_{\tau}$ ($\tau\in[h-1]$) is the gadget at the root path to $n_{h}$ and
$o_{\tau}$ is the outcome at $n_{\tau}$. We use $S^{\mathsf{EFG}}_{j}$ to
denote the strategy space of player $j\in[3]$ in the extensive-form game
$\Gamma$, and $S_{i}$ to denote the strategy space of player $i\in[2]$ in the
Bayesian game $\mathcal{G}$. For player $i\in[2]$, we have
$S^{\mathsf{EFG}}_{i}=\prod_{h\in[H]}\prod_{n_{h}\in N_{h}}S_{i}$ and
$X_{i}^{\mathsf{EFG}}=\prod_{h\in[H]}\prod_{n_{h}\in N_{h}}X_{i}$, i.e., the
pure/behaviour strategy space is the product of pure/behaviour strategy space
at each gadget. Given a behaviour strategy $x_{i}\in X_{i}^{\mathsf{EFG}}$,
for any gadget $n_{h}\in N_{h}$, we write $x_{i,n_{h}}\in X_{i}$ to denote the
behaviour strategy of $x_{i}$ on $n_{h}$, i.e., $x_{i,n_{h}}$ is the marginal
distribution of $x_{i}$ on $n_{h}$. For player $\K$, we have
$S^{\mathsf{EFG}}_{\K}=\prod_{h\in[H]}\prod_{n_{h}\in N_{h}}A_{\K}$,
$X_{\K}^{\mathsf{EFG}}=\prod_{h\in[H]}\prod_{n_{h}\in N_{h}}\Delta(A_{\K})$,
and we define $x_{\K,n_{h}}\in\Delta(A_{\K})$ similarly.

Given a rank-$T$ $\epsilon$-CCE $\mu$ of the extensive-form game $\Gamma$, we
write

$\displaystyle\mu=\sum_{t\in[T]}x^{(t)}=\sum_{t\in[T]}x_{1}^{(t)}\otimes
x_{2}^{(t)}\otimes x_{\K}^{(t)},$

where $x_{j}^{(t)}\in X_{j}^{\mathsf{EFG}}$ ($j\in[3]$) is a behaviour
strategy of player $j$.

###  3.2 Analysis of players 1,2

We first prove that at any approximate CCE, the utilities of the first two
players are not far below zero. To this end, for player $i\in[2]$, we consider
the deviation strategy $x_{i}^{\dagger}\in S^{\mathsf{EFG}}_{i}$, whose
construction is shown at Algorithm 3. For any product distribution $t\in[T]$,
player $i\in[2]$, let $x_{-i}^{(t)}=x^{(t)}_{i^{\prime}}\times x^{(t)}_{\K}$.
Let $O_{-i}=A_{i^{\prime}}\times A_{\K}\times\Theta_{1}\times\Theta_{2}$ be
the outcome space of player $\K$, player $i^{\prime}$ and the chance player.
For any gadget $n_{h}\in N_{h}$, let $x_{-i,n_{h}}^{(t)}\in\Delta(O_{-i})$ be
the distribution of outcome (except player $i$) at gadget $n_{h}$ under
strategy $x_{-i}^{(t)}$.

Algorithm 3 Deviation strategy of player $1,2$ $\triangleright$ Analysis only

1:Input: rank-$T$ $\epsilon$-CCE
$\mu=\frac{1}{T}\sum_{t\in[T]}x_{1}^{(t)}\otimes x_{2}^{(t)}\otimes
x_{\K}^{(t)}$, $i\in[2]$

2:for $h=1,2,\ldots,H$ do $\triangleright$ repetition $h\in[H]$

3: for $n_{h}\in N_{h}$ do $\triangleright$ gadget $n_{h}$

4: $\sigma(n_{h})=(n_{1},o_{1},\ldots,n_{h-1},o_{h-1})$ $\triangleright$
history of $n_{h}$

5: Compute a distribution $q_{i,n_{h}}\in\Delta(T)$ over $[T]$
$\triangleright$ Vovk’s rule
$q_{-i,n_{h}}(t)=\frac{\exp\left(-\sum_{\nu=1}^{h-1}\log\left(\frac{1}{x_{-i,n_{v}}^{(t)}(o_{-i,\nu})}\right)\right)}{\sum_{t^{\prime}\in[T]}\exp\left(-\sum_{\nu=1}^{h-1}\log\left(\frac{1}{x_{-i,n_{v}}^{(t^{\prime})}(o_{-i,\nu})}\right)\right)}\quad
t\in[T]$

6: Compute $p_{-i,n_{h}}=\mathbb{E}_{t\sim
q_{-i,n_{h}}}[x_{-i,n_{h}}^{(t)}]\in\Delta(O_{-i})$ $\triangleright$ predicted
outcome

7: Define the deviation strategy $x^{\dagger}_{i,n_{h}}\in S_{i}$ at gadget
$n_{h}$ $\displaystyle x_{i,n_{h}}^{\dagger}=$
$\displaystyle~{}\operatorname*{arg\,max}_{s_{i}\in
S_{i}}\mathbb{E}_{(a_{i^{\prime}},a_{\K},\theta_{1},\theta_{2})\sim
p_{-i,n_{h}}}[u_{i,n_{h}}(s_{i}(\theta_{i}),a_{i^{\prime}},a_{\K},\theta_{1},\theta_{2})]$

8: end for

9:end for

First, we prove

######  Lemma 3.2.

For player $i\in[2]$, product distribution $t\in[T]$, we have

$\displaystyle\frac{1}{H}\sum_{h\in[H]}\mathbb{E}_{x_{i}^{\dagger}\times
x_{-i}^{(t)}}\left[\mathsf{TV}(p_{-i,n_{h}};x_{-i,n_{h}}^{(t)})\right]\leq\sqrt{\frac{\log(T)}{H}}.$

Here $n_{1},n_{2},\ldots,n_{H}$ is the (random) sequence of gadgets visited
under strategy $x_{i}^{\dagger}\times x_{-i}^{(t)}$.

###### Proof.

Consider the following online density estimation procedure. The outcome space
is $O_{-i}$, the set of experts are $T$ strategies
$\\{x_{-i,n_{h}}^{(t)}\\}_{t\in[T]}$, the context comes from the set of
gadgets $\cup_{h\in[H]}N_{h}$. At each round $h\in[H]$,

  * •

Nature provides the context $n_{h}$

  * •

The algorithm predicts the distribution $p_{-i,n_{h}}\in\Delta(O_{-i})$ over
outcome space $O_{-i}$;

  * •

Nature reveals the outcome
$o_{-i,h}=(a_{i^{\prime}},a_{\K},\theta_{1},\theta_{2})\sim
x_{-i,n_{h}}^{(t)}$.

  * •

The next context $n_{h+1}=n_{h}|(o_{-i,h},x_{i}^{\dagger}(\theta_{i}))$

By Lemma 2.7, we have

$\displaystyle\frac{1}{H}\sum_{h=1}^{H}\mathbb{E}_{x_{i}^{\dagger}\times
x_{-i}^{(t)}}\left[\mathsf{TV}(p_{-i,n_{h}};x_{-i,n_{h}}^{(t)})\right]\leq\sqrt{\frac{\log(T)}{H}}.$

∎

Now we can bound the utility of the first two players at $\epsilon$-CCE.

######  Lemma 3.3 (Equilibrium utility).

The utility at $\epsilon$-CCE of player $i\in[2]$ satisfies
$u_{i}(\mu)\geq-5\epsilon$.

###### Proof.

For any player $i\in[2]$, production distribution $t\in[T]$, gadget $n_{h}\in
N_{h}$, define

$s^{(t)}_{i,n_{h}}=\operatorname*{arg\,max}_{s_{i}\in
S_{i}}\mathbb{E}_{(a_{i^{\prime}},a_{\K},\theta_{1},\theta_{2})\sim
x_{-i,n_{h}}^{(t)}}u_{i,n_{h}}(s_{i}(\theta_{i}),a_{i^{\prime}},a_{\K},\theta_{1},\theta_{2}).$

That is $s^{(t)}_{i,n_{h}}\in S_{i}$ is the best strategy of player $i$, given
that the other players use strategies $x_{i^{\prime},n_{h}}^{(t)}\times
x_{\K,n_{h}}^{(t)}$. We claim that

$\displaystyle u_{i,n_{h}}(s^{(t)}_{i,n_{h}},x^{(t)}_{-i,n_{h}})\geq 0.$ (3)

This is because player $i$ can always best-respond to
$x_{i^{\prime},n_{h}}^{(t)}$ in the Bayesian game, and the strategy
$x_{\K,n_{h}}^{(t)}$ of Kibitzer is independent of $x_{i^{\prime}}^{(t)}$ so
it cannot find a better action.

Now we compute its utility under deviation $x_{i}^{\dagger}$. For any
$t\in[T]$, gadget $n_{h}\in N_{h}$, we have

$\displaystyle~{}u_{i,n_{h}}(x_{i,n_{h}}^{\dagger},x_{-i,n_{h}}^{(t)})$
$\displaystyle=$
$\displaystyle~{}u_{i,n_{h}}(x_{i,n_{h}}^{\dagger},x_{-i,n_{h}}^{(t)})-u_{i,n_{h}}(x_{i,n_{h}}^{\dagger},p_{-i,n_{h}})+u_{i,n_{h}}(x_{i,n_{h}}^{\dagger},p_{-i,n_{h}})-u_{i,n_{h}}(s_{i,n_{h}}^{(t)},p_{-i,n_{h}})$
$\displaystyle~{}+u_{i,n_{h}}(s_{i,n_{h}}^{(t)},p_{-i,n_{h}})-u_{i,n_{h}}(s_{i,n_{h}}^{(t)},x_{-i,n_{h}}^{(t)})+u_{i,n_{h}}(s_{i,n_{h}}^{(t)},x_{-i,n_{h}}^{(t)})$
$\displaystyle\geq$
$\displaystyle~{}-\frac{2}{H}\mathsf{TV}(p_{-i,n_{h}};x_{-i,n_{t}}^{(t)})+0-\frac{2}{H}\mathsf{TV}(p_{-i,n_{h}};x_{-i,n_{t}}^{(t)})+u_{i,n_{h}}(s_{i,n_{h}}^{(t)},x_{-i,n_{h}}^{(t)})$
$\displaystyle\geq$
$\displaystyle~{}-\frac{4}{H}\mathsf{TV}(p_{-i,n_{h}};x_{-i,n_{t}}^{(t)}).$
(4)

The second step follows from (i) the value of $u_{i,n_{h}}$ is between
$[-\frac{1}{H},\frac{1}{H}]$ and (ii) $x_{i,n_{h}}^{\dagger}$ is the best
response under $p_{-i,n_{h}}$. The third step follows from Eq. (3).

Taking an expectation, we have

$\displaystyle u_{i}(x_{i}^{\dagger},x_{-i}^{(t)})=$
$\displaystyle~{}\sum_{h=1}^{H}\mathbb{E}_{x_{i}^{\dagger}\times
x_{-i}^{(t)}}\left[u_{i,n_{h}}(x_{i,n_{h}}^{\dagger},x_{-i,n_{h}}^{(t)})\right]$
$\displaystyle\geq$
$\displaystyle~{}-\frac{4}{H}\sum_{h=1}^{H}\mathbb{E}_{x_{i}^{\dagger}\times
x_{-i}^{(t)}}\left[\mathsf{TV}(p_{-i,n_{h}};x_{-i,n_{h}}^{(t)})\right]$
$\displaystyle\geq$
$\displaystyle~{}-4\sqrt{\frac{\log(T)}{H}}\geq-4\epsilon.$

Here the second step follows from Eq. (4), the third step follows from Lemma
3.2.

Taking an expectation over $t\sim[T]$, we have

$\displaystyle
u_{i}(x_{i}^{\dagger},\mu_{-i})=\frac{1}{T}\sum_{t\in[T]}u_{i}(x_{i}^{\dagger},x_{-i}^{(t)})\geq-4\epsilon.$

Note $\mu$ is an $\epsilon$-CCE, we have $u_{i}(\mu)\geq-5\epsilon$ ∎

A direct corollary of Lemma 3.3 is that the utility of player $\K$ at
$\epsilon$-CCE is not much above $0$.

######  Lemma 3.4.

The utility at $\epsilon$-CCE of player $\K$ satisfies $u_{\K}(\mu)\leq
10\epsilon$.

###### Proof.

The utility of three players sums to $0$. By Lemma 3.3, we have that

$u_{\K}(\mu)=-u_{1}(\mu)-u_{2}(\mu)\leq 10\epsilon.\qed$

###  3.3 Reduction

The reduction is formally presented at Algorithm 4, using some of the
following notation. Let $O_{-\K}=A_{1}\times
A_{2}\times(\Theta_{1}\cup\Theta_{2})$ be the outcome space of player $1,2$
and the chance player. For any $t\in[T]$, let $x_{-\K}^{(t)}=x^{(t)}_{1}\times
x^{(t)}_{2}$. For any gadget $n_{h}\in N_{h}$ and action
$a_{\K}=(i,\theta_{i},\widetilde{a}_{i})\in A_{\K}$, let
$x_{-\K,n_{h},a_{\K}}^{(t)}\in\Delta(O_{-\K})$ be the distribution of outcomes
(except player $\K$) at gadgets $n_{h}$, given that player $\K$ plays $a_{\K}$
and players $1,2$ use (mixed) strategy profile $x_{1,n_{1}}^{(t)}\times
x_{2,n_{2}}^{(t)}$.

Algorithm 4 Reduction

1:Input: rank-$T$ $\epsilon$-CCE
$\mu=\frac{1}{T}\sum_{t\in[T]}x_{1}^{(t)}\otimes x_{2}^{(t)}\otimes
x_{\K}^{(t)}$

2:for $h=1,2,\ldots,H$ do$\triangleright$ repetition $h$

3: for $n_{h}\in N_{h}$ do $\triangleright$ gadget $n_{h}$

4: $\sigma(n_{h})=(n_{1},o_{1},\ldots,n_{h-1},o_{h-1})$ $\triangleright$
history of $n_{h}$

5: Compute a distribution $q_{-\K,n_{h}}\in\Delta(T)$ over $[T]$
$q_{-\K,n_{h}}(t)=\frac{\exp\left(-\sum_{\nu=1}^{h-1}\log\left(\frac{1}{x_{-\K,n_{v},a_{\K,\nu}}^{(t)}(o_{-\K,\nu})}\right)\right)}{\sum_{t^{\prime}\in[T]}\exp\left(-\sum_{\nu=1}^{h-1}\log\left(\frac{1}{x_{-\K,n_{v},a_{\K,\nu}}^{(t^{\prime})}(o_{-\K,\nu})}\right)\right)}\quad\forall
t\in[T]$

6: Compute $p_{i,n_{h}}=\mathbb{E}_{t\sim
q_{-\K,n_{h}}}[x_{i,n_{h}}^{(t)}]\in\Delta(S_{i})$ for $i=1,2$

7: if $(p_{1,n_{h}},p_{2,n_{h}})$ is an (every-type-$16\epsilon$)-BNE then

8: return $(p_{1,n_{h}},p_{2,n_{h}})$

9: else

10: Choose $a_{\K,n_{h}}^{\dagger}=(i,\theta_{i},\widetilde{a}_{i})\in A_{\K}$
such that
$\mathbb{E}_{\theta_{i^{\prime}}\sim\rho|\theta_{i}}\mathbb{E}_{s_{i}\sim
p_{i,n_{h}}}\mathbb{E}_{s_{i^{\prime}}\sim
p_{i^{\prime},n_{h}}}[u_{i}(\theta_{i},\theta_{i^{\prime}};\widetilde{a}_{i},s_{i^{\prime}}(\theta_{i^{\prime}}))-u_{i}(\theta_{i},\theta_{i^{\prime}};s_{i}(\theta_{i}),s_{i^{\prime}}(\theta_{i^{\prime}}))]\geq
16\epsilon.$

11: end if

12: end for

13:end for

For any node $n_{h}\in N_{h}$, $a_{\K}=(i,\theta_{i},\widetilde{a}_{i})\in
A_{\K}$, define $p_{-\K,n_{h},a_{\K}}\in\Delta(\Theta_{i^{\prime}}\times
A_{1}\times A_{2})$ such that

$p_{-\K,n_{h},a_{\K}}(\theta_{i^{\prime}},a_{i},a_{i^{\prime}})=\Pr_{\hat{\theta}_{i^{\prime}}\sim\rho|\theta_{i}}[\hat{\theta}_{i^{\prime}}=\theta_{i^{\prime}}]\cdot\Pr_{s_{i}\sim
p_{i,n_{h}}}[a_{i}=s_{i}(\theta_{i})]\cdot\Pr_{s_{i^{\prime}}\sim
p_{i^{\prime},n_{h}}}[a_{i^{\prime}}=s_{i^{\prime}}(\theta_{i^{\prime}})]$

That is, it first samples $\theta_{i^{\prime}}\sim\rho|\theta_{i}$, then it
independently samples strategies $s_{i},s_{i^{\prime}}$ from
$p_{i,n_{h}},p_{i^{\prime},n_{h}}$ (respectively), and finally takes
$a_{i}=s_{i}(\theta_{i}),a_{i^{\prime}}=s_{i^{\prime}}(\theta_{i^{\prime}})$.
For $i\in[2]$, $\theta_{i}\in\Theta_{i}$, we further define
$p_{i,n_{h},\theta_{i}}\in\Delta(A_{i})$ such that
$p_{i,n_{h},\theta_{i}}(a_{i})=\mathbb{E}_{s_{i}\sim
p_{i,n_{h}}}[s_{i}(\theta_{i})]$.

Our goal is to prove, if Algorithm 4 doesn’t find an approximate BNE, then
Kibitzer has a good deviation strategy $x_{\K}^{\dagger}$. First, we prove
Kibitzer approximately learns the outcome distribution.

######  Lemma 3.5.

Suppose Algorithm 4 does not find an (every-type-$16\epsilon$)-BNE, i.e. the
if-statement in Line 7 is always false, For every $t\in[T]$, we have

$\displaystyle\frac{1}{H}\sum_{h\in[H]}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[\mathsf{TV}(p_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})\right]\leq
2\sqrt{\frac{\log(T)}{H}}.$

Here $n_{1},\ldots,n_{H}$ is the (random) sequence of gadgets visited under
$x_{\K}^{\dagger}\times x_{-\K}^{\dagger}$ and
$a_{\K,h}^{\dagger}=a_{\K,n_{h}}^{\dagger}$ is the action of player $\K$ at
gadget $n_{h}$.

###### Proof.

For any gadget $n_{h}\in N_{h}$, define

$w_{-\K,n_{h},a^{\dagger}_{\K,h}}=\mathbb{E}_{t^{\prime}\sim
q_{-\K,n_{h}}}\left[x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t^{\prime})}\right]\in\Delta(O_{-\K}).$

We first bound the (expected) TV distance between
$w_{-\K,n_{h},a_{\K,h}^{\dagger}}$ and
$x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)}$. Consider the following online
density estimation procedure. The outcome space is $O_{-\K}$, the set of
experts are $T$ indices $\\{x_{-\K}^{(t)}\\}_{t\in[T]}$ , and the context
comes from $\cup_{h\in[H]}N_{h}\times A_{\K}$. At round $h\in[H]$,

  * •

Nature provides the context $(n_{h},a_{\K,h}^{\dagger})$;

  * •

The algorithm predicts $w_{-\K,n_{h},a_{\K,h}^{\dagger}}\in\Delta(O_{-\K})$;

  * •

Nature samples the outcome $o_{-\K,h}\sim
x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)}$;

  * •

The next context $n_{h+1}=n_{h}|(a_{\K,h}^{\dagger},o_{-\K,h})$ and
$a_{\K,h+1}^{\dagger}=a_{\K,n_{h+1}}^{\dagger}$

By the guarantee of Lemma 2.7, we have

$\displaystyle\frac{1}{H}\sum_{h\in[H]}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[\mathsf{TV}(w_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})\right]\leq\sqrt{\frac{\log(T)}{H}}.$
(5)

Now consider the three distributions
$p_{-\K,n_{h},a_{\K,h}^{\dagger}},w_{-\K,n_{h},a_{\K,h}^{\dagger}},x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)}\in\Delta(\Theta_{i^{\prime}}\times
A_{1}\times A_{2})$. Intuitively, $x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)}$ is
the outcome under the product distribution $x_{-i}^{(t)}$;
$w_{-\K,n_{h},a_{\K,h}^{\dagger}}$ is the predicted outcome under Vovk’s
algorithm; $p_{-\K,n_{h},a_{\K,h}^{\dagger}}$ is the outcome after taking
marginal of $w_{-\K,n_{h},a_{\K,h}^{\dagger}}$. Formally, these three
distributions have the same marginal distribution on $\Theta_{i^{\prime}}$ due
to the independence of chance player. Conditioning on the first coordinates
being $\theta_{i^{\prime}}\in\Theta_{i^{\prime}}$

  * •

$x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)}|\theta_{i^{\prime}}=x_{1,n_{h},\theta_{1}}^{(t)}\times
x_{2,n_{h},\theta_{1}}^{(t)}\in\Delta(A_{1})\times\Delta(A_{2})$ is a product
distribution;

  * •

$p_{-\K,n_{h},a_{\K,h}^{\dagger}}|\theta_{i^{\prime}}=p_{1,n_{h},\theta_{1}}\times
p_{2,n_{h},\theta_{2}}\in\Delta(A_{1})\times\Delta(A_{2})$ is a product
distribution; while

  * •

$w_{-\K,n_{h},a_{\K,h}^{\dagger}}|\theta_{i^{\prime}}=\mathbb{E}_{t\sim
q_{-\K,n_{h}}}[x_{1,n_{h},\theta_{1}}^{(t)}\times
x_{2,n_{h},\theta_{2}}^{(t)}]\in\Delta(A_{1}\times A_{2})$ is a joint
distribution over $A_{1}\times A_{2}$

  * •

$p_{-K,n_{h},a_{K,h}^{\dagger}}|\theta_{i^{\prime}}$ and
$w_{-K,n_{h},a_{K,h}^{\dagger}}|\theta_{i^{\prime}}$ have the same marginal
distribution over $a_{1}\in A_{1}$ (resp. $a_{2}\in A_{2}$), because
$p_{1,n_{h},\theta_{1}}=\mathbb{E}_{t\sim
q_{-\K,n_{h}}}[x_{1,n_{h},\theta_{1}}^{(t)}]$ and
$p_{2,n_{h},\theta_{2}}=\mathbb{E}_{t\sim
q_{-\K,n_{h}}}[x_{2,n_{h},\theta_{2}}^{(t)}]$ (see Line 6 of Algorithm 4)

Then we have

$\displaystyle\mathsf{TV}(p_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a^{\dagger}_{\K,h}}^{(t)})=$
$\displaystyle~{}\mathbb{E}_{\theta_{i^{\prime}}\sim\rho|\theta_{i}}\left[\mathsf{TV}\left(p_{1,n_{h},\theta_{1}}\times
p_{2,n_{h},\theta_{2}}\;\;;\;\;x_{1,n_{h},\theta_{1}}^{(t)}\times
x_{2,n_{h},\theta_{2}}^{(t)}\right)\right]$ $\displaystyle\leq$
$\displaystyle~{}2\mathbb{E}_{\theta_{i^{\prime}}\sim\rho|\theta_{i}}\left[\mathsf{TV}\left(w_{-\K,n_{h},a_{\K,h}^{\dagger}}|\theta_{i^{\prime}}\;\;;\;\;x_{1,n_{h},\theta_{1}}^{(t)}\times
x_{2,n_{h},\theta_{2}}^{(t)}\right)\right]$ $\displaystyle=$
$\displaystyle~{}2\mathsf{TV}\left(w_{-\K,n_{h},a_{\K,h}^{\dagger}}\;\;;\;\;x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)}\right).$

Here the first step follows from Fact B.1, the second follows from Fact B.2
and the last step follows from Fact B.1.

Taking an expectation and combining with Eq. (5), we have

$\displaystyle~{}\frac{1}{H}\sum_{h\in[H]}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[\mathsf{TV}(p_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})\right]$
$\displaystyle\leq$
$\displaystyle~{}\frac{2}{H}\sum_{h\in[H]}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[\mathsf{TV}(w_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})\right]\leq
2\sqrt{\frac{\log(T)}{H}}.$

∎

Now we can prove the correctness of the reduction.

######  Lemma 3.6.

Algorithm 4 returns an (every-type-$16\epsilon$)-BNE.

###### Proof.

We prove by contradiction and assume Algorithm 4 never returns. We compute the
utility under deviation $x_{\K}^{\dagger}$. For any product distribution
$t\in[T]$, we have

$\displaystyle u_{\K}(x_{\K}^{\dagger},x_{-\K}^{(t)})=$
$\displaystyle~{}\sum_{h=1}^{H}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[u_{\K,n_{h}}(a_{\K,h}^{\dagger},x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})\right]$
$\displaystyle\geq$
$\displaystyle~{}\sum_{h=1}^{H}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[-\frac{2}{H}\mathsf{TV}(p_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})+u_{\K,n_{h}}(a_{\K,h}^{\dagger},p_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})\right]$
$\displaystyle\geq$
$\displaystyle~{}\sum_{h=1}^{H}\mathbb{E}_{x_{\K}^{\dagger}\times
x_{-\K}^{(t)}}\left[-\frac{2}{H}\mathsf{TV}(p_{-\K,n_{h},a_{\K,h}^{\dagger}};x_{-\K,n_{h},a_{\K,h}^{\dagger}}^{(t)})+\frac{16\epsilon}{H}\right]$
$\displaystyle\geq$ $\displaystyle~{}-4\sqrt{\frac{\log(T)}{H}}+16\epsilon\geq
12\epsilon.$

The second step holds since $u_{K,n_{h}}$ is between
$[-\frac{1}{H},\frac{1}{H}]$, the third step follows from the choice
$a_{\K,h}^{\dagger}$ (see Line 10 of Algorithm 4). The fourth step follows
from Lemma 3.5.

Taking an expectation over $t\sim[T]$, we have

$\displaystyle
u_{\K}(x_{\K}^{\dagger},\mu_{-\K})=\frac{1}{T}\sum_{t\in[T]}u_{i}(x_{\K}^{\dagger},x_{-\K}^{(t)})\geq
12\epsilon.$

Note $\mu$ is an $\epsilon$-CCE, we have $u_{\K}(\mu)\geq
u_{\K}(x_{\K}^{\dagger},\mu_{-\K})-\epsilon\geq 11\epsilon$. This contradicts
Lemma 3.4, hence, we have proved Algorithm 4 must return an (every-
type-$16\epsilon$)-BNE at some step. ∎

Now we can finish the proof of Theorem 3.1.

###### Proof of Theorem 3.1.

Let $\delta>0$ be the absolute constant in Theorem 2.8. We prove by
contradiction and assume that there exists a constant $\alpha>0$, such that
one can find an rank-$2^{\log_{2}^{1-\alpha}(|\mathcal{I}|)}$
$\frac{\delta}{16}$-CCE of a three-player extensive-form game with runtime
polynomial in $|\mathcal{I}|$. Given a two-player, $n$ types, two-action
Bayesian game $\mathcal{G}$, we construct the extensive-form game $\Gamma$
with $H=(\frac{\log_{2}(n)}{\delta^{2}})^{1/\alpha}$ repetitions. The number
of information sets at each gadget is $O(n^{2})$, and therefore, the total
number of information sets $|\mathcal{I}|=n^{O(H)}$. Moreover, the number of
repetition $H$ satisfies

$\frac{\log(2^{\log_{2}^{1-\alpha}(|\mathcal{I}|)})}{(\delta/16)^{2}}=O(\delta^{-2}\log_{2}^{1-\alpha}(|\mathcal{I}|))=O(H^{1-\alpha}\log_{2}^{1-\alpha}(n)\delta^{-2})\leq
H.$

Hence, by Lemma 3.6, one can find an (every-type-$\delta$)-BNE in time
$\poly(|\mathcal{I}|)=n^{O(H)}=n^{\polylog(n)}$, which, by Theorem 2.8
contradicts the assumption that $\PPAD\not\subset\TIME(n^{\polylog(n)})$. ∎

##  4 Efficient algorithm for Bayesian game

Our goal is to prove

######  Theorem 4.1 (Formal statement of Theorem 1.2).

Let $\epsilon>0$, for any $m$-player, $n$-action, $K$-type Bayesian game,
there exists uncoupled dynamics that converge to the set of (every-
type-$\epsilon$)-NFCE in $(\log(n)/\epsilon^{2})^{O(1/\epsilon)}$ iterations.
The computation cost at each iteration is
$O(mnK\log(mnK/\epsilon)/\epsilon^{3})$.

We have each player run the no-regret learning algorithm (shown in Algorithm
5) for a sequence of $T$ days. Algorithm 5 is an adaptation of the multi-scale
MWU [PR24] for Bayesian game. Given the regret parameter $\epsilon>0$, it sets
$H=\log(n)/\epsilon^{2}$, $L=1/\epsilon$ and runs for $T=H^{L}$ days. It
maintains $L$ threads and plays uniformly over them. The $L$ threads restart
and update in different frequency. The key innovation of Algorithm 5 is that
it runs MWU for each type $k\in[K]$ independently (see Procedure
$\textsc{MWU}_{\ell,k}$) and the strategy of the $\ell$-th thread is the
product strategy of each type (see Line 7). Concretely, for each type
$k\in[K]$, $\textsc{MWU}_{\ell,k}$ runs MWU and the reward vector is
constructed as the expected reward conditioning on type $k$ (see Line 17).

Algorithm 5 Multi-scale MWU for Bayesian game
$\triangleright$ No-regret learning algorithm for player $i\in[m]$, the
opponents play $\mu_{t}^{(-i)}\in\Delta(S_{-i})$ at day $t\in[T]$

1:Parameters $H=\log(n)/\epsilon^{2}$, $L=1/\epsilon$, $T=H^{L}$

2:Let $q_{t,\ell}\in(\Delta(A_{i}))^{\Theta_{i}}$ be the strategy of
$\textsc{Thread}_{\ell}$ ($\ell\in[L]$) at day $t\in[T]$

3:Play the uniform mixture
$p_{t}=\frac{1}{L}\sum_{\ell\in[L]}q_{t,\ell}\in\Delta(S_{i})$

4:

5:procedure $\textsc{Thread}_{\ell}$ $\triangleright$ Thread $\ell\in[L]$

6: Let $w_{t,\ell,k}\in\Delta(A_{i})$ be the strategy of
$\textsc{MWU}_{\ell,k}$ ($k\in[K]$) at day $t\in[T]$

7: Play the product distribution $q_{t,\ell}=w_{t,\ell,1}\times\cdots\times
w_{t,\ell,K}\in(\Delta(A_{i}))^{\Theta_{i}}$

8:end procedure

9:

10:procedure $\textsc{MWU}_{\ell,k}$ $\triangleright$ Thread $\ell\in[L]$,
type $k\in[K]$

11: for $\beta=1,2,\ldots,T/H^{\ell}$ do $\triangleright$ $\beta$-th restart,
restart every $H^{\ell}$ days

12: Initiate MWU with parameters $H,n,H^{\ell-1}$

13: for $h=1,2,\ldots,H$ do$\triangleright$ Round $h$

14: Let $z_{\beta,h,\ell,k}\in\Delta(A_{i})$ be the strategy of MWU at the
$h$-th round

15: Play $w_{t,\ell,k}=z_{\beta,h,\ell,j}$ at day
$t\in[(\beta-1)H^{\ell}+(h-1)H^{\ell-1}+1:(\beta-1)H^{\ell}+hH^{\ell-1}]$

16: Update MWU with the aggregated rewards of the past $H^{\ell-1}$ days
$\left\\{\sum_{t=(\beta-1)H^{\ell}+(h-1)H^{\ell-1}+1}^{(\beta-1)H^{\ell}+hH^{\ell-1}}r_{t,k}(j)\right\\}_{j\in[n]}\in[0,H^{\ell-1}]^{n}$

17: where
$r_{t,k}(j)=\mathbb{E}_{s_{-i}\sim\mu_{t}^{(-i)}}\mathbb{E}_{\theta_{-i}\sim(\rho|\theta_{i}=k)}[u_{i}(\theta;j,s_{-i}(\theta_{-i}))]\quad\forall
j\in[n]$ $\triangleright$ $\mu_{t}^{(-i)}\in\Delta(S_{-i})$

18: end for

19: end for

20:end procedure

We first bound the external regret for each thread $\ell\in[L]$ and each type
$k\in[K]$.

######  Lemma 4.2 (External regret).

For each thread $\ell\in[L]$, restart $\beta\in[T/H^{\ell}]$, type $k\in[K]$
and action $j\in[n]$, we have

$\displaystyle\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}r_{t,k}(j)-\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}\sum_{s_{i}\in S_{i}}q_{t,\ell}(s_{i})r_{t,k}(s_{i}(k))\leq 2\epsilon
H^{\ell}.$

###### Proof.

We have

$\displaystyle\sum_{t=(\beta-1)H^{\ell}+1}^{\beta H^{\ell}}\sum_{s_{i}\in
S_{i}}q_{t,\ell}(s_{i})r_{t,k}(s_{i}(k))=$
$\displaystyle~{}\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}\sum_{j\in[n]}\sum_{s_{i}\in
S_{i},s_{i}(k)=j}q_{t,\ell}(s_{i})r_{t,k}(j)$ $\displaystyle=$
$\displaystyle~{}\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}\sum_{j\in[n]}w_{t,\ell,k}(j)r_{t,k}(j)$ $\displaystyle\geq$
$\displaystyle~{}\max_{j\in[n]}\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}r_{t,k}(j)-2\sqrt{H\log(n)}H^{\ell-1}$ $\displaystyle=$
$\displaystyle~{}\max_{j\in[n]}\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}r_{t,k}(j)-2\epsilon H^{\ell}.$

Here the second step holds since the strategy
$q_{t,\ell}=w_{t,\ell,1}\times\cdots\times w_{t,\ell,K}$ is the product
distribution of $\\{w_{t,\ell,k}\\}_{k\in[K]}$. The third step holds due to
the regret guarantee of MWU, the last step holds due to
$H=\log(n)/\epsilon^{2}$. ∎

The next step is to bound the swap regret from the external regret guarantee.

######  Lemma 4.3 (External to swap regret reduction).

For any type $k\in[K]$ and any swap function $\phi:S_{i}\rightarrow S_{i}$, we
have

$\displaystyle\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}p_{t}(s_{i})r_{t,k}(\phi(s_{i})(k))-p_{t}(s_{i})r_{t,k}(s_{i}(k))\leq
3\epsilon T.$

###### Proof.

First, we have

$\displaystyle~{}\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}p_{t}(s_{i})r_{t,k}(\phi(s_{i})(k))-p_{t}(s_{i})r_{t,k}(s_{i}(k))$
$\displaystyle=$
$\displaystyle~{}\frac{1}{L}\sum_{\ell\in[L]}\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}q_{t,\ell}(s_{i})r_{t,k}(\phi(s_{i})(k))-q_{t,\ell}(s_{i})r_{t,k}(s_{i}(k))$
(6)

since $p_{t}=\frac{1}{L}\sum_{\ell\in[L]}q_{t,\ell}$.

For the first term, for each thread $\ell\in[L]$, we have

$\displaystyle\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}q_{t,\ell}(s_{i})r_{t,k}(\phi(s_{i})(k))=$
$\displaystyle~{}\sum_{\beta\in[T/H^{\ell}]}\sum_{h\in[H]}\sum_{t=(\beta-1)H^{\ell}+(h-1)H^{\ell-1}+1}^{(\beta-1)H^{\ell}+hH^{\ell-1}}\sum_{s_{i}\in
S_{i}}q_{t,\ell}(s_{i})r_{t,k}(\phi(s_{i})(k))$ $\displaystyle\leq$
$\displaystyle~{}\sum_{\beta\in[T/H^{\ell}]}\sum_{h\in[H]}\left\|\sum_{t=(\beta-1)H^{\ell}+(h-1)H^{\ell-1}+1}^{(\beta-1)H^{\ell}+hH^{\ell-1}}r_{t,k}\right\|_{\infty}$
(7)

where the second step holds since $q_{t,\ell}=w_{t,\ell,1}\times\cdots\times
w_{t,\ell,K}$ is fixed during the interval
$t\in[(\beta-1)H^{\ell}+(h-1)H^{\ell-1}+1:(\beta-1)H^{\ell}+hH^{\ell-1}]$.

For the second term in Eq. (6), for each thread $\ell\in[L]$ we have

$\displaystyle\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}q_{t,\ell}(s_{i})r_{t,k}(s_{i}(k))=$
$\displaystyle~{}\sum_{\beta\in[T/H^{\ell}]}\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}\sum_{s_{i}\in S_{i}}q_{t,\ell}(s_{i})r_{t,k}(s_{i}(k))$
$\displaystyle\geq$
$\displaystyle~{}\sum_{\beta\in[T/H^{\ell}]}\left(\left\|\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}r_{t,k}\right\|_{\infty}-2\epsilon H^{\ell}\right)$ $\displaystyle=$
$\displaystyle~{}\sum_{\beta\in[T/H^{\ell}]}\left\|{\sum_{t=(\beta-1)H^{\ell}+1}^{\beta
H^{\ell}}}r_{t,k}\right\|_{\infty}-2\epsilon T$ (8)

where the second step follows from Lemma 4.2.

Combining Eq. (6)(7)(8), we have

$\displaystyle\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}p_{t}(s_{i})r_{t,k}(\phi(s_{i})(k))-p_{t}(s_{i})r_{t,k}(s_{i}(k))\leq\frac{1}{L}\sum_{t\in[T]}\|r_{t,k}\|_{\infty}+2\epsilon
T\leq 3\epsilon T$

Here the second step follows from $L=1/\epsilon$ and $\|r_{t,k}\|_{\infty}\leq
1$. ∎

Now we can prove Theorem 4.1

###### Proof of Theorem 4.1.

We make each player $i\in[m]$ run Algorithm 5 for
$T=(\log(n)/\epsilon^{2})^{1/\epsilon}$ rounds. Let
$p^{(i)}_{t}\in\Delta(S_{i})$ be the strategy distribution of player $i$ at
round $t\in[T]$, then the joint distribution is
$\mu_{t}=\bigotimes_{i\in[m]}p_{t}^{(i)}$. We take
$\mu_{t}^{(-i)}=\bigotimes_{i^{\prime}\neq i}p_{t}^{(i^{\prime})}$ for any
$i\in[m]$. We prove the empirical distribution
$\mu=\frac{1}{T}\sum_{t\in[T]}\mu_{t}$ is a (every-type-$3\epsilon$)-NFCE.

For each player $i\in[m]$, type $k\in[K]$, swap function
$\phi:S_{i}\rightarrow S_{i}$, we have

$\displaystyle~{}\mathbb{E}_{\theta\sim(\rho|\theta_{i}=k)}\mathbb{E}_{s\sim\mu}[u_{i}(\theta;\phi(s_{i})(\theta_{i}),s_{-i}(\theta_{-i}))-u_{i}(\theta;s(\theta))]$
$\displaystyle=$
$\displaystyle~{}\frac{1}{T}\mathbb{E}_{\theta\sim(\rho|\theta_{i}=k)}\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}p_{t}^{(i)}(s_{i})\mathbb{E}_{s_{-i}\sim\mu_{t}^{(-i)}}[u_{i}(\theta;\phi(s_{i})(k),s_{-i}(\theta_{-i}))-u_{i}(\theta;s_{i}(k),s_{-i}(\theta_{-i}))]$
$\displaystyle=$ $\displaystyle~{}\frac{1}{T}\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}p_{t}^{(i)}(s_{i})\underbrace{\mathbb{E}_{s_{-i}\sim\mu_{t}^{(-i)}}\mathbb{E}_{\theta\sim(\rho|\theta_{i}=k)}[u_{i}(\theta;\phi(s_{i})(k),s_{-i}(\theta_{-i}))-u_{i}(\theta;s_{i}(k),s_{-i}(\theta_{-i}))]}_{r_{t,k}^{(i)}(\phi(s_{i})(k))-r_{t,k}^{(i)}(s_{i}(k))}$
$\displaystyle=$ $\displaystyle~{}\frac{1}{T}\sum_{t\in[T]}\sum_{s_{i}\in
S_{i}}p_{t}^{(i)}(s_{i})(r_{t,k}^{(i)}(\phi(s_{i})(k))-r_{t,k}^{(i)}(s_{i}(k)))$
$\displaystyle\leq$ $\displaystyle~{}3\epsilon.$

The first step follows from the construction of
$\mu=\frac{1}{T}\sum_{t\in[T]}\mu_{t}=\frac{1}{T}\sum_{t\in[T]}\bigotimes_{i\in[n]}p_{t}^{(i)}$,
the third step follows from the definition of reward $r_{t,k}^{(i)}$ for
player $i$ (Line 17 of Algorithm 5), the last step follows from Lemma 4.3.
Hence, we have proved $\mu$ is a (every-type-$3\epsilon$)-NFCE.

For computation efficiency, a player needs to compute $O(nK)$ reward entries
per iteration (Line 17 of Algorithm 5). Each of those entries can be
approximated (with high probability, up to $\pm\epsilon$ error) by random
sampling $O(\log(mTnKL)/\epsilon^{2})=O(\log(mnK/\epsilon)/\epsilon^{3})$
entries from the joint strategy distribution $\mu_{t}$ and the prior
distribution over $\Theta$ – we assume one can sample from the conditional
distribution $(\rho|\theta_{i}=k)$ in $O(m)$ time. The total runtime per
player equals $O(mnK\log(mnK/\epsilon)/\epsilon^{3})$.

∎

## References

  * [ADF+22] Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm.  Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736–749, 2022.
  * [AFK+22] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm.  Uncoupled learning dynamics with $O(\log T)$ swap regret in multiplayer games.  Advances in Neural Information Processing Systems, 35:3292–3304, 2022.
  * [AFS23] Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm.  Near-optimal $\Phi$-regret learning in extensive-form games.  In International Conference on Machine Learning, pages 814–839. PMLR, 2023.
  * [AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of computing, 8(1):121–164, 2012.
  * [AKSZ24] Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis.  On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games.  In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2024.
  * [BBJT15] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin.  Heads-up limit hold’em poker is solved.  Science, 347(6218):145–149, 2015.
  * [BCI+08] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou.  The myth of the folk theorem.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 365–372, 2008.
  * [BJM+22] Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu.  Efficient phi-regret minimization in extensive-form games via online mirror descent.  Advances in Neural Information Processing Systems, 35:22313–22325, 2022.
  * [BLGS19] Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm.  Deep counterfactual regret minimization.  In International conference on machine learning, pages 793–802. PMLR, 2019.
  * [BM07] Avrim Blum and Yishay Mansour.  From external to internal regret.  Journal of Machine Learning Research, 8(6), 2007.
  * [BPR16] Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein.  Can almost everybody be almost happy?  In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 1–9. ACM, 2016.
  * [BS18] Noam Brown and Tuomas Sandholm.  Superhuman ai for heads-up no-limit poker: Libratus beats top professionals.  Science, 359(6374):418–424, 2018.
  * [BS19] Noam Brown and Tuomas Sandholm.  Superhuman ai for multiplayer poker.  Science, 365(6456):885–890, 2019.
  * [CBL03] Nicolo Cesa-Bianchi and Gábor Lugosi.  Potential-based algorithms in on-line prediction and game theory.  Machine Learning, 51:239–261, 2003.
  * [CCPY22] Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis.  Computational hardness of the hylland-zeckhauser scheme.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2253–2268. SIAM, 2022.
  * [CDDT09] Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng.  Settling the complexity of arrow-debreu equilibria in markets with additively separable utilities.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 273–282. IEEE, 2009.
  * [CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng.  Settling the complexity of computing two-player nash equilibria.  Journal of the ACM (JACM), 56(3):1–57, 2009.
  * [CP20] Xi Chen and Binghui Peng.  Hedging in games: Faster convergence of external and swap regrets.  Advances in Neural Information Processing Systems, 33:18990–18999, 2020.
  * [CP23] Xi Chen and Binghui Peng.  Complexity of equilibria in first-price auctions under general tie-breaking rules.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 698–709, 2023.
  * [CPY13] Xi Chen, Dimitris Paparas, and Mihalis Yannakakis.  The complexity of non-monotone markets.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 181–190, 2013.
  * [DDFG24] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich.  From external to swap regret 2.0: An efficient reduction and oblivious adversary for large action spaces.  In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
  * [DFG21] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich.  Near-optimal no-regret learning in general games.  Advances in Neural Information Processing Systems, 34:27604–27616, 2021.
  * [DFHM22] Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos.  Pure-circuit: Strong inapproximability for ppad.  In 2022 IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS), 2022.
  * [DGP09] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou.  The complexity of computing a nash equilibrium.  SIAM Journal on Computing, 39(1):195–259, 2009.
  * [DGZ23] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang.  The complexity of markov equilibrium in stochastic games.  In The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023\.
  * [DSZ21] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis.  The complexity of constrained min-max optimization.  In Proceedings of the 53th Annual ACM SIGACT Symposium on Theory of Computing, 2021.
  * [FCMG22] Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti.  Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium.  Journal of the ACM, 69(6):1–41, 2022.
  * [FGK23] Dylan J Foster, Noah Golowich, and Sham M Kakade.  Hardness of independent learning and sparse equilibrium computation in markov games.  In International Conference on Machine Learning. PMLR, 2023.
  * [FKS19] Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Optimistic regret minimization for extensive-form games via dilated distance-generating functions.  Advances in neural information processing systems, 32, 2019.
  * [FLFS19] Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm.  Efficient regret minimization algorithm for extensive-form correlated equilibrium.  Advances in Neural Information Processing Systems, 32, 2019.
  * [FLL+16] Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos.  Learning in games: Robustness of fast convergence.  Advances in Neural Information Processing Systems, 29, 2016.
  * [FLLK22] Gabriele Farina, Chung-Wei Lee, Haipeng Luo, and Christian Kroer.  Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games.  In International Conference on Machine Learning, pages 6337–6357. PMLR, 2022.
  * [For93] Françoise Forges.  Five legitimate definitions of correlated equilibrium in games with incomplete information.  Theory and decision, 35:277–310, 1993.
  * [FRGH+21] Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças.  On the complexity of equilibrium computation in first-price auctions.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 454–476, 2021.
  * [FS97] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * [FS99] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * [Fuj23] Kaito Fujii.  Bayes correlated equilibria and no-regret dynamics.  arXiv preprint arXiv:2304.05005, 2023.
  * [FV97] Dean P Foster and Rakesh V Vohra.  Calibrated learning and correlated equilibrium.  Games and Economic Behavior, 21(1-2):40, 1997.
  * [FV98] Dean P Foster and Rakesh V Vohra.  Asymptotic calibration.  Biometrika, 85(2):379–390, 1998.
  * [FV99] Dean P Foster and Rakesh Vohra.  Regret in the on-line decision problem.  Games and Economic Behavior, 29(1-2):7–35, 1999.
  * [HM10] Sergiu Hart and Yishay Mansour.  How long to equilibrium? the communication complexity of uncoupled equilibrium procedures.  Games and Economic Behavior, 69(1):107–126, 2010.
  * [HMC00] Sergiu Hart and Andreu Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  Econometrica, 68(5):1127–1150, 2000.
  * [HMC01] Sergiu Hart and Andreu Mas-Colell.  A reinforcement procedure leading to correlated equilibrium.  In Economics Essays: A Festschrift for Werner Hildenbrand, pages 181–200. Springer, 2001.
  * [HMC13] Sergiu Hart and Andreu Mas-Colell.  Simple adaptive strategies: from regret-matching to uncoupled dynamics, volume 4.  World Scientific, 2013.
  * [HST15] Jason Hartline, Vasilis Syrgkanis, and Eva Tardos.  No-regret learning in bayesian games.  Advances in Neural Information Processing Systems, 28, 2015.
  * [JMS23] Yujia Jin, Vidya Muthukumar, and Aaron Sidford.  The complexity of infinite-horizon general-sum stochastic games.  In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.
  * [Kuh53] HW Kuhn.  Extensive games and the problem of information.  Contributions to the Theory of Games, page 193, 1953.
  * [LMM03] Richard J Lipton, Evangelos Markakis, and Aranyak Mehta.  Playing large games using simple strategies.  In Proceedings of the 4th ACM Conference on Electronic Commerce, pages 36–41, 2003.
  * [LW94] Nick Littlestone and Manfred K Warmuth.  The weighted majority algorithm.  Information and computation, 108(2):212–261, 1994.
  * [LWZB09] Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling.  Monte carlo sampling for regret minimization in extensive games.  Advances in neural information processing systems, 22, 2009.
  * [OPR16] Abraham Othman, Christos Papadimitriou, and Aviad Rubinstein.  The complexity of fairness through equilibrium.  ACM Transactions on Economics and Computation (TEAC), 4(4):1–19, 2016.
  * [Pap94] Christos H Papadimitriou.  On the complexity of the parity argument and other inefficient proofs of existence.  Journal of Computer and system Sciences, 48(3):498–532, 1994.
  * [PP21] Christos Papadimitriou and Binghui Peng.  Public goods games in directed networks.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 745–762, 2021.
  * [PR08] Christos H Papadimitriou and Tim Roughgarden.  Computing correlated equilibria in multi-player games.  Journal of the ACM (JACM), 55(3):1–29, 2008.
  * [PR23] Binghui Peng and Aviad Rubinstein.  Near optimal memory-regret tradeoff for online learning.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1171–1194. IEEE, 2023.
  * [PR24] Binghui Peng and Aviad Rubinstein.  Fast swap regret minimization and applications to approximate correlated equilibria.  In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
  * [Rub16] Aviad Rubinstein.  Settling the complexity of computing approximate two-player nash equilibria.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 258–265. IEEE, 2016.
  * [Rub18] Aviad Rubinstein.  Inapproximability of nash equilibrium.  SIAM Journal on Computing, 47(3):917–959, 2018.
  * [Rub19] Aviad Rubinstein.  Hardness of Approximation Between P and NP.  Morgan & Claypool, 2019.
  * [SALS15] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire.  Fast convergence of regularized learning in games.  Advances in Neural Information Processing Systems, 28, 2015.
  * [SL05] Gilles Stoltz and Gábor Lugosi.  Internal regret in on-line portfolio selection.  Machine Learning, 59:125–159, 2005.
  * [SL07] Gilles Stoltz and Gábor Lugosi.  Learning correlated equilibria in games with compact sets of strategies.  Games and Economic Behavior, 59(1):187–208, 2007.
  * [Vov90] Vladimir Vovk.  Aggregating strategies.  In Proceedings of 3rd Annu. Workshop on Comput. Learning Theory, pages 371–383, 1990.
  * [VSF08] Bernhard Von Stengel and Françoise Forges.  Extensive-form correlated equilibrium: Definition and computational complexity.  Mathematics of Operations Research, 33(4):1002–1022, 2008.
  * [VY11] Vijay V Vazirani and Mihalis Yannakakis.  Market equilibrium under separable, piecewise-linear, concave utilities.  Journal of the ACM (JACM), 58(3):1–25, 2011.
  * [ZJBP07] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione.  Regret minimization in games with incomplete information.  Advances in neural information processing systems, 20, 2007.

##  Appendix A On the rank of CE

We give a simple example of Bayesian game (thus also an example of extensive-
form game), where behaviourizing a rank-$2$ CE is no longer a CE. There are
two players, Alice and Bob, in the game. Bob has $2$ actions, one type and his
utility is always $0$. Alice has $n$ types and $4$ actions. For each type,
Alice has utility

$\displaystyle u_{A}(0,0)=0,u_{A}(1,0)=0,u_{A}(2,0)=1,u_{B}(3,0)=-2$

and

$\displaystyle u_{A}(0,1)=0,u_{A}(1,1)=0,u_{A}(2,1)=-2,u_{A}(3,1)=1.$

Consider the following rank-$2$ CE $\mu=\frac{1}{2}p_{A}^{(1)}\otimes
p_{B}^{(1)}+\frac{1}{2}p_{A}^{(2)}\otimes p_{B}^{(2)}$, where
$p_{A}^{(1)}=\frac{1}{3}(0,0,\ldots,0)+\frac{2}{3}(1,1,\ldots,1)$,
$p_{A}^{(2)}=\frac{2}{3}(0,0,\ldots,0)+\frac{1}{3}(1,1,\ldots,1)$;
$p_{B}^{(1)}=0$, $p_{B}^{(0)}=1$. That is, in the first product distribution,
Alice plays all $0$ w.p. $1/3$ and plays all $1$ w.p. $2/3$, Bob always plays
$0$; in the second product distribution, Bob plays all $0$ w.p. $2/3$ and
plays all $1$ w.p. $2/3$, Bob always plays $1$. It is not hard to verify that
$\mu$ is indeed a CE and Alice receives $0$ utility.

Meanwhile, the only way to behaviourize $\mu$, is to replace $p_{A}^{(1)}$
with
$x_{A}^{(1)}=(\frac{1}{3},\frac{2}{3})\otimes\cdots\otimes(\frac{1}{3},\frac{2}{3})$
and
$x_{B}^{(1)}=(\frac{2}{3},\frac{1}{3})\otimes\cdots\otimes(\frac{2}{3},\frac{1}{3})$.
Let $\mu^{\prime}=\frac{1}{2}x_{A}^{(1)}\otimes
p_{B}^{(1)}+\frac{1}{2}x_{A}^{(2)}\otimes p_{B}^{(2)}$. Consider the swap
function $\phi_{A}=\\{0,1,2,3\\}^{n}\rightarrow\\{0,1,2,3\\}^{n}$

$\displaystyle\phi_{A}(s)=\left\\{\begin{matrix}(2,\ldots,2)&s\in\\{0,1\\}^{n},|s|\in(n/3-\sqrt{n}\log(n),n/3+\sqrt{n}\log(n))\\\
(3,\ldots,3)&s\in\\{0,1\\}^{n},|s|\in(2n/3-\sqrt{n}\log(n),2n/3+\sqrt{n}\log(n))\\\
s&\text{otherwise}\end{matrix}\right.$

We claim that applying the swap function $\phi_{A}$, the utility of Alice
becomes $1-o(1)$ (under $\mu^{\prime}$). First, we know that with probability
$1-o(1)$, for any $(s_{A},s_{B})\sim\mu^{\prime}$,
$|s_{A}|\in(n/3-\sqrt{n}\log(n),n/3+\sqrt{n}\log(n))$ or
$|s_{A}|\in(2n/3-\sqrt{n}\log(n),2n/3+\sqrt{n}\log(n))$. In the former case,
Bob plays $1$ w.p. $1-o(1)$ so switching to action $(3,3,\ldots,3)$ has
utility $1$; in the latter case, Bob plays $0$ w.p. $1-o(1)$ so switching to
action $(2,2,\ldots,2)$ has utility $1$. This implies $\mu^{\prime}$ is not a
CE.

##  Appendix B Missing proof from Section 3

######  Fact B.1.

Let $X,Y$ be finite domains. Let $p,q\in\Delta(X\times Y)$ be two probability
distributions over $X\times Y$. Define $p(x):=\sum_{y\in Y}p(x,y)$ be the
marginal probability of $x\in X$ and $p(y|x)=p(x,y)/p(x)$ be the conditional
probability of $y\in Y$ on $x\in Y$. Suppose $p(x)=q(x)$ holds for any $x\in
X$, then

$\mathsf{TV}(p;q)=\sum_{x\in X}p(x)\cdot\mathsf{TV}(p(\cdot|x);q(\cdot|x)).$

###### Proof.

We have

$\displaystyle\mathsf{TV}(p;q)=$ $\displaystyle~{}\frac{1}{2}\sum_{(x,y)\in
X\times Y}|p(x,y)-q(x,y)|=\sum_{x\in X}\left(\frac{1}{2}\sum_{y\in
Y}|p(x,y)-q(x,y)|\right)$ $\displaystyle=$ $\displaystyle~{}\sum_{x\in
X}p(x)\left(\frac{1}{2}\sum_{y\in Y}|p(y|x)-q(y|x)|\right)=\sum_{x\in
X}p(x)\cdot\mathsf{TV}(p(\cdot|x);q(\cdot|x)).$

The first step follows from the definition of TV distance, the third step
holds since $p(x,y)=p(x)\cdot p(y|x)$, $q(x,y)=q(x)q(y|x)=p(x)q(y|x)$, the
last step follows the definition of TV distance. ∎

######  Fact B.2.

Let $X,Y$ be finite domains. Let $w\in\Delta(X\times Y)$ be a joint
distribution over $X\times Y$, and $w_{X},w_{Y}$ be the marginal distribution
of $w$ on $X,Y$. Let $p=w_{X}\times w_{Y}\in\Delta(X)\times\Delta(Y)$ be a
product distribution over $X\times Y$ and it has the same marginal
distribution as $w$. Then for any product distribution
$q\in\Delta(X)\times\Delta(Y)$, we have

$\mathsf{TV}(p;q)\leq 2\mathsf{TV}(w;q)$

###### Proof.

We have

$\displaystyle\mathsf{TV}(p;q)\leq\mathsf{TV}(w_{X};q_{X})+\mathsf{TV}(w_{Y};q_{Y})\leq
2\mathsf{TV}(w;q).$

∎