# Strengthening Nash Equilibria

Ivan Geffner  Moshe Tennenholtz The work by Ivan Geffner and Moshe Tennenholtz
was supported by funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement 740435).

###### Abstract

Nash equilibrium is often heralded as a guiding principle for rational
decision-making in strategic interactions. However, it is well-known that Nash
equilibrium sometimes fails as a reliable predictor of outcomes, with two of
the most notable issues being the fact that it is not resilient to collusion
and that there may be multiple Nash equilibria in a single game. In this
paper, we show that a mechanism designer can get around these two issues for
free by expanding the action sets of the original game. More precisely, given
a normal-form or Bayesian game $\Gamma$ and a Nash equilibrium $\vec{\sigma}$
in $\Gamma$, a mechanism designer can construct a new game
$\Gamma^{\vec{\sigma}}$ by expanding the action set of each player and
defining appropriate utilities in the action profiles that were not already in
the original game. We show that the designer can construct
$\Gamma^{\vec{\sigma}}$ in such a way that (a) $\vec{\sigma}$ is a semi-strong
Nash equilibrium of $\Gamma^{\vec{\sigma}}$, and (b) $\vec{\sigma}$ Pareto-
dominates or quasi Pareto-dominates all other Nash equilibria of
$\Gamma^{\vec{\sigma}}$.

##  1 Introduction

Suppose that three pirates want to share a treasure consisting of $300$ coins.
Each pirate can individually choose if it cooperates or defects. If all three
pirates cooperate, they split the treasure equally and each one of them gets
$100$ coins. The same happens if only one pirate defects (she cannot overpower
the other two), or if all three pirates defect. However, if exactly two
pirates defect, they can keep the treasure for themselves and get $150$ coins
each while the remaining pirate gets $0$. Clearly, all three pirates
cooperating is a Nash equilibrium since no pirate gets additional utility by
defecting. However, this equilibrium is not resilient to coalitions since two
pirates can get additional utility by defecting together. Now, suppose that
these three pirates are in an identical situation with the exception that
there is an additional action available for them: _Betray_. Betraying works as
follows. If the number of pirates that play either _Defect_ or _Betray_ is
different than two, nothing happens and all three pirates split the treasure
equally. Otherwise, we have the following cases depending on what the two non-
cooperative pirates play:

  * •

(Defect, Defect): The two defecting pirates get $150$ coins each while the
remaining pirate gets $0$.

  * •

(Betray, Defect): The pirate that betrays kills the pirate that defects and
gets all $300$ coins.

  * •

(Betray, Betray): Both pirates kill each other. The remaining pirate gets all
$300$ coins.

As in the previous game, the strategy profile in which all three pirates
cooperate is a Nash equilibrium that is not resilient to collusion.
Nevertheless, we can argue that in this scenario it is never in the interest
of the pirates to collude. If two pirates decide to play (Defect, Defect), one
could easily betray the other in order to get a bigger share. In general, this
type of Nash equilibrium is called _semi-strong_ [21]. In a semi-strong Nash
equilibrium, no coalition can increase the utility of all of its members while
simultaneously satisfying that no member of the coalition can further increase
its utility by defecting (inside of the coalition).

In the game with three pirates described above, we showed that the addition of
the _Betray_ action converted a Nash equilibrium that was vulnerable to
coalitions to a semi-strong one. A natural question that follows is if a
mechanism designer can make any Nash equilibrium semi-strong by adding
appropriate actions and utilities to the original game. In this paper, we give
a positive answer to this question. Moreover, in normal-form games or Bayesian
games with independent types, we show that we can add actions in such a way
that the original equilibrium is not only semi-strong, but also Pareto-
dominates all other Nash equilibria of the extended game. In arbitrary
Bayesian games, we show that the original equilibrium quasi Pareto-dominates
all other equilibria, which means that the total welfare of any subset $S$ of
players with $|S|\geq 2$ is always greater in the original equilibrium. This
implies that the mechanism designer can bluff about the existence of these
additional actions since they would never be played in practice.

Perhaps not surprisingly, strengthening a pure Nash equilibrium $\vec{\sigma}$
is relatively simple. We can do so by simply adding a _report_ action to each
player and defining the new utilities in such a way that players that defect
from $\vec{\sigma}$ while being reported get punished (note that if two
players play _report_ , they both are defecting while being reported), and
players who report defecting players get rewarded. The real difficulty of the
problem arises when $\vec{\sigma}$ is a mixed strategy, since in this case it
is hard to tell if a player $i$ is defecting or if the action played by $i$ is
a legitimate outcome from randomization. Additional complexity is added when
players have (possibly correlated) private information and when the game is
infinite (i.e., when the sets of possible actions are infinite). In fact,
these cases require carefully calibrated mechanisms, which serve as the main
technical contribution of our paper. At a high level, our approach is to allow
players to _bet_ or _predict_ what actions or action profiles are going to be
played by other players (besides playing an action in the original game). If
they guess correctly, they get rewarded and the player whose action was
predicted gets punished. If they guess wrong, they get punished. We show that
we can calibrate the payoffs of such bets in such a way that, if a coalition
defects and they all win, there exists a player in the coalition that has
incentives to bet on other members of the coalition or there exists a player
in the coalition that has incentives to modify its strategy because of the
bets placed by other players.

###  1.1 Related work

The work in this paper intersects with two large branches of the economics and
computer science literature. The first one is the study of collusion-resilient
protocols in multi-agent systems. Ben-Or [9] and Rabin [22] provided protocols
that implement consensus in the presence of $t$ byzantine faults if the number
of players $n$ satisfies $n>3t$. These protocols were later generalized by
Ben-Or, Goldwasser and Widgerson [8] who showed that, if $n>3t$, we can
implement synchronous multiparty secure computation of any function $f$ on a
finite domain in the presence of at most $t$ byzantine faults. Many subsequent
authors added strategic incentives into the mix [1, 5, 4, 16, 25, 23].
Bernheim, Peleg and Whinston [11] introduced a recursive definition for
_coalition-proof equilibrium_. Intuitively, a strategy profile $\vec{\sigma}$
is coalition-proof if there is no coalition that can defect from the main
strategy to another coalition-proof strategy in such a way that all of its
members get a better utility. Penn, Polukarov and Tennenholtz [21] defined
_semi-strong Nash equilibrium_ in a similar way, but with only one level of
recursion (i.e., for a coalition to succeed, their new strategy must also be a
Nash equilibrium). Abraham, Dolev, Gonen and Halpern [3] adapted Aumann’s
definition of _$k$ -resilience_ [6] to cheap-talk games, and showed that every
synchronous mediator can be implemented by a $k$-resilient cheap-talk strategy
(i.e., a strategy in which coalitions of at most $k$ agents do not benefit
from defecting from the proposed strategy) if $n>2k$ and if there is an
appropriate way to punish defecting players. Most of these results have been
generalized to the asynchronous setting as well [12, 13, 10, 17, 15]. In
particular, Abraham, Dolev, Geffner and Halpern [2] provided a $k$-resilient
implementation of asynchronous mediators if $n>3k$ and there exists a
punishment strategy. Although most of the results in this area require that
the ratio between the number of players $n$ and the maximum size $t$ or $k$ of
the defecting coalition satisfies a certain threshold, our results show that,
if we only need semi-strongness, we can take the protocol used for $t=1$ or
$k=1$ and expand the set of actions in such a way that the same protocol
tolerates deviations of coalitions of arbitrary size (according to the semi-
strong definition). For example, this means that if a mechanism designer can
modify (or can bluff about modifying) the action sets of the players, we
provide a way to design semi-strong protocols that implement mediators in
synchronous or asynchronous systems that require only three or four players,
respectively.

The second closely related branch is mechanism design. The aim of a mechanism
designer is to design the set of strategies of the players and to define the
utilities that they would get by following said strategies in order to
influence the outcomes obtained from rational play. Sometimes, this influence
can be exerted with the inclusion of a third-party mediator that may interfere
with the game in different ways. Aumann[7] considered the inclusion of a
cheap-talk mediator in normal-form and Bayesian games. More precisely, given a
normal-form game $\Gamma$, Aumann constructed a game $\Gamma_{d}$ where
players can communicate via cheap-talk with a mediator $d$ before playing an
action in $\Gamma$. The Nash equilibria of the resulting games were defined as
correlated equilibria. Forges [14] considered the same extension in Bayesian
games and gave a geometric characterization of the resulting equilibria, which
were labelled as _communication equilibria_. Monderer and Tennenholtz [19]
showed that we can guarantee the existence of strong Nash equilibria in games
with several classes of mediators. In their setting, some of these mediators
can go beyond sending messages or signals to the players, such as for instance
playing on their behalf when permitted. In another paper, Monderer and
Tennenholtz [18] considered a setting where the mediator has the power to
_promise payments_ to the players (i.e., to increase their utility on given
outcomes) but cannot communicate. They study the minimum payment that is
necessary to influence the behavior of the players. Monderer and Tennenholtz
showed that, given any normal-form game $\Gamma$ and any pure Nash equilibrium
$\vec{\sigma}$ in $\Gamma$, there exists a mediator $d$ that promises payments
only outside of the equilibrium path in such a way that $\vec{\sigma}$ is not
only a Nash equilibrium but also a dominant strategy in the newly generated
game. Tennenholtz [24] later considered a type of normal-form games where
players are programs and a third-party mediator is able to access and reveal
the source code of other players before they commit to an action. Tennenholtz
showed that the set of Nash equilibria in this setting (or _program
equilibria_ , as defined in [24]) is richer than without the inclusion of the
mediator. For example, there exist program equilibria in the one-shot
Prisoner’s Dilemma where both players cooperate. Oesterheld et al. [20]
refined this idea and defined _similarity-based coopaeration_ , where each
player only has access to a similarity parameter instead of the whole source
code of other players. They showed that, in their setting, there also exist
equilibria in which both players cooperate in the Prisoner’s Dilemma. Our
setting can also be viewed as including a mediator into a normal-form or
Bayesian game in order to influence the outcome. In this case, the mediator
cannot communicate with the players but can extend the game by adding new
actions with arbitrary utilities.

###  1.2 Paper Structure

The rest of the paper is structured as follows. In Section 2 we give the
necessary definitions to formalize and prove our main results, which are
stated in Section 3. Section 4 provides a high-level overview of the proofs,
along with several examples that showcase the main difficulties that are
needed to overcome in each setting. We give a formal proof of our main results
in Sections 5 and 6. The first of these sections deals with the case of finite
normal-form games and finite Bayesian games with independent types, and the
latter deals with (arbitrary) finite Bayesian games. These proofs are
generalized in Section 7 in order to hold for games with infinite actions as
well. We give a conclusion in Section 8, along with a brief summary about the
remaining open problems.

##  2 Basic definitions

###  2.1 Games and Equilibria

A normal-form game is a tuple $(P,A,U)$ where $P=\\{1,2,\ldots,n\\}$ is the
set of players, $A:=A_{1}\times A_{2}\times\ldots\times A_{n}$ is the set of
possible actions profiles and $U=(u_{1},u_{2},\ldots,u_{n})$ is a tuple of
utility functions such that $u_{i}:A\times\mathbb{R}$ outputs the utility of
player $i$ given the action profile played. In a normal form game, a (mixed)
strategy $\sigma_{i}$ for player $i$ is simply a distribution of actions of
$A_{i}$ (we denote by $\Delta A_{i}$ the set of such possible distributions).
A strategy profile $\vec{\sigma}=(\sigma_{1},\ldots,\sigma_{n})$ is a Nash
Equilibrium of $\Gamma$ if no player can increase its utility by switching to
another strategy. More precisely, $\vec{\sigma}$ is a Nash equilibrium if
$u_{i}(\vec{\sigma})\geq u_{i}(\vec{\sigma}_{-i},\tau_{i})$ for all players
$i$ and all strategies $\tau_{i}$ for $i$ (where $\vec{\sigma}_{-i}$ denotes
that all players but $i$ play their part of strategy profile $\vec{\sigma}$).

A Bayesian game is a generalization of normal-form games where players have
private types and the utility of each player depends not only on the action
profile played but also on its own type. More formally, a Bayesian game is a
tuple $(P,T,q,A,U)$ where $T=T_{1}\times T_{2}\times\ldots\times T_{n}$ is the
set of possible type profiles and $q$ is the prior distribution over $T$ that
is common knowledge among the players. $P$, $A$ and $U$ denote the same
concepts as in normal-form games, except that the domain of each utility
function $u_{i}$ is $T_{i}\times A$ instead of just $A$. In Bayesian games,
strategies are functions from types to distributions over action profiles.
More precisely, in a Bayesian game $\Gamma=(P,T,q,A,U)$, a strategy
$\sigma_{i}$ for player $i$ maps elements from $T_{i}$ to distributions over
$A$. As in normal-form games, a strategy profile $\vec{\sigma}$ is a Nash
equilibrium if $u_{i}(\vec{\sigma})\geq u_{i}(\vec{\sigma}_{-i},\tau_{i})$ for
all players $i$ and all strategies $\tau_{i}$ for $i$. For simplicity, we will
assume that no player has a type that has $0$ probability of being sampled.

Given a normal-form or Bayesian game $\Gamma$, we say that $\Gamma$ is
_finite_ if the set of actions is finite, and we say that $\Gamma$ is
_bounded_ if all utility functions are bounded. Note that if a game is finite,
it is also bounded.

###  2.2 Resilience to coalitions

There are well-known notions of equilibria that are resilient to collusion and
joint deviations. The first of such notions is _strong Nash equilibrium_ [6],
which occurs if no possible coalition can strictly increase the payoff of all
its members by jointly deviating. More precisely, in a normal-form or Bayesian
game $\Gamma=(P,T,q,A,U)$, a strategy profile $\vec{\sigma}$ is a strong Nash
equilibrium if, for all subsets $S\subseteq P$ and all strategy profiles
$\vec{\tau}_{S}$ for players in $S$, there exists a player $i\in S$ such that
$u_{i}(\vec{\sigma})\geq u_{i}(\vec{\sigma}_{-S},\vec{\tau}_{S})$.

In this paper we focus on a variant of strong Nash equilibrium introduced by
Penn, Polukarov and Tennenholtz [21] in which, for a joint deviation to be
successful, not only all members must strictly benefit from colluding, but
also the strategy performed by the members of the coalition must be a Nash
equilibrium inside of the larger game (in which the players outside of the
coalition simply play their part of $\vec{\sigma}$). The following definition
makes this precise.

######  Definition 1.

Let $\Gamma$ be a normal-form or a Bayesian game and $\vec{\sigma}$ be a
strategy profile for $\Gamma$. Then, $\vec{\sigma}$ is a semi-strong Nash
equilibrium if, for all subsets $S$ and all strategy profiles $\vec{\tau}_{S}$
for $S$, there exists a player $i\in S$ and a strategy $\tau^{\prime}_{i}$ for
$i$ such that

$u_{i}(\vec{\sigma})\geq
u_{i}(\vec{\sigma}_{-S},\vec{\tau}_{S})\quad\mbox{or}\quad
u_{i}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})>u_{i}(\vec{\sigma}_{-S},\vec{\tau}_{S})$

Note that if the first condition is satisfied for some $i$, then
$\vec{\tau}_{S}$ is not profitable for $i$, while the second condition implies
that $i$ can further deviate from $\vec{\tau}_{S}$ to increase its utility
from the one it would get in the coalition.

###  2.3 Game extensions

The results of this paper involve games that result from extending the set of
actions of simpler games. We say that a Bayesian game
$\Gamma^{\prime}=(P^{\prime},T^{\prime},q^{\prime},A^{\prime},U^{\prime})$
_extends_ another Bayesian game $\Gamma=(P,T,q,A,U)$ if $P^{\prime}=P$,
$T^{\prime}=T$, $q^{\prime}=q$, $A_{i}\subseteq A^{\prime}_{i}$ for all $i\in
P$, and $u_{i}(\vec{a})=u^{\prime}_{i}(\vec{a})$ for all $\vec{a}\in A$ and
$i\in P$. Intuitively, game extensions must have the same players, action
profiles, and utilities as the original game, but they may also include
additional actions for the players that may give arbitrary utilities when
played. The definition for normal-form games is analogous.

For future reference, note that if $\Gamma^{\prime}$ extends $\Gamma$, we can
view strategy profiles of $\Gamma$ as strategy profiles in $\Gamma^{\prime}$
in a natural way: each player $i$ plays each action in $A_{i}$ with the same
probability as in $\Gamma$, and plays each action in $A^{\prime}_{i}\setminus
A_{i}$ with probability $0$. Unless it is specified, for the rest of the paper
we will always use such convention.

###  2.4 Comparing Nash Equilibria

Given a Bayesian or Normal-form game $\Gamma$ and two Nash equilibria
$\vec{\sigma}$ and $\vec{\tau}$, we say that $\vec{\sigma}$ _Pareto-dominates_
$\vec{\tau}$ if $u_{i}(\vec{\sigma})\geq u_{i}(\vec{\tau})$ for all $i\in P$.
Moreover, we say that $\vec{\sigma}$ _quasi Pareto-dominates_ $\vec{\tau}$ if,
for all subsets $S\subseteq P$ with $|S|\geq 2$,

$\sum_{i\in S}u_{i}(\vec{\sigma})\geq\sum_{i\in S}u_{i}(\vec{\tau}).$

Note that, if $|P|\geq 2$ and $\vec{\sigma}$ quasi Pareto-dominates
$\vec{\tau}$,

  * •

At most one player $i$ satisfies $u_{i}(\vec{\tau})>u_{i}(\vec{\sigma})$.

  * •

The total welfare of the players is greater with $\vec{\sigma}$ than with
$\vec{\tau}$.

##  3 Main Results

The main contribution of this paper can be summarized by the following
Theorems.

######  Theorem 1.

Let $\Gamma=(P,T,q,A,U)$ be a bounded Bayesian game with independent types
(i.e., that $q$ samples the types independently). Then, for each Nash
equilibrium $\vec{\sigma}$ of $\Gamma$ there exists an extension
$\Gamma^{\vec{\sigma}}=(P,T,q,A^{\vec{\sigma}},U^{\vec{\sigma}})$ of $\Gamma$
such that:

  * (a)

$\vec{\sigma}$ is a semi-strong Nash equilibrium of $\Gamma^{\vec{\sigma}}$.

  * (b)

$\vec{\sigma}$ Pareto-dominates all other Nash equilibria of
$\Gamma^{\vec{\sigma}}$.

Moreover, if $A$ is finite, $A^{\vec{\sigma}}$ satisfies that
$|A^{\vec{\sigma}}_{i}|\leq|A_{i}|\cdot|P|\cdot|A|_{max}$ for all $i\in P$,
where $|A|_{max}=\max_{i\in P}{|A_{i}|}$.

Intuitively, part (a) of Theorem 1 states that given any game and any Nash
equilibrium, we can expand the game such that the original Nash equilibrium
becomes semi-strong. At the same time, part (b) implies that none of the newly
added actions will ever be played if all players play optimally. The last part
of the Theorem states that, if $\Gamma$ is finite, then the size of the
resulting extension is polynomial over the size of $\Gamma$. The following
Theorem extends Theorem 1 to arbitrary Bayesian games.

######  Theorem 2.

Let $\Gamma=(P,T,q,A,U)$ be a bounded Bayesian game. Then, for each Nash
equilibrium $\vec{\sigma}$ of $\Gamma$ there exists an extension
$\Gamma^{\vec{\sigma}}=(P,T,q,A^{\vec{\sigma}},U^{\vec{\sigma}})$ of $\Gamma$
such that:

  * (a)

$\vec{\sigma}$ is a semi-strong Nash equilibrium of $\Gamma^{\vec{\sigma}}$.

  * (b)

$\vec{\sigma}$ quasi Pareto-dominates all other Nash equilibria of
$\Gamma^{\vec{\sigma}}$.

Moreover, if $A$ is finite, $A^{\vec{\sigma}}$ satisfies that
$|A^{\vec{\sigma}}_{i}|=|A_{i}|+|A|$ for all $i\in P$.

The only two differences between Theorem 1 and Theorem 2 are the size of the
extension and the fact that, in Theorem 2, the resulting equilibrium quasi
Pareto-dominates all other Nash equilibria of $\Gamma^{\vec{\sigma}}$ instead
of Pareto-dominating. Note that Theorem 1 and Theorem 2 do not require that
$\Gamma$ is finite. In fact, as shown in Section 7, the statements still hold
when the action sets are uncountable, as long as $\Gamma$ is bounded.

##  4 Sketch of the Proofs

As in the _three pirates_ example from the introduction, the idea behind the
construction of $\Gamma^{\sigma}=(P,A^{\vec{\sigma}},U^{\vec{\sigma}})$ is
that players can play special actions that reward them if another player goes
off the equilibrium path. This construction can be very simple for pure Nash
equilibria: suppose that $\vec{\sigma}$ is a pure Nash equilibrium where each
player $i$ plays some action $a_{i}$ with probability 1. Then, we can set
$A^{\vec{\sigma}}_{i}=A_{i}\cup\\{\alpha\\}$ and define the payoffs as follows
when some player $i$ plays $\alpha$:

  * •

If another player $j$ plays $\alpha$, all players $k$ that didn’t play $a_{k}$
get $m-1$ utility (including those who played $\alpha$), where $m$ is the
minimum utility of the game. All other players get the same utility as in
equilibrium.

  * •

If no other player plays $\alpha$,

    * –

If all other players $j$ play $a_{j}$, they all get the same utility as in
equilibrium and $i$ gets $m-1$.

    * –

Otherwise, $i$ gets the maximum possible utility plus $1$, all players $j$
that played $a_{j}$ get the same utility as in equilibrium, and all other
players get $m-1$.

It is straightforward to check that $\Gamma^{\vec{\sigma}}$ satisfies the
conditions of Theorem 1: First, no player can increase its utility by
defecting from $\vec{\sigma}$. Second, if a coalition defects from
$\vec{\sigma}$ and they all increase their utility, it means that none of them
is playing $\alpha$. However, this implies that a player can further increase
its utility by switching its action to $\alpha$. Lastly, an analogous
reasoning shows that $\vec{\sigma}$ is Pareto-optimal: if another strategy
profile $\vec{\tau}$ gives a better utility than $\vec{\sigma}$ to all
players, it means that none of them is playing $\alpha$. Then, again, this
would not be a Nash equilibrium since a player can increase its utility by
playing $\alpha$ instead.

If we consider mixed Nash equilibria, the construction becomes more
complicated. For instance, there could be Nash equilibria where all actions
have non-zero chance of being played, as in the following example.

######  Example 1.

Consider a normal-form game $\Gamma=(P,A,U)$ with $P=\\{1,2,\ldots,n\\}$,
$A_{i}=\\{0,1\\}$ for all $i\in P$, and such that

$u_{i}(a_{1},\ldots,a_{n})=\left\\{\begin{array}[]{ll}1&\mbox{if
}\\#a_{i}(a_{1},\ldots,a_{n})\geq\\#(1-a_{i})(a_{1},\ldots,a_{n})\\\
0&\mbox{otherwise,}\end{array}\right.$

where $\\#a_{i}(a_{1},\ldots,a_{n})$ denotes the number of players who played
action $a_{i}$. Denote by $\vec{\sigma}$ the strategy profile in which each
player chooses its action uniformly at random.

Intuitively, $i$ gets $1$ utility if its action is played by the majority of
the players and $i$ gets $0$ utility otherwise. Clearly, if all other players
randomize their action, it doesn’t matter what action $i$ chooses since both
give the same utility in expectation. Therefore, randomizing its own action is
also a best response for $i$, which means that $\vec{\sigma}$ is a Nash
equilibrium. However, $\vec{\sigma}$ is not semi-strong: if two or more
players collude, it is in their interest to vote on the same value. For
instance, all of them playing $0$ or all of them playing $1$ strictly
increases their expected utility and no agent in the coalition can further
increase it by playing anything else.

In order to create an extension of $\Gamma$ such that $\vec{\sigma}$ is a
semi-strong Nash equilibrium we need a different approach than the one given
for pure Nash equilibria. The main issue is that it is not easy to tell if a
player $i$ is defecting from the proposed strategy or not since, regardless of
what $i$ plays, its action could be the result of playing $\sigma_{i}$. They
key idea is that, in equilibrium, $i$ must play $0$ and $1$ with $\frac{1}{2}$
probability each. By contrast, if $i$ defects, one of these actions must be
played with probability greater than $\frac{1}{2}$. We can make use of this
fact as follows. Suppose that, for each player $i$ and each action
$a_{i}\in\\{0,1\\}$, we give each player $j$ the possibility of _betting_ that
$i$ will play $a_{i}$. If $i$ plays $a_{i}$, then $j$ gets $x$ utility and $i$
loses $x^{\prime}$ utility. Otherwise, $j$ gets $-x$ utility. Clearly, if $i$
follows ${\sigma}_{i}$, there is no incentive for $j$ to place such a bet.
However, if $i$ defects, betting on one of $i$’s actions gives $j$ a strictly
positive expected utility. We can adjust the values of $x$ and $x^{\prime}$
such that it is never in the interest of $i$ to collude and defect. The
construction given in Section 5.1 follows a similar approach, except for the
fact that the utility won by winning a bet and the utility lost by losing a
bet may be different. More precisely, the bets are calibrated in such a way
that, if $i$ plays some action $a$ with the same probability as in
$\sigma_{i}$, the expected payoff of betting on $(i,a)$ is $0$, while if $i$
plays $a$ with more probability than in $\sigma_{i}$ the expected payoff of
betting on $(i,a)$ is strictly positive.

The construction of $\Gamma^{\vec{\sigma}}$ for Bayesian games is more
complicated. The main issue is that, in normal-form games, whenever a player
$i$ defects from $\sigma_{i}$ to a different strategy $\tau_{i}$, it is
guaranteed that there exists an action that is more likely to be played with
$\tau_{i}$ than with $\sigma_{i}$. However, this is not true for Bayesian
games. For example, consider a game such that $T_{i}=A_{i}=\\{0,1\\}$ for all
players $i$, and such that all types are sampled independently and uniformly
from $\\{0,1\\}$. If $\sigma_{i}$ is the strategy in which player $i$ plays
whatever its type is and $\tau_{i}$ is the strategy in which it plays the
opposite of its type, it is indistinguishable to the other players if $i$ is
playing $\sigma_{i}$ or if $i$ is playing $\tau_{i}$. In particular, we cannot
design bets that give a strictly positive expected utility when $i$ plays
$\tau_{i}$ and simultaneously give $0$ expected utility when $i$ plays
$\sigma_{i}$. The key observation is that, if $\vec{\tau}_{S}$ is a profitable
deviation for some coalition $S$ and types are independent, each player $i\in
S$ must be able to tell the strategy $\tau_{j}$ of at least one other player
$j\in S$. Otherwise, $i$ would get the same utility in
$(\vec{\sigma}_{-i},\tau_{i})$ (see Proposition 4). This observation implies
that the construction used for normal-form games can be easily generalized to
also cover Bayesian games with independent types.

Unfortunately, the construction used for normal-form games does not quite work
in general for Bayesian games, as the following example shows.

######  Example 2.

Consider a Bayesian game $\Gamma=(P,T,q,A,U)$ such that $P=\\{1,2,3\\}$,
$T_{i}=A_{i}=\\{0,1\\}$ for all $i\in P$, and $q$ is the uniform distribution
over the subset of $T$ such that the sum of coordinates is odd (i.e.,
$\\{(t_{1},t_{2},t_{3})\in T\mid t_{1}+t_{2}+t_{3}\equiv 1\bmod 2\\}$). Given
an action profile $(a_{1},a_{2},a_{3})$, all players get $1$ utility if
$a_{1}+a_{2}+a_{3}$ is odd. Otherwise, they all get $0$ utility.

Consider two strategy profiles $\vec{\sigma}$ and $\vec{\tau}$. In
$\vec{\sigma}$, each player independently plays $0$ and $1$ with equal
probability. In $\vec{\tau}$, each player plays its own type.

In Example 2, it is straightforward to check that $\vec{\sigma}$ and
$\vec{\tau}$ are both Nash equilibria where each player plays $0$ and $1$ with
equal probability. However, players get $1/2$ expected utility with
$\vec{\sigma}$ and $1$ expected utility with $\vec{\tau}$. The main difference
between the strategy profiles is that, even though each player has $1/2$
chance of having type $0$ and $1/2$ chance of having type $1$, their types are
correlated in such a way that their sum is always an odd number. Moreover, we
can easily check that players’ types are pairwise independent. This means that
the probability that a player $i$ plays a certain action $a\in\\{0,1\\}$ with
$\tau_{i}$ is exactly the same as the probability that $i$ plays $a$ with
$\sigma_{i}$, even if we condition the probability on another player $j$’s
type. Therefore, $j$ cannot guess $i$’s action with $\vec{\tau}$ any better
than with $\vec{\sigma}$, which implies that the construction used for normal-
form games fails in this case.

In order to deal with situations as the one presented in Example 2, we modify
the construction $\Gamma^{\vec{\sigma}}$ used for normal form games in such a
way that players can bet on action profiles played by other players instead of
individual actions. It can be shown that if bets are calibrated in a similar
fashion, $\Gamma^{\vec{\sigma}}$ satisfies the properties of Theorem 2.

To extend the proofs of Theorems 1 and 2 to infinite games, we need a slightly
different construction, as shown by the following example.

######  Example 3.

Consider a normal-form game $\Gamma=(P,A,U)$ with $P=\\{1,2\\}$,
$A_{1}=A_{2}=\mathbb{N}$, and

$u_{1}(a_{1},a_{2})=u_{2}(a_{1},a_{2})=\left\\{\begin{array}[]{ll}0&\mbox{ if
}a_{1}=0\mbox{ or }a_{2}=0\\\ 1&\mbox{ otherwise.}\end{array}\right.$

Denote by $\vec{\sigma}$ the strategy profile in which each player plays $0$
with probability 1, and by $(\vec{\tau})_{N}$ the strategy profile in which
both players sample their action uniformly at random from
$\\{1,2,\ldots,N\\}$.

It is easy to check that $\vec{\sigma}$ and $(\vec{\tau})_{N}$ are Nash
equilibria of $\Gamma$. Suppose that we construct $\Gamma^{\vec{\sigma}}$ in
the same way as in normal-form games and have each player lose $C$ utility
whenever the other player guesses its action correctly. By playing
$\vec{\sigma}$, each player gets $0$ expected utility. However, if they play
$(\vec{\tau})_{N}$, each player has at most $1/N$ chance of guessing the other
player’s action correctly. Therefore, regardless of how they place their bets,
each player can get at least $1-\frac{C}{N}$ expected utility in
$\Gamma^{\vec{\sigma}}$. If $N$ is large enough, this value is larger than the
utility that they would get with $\vec{\sigma}$.

The main issue presented in Example 3 is that players can spread their actions
really thin, avoiding this way being caught by other players. Even though this
doesn’t always lead to a better equilibrium (e.g., it may happen that no
matter how player $i$ spreads her actions, it is always better for $i$ to
spread them even thinner), this situation is clearly non-desirable. In order
to avoid it, the construction in Section 7 allows players to bet on arbitrary
sets of actions (or arbitrary sets of action profiles when dealing with
Bayesian games) instead of just individual actions. Again, these bets are
calibrated in such a way that no player benefits from betting if all other
players play their part of $\vec{\sigma}$. However, if a player $i$ defects
from $\vec{\sigma}$, betting on the set of actions that $i$ is more likely to
play after defecting always gives a strictly positive payoff. It can be shown
that the rewards and punishments from betting can be calibrated in such a way
that it is always better to follow the proposed equilibrium $\vec{\sigma}$.

##  5 Proof of Theorem 1 for Finite Games

In this section we prove Theorem 1 for the case in which $\Gamma$ is finite.
We extend this proof for infinite games in Section 7.

In the following sections, we prove Theorem 1 for finite normal-form games.
Later, in Section 5.3, we extend the proof to Bayesian games with independent
types.

###  5.1 Construction of $\Gamma^{\sigma}$

In this section we give the precise construction of $\Gamma^{\vec{\sigma}}$.
Define

$A_{i}^{\vec{\sigma}}:=A_{i}\cup\left(A_{i}\times\bigcup_{j\in
P}\left(\\{j\\}\times A_{j}\right)\right).$

Elements of $A_{i}^{\vec{\sigma}}$ are either actions of $A_{i}$ or a tuple
$(a_{i},j,a_{j})$ that indicates that $i$ is playing action $a_{i}$ but is
also betting that player $j$ is playing action $a_{j}$. Suppose that players
play actions $(a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})$ where, for
convenience, we use the notation $b_{i}:=\bot$ to denote that player $i$
placed no bet (i.e., if $i$ played an action in $A_{i}$). The utility
$u^{\vec{\sigma}}_{i}$ of player $i$ is given by

$\begin{array}[]{lll}u^{\vec{\sigma}}_{i}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n}))&:=&u_{i}(a_{1},a_{2},\ldots,a_{n})\\\
&+&w_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n}))\\\
&+&\ell_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})),\end{array}$

where $w_{i}$ is the additional utility that $i$ gets by placing a bet on
another player’s action, and $\ell_{i}$ is the additional (negative) utility
that $i$ gets if another player bets on $i$’s action and wins. If
$p_{(j,a_{j})}^{\vec{\sigma}}$ is the probability that strategy $\sigma_{j}$
assigns to action $a_{j}$, then

$w_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})):=\left\\{\begin{array}[]{ll}0&\mbox{if
}b_{i}=\bot\\\ 1-p_{(j,a_{j})}^{\vec{\sigma}}&\mbox{if }b_{i}\mbox{ is of the
form }(j,a_{j})\\\ -p_{(j,a_{j})}^{\vec{\sigma}}&\mbox{if }b_{i}\mbox{ is of
the form }(j,a)\mbox{ with }a\not=a_{j}.\\\ \end{array}\right.$

It is important to note that, if $j$ does not defect and $i$ bets on $a_{j}$,
then its expected additional utility is given by
$p_{(j,a_{j})}^{\vec{\sigma}}\left(1-p_{(j,a_{j})}^{\vec{\sigma}}\right)+\left(1-p_{(j,a_{j})}^{\vec{\sigma}}\right)\left(-p_{(j,a_{j})}^{\vec{\sigma}}\right)=0$.

Finally, we define $\ell_{i}^{\vec{\sigma}}:=\sum_{j\in
P}\ell_{(i,j)}^{\vec{\sigma}}$, where

$\ell_{(i,j)}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})):=\left\\{\begin{array}[]{ll}0&\mbox{if
}b_{j}=\bot\mbox{ or }b_{j}\mbox{ is of the form }(i,a)\mbox{ with
}a\not=a_{i}\\\ -C&\mbox{otherwise.}\end{array}\right.$

The constant $C$ used in the previous definition is simply a large value that
serves as a deterrent for players to defect from $\vec{\sigma}$: if a player
$i$ follows a different strategy $\tau_{i}$, then there exists some action
$a\in A_{i}$ such that $a$ is played with strictly more probability in
$\tau_{i}$ than in $\sigma_{i}$. If this is the case, because of the way in
which we defined $w_{j}$, it is in the interest of other players $j$ to bet on
$(i,a_{i})$, which decreases $i$’s overall utility. In Section 5.2, we show
that we can choose a value for $C$ so that conditions (a) and (b) of Theorem 1
are satisfied.

###  5.2 Proof of Correctness

####  5.2.1 Part (a)

We start by showing that $\vec{\sigma}$ is a semi-strong Nash equilibrium if
$\Gamma^{\vec{\sigma}}$. First, as observed in the previous section, it is
easy to check that our construction of $\Gamma^{\vec{\sigma}}$ satisfies the
following property:

######  Lemma 1.

Given a strategy profile $\vec{\tau}$ for $\Gamma^{\vec{\sigma}}$, a player
$j\in P$, and an action $a_{j}\in A_{j}$, let $p^{\vec{\tau}}_{(j,a_{j})}$
denote the probability that $j$ plays an action in $A_{j}^{\vec{\sigma}}$ such
that its first component is $a_{j}$. Let $x_{(j,a_{j})}^{\vec{\tau}}$ denote
the expected additional utility of any other player when betting that $j$
plays action $a_{j}$. Then

$x_{(j,a_{j})}^{\vec{\tau}}=p^{\vec{\tau}}_{(j,a_{j})}-p^{\vec{\sigma}}_{(j,a_{j})}$

###### Proof.

The expected additional utility can be computed as follows:

$x_{(j,a_{j})}^{\vec{\tau}}=p^{\vec{\tau}}_{(j,a_{j})}\left(1-p^{\vec{\sigma}}_{(j,a_{j})}\right)+\left(1-p^{\vec{\tau}}_{(j,a_{j})}\right)\left(-p^{\vec{\sigma}}_{(j,a_{j})}\right)=p^{\vec{\tau}}_{(j,a_{j})}-p^{\vec{\sigma}}_{(j,a_{j})}.$

∎

With this, it is straightforward to check that, if $C\geq 1$, $\vec{\sigma}$
is a (standard) Nash equilibrium of $\Gamma^{\vec{\sigma}}$: Fix a player $i$
and assume all other players play $\vec{\sigma}_{-i}$. Since $\vec{\sigma}$ is
a Nash equilibrium of $\Gamma$, regardless of the bets $i$ places, it is a
best response for $i$ to distribute the first component of its action in the
same way as $\sigma_{i}$. It just remains to check that $i$ gets no utility
from placing bets. By Lemma 1, $i$ gets no utility from betting on other
players. Moreover, if $C\geq 1$, $i$ gets negative expected utility by betting
on itself. This shows that $\sigma_{i}$ is indeed a best response for $i$.

Now suppose that $\vec{\sigma}$ does not satisfy the conditions of Definition
1. This would imply that there exists a coalition $S\subseteq P$ and a
strategy profile $\vec{\tau}_{S}$ for players in $S$ such that (a1) all
players $i\in S$ get a strictly better expected utility than
$u_{i}(\vec{\sigma})$, and (b1) no player $i\in S$ is better off defecting
from $\vec{\tau}_{S}$, assuming that the rest of the players play
$(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}})$. Given a strategy
$\tau_{i}$ for some player $i\in P$ in $\Gamma^{\vec{\sigma}}$, denote by
$\tilde{\tau}_{j}$ the strategy for $i$ in $\Gamma$ obtained by projecting the
actions of $A_{j}^{\vec{\sigma}}$ onto their first component (i.e., by getting
rid of the bets). Then, we have the following:

######  Proposition 1.

Let $M$ be the difference between the maximum and minimum utility of $\Gamma$.
If $S$ and $\vec{\tau}_{S}$ satisfy (a1), there exist at least one player
$i\in S$ such that $\tilde{\tau}_{i}\not=\sigma_{i}$.

###### Proof.

If all players $i\in S$ satisfy $\tilde{\tau}_{i}=\sigma_{i}$. Then, by Lemma
1, none of the players in $S$ can increase their utility by placing a bet.
This would imply that their expected utilities are at most the ones they would
get when playing $\vec{\sigma}_{S}$, which contradicts the (a1) assumption.

∎

Proposition 1 implies that if a coalition $S$ with strategy $\vec{\tau}_{S}$
satisfies (a1), there exist at least one player $i\in S$ and an action
$a_{i}\in A_{i}$ such that $i$ is more likely to play $a_{i}$ in
$\vec{\tau}_{S}$ than in $\vec{\sigma}_{S}$. By Lemma 1, betting that $i$ is
going to play $a_{i}$ gives a strictly positive utility to all other players.
In particular, if $S$ and $\vec{\tau}_{S}$ satisfy (b1), all other players in
$S$ must place bets on $i$ or other players in $S$ with probability $1$ since
there exist at least one bet with strictly positive expected utility. Since
there is a finite number of possible bets, we have the following result.

######  Proposition 2.

Let $q_{(i,a_{i})}^{(j,\tau_{j})}$ be the probability that player $j$ bets on
$(i,a_{i})$ when playing $\tau_{j}$. Then, if $S$ and $\vec{\tau}_{S}$ satisfy
(a1) and (b1), there exists a player $i\in S$ and an action $a_{i}\in A_{i}$
such that

$\sum_{j\in S}q_{(i,a_{i})}^{(j,\tau_{j})}\geq\frac{1}{|A|_{max}},$

where $|A|_{max}=\max_{i}\\{|A_{i}|\\}$.

###### Proof.

By proposition 1, there exists a player $i\in S$ such that
$\tilde{\tau}_{i}\not=\sigma_{i}$. Because of (b1), if $i$ is the only player
in $S$ such that $\tilde{\tau}_{i}\not=\sigma_{i}$, all other players in $S$
must bet on $i$ with probability $1$. Since $|S|\geq 2$, it follows that there
exist an action $a\in A_{i}$ such that at least $\frac{1}{|A_{i}|}$ players
bet on $(i,a_{i})$ in expectation.

If there are at least two players $i\in S$ such that
$\tilde{\tau}_{i}\not=\sigma_{i}$ and $S$ and $\vec{\tau}_{S}$ satisfy (a1)
and (b1), then all players in $S$ must place bets on other players in $S$ with
probability $1$. This means that, for a fixed $j\in S$,

$\sum_{i\in S,\ a_{i}\in A_{i}}q_{(i,a_{i})}^{(j,\tau_{j})}=1.$

If we add the equation above for all $j\in S$ we get that

$\sum_{i,j\in S,\ a_{i}\in A_{i}}q_{(i,a_{i})}^{(j,\tau_{j})}=|S|.$

Rearranging the terms of the previous sum, we get

$\sum_{i\in S,\ a_{i}\in A_{i}}\left(\sum_{j\in
S}q_{(i,a_{i})}^{(j,\tau_{j})}\right)=|S|.$

Since the outer sum has at most $|S|\cdot|A|_{max}$ elements, there exists
$i\in S$ and $a_{i}\in A_{i}$ such that

$\sum_{j\in
S}q_{(i,a_{i})}^{(j,\tau_{j})}\geq\frac{|S|}{|S|\cdot|A|_{max}}=\frac{1}{|A|_{max}},$

as desired. ∎

Proposition 2 shows that, if $S$ and $\vec{\tau}_{S}$ satisfy (a1) and (b1),
there exists a player $i\in P$ and an action $a_{i}\in A_{i}$ such that at
least a constant fraction of the players are betting on it in expectation. We
next show that, if $C>\max\\{M\cdot|A|_{max},1\\}$, $i$ can strictly increase
its utility by decreasing the probability of playing $a_{i}$. This would
contradict the fact that $S$ and $\vec{\tau}_{S}$ satisfy (b1) and prove
Theorem 1.

By Proposition 1, the probability $p^{\vec{\tau}}_{(i,a_{i})}$ that $i$ plays
action $a_{i}$ with strategy $\tilde{\tau}_{i}$ must satisfy
$p^{\vec{\tau}}_{(i,a_{i})}>p^{\vec{\sigma}}_{(i,a_{i})}$ since, otherwise,
players could get a better utility by betting somewhere else. The existence of
$a_{i}$ implies that there exists another action $a^{\prime}_{i}\in A_{i}$
such that
$p^{\vec{\tau}}_{(i,a^{\prime}_{i})}<p^{\vec{\sigma}}_{(i,a^{\prime}_{i})}$
(i.e., an action that is played with less probability in $\tilde{\tau}_{i}$
than in $\sigma_{i}$). Since $S$ and $\vec{\tau}_{S}$ satisfy (b1), it is
guaranteed that no player will ever bet on $(i,a_{i}^{\prime})$ since, by
Lemma 1, betting on it gives a strictly negative expected utility. Consider a
strategy $\tau_{i}^{\prime}$ in which $i$ plays in the same way as in
$\tau_{i}$, except that $i$ plays $a_{i}^{\prime}$ whenever it would play
$a_{i}$ in $\tau_{i}$.

Then, we have that

$\begin{array}[]{lll}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})-u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})&=&u_{i}(\vec{\sigma}_{-S},\tilde{\tau}_{S\setminus\\{i\\}},\tilde{\tau}^{\prime}_{i})-u_{i}(\vec{\sigma}_{-S},\tilde{\tau}_{S})\\\
&+&w_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})-w_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\\\
&+&\ell_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})-\ell_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S}).\end{array}$

Let $p_{(i,a_{i})}^{\tilde{\tau}_{i}}$ be the probability that $i$ plays
action $a_{i}$ when following strategy $\tilde{\tau}_{i}$. Then, we can bound
the first term in the sum by

$u_{i}(\vec{\sigma}_{-S},\tilde{\tau}_{S\setminus\\{i\\}},\tilde{\tau}^{\prime}_{i})-u_{i}(\vec{\sigma}_{-S},\tilde{\tau}_{S})\geq-
p_{(i,a_{i})}^{\tilde{\tau}_{i}}M$

since the difference in utility by switching from $a_{i}$ to $a^{\prime}_{i}$
can be at most $-M$. Since $\tau^{\prime}_{i}$ bets exactly in the same way as
$\tau_{i}$ does, we have that
$w_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})-w_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})=0$.
Finally, since the probability that another player bets on $(i,a_{i})$ is at
least $\frac{1}{|A_{i}|}$, the following inequality holds:

$\ell_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})-\ell_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\geq
p_{(i,a_{i})}^{\tilde{\tau}_{i}}\frac{C}{|A_{i}|}.$

In the equation above, we are using the fact that the only difference between
$\tau_{i}$ and $\tau^{\prime}_{i}$ is that $i$ is switching from $a_{i}$ to
another action $a^{\prime}_{i}$ that no player ever bets on. If
$C>M\cdot|A|_{max}$, then

$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})-u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\geq
p_{(i,a_{i})}^{\tilde{\tau}_{i}}\frac{C}{|A_{i}|}-p_{(i,a_{i})}^{\tilde{\tau}_{i}}M>0.$

This would imply that $i$ can increase its utility by switching from
$\tau_{i}$ to $\tau^{\prime}_{i}$, which contradicts our original assumption
that $S$ and $\vec{\tau}_{S}$ satisfy (b1).

####  5.2.2 Part (b)

The proof of part (b) follows from the following proposition.

######  Proposition 3.

If $\vec{\tau}$ is a Nash equilibrium of $\Gamma^{\sigma}$, then
$\tilde{\tau}_{i}=\sigma_{i}$ for all $i\in P$.

Intuitively, this proposition says that all Nash equilibria of
$\Gamma^{\vec{\sigma}}$ are essentially $\vec{\sigma}$ with some bets on top
of it. Note that if $\tilde{\tau}_{i}=\sigma_{i}$ for all $i\in P$, $w_{i}$
gives exactly $0$ utility for all strategies of $i$. Since $\ell_{i}$ is a
negative function, Proposition 3 implies that all Nash equilibria of
$\Gamma^{\vec{\sigma}}$ are Pareto-dominated by $\vec{\sigma}$, as desired.

###### Proof of Proposition 3.

Suppose that there exists a player $i$ such that
$\tilde{\tau}_{i}\not=\sigma_{i}$. An analogous reasoning to the one used for
proving Proposition 2 shows that there exists a player $i\in P$ and an action
$a_{i}\in A_{i}$ such that

$\sum_{j\in S}q_{(i,a_{i})}^{\tau_{j}}\geq\frac{1}{|A|_{max}}.$

Then, analogously to the proof of part (a), it can be shown that $i$ can
strictly increase its utility by switching from $a_{i}$ to another action
$a^{\prime}_{i}$, contradicting the fact that $\vec{\tau}$ is a Nash
equilibrium of $\Gamma^{\sigma}$. ∎

###  5.3 Generalization to Finite Bayesian Games with Independent Types

As shown in Section 4, the construction of $\Gamma^{\vec{\sigma}}$ used for
normal-form games does not work in general for Bayesian games. However, if
types are independent, we have the following proposition that states that, if
a coalition can defect in such a way that they all increase their expected
utility with respect to $\vec{\sigma}$, each player in the coalition must be
able to tell the strategy of another member $j$ of the coalition from
$\sigma_{j}$.

######  Proposition 4.

Let $\Gamma=(P,T,q,A,U)$ be a Bayesian game with independent types. Let $S$ be
a subset of players and $\vec{\tau}_{S}$ be a strategy profile for players in
$S$ such that $u_{i}(\vec{\sigma}_{-S},\vec{\tau}_{S})>u_{i}(\vec{\sigma})$
for all $i\in S$. Then, there exists a player $i\in S$ and an action $a_{i}\in
A_{i}$ such that

$p_{(i,a_{i})}^{\tau_{i}}>p_{(i,a_{i})}^{\sigma_{i}},$

where $p_{(i,a_{i})}^{\tau_{i}}$ (resp., $p_{(i,a_{i})}^{\sigma_{i}}$) is the
probability that player $i$ plays action $a_{i}$ when following strategy
$\tau_{i}$ (resp., $\sigma_{i}$).

###### Proof.

Suppose that $p_{(i,a_{i})}^{\tau_{i}}=p_{(i,a_{i})}^{\sigma_{i}}$ for all
$i\in S$ and all $a_{i}\in A_{i}$. Then, since types are independent, if we
fix a player $i\in S$ and a type $t_{i}$ of $i$, the distribution over action
profiles $\vec{a}_{-i}$ played by the other players $j$ conditioned to the
fact that $i$ has type $t_{i}$ is identical when players in $S$ play
$\vec{\tau}_{S}$ and when players in $S$ play $\vec{\sigma}_{S}$. Therefore,
we would have that

$u_{i}(\vec{\sigma}_{-S},\vec{\tau}_{S})=u_{i}(\vec{\sigma}_{-i},\tau_{i})$

for all $i\in S$, and thus

$u_{i}(\vec{\sigma}_{-i},\tau_{i})>u_{i}(\vec{\sigma}),$

which contradicts the fact that $\vec{\sigma}$ is a Nash equilibrium of
$\Gamma$. ∎

Note that the proof of Proposition 4 requires that the types of the players
are independent. In fact, if they were not, Example 2 shows that players can
defect in such a way that they all benefit while no player $i$ can tell
between the strategy of another player $j$ and $\sigma_{j}$. However, in the
case of independent types, Proposition 4 shows that we can use the same
approach as in the case of normal-form games. Define $A^{\vec{\sigma}}$ as in
Section 5.1, and let

$\begin{array}[]{lll}u^{\vec{\sigma}}_{i}(t_{i},((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})))&:=&u_{i}(t_{i},(a_{1},a_{2},\ldots,a_{n}))\\\
&+&w_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n}))\\\
&+&\ell_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})),\end{array}$

where $w_{i}$ and $\ell_{i}$ are defined in the same way as in Section 5.1 and
$C>\max\\{M\cdot|A|_{\max},1\\}$, as in Section 5.2. An analogous reasoning to
that of the proof of Proposition 2 shows that, if $S$ and $\vec{\tau}_{S}$
satisfy that
$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})>u_{i}^{\vec{\sigma}}(\vec{\sigma})$
for all $i\in S$, and that
$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\geq
u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})$
for all $i\in S$ and all strategies $\tau^{\prime}_{i}$ for $i$, then there
exists a player $i$ and an action $a_{i}$ such that, regardless of $i$’s type,
at least $\frac{1}{|A|_{max}}$ players bet on $(i,a_{i})$ in expectation. The
rest of the proof proceeds as in the case of normal-form games.

##  6 Proof of Theorem 2 for Finite Bayesian Games

The analysis of Example 2 given in Section 4 shows that the construction used
for normal-form games and for Bayesian games with independent types does not
quite work in general for Bayesian games. However, note that if all three
players play $\vec{\tau}$ in Example 2, even though player $1$ cannot tell if
player $2$ or player $3$ are going to play $0$ or $1$, she knows the
following. If her type is $0$, then players $2$ and $3$ are going to play
either $(0,1)$ or $(1,0)$. Otherwise, they are going to play $(0,0)$ or
$(1,1)$. This means that, even if $i$ cannot guess the action of another
player $j$ with higher probability in $\tau_{j}$ than in $\sigma_{j}$, she can
guess the action profile of all other players with higher probability. This
suggests that, instead of allowing players to bet on which action another
player will play, they should be able to bet on action profiles of other
players. This motivates the following construction. Define
$\Gamma^{\vec{\sigma}}:=(P,T,q,A^{\vec{\sigma}},U^{\vec{\sigma}})$. We define
the action set $A_{i}^{\vec{\sigma}}$ of each player as
$A^{\vec{\sigma}}_{i}:=A_{i}\cup A$. As in Section 5.1, we can view each
element of $A^{\vec{\sigma}}_{i}$ with a pair $(a,b)$, where $a$ is the actual
action that $i$ plays and $b\in A_{-i}$ is $i$’s bet over the action profile
of other players. Again, for convenience, whenever $i$ plays an action $a_{i}$
without placing a bet, we will use the pair $(a_{i},\bot)$ instead of $a_{i}$.
The utility of each player $i$ is defined as follows:

$\begin{array}[]{lll}u^{\vec{\sigma}}_{i}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n}))&:=&u_{i}(a_{1},a_{2},\ldots,a_{n})\\\
&+&w_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n}))\\\
&+&\ell_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})),\end{array}$

where $w_{i}^{\vec{\sigma}}$ and $\ell_{i}^{\vec{\sigma}}$ are defined
similarly to their counterparts in Section 5.1. In this case, let
$p^{\vec{\sigma}}_{i,t_{i},\vec{a}_{-i}}$ denote the probability that the
action profile played by $P_{-i}$ is $\vec{a}_{-i}$, conditioned to the fact
that all players play $\vec{\sigma}$ and that player $i$ has type $t_{i}$.
Then, we can define $w_{i}^{\vec{\sigma}}$ as follows:

$w_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})):=\left\\{\begin{array}[]{ll}0&\mbox{if
}b_{i}=\bot\\\ 1-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}&\mbox{if
}b_{i}\mbox{ is of the form }\vec{a}_{-i}\\\
-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}&\mbox{if }b_{i}\mbox{ is of the
form }\vec{a}_{i}^{\prime}\mbox{ with
}\vec{a}_{i}^{\prime}\not=\vec{a}_{-i}.\\\ \end{array}\right.$

Finally, we define
$\ell_{i}^{\vec{\sigma}}:=\sum_{j\not=i}\ell_{(i,j)}^{\vec{\sigma}}$, where

$\ell_{(i,j)}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})):=\left\\{\begin{array}[]{ll}0&\mbox{if
}b_{j}=\bot\mbox{ or }b_{j}\mbox{ is of the form }\vec{a}_{-j}^{\prime}\mbox{
with }\vec{a}_{-j}^{\prime}\not=\vec{a}_{-j}\\\
-C&\mbox{otherwise,}\end{array}\right.$

and $C=2|A|\cdot(M+1)$. Note that, in this case, $\ell_{(i,j)}$ does not
depend on $i$.

To prove that this construction satisfies the properties of Theorem 1 we need
a few preliminary lemmas. Before stating the first of these, we need the
following definition. Given a player $i\in P$, a type $t_{i}\in T_{i}$, and a
strategy profile $\vec{\tau}$, define $\Delta_{(i,t_{i})}^{\vec{\tau}}$ as

$\Delta_{(i,t_{i})}^{\vec{\tau}}=\sum_{\vec{a}_{-i}\in
A_{-i}}\left|p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}\right|.$

Intuitively, $\Delta_{(i,t_{i})}^{\vec{\tau}}$ can be seen as the “Manhattan
distance” between the distributions over actions played by $P_{-i}$ that are
generated when players play $\vec{\sigma}$ and $\vec{\tau}$ respectively,
conditioned to the fact that $i$ has type $t_{i}$. Our first lemma states
that, if players play $\vec{\tau}$, the expected utility of a player $i$ with
type $t_{i}$ is bounded by its expected utility when players play
$\vec{\sigma}$ plus $\Delta_{(i,t_{i})}^{\vec{\tau}}\cdot M$.

######  Lemma 2.

Given a player $i\in P$, its type $t_{i}\in T_{i}$, and a strategy profile
$\vec{\tau}$ for $\Gamma$, denote by $u_{i}(t_{i},\vec{\tau})$ the expected
utility of $i$ when players play $\vec{\tau}$, conditioned to the fact that
$i$ has type $t_{i}$. Then,

$u_{i}(t_{i},\vec{\tau})\leq
u_{i}(t_{i},\vec{\sigma})+\Delta_{(i,t_{i})}^{\vec{\tau}}\cdot M.$

###### Proof.

Player $i$’s expected utility when players play $\vec{\tau}$ conditioned to
the fact that $i$ has type $t_{i}$ is given by

$u_{i}(t_{i},\vec{\tau})=\sum_{a_{i}\in
A_{i}}\tau_{i}(t_{i},a_{i})\left(\sum_{a_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}u_{i}(t_{i},\vec{a})\right),$

where $\tau_{i}(t_{i},a_{i})$ denotes the probability that $i$ plays $a_{i}$
when following strategy $\tau_{i}$, conditioned to the fact that it has type
$t_{i}$.

We can rewrite the sum as

$u_{i}(t_{i},\vec{\tau})=\sum_{a_{i}\in
A_{i}}\tau_{i}(t_{i},a_{i})\left(\sum_{a_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}u_{i}(t_{i},\vec{a})+(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})u_{i}(t_{i},\vec{a})\right).$

Note that, since $\vec{\sigma}$ is a Nash equilibrium, we have that

$\sum_{a_{i}\in A_{i}}\tau_{i}(t_{i},a_{i})\left(\sum_{a_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}u_{i}(t_{i},\vec{a})\right)\leq
u_{i}(t_{i},\vec{\sigma}).$

It remains to show that

$\sum_{a_{i}\in A_{i}}\tau_{i}(t_{i},a_{i})\left(\sum_{a_{-i}\in
A_{-i}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})u_{i}(t_{i},\vec{a})\right)\leq\Delta_{(i,t_{i})}^{\vec{\tau}}\cdot
M.$

Let $M_{min}$ be the minimum utility of any player in $\Gamma$ and $M_{max}$
be the maximum utility of any player in $\Gamma$ (recall that
$M=M_{max}-M_{min}$). Then,

$\sum_{a_{-i}\in
A_{-i}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})u_{i}(t_{i},\vec{a})=\sum_{a_{-i}\in
A_{-i}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})(M_{min}+(u_{i}(t_{i},\vec{a})-M_{min})).$

Since $\sum_{a_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}=\sum_{a_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}=1$, we have that

$\begin{array}[]{ll}&\sum_{a_{-i}\in
A_{-i}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})(M_{min}+(u_{i}(t_{i},\vec{a})-M_{min}))\\\
=&\sum_{a_{-i}\in
A_{-i}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})(u_{i}(t_{i},\vec{a})-M_{min})\\\
\leq&\sum_{a_{-i}\in
A_{-i}}\left|p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}\right|\cdot(M_{max}-M_{min})\\\
=&\Delta_{(i,t_{i})}^{\vec{\tau}}\cdot M.\end{array}$

Therefore,

$\begin{array}[]{ll}&\sum_{a_{i}\in
A_{i}}\tau_{i}(t_{i},a_{i})\left(\sum_{a_{-i}\in
A_{-i}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})u_{i}(t_{i},\vec{a})\right)\\\
\leq&(\Delta_{(i,t_{i})}^{\vec{\tau}}\cdot M)\sum_{a_{i}\in
A_{i}}\tau_{i}(t_{i},a_{i})\\\ =&\Delta_{(i,t_{i})}^{\vec{\tau}}\cdot
M,\end{array}$

as desired.

∎

The second preliminary lemma gives the expected utility that a player can get
by betting on the other players’ actions.

######  Lemma 3.

Given a player $i\in P$, its type $t_{i}\in T_{i}$, and a strategy profile
$\vec{\tau}$ for $\Gamma^{\vec{\sigma}}$. The expected utility that $i$ gets
when betting on action profile $\vec{a}_{-i}$ is given by
$p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}.$

The proof of Lemma 3 is equivalent to that of Lemma 1. The following corollary
is a direct implication.

######  Corollary 1.

Given a player $i\in P$, its type $t_{i}\in T_{i}$, and a Nash equilibrium
$\vec{\tau}$ for $\Gamma^{\vec{\sigma}}$. The maximum expected utility
$w_{i}(t_{i},\vec{\tau}_{i})$ that $i$ can get by betting when players play
$\vec{\tau}$ and $i$ has type $t_{i}$ satisfies

$w_{i}(t_{i},\vec{\tau}_{i})\leq\Delta_{(i,t_{i})}^{\vec{\tau}}$

###### Proof.

By Lemma 3, the maximum utility that $i$ can get by betting, conditioned to
the fact that $i$ has type $t_{i}$ and players play $\vec{\tau}$ is given by

$\max_{\vec{a}_{-i}\in
A_{-i}}\\{p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}\\}.$

By definition, this value is at most $\Delta_{(i,t_{i})}^{\vec{\tau}}$. ∎

The third and final preliminary lemma gives a lower bound on the expected
losses of other players incurred by $i$’s bets.

######  Lemma 4.

Given a player $i\in P$, its type $t_{i}\in T_{i}$, and a Nash equilibrium
$\vec{\tau}$ for $\Gamma^{\vec{\sigma}}$, denote by
$\ell_{j,i}^{\vec{\sigma}}(t_{i},\vec{\tau})$ the expected utility that $j$
loses because of $i$’s bet, conditioned to the fact that $i$ plays $\tau_{i}$
with type $t_{i}$. Then,

$\ell_{j,i}^{\vec{\sigma}}(t_{i},\vec{\tau})\leq-\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}C}{2|A_{-i}|}.$

###### Proof.

If $\Delta_{(i,t_{i})}^{\vec{\tau}}=0$, the lemma is automatically true since
$\ell_{j,i}^{\vec{\sigma}}(t_{i},\vec{\tau})\leq 0$. Therefore, for the rest
of the proof we will assume that $\Delta_{(i,t_{i})}^{\vec{\tau}}>0$, and thus
that there exists an action profile $\vec{a}_{-i}$ such that
$p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}>0$.
By Lemma 3, this implies that there exists at least one bet for $i$ that gives
her strictly positive utility, and therefore that $i$ will always bet with
probability $1$ since $\vec{\tau}$ is a Nash equilibrium.

Let

$X:=\sum_{\begin{subarray}{c}\vec{a}_{-i}\in A_{-i}\\\
p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}\geq
0\end{subarray}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}})$

and

$Y:=\sum_{\begin{subarray}{c}\vec{a}_{-i}\in A_{-i}\\\
p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}<0\end{subarray}}(p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}).$

We have that

$X+Y=\sum_{\vec{a}_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-\sum_{\vec{a}_{-i}\in
A_{-i}}p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}=0.$

Moreover, by definition, $X-Y=\Delta_{(i,t_{i})}^{\vec{\tau}}.$ Putting the
last two equations together we get that
$X=\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}}{2}$. Therefore, since $X$ is a sum
of at most $|A_{-i}|$ terms, there exists an action profile $\vec{a}_{-i}\in
A_{-i}$ such that

$p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}\geq\frac{1}{|A_{-i}|}\cdot\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}}{2}=\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}}{2|A_{-i}|}.$

We show next that the loss of every other player when $i$ bets on an action
that maximizes
$p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}$
is upper-bounded by $-\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}C}{2|A_{-i}|}$.
Note that this completes the proof since, by Lemma 3, $i$ will always bet on
actions that maximize
$p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}$
since $\vec{\tau}$ is a Nash equilibrium.

Let $\vec{a}_{-i}$ be an action profile that maximizes
$p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}-p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}$.
The expected loss $\ell_{j,i}^{\vec{\sigma}}(t_{i},\vec{a}_{-i})$ of every
other player $j$ when $i$ bets on $\vec{a}_{-i}$ and $i$ has type $t_{i}$ is
given by

$\ell_{j,i}^{\vec{\sigma}}(t_{i},\vec{a}_{-i})=p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}\cdot(-C).$

Since $p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\tau}}\geq
p_{(i,t_{i},\vec{a}_{-i})}^{\vec{\sigma}}+\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}}{2|A_{-i}|}\geq\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}}{2|A_{-i}|}$,
we get that

$\ell_{j,i}^{\vec{\sigma}}(t_{i},\vec{a}_{-i})\leq-\frac{\Delta_{(i,t_{i})}^{\vec{\tau}}C}{2|A_{-i}|},$

and this completes the proof. ∎

With Lemmas 2 and 4, and Corollary 1, we are ready to prove Theorem 1. Let $S$
be a coalition of players and $\vec{\tau}_{S}$ be a strategy profile for
players in $S$ such that (a1)
$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})>u_{i}^{\vec{\sigma}}(\vec{\sigma})$
for all $i\in S$, and (b1)
$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\geq
u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})$
for all $i\in S$ and all strategies $\tau^{\prime}_{i}$ for $i$. By
construction, we have that

$\begin{array}[]{lll}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})&=&u_{i}(\vec{\sigma}_{-S},\tilde{\tau}_{S})\\\
&+&w_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\\\
&+&\ell_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S}).\end{array}$

If we denote by $p(i,t_{i})$ the probability that $i$ gets type $t_{i}$
according to distribution $p$, can rewrite the previous identity as

$\begin{array}[]{lll}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})&=&\sum_{t_{i}\in
T_{i}}p(i,t_{i})u_{i}(t_{i},(\vec{\sigma}_{-S},\tilde{\tau}_{S}))\\\
&+&\sum_{t_{i}\in
T_{i}}p(i,t_{i})w_{i}^{\vec{\sigma}}(t_{i},(\vec{\sigma}_{-S},\vec{\tau}_{S}))\\\
&+&\sum_{j\in
S\setminus\\{i\\}}\ell_{(i,j)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S}).\end{array}$

Applying Lemma 2 and Corollary 1 we get that

$\begin{array}[]{lll}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})&\leq&\sum_{t_{i}\in
T_{i}}p(i,t_{i})(u_{i}(t_{i},\vec{\sigma})+\Delta^{(\vec{\sigma}_{-S},\tilde{\tau}_{S})}_{(i,t_{i})}\cdot
M)\\\ &+&\sum_{t_{i}\in
T_{i}}p(i,t_{i})\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}\\\
&+&\sum_{j\in
S\setminus\\{i\\}}\ell_{(i,j)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S}),\end{array}$

which can be written as

$\begin{array}[]{lll}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})&\leq&\sum_{t_{i}\in
T_{i}}p(i,t_{i})(u_{i}(t_{i},\vec{\sigma})+\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}\cdot(M+1))\\\
&+&\sum_{j\in
S\setminus\\{i\\}}\ell_{(i,j)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S}),\end{array}$

By linearity of expectation, this implies that

$\begin{array}[]{lll}\sum_{i\in
S}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})&\leq&\sum_{i\in
S}\sum_{t_{i}\in
T_{i}}p(i,t_{i})(u_{i}(t_{i},\vec{\sigma})+\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}\cdot(M+1))\\\
&+&\sum_{i\in S}\sum_{j\in
S\setminus\\{i\\}}\ell_{(i,j)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S}).\end{array}$
(1)

Note that $\sum_{i\in S}\sum_{j\in
S\setminus\\{i\\}}\ell_{(i,j)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})=\sum_{i\in
S}\sum_{j\in
S\setminus\\{i\\}}\ell_{(j,i)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})$.
Moreover, we can write
$\ell_{(j,i)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})$ as
$\sum_{t_{i}\in
T_{i}}p(i,t_{i})\ell_{(j,i)}^{\vec{\sigma}}(t_{i},(\vec{\sigma}_{-S},\vec{\tau}_{S}))$.
Therefore, by Lemma 4, we get that

$\ell_{(j,i)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\leq\sum_{t_{i}\in
T_{i}}-p(i,t_{i})\cdot\frac{\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}C}{2|A_{-i}|}.$

This implies that

$\sum_{i\in S}\sum_{j\in
S\setminus\\{i\\}}\ell_{(j,i)}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\leq\sum_{i\in
S}\sum_{t_{i}\in
T_{i}}-p(i,t_{i})\cdot(|S|-1)\cdot\frac{\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}C}{2|A_{-i}|}$

Inserting this into Equation 1 gives that

$\sum_{i\in
S}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\leq\sum_{i\in
S}\sum_{t_{i}\in
T_{i}}p(i,t_{i})\left[(u_{i}(t_{i},\vec{\sigma})+\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}\cdot(M+1))-(|S|-1)\cdot\frac{\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}C}{2|A_{-i}|}\right].$

Since $C=2|A|\cdot(M+1)$, it follows that

$(|S|-1)\cdot\frac{\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}C}{2|A_{-i}|}\geq\Delta^{(\vec{\sigma}_{-S},\vec{\tau}_{S})}_{(i,t_{i})}\cdot(M+1),$

and therefore

$\sum_{i\in
S}u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\leq\sum_{i\in
S}\sum_{t_{i}\in T_{i}}p(i,t_{i})u_{i}(t_{i},\vec{\sigma})=\sum_{i\in
S}u_{i}(\vec{\sigma}).$

This implies that there exists at least one player $i\in S$ such that
$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\leq
u_{i}(\vec{\sigma})$, which contradicts the (a1) assumption. This proves
Theorem 1 part (a). Part (b) follows from the same argument with $S=P$.

##  7 Proof of Theorems 1 and 2, Infinite Case

As stated in Section 3, the proof of Theorem 1 can be generalized to games in
which the sets of actions and types are infinite. We’ll prove this
generalization in the case where $\Gamma$ is a normal-form game. The
generalization in the case of Bayesian games is identical, except that we use
the proofs and constructions from Sections 5.3 and 6 as a starting point (as
opposed to the proofs and constructions of Section 5.2).

For ease of exposition, we will begin by generalizing the constructions given
in previous sections to games with a countable number of actions. The proof
for arbitrary sets is given in Section 7.2 and follows the same lines.

###  7.1 Countable Case

As suggested by Example 3, the proof given in Section 5.1 does not quite work
when the sets of actions are infinite. In fact, the construction for finite
games uses the fact that if a coalition $S$ defects, there exists a player $i$
and an action $a$ such that $\frac{1}{|A|_{max}}$ of the players bet on
$(i,a)$ in expectation. This allowed us to adjust $C$ so that it is never
beneficial for $i$ to play $a$. If the game is infinite, there is no lower
bound of the expected number of players that bet on a particular action, and
therefore there is no value of $C$ that does the trick.

We can avoid this problem by slightly modifying the bet space. Suppose that
instead of betting on pairs $(i,a)$ with $i\in P$ and $a\in A_{i}$, players
can bet on pairs $(i,X)$ with $i\in P$ and $X\subseteq A_{i}$. Given the
actions and bets $(a_{1},b_{1}),\ldots,(a_{n},b_{n})$ of the players, we
define the utilities of $\Gamma^{\vec{\sigma}}$ as in Section 5.1, except that

$w_{i}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})):=\left\\{\begin{array}[]{ll}0&\mbox{if
}b_{i}=\bot\\\ 1-p_{(j,X)}^{\vec{\sigma}}&\mbox{if }b_{i}\mbox{ is of the form
}(j,X)\mbox{ with }a_{j}\in X\\\ -p_{(j,X)}^{\vec{\sigma}}&\mbox{if
}b_{i}\mbox{ is of the form }(j,X)\mbox{ with }a_{j}\not\in X\\\
\end{array}\right.$

where $p_{(j,X)}^{\vec{\sigma}}$ is the probability that the first component
of $j$’s action is in $X$, assuming that $j$ uses strategy $\sigma_{j}$, and

$\ell_{(i,j)}^{\vec{\sigma}}((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n})):=\left\\{\begin{array}[]{ll}0&\mbox{if
}b_{j}=\bot\mbox{ or }b_{j}\mbox{ is of the form }(i,X)\mbox{ with }a\not\in
X\\\ -M-1&\mbox{otherwise,}\end{array}\right.$

where $M$ is the difference between the supremum and the infimum utility that
a player can get in $\Gamma$. An analogous reasoning to that of Lemma 1 shows
that the expected utility $x^{\tau_{j}}_{(j,a_{j})}$ that a player gets by
betting on $(j,X)$ conditioned to the fact that $j$ is playing strategy
$\tau_{j}$, is given by

$x^{\tau_{j}}_{(j,a_{j})}:=p_{(j,X)}^{\tau_{j}}-p_{(j,X)}^{\sigma_{j}}.$

This implies that if player $j$ plays some action $a$ with more probability in
$\tau_{j}$ than in $\sigma_{j}$, including action $a$ in $X$ strictly
increases the expected utility of betting on $(j,X)$. This proves the
following lemma.

######  Lemma 5.

Given a normal-form game $\Gamma=(P,A,U)$, let $S\subset P$ be a subset of
players and $\vec{\tau}_{S}$ be a strategy for players in $S$ in
$\Gamma^{\vec{\sigma}}$ such that
$u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S})\geq
u_{i}^{\vec{\sigma}}(\vec{\sigma}_{-S},\vec{\tau}_{S\setminus\\{i\\}},\tau^{\prime}_{i})$
for all $i\in S$ and all strategies $\tau^{\prime}_{i}$ for $i$. For each
player $i\in S$, let $X_{i}^{>}$ (resp., $X_{i}^{<}$) be the set of all
actions $a\in A_{i}$ such that the probability that $i$ plays $a$ with
$\tilde{\tau}_{i}$ is strictly greater (resp., smaller) than the probability
that $i$ plays $a$ with $\sigma_{i}$. Then, all bets of the form $(i,X)$ that
may occur with positive probability when playing
$(\vec{\sigma}_{-S},\vec{\tau}_{S})$ must satisfy that $X_{i}^{>}\subseteq X$
and $X_{i}^{<}\cap X=\emptyset$.

With Lemma 5, we can use a similar argument to the one used in the finite
case. Suppose that a coalition $S$ defects from the proposed strategy
following strategy profile $\vec{\tau}_{S}$ in such a way that (a1) all
players in $S$ get more utility with $\vec{\tau}_{S}$ than with $\vec{\sigma}$
and (b1) no player in $S$ can further increase its utility by defecting from
$\vec{\tau}_{S}$. Then, it is straightforward to check that, if (a1) is
satisfied, all players in $S$ bet with probability $1$. Therefore, there
exists a player $i\in S$ such that at least one other player bets on $i$ in
expectation. By Lemma 5, all of these bets must include all elements in
$X_{i}^{>}$ and none of them includes any element of $X_{i}^{<}$. Therefore,
if $i$ reduces the probability of playing any action in $X_{i}^{>}$ by
$\delta$ and increases the probability of playing any action in $X_{i}^{<}$ by
$\delta$, an analogous reasoning to the one at the end of Section 5.2 shows
that the utility of $i$ increases at least by

$\delta(M+1)-\delta M,$

which contradicts the (b1) assumption. The proof for Bayesian games follow the
same generalization (betting on sets of actions or action profiles rather than
on individual actions or action profiles), using as a basis the constructions
in Sections 5.3 and 6.

###  7.2 Uncountable Case

The idea used for the countable case can be generalized for any probability
space, although the proof is much more technical. We begin by giving the basic
notions on probability theory, and then move to the desired generalization.

####  7.2.1 Basic Definitions

Given a set $X$, a _$\sigma$ -algebra_ on $X$ is a collection $\Sigma$ of
subsets of $X$ that is closed under complement, countable unions, and
countable intersections. This means that,

  * •

$Y\in\Sigma\Longrightarrow\overline{Y}\in\Sigma$, where $\overline{Y}$ denotes
the complement of $Y$ in $X$ (i.e., $X\setminus Y$).

  * •

If $\\{X_{i}\\}_{i=1}^{\infty}$ is a countable collection of elements of
$\Sigma$, then both $\bigcup_{i\geq 1}X_{i}$ and $\bigcup_{i\geq 1}X_{i}$ are
also elements of $\Sigma$.

A pair $(X,\Sigma)$ consisting of a set $X$ and a $\sigma$-algebra $\Sigma$ on
$X$ is called a _measurable space_. Given a measurable space $(X,\Sigma)$, a
measure on $(X,\Sigma)$ is a function
$\mu:\Sigma\longrightarrow\mathbb{R}\cup\\{-\infty,+\infty\\}$ that satisfies

  * •

$\mu(\emptyset)=0$.

  * •

Non-negativity: $\mu(Y)\geq 0$ for all $Y\in\Sigma$.

  * •

Countable additivity: For all countable collections
$\\{X_{i}\\}_{i=1}^{\infty}$ of pairwise disjoint sets in $\Sigma$,
$\mu(\bigcup_{i=1}^{\infty}X_{i})=\sum_{i=1}^{\infty}\mu(X_{i})$.

Intuitively, a measure is a non-negative function that assigns $0$ to the
empty set and such that the measure of a countable union disjoint sets is the
sum of their measures.

With these definitions, we can define a probability space. A probability space
is a tuple $(X,\Sigma,P)$, where $(X,\Sigma)$ is a $\sigma$-algebra, and $P$
is a measure such that the image of all elements of $\Sigma$ is in $[0,1]$,
and such that the measure of the whole space is $1$. More precisely, $P$ must
satisfy that

  * •

$P(E)\in[0,1]$ for all $E\in\Sigma$.

  * •

$P(X)=1$.

In the next sections we will assume that, in a normal-form game $\Gamma$, the
action sets $A_{i}$ of each player have an embedded $\sigma$-algebra
$\Sigma_{i}$, and the strategy of each player $i$ consists of choosing a
measure $Q_{i}$ such that $(A_{i},\Sigma_{i},Q_{i})$ is a probability space.
Intuitively, this means that $i$ cannot choose which sets of $A_{i}$ are
measurable, but it can choose what probability it is assigned to each of these
sets (i.e., with what probability each action is sampled). Given the strategy
$P_{i}$ of each player, the probability space $(A,\Sigma,Q)$ that gives the
probability of each subset of action profiles when each player plays $Q_{i}$
is precisely the product of $(A_{i},\Sigma_{i},P_{i})$ for all $i\in P$, in
which $A:=A_{1}\times A_{2}\times\ldots\times A_{n}$,
$\Sigma:=\sigma(\Sigma_{1}\otimes\ldots\otimes\Sigma_{n})$ (i.e., the
$\sigma$-algebra generated by sets of the form $(X_{1},\ldots,X_{n})$ with
$X_{i}\in\Sigma_{i}$ for all $i$), and $Q:=Q_{1}\times\ldots\times Q_{n}$,
which is the unique measure function such that
$Q(X_{1},\ldots,X_{n})=Q_{1}(X_{1})Q_{2}(X_{2})\ldots Q_{n}(X_{n})$. Fixing
$(A,\Sigma,Q)$, the expected utility of a player $i$ is given by the Lebesgue
integral

$u_{i}(Q):=\int_{A}u_{i}(X)\ dQ.$

In order to avoid confusion between the strategy profile $\vec{\sigma}$ of
Theorems 1 and 2 and the $\sigma$ used in the definition of $\sigma$-algebras,
in the next sections we will use $Q$ instead of $\vec{\sigma}$ to denote the
Nash equilibrium of Theorems 1 and 2.

####  7.2.2 Construction of $\Gamma^{Q}$

The construction of $\Gamma^{Q}$ for arbitrary probability spaces is quite
similar to the one given in Section 7.1. In fact, we define
$A_{i}^{Q}:=A_{i}\cup\left(A_{i}\times\bigcup_{j\in
P}(\\{j\\}\times\Sigma_{j})\right)$. Intuitively, $i$ can either play an
action in $A_{i}$, or play an action in $A_{i}$ and simultaneously bet that
the action that another player $j$ plays is in some measurable subset
$S\in\Sigma_{j}$. The $\sigma$-algebra of $A_{i}^{Q}$ is the one spanned by
$\Sigma_{i}$ and
$\sigma(\Sigma_{i}\otimes\mathcal{P}(\\{j\\}\times\Sigma_{j}))$ for each $j\in
P$ (where $\mathcal{P}(S)$ denotes the power set of a set $S$).

We define $U^{Q}$ exactly in the same way as in Section 7.1. Note that
$p_{(j,X)}^{Q}$ is well defined since, by construction, $X$ must belong to
$\Sigma_{j}$. In fact, $p_{(j,X)}^{Q}=Q_{j}(X)$.

####  7.2.3 High Level Proof

A similar argument to the one given in Lemma 1 shows that, if players follow
strategy profile $Q^{\prime}$, the expected utility that a player $i$ gets
when betting on $(j,S)$ for some $S\in\Sigma_{j}$ is given by
$\tilde{Q}^{\prime}_{j}(S)-Q_{j}(S)$ (where, again, $\tilde{Q}^{\prime}$ is
the projection of $Q^{\prime}$ onto its first component). Therefore, it is
optimal for player $i$ to bet on sets that maximize
$\tilde{Q}^{\prime}_{j}(S)-Q_{j}(S)$ with probability $1$. However, it is not
clear at first if such a bet always exists, since it could be the case that
the supremum of $\\{\tilde{Q}^{\prime}_{j}(S)-Q_{j}(S)\\}_{S\in\Sigma_{j}}$ is
never attained in $\Sigma_{j}$. The first part of the proof is precisely
showing that such a bet always exists.

######  Proposition 5.

Let $\Gamma^{Q}$ be the game constructed in Section 7.2.2 and let $j\in P$ be
a player that plays strategy $Q^{\prime}_{j}$. Then, for all other players
$i\in P$, there exists a maximal and a minimal bet of the form $(j,X)$.

The proof of Proposition 5 is somewhat technical and will be shown in Section
7.2.4. Once we have Proposition 5, the second part of the proof is showing
that, among all sets $X$ that maximize or minimize the bets on $j$, there
exists one that minimizes $Q(X)$.

######  Proposition 6.

Let $\Gamma^{Q}$ be the game constructed in Section 7.2.2 and let $j\in P$ be
a player that plays strategy $Q^{\prime}_{j}$. Let
$\Sigma_{Q^{\prime}_{j}}^{+}$ and $\Sigma_{Q^{\prime}_{j}}^{-}$ be the subsets
of $\Sigma_{j}$ that maximize and minimize
$\tilde{Q}^{\prime}_{j}(S)-Q_{j}(S)$, respectively. Then, there exists a set
$X^{+}\in\Sigma_{Q^{\prime}_{j}}^{+}$ and a set
$X^{-}\in\Sigma_{Q^{\prime}_{j}}^{-}$ such that $X^{+}\cap X^{-}=\emptyset$,
$Q(X^{+})\leq Q(X)$ for all $X\in\Sigma_{Q^{\prime}_{j}}^{+}$ and
$Q(X^{-})\leq Q(X)$ for all $X\in\Sigma_{Q^{\prime}_{j}}^{-}$.

The proof of Proposition 6 is quite similar to that of Proposition 5 and is
also shown in Section 7.2.4. With these propositions we are ready to give
complete the proof of correctness of the construction given in Section 7.2.2.
Suppose that a subset $S$ of players with $|S|\geq 2$ defects from $Q_{S}$ to
another strategy profile $Q^{\prime}_{S}$ in such a way that (a1)
$u_{i}^{Q}(Q_{-S},Q^{\prime}_{S})>u_{i}^{Q}(Q)$ for all $i\in S$, and (b1)
$u_{i}^{Q}(Q_{-S},Q^{\prime}_{S\setminus\\{i\\}},Q^{\prime\prime}_{i})\leq
u_{i}^{Q}(Q_{-S},Q^{\prime}_{S})$ for all $i\in S$ and all strategies
$Q^{\prime\prime}_{i}$ for $i$. Then, there must exist a player $i\in S$ and a
subset $X\in\Sigma_{i}$ such that $\tilde{Q}^{\prime}_{i}(X)\not=Q_{i}(X)$
since, otherwise, all bets would give $0$ expected utility and all players
would get at most the expected utility they’d get with $Q$, which contradicts
(a). If $\tilde{Q}^{\prime}_{i}(X)\not=Q_{i}(X)$, it means that either
$\tilde{Q}^{\prime}_{i}(X)-Q_{i}(X)>0$ or
$\tilde{Q}^{\prime}_{i}(\overline{X})-Q_{i}(\overline{X})>0$, which implies
that all other players in $S$ must place bets with probability $1$ (otherwise,
it contradicts (b1)). It is easy to check that, if this is the case, there
exists a player $j$ such that the expected number of other players that bet on
$j$ is at least $1$. Let $X^{+}$ and $X^{-}$ be the subsets given in
Proposition 6 (for player $j$) and consider a strategy $Q^{\prime\prime}_{j}$
bets in the same way as in $Q^{\prime}_{j}$ but that intuitively does the
following in order to select an action in $A_{j}$:

  1. 1.

Step 1: $j$ samples an action $a$ according to $Q^{\prime}_{j}$.

  2. 2.

Step 2: If $a\not\in X^{+}$, $j$ plays $a$.

  3. 3.

Step 3: Otherwise, $j$ sequentially samples an action $a$ according to $Q_{j}$
until $a\in X^{-}$. Then, $j$ plays $a$.

Note that this algorithm always terminates since
$\tilde{Q}^{\prime}_{j}(X^{-})-Q_{j}(X^{-})<0$, which means that
$Q_{j}(X^{-})>0$. More precisely, what $j$ is doing is selecting an action in
$A_{i}$ according to the probability measure $\tilde{Q}^{\prime\prime}_{j}$ on
$(A_{j},\Sigma_{j})$ defined by

$\tilde{Q}^{\prime\prime}_{j}(X):=\tilde{Q}^{\prime}_{j}(X\setminus
X^{+})+\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}Q_{j}(X\cap X^{-}).$

It is straightforward to check that $\tilde{Q}^{\prime\prime}_{j}(X)$ is
indeed a probability measure on $(A_{j},\Sigma_{j})$:

  * •

$\tilde{Q}^{\prime\prime}_{j}(\emptyset)=\tilde{Q}^{\prime}_{j}(\emptyset)+\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}Q_{j}(\emptyset)=0$.

  * •

$\tilde{Q}^{\prime\prime}_{j}(A_{j})=\tilde{Q}^{\prime}_{j}(A_{j})-\tilde{Q}^{\prime}_{j}(X^{+})+\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}Q_{j}(X^{-})=1$.

  * •

If $\\{X_{i}\\}_{i\geq 1}$ is a countable sequence of pairwise disjoint
subsets in $\Sigma_{j}$, we have that $\left(\bigcup_{i\geq
1}X_{i}\right)\setminus X^{+}=\bigcup_{i\geq 1}(X_{i}\setminus X^{+})$, and
$\left(\bigcup_{i\geq 1}X_{i}\right)\cap X^{-}=\bigcup_{i\geq 1}(X_{i}\cap
X^{-})$. Moreover, the subsets of the form $X_{i}\setminus X^{+}$ are pairwise
disjoint, and so are those of the form $X_{i}\cap X^{-}$. Therefore,

$\tilde{Q}^{\prime\prime}_{j}\left(\bigcup_{i\geq 1}X_{i}\right)=\sum_{i\geq
1}\tilde{Q}^{\prime}_{j}(X_{i}\setminus
X^{+})+\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}\sum_{i\geq
1}Q_{j}(X_{i}\cap X^{-})=\sum_{i\geq 1}\tilde{Q}^{\prime\prime}_{j}(X_{i}).$

We show next that $j$ strictly improves its utility by switching from
$Q^{\prime}_{j}$ to $Q^{\prime\prime}_{j}$. Recall that the expected utility
$u_{j}^{Q}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})$ that
$j$ gets when playing strategy $Q^{\prime\prime}_{j}$ can be decomposed as

$\begin{array}[]{lll}u_{j}^{Q}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})&=&u_{j}(Q_{-S},\tilde{Q}^{\prime}_{S\setminus\\{j\\}},\tilde{Q}^{\prime\prime}_{j})\\\
&+&w_{j}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})\\\
&+&\ell_{j}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j}).\\\
\end{array}$

As in previous sections,
$w_{j}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})=w_{j}(Q_{-S},Q^{\prime}_{S})$
since, by construction, $j$ places the same bets in $Q^{\prime}_{j}$ and
$Q^{\prime\prime}_{j}$. We finish with the following lemma, whose proof is
given in Section 7.2.4.

######  Lemma 6.

$\begin{array}[]{ll}u_{j}(Q_{-S},\tilde{Q}^{\prime}_{S\setminus\\{j\\}},\tilde{Q}^{\prime\prime}_{j})-u_{j}(Q_{-S},\tilde{Q}^{\prime}_{S})\leq
Q^{\prime}_{j}(X^{+})M\\\
\ell_{j}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})-\ell_{j}(Q_{-S},Q^{\prime}_{S})>Q^{\prime}_{j}(X^{+})M.\end{array}$

Note that this lemma implies that
$u_{j}^{Q}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})>u_{j}(Q_{-S},Q^{\prime}_{S})$,
contradicting the (b1) assumption. This completes the proof of Theorem 1 part
(a). A similar argument can be used to prove part (b), as done in Section
5.2.2.

####  7.2.4 Proof of the Technical Results

In this section, we prove the technical propositions and lemmas given in the
previous section.

We begin with Proposition 5. Its proof follows from the following lemma.

######  Lemma 7.

Let $\Sigma$ be a $\sigma$-algebra and let $f:\Sigma\longrightarrow\mathbb{R}$
be a bounded function. Then, $f$ has a global minimum and a global maximum on
$\Sigma$.

Note that Proposition 5 is an immediate consequence of Lemma 7 since the
expected utility of a bet is bounded between $1$ and $-1$. To prove Lemma 7 we
need the following well-known result.

######  Lemma 8.

Let $\Sigma$ be a $\sigma$-algebra on some set $\Omega$, let
$\\{X_{n}\\}_{n\geq 1}$ be a sequence of elements of $\Sigma$, and let $f$ be
a function from $\Sigma$ to $\mathbb{R}$ that satisfies countable additivity
and such that

  * (a)

$X_{n}\subseteq X_{n+1}$ for all $n\in\mathbb{N}$, and

  * (b)

$\lim_{n\rightarrow\infty}f(X_{n})=L$, for some $L\in\mathbb{R}$.

Then $f\left(\bigcup_{n\geq 1}X_{n}\right)=L$.

###### Proof.

Let $Y_{n}:=X_{n+1}\setminus X_{n}$. Then, by (a), $X_{1}$ and all sets
$Y_{n}$ are pairwise disjoint. Therefore, since $f$ satisfies countable
additivity, we have that

$f\left(\bigcup_{i=1}^{n}X_{i}\right)=f(X_{n})=f(X_{1})+\sum_{i=1}^{n-1}f(Y_{i}).$

Since $\lim_{n\rightarrow\infty}f(X_{n})=L$, it means that the sum is
convergent and the limit is equal to $L-f(X_{1})$. Therefore,

$f\left(\bigcup_{n\geq 1}X_{n}\right)=f(X_{1})+\sum_{i=1}^{\infty}f(Y_{i})=L.$

∎

To prove Lemma 7 we also need the following observation.

######  Lemma 9.

Let $\Sigma$ be a $\sigma$-algebra on some set $\Omega$ and let $f$ be a
function from $\Sigma$ to $\mathbb{R}$ that satisfies countable additivity and
such that $f(X)\leq L$ for all $X\in\Sigma$. Let $a_{1},a_{2},\ldots,a_{n}$ be
a finite sequence of positive real numbers and $X_{1},X_{2},\ldots,X_{n}$ be a
finite sequence of elements of $\Sigma$ such that $f(X_{i})>L-a_{i}$. Then,

$f\left(\bigcap_{i=1}^{n}X_{i}\right)>L-\sum_{i=1}^{n}a_{i}$

.

###### Proof.

We will only show this result for $n=2$. The general case follows by
induction.

Given two sets $X$ and $Y$ in $\Sigma$ such that $f(X)>L-a$ and $f(Y)>L-b$,
let $X^{\prime}=X\setminus Y$ and let $Y^{\prime}=Y\setminus X$. Then, we have
that

$\begin{array}[]{lll}f(X^{\prime})+f(X\cap Y)&>&L-a\\\ f(Y^{\prime})+f(X\cap
Y)&>&L-b\\\ f(X\cup Y)&\leq&L\end{array}$

Writing $X\cup Y$ as $X^{\prime}\cup Y^{\prime}\cup(X\cap Y)$, we can add the
first two equations and substract the third one to get the desired result. ∎

With these lemmas we are ready to prove Lemma 7.

###### Proof of Lemma 7.

We will only show that $f$ has a global maximum since, if $X$ is a global
maximum of $f$, then $\overline{X}$ is a global minimum (and viceversa). Let
$L$ be the supremum of $\\{f(X)\\}_{X\in\Sigma}$ and let $X_{1},X_{2},\ldots$
be a sequence of elements of $\Sigma$ such that $f(X_{n})>L-\frac{1}{2^{n}}$.
Let $Y_{m}^{n}=\bigcap_{i=m}^{n}X_{i}$. By Lemma 9 we have that
$f(Y_{m}^{n})>L-\sum_{i=m}^{n}\frac{1}{2^{i}}=L-(\frac{1}{2^{m-1}}-\frac{1}{2^{n}})$.

If we take the limit when $n\rightarrow\infty$, we have that
$f(Y_{m}^{\infty})>L-\frac{1}{2^{m-1}}$ (note that $Y_{m}^{\infty}\in\Sigma$
since $\Sigma$ is closed under countable intersections). By construction,
$Y_{m}^{\infty}\subseteq Y_{m+1}^{\infty}$ for all $m\in\mathbb{N}$. Moreover,

$\lim_{m\rightarrow\infty}f(Y_{m}^{\infty})=\lim_{m\rightarrow\infty}L-\frac{1}{2^{m-1}}=L.$

By Lemma 8, this means that

$f\left(\bigcup_{m=1}^{\infty}Y_{m}^{\infty}\right)=L.$

This completes the proof. ∎

The proof of Proposition 6 is analogous to that of Proposition 5. The key
observation is that the set of maximal and the set of minimal bets are closed
under countable unions and intersections, which means that we can do an
analogue of the proof of Lemma 7 restricted to $\Sigma_{Q_{j}^{+}}$ and to
$\Sigma_{Q_{j}^{-}}$. To prove this, note that if $f$ is a countably additive
bounded function defined on a $\sigma$-algebra $\Sigma$, we have that
$f(X)=f(X\cap Y)+f(X\setminus Y)$ and $f(Y)=f(X\cap Y)+f(Y\setminus X)$ for
any two sets $X,Y\in\Sigma$. If Both $X$ and $Y$ maximize $f$, then
$f(Y\setminus X)=f(X\setminus Y)=0$. Otherwise, $f(X\cap Y)$ or $f(X\cup Y)$
would be strictly greater than $f(X)$. This implies that $f(X\cap Y)=f(X\cup
Y)=f(X)=f(Y)$.

It is important to note that if we restrict the proof of Lemma 7 to
$\Sigma_{Q_{j}^{+}}$ and to $\Sigma_{Q_{j}^{-}}$, finding the minimum does not
reduce to finding the maximum (as we did in Lemma 7) since
$\Sigma_{Q_{j}^{+}}$ and $\Sigma_{Q_{j}^{-}}$ are not closed under
complements. However, we can reproduce an analogous proof using analogues to
Lemma 8 and Lemma 9 for intersections and infimums, respectively. Finally,
note that we can assume w.l.o.g. that the sets $X^{+}$ and $X^{-}$ in
Proposition 6 are disjoint since, if $X^{+}\cap X^{-}\not=\emptyset$, then we
can use the same argument as above to show that
$Q^{\prime}_{j}(X^{\cap}X^{-})=Q_{j}(X^{\cap}X^{-})=0$. If this happens, we
can take $X^{+}\setminus X^{-}$ and $X^{-}\setminus X^{+}$ instead of $X^{+}$
and $X^{-}$.

It remains to show Lemma 6.

###### Proof of Lemma 6.

We prove each equation separately.

First equation:
$u_{j}(Q_{-S},\tilde{Q}^{\prime}_{S\setminus\\{j\\}},\tilde{Q}^{\prime\prime}_{j})-u_{j}(Q_{-S},\tilde{Q}^{\prime}_{S})\leq
Q^{\prime}_{j}(X^{+})M$.

For simplicity, let $R$ denote the strategy profile where players in $S$ play
$\tilde{Q}^{\prime}_{S}$ and the rest of the players play $Q_{-S}$.

By definition,

$u_{j}(R_{-j},\tilde{Q}^{\prime\prime}_{j})=\int_{A}u_{j}(X)\
d(R_{-j},\tilde{Q}^{\prime\prime}_{j}).$

We can split $A$ into $\Omega_{1}:=X^{+}\times A_{-i}$ and
$\Omega_{2}:=(A_{i}\setminus X^{+})\times A_{-i}$ to get

$u_{j}(R_{-j},\tilde{Q}^{\prime\prime}_{j})=\int_{\Omega_{1}}u_{j}(X)\
d(R_{-j},\tilde{Q}^{\prime\prime}_{j})+\int_{\Omega_{2}}u_{j}(X)\
d(R_{-j},\tilde{Q}^{\prime\prime}_{j}).$

By construction, $Q_{j}^{\prime\prime}(X)=0$ for all $X\subseteq X^{+}$, which
means that $\int_{\Omega_{1}}u_{j}(X)\
d(R_{-j},\tilde{Q}^{\prime\prime}_{j})=0$. Additionally, if we define
$\Omega_{3}:=X^{-}\times A_{-i}$, we have that

$\int_{\Omega_{2}}u_{j}(X)\
d(R_{-j},\tilde{Q}^{\prime\prime}_{j})=\int_{\Omega_{2}}u_{j}(X)\
dR+\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}\int_{\Omega_{3}}u_{j}(X)\
d(R_{-j},Q_{j}).$

Note that $u_{j}(R)=\int_{\Omega_{2}}u_{j}(X)\ dR+\int_{\Omega_{1}}u_{j}(X)\
dR$, which implies that

$u_{j}(R_{-j},\tilde{Q}^{\prime\prime}_{j})-u_{j}(R)=\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}\int_{\Omega_{3}}u_{j}(X)\
d(R_{-j},Q_{j})-\int_{\Omega_{1}}u_{j}(X)\ dR.$

If $M_{\max}$ is the supremum of $u_{j}$ and $M_{\min}$ is its infimum, we can
bound $u_{j}(R_{-j},\tilde{Q}^{\prime\prime}_{j})-u_{j}(R)$ by

$u_{j}(R_{-j},\tilde{Q}^{\prime\prime}_{j})-u_{j}(R)\leq\frac{\tilde{Q}^{\prime}_{j}(X^{+})}{Q_{j}(X^{-})}M_{\max}\cdot(R_{-j},Q_{j})(\Omega_{3})-M_{\min}\cdot
R(\Omega_{1}).$

Note, however, that $(R_{-j},Q_{j})(\Omega_{3})=Q_{j}(X^{-})$ and
$R(\Omega_{1})=\tilde{Q}^{\prime}_{j}(X^{+})$. Therefore,

$u_{j}(R_{-j},\tilde{Q}^{\prime\prime}_{j})-u_{j}(R)\leq
Q^{\prime}_{j}(X^{+})(M_{\max}-M_{\min}),$

as desired.

Second equation:
$\ell_{j}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})-\ell_{j}(Q_{-S},Q^{\prime}_{S})>Q^{\prime}_{j}(X^{+})\cdot
M$.

The second equation follows from the observation we made in the proof of
Proposition 6: if $(j,X)$ is a maximal bet on $j$, then $Q_{j}(X\setminus
X^{+})=Q_{j}^{\prime}(X\setminus X^{+})=0$. Since
$\tilde{Q}^{\prime\prime}_{j}(X^{+})=0$, it follows that
$\ell_{j}(Q_{-S},Q^{\prime}_{S\setminus\\{j\\}},Q^{\prime\prime}_{j})=0$.
Thus, it remains to show that
$\ell_{j}(Q_{-S},Q^{\prime}_{S})<-Q^{\prime}_{j}(X^{+})\cdot M$. This follows
from the same observation since then
$\ell_{j}(Q_{-S},Q^{\prime}_{S})=\mathbb{E}[\mbox{\\# of other players betting
on j}]\cdot Q^{\prime}_{j}(X^{+})\cdot(-M-1)$. Since we assumed that at least
one other player bets on $j$ in expectation, it follows that
$\ell_{j}(Q_{-S},Q^{\prime}_{S})<-Q^{\prime}_{j}(X^{+})\cdot M$. ∎

##  8 Conclusion and Open Problems

This paper shows that if a mechanism designer has the power to add new actions
to a normal-form or Bayesian game, it can shield a given Nash equilibrium from
collusion and from equilibrium selection issues. More precisely, given a
normal-form (resp., Bayesian) game $\Gamma$ and a Nash equilibrium
$\vec{\sigma}$ of $\Gamma$, we showed that exists an extension
$\Gamma^{\vec{\sigma}}$ of $\Gamma$ such that (a) $\vec{\sigma}$ is a semi-
strong Nash equilibrium of $\Gamma$ and (b) $\vec{\sigma}$ Pareto-dominates
(resp., quasi Pareto-dominates) all other equilibria of
$\Gamma^{\vec{\sigma}}$. This result opens the door for three important
follow-up problems.

  * •

Can we also get Pareto-dominance for arbitrary Bayesian games? We proved that
the construction of $\Gamma^{\vec{\sigma}}$ given in Section 5.3 satisfies
that $\vec{\sigma}$ quasi Pareto-dominates all other Nash equilibria of
$\Gamma^{\vec{\sigma}}$. We conjecture that, in fact, $\vec{\sigma}$ also
Pareto-dominates all other Nash equilibria in this construction.

  * •

Minimizing promises. As discussed in earlier sections, we can view the newly
added actions in $\Gamma^{\vec{\sigma}}$ as _promises_ made by the mechanism
designer to the players. In practice, if players are rational and have full
information, these newly actions should never be played since every Nash
equilibrium that includes them is Pareto-dominated (or quasi Pareto-dominated)
by $\vec{\sigma}$. Thus, in theory, the mechanism designer can simply bluff
about the existence of these new actions (e.g., by promising to play certain
amount to a given player). Nevertheless, it is still an open question to see
exactly how much utility must the mechanism designer promise in order to
construct a game $\Gamma^{\vec{\sigma}}$ that satisfies the properties of
Theorem 1 and 2.

  * •

Minimum size of $\Gamma^{\vec{\sigma}}$. Theorems 1 and 2 give upper bounds on
the minimum number of actions that must be added in order to construct
$\Gamma^{\vec{\sigma}}$. It is still an open problem to verify if there exists
a smaller construction.

## References

  * [1] Ittai Abraham, Lorenzo Alvisi, and Joseph Y Halpern.  Distributed computing meets game theory: combining insights from two fields.  Acm Sigact News, 42(2):69–76, 2011.
  * [2] Ittai Abraham, Danny Dolev, Ivan Geffner, and Joseph Y Halpern.  Implementing mediators with asynchronous cheap talk.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 501–510, 2019.
  * [3] Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y Halpern.  Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation.  In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 53–62, 2006.
  * [4] Ittai Abraham, Danny Dolev, and Joseph Y Halpern.  Lower bounds on implementing robust and resilient mediators.  In Theory of Cryptography: Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008. Proceedings 5, pages 302–319. Springer, 2008.
  * [5] Amitanand S Aiyer, Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth.  Bar fault tolerance for cooperative services.  In Proceedings of the twentieth ACM symposium on Operating systems principles, pages 45–58, 2005.
  * [6] Robert J Aumann.  Acceptable points in general cooperative n-person games.  Contributions to the Theory of Games, 4:287–324, 1959.
  * [7] Robert J Aumann.  Subjectivity and correlation in randomized strategies.  Journal of mathematical Economics, 1(1):67–96, 1974.
  * [8] M. Ben-Or, S. Goldwasser, and A. Wigderson.  Completeness theorems for non-cryptographic fault-tolerant distributed computation.  In Proceedings of the 20th ACM Symposium on Theory of Computing, pages 1–10, 1988.
  * [9] Michael Ben-Or.  Another advantage of free choice (extended abstract) completely asynchronous agreement protocols.  In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 27–30, 1983.
  * [10] Michael Ben-Or, Ran Canetti, and Oded Goldreich.  Asynchronous secure computation.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 52–61, 1993.
  * [11] B Douglas Bernheim, Bezalel Peleg, and Michael D Whinston.  Coalition-proof nash equilibria i. concepts.  Journal of economic theory, 42(1):1–12, 1987.
  * [12] Gabriel Bracha.  An asynchronous [(n-1)/3]-resilient consensus protocol.  In Proceedings of the third annual ACM symposium on Principles of distributed computing, pages 154–162, 1984.
  * [13] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  Journal of the ACM (JACM), 32(4):824–840, 1985.
  * [14] Francoise Forges.  An approach to communication equilibria.  Econometrica: Journal of the Econometric Society, pages 1375–1385, 1986.
  * [15] Ivan Geffner and Joseph Y Halpern.  Security in asynchronous interactive systems.  In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 123–140. Springer, 2021.
  * [16] Ivan Geffner and Joseph Y Halpern.  Communication games, sequential equilibrium, and mediators.  arXiv preprint, arXiv:2309.14618, 2023.
  * [17] Ivan Geffner and Joseph Y Halpern.  Lower bounds on implementing mediators in asynchronous systems with rational and malicious agents.  Journal of the ACM, 70(2):1–21, 2023.
  * [18] Dov Monderer and Moshe Tennenholtz.  k-implementation.  In Proceedings of the 4th ACM conference on Electronic Commerce, pages 19–28, 2003.
  * [19] Dov Monderer and Moshe Tennenholtz.  Strong mediated equilibrium.  Artificial Intelligence, 173(1):180–195, 2009.
  * [20] Caspar Oesterheld, Johannes Treutlein, Roger Grosse, Vincent Conitzer, and Jakob Foerster.  Similarity-based cooperation.  arXiv preprint, arXiv:2211.14468, 2022.
  * [21] Michal Penn, Maria Polukarov, and Moshe Tennenholtz.  Congestion games with failures.  In Proceedings of the 6th ACM Conference on Electronic Commerce, pages 259–268, 2005.
  * [22] Michael O Rabin.  Randomized byzantine generals.  In 24th annual symposium on foundations of computer science (sfcs 1983), pages 403–409. IEEE, 1983.
  * [23] Alejandro Ranchal-Pedrosa and Vincent Gramoli.  Rational agreement in the presence of crash faults.  In 2021 IEEE International Conference on Blockchain, pages 470–475. IEEE, 2021.
  * [24] Moshe Tennenholtz.  Program equilibrium.  Games and Economic Behavior, 49(2):363–373, 2004.
  * [25] Xavier Vilaça, Joao Leitao, Miguel Correia, and Luís Rodrigues.  N-party bar transfer.  In Proceedings of the 2011 Conference on Principles of Distributed Systems, pages 392–408. Springer, 2011.