# Communication games, sequential equilibrium, and mediators

Ivan Geffner
Cornell University Supported in part by NSF grants IIS-1703846 and
IIS-0911036, ARO grant W911NF-17-1-0592, MURI grant W911NF-19-1-0217 from the
ARO, and a grant from Open Philanthropy.Declarations of interest: none. Joseph
Y. Halpern
Cornell University11footnotemark: 1 22footnotemark: 2

We consider _$k$ -resilient sequential equilibria_, strategy profiles where no
player in a coalition of at most $k$ players believes that it can increase its
utility by deviating, regardless of its local state. We prove that all
$k$-resilient sequential equilibria that can be implemented with a trusted
mediator can also be implemented without the mediator in a synchronous system
of $n$ players if $n>3k$. In asynchronous systems, where there is no global
notion of time and messages may take arbitrarily long to get to their
recipient, we prove that a $k$-resilient sequential equilibrium with a
mediator can be implemented without the mediator if $n>4k$. These results
match the lower bounds given by Abraham, Dolev, and Halpern [2008b] and
Geffner and Halpern [2023] for implementing a Nash equilibrium without a
mediator (which are easily seen to apply to implementing a sequential
equilibrium) and improve the results of Gerardi [2004], who showed that, in
the case that $k=1$, a sequential equilibrium can be implemented in
synchronous systems if $n\geq 5$.

##  1 Introduction

A standard technique for dealing with complicated problems in distributed
computing, cryptography, and game theory is to show that the problem can be
solved under the assumption that there is a _trusted mediator_ , a third party
to whom all agents in the system can communicate, and then showing that we can
_implement_ the mediator; that is, the agents just communicating among
themselves (using what economists call _cheap talk_) can simulate what the
mediator does. In the distributed computing and cryptography literature, the
focus has been on _secure multiparty computation_ Goldreich et al. [1987]; Yao
[1982]. Given $n$ agents in which each agent $i$ has input $x_{i}$, the goal
is to compute some function $f(x_{1},\ldots,x_{n})$ without revealing anything
about the agents’ inputs besides what can be deduced from the output of the
function itself. With a mediator, this is trivial: each agent $i$ just tells
the mediator $x_{i}$, and the mediator tells the agents
$f(x_{1},\ldots,x_{n})$. It is known that, as long as no more than $k$ agents
are malicious, this mediator can be implemented if $n>3k$.

Game theory adds incentives to the mix. While in the work done in
cryptography, it is simply assumed that malicious agents will do what they can
to bring down the system, in the game-theoretic setting, it is assumed that
agents will deviate from a strategy only if it is in their best interests to
do so. To make this precise, in the game theory literature, three games were
considered: an _underlying_ normal-form game $\Gamma$, a game $\Gamma_{d}$
with a mediator, where, after communicating with the mediator, players make a
move in $\Gamma$ and get the same payoffs that they do in $\Gamma$, and a
_cheap-talk game_ $\Gamma_{\mathit{CT}}$, where players just talk to each
other and then make a move in the underlying game. Forges [1990] and Barany
[1992] showed that a Nash equilibrium (NE) in the mediator game $\Gamma_{d}$
could be _implemented_ by a NE in the cheap-talk game if $n\geq 4$ in the
sense that the distribution over action profiles in the NE in $\Gamma_{d}$ is
the same as that in the NE in $\Gamma_{\mathit{CT}}$.

As is well known, Nash equilibrium considers only deviations on the
_equilibrium path_ (situations that arise with positive probability if the NE
is played). In extensive-form games such as $\Gamma_{\mathit{CT}}$, Nash
equilibrium does not always describe what intuitively would be reasonable
play. For example if $A$ tells $B$ to give her $1 or she will destroy the
world, $B$ giving $1 to $A$ and $A$ not destroying the world is a NE. However,
this equilibrium is based on a non-credible threat. Would $A$ really destroy
the world if she doesn’t get $1? For this reason, game theorists have
considered solution concepts such as _sequential equilibrium_ Kreps and Wilson
[1982], where players cannot increase their utility by deviating even off the
equilibrium path (see Section 13 for a formal definition).

Not surprisingly, the question of whether a sequential equilibrium with a
mediator can be implemented has been considered before in the game theory
literature. Ben-Porath [2003] claimed that a sequential equilibrium could be
implemented in $\Gamma_{\mathit{CT}}$ if $n>3$ provided that there is a
_punishment strategy_ (a way for players to punish players who are caught
cheating—see Section 3 for a formal definition);111Unfortunately, there is a
serious error in Ben-Porath’s proof; see Abraham et al. [2008b]; Ben-Porath
[2021]. Gerardi [2004] showed that, in the case that $k=1$, a sequential
equilibrium can be implemented if $n\geq 5$.

Nash and sequential equilibria incentivize individual participants to follow
the given strategy since otherwise they would get a lower expected payoff.
However, if players can form coalitions and deviate in a coordinated way, then
a coalition of players may have incentive to deviate in a Nash or sequential
equilibrium. For instance, consider a normal-form game for $n$ players in
which players can play either $0$ or $1$. If at least $n-1$ players play $0$,
they all get $0$ utility, but if two or more players play $1$, these players
get a utility of $1$ and everyone else gets a utility of $-1$. Clearly,
playing $0$ is a Nash equilibrium of this game. However, if two players can
deviate together, they can increase their payoff by playing $1$ instead of
$0$. Designing mechanisms that incentivize not only individuals, but also
coalitions to act as intended has become increasingly important, especially in
Internet applications (e.g., blockchain), where the same person can maintain
several identities. Not surprisingly, coalitions have received significant
attention recently in the literature (see, e.g., Eyal and Sirer [2014]; Heller
[2010]). Abraham, Dolev, Gonen and Halpern [2006] (ADGH from now on)
introduced the notion of _$k$ -resilient Nash equilibrium_, which is a
strategy profile in which no coalition of up to $k$ players can increase their
payoff by deviating. They also generalized Forges and Barany’s results by
showing that any $k$-resilient Nash equilibrium in $\Gamma_{d}$ can be
implemented in $\Gamma_{\mathit{CT}}$ if the number of players $n$ satisfies
$n>3k$, and proved that the $n>3k$ bound is tight Abraham et al. [2008b]. More
precisely, if $n\leq 3k$, then there exists a game $\Gamma_{d}$ for $n$
players and a mediator and a $k$-resilient Nash equilibrium $\vec{\sigma}$ in
$\Gamma_{d}$ that can’t be implemented in $\Gamma_{\mathit{CT}}$.

Two natural questions follow from these results. First, whether we can
generalize Gerardi’s result and give necessary and sufficient conditions on
$n$ and $k$ to implement a $k$-resilient sequential equilibrium (which is
defined analogously to $k$-resilient Nash equilibrium), and second, whether
the $n\geq 5$ upper bound given by Gerardi is actually tight. It is easy to
check that the $n>3k$ lower bound given in Abraham et al. [2008b] for Nash
equilibrium applies without change to $k$-resilient sequential equilibria. In
particular, if $k=1$, it shows that at least $4$ players are required to
implement a sequential equilibrium, but it was not known whether $n\geq 5$ is
necessary. Here, we show that we can always implement a $k$-resilient
sequential equilibrium in a game with a mediator and $n$ players if $n>3k$,
matching the lower bound given in Abraham et al. [2008b] and improving
Gerardi’s result for $k=1$.

Following Gerardi [2004] and Gerardi and Myerson [2007], we also relate our
results to two other solution concepts in normal-form games: _correlated
equilibrium_ Aumann [1987] and _communication equilibrium_ Forges [1986];
Myerson [1986]. Both of these concepts can be understood in terms of games
with mediators. A correlated equilibrium is an equilibrium in a game with a
mediator where the players do not talk to the mediator; the mediator simply
tells the agent which strategy to play. A _communication equilibrium_ in a
Bayesian game is an equilibrium in a game with a mediator where the players
can tell the mediator their types, and the mediator then tells the players
what strategy to play (see Appendix A for formal definitions). Our results
give a characterization of the set $SE_{k}(\Gamma_{\mathit{CT}})$ of outcomes
that can be implemented with $k$-resilient sequential equilibria in the cheap-
talk game $\Gamma_{\mathit{CT}}$; if $\Gamma$ is a normal-form game, then
$SE_{k}(\Gamma_{\mathit{CT}})$ is the set of $k$-resilient correlated
equilibria of $\Gamma$, while if $\Gamma$ is a Bayesian game,
$SE_{k}(\Gamma_{\mathit{CT}})$ is the set of $k$-resilient communication
equilibria of $\Gamma$.

Sequential equilibrium involves describing not only what the players do at
each point in an extensive-form game, but describing what their beliefs are,
even off the equilibrium path. It must be shown that players are always best
responding to their beliefs. The key difficulty in our proof involves finding
appropriate beliefs that are consistent with the equilibrium strategy. The
proof given by Gerardi involves an extensive case analysis for both
consistency and sequential rationality, which makes it hard to generalize to
other settings. Our proof introduces an interesting new technique. We show
that all strategies in $\Gamma_{\mathit{CT}}$ (even those that are not an
equilibrium) admit a consistent _$k$ -paranoid belief system_, where all
coalitions $K$ of at most $k$ players always believe that, if other players
deviated, they did so by sending inappropriate messages only to players in
$K$. That is, all coalitions of size at most $k$ believe that the remaining
players are being truthful among themselves. We show that, given a
$k$-resilient Nash equilibrium $\vec{\sigma}$, we can extend it to a
$k$-resilient sequential equilibrium by constructing a $k$-paranoid belief
system. The idea is that, given these $k$-paranoid beliefs, players in a
coalition $K$ will not believe that there is anything that they can do to
prevent the remaining players from playing their part of the equilibrium. We
then apply these results to the $k$-resilient Nash equilibrium of Abraham et
al. [2006] to get our result.

All of the results presented so far assume a _synchronous_ setting:
communication proceeds in atomic rounds, and all messages sent during round
$r$ are received by round $r+1$. In an _asynchronous_ setting, there are no
rounds and messages sent by the players may take arbitrarily long to get to
their recipients. Asynchrony is a standard assumption in the distributed
computing and cryptography literature, precisely because many systems that
practitioners care about, such as markets or the internet, are asynchronous in
practice. Considering asynchronous systems can have significant implications
for how players will play a game. For instance, in an online second-price
auction, the seller can benefit from inserting fake transactions whose value
is between that of the highest and second-highest bid immediately after a new
highest bid is received, thus increasing the second-highest price at no cost
Roughgarden [2020]. This type of attack can be carried out only in
asynchronous or _partially synchronous_ systems (where there is an upper bound
on how long messages take to arrive), since in a synchronous system, all bids
are received at the same time. (In a synchronous system, the seller would have
to guess what the players will bid in order to benefit from a fake
transaction.)

This example shows that asynchrony and partial synchrony allow players to
influence the communication pattern in ways that they can’t in a synchronous
setting. Other examples include the fact that, in a fully asynchronous system,
a player that didn’t send a message is indistinguishable from a player whose
message is delayed (which means that players can safely deviate by not sending
messages for a while, which they cannot do in a synchronous system), and that,
in a partially synchronous system, players may read other players’ messages
before sending their own and adapt their strategy accordingly. As a result,
the number of honest players required to implement a given functionality is
greater in an asynchronous setting. For instance, the upper bound for
asynchronous secure computation is $n>4k$ Ben-Or et al. [1993], as opposed to
$n>3k$ bound in synchronous systems proved by Ben-Or, Goldwasser, and
Wignerson [1988].

The simplicity of our approach allows us to generalize our main result to the
asynchronous setting with very little work. Given a $k$-resilient sequential
equilibria $\vec{\sigma}$ in an asynchronous game with $n$ players and a
mediator, we extend implementation given by Abraham et al. [2019b] of
asynchronous $k$-resilient Nash equilibria in $\Gamma_{\mathit{CT}}$ for
$n>4k$ by constructing a consistent $k$-paranoid belief system. Reasoning
analogous to that used in the synchronous case shows that the resulting
strategy and belief system form a $k$-resilient sequential equilibria. In the
asynchronous setting, this result is also optimal, since it matches the $n>4k$
lower bound given by Geffner and Halpern [2023]. We believe that the
techniques presented in this paper can be applied to design $k$-resilient
sequential equilibria in many other scenarios as well.

The rest of the paper is organized as follows. In Section 2, we provide the
concepts and definitions required to understand the main results and its
proofs (some of the most basic definitions can be found in Appendix A). In
Section 3, we state the main result and give a short outline of its proof. The
details are given in Section 4. In Section 5, we provide our characterization
of $SE_{k}(\Gamma_{CT})$. In Section 6, we carefully define asynchronous
systems and extend the results of Section 6 to the asynchronous case; these
results are further extended in Section 7 assuming that players can send
arbitrarily precise real numbers in their messages (rather than just rational
numbers, which is what we assume up to this point).

##  2 $k$-resilient equilibrium

In this section, we extend the different types of equilibria that appear in
the literature (which are discussed in Appendix A) to account for deviations
of coalitions of at most $k$ players. For future reference, in normal-form
games, we use $n$ to denote the number of players, $P$ to denote the set of
players, $A$ to denote the set of possible action profiles, and $U$ to denote
the tuple of utility functions. In Bayesian games, we use $T$ to denote the
possible type profiles and $q$ to denote the prior distribution over $T$.
Moreover, in extensive-form games, we use $G$ to denote the game tree, $M$ to
denote the function that outputs which player moves at each node, and $R$ to
denote the tuple of equivalence relations between the nodes in which two nodes
$v$ and $w$ are equivalent according to the $i$th relation if $i$ cannot
distinguish these between $v$ and $w$ (i.e., if $v$ and $w$ are in the same
partition). The full definitions can be found in Appendix A.

Intuitively, traditional notions of equilibria guarantee that no individual
player can increase her own payoff by deviating from the proposed strategy.
For each of these equilibria we consider also its $k$-resilient variant, which
states that no coalition of at most $k$ players can jointly increase their
payoff by deviating, even if they do so in a coordinated way. We also consider
the notion of _strong $k$-resilience_, which guarantees that no individual
player inside the coalition can increase its own payoff, even at the expense
of other coalition members (as opposed to the original notion, in which no
member of the coalition can be worse than by following the proposed strategy).

###  2.1 $k$-resilient Nash, sequential, Bayesian Nash, and communication
equilibrium

We begin by extending the definition of Nash equilibrium (Definition 11) to
$k$-resilient Nash equilibrium:

######  Definition 1.

In a normal-form game $\Gamma$, a (mixed) strategy profile
$\vec{\sigma}=(\sigma_{1},\ldots,\sigma_{n})$ is a _$k$ -resilient Nash
equilibrium_ (resp., _strongly $k$-resilient Nash equilibrium_) if, for all
coalitions $K$ such that $|K|\leq k$, and all strategies
$\vec{\sigma}^{\prime}_{K}\in\Delta(A_{K})$

$u_{i}(\vec{\sigma}_{K},\vec{\sigma}_{-K})\geq
u_{i}(\vec{\sigma}^{\prime}_{K},\vec{\sigma}_{-K})$

for some (resp., for all) $i\in K$.

We can similarly extend the notion of correlated equilibrium (see Definition
12 of Appendix A) to $k$-resilient correlated equilibrium:

######  Definition 2.

Given a normal-form game $\Gamma=(n,A,U)$, a distribution $p\in\Delta(A)$ is a
_$k$ -resilient correlated equilibrium_ (resp., _strongly $k$-resilient
correlated equilibrium_) if, for all subsets $K\subseteq P$ such that $|K|\leq
k$, and all action profiles $\vec{a}^{\prime}_{K},\vec{a}^{\prime\prime}_{K}$
for players in $K$ such that $p(\vec{a}^{\prime}_{K})>0$,

$\sum_{\vec{a}\in\Delta(A):\vec{a}_{K}=\vec{a}^{\prime}_{K}}u_{i}(\vec{a}^{\prime}_{K},\vec{a}_{-K})p(\vec{a}\mid\vec{a}_{K}=\vec{a}^{\prime}_{K})\geq\sum_{\vec{a}\in\Delta(A):\vec{a}_{K}=\vec{a}^{\prime}_{K}}u_{i}(a^{\prime\prime}_{K},a_{-K})p(\vec{a}\mid\vec{a}_{K}=\vec{a}^{\prime}_{K})$

for some (resp., for all) $i\in K$.

Simply put, a distribution $p\in\Delta(A)$ is a $k$-resilient correlated
equilibrium if no subset of at most $k$ players would be better off by
deviating if they knew that the action profile used was sampled according to
$p$ (and they knew their components of the profile), even if they could
coordinate their deviations.

The definition of $k$-resilient Nash equilibrium in extended-form games is
equivalent. However, the extension of sequential equilibrium (Definition 13)
to $k$-resilient sequential equilibrium requires additional definitions
Abraham et al. [2019a].

######  Definition 3.

Let $\Gamma=(P,G,M,U,R)$ be an extensive-form game and $K\subseteq P$ be a
subset of players. We define the equivalence relation $\sim_{K}$ by
$v\sim_{K}v^{\prime}$ iff $v\sim_{i}v^{\prime}$ for all $i\in K$.222The
$\sim_{i}$ relation defines player $i$’as information sets in an extensive-
form game. Se Appendix A for the formal definition. The equivalence classes of
$\sim_{K}$ are called _$K$ -information sets_.

Intuitively, two nodes are related according to $\sim_{K}$ if they are
indistinguishable for all players $i\in K$. With this, we can extend the
notion of belief systems to account for coalitions of players that share
information between themselves.

######  Definition 4.

A _$k$ -belief system_ $b$ in a game $\Gamma$ is a function that maps each
$K$-information set $I$ such that $K\subseteq P$ and $|K|\leq k$ to a
distribution over the nodes in $I$.

We can define what it means for a $k$-belief system to be consistent with
$\vec{\sigma}$ just as in the case of standard belief systems. We say that a
$k$-belief system $b$ is consistent with strategy $\vec{\sigma}$ if there
exists a sequence $\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ of completely-
mixed strategies that converges to $\vec{\sigma}$ such that the beliefs
induced by Bayes’ rule converge to $b$. With these definitions in hand, we can
find the desired generalization of sequential equilibrium.

######  Definition 5.

A pair $(\vec{\sigma},b)$ consisting of a strategy profile $\vec{\sigma}$ and
a $k$-belief system $b$ consistent with $\vec{\sigma}$ is a _$k$ -resilient
sequential equilibrium_ (resp., _strongly $k$-resilient sequential
equilibrium_) if, for all $K\subseteq P$ with $|K|\leq k$, all $K$-information
sets $I$, and all strategies $\tau_{K}$ for players in $K$ (w.r.t.
$\sim_{K}$),

$u_{i}(\vec{\sigma},I,b)\geq u_{i}((\tau_{K},\vec{\sigma}_{-K}),I,b)$

for some (resp., for all) $i\in K$.

Note that the notions of $1$-resilient correlated equilibrium and
$1$-resilient sequential equilibrium are equivalent to the standard notions of
correlated equilibrium and sequential equilibrium, respectively. Note that, in
games with a mediator $d$, since the mediator never deviates from its
strategy, a belief system $b$ is consistent with strategy
$\vec{\sigma}+\sigma_{d}$ (where $\vec{\sigma}+\sigma_{d}$ means that players
play strategy profile $\vec{\sigma}$ and the mediator plays strategy
$\sigma_{d}$) if there exists a sequence
$\vec{\sigma}^{1}+\sigma_{d},\vec{\sigma}^{2}+\sigma_{d},\ldots$ of
completely-mixed strategies that converges to $\vec{\sigma}+\sigma_{d}$ such
that the beliefs induced by Bayes’ rule converge to $b$. The definition of
$k$-resilient sequential equilibrium in mediator games is identical to the one
given in Definition 5, using this definition of consistent beliefs.
Intuitively, this means that the players believe that the mediator never
deviates from its protocol.

In a Bayesian game with type space $T$ (see Appendix A.2 for the formal
definitions), a _correlated strategy profile_ is a map
$\mu:T\rightarrow\Delta(A)$. Note that all distributions over strategy
profiles can be viewed as correlated strategy profiles, but the converse is
not true. For instance, in a game with two players in which
$A_{i}=T_{i}=\\{0,1\\}$ for all $i$, a correlated strategy profile may consist
of both players playing action $t_{1}+t_{2}\bmod 2$; this cannot be
represented by a strategy profile, since players must independently choose
their action given their type.

The expected utility of player $i$ in a coalition $K$ when playing (a possibly
correlated) strategy profile $\vec{\mu}$, where $T_{K}$ is the set of possible
type profiles of the players in $K$, is

$u_{i}^{K}(\vec{\mu})=\sum_{\vec{t}_{K}\in
T_{K}}q(\vec{t}_{K})\sum_{\vec{t}\in
T}q(\vec{t}\mid\vec{t}_{K})u_{i}(\vec{\mu}(\vec{t})),$

where $u_{i}(\vec{\mu}(\vec{t}))$ denotes the expected utility of player $i$
when an action profile is chosen according to $\mu(\vec{t})$. Intuitively, we
are assuming that players in $K$ can share their types, which is why we
condition on $\vec{t}_{K}$. With this, we can extend Bayesian Nash equilibrium
(see Definition 14 in Appendix A) to $k$-resilient Bayesian Nash equilibrium:

######  Definition 6.

In a Bayesian game $\Gamma=(P,T,q,A,U)$, a strategy profile
$\vec{\mu}:=(\mu_{1},\ldots,\mu_{n})$ is a _$k$ -resilient Bayesian Nash
equilibrium_ (resp., _strongly $k$-resilient Bayeisan Nash equilibrium_) if,
for all coalitions $K$ with $|K|\leq k$ and all maps
$\mu^{\prime}_{K}:T_{K}\rightarrow\Delta(A_{K})$,

$u_{i}^{K}(\vec{\mu})\geq u_{i}^{K}(\vec{\mu}_{-K},\mu^{\prime}_{K})$

for some (resp., for all) $i\in K$.

We can similarly generalize communication equilibrium (see Definition 15 of
Appendix A)) to $k$-resilient communication equilibrium:

######  Definition 7.

A correlated strategy profile $\mu:T\rightarrow\Delta(A)$ is a _$k$ -resilient
communication equilibrium_ (resp., _strongly $k$-resilient communication
equilibrium_ of Bayesian Game $\Gamma=(P,T,q,A,U)$ if, for all $K\subseteq P$
such that $|K|\leq k$, all $\vec{t}_{K}\in T_{K}$, all $\psi:T_{K}\rightarrow
T_{K}$, and all $\varphi:A_{K}\rightarrow A_{K}$, we have that

$\sum_{\vec{t}_{-K}\in T_{-K}}\sum_{\vec{a}\in
A}q(t_{-K},\vec{t}_{K})\mu(\vec{a}\mid\vec{t}_{-K},\vec{t}_{K})u_{i}(\vec{t}_{-K},\vec{t}_{K},\vec{a})\geq$
$\sum_{\vec{t}_{-K}\in T_{-K}}\sum_{\vec{a}\in
A}q(t_{-K},\vec{t}_{K})\mu(\vec{a}\mid\vec{t}_{-K},\psi(\vec{t}_{K}))u_{i}(\vec{t}_{-K},\vec{t}_{K},\vec{a}_{-K},\varphi(\vec{a}_{K}))$

for some (resp., for all) $i\in K$.

As in the case of the standard communication equilibrium, we can identify a
correlated strategy profile $\mu$ with a canonical game with a mediator in
which each player $i$ must send its type $t_{i}$ to the mediator, then the
mediator samples an action profile $\vec{a}$ from $\mu(\vec{t})$ and sends
$a_{i}$ to each player $i$, and then each player $i$ plays whatever it
received from the mediator. In Definition 7, the functions $\psi$ and
$\varphi$ represent possible deviations for players in $K$ in this canonical
game; $\psi$ describes how they might lie to the mediator about their type (by
sending type profile $\psi(\vec{t}_{K})$ instead of their actual type profile
$\vec{t}_{K}$), while $\varphi$ represents how they might deviate in what they
do (playing strategy profile $\varphi(\vec{a}_{K})$ instead of the strategy
profile $\vec{a}_{K}$ suggested by the mediator). Definition 7 says that $\mu$
is a $k$-resilient (resp., strongly $k$-resilient) communication equilibrium
if none of these deviations is profitable for all players (resp., for some
player) in $K$.

###  2.2 Cheap-talk games

Given a normal-form game $\Gamma=(n,A,U)$ or a Bayesian game
$\Gamma=(P,T,q,A,U)$, consider an extension $\Gamma_{\mathit{CT}}$ in which
players can communicate among themselves before playing an action in $\Gamma$.
We call this extension a _cheap-talk game_. More precisely, in a cheap-talk
game $\Gamma_{\mathit{CT}}$, players are able to exchange messages and play an
action in $\Gamma$ (although they may play an action in $\Gamma$ at most
once). The payoff of each player is defined by the utilities $U$ of $\Gamma$,
given the action profile played in $\Gamma$. In this paper we always assume
that messages are _authenticated_ , so that each recipient knows who sent the
message, and messages are never corrupted or modified.

We can view cheap-talk games as possibly infinite extensive-form games in
which the nodes are the _global histories_ $\vec{h}=(h_{1},\ldots,h_{n})$ of
the players, and the actions associated with an edge involve either performing
an internal computation (e.g., tossing a random coin or updating the local
state with the messages received), sending messages, or playing an action in
the underlying game. A global history $\vec{h}$ is just a tuple of local
histories, where the local history $h_{i}$ of player $i$ contains all internal
computations, all messages sent by $i$ and received by $i$, along with their
time stamps (in the synchronous case) or the number of times that $i$ was
scheduled since the beginning of the game (in the asynchronous case). Two
global histories $\vec{h}=(h_{1},\ldots,h_{n})$ and
$\vec{h}^{\prime}=(h_{1}^{\prime},\ldots,h_{n}^{\prime})$ are
indistinguishable by player $i$ if $h_{i}=h^{\prime}_{i}$. Analogously,
$\vec{h}$ and $\vec{h}^{\prime}$ are indistinguishable by a coalition $K$ of
players if $\vec{h}_{K}=\vec{h}^{\prime}_{K}$.

A strategy profile $\vec{\sigma}$ in a cheap-talk game $\Gamma_{\mathit{CT}}$
_induces_ a strategy profile $\vec{\tau}$ in $\Gamma$ if the outcome that
results from playing $\vec{\sigma}$ in $\Gamma_{\mathit{CT}}$ is identical to
that that results from playing $\vec{\tau}$ in $\Gamma$. If $\Gamma$ is a
normal-form game, the outcome that results from playing $\vec{\sigma}$ is the
distribution over action profiles in $\Gamma$ that results when $\vec{\sigma}$
is played in $\Gamma_{\mathit{CT}}$. If $\Gamma$ is a Bayesian game, the
outcome is a map from type profiles to distributions over action profiles
(i.e., a correlated strategy profile). A strategy profile $\vec{\sigma}$
_implements_ a strategy profile $\vec{\sigma}^{\prime}$ if $\vec{\sigma}$ and
$\vec{\sigma}^{\prime}$ induce the same strategy profiles in $\Gamma$.

Unless specified otherwise, we assume that all communication in cheap-talk
games is _synchronous_ , which means that it proceeds in rounds and that all
messages sent in a given round by each player are guaranteed to be received by
their recipient at the beginning of the next round. The analysis of
_asynchronous_ communication is done in section 6.

These definitions are illustrated by the following example.

######  Example 1.

Consider a Bayesian game $\Gamma$ with two players. Each player
$i\in\\{1,2\\}$ has a type $t_{i}\in\\{0,1\\}$ and can play actions in
$\\{0,1\\}$. If the action $a_{i}$ played by player $i$ satisfies
$a_{i}=t_{1}t_{2}$, then that player gets a utility of 1; otherwise, she gets
0\. Consider a strategy profile $\vec{\sigma}$ for the cheap-talk extension
$\Gamma_{\mathit{CT}}$ of $\Gamma$ in which each player sends its type to the
other player in the first round, then the players each locally compute
$t_{1}t_{2}$ and play it in the underlying game. It is easy to check that
$\vec{\sigma}$ is a Bayesian Nash equilibrium (both players get the maximum
possible payoff), and that it implements the correlated strategy profile that
maps a given type profile $(t_{1},t_{2})$ to the distribution that assigns
probability $1$ to $(t_{1}t_{2},t_{1}t_{2})$ and $0$ to everything else.

##  3 The main result

Given a normal-form or Bayesian game $\Gamma$, let $\Gamma_{\mathit{CT}}$ be
its cheap-talk extension and $\Gamma_{d}$ be its cheap-talk extension, where
players can also communicate with a trusted mediator $d$. Let
$SE_{k}(\Gamma_{\mathit{CT}})$ (resp., $SE_{k}(\Gamma_{d})$) denote the set of
possible strategies in $\Gamma$ induced by $k$-resilient sequential equilibria
in $\Gamma_{\mathit{CT}}$ (resp., $\Gamma_{d})$. Note that if $\Gamma$ is a
normal-form game, $SE_{k}(\Gamma_{\mathit{CT}})$ is a set of distributions
over action profiles, while if $\Gamma$ is a Bayesian game,
$SE_{k}(\Gamma_{\mathit{CT}})$ is a set of correlated strategy profiles. We
define $SE_{k}^{S}$ equivalently but for strong $k$-resilient sequential
equilibria instead.

In the rest of this paper, we consider only equilibria in which each action
profile is sampled with rational probability. The reason for this restriction
is that it is a standard assumption in distributed systems that messages have
finite length and that players cannot perform arbitrarily large operations.
This means that agents cannot encode real numbers into messages and they
cannot perform operations on real numbers, in general. If we relax these
constraints and allow players to send messages and operate with arbitrary real
numbers, our results can be extended to all equilibria inside the convex hull
of rational equilibria, using techniques due to Gerardi [2004]. These
techniques are described in Section 7.

Our main result shows that we can implement a (strongly) $k$-resilient
equilibrium with a mediator and $n$ players using cheap talk if $n>3k$.

######  Theorem 1.

If $\Gamma=(P,T,q,A,U)$ is a Bayesian game for $n$ players and $n>3k$, then
$SE_{k}(\Gamma_{\mathit{CT}})=SE_{k}(\Gamma_{d})$ and
$SE_{k}^{S}(\Gamma_{\mathit{CT}})=SE_{k}^{S}(\Gamma_{d})$.

As shown in Section 5, the sets $SE_{k}(\Gamma_{d})$ and
$SE_{k}^{S}(\Gamma_{d})$ have a relatively simple characterization. For
instance, it can be shown that if $\Gamma$ is a normal-form game, then
$SE_{k}(\Gamma_{d})$ is the set of $k$-resilient correlated equilibria of
$\Gamma$; and if $\Gamma$ is a Bayesian game, then $SE_{k}(\Gamma_{d})$ is the
set of $k$-resilient communication equilibria of $\Gamma$. (Gerardi [2004]
proved these results for $k=1$.)

###  3.1 Outline of the proof

The proof of Theorem 1 is divided into two parts. We first describe a
relatively simple strategy profile $\vec{\sigma}$ in $\Gamma_{\mathit{CT}}$
that implements the desired strategy profile in $\Gamma_{d}$ and tolerates
deviations of up to $k$ players. Moreover, with $\vec{\sigma}$, no subset of
at most $k$ players can sabotage the joint computation or learn anything other
than what they were originally supposed to learn. These security properties of
$\vec{\sigma}$ guarantee that it is a $k$-resilient Nash equilibrium.

The next step in the proof is extending $\vec{\sigma}$ to a $k$-resilient
sequential equilibrium $\vec{\sigma}^{seq}$. The key idea for doing this is
showing that there exists a belief system $b$ such that all coalitions $K$ of
at most $k$ players believe that all players that deviated from the protocol
did so by sending inappropriate messages only to players in $K$; that is, each
coalition $K$ of size at most $k$ believes that if $i,j\not\in K$, then $i$
and $j$ always send each other the messages that they are supposed to send
according to $\vec{\sigma}$. If players have belief system $b$, then all
coalitions $K$ with $|K|\leq k$ believe, regardless of their local history,
that the remaining players will always compute their part of the sequential
equilibrium correctly, since $\vec{\sigma}$ tolerates deviations by up to $k$
players and all the players not in $K$ get the messages that they are supposed
to get according to $\vec{\sigma}$ from all players except possibly those in
$K$ (and thus do not observe deviations by more than $k$ players). Moreover,
in the construction of $\vec{\sigma}$, if fewer than $k$ players deviate, all
players eventually receive enough information to compute their own action,
even if they don’t take part in the computation. These two properties are
enough to guarantee that players in $K$ cannot gain by deviating during the
communication phase, since (they believe that) nothing they can do will affect
what the remaining players play in the underlying game, and they can’t learn
any additional information.

Constructing a strategy profile that implements a given sequential equilibrium
with a mediator is in general nontrivial, since players must not only jointly
compute the action that the mediator sends to each player, but this must be
done in such a way that $i$ does not learn anything from the communication
phase other than its own action $a_{i}$. For if $i$ was able to get such
information, $i$ might be tempted to deviate (since it might have more
information about what the utility of deviating would be).

There are well-known techniques in distributed computing for constructing
protocols with the appropriate security properties. The standard solution
(which we also use) involves distributing the information about the necessary
computations between the players in such a way that each player knows only a
part or _share_ of that information. Players can thus jointly compute the
mediator’s local history and simulate everything that the mediator would do,
without leaking any information. More precisely, if a player $i$ would send
its type $t_{i}$ to the mediator in the mediator game, in the cheap-talk game
it instead shares $t_{i}$ among all players in such a way that no player (or
coalition of players) can learn anything about it. When all the types have
been distributed, players can then compute the actions that the mediator would
have sent to each player in the game with the mediator. However, each player
$i$ does not directly compute its own action $a_{i}$, but rather its share of
every action $a_{j}$. Then each player $i$ sends the share of each action
$a_{j}$ to player $j$. This guarantees that only $j$ learns $a_{j}$.

There are two standard primitives that we use in this construction,
_verifiable secret sharing_ (VSS) and _circuit computation_ (CC). Roughly
speaking, VSS takes as input a value $v$, and distributes to each player $i$ a
share $s^{i}_{v}$ of $v$. If we are interested in $k$-resilience, we can
arrange for these shares to have the property that knowing a subset of at most
$k$ shares gives no information about $v$, while knowing strictly more than
$k$ suffices to reconstruct $v$. CC is used to distribute the shares of the
output of a function for which each of the players has shares of all of its
inputs. More precisely, given a function $f:D^{t}\rightarrow D$ and $t$ values
$v_{1},\ldots,v_{t}$ such that each player $i$ knows only its own share
$s_{v_{j}}^{i}$ of $v_{j}$, for $j=1,\ldots,t$, the CC procedure takes as
inputs the shares $s_{v_{1}}^{i},\ldots,s_{v_{t}}^{i}$ of each player $i$, and
allows player $i$ to compute its share $s^{i}$ of $f(v_{1},\ldots,v_{t})$ in
such a way that no player learns any information about $v_{1},\ldots,v_{t}$.
Therefore, VSS allows players to share private values in a secret way, and CC
allows players to generate (shares of) new values without leaking any
information about all values previously shared. We define VSS and CC formally
in Appendix B, and show that, if $n>3k$, then it is possible to implement VSS
and CC in a $k$-resilient way, so that they both tolerate deviations by up to
$k$ players. In the next section, we prove Theorem 1 assuming that we can
implement VSS and CC.

##  4 Proof of Theorem 1

In this section, we prove Theorem 1 for the case of $k$-resilient sequential
equilibrium. The case of strongly $k$-resilient sequential equilibrium is
similar.

###  4.1 Constructing a $k$-resilient Nash equilibrium

By definition, $SE_{k}(\Gamma_{\mathit{CT}})\subseteq SE_{k}(\Gamma_{d})$. It
thus remains to show that a $k$-resilient sequential equilibrium with a
mediator can be implemented by a $k$-resilient sequential equilibrium in the
cheap-talk game. Let $Com_{k}(\Gamma)$ be the set of $k$-resilient
communication equilibria of $\Gamma$. As we noted in Section 3,
$SE_{k}(\Gamma_{d})=Com_{k}(\Gamma)$, and thus
$SE_{k}(\Gamma_{\mathit{CT}})\supseteq SE_{k}(\Gamma_{d})$ reduces to showing
that all $k$-resilient communication equilibria $\mu$ of $\Gamma$ can be
implemented with cheap talk without a mediator. We begin by constructing a
strategy profile $\vec{\sigma}$ in $\Gamma_{\mathit{CT}}$ that is a
$k$-resilient Nash equilibrium and induces the same correlated strategy
profile as $\mu$.

Given $\mu$, consider the canonical protocol $\vec{\sigma}_{can}$ for $n$
players and a mediator in which each player $i$ sends its type $t_{i}$ to the
mediator, and the mediator then computes the type profile $\vec{t}$ of the
players using the messages received, replacing the types of players that
didn’t send theirs by a default type $\bot$. (Since we are working in
synchronous systems for this part of the proof, the mediator can tell if a
player did not send his type.) The mediator then samples $\vec{a}\in\Delta(A)$
according to the distribution $\mu(\vec{t})$ and sends $a_{i}$ to each player
$i$. If $i$ sent its true type at the beginning of the game and receives an
action $a_{i}$ from the mediator, it plays $a_{i}$. Otherwise, it plays the
best response assuming that the remaining players are playing their part of
$\mu(\vec{t})$ (note that the best response is well-defined since both $\mu$
and the distribution $q$ of type profiles are common knowledge). It is
straightforward to check that $\vec{\sigma}_{can}$ induces the same correlated
strategy profile as $\mu$, and that $\vec{\sigma}_{can}$ is a $k$-resilient
sequential equilibrium. The details are left to the reader.

The idea for constructing $\vec{\sigma}$ is that instead of having a mediator
that receives the types of the players and then computes $\mu$, the players
perform these tasks by themselves using VSS and CC to help them simulate the
mediator: each player $i$, instead of sending its type $t_{i}$ to the
mediator, shares it among all the players using a $k$-resilient VSS
implementation. After the number of rounds needed to perform VSS, players
compute $(a_{1},\ldots,a_{n}):=\mu(t_{1},\ldots,t_{n})$ with CC, using as
input the shares of each of the types $t_{i}$. Each player $i$ then sends to
each player $j$ $i$’s share of $a_{j}$. Thus, each player $i$ can compute
$a_{i}$ without learning anything about the other players’ actions.

Note that, since $\vec{a}$ is sampled from $\mu(\vec{t})$, players are
required to randomize in a coordinated way. The problem of jointly sampling an
element from a distribution with rational probabilities over a finite set can
be reduced to the problem of sampling an integer from $[N]:=\\{1,\ldots,N\\}$
for some $N$, as the following proposition shows.

######  Proposition 1.

Given a correlated strategy profile $\mu$ with rational parameters, there
exists an integer $N$ and a function $\mu^{*}:T\times[N]\rightarrow A$ such
that, if $X_{\vec{t}}$ is the distribution over action profiles obtained from
playing $\mu^{*}(\vec{t},r)$ when $r$ is uniformly sampled from $[N]$, then
$X_{\vec{t}}=\mu(\vec{t})$ for all $\vec{t}\in T$.

###### Proof.

Fix an integer $N$ such that, for all $\vec{t}$ and all action profiles
$\vec{a}$, the probability $\mu(\vec{t})(\vec{a})$ is an integer multiple of
$1/N$. For each $\vec{t}$, partition $N$ into subsets
$C_{1}^{\vec{t}},C_{2}^{\vec{t}},\ldots,C_{m}^{\vec{t}}$ such that
$|C_{i}^{\vec{t}}|$ is proportional to the probability of
$\mu(\vec{t})(\vec{a}^{i})$ for some indexing $\vec{a}^{1},\ldots,\vec{a}^{m}$
of the action profiles. We take $\mu^{*}(\vec{t},r)$ to be $\vec{a}^{i}$ if
$r\in C_{i}^{\vec{t}}$ for some $i$. It is straightforward to check that
$\mu^{*}$ satisfies the desired properties. ∎

Players can thus compute the desired action profile using a deterministic
function $\mu^{*}$, given that they are able to jointly sample an integer
$r\in N$ uniformly at random.

We next present a formal construction of the protocol $\vec{\sigma}$ described
above. This protocol is an adaptation of the multiparty computation protocol
of Ben-Or, Goldwasser, and Wigderson [1988] to a setting in which the output
of the function must be sampled from a common distribution.

  1. Phase 1:

Each player $i$ generates a random number $r_{i}$ between $1$ and $N$
uniformly at random. Then $i$ shares $r_{i}$ and its type $t_{i}$ using a
$k$-resilient VSS procedure. If a player $i$ does not share $t_{i}$ or
$r_{i}$, then $t_{i}$ and $r_{i}$ are taken to be a default type $\bot\in
T_{i}$ and $0$, respectively.

  2. Phase 2:

For each player $j$, let $r_{j}^{i}$ be $i$’s share of $r_{j}$ and let
$t_{j}^{i}$ be $i$’s share of $t_{j}$. Each player $i$ initiates a
$k$-resilient CC of the functions $\mu^{*}_{1},\ldots,\mu^{*}_{n}$, where
$\mu^{*}_{j}(\vec{t},\vec{r})$ is the $j$th component of $\mu^{*}(\vec{t},r)$
and $r:=r_{1}+\ldots+r_{n}\bmod N$. Player $i$’s inputs for each of these CC
instances are the shares $r_{1}^{i},\ldots,r_{n}^{i}$ and
$t_{1}^{i},\ldots,t_{n}^{i}$ computed in Phase 1.

  3. Phase 3:

For each player $i$, let $o_{j}^{i}$ be $i$’s output of the CC instance of
$\mu^{*}_{j}$ (this output is $i$’s share of $\mu^{*}_{j}(\vec{t},\vec{r})$).
For each player $j$, player $i$ sends $o_{j}^{i}$ to $j$.

  4. Phase 4:

If $i$ shared its true type in Phase 1 and $i$ receives at least $2k+1$ shares
$o_{i}^{j}$ from different players such that every subset of those shares of
size $k+1$ defines the same secret $a_{i}$, $i$ plays $a_{i}$ and terminates.
Otherwise, $i$ plays a best response given its local history, assuming that
all the remaining players shared their true type and play their part of the
communication equilibrium. The optimal response depends on which was the value
$t_{i}$ that $i$ shared in Phase 1 (note that $t_{i}$ is 0 if $i$ didn’t
successfully share a type), and which shares of $o_{i}$ $i$ received from
other players. Note that these values give a posterior distribution over the
possible types of the other players and the actions that they played since $i$
is assuming that they share their true type $\vec{t}_{-i}$ and play their part
of the communication equilibrium with input $\vec{t}$.

Since the VSS and CC primitives are $k$ resilient, the protocol above is
explicitly defined in all scenarios in which at most $k$ players deviate.
However, there might be histories in which more than $k$ players deviate and
other players are not able to continue because either they didn’t receive
enough messages or the messages they received were inconsistent. (For example,
players will not able to jointly compute the functions $u_{i}^{*}$ in Phase 2
if insufficiently many players send messages. This means they won’t be able to
start Phase 3.) We extend the protocol to cover all these cases using the
following convention: if a player is not able to continue because the protocol
does not explicitly state what to do in a certain situation, the player does
not take part in subsequent phases. For instance, if a player $i$ is not able
to compute the functions $u_{i}^{*}$ in Phase 2, then $i$ does not take part
in Phase 3. Note, however, that the action played at the end of Phase 4 is
always specified even if a player doesn’t complete some of the previous
phases.

######  Proposition 2.

If $n>3k$, $\vec{\sigma}$ is a $k$-resilient Nash equilibrium and induces the
same correlated strategy profile as $\mu$.

###### Proof.

Clearly $\vec{\sigma}$ induces the same correlated strategy profile as $\mu$
by construction. The fact that $\vec{\sigma}$ is a $k$-resilient NE follows
directly from the properties of $k$-resilient VSS and $k$-resilient CC: no
matter what a coalition of at most $k$ players does, the remaining $n-k$
players are guaranteed to terminate all their VSS and CC instances correctly.
Since honest players choose $r_{i}$ uniformly at random, the number
$r:=r_{1}+\ldots+r_{n}\bmod N$ is also randomly distributed in $[N]$
regardless of what a coalition of at most $k$ players decides to share. This
guarantees that the actions $a_{1},\ldots,a_{n}$ encoded by the shares
$(o_{1}^{1},\ldots,o_{1}^{n}),\ldots,(o_{n}^{1},\ldots,o_{n}^{n})$ of honest
players are distributed according to $\mu(\vec{t})$. The correctness of the
output of each player follows from the fact that if a player $i$ waits until
receiving at least $2k+1$ shares that define the same secret $a_{i}$, at least
$k+1$ of those shares were sent by honest players and thus define the correct
value $a_{i}$ (note that if $n>3k$, all players are guaranteed to be able to
reconstruct their action $a_{i}$ in Phase 4 even if a coalition of $k$ players
deviates, since at least $2k+1$ players are honest). To complete the proof,
note that the secrecy properties of the $k$-resilient VSS and CC guarantee
that no coalition of at most $k$ players can learn anything besides their own
actions, and thus that playing the action $a_{i}$ computed in Phase 4 is
optimal. ∎

###  4.2 Constructing a $k$-resilient sequential equilibrium

Proposition 2 shows that, for all $\mu\in Com_{k}(\Gamma)$, there exists a
strategy $\vec{\sigma}$ in $\Gamma_{\mathit{CT}}$ such that $\vec{\sigma}$ is
a $k$-resilient Nash equilibrium that implements $\mu$. Our aim is to extend
$\vec{\sigma}$ to a $k$-resilient sequential equilibrium. The difficulty in
constructing such an extension is due to the fact that the $k$-resilience of
VSS and CC guarantees that no coalition of at most $k$ players can prevent the
remaining players from carrying out the VSS and CC computations if no other
player deviates (which is all that is needed to show that the construction
gives a $k$-resilient Nash equilibrium). However, it is not clear what the
coalition can accomplish starting at a point off the equilibrium path where
they detect that other players are deviating as well.

For instance, consider a normal-form game $\Gamma$ for $n$ players such that
the set of actions for each player is $[n]$. The payoffs are as follows:
$\vec{a}$, if at least $n-k$ coordinates of an action profile $\vec{a}$ are
different, then all players get a payoff of $0$; otherwise, all players get a
payoff of $1$. Consider the $k$-resilient correlated equilibrium $p$ in which
all possible permutations of $[n]$ are played with equal probability, giving
all players a payoff of 0. Suppose that players play the protocol
$\vec{\sigma}$ described in Section 4.1. If at least $n-k$ of the players are
honest, it is guaranteed by construction that all of them will play different
actions by the end of the protocol, and thus that all players will get a
payoff of 0 regardless of what the remaining $k$ players do. However, consider
the case that a coalition $K$ of at most $k$ players follows the protocol but
at some point detects an inconsistency among their local histories. Since
players in $K$ were following the protocol faithfully, it must be the case
that one of the remaining $n-k$ players deviated. If this leads the players in
$K$ to believe that there is a chance that at least two of the remaining
players played the same action $a\in[n]$, it is worthwhile for players in $K$
to deviate and play $a$ at the end of the protocol. If this is the case, then
we do not have a sequential equilibrium.

Our approach to showing that $\mu$ can be implemented with a $k$-resilient
sequential equilibrium is to show that there exists a belief system such that
all coalitions $K$ of size at most $k$ believe, regardless of their local
history, that

  * (a)

the remaining players will successfully complete their part of $\vec{\sigma}$,
no matter what the players in $K$ do;

  * (b)

players in $K$ cannot infer anything about the action profile $\vec{a}$ being
played other than their own part $\vec{a}_{K}$ (and $\mu$).

It is important to stress that property (b) does in fact depend on the beliefs
of players in $K$: If some player $i$ in $K$ receives a message $\bot$ from a
player $j$ that was not supposed to be sent on the equilibrium path, if $i$
believes that $j$ sends that message only when $j$ has type $t_{j}$ (whether
or not this is actually the case), then $i$ will believe that it has acquired
important information when it receives $\bot$, and adjust its play
accordingly. However, if $i$ believes that $j$ chose that message uniformly at
random, then $i$ will not adjust its play. The following proposition shows
that if properties (a) and (b) are satisfied, then $\vec{\sigma}$ is
$k$-sequentially rational (i.e., it is never in the interest of coalitions of
size at most $k$ to deviate from $\vec{\sigma}$).

######  Proposition 3.

If $b$ is a belief system compatible with $\vec{\sigma}$ that satisfies
properties (a) and (b), then $(\vec{\sigma},b)$ is a $k$-resilient sequential
equilibrium.

###### Proof.

If $b$ satisfies property (a), then at all nodes in the game tree (including
nodes off the equilibrium path), no matter what the players in $K$ do, the
remaining players will eventually terminate their part of $\vec{\sigma}$ and
thus sample an action profile $\vec{a}\in\mu(\vec{t})$ and play their part
$\vec{a}_{-K}$. Property (a) also guarantees that by the end of Phase 4 (and
the end of the communication phase), players not in $K$ will send the shares
of $\vec{a}_{K}$ to players in $K$, which means that players in $K$ believe
that they will always learn $\vec{a}_{K}$. Property (b) guarantees that
players in $K$ won’t learn anything besides their own actions. Properties (a)
and (b) together imply that players in $K$ believe that they cannot prevent
the remaining players from playing their part of an action profile $\vec{a}$
sampled according to $\mu$, and that players in $K$ will eventually learn
$\vec{a}_{K}$ and nothing else. Since $\mu$ is a $k$-resilient communication
equilibrium, it is always a best response for the players in $K$ to share
their own type in Phase 1, as long as they can continue the basic protocol.
Similar arguments show that following the basic protocol if they can (i.e.,
they receive messages enough consistent with the protocol) is a best response
in phases 2 and 3. Moreover, it also follows from properties (a) and (b) that,
since the players in $K$ cannot influence the outcome, doing nothing is a best
response if they cannot continue the basic protocol (in all phases). It
remains to show that the action played in Phase 4 is optimal. By construction,
this reduces to showing that if a coalition $K$ of players with $|K|\leq k$
shared their true type in Phase 1 and were able to compute their actions
$a_{i}$ in Phase 4, it is optimal for them to play $a_{i}$ (note that
otherwise $i$ is already best responding given that the belief system $b$
satisfies properties (a) and (b)). This follows from the fact that, by
properties (a) and (b), players in $K$ believe that all remaining players
computed $\vec{a}$ and thus played $\vec{a}_{-K}$. Since $\mu$ is a
$k$-resilient communication equilibrium, it is then always in the interest of
players in $K$ to play $\vec{a}_{K}$. ∎

Proposition 3 shows that Theorem 1 reduces to finding a belief system $b$
compatible with $\vec{\sigma}$ that satisfies properties (a) and (b). We start
by showing how such a belief system can be constructed for a fixed subset $K$
with $|K|\leq k$. Consider the sequence
$\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ of strategy profiles in which
player $i$ proceeds as follows with $\vec{\sigma}^{m}_{i}$: Given local
history $h_{i}$, $i$ does exactly what it would have done with $\vec{\sigma}$,
except that if it is supposed to send a message $msg$ to another player $j$,
if $j\in K$, with probability $1/m$ it replaces $msg$ by a random message
$msg^{\prime}$ sampled according to some fixed distribution that gives all
messages positive probability, and sends $msg^{\prime}$ instead. If $j\not\in
K$, $i$ replaces $msg$ with $msg^{\prime}$ with probability $m^{-m}$. That is,
players play as in $\vec{\sigma}$, except that they may lie to players in $K$
with a low probability, and to players outside of $K$ with a much lower
probability. By construction, each $\vec{\sigma}^{m}$ is completely mixed and
the belief $b$ induced by the limits of the beliefs in
$\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ satisfies the properties (a) and
(b) described above for the set $K$. To see this, note that property (a) is
satisfied because players in $K$ believe that the remaining $n-k$ players are
being truthful between themselves (note that the probability of anyone lying
to a player not in $K$ is negligible) and thus, since the VSS and CC
implementations are $k$-resilient, that they can carry out all the necessary
computations without the help of players in $K$. Moreover, since players in
$K$ believe that if they get a message incompatible with $\vec{\sigma}$ (i.e.,
a message that could not have been according to $\vec{\sigma}$, given their
joint histories), then they are getting a message drawn from some fixed
distribution, they learn no useful information about the action profile being
played by getting this message. Property (b) follows.

This example shows how to construct a $k$-belief system compatible with
$\vec{\sigma}$ that satisfies properties (a) and (b) for a particular subset
$K$ with $|K|\leq k$, but it unfortunately does not satisfy these properties
for all such sets simultaneously. Note that it is critical that players in $K$
believe that they are the only ones being lied to, and also that the lies sent
to players in $K$ convey no information since they do not depend on the
senders’ local histories (in the example, they are sampled from a fixed
distribution). The next definitions generalizes these ideas:

######  Definition 8.

Given history $h_{i}$ of player $i$, a message $msg$ in $h_{i}$ from $i$ to
$j$ is a _lie_ if it is incompatible with $\vec{\sigma}$. A subset $K$ of
players is _truthful relative to $\vec{\sigma}$ in global history $\vec{h}$_
if, in $\vec{h}$, no player in $K$ ever _lies_ (i.e., sends a message that is
a lie) to another player in $K$.

Note that since the local history $h_{i}$ of player $i$ includes all of $i$’s
randomization up to the point where it is supposed to send a message, given
local history $h_{i}$, there is a unique message sent by $i$ to $j$ that is
compatible with $\vec{\sigma}$, even if $\vec{\sigma}$ is a mixed strategy
(intuitively, when $i$ sends a message to $j$, all of $i$’s coins have already
been tossed and their outcomes appear in $i$’s history). A message from player
$i$ to player $j$ in local history $h_{i}$ is _correct_ if it is not a lie
(relative to the protocol $\vec{\sigma}$).

######  Definition 9 ($k$-paranoid belief system).

Given a $k$-belief system $b$ and the local histories $\vec{h}_{K}$ of a
subset $K$ of players, a global history $\vec{h}$ is _$b$ -consistent_ with
$\vec{h}_{K}$ if the probability according to $b$ that players have global
history $\vec{h}$ conditional on players in $K$ having history $\vec{h}_{K}$
is non-zero. Given a protocol $\vec{\sigma}$, a $k$-belief system $b$ is _$k$
-paranoid_ if

  * (1)

for all subsets $K\subseteq[n]$ with $|K|\leq k$ and all histories
$\vec{h}_{K}$ of players in $K$, in all histories $\vec{h}$ that are
$b$-consistent with $\vec{h}_{K}$, the set $\overline{K}$ of players is
truthful relative to $\vec{\sigma}$ (where $\overline{K}$ is the complement of
$K$);

  * (2)

there exists a sequence $\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ of
protocols that induces $b$ such that the lies relative to $\vec{\sigma}$ sent
in $\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ do not depend on the players’
local histories.

Intuitively, a $k$-belief system is $k$-paranoid if all subsets of at most $K$
players believe, regardless of their local history, that they are the only
ones being lied to, and also that the lies received convey no information. Our
earlier discussion provides a proof of the following proposition.

######  Proposition 4.

Let $\vec{\sigma}$ be the protocol presented in Section 4.1. If $b$ is a
$k$-paranoid belief system consistent with $\vec{\sigma}$, then $b$ satisfies
properties (a) and (b).

Thus, by Proposition 3, Theorem 1 reduces to find a $k$-paranoid belief system
$b$ that is consistent with $\vec{\sigma}$. The first candidate for generating
such a belief system is the sequence
$\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ of strategy profiles mentioned
earlier, except that with strategy $\sigma_{i}^{m}$, rather than player $i$
lying to player $j$ with probability $1/m$ if $j$ is in some fixed set $K$ and
with probability $m^{-m}$ if $j$ is not in $K$, now $i$ lies to all players
with probability $1/m$. We might hope that if players detect that they
received inappropriate messages, they would assume that they are the only ones
being lied to, since lies are highly unlikely. For instance, if a player $i$
receives four inconsistent messages, we would hope that $i$ would believe that
these are the only lies. Unfortunately, this is not necessarily the case. If
an earlier lie by some other player could result in players sending these
messages to $i$ according to $\vec{\sigma}$, then $i$ would instead believe
that there was only one lie. To prevent this, we want players to believe that
earlier lies are much less likely than later lies. It turns out that if we do
this, then we can get the result that we want.

######  Proposition 5.

For all strategies $\vec{\sigma}$ in $\Gamma_{\mathit{CT},syn}$, there exists
a $k$-paranoid belief system $b$ that is consistent with $\vec{\sigma}$.

###### Proof.

Consider the sequence
$\vec{\sigma}^{1},\vec{\sigma}^{2},\vec{\sigma}^{3},\ldots$ of strategy
profiles where in $\vec{\sigma}^{n}$ players act exactly as they do in
$\vec{\sigma}$, except that whenever $i$ would send a message $msg$ to another
player $j$, with probability $m^{-\left((2n)^{-r}\right)}$ (where $r$ is the
current round of communication), $i$ replaces this message by a message
$msg^{\prime}$ chosen according to some fixed distribution and sends
$msg^{\prime}$ instead. Intuitively, these are protocols where each player
lies to other players with a probability that (greatly) increases with the
round number and that decreases with $m$. It is straightforward to check that
$\vec{\sigma}^{1},\vec{\sigma}^{2},\vec{\sigma}^{3},\ldots$ converges to
$\vec{\sigma}$. Let $b$ be the belief system induced by the sequence. We want
to show that $b$ is $k$-paranoid. By construction, $b$ satisfies property (2)
of Definition 9 since lies in
$\vec{\sigma}^{1},\vec{\sigma}^{2},\vec{\sigma}^{3},\ldots$ are sampled from a
fixed distribution. To show that it also satisfies property (1), we need some
preliminary lemmas.

Given a global history $\vec{h}$ of $\vec{\sigma}$, let $L(\vec{h})$ be the
sequence $(\ell_{1},\ell_{2},\ldots,\ell_{R})$, where $R$ is the total number
of communication rounds in $\vec{h}$ and $\ell_{r}$ is the number of lies sent
at round $r$ in $\vec{h}$.

######  Lemma 1.

If $P^{m}$ is the probability on global histories induced by
$\vec{\sigma}^{m}$, and $\vec{h}$ and $\vec{h}^{\prime}$ are global history
profiles such that $L(\vec{h})<L(\vec{h}^{\prime})$ in lexicographical order
(the smaller sequence is the one that has the smaller value in the first
position in which they differ), then
$\lim_{m\rightarrow\infty}\frac{P^{m}(\vec{h}^{\prime})}{P^{m}(\vec{h})}=0$.

###### Proof.

If $L(\vec{h})=(\ell_{1},\ell_{2},\ldots,\ell_{R})$, then

$\log(P^{m}(\vec{h}))=-\log(m)\left(\sum_{r=1}^{n}\ell_{r}(2n)^{-r}\right)+\Theta(1),$

where $\Theta(1)$ denotes an expression that is bounded by some constant.
Thus, if $L(\vec{h})=(\ell_{1},\ell_{2},\ldots,\ell_{R})$ and
$L(\vec{h}^{\prime})=(\ell^{\prime}_{1},\ldots,\ell^{\prime}_{R^{\prime}})$,
we must show that if $L(\vec{h})<L(\vec{h}^{\prime})$, then
$\sum_{r=1}^{R^{\prime}}\ell_{r}(2n)^{-r}<\sum_{r=1}^{R^{\prime}}\ell^{\prime}_{r}(2n)^{-r}$,
which is equivalent to showing that
$\sum_{r=1}^{\max(R,R^{\prime})}(\ell^{\prime}_{r}-\ell_{r})(2n)^{-r}>0$
(taking the elements beyond the end of a sequence to be 0).

Since each player sends exactly one message to each other player, we have that
$0\leq\ell_{i}\leq n$. Therefore, if $r^{*}$ is the first round such that
$\ell^{\prime}_{r}\not=\ell_{r}$, we have that

$\sum_{r=1}^{\max(R,R^{\prime})}(\ell^{\prime}_{r}-\ell_{r})(2n)^{-r}\geq(2n)^{-r^{*}}-n\sum_{r=r^{*}+1}^{\max(R,R^{\prime})}(2n)^{-r}=(2n)^{-r^{*}}\left(1-n\sum_{r=1}^{\max(R,R^{\prime})-r^{*}}(2n)^{-r}\right),$

and

$1-n\sum_{r=1}^{\max(R,R^{\prime})-r^{*}}(2n)^{-r}>1-n\sum_{r>0}(2n)^{-r}>1-n\sum_{r>0}2^{-r}n^{-1}=0$

∎

######  Lemma 2.

If $|K|\leq k$ and $\vec{h}_{K}^{*}$ is a local history of the players in $K$,
then for every global history profile $\vec{h}$ such that $\overline{K}$ is
not truthful in $\vec{h}$,

$\lim_{m\rightarrow\infty}P^{m}(\vec{h}\mid\vec{h}_{K}^{*})=0.$

###### Proof.

Suppose that for some global history $\vec{h}$,
$P^{m}(\vec{h}\mid\vec{h}_{K}^{*})>0$ and $\overline{K}$ is not truthful in
$\vec{h}$. Since

$P^{m}(\vec{h}\mid\vec{h}_{K}^{*})=\frac{P^{m}(\vec{h})}{\sum_{\vec{h}^{\prime}:\vec{h}^{\prime}_{K}=\vec{h}_{K}^{*}}P^{m}(\vec{h}^{\prime})},$

by Lemma 1, this result reduces to finding a global history $\vec{h}^{\prime}$
such that $\vec{h}^{\prime}_{K}=\vec{h}_{K}$ and
$L(\vec{h}^{\prime})<L(\vec{h})$. This history can be constructed as follows:
suppose that $r$ is the first round in $\vec{h}$ where a player
$i\in\overline{K}$ lies to another player $j\in\overline{K}$. Consider a
history $\vec{h}^{\prime}$ in which players in $K$ perform the same internal
computations and send exactly the same messages as in $\vec{h}$, but players
in $\overline{K}$ only do so until round $r-1$. In round $r$, players in
$\overline{K}$ perform exactly the same internal computations as in $\vec{h}$
and send the same messages to players in $K$, but they send to other players
in $\overline{K}$ the _correct_ messages (i.e., the messages players in
$\overline{K}$ were supposed to send according to the protocol). Notice that
since a player $i$’s local history includes the random bits that the players
needs, there is a unique correct message, even if player $i$ is uses a
randomized protocol. From round $r+1$ on, players in $\overline{K}$ send
players in $K$ exactly the same messages as in $\vec{h}$. Clearly, by
construction, $\vec{h}^{\prime}_{K}=\vec{h}_{K}$. Let
$L(\vec{h})=(\ell_{1},\ell_{2},\ldots,\ell_{R})$ and
$L(\vec{h}^{\prime})=(\ell^{\prime}_{1},\ell^{\prime}_{2},\ldots,\ell^{\prime}_{R})$.
Then $\ell_{i}=\ell^{\prime}_{i}$ for all $i<r$, since players have the same
local histories in $\vec{h}$ and $\vec{h}^{\prime}$ for the first $r-1$ rounds
of communication, and they also send exactly the same messages. A similar
argument shows that, for all $r^{\prime}\geq r$, the players in $K$ tell
identical lies in round $r^{\prime}$ in both $h$ and $\vec{h}^{\prime}$.
Finally, note that strictly fewer lies are told by players in $\overline{K}$
in round $r$ of $\vec{h}^{\prime}$ than in round $r$ of $\vec{h}$, since the
players in $\overline{K}$ have exactly the same local history in both
$\vec{h}$ and $\vec{h}^{\prime}$, send exactly the same messages to players in
$K$ in both, but in $\vec{h}^{\prime}$ they tell no lies to each other
whereas, by assumption, there is at least one such lie told in $\vec{h}$.
Thus, $\ell^{\prime}_{r}<\ell_{r}$, and $L(\vec{h}^{\prime})<L(\vec{h})$ as
desired. ∎

This shows that $b$ satisfies property (1) of Definition 9, and thus that $b$
is a $k$-paranoid belief system consistent with $\vec{\sigma}$, completing the
proof of Proposition 5. ∎

##  5 Characterization of $SE_{k}(\Gamma_{d})$ and $SE_{k}^{S}(\Gamma_{d})$

In this section we characterize the sets $SE_{k}(\Gamma_{d})$, and
$SE_{k}^{S}(\Gamma_{d})$ (note that, by Theorem 1, the characterization of
$SE_{k}(\Gamma_{\mathit{CT}})$ and $SE_{k}^{S}(\Gamma_{\mathit{CT}})$ is
identical if $n>3$.) If $\Gamma$ is a normal-form game, let $CE_{k}(\Gamma)$
denote the set of possible distributions over action profiles induced by a
$k$-resilient correlated equilibrium in $\Gamma$; if $\Gamma$ is a Bayesian
game, let $Com_{k}(\Gamma)$ denote the set of possible maps from type profiles
to distributions over action profiles induced by $k$-resilient communication
equilibria in $\Gamma$. We also denote by $CE_{k}^{S}(\Gamma)$ the set of
possible distributions over action profiles induced by a strongly
$k$-resilient correlated equilibrium in $\Gamma$. $Com_{k}^{S}(\Gamma)$ and
$SE_{k}^{S}(\Gamma)$ are defined analogously.

The first characterization shows that, if $\Gamma$ is a normal-form game, then
$SE_{k}(\Gamma_{d})$ is the set of $k$-resilient correlated equilibria of
$\Gamma$ and $SE_{k}^{S}(\Gamma_{d})$ is the set of strongly $k$-resilient
correlated equilibria of $\Gamma$.

######  Proposition 6.

If $\Gamma=(P,A,U)$ is a normal-form game for $n$ players, then
$SE_{k}(\Gamma_{d})=CE_{k}(\Gamma)$ and
$SE_{k}^{S}(\Gamma_{d})=CE_{k}^{S}(\Gamma)$ for all $k\leq n$.

###### Proof.

Clearly, the distribution over actions induced by a $k$-resilient sequential
equilibrium (resp., strongly $k$-resilient sequential equilibrium)
$\vec{\sigma}$ in $\Gamma_{d}$ is also a $k$-resilient correlated equilibrium
(resp., strongly $k$-resilient correlated equilibrium) of $\Gamma$, for
otherwise there exists a coalition $K$ of at most $k$ players such that all
(resp., some) members of the coalition can increase their utility by deviating
from $\vec{\sigma}$ by playing a different action in the underlying game. For
the opposite inclusion, observe that all $k$-resilient (resp., strongly
$k$-resilient) correlated equilibria $p$ of $\Gamma$ can be easily implemented
with a mediator the mediator samples an action profile $\vec{a}$ following
distribution $p$ and gives $a_{i}$ to each player $i$. Then each player $i$
plays whatever is sent by the mediator. ∎

Theorem 1 and Proposition 6 together imply the following corollary:

######  Corollary 1.

If $\Gamma=(P,A,U)$ is a normal-form game for $n$ players and $n>3k$, then
$SE_{k}(\Gamma_{\mathit{CT}})=CE_{k}(\Gamma)$ and
$SE_{k}^{S}(\Gamma_{\mathit{CT}})=CE_{k}^{S}(\Gamma)$.

For Bayesian games, we can show that the set of sequential equilibria in
$\Gamma_{d}$ is equal to the set of communication equilibria of $\Gamma$.

######  Proposition 7.

If $\Gamma=(P,T,q,A,U)$ is a Bayesian game for $n$ players and $n\geq k$, then
$SE_{k}(\Gamma_{d})=Com_{k}(\Gamma)$ and
$SE_{k}^{S}(\Gamma_{d})=Com_{k}^{S}(\Gamma)$ .

###### Proof.

Suppose that $\vec{\sigma}$ is a $k$-resilient (resp., strongly $k$-resilient)
sequential equilibrium of $\Gamma_{d}$. Then the correlated strategy profile
$\mu$ induced by $\vec{\sigma}$ in $\Gamma$ must be a $k$-resilient (resp.,
strongly $k$-resilient) communication equilibrium. If $\mu$ is not a
$k$-resilient (resp., strongly $k$-resilient) communication equilibrium, then
there exists a coalition $K$ of players with $|K|\leq k$ and two functions
$\psi:T_{K}\rightarrow T_{K}$ and $\varphi:A_{K}\rightarrow A_{K}$ such that
the inequality of Definition 7 does not hold for some (resp., for all) $i\in
K$. It follows that if agents in $\Gamma_{d}$ $K$ play $\vec{\sigma}$ as if
they had type profile $\psi(\vec{t}_{K})$ instead of their true types, and
then play action $\varphi(\vec{a}_{K})$ instead of the action profile
$\vec{a}_{K}$, the utility of all (resp., some) agents would strictly
increase, which contradicts the assumption that $\vec{\sigma}$ is a
$k$-resilient (resp., strongly $k$-resilient) sequential equilibrium of
$\Gamma_{d}$. For the opposite inclusion, recall from the discussion after
Definition 7 that we can identify a correlated strategy profile $\mu$ in
$\Gamma$ with a canonical strategy $\vec{\sigma}$ in $\Gamma_{d}$ in which
players tell the mediator their type and the mediator computes which action
profile they should play according to $\mu$. If $\mu$ is a $k$-resilient
(resp., strongly $k$-resilient) communication equilibrium, then the canonical
strategy $\vec{\sigma}$ is a $k$-resilient (resp., strongly $k$-resilient)
sequential equilibrium of $\Gamma_{d}$ that induces $\mu$ (see the discussion
after Definition 7 for details). ∎

Theorem 1 and Proposition 7 together imply the following:

######  Corollary 2.

If $\Gamma=(P,T,q,A,U)$ be a Bayesian game for $n$ players and $n>3k$, then
$SE_{k}(\Gamma_{\mathit{CT}})=Com_{k}(\Gamma)$ and
$SE_{k}^{S}(\Gamma_{\mathit{CT}})=Com_{k}^{S}(\Gamma)$ .

##  6 The asynchronous setting

Up to this point, as in the game-theory literature, we assumed that the
communication between players proceeded in synchronous rounds. That is, at
each round $t$, all the players send messages to each other player (we
identify not sending a message with sending a special message $\bot$) and
these messages are received by their intended recipients before the beginning
of round $t+1$. The assumption that we identify not sending a message with
sending $\bot$ is made without loss of generality—player $j$ can tell if
player $i$ has not sent her a message. Moreover, it is typically assumed when
analyzing games with mediators and communication games that it is common
knowledge when the communication phase ends and that, after it ends, all the
players simultaneously move in the underlying game. We call this the
_synchronous_ setting.

In this section, we consider an _asynchronous_ setting that is quite standard
in the distributed computing literature. In the asynchronous setting, there is
no global notion of time, and messages may take arbitrary amounts of time to
be delivered (although we do assume that all messages are eventually
delivered). Thus, we can no longer identify not sending a message with sending
$\bot$; if $j$ has not received a message from player $i$, $j$ is not sure if
this is because $i$ did not send $j$ a message or if $i$ sent a message that
has not yet been delivered. For ease of exposition, we assume that message
delivery is under the control of a _scheduler_ , who also decides when each
player gets to move, with the guarantee that all players eventually get to
move if they want to move. More precisely, in an asynchronous setting, the
players and the scheduler alternate turns. During a player’s turn, it receives
all the messages delivered to it by the scheduler since its last turn; it may
also perform additional computation and send messages to other players (note
that these messages are not received until they are delivered by the scheduler
to their recipients). When the player finishes all necessary operations and
sends all the necessary messages, it ends its turn, at which point it become’s
the scheduler’s turn. During its turn, the scheduler can deliver messages that
have been sent but not yet delivered, or it may schedule a player. If the
scheduler schedules player $i$, the scheduler’s turn ends and $i$’s turn
begins.

What internal computations a player $i$ performs, what messages $i$ sends, and
to which players $i$ sends messages during its turn is dictated by $i$’s
strategy, which is a function from $i$’s local history to operations and
messages (i.e., a strategy tells a player what to do as a function of its
local history). Note that $i$’s local history is simply an ordered list
containing, for each time that $i$ was scheduled, the messages that $i$ sent
and received, and the internal computations that $i$ performed. (We can
represent this as a game, in which case we would identify each information set
of $i$ with a local history.) Note that $i$ does not in general know how many
times another player $j$ has been scheduled since $i$’s last turn.

The scheduler’s behavior is also encoded in its strategy, which describes
which messages the scheduler delivers and which players are scheduled, as a
function of the scheduler’s local history. The scheduler’s local history is
again an ordered list, which includes which players have been scheduled up to
that point and which messages have been delivered. Note that the scheduler
does not know the contents of the messages sent by the players, but it can
still identify the messages by, for instance, labelling them by the order they
were sent. For example, an entry in the scheduler’s local history could be
“delivered player 3’s fourth message”. The only constraint on the scheduler’s
strategy is that it must eventually deliver all messages that have been sent
and, starting from any local history, it must eventually schedule all players
that have not terminated. (We assume that “done” is a signal that a player can
send the scheduler that indicates that it has terminated.)

If $\Gamma_{\mathit{CT}}$ is asynchronous, the payoff of the players may
depend on the strategy $\sigma_{e}$ of the scheduler. This means that the
definition of implementation and of the solution concepts must take the
scheduler into account. We extend the definitions of Nash equilibrium,
correlated equilibrium, sequential equilibrium, and communication equilibrium
by requiring that the relevant inequality holds for all choices of
$\sigma_{e}$. For example a strategy profile $\vec{\sigma}$ is a Nash
equilibrium in an asynchronous setting if, for all $i\in P$, all strategies
$\tau_{i}$ for player $i$, and all schedulers $\sigma_{e}$,
$u_{i}(\vec{\sigma},\sigma_{e})\geq
u_{i}(\tau_{i},\vec{\sigma}_{-i},\sigma_{e})$. Since the action profile played
might depend on the scheduler, a strategy $\vec{\sigma}$ in
$\Gamma_{\mathit{CT}}$ might induce more than one strategy in $\Gamma$ (see
Example 2 below). A strategy profile $\vec{\sigma}$ for $\Gamma_{\mathit{CT}}$
_implements a set $S$ of strategy profiles in $\Gamma$_ in an asynchronous
setting if (a) for every scheduler $\sigma_{e}$ in $\Gamma_{\mathit{CT}}$, the
outcome obtained when playing $\vec{\sigma}$ with scheduler $\sigma_{e}$ is
the same as that obtained when playing some strategy profile in $S$, and (b)
for every strategy profile $\vec{\tau}$ in $S$, there exists a scheduler
$\sigma_{e}$ such that the outcome obtained when playing $\vec{\sigma}$ with
$\sigma_{e}$ is the same as that obtained when playing $\vec{\tau}$.
Intuitively, $\vec{\sigma}$ implements $S$ if the set of outcomes that result
from playing $\vec{\sigma}$ with different choices of scheduler are precisely
those that result from playing strategy profiles in $S$. As in the synchronous
setting, if $\Gamma$ is a normal-form game, we take the strategy profiles in
$S$ to consist of distributions over action profiles in $\Gamma$, while if
$\Gamma$ is a Bayesian game, the strategy profiles in $S$ are correlated
strategy profiles.

In cheap-talk games in synchronous systems, we assumed (as is standard in the
literature) that the game tree is finite and at the last move on a path, the
players play an action in the underlying game; we take the utility of a leaf
to be the utility of the corresponding action profile in the normal-form game.
We cannot assume this in asynchronous systems. Indeed, in asynchronous
systems, to allow for players who deviate from an equilibrium, we must
consider game trees with infinite paths. For example, a player $i$ may wait
forever for a message that never arrives, because the sender deviated and
never sent it, so $i$ may never play an action in the underlying game. We must
thus define what the payoffs are on infinite paths and at the leaf of a finite
path where some players do not play an action in the underlying game. This
amounts to treating players who have not played an action as, in fact, having
played some action. The two main approaches for doing this are the _default-
move approach_ Abraham et al. [2019b], where if player $i$ never plays an
action in the underlying game, its action is sampled from a default
distribution, and the _Aumann and Hart_ (AH) approach Aumann and Hart [2003],
where the action played by $i$ is some function of $i$’s local history. The AH
approach essentially assumes that players can leave a “will” defining the
action in the underlying game that they should play if they never actually
play an action in the underlying game while playing the cheap-talk game. In
the asynchronous setting (with both the AH and the default move approach), we
say that a strategy profile $\vec{\sigma}$ in $\Gamma_{\mathit{CT}}$
_implements_ a strategy profile $\vec{\tau}$ in $\Gamma$ if the set of
strategy profiles implemented by $\vec{\sigma}$ (for different choices of
scheduler) is $\\{\vec{\tau}\\}$ (thus, playing $\vec{\sigma}$ results in the
same outcome no matter what the scheduler does).

The following example illustrates some of the new subtleties that asynchrony
introduces.

######  Example 2.

Let $\Gamma$ be a normal-form game for $n$ players where the set of actions is
$\\{1,2,\ldots,n\\}$, and let $\Gamma_{d,asyn}$ be a cheap-talk extension of
$\Gamma$ in the asynchronous setting, where there is a trusted mediator $d$
and the AH approach is used. Suppose that $\vec{\sigma}$ is the strategy
profile that proceeds as follows: each player sends an empty message to the
mediator when they are first scheduled. The mediator waits until it receives a
message, and then sends a message to all players with the index of the player
whose message was received first. When a player $j$ receives a message from
the mediator with a number $i\in\\{1,2,\ldots,n\\}$, player $j$ plays action
$i$. If player $j$ never receives a message from the mediator, then according
to its will, $j$ plays action $j$. The player whose index appears the most
often in the resulting action profile receives a payoff of 1 (if there are
ties, they all get 1), while the remaining players get 0.

This game can be viewed as a race. The player whose message gets to the
mediator first receives a payoff of 1 while the rest receive 0. Note that,
regardless of the scheduler, all players play the same action in $\Gamma$.
However, the scheduler decides which action is played. Thus, the strategy
$\vec{\sigma}$ in the example implements the set of strategies
$\\{(1,1\ldots,1),(2,2,\ldots,2),\ldots,(n,n,\ldots,n)\\}$. This strategy is
not a Nash equilibrium. To see this, consider the scheduler $\sigma_{e}$ that
schedules the players sequentially (first player 1, then player 2, and so on).
If player $i$ sends two messages to the mediator and is the only player to do
so, then the scheduler delivers $i$’s first message before it delivers any
other player’s message. If more than one player sends two messages to the
mediator, the schedulers chooses one of these players at random and delivers
her message first. The remaining messages are delivered in some random order.
With this scheduler, the players benefit by deviating and sending two messages
to the mediator instead of just one. Thus, $\vec{\sigma}$ is not a Nash
equilibrium. A similar argument can be used to show that, for all games
$\Gamma$, if $\vec{\sigma}$ is a $k$-resilient Nash equilibrium in
$\Gamma_{\mathit{CT}}$, then the payoffs of the players when playing
$\vec{\sigma}$ cannot depend on the scheduler (see Abraham et al. [2019b]).

This example shows that in asynchronous systems, the set of possible
deviations is much larger than in synchronous systems. However, there are
cases where controlling the scheduling of the messages and players does not
give that much power to an adversary. For instance, if we consider an
asynchronous cheap-talk extension of Example 1, the strategy profile in which
both agents send their type to each other the first time they are scheduled
and play action $t_{1}t_{2}$ is a Nash equilibrium (note that this is almost
equivalent to the strategy proposed in Example 1, however there is no notion
of “rounds” in an asynchronous setting). Many of the results that hold in the
synchronous case also hold in the asynchronous case, but may require a larger
proportion of the players to be honest. For instance, asynchronous multiparty
secure computation tolerates deviations by at most a quarter of the agents,
while synchronous multiparty secure computation tolerates deviations by at
most a third Ben-Or et al. [1988, 1993]. Our results hold for similar bounds.
(An intuitive explanation of why there is a difference between the thresholds
for the synchronous and asynchronous settings can be found in Appendix B.)

###  6.1 Main results

Given a normal-form or Bayesian game $\Gamma$, let $\Gamma_{\mathit{CT},asyn}$
and $\Gamma_{d,asyn}$ be the asynchronous equivalents of
$\Gamma_{\mathit{CT}}$ and $\Gamma_{d}$ respectively (i.e., the asynchronous
cheap-talk and mediator extensions of $\Gamma$). As in Section 3, let
$SE_{k}(\Gamma_{\mathit{CT},asyn})$ (resp.,
$SE_{k}^{S}(\Gamma_{\mathit{CT},asyn})$) denote the set of possible strategy
profiles in $\Gamma$ induced by $k$-resilient sequential equilibria in
$\Gamma_{\mathit{CT},asyn}$. However, since in the asynchronous setting the
outcome may depend on the scheduler (see the discussion in Section 6), if
$\Gamma$ is a normal-form game, then $SE_{k}(\Gamma_{\mathit{CT},asyn})$ is a
set of sets of strategy profiles, and if $\Gamma$ is a Bayesian game, then
$SE_{k}(\Gamma_{\mathit{CT},asyn})$ is a set of sets of correlated strategy
profiles.

In the asynchronous setting we have equivalent results to those in the
synchronous setting.

######  Theorem 2.

If $\Gamma=(P,T,q,A,U)$ is a Bayesian game for $n$ players and $n>4k$, then
$SE_{k}(\Gamma_{\mathit{CT},asyn})=SE_{k}(\Gamma_{d,asyn})$ and
$SE_{k}^{S}(\Gamma_{\mathit{CT},asyn})=SE_{k}^{S}(\Gamma_{d,asyn})$ with both
the default move and AH approaches.

Note that the only difference with respect to Theorem 1, is that in the
asynchronous setting we require that $n>4k$ instead of $n>3k$. This difference
comes down to the fact that, in the asynchronous setting, players cannot tell
if a message has not been received because the player didn’t send it or
because the message is being delayed by the scheduler. In fact, this is the
reason why most of the distributed computing primitives in asynchronous
systems are resilient to deviations of up to a fourth of the players, as
opposed to a third in the synchronous case (see Appendix B for more details).

As in the synchronous case, $SE_{k}(\Gamma_{\mathit{CT},asyn})$ and
$SE_{k}^{S}(\Gamma_{\mathit{CT},asyn})$ have a relatively simple
characterization. This is described in Section 6.3.

###  6.2 Proof of Theorem 2 (outline)

The proof of Theorem 2 is quite similar to the proof of Theorem 1. Given a
strategy profile $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}\in
SE_{k}(\Gamma_{d,asyn})$, we first construct a $k$-resilient Nash equilibrium
$\vec{\sigma}$ that implements $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ and
guarantees that, if less than $k$ players deviate, all players will eventually
be able to compute the action that they should play, and then we construct a
$k$-paranoid belief system $b$ that is consistent with $\vec{\sigma}$ just as
in the proof of Theorem 1. An argument similar to the one used in the
synchronous case shows that $(\vec{\sigma},b)$ is indeed a $k$-resilient
sequential equilibrium. The only major difference between the synchronous and
the asynchronous case is that, in an asynchronous system, constructing a
$k$-resilient Nash equilibrium $\vec{\sigma}$ that implements
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ is far more complicated than in a
synchronous system (the reason for this can be found below), and is beyond the
scope of this work. In this paper, we only provide a very high-level overview
of the construction used in Geffner and Halpern [2021] and Abraham et al.
[2019b] that satisfies all the properties we need. As in the case of Theorem
1, we prove Theorem 2 for the case of $k$-resilient sequential equilibrium.
The case of strongly $k$-resilient equilibrium is analogous.

As discussed in Section 3, in general, there is no simple description of
$SE_{k}(\Gamma_{d,asyn})$; thus, the proof of Theorem 2 consists of showing
that arbitrary interactions $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ with a
trusted mediator in the asynchronous setting can be emulated by a strategy
$\vec{\sigma}$ without the mediator that tolerates deviations of coalitions of
size at most $k$. We proceed as in the proof of Theorem 1: we first construct
a $k$-resilient Nash equilibrium $\vec{\sigma}$ that implements
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$, and then we construct a
$k$-paranoid belief system to extend the Nash equilibrium to a $k$-resilient
sequential equilibrium $\vec{\sigma}_{seq}$. The main problem is that the
construction of a $k$-resilient Nash equilibrium is not as simple as in the
synchronous setting. The communication between the players and the mediator
can be arbitrarily convoluted (as opposed to the players just sending their
types and receiving their suggested action), and it may depend on the
scheduler. This means that, to be sure that all possible cases are considered,
players in $\vec{\sigma}$ must somehow be able to simulate all possible
scheduling orders for the players and the messages in
$\vec{\sigma}^{\prime}+\sigma_{d}$. (In a given run, the particular order that
they choose must depend on the actual scheduler in $\vec{\sigma}$.) The
simulation is quite nontrivial, but the high-level idea is that each player
$i$ in $\vec{\sigma}$ simulates its counterpart in
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$, except that whenever it would
send a message $msg$ in $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$, $i$
shares $msg$ using VSS. Moreover, each player simultaneously plays its part
simulating the mediator, which means using a _consensus protocol_ (see
Appendix C) to guarantee that the nonfaulty players agree on when the mediator
is scheduled (there exist $t$-resilient consensus protocols in asynchronous
systems if $n>3t$ Abraham et al. [2008a]) and using CC to compute which
messages it receives, which messages it sends, and what the contents of those
messages are. With this procedure, each player is able to compute its share of
every message sent by the mediator. If that message was supposed to be sent to
player $j$, then each player $i$ sends its share of the message to $j$ in
order for $j$ to be able to reconstruct it. The full construction can be found
in Geffner and Halpern [2021]. It satisfies a property called _$k$
-bisimulation_, which states the following:

  * (a)

For all coalitions $K$ of size at most $k$, all strategies $\vec{\tau}_{K}$
for players in $K$, and all schedulers $\sigma_{e}$, there exists a strategy
$\vec{\tau}^{\prime}_{K}$ and a scheduler $\sigma_{e}^{\prime}$ such that
$(\vec{\sigma}_{-K},\tau_{K},\sigma_{e})$ and
$((\vec{\sigma}^{\prime}_{-K},\tau^{\prime}_{K})+\sigma^{\prime}_{d},\sigma^{\prime}_{e})$
are identically distributed.

  * (b)

For all coalitions $K$ of size at most $k$, all strategies
$\vec{\tau}^{\prime}_{K}$ for players in $K$, and all schedulers
$\sigma^{\prime}_{e}$, there exists a strategy $\vec{\tau}_{K}$ and a
scheduler $\sigma_{e}$ such that $(\vec{\sigma}_{-K},\tau_{K},\sigma_{e})$ and
$((\vec{\sigma}^{\prime}_{-K},\tau^{\prime}_{K})+\sigma^{\prime}_{d},\sigma^{\prime}_{e})$
are identically distributed.

Intuitively, if $\vec{\sigma}$ $k$-bisimulates
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$, then all possible distributions
over action profiles in $\vec{\sigma}$ when a coalition of at most $k$ players
deviates also occur in $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ when the
same coalition deviates (possibly in a different way). In particular, if a
coalition $K$ of players with $|K|\leq k$ can increase their payoff in
$\vec{\sigma}$ by deviating, they could already do so in
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$, which contradicts the assumption
that $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ is a $k$-resilient sequential
equilibrium. This implies that $\vec{\sigma}$ is a $k$-resilient Nash
equilibrium that implements $\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ (a
result shown by Abraham, Dolev, Geffner, and Halpern [2019b]).

In the proof of Theorem 2 we use a slightly modified variant of Geffner and
Halpern’s construction. In this variant, each player $i$ terminates only if
all messages sent in the past are correct according to $\vec{\sigma}$ and
$i$’s local history. If $i$ ever lied to some player $j$, $i$ sends the
correct message before terminating. The purpose of this is that even if a
player $j$ is not able to proceed with $\vec{\sigma}$ (for instance, because
it received incorrect messages), $j$ would still believe that in the future it
will still be able to reconstruct the (simulated) mediator’s messages as long
as the remaining players are able to continue. Additionally, as in the
synchonous case, if players cannot continue with the protocol (for instance,
because they received incorrect messages), they do nothing. It is easy to
check that this variant still $k$-bisimulates
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$ and, thus, $\vec{\sigma}$ is also
a $k$-resilient Nash equilibrium that implements
$\vec{\sigma}^{\prime}+\sigma^{\prime}_{d}$.

The rest of the proof of Theorem 2 consists of finding an appropriate
$k$-paranoid belief system consistent with $\vec{\sigma}$. If these beliefs
exist then, as in the synchronous case, no coalition $K$ of up to $k$ players
would have an incentive to deviate from the proposed protocol since, according
to their beliefs, the remaining players would still be able to compute their
part of the action profile $\vec{a}$ (which is sampled from a communication
equilibrium), and thus it is optimal for players in $K$ to play their part of
$\vec{a}$ as well. Note that, since the protocol states that players should
send the correct messages at the very end of the protocol, with any belief
system consistent with $\vec{\sigma}$, players in $K$ always believe that they
will be able to compute their part of $\vec{a}$ if they wait long enough,
regardless of their local history. This means that proving Theorem 2 reduces
to proving an analogue of Proposition 5 for asynchronous systems:

######  Proposition 8.

For all strategies $\vec{\sigma}$ in $\Gamma_{\mathit{CT},asyn}$, there exists
a $k$-paranoid belief system $b$ that is consistent with $\vec{\sigma}$.

###### Proof.

Consider a sequence $\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ of strategy
profiles defined just as in the proof of Proposition 5, and consider a
randomized scheduler $\sigma_{e}$ such that all valid _schedule prefixes_
(i.e., ordered list of players scheduled and messages delivered so far) occur
with positive probability. For instance, $\sigma_{e}$ could be a scheduler
that at each point in time either delivers a message or chooses a player to be
scheduled uniformly at random. Consider the belief system $b$ induced by the
previous sequence of strategies with scheduler $\sigma_{e}$. An argument
similar to that given in Lemmas 1 and 2 shows that $b$ is a $k$-paranoid
belief system, as desired. ∎

###  6.3 Characterization of $SE_{k}(\Gamma_{d,asyn})$ and
$SE_{k}^{S}(\Gamma_{d,asyn})$

In the asynchronous setting, the description of $SE_{k}(\Gamma_{d,asyn})$ is a
bit more convoluted than those of Section 5. Reasoning similar to that used in
the proof of Proposition 6 shows that for a fixed scheduler, a $k$-resilient
(resp., strongly $k$-resilient) sequential equilibrium in
$SE_{k}(\Gamma_{d,asyn})$ induces a $k$-resilient (resp., strongly
$k$-resilient) correlated equilibrium in $\Gamma$. Thus,
$SE_{k}(\Gamma_{d,asyn})\subseteq\mathcal{P}(CE_{k}(\Gamma))$ and
$SE_{k}^{S}(\Gamma_{d,asyn})\subseteq\mathcal{P}(CE_{k}^{S}(\Gamma))$, where
$\mathcal{P(S)}$ denotes the power set of $S$ (i.e., the set of all subsets of
$S$). The next proposition gives a precise description of
$SE_{k}(\Gamma_{d,asyn})$ and $SE_{k}^{S}(\Gamma_{d,asyn})$.

######  Proposition 9.

Given a set $S$ of strategies, let $\mathcal{P}_{=}(S)$ the set of nonempty
subsets $S^{\prime}$ of $S$ such that every element of $S^{\prime}$ gives the
same expected utility to all players. If $\Gamma=(P,A,U)$ is a normal-form
game for $n$ players and $n\geq k$, then
$SE_{k}(\Gamma_{d,asyn})=\mathcal{P}_{=}(CE_{k}(\Gamma))$ and
$SE_{k}^{S}(\Gamma_{d,asyn})=\mathcal{P}_{=}(CE_{k}^{S}(\Gamma))$.

###### Proof.

In games with a mediator, we write $\sigma_{d}$ to denote a generic strategy
for the mediator, and $\vec{\sigma}+\sigma_{d}$ to denote a strategy profile
for the players and the mediator. To show that
$SE_{k}(\Gamma_{d,asyn})\subseteq\mathcal{P}_{=}(CE_{k}(\Gamma))$ and
$SE_{k}^{S}(\Gamma_{d,asyn})\subseteq\mathcal{P}_{=}(CE_{k}^{S}(\Gamma))$,
suppose by way of contradiction that some strategy $\vec{\sigma}+\sigma_{d}$
in $SE_{k}(\Gamma_{d,asyn})$ (resp., $SE_{k}^{S}(\Gamma_{d,asyn})$) induces a
set $S$ of strategies such that, for some player $i$, there exist two
strategies $\vec{\tau},\vec{\tau}^{\prime}\in S$ induced by schedulers
$\sigma_{e}$ and $\sigma_{e}^{\prime}$, respectively, such that
$u_{i}(\vec{\tau})<u_{i}(\vec{\tau}^{\prime})$. Consider a scheduler
$\sigma_{e}^{\prime\prime}$ that does the following: it first schedules player
$i$. If $i$ sends a message to itself when it is first scheduled, then
$\sigma_{e}$ acts like $\sigma^{\prime}_{e}$, and otherwise it acts like
$\sigma_{e}$. By construction, when the scheduler is
$\sigma^{\prime\prime}_{e}$, $i$ gains by deviating from $\sigma_{i}$ and
sending a message to itself when it is first scheduled. (This construction
will not work if $\sigma_{i}$ already requires $i$ to send a message to
itself; in this case, we construct $\sigma^{\prime\prime}_{e}$ so that the
signal from $i$ to the scheduler is encoded differently, for example, by $i$
sending two messages to itself.) This shows that
$SE_{k}(\Gamma_{d,asyn})\subseteq\mathcal{P}_{=}(CE_{k}(\Gamma))$ and
$SE_{k}^{S}(\Gamma_{d,asyn})\subseteq\mathcal{P}_{=}(CE_{k}^{S}(\Gamma))$.

To prove the opposite inclusions, since we consider only equilibria with
rational probabilities, the set $CE_{k}(\Gamma)$ (resp., $CE_{k}^{S}(\Gamma)$)
is countable, as is any subset $S\subseteq CE_{k}(\Gamma)$ (resp., any subset
$S\subseteq CE_{k}^{S}(\Gamma)$). Given
$S=\\{\vec{\tau}^{1},\vec{\tau}^{2},\ldots\\}$ such that for all $k$ and
players $i$ and $j$, $u_{i}(\vec{\tau}^{k})=u_{j}(\vec{\tau}^{k})$, consider
the following strategy $\vec{\sigma}+\sigma_{d}$. Each player sends an empty
message to the mediator when it is first scheduled. Let $N$ be the number of
times the mediator that has been scheduled before receiving a message from
some player. The mediator samples an action profile $\vec{a}$ from
$\vec{\tau}^{N}$ (or from $\vec{\tau}^{1}$ if $S$ is finite and has fewer than
$N$ elements), and sends $a_{i}$ to each player $i$. Players play whatever
they receive from the mediator. It is straightforward to check that for each
strategy $\vec{\tau}$ in $S$, there is a scheduler $\sigma_{e}$ that induces
$\vec{\tau}$ when the players and the mediator play $\vec{\sigma}+\sigma_{d}$.
To check that $\vec{\sigma}+\sigma_{d}$ is indeed a $k$-resilient (resp.,
strongly $k$-resilient) correlated equilibrium, note that all strategies in
$S$ are $k$-resilient (resp., strongly $k$-resilient) correlated equilibria of
$\Gamma$ that give the same utility to each player, and thus (a) after
determining the number of times $t$ that the mediator is scheduled before
receiving the first message, no coalition of $k$ or less players can benefit
from playing an action profile different from the one suggested by the
mediator, and (b) the expected utility of each player is independent of $t$.
This shows that $\vec{\sigma}+\sigma_{d}$ is indeed a $k$-resilient (resp.,
strongly $k$-resilient) correlated equilibrium. ∎

Theorem 2 and Proposition 9 together imply:

######  Corollary 3.

If $\Gamma=(P,A,U)$ is a normal-form game for $n$ players and $n>4k$, then
$SE_{k}(\Gamma_{\mathit{CT},asyn})=\mathcal{P}_{=}(CE_{k}(\Gamma))$ and
$SE_{k}^{S}(\Gamma_{\mathit{CT},asyn})=\mathcal{P}_{=}(CE_{k}^{S}(\Gamma))$
with both the DM and AH approaches.

For Bayesian games, we do not believe that there is a simple description of
$SE_{k}(\Gamma_{d,asyn})$. To understand why, note that a key step in the
proofs of Theorems 1 and 2 is for players to send their types to the mediator.
In asynchronous systems, the mediator cannot distinguish between players that
don’t send their type to the mediator and players that send it but the receipt
of the message is delayed by the scheduler. Nevertheless, if players can
somehow punish those that never send their type to the mediator, we can
guarantee that it is optimal for all players to send a type to the mediator,
and thus we can extend the constructions used in the proof of Propositions 9
and 7 to describe $SE_{k}(\Gamma_{d,asyn})$ and $SE_{k}^{S}(\Gamma_{d,asyn})$.

######  Definition 10 (Ben-Porath [2003]; Abraham et al. [2006]).

If $\Gamma=(P,T,q,S,U)$ is a Bayesian game for $n$ players and $\mu\in
Com_{k}(\Gamma)$ or $\mu\in Com_{k}^{S}(\Gamma)$, then a _$k$ -punishment
equilibrium_ with respect to $\mu$ is a $k$-resilient Bayesian Nash
equilibrium $\vec{\tau}$ such that $u_{i}(\mu)>u_{i}(\vec{\tau})$ for all
players $i$.

Intuitively, a $k$-punishment equilibrium with respect to $\mu$ is a strategy
profile that is a $k$-resilient Bayesian Nash equilibrium which, if played by
at least $n-k$ players, results in all players being worse off than they would
be with $\mu$. If a $k$-punishment equilibrium exists, then we have the
following.

######  Proposition 10.

If $\Gamma=(P,T,q,S,U)$ is a Bayesian game, $S$ is a subset of $k$-resilient
(resp., strongly $k$-resilient) communication equilibria of $\Gamma$ such
that, for all players $i$ and all types $t_{i}$ of $i$, the expected utility
of $i$ given $t_{i}$ is the same for all $\mu$ in $S$ (i.e., $u_{i}(\mu\mid
t_{i})=u_{i}(\mu^{\prime}\mid t_{i})$ for all $\mu,\mu^{\prime}\in S$), and
there exists a $k$-punishment equilibrium $\vec{\tau}$ with respect to some
$\mu$ in $S$, then $S\in SE_{k}(\Gamma_{d,asyn})$ (resp., $S\in
SE_{k}^{S}(\Gamma_{d,asyn})$) with the AH approach or with the default move
approach if, for each player $i$, $i$’s default move is $\tau_{i}$.

Note that if $\vec{\tau}$ is a $k$-punishment equilibrium with respect to some
$\mu$ in $S$, then it is a $k$-punishment equilibrium with respect to all
$\mu\in S$, since all $\mu$ give the same utility to the players.

###### Proof.

This proof follows the same lines as the proof of Proposition 9, with the only
difference that the players must tell the mediator their type at the beginning
of the game. The punishment strategy is required to force players to tell
their true type; if players do not tell report a type, the remaining players
will play their part of the punishment strategy (note that in Proposition 9, a
punishment strategy is not needed since players have no types and thus the
mediator requires no inputs). Moreover, this type must be their true type
since all strategies in $S$ are $k$-resilient communication equilibria of
$\Gamma$. Since we are considering only distributions with rational
probabilities, the set $S$ is countable. Let $S=\\{\mu^{1},\mu^{2},\ldots\\}$.
Consider a strategy $\vec{\sigma}+\sigma_{d}$ in which each player sends its
type to the mediator when it is first scheduled and the mediator waits until
it receives the type of each player. Let $N$ be the number of times that the
mediator is scheduled before receiving all the types. The mediator samples an
action profile $\vec{a}$ from $\mu^{N}$ (or from $\mu^{1}$ if $S$ is finite
and has fewer than $N$ elements), and sends $a_{i}$ to each player $i$. If a
player sent its true type to the mediator, it plays whatever it receives from
the mediator. Otherwise, it plays the optimal action conditioned on what it
sent and what it receives from the mediator. If player $i$ never receives an
action, it plays $\tau_{i}$ (either because it is the default action or
because $i$ leaves it in its will). As in the proof of Proposition 9, it is
easy to check that $\vec{\sigma}$ induces $S$.

We next show that $\vec{\sigma}$ is a $k$-resilient (resp., strongly
$k$-resilient) sequential equilibrium for some belief system $b$. Consider a
sequence of strategy profiles $\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ such
that, in $\vec{\sigma}^{N}$, each player $i$ acts as follows. The first time
$i$ is scheduled, it sends its type $t_{i}$ to the mediator with probability
$1-1/N$ (instead of sending its type to the mediator with probability 1, as in
$\vec{\sigma}$). Moreover, each time it is scheduled, $i$ sends a random
message to each other player $j$ with probability $1/N$. Whenever a player $i$
receives an action $a_{i}$ from the mediator, it plays $a_{i}$. Otherwise, it
plays $\vec{\tau}(t_{i})$. By construction, the strategy profiles
$\vec{\sigma}^{1}+\sigma_{d},\vec{\sigma}^{2}+\sigma_{d},\ldots$ are
completely mixed and converge to $\vec{\sigma}$. Let $b$ be the belief system
induced by $\vec{\sigma}^{1}+\sigma_{d},\vec{\sigma}^{2}+\sigma_{d},\ldots$.
According to $b$, since all messages received from other players are randomly
generated, they can be ignored. Thus, $i$’s utility depends only on the
message received by the mediator. If player $i$ receives a message from the
mediator, then it must be that every player sent its type and therefore, if
$i$ sent its true type, it is optimal for $i$ to play the action received. If
$i$ did not report its true type, by construction $i$ also plays its optimal
action. On the other hand, if $i$ never receives a message from the mediator,
then according to its beliefs (as characterized by $b$), it must be that no
one else got a message and thus everyone else is going to play their part of
$\vec{\tau}$. Since $\vec{\tau}$ is a $k$-resilient Nash equilibrium, playing
$\tau_{i}$ is optimal. This shows that $(\vec{\sigma},b)$ is a $k$-resilient
(resp., strongly $k$-resilient) sequential equilibrium. ∎

Proposition 10 implies the following:

######  Corollary 4.

If $\Gamma=(P,T,q,S,U)$ is a Bayesian game and $\mu$ is a $k$-resilient
(resp., strongly $k$-resilient) correlated equilibrium of $\Gamma$ such that
there exists a $k$-punishment equilibrium $\vec{\tau}$ w.r.t. $\mu$, then
$\\{\mu\\}\in SE_{k}(\Gamma_{d,asyn})$ (resp., $\\{\mu\\}\in
SE_{k}^{S}(\Gamma_{d,asyn})$) with the AH approach or with the default move
approach if the default move is $\vec{\tau}$.

##  7 Extending the set of equilibria

Up to now we have considered only distributions over action profiles that
involve rational probabilities. We can extend our result to some extent to
distributions described by real numbers. Specifically, suppose that players
can send messages and operate with real numbers, and an equilibrium
$e=\sum_{i}\lambda_{i}e_{i}$ is a convex combination of countable rational
equilibria $e_{i}$. If players could jointly sample a real number $r\in[0,1)$
uniformly at random, they could easily implement $e$: after sampling
$r\in[0,1]$ uniformly at random, they play their part of the rational
equilibrium $e_{m}$ such that $\sum_{i=1}^{m-1}\lambda_{i}\leq
r<\sum_{i=1}^{m}\lambda_{i}$. (Our earlier results show that $e_{m}$ can be
implemented.) Note that this procedure guarantees that players implement
$e_{m}$ with probability $\lambda_{m}$, as desired.

The following is a $k$-resilient strategy $\vec{\tau}$ that allows players to
jointly sample $r$ in the synchronous setting if $n>3k$:

  1. 1.

Each player privately generates a random number $r_{i}\in[0,1)$ and broadcasts
it using Bracha’s $k$-resilient broadcast protocol Bracha [1987]. If $i$
doesn’t broadcast a number, $r_{i}$ is assumed to be $0$.

  2. 2.

Players take $r:=frac(r_{1}+\ldots+r_{n})$, where $frac(x)$ is the fractional
part of $x$.

In the asynchronous setting, this process is harder because players cannot
distinguish players that didn’t broadcast a value from players that are being
delayed by the scheduler. Moreover, players cannot agree on using only a
subset $C$ of the values shared since players might want to influence the
computation of $C$ in such a way that the number $r$ chosen is beneficial for
them. However, if $n>4k$, each player can generate $r_{i}$ as in the
synchronous setting, and then compute $r$ using a $k$-resilient secure
computation Ben-Or et al. [1993].

##  8 Conclusion

We have shown that, for all Bayesian games $\Gamma$ for $n$ players, all
$k$-resilient sequential equilibria in $\Gamma_{d}$ can also be implemented in
$\Gamma_{\mathit{CT}}$ if $n>3k$ in the synchronous setting or $n>4k$ in the
asynchronous setting. These results are optimal since it follows from Abraham
et al. [2008b] and Geffner and Halpern [2023] that if $n\leq 3k$ in the
synchronous case or $n\leq 4k$ in the asynchronous case, there are
$k$-resilient sequential equilibria in $\Gamma_{d}$ that cannot be implemented
even with a $k$-resilient Nash equilibrium.

Our results also allow us to characterize the sets
$SE_{k}(\Gamma_{\mathit{CT}})$ of all possible strategies in $\Gamma$ induced
by $k$-resilient sequential equilibria of $\Gamma_{ACT}$, generalizing results
of Gerardi [2004]. If players have perfect information (i.e. $\Gamma$ is a
normal-form game), then $SE_{k}(\Gamma_{\mathit{CT}})$ is the set of
$k$-resilient correlated equilibria of $\Gamma$; if $\Gamma$ is a Bayesian
game, then $SE_{k}(\Gamma_{\mathit{CT}})$ is the set of $k$-resilient
communication equilibria. In the asynchronous setting, we show that
$SE_{k}(\Gamma_{\mathit{CT}})=SE_{k}(\Gamma_{d})$, but characterizing the set
$SE_{k}(\Gamma_{d})$ of $k$-resilient sequential equilibria with a trusted
mediator is still an open problem. However, if $\Gamma$ has a $k$-punishment
equilibrium, then $SE_{k}(\Gamma_{d})$ is also the set of $k$-resilient
communication equilibria of $\Gamma$.

If $\Gamma$ has a $k$-punishment equilibrium, Abraham, Dolev, Gonen, and
Halpern [2006] and Abraham, Dolev, Geffner, and Halpern [2019b] showed that
all $k$-resilient Nash equilibria in $\Gamma_{d}$ could be implemented in
$\Gamma_{\mathit{CT}}$ if $n>2k$ in the synchronous setting or $n>3k$ in the
asynchronous setting respectively. The question of whether these results can
be extended to $k$-resilient sequential equilibria is still open.

##  Appendix A Game theory: basic definitions

In this section, we review the basic concepts and definitions that are needed
for this paper. We begin by presenting several types of games that are common
in the literature, each of them with its own settings. For each of these
games, we also introduce some of the _solution concepts_ that we are
interested in. A solution concept describes what rational agents should do in
a game, according to some theory of rationality. Typically, a solution concept
determines for each game a set of _strategy profiles_ , where a strategy
profile $\vec{s}=(s_{1},\ldots,s_{n})$ is a tuple consisting of one strategy
for each agent, and a strategy is a description of how each player should
move/act in all “situations” in the given game. (As we shall see, what counts
as a situation depends on the type of game we consider.)

###  A.1 Nash, Correlated, and Sequential Equilibrium

A normal-form game $\Gamma$ is a tuple $(P,A,U)$, where $P=\\{1,\ldots,n\\}$
is the set of _players_ , $A=A_{1}\times\cdots A_{n}$, where $A_{i}$ is the
set of possible actions for player $i\in P$, and $U=(u,\ldots,u_{n})$ is an
$n$-tuple of _utility_ functions $u_{i}:A\rightarrow\mathbb{R}$, again, one
for each player $i\in P$. A _pure strategy profile_ $\vec{a}$ is an $n$-tuple
of actions $(a_{1},\ldots,a_{n})$, with $a_{i}\in A_{i}$. A _mixed strategy_
for player $i$ is an element of $\Delta(A_{i})$, the set of probability
distributions on $A_{i}$. We extend $u_{i}$ to mixed strategy profiles
$\sigma=(\sigma_{1},\ldots,\sigma_{n})$ by defining
$u_{i}(\sigma)=\sum_{(a_{1},\ldots,a_{n})\in
A}\sigma_{1}(a_{1})\ldots\sigma_{n}(a_{n})u_{i}(a_{1},\ldots,a_{n})$: that is,
the sum over all pure strategy profiles $\vec{a}$ of the probability of
playing $\vec{a}$ according to $\sigma$ times the utility of $\vec{a}$ to $i$.

######  Definition 11.

In a normal-form game $\Gamma$, a (mixed) strategy profile
$\vec{\sigma}=(\sigma_{1},\ldots,\sigma_{n})$ is a _Nash equilibrium_ if, for
all $i\in P$ and strategies $\sigma_{i}^{\prime}\in\Delta(A_{i})$,

$u_{i}(\sigma_{i},\vec{\sigma}_{-i})\geq
u_{i}(\sigma^{\prime}_{i},\vec{\sigma}_{-i}).$

######  Definition 12.

In a normal-form game $\Gamma=(P,A,U)$, a distribution $p\in\Delta(A)$ is a
_correlated equilibrium_ (CE) if, for all $i\in P$ and all
$a^{\prime}_{i},a^{\prime\prime}_{i}\in A_{i}$ such that
$p(a^{\prime}_{i})>0$,

$\sum_{\vec{a}\in\Delta(A):a_{i}=a^{\prime}_{i}}u_{i}(a^{\prime}_{i},\vec{a}_{-i})p(\vec{a}\mid
a_{i}=a^{\prime}_{i})\geq\sum_{\vec{a}\in\Delta(A):a_{i}=a^{\prime}_{i}}u_{i}(a_{i}^{\prime\prime},\vec{a}_{-i})p(\vec{a}\mid
a_{i}=a^{\prime}_{i}).$

Intuitively, for a distribution $p$ over action profiles to be a correlated
equilibrium, it cannot be worthwhile for player $i$ to deviate from $a_{i}$ to
$a_{i}^{\prime}$ if $i$ knows only that $\vec{a}$ is sampled from distribution
$p$ (and $a_{i}$). Note that all Nash equilibria are correlated equilibria as
well.

An _extensive-form game_ $\Gamma$ is a tuple $(P,G,M,U,R)$, where

  * •

$P=\\{1,\ldots,n\\}$ is the set of players.

  * •

$G$ is a game tree in which each node represents a possible state of the game
and each of the edges going out of a node an action that a player can perform
in the state corresponding to that node. (In the sequel, we refer to the edges
as actions.)

  * •

$M$ is a function that associates with each non-leaf node of $G$ (we let
$G^{\circ}$ denote the non-leaf nodes) a player in $P$ that describes which
player moves at each of these nodes; if $M(v)=i$, then all the edges going out
of node $v$ must correspond to actions that player $i$ can play.

  * •

$U=(u_{1},\ldots,u_{n})$ is an $n$-tuple of utility functions from the leaves
of $G$ to $\mathbb{R}$.

  * •

$R=(\sim_{1},\ldots,\sim_{n})$ is an $n$-tuple of equivalence relations on the
nodes of $G^{\circ}$, one for each player. Intuitively, if
$v\sim_{i}v^{\prime}$, then nodes $v$ and $v^{\prime}$ are indistinguishable
to player $i$. Clearly, if $v\sim_{i}v^{\prime}$ for some $i\in[n]$, then the
set of possible actions that can be performed at $v$ and $v^{\prime}$ must be
identical and $M(v)=M(v^{\prime})$ (for otherwise, $i$ would have a basis for
distinguishing $v$ and $v^{\prime}$).

The equivalence relation $\sim_{i}$ induces a partition of $G^{\circ}$ into
equivalence classes called _information sets_ (of player $i$). It is more
standard in game theory to define $\sim_{i}$ as an equivalence relation only
on the nodes where $i$ moves. We define it on all non-leaf nodes because if
$K$ is a subset of players, we are then able to define $\sim_{K}$ as the the
intersection of $\sim_{i}$ for $i\in K$. Intuitively, $v\sim_{K}v^{\prime}$ if
the agents in $K$ cannot distinguish $v$ from $v^{\prime}$, even if they pool
all their information together. We use the equivalence relation $\sim_{K}$
when defining $k$-resilient sequential equilibrium.

A _(pure) strategy_ $s_{i}$ for player $i$ in an extensive-form game $\Gamma$
is a function that maps each node $v$ where $i$ moves to an action that can be
performed at $v$, with the constraint that if two nodes are indistinguishable
to $i$, then $s_{i}$ must choose the same action on both. More precisely, if
$v\sim_{i}v^{\prime}$ then $s_{i}(v)=s_{i}(v^{\prime})$. Each pure strategy
profile $\vec{s}$ induces a unique path from the root of the tree to some leaf
$\ell\in G\setminus G^{\circ}$ where, given node $v$ on the path, the next
node in the path is the node reached from $v$ by the edge (action)
$s_{M(v)}(v)$. The payoff of player $i$ given strategy $\vec{\sigma}$ is given
by $u_{i}(\ell)$, although we also write $u_{i}(\vec{\sigma})$ for simplicity.
A _behavioral strategy_ for player $i$ allows randomization. More precisely, a
behavioral strategy is a function $s_{i}$ that maps each node $v$ such that
$M(v)=i$ to a distribution over $i$’s possible actions at $v$ (again, with the
requirement that $s_{i}(v)=s_{i}(v^{\prime})$ if $v\sim_{i}v^{\prime}$). We
denote by $u_{i}(\vec{\sigma})$ the expected payoff of player $i$ if players
play (behavioral) strategy profile $\vec{\sigma}$.

Nash equilibrium is defined for extensive-form games just as it is in
strategic-form games. Given a NE $\vec{\sigma}$, the _equilibrium path_
consists of the nodes of $G$ that can be reached with positive probability
using $\vec{\sigma}$. It is well known that in extensive-form games, Nash
equilibrium does not always describe what intuitively would be a reasonable
play. For instance, consider the following game for two players in which
$(p_{1},p_{2})$ describes the payoff of players 1 and 2 respectively:

In this case, the strategy profile in which player 1 plays $B$ at node $a$ and
player 2 plays $L$ at node $b$ and $R$ at $c$ is a Nash equilibrium. However,
the reason that it is better for player 1 to play $B$ is that if she plays
$A$, then player 2 would play $L$ and they would both get a utility of $-5$.
This means that player 1 is being influenced by an irrational threat, since if
1 plays $A$, it is in player 2’s best interest to play $R$ instead of $L$. In
order to avoid these situations, we can extend the notion of Nash equilibrium
to _subgame-perfect Nash equilibrium_ , in which, roughly speaking, the
strategy must be a Nash equilibrium, not only in $\Gamma$, but in all the of
subgames of $\Gamma$ as well. In the example above, the only subgame-perfect
equilibrium is the one given by $\sigma_{1}(a)=A$, $\sigma_{2}(b)=R$ and
$\sigma_{2}(c)=R$.

Unfortunately, subgame-perfect equilibrium may not be well-defined if players
have nontrivial information sets. Consider the following game, where $b$ and
$b^{\prime}$ are in the same information set for player 2, as are $c$ and
$c^{\prime}$.

At node $b^{\prime}$, player 2 would play $L$; at $b$, he would play $R$. For
player 2 to decide its move, it must have a belief about the probability of
being at each node of the information set, and this belief must be consistent
with the strategy $\vec{\sigma}$ being played. For example, if
$\sigma_{1}(a)=B$, then if player 2 is in information set
$\\{b,b^{\prime}\\}$, then 2 would be sure that the true node is $b^{\prime}$.
We capture the players’ beliefs by using a _belief system_ $b$, which is a
function from information sets $I$ to a probability distribution over nodes in
$I$. Intuitively, if $I$ is an information set for player $i$, then $b$
represents how likely it is for $i$ to be at each of the nodes of $I$. Note
that if $\vec{\sigma}$ is _completely mixed_ , which means that all actions
are taken with positive probability, then $b$ is uniquely determined by Bayes’
rule. More generally, we say that a belief system $b$ is _consistent_ with a
strategy $\vec{\sigma}$ if there exists a sequence
$\vec{\sigma}^{1},\vec{\sigma}^{2},\ldots$ of completely-mixed strategies that
converges to $\vec{\sigma}$ such that the beliefs induced by Bayes’ rule
converge to $b$. Given an extensive-form game $\Gamma=(P,G,M,U,R)$, a strategy
profile $\vec{\sigma}$, a belief system $b$, and an information set $I$ for
player $i$, let $u_{i}(\vec{\sigma},I,b)$ denote $i$’s expected utility
conditional on being in information set $I$ and having belief system $b$, if
$\vec{\sigma}$ is played.

######  Definition 13 (Kreps and Wilson [1982]).

A pair $(\vec{\sigma},b)$ consisting of a strategy profile $\vec{\sigma}$ and
a belief system $b$ consistent with $\vec{\sigma}$ is a _sequential
equilibrium_ if, for all players $i$, all information sets $I$ of player $i$,
and all strategies $\tau_{i}$ for player $i$,

$u_{i}(\vec{\sigma},I,b)\geq u_{i}((\tau_{i},\vec{\sigma}_{-i}),I,b).$

Even though it is standard to define a sequential equilibrium as a pair
$(\vec{\sigma},b)$ consisting of strategy profile and a belief system, for
convenience we also say that a strategy profile $\vec{\sigma}$ is a sequential
equilibrium if there exists a belief system $b$ such that $(\vec{\sigma},b)$
is a sequential equilibrium.

###  A.2 Bayesian games

In all of the previous definitions, the utility of each player is assumed to
be common knowledge (_perfect information_). However, this is not always the
case. Bayesian games capture this idea by assuming that each player $i$ has a
type $t_{i}\in T_{i}$ sampled from a distribution $q\in\Delta(T)$, where
$T=(T_{1},\ldots,T_{n})$, and that the utility $u_{i}$ of $i$ is not only a
function of the action profile being played, but also of its type $t_{i}$.
Formally, a _Bayesian games_ is a tuple $(P,T,q,A,U)$, where, as in normal-
form games, $P$, $A$, and $U$ are the set of players, their actions, and their
utility functions, respectively; $T$ is the set of possible type profiles, and
$q$ is a distribution in $\Delta(T)$.

A _strategy_ in a Bayesian game for player $i$ is a map
$\mu_{i}:T_{i}\rightarrow\Delta(A_{i})$. Intuitively, a strategy in a Bayesian
game tells player $i$ how to choose its action given its type. Since the
distribution $q$ is common knowledge, given a strategy profile $\vec{\mu}$ in
$\Gamma$, the expected utility of a player $i$ is

$u_{i}(\vec{\mu})=\sum_{t_{i}\in T_{i}}q(t_{i})\sum_{\vec{t}}q(\vec{t}\mid
t_{i})u_{i}(\vec{\mu}(\vec{t})),$ (1)

where $u_{i}(\vec{\mu}(\vec{t}))$ denotes the expected utility of player $i$
when an action profile is chosen according to $(\mu(\vec{t}))$. This allows us
to define Bayesian Nash equilibrium as follows:

######  Definition 14.

In a Bayesian Game $\Gamma=(P,T,q,A,U)$, a strategy profile
$\vec{\mu}:=(\mu_{1},\ldots,\mu_{n})$ is a _(Bayesian) Nash equilibrium_ if,
for all players $i$ and all strategies $u^{\prime}_{i}$ for $i$,

$u_{i}(\vec{\mu})\geq u_{i}(\vec{\mu}_{-i},\mu^{\prime}_{i}).$

We can generalize correlated equilibrium to Bayesian games as follows. We can
view a correlated equilibrium as a distribution $p\in\Delta(A)$ such that if a
trusted mediator samples an action profile $\vec{a}\in p$ and sends action
$a_{i}$ to each player $i$, it is always better for $i$ to play $a_{i}$ rather
than something else. In a Bayesian game, the mediator instead samples the
action profile from a distribution that depends on the type profile. More
precisely, suppose that players send their types to a trusted mediator, the
mediator samples an action profile $\vec{a}$ from a distribution
$\mu(\vec{t})$ that depends on the type profile $\vec{t}$ received, and then
sends action $a_{i}$ to each player $i$. We say that $\mu$ is a _communication
equilibrium_ if it is optimal for the players to (a) tell their true type to
the mediator, and (b) play the action sent by the mediator. The following
definitions make this precise.

######  Definition 15.

Forges [1986]; Myerson [1986] A correlated strategy profile
$\mu:T\rightarrow\Delta(A)$ is a _communication equilibrium_ of Bayesian Game
$\Gamma=(P,T,q,A,U)$ if, for all $i\in P$, all $t_{i}\in T_{i}$, all
$\psi:T_{i}\rightarrow T_{i}$ and all $\varphi:A_{i}\rightarrow A_{i}$, we
have that

$\sum_{\vec{t}_{-i}\in T_{-i}}\sum_{\vec{a}\in
A}q(t_{-i},t_{i})\mu(\vec{a}\mid\vec{t}_{-i},t_{i})u_{i}(\vec{t}_{-i},t_{i},\vec{a})\geq$
$\sum_{\vec{t}_{-i}\in T_{-i}}\sum_{\vec{a}\in
A}q(t_{-i},t_{i})\mu(\vec{a}\mid\vec{t}_{-i},\psi(t_{i}))u_{i}(\vec{t}_{-i},t_{i},\vec{a}_{-i},\varphi(a_{i})).$

We can combine the notions of extensive-form game and Bayesian game in the
obvious way to get _extensive-form Bayesian games_ : we start with an
extensive form game, add a type space $T$ and a commonly known distribution
$q$ on $T$, and then have the utility function depend on the type profile as
well the leaf reached. We leave formal details to the reader.

##  Appendix B VSS and CC: a review

In this section, we present the two main primitives used to construct the
strategies required for the proof of Theorem 1. The purpose of these
primitives is that agents are able to distribute information between them
(verifiable secret sharing), and compute any relevant data from the
information shared without learning anything besides the data itself (circuit
computation).

Intuitively, verifiable secret sharing is designed to distribute between the
players a given piece of information $y$ in some finite field $\mathbb{F}_{q}$
in such a way that each agent $i$ knows only a part $y_{i}$ of the secret that
does not reveal any information about the secret by itself. In fact, with
$k$-resilient verifiable secret sharing, even if $k$ agents collude and put
their information together, they still cannot deduce anything about the shared
secret, but any subset of $k+1$ agents can compute the secret with no error
given their pieces of information. To achieve these properties, the idea is
that the agent $i$ that knows the secret $y$ shares it using Shamir’s secret-
sharing scheme Shamir [1979]: $i$ gives each agent $j$ a value $y_{j}$ such
that there exists a polynomial $p$ of degree $k$ such that $p(j)=y_{j}$ for
each $j$ and $p(0)=y$. It is easy to check that, if $p$ is chosen uniformly at
random, then the values $y_{i}$ received by any subset of $k$ agents is
uniformly distributed in $\mathbb{F}_{q}^{k}$, and thus convey no information
about $y$. However, any subset of $k+1$ agents can reconstruct the secret $y$
by interpolating their $k+1$ points. Note that, since up to $k$ agents may
misreport their values, players cannot just simply reconstruct the secret
using the first $k+1$ points they receive. In fact, they must wait until
receiving at least $2k+1$ points that lie on the same polynomial $p$ of degree
$k$. In that case, even if $k$ players misreport their values, at least $k+1$
of the points in $p$ are guaranteed to be reported by honest players, which
ensures that $p$ defines the correct secret. At a high level, this is why this
primitive requires that the number of players $n$ satisfies $n>3k$: even if
$k$ players misreport their values, at least $2k+1$ of those values are shared
by honest players, and thus all players are guaranteed to eventually find
$2k+1$ points that lie on the same polynomial of degree $k$, which allows them
to reconstruct the secret correctly.

In order to share a secret using Shamir’s secret-sharing scheme, it is
unfortunately not enough to have the sender choose a polynomial $p$ uniformly
at random such that $p(0)=y$ and send each agent $i$ the value of $p(i)$. This
protocol is vulnerable when the sender is malicious: it could generate $n$
points that do not lie on the same polynomial, and agents could never
reconstruct the secret. In order to guarantee that the shared points define
some secret, players have to follow a non-trivial protocol that checks the
validity of the points without leaking information about the underlying
secret. In the synchronous setting, Ben-Or, Goldwasser, and Wigderson [1988]
provide a $k$-resilient VSS protocol if $n>3k$; in the asynchronous setting,
Ben-Or, Canetti, and Goldreich [1993] provide a $k$-resilient VSS protocol if
$n>4k$. Intuitively, in asynchronous systems, $n>4k$ is necessary since $k$ of
the $4k+1$ players might be delayed arbitrarily (and are indistinguishable
from deviating players that didn’t send a message), and $k$ might send the
wrong values, which leaves $2k+1$ points to interpolate without error. A more
rigorous description of the properties of VSS can be found in Appendix B.1.

In circuit computation, players generate the shares of either the sum or
product of two shared secrets without leaking information about the secrets
themselves. More precisely, suppose that secrets $y,z\in\mathbb{F}_{q}$ are
shared among the players. Then $k$-resilient circuit computation that allows
each player to compute its share of $y+z$ or $yz$ without leaking any
information about $y$ or $z$ to any coalition of at most $k$ players. By
successively using this primitive, players can compute the shares of any
secret that is the output of a circuit with addition and multiplication gates
given the inputs. This, in turn, allows agents to compute the shares of the
output of any function whose domain and range are finite, since, without loss
of generality, we can then take the domain and range to be $\mathbb{F}_{q}$
for some $q$ sufficiently large, and any function
$f:\mathbb{F}_{q}\rightarrow\mathbb{F}_{q}$ can be viewed as a polynomial on
$\mathbb{F}_{q}$, and so involves only addition and multiplication. An
implementation of a $k$-resilient circuit computation protocol is given by
Ben-Or, Goldwasser, and Wigderson [1988] in the case of synchronous systems,
and by Ben-Or, Canetti, and Goldreich [1993] in the case of asynchronous
systems. A more detailed description of the properties of CC can be found in
Appendix B.2.

###  B.1 Verifiable secret sharing

Verifiable secret sharing allows a player (the sender) to securely distribute
shares of a private value $v$ among all players. A protocol $\vec{\sigma}$ is
a _$k$ -resilient implementation of VSS in synchronous systems_ if, for all
senders $s\in[n]$, all coalitions $K\subseteq[n]$ of at most $k$ players, and
all strategies $\vec{\tau}_{K}$ for players in $K$, the following holds of
$(\vec{\sigma}_{-K},\vec{\tau}_{K})$:

  * (a)

All players not in $K$ terminate.

  * (b)

If $s^{i}$ is $i$’s output, then there exists a polynomial $r$ of degree $k$
such that $r(i)=s^{i}$ for all $i\not\in K$. Moreover, if the sender $s$ is
not in $K$, $r(0)$ is its input $v$.

  * (c)

If the sender $s$ is not in $K$, the distribution over histories $h_{K}^{v}$
of players in $K$ when $s$ shares $v$ is the same for all
$v\in\mathbb{F}_{q}$.

Properties (a) and (b) guarantee that, regardless of what a coalition of at
most $k$ players does, all honest players terminate and their outputs are
consistent even when the sender is deviating from the protocol, which means
that even if the sender decides not to share an input or not send messages at
all, all honest players eventually agree on some shares. Property (c)
guarantees that no coalition of $k$ players can learn anything about the
secret being shared if the sender is not in the coalition.

In asynchronous systems, properties (a) and (b) cannot be guaranteed
simultaneously, since a player that sends no messages is indistinguishable
from a player that is being delayed by the scheduler. In this case we have
that:

  * (a1)

If the sender is not in $K$, all players not in $K$ terminate.

  * (a2)

If a player $i\not\in K$ terminates, all players not in $K$ terminate.

  * (b)

If $S$ is the subset of players not in $K$ that terminate and $s^{i}$ is the
output of player $i\in S$, then there exists a polynomial $r$ of degree $k$
such that $r(i)=s^{i}$ for all $i\in S$. Moreover, if the sender $s$ is not in
$K$, $r(0)$ is its input $v$.

  * (c)

If the sender $s$ is not in $K$, then for all schedulers, the distribution
over histories $h_{K}^{v}$ of players in $K$ when $s$ shares $v$ is the same
for all $v\in\mathbb{F}_{q}$.

Note that, in the asynchronous setting, a player might not terminate if the