# Pure Bayesian Nash Equilibrium for Bayesian Games with Multidimensional
Vector Types and Linear Payoffs

Sébastien Huot
Department of Computing
Imperial College London
London, United Kingdom
<EMAIL_ADDRESS>
& Abbas Edalat
Department of Computing
Imperial College London
London, United Kingdom
<EMAIL_ADDRESS>

###### Abstract

We study $n$-agent Bayesian Games with $m$-dimensional vector types and linear
payoffs, also called Linear Multidimensional Bayesian Games [17]. This class
of games is equivalent with $n$-agent, $m$-game Uniform Multigames introduced
in [6]. We distinguish between games that have a discrete type space and those
with a continuous type space. More specifically, we are interested in the
existence of pure Bayesian Nash Equilibrium for such games and efficient
algorithms to find them. For continuous priors we suggest a methodology to
perform Nash Equilibrium search in simple cases. For discrete priors we
present algorithms that can handle two actions and two players games
efficiently. We introduce the core concept of threshold strategy and, under
some mild conditions, we show that these games have at least one pure Bayesian
Nash Equilibrium. We illustrate our results with several examples like Double
Game Prisoner Dilemna (DGPD), Chicken Game and Sustainable Adoption Decision
Problem (SADP).

_Keywords_ Multigame $\cdot$ Bayesian $\cdot$ Linear payoff $\cdot$
Multidimensional $\cdot$ Pure Bayesian Nash Equilibrium

Experimental results are accessible at this repository.

##  1 Introduction

Game theory provides an abstract framework to model a broad range of decision-
making scenarios in real-life situations. From social cooperation [18] to
biological evolution [10] and economics [26] we can find models of games that
can help to predict, or at least explain, the decision-makers’ behaviour. Game
theory is a bag of analytical tools designed to help us understand the
phenomena that we observe when decision-makers interact[21]. A game is
designed to model any situation involving decision-makers (players, agents)
that are rational and reason strategically. An agent is rational when it has a
well-defined objective, is able to say which situation it prefers and attempts
to maximize its payoff. Strategic reasoning is to use our knowledge in the
best possible way to anticipate the other agents’ action and take it into
account in the decision process. The knowledge of an agent is the information
that it has before making its decision. An information only known by one
player is said to be private knowledge. When it is shared among a group of
players, we say that this is common knowledge.

More formally, we assume agents are indexed by a set $I$. We denote the set of
actions of agents by $A$, the set of outcomes by $O$ and consider an outcome
function $f:A\rightarrow O$ giving the outcome of each action. The preferences
of any agent are specified by the maximization of a utility (or payoff)
function $u:O\rightarrow\mathds{R}$. The simplest form of game is the
Strategic Game given in Definition 1. An action profile $a=(a_{i})_{i\in I}$
is an outcome of the game. We use the index $-i$ to designate all players
except $i$ and write $a=(a_{i},a_{-i})$ for $a\in A$.

######  Definition 1.

A Strategic Game $G=\left<I,(A_{i})_{i\in I},(u_{i})_{i\in I}\right>$ is made
of:

  1. 1.

A finite set $I=\\{1,2,3,...,n\\}$ of $n$ agents.

  2. 2.

For each agent $i\in I$ a nonempty set $A_{i}$ of possible actions. If $A_{i}$
is finite for all agents, then we say that the game is finite.

  3. 3.

A set $A=\prod_{i\in I}A_{i}$ of possible outcomes.

  4. 4.

A set of utility functions $u_{i}:A\rightarrow\mathds{R}$ specifying the
preferences of agent $i$.

A Nash Equilibrium (NE) captures a steady state [21] of a game in which all
agents have no incentive to deviate from their action unilaterally (Definition
2).

######  Definition 2.

A Nash Equilibrium of the strategic game $G=\left<I,(A_{i})_{i\in
I},(u_{i})_{i\in I}\right>$ is an action profile $a^{*}\in A$ such that:

$\forall i\in I\quad\forall a_{i}\in A_{i}\quad
u_{i}(a_{i}^{*},a_{-i}^{*})\geq u_{i}(a_{i},a_{-i}^{*})$

For a set $X$, let $\mathcal{P}(X)$ denote its set of subsets.

######  Definition 3.

Given an agent $i$ and the action $a_{-i}\in A_{-i}$ , the best-response
function $B_{i}:A_{-i}\rightarrow\mathcal{P}(A_{i})$ is such that:

$B_{i}(a_{-i})=\\{a_{i}\in A_{i}\mid u_{i}(a_{i},a_{-i})\geq
u_{i}(a_{i}^{\prime},a_{-i})\quad\forall a_{i}^{\prime}\in A_{i}\\}$

This implies that, $a^{*}$ is a Nash Equilibrium if and only if $a^{*}\in
B(a^{*}):=\left(B_{i}(a_{-i})\right)_{i\in I}$.

The Prisoner Dilemma (PD) [9] is a widely used toy example that models a
simple situation of self-interest driven decision and illustrates the case
where the Nash Equilibrium is not efficient in the sense of Pareto [21].
Extended to more than two agents, it’s often associated with the tragedy of
the commons [2]. It is a situation in which individuals, who have open access
to a shared resource act independently according to their own self-interest
and, contrary to the common good of all users, cause depletion of the resource
through their uncoordinated action [11].

However, this behaviour may not be very common in real life as stated by
Poundstone using the example of newspaper boxes in New Zealand [23]. Indeed,
the PD can even fail to model real life examples.

Consider for example the TV show Friend or Foe? aired between 2002 and 2005 in
the US. Two players who previously failed to answer some questions have to
play The Trust Box: if they both choose Friend, they share a specified amount
of money. If they both choose Foe, the money is lost. And if one plays Friend
while the other plays Foe, the player choosing Foe wins all the money.
Although (Friend, Friend) is not a NE, data collected from this kind of game
showed that in such situation, cooperation is surprisingly high [16].
Experience suggests that when a significant amount of money is at stake
players tend to cooperate. Indeed, humans are not only driven by material
considerations but also moral and sociocultural matters.

###  1.1 Bayesian games

Concrete situations usually involve uncertainty at multiple levels so
Strategic Games with perfect information (such as the Prisonner Dilemna or
Hawk-Dove [30]) may not be sufficient to describe the game. Usually we denote
this unknown information by state of nature and model it with a state space
$\Omega$ [21]. Suppose each agent has some private information (or private
knowledge): this information, called the type $\theta_{i}$ of agent $i$, is
unknown to the other agents, who can only have a (subjective) probability
distribution over such possible types for an agent. So we assume that they
have in mind a type space $\Theta$ and a probability measure over $\Theta$,
and, following von Neumann and Morgenstern’s theory [31], they play $a^{*}$
that maximizes the expected value of $u(f(a^{*},\theta))$ subject to
$\theta\in\Theta$.

A game $G$ is Bayesian [12, 13, 14] when there is uncertainty for the agents
(as in Definition 4). In this situation, an agent can no longer anticipate
with certainty the output of the game because some information about the game
is unknown. Variance of the outcome is generally associated to risk or how
much we could diverge from what we expect. A human player who wants to
maximize his/her payoff without taking too much risk could be modeled by
optimizing a combination of the expected value and the associated variance as
seen in portfolio management models [19].

Bayesian Games also introduce the concept of strategy which varies over the
type of an agent. Indeed, the action of an agent depends on all the
information it has (its own type) at the moment of the decision. We
distinguish pure strategies $s_{i}:\Theta_{i}\rightarrow A_{i}$ from mixed
strategies $\sigma_{i}:\Theta_{i}\rightarrow\Delta A_{i}$, where $\Delta X$
denotes the set of all probability distributions on a set $X$. In the latter
case, the action played is not deterministic anymore but chosen randomly
according to a probability distribution.

######  Definition 4.

A Bayesian Game G is a game in strategic form with incomplete information
which we denote by $G=\left<I,(A_{i},\Theta_{i},u_{i},p_{i}(\cdot))_{i\in
I}\right>$ where:

  1. 1.

$I=\\{1,...,n\\}$ is the set of agents.

  2. 2.

$A_{i}$ is agent $i$’s action set and $A=\prod_{i\in I}A_{i}$ is the set of
action outcomes or action profiles.

  3. 3.

$\Theta_{i}$ is agent $i$’s type space and $\Theta=\prod_{i\in I}\Theta_{i}$
is the set of type profiles.

  4. 4.

$u_{i}:A\times\Theta\rightarrow\mathds{R}$ is agent $i$’s utility for each
$i\in I$.

  5. 5.

$p_{i}:\Theta\rightarrow\mathds{R}$ is a (subjective) joint probability on
$\Theta$ for each $i\in I$.

For such games we can derive the notion of Bayesian Nash Equilibrium from the
NE of strategic games where we maximize an expected utility $\overline{u_{i}}$
subject to agents’ types. We also distinguish pure and mixed Nash Equilibria.
Thanks to the Nash Theorem (Theorem 1), we know that there always exists a
mixed strategy Nash Equilibrium (denoted by mixed NE). However, this theorem
doesn’t give a practical method to find this Nash Equilibrium. In fact,
finding a Nash Equilibrium is often very complex and cannot be computed in a
reasonable time. In 1994, Christos H. Papadimitriou introduced the complexity
class PPAD (Polynomial Parity Arguments on Directed graphs) [22] in order to
classify the problem of finding a Nash Equilibrium. Later, he also showed that
the problem of finding a Nash Equilibrium for a finite game is PPAD-complete
[3].

######  Theorem 1 (Nash Theorem [21]).

Every finite strategic game has a mixed strategy Nash equilibrium.

Although finding a Nash Equilibrium is very hard in general, we can find some
classes of games that have nice properties and an efficiently computable Nash
Equilibrium [24].

###  1.2 Linear multidimensional Bayesian games

For our study, we consider Linear Multidimensional Bayesian Games (Definition
5). They were initially introduced by Krishna and Perry to model multiple
object auctions [17]. This class of games was shown [6] to be equivalent to
another class of games called Uniform Multigames (Theorem 2). A multigame
(Definition 6) is a game that is made of several local games that are played
simultaneously by all agents. Each local game has its own payoff matrix and
possible actions. For example an agent playing Head or Tail with one person
and Rock, Paper, Scissors with another person simultaneously can be modeled by
a multigame. Even if both local games are solved simultaneously, the agent is
just playing on two separate games and tries to maximize a global utility
which is a linear combination of local utilities. More specifically, for
multigames in which every agent has the same set of actions in all local
games, we can consider uniform games: agents can only take the same action in
all local games. When a multigame is uniform, an agent chooses only one
strategy that is played identically in all local games. Said differently, one
decision has multiple consequences and each agent wants to optimize their
overall utility. We say that an agent chooses a global strategy that is
applied on all the local games. Let $\mathds{R}_{+}$ denote the set of non-
negative real numbers.

######  Definition 5 (Linear Multidimensional Bayesian Games).

A Bayesian game $G$ is $m$-dimensional if the type space of each agent is a
bounded subset of $\mathds{R}^{m}_{+}$. When the positive integer $m>1$ is
implicitly given, we say $G$ is multidimensional. A multidimensional Bayesian
game is linear if the utility of each agent only depends linearly on its own
type components, i.e., there exists $L_{i}(s_{i},s_{-i})\in\mathds{R}^{m}$
such that $u_{i}(s_{i},s_{-i},\theta_{i},\theta_{-i})=\sum_{j\in
J}\left(L_{i}(s_{i},s_{-i})\right)_{j}\theta_{ij}$.

######  Definition 6.

A multigame

$G=\langle I,J,(w_{i})_{i\in I},(G_{j})_{j\in J},(\Theta_{i})_{i\in
I},(A_{ij},u_{ij})_{i\in I,j\in J},p(\cdot))\rangle$

is a game in strategic form with incomplete information with the following
structure:

  1. 1.

The set of agents $I=\\{1,...,n\\}$.

  2. 2.

The set of $n$-agent basic games is given by $G_{j}$, where $j\in
J=\\{1,...,m\\}$ with action space $A_{ij}$ and utility function $u_{ij}$ for
each agent $i\in I$ in the game $G_{j}$.

  3. 3.

Agent’s $i$’s strategy is $s_{i}=(s_{ij})_{j\in J}\in S_{i}=\prod_{j\in
J}A_{ij}$ where $s_{ij}$ is agent $i$’s action in $G_{j}$.

  4. 4.

Agent $i$’s type is $\theta_{i}=(\theta_{ij})_{j\in J}\in\Theta_{i}$ with
$\theta_{ij}\geq 0$, $w_{i}>0$ and $\sum_{j\in J}{\theta_{ij}}\leq w_{i}$

  5. 5.

Agent $i$’s utility for the strategy profile $(s_{i},s_{-i})$ and type profile
$(\theta_{i},\theta_{-i})$ depends linearly on its types:

$u_{i}(s_{i},s_{-i},\theta_{i},\theta_{-i})=\sum_{j\in
J}{\theta_{ij}u_{ij}(s_{1j},...,s_{nj})}$

  6. 6.

The agents’ type profile $\theta=(\theta_{1},...,\theta_{n})\in\prod_{i\in
I}\Theta_{i}$ is drawn from a given joint probability distribution
$p(\theta)$. For any $\theta_{i}\in\Theta_{i}$, the function
$p(\cdot\mid\theta_{i})$ specifies a conditional probability distribution
$\Theta_{-i}$ representing what agent $i$ believes about the types of the
other agents if its own type where $\theta_{i}$.

######  Theorem 2.

[6] Suppose $G$ is a linear $m$-dimensional Bayesian game with a bounded type
space $\Theta_{i}\subset\mathds{R}^{m}_{+}$ for each $i\in I$, then $G$ is
equivalent with a uniform multigame with $m$ basic games.

Note that according to Definition 6, the type can be any $m$-dimensional
vector with positive coefficients. We say that a multigame is normalized when
$\forall i\in I,w_{i}=1$. Any multigame can be converted into a normalized
multigame by adding a well-chosen local game [6]. Thus we can assume without
loss of generality that multigames are normalized and such that for all agents
their type’s coefficients add up to 1. As mentionned previously, this paper
focuses on uniform multigames that have the following two basic features: (1)
action sets are identical in all local games for every agent $i\in I$, i.e.,
$\forall j\in J,A_{ij}=A_{i}$ and (2) each agent plays the same action in all
basic games $G_{j}$, i.e. $S_{i}=\\{(s,s,...,s)\mid s\in A_{i}\\}$.
Additionally, we make the assumption that the agents’ types are independent

$\forall i\in I,\quad p_{i}(\theta_{-i}\mid\theta_{i})=p_{i}(\theta_{-i})$

We aim to show, beyond what is provided in [6], that the multigame framework
can model a wide range of complex situations that are worth exploring such as
coordinated international environmental and social actions. First, take the
situation in which two countries could either keep their traditional
unsustainable production system or shift to a more responsible production. The
shift is only beneficial if both countries do it. But each country can be
tempted to keep the old traditional production system that doesn’t incur an
additional cost and is more efficient and profitable (at least this is what
agents trust). This situation falls into the original Prisoner Dilemma
framework and we end up with both countries keeping their traditional
production (assuming that they act rationally).

Now, we extend this situation to $N$ companies in the same geographical area.
We assume that each company that continues to keep an unsustainable production
unit causes a pollution cost of $1$ unit. Thus the (shared) pollution cost $k$
is the number of companies that don’t shift their production unit, $0\leq
k\leq N$. On the other hand, a company that shifts its production unit for a
more sustainable one has to pay an additional (fixed) cost $c\ll N$. Thus
$c_{i}=k+c$ for a company $i$ that shifts its production and $c_{i}=k$ for a
company that keeps it. If all $N$ agents shift, they all end up with a (small)
cost $c$ and if no agent does so, they all end up with a (high) cost of $N$.
Therefore, it is in the common interest that everyone shifts their production
unit. But as each individual company has no incentive to deviate from not
shifting, the only Nash Equilibrium of this game is that they all avoid the
shift. The latter example can handle any number of companies but remains very
limited as we cannot include the particularities of the agents (types) and the
uncertainty about what other companies value the most (i.e., the Bayesian
aspect).

Later on, we study a more powerful approach through the multigames framework.
We call it the Sustainable Adoption Decision Problem (SADP): $n$ independent
countries share $m$ possible concerns like population well-being, air
pollution, economic stability, education or preserving biodiversity. Each
country has its own (subjective) priorities characterized by an
$m$-dimensional vector and has to choose between keeping their current
lifestyle or radically shifting to a more sustainable one.

We denote by $G_{m,n,a}$ a uniform multigame with $n$ agents, $m$ local games
and $a$ number of possible actions assuming that all agents have the same
number of possible actions. When we have games with 2 actions ($a=2$), we call
these two actions C (cooperation) and D (defection). In this paper, we study
$G_{m,n,2}$ multigames with continuous type space and show that with a simple
condition on local games, the existence of a pure Bayesian Nash Equilibrium is
guaranteed. At the same time, we define the notion of threshold strategy and
discuss the possibility to extend it to any number of actions. Then, we
operate the same kind of analysis for discrete games. For both continuous and
discrete type spaces we define a particular kind of multigame $G_{2,2,2}$ that
is called Double Game Prisoner Dilemma (DGPD). In the last part, we propose
algorithms that can efficiently find NE in particular situations and formulate
postulates by exploring some properties of multigames.

###  1.3 Related work

Thanks to Nash Theorem, we know that any (finite) game has (at least) one Nash
Equilibrium. But the number of equilibrium(s) and their nature is not
described in general. There have been many researches to identify particular
examples or sets of games that showcase patterns in the number or nature of
their NE. For instance, [8] identifies that N-player Colonel Blotto games with
incomplete information have Bayes–Nash equilibrium in which the resource
allocation is strictly monotone. Probabilistic approaches [4, 25, 27, 28, 29]
have also been proposed, where the games are randomly generated under some
constraints. The condition of coarser inter-player information introduced by
[15] is shown to be necessary and sufficient to have pure Bayesian Nash
Equilibrium. In [7], the existence of pure-strategy equilibrium is proven for
potential Bayesian games [20] with absolutely continuous information and a
Bayesian potential that is upper semi-continuous in actions for any
realization of the players’ types. Similarly, we showcase a specific set of
games that have pure Bayesian Nash Equilibrium and identify examples that
illustrate our results.

##  2 Uniform multigames with continuous type space

###  2.1 General remarks

We use the standard Lebesgue measure on finite dimensional Euclidean spaces.
When the type space is continuous, there are 3 possibilities: the probability
distribution is either discrete, continuous or a mixture of both. If the
probability distribution is fully discrete, we fall into the discrete type
space case that we study later on. We choose to exclude the mixture case so
that the distribution over the type space has no atomic value.

We suppose that the probability distribution for the game is absolutely
continuous with respect to the Lebesgue measure: Denote the Lebesgue measure
on $\mathds{R}^{m}$ by $\lambda_{m}$; if $p$ is a probability distribution on
$\mathds{R}^{m}$, then the probability distribution $p$ is absolutely
continuous with respect to $\lambda_{m}$ if for any measurable set $E$, we
have: $\lambda_{m}(E)=0\implies p(E)=0$. Let $p_{i}$ be the probability
distribution for agent $i\in I$. We assume that we can use a probability
density function: recall that, for any measurable set $E$, the probability
density function $f_{i}$ satisfies:

$p_{i}(\theta_{-i}\in
E)=\int_{E}f_{i}({\boldsymbol{{\theta}}}_{-i})d{\boldsymbol{{\theta}}}_{-i}$

In our case, $p_{i}({\boldsymbol{{\theta}}}_{-i}\in E)$ is the probability,
according to agent $i$, that the other agents have a type in the set
$E\subset\Theta_{-i}$ and $f_{i}$ is the associated density function.

The type space $\Theta$ is assumed to be a compact subset of $\mathds{R}^{m}$
and, thanks to the fact that the multigame is normalized, we have
$dim(\Theta_{i})=m-1$.

A pure strategy for agent $i$ is denoted by $s_{i}$, a mixed strategy by
$\sigma_{i}$. We use $\sigma_{i}$ if we don’t know a priori the nature of the
strategy. We recall that for a pure strategy $s_{i}:\Theta_{i}\rightarrow
A_{i}$ the agent plays an action for a given type. For a mixed strategy
$\sigma_{i}:\Theta_{i}\rightarrow\Delta A_{i}$, the agent follows a
probability for a given type where
$\sigma_{i}({\boldsymbol{{\theta}}}_{i},a_{i})$ is the probability of agent
$i$ playing $a_{i}$ when their type is ${\boldsymbol{{\theta}}}_{i}$.

###  2.2 Threshold strategy

First, consider agent $i$’s expected utility
$\overline{U}_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$ given that
it plays action $a_{i}$, has type ${\boldsymbol{{\theta}}}_{i}$ and other
agents follow the strategy $\sigma_{-i}$:

$\displaystyle\overline{U}_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i})=\int_{{\boldsymbol{{\theta}}}_{-i}}f_{i}({\boldsymbol{{\theta}}}_{-i})U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i}({\boldsymbol{{\theta}}}_{-i}))\,d{\boldsymbol{{\theta}}}_{-i}$
(1)

$U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i}({\boldsymbol{{\theta}}}_{-i}))$
is agent $i$’s utility playing $a_{i}$ with type ${\boldsymbol{{\theta}}}_{i}$
given that the others follow $\sigma_{-i}({\boldsymbol{{\theta}}}_{-i})$. This
utility can be expressed in terms of
$U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},a_{-i})$ for $a_{-i}\in A_{-i}$:

$\displaystyle
U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i}({\boldsymbol{{\theta}}}_{-i}))=\sum_{a_{-i}\in
A_{-i}}U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},a_{-i})\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})$
(2)

As $G$ is a multigame, $U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},a_{-i})$ can
be expressed as follows:

$\displaystyle U_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},a_{-i})=\sum_{j\in
J}u_{ij}(a_{i},a_{-i})\theta_{ij}$ (3)

We define:

$\displaystyle\zeta_{i}^{a_{-i}}(\sigma_{-i})$
$\displaystyle:=\int_{{\boldsymbol{{\theta}}}_{-i}}f_{i}({\boldsymbol{{\theta}}}_{-i})\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})\,d{\boldsymbol{{\theta}}}_{-i}$
(4) $\displaystyle\overline{u}_{ij}(a_{i},\sigma_{-i})$
$\displaystyle:=\sum_{a_{-i}}u_{ij}(a_{i},a_{-i})\zeta_{i}^{a_{-i}}(\sigma_{-i})$
(5)

Here, $\zeta_{i}^{a_{-i}}(\sigma_{-i})$ is the probability that $a_{-i}$ is
played by others given that they follow strategy $\sigma_{-i}$. Thus
$\overline{u}_{ij}(a_{i},\sigma_{-i})$ is the expected utility for agent $i$
in the local game $j$ if it plays action $a_{i}$ and others follow the
strategy $\sigma_{-i}$. Using these, we can write:

$\displaystyle\overline{U_{i}}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$
$\displaystyle=$
$\displaystyle\int_{{\boldsymbol{{\theta}}}_{-i}}f_{i}({\boldsymbol{{\theta}}}_{-i})\sum_{a_{-i}}\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})\sum_{j\in
J}u_{ij}(a_{i},a_{-i})\theta_{ij}\,d{\boldsymbol{{\theta}}}_{-i}$ (6)
$\displaystyle=$ $\displaystyle\sum_{j\in
J}\theta_{ij}\sum_{a_{-i}}u_{ij}(a_{i},a_{-i})\int_{{\boldsymbol{{\theta}}}_{-i}}f_{i}({\boldsymbol{{\theta}}}_{-i})\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})\,d{\boldsymbol{{\theta}}}_{-i}$
(7) $\displaystyle=$ $\displaystyle\sum_{j\in
J}\theta_{ij}\sum_{a_{-i}}u_{ij}(a_{i},a_{-i})\zeta_{i}^{a_{-i}}(\sigma_{-i})$
(8) $\displaystyle=$ $\displaystyle\sum_{j\in
J}\theta_{ij}\overline{u}_{ij}(a_{i},\sigma_{-i})$ (9) $\displaystyle=$
$\displaystyle{\boldsymbol{{\theta}}}_{i}\cdot(\overline{u}_{ij}(a_{i},\sigma_{-i}))_{j\in
J}$ (10)

We thus have a more compact and explicit expression of the expected utility
$\overline{U_{i}}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$. Indeed, it
can be computed as the scalar product of the vector type of agent $i$ and the
vector of the expected utilities for local games.

So far, we have kept game parameters $m,n$ and $a$ as general as possible, the
previous expression holds for any choice of those parameters. To go further on
with the analysis, we consider that $a=2$. We will discuss in the conclusion
section the extension to any number of actions.

We aim to evaluate whether agent $i$ with type ${\boldsymbol{{\theta}}}_{i}$
and opponents’ strategy $\sigma_{-i}$ prefers to play $C$ or $D$. We compare
$\overline{U_{i}}(C,{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$ and
$\overline{U_{i}}(D,{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$:

$\displaystyle\overline{U_{i}}(C,{\boldsymbol{{\theta}}}_{i},\sigma_{-i})-\overline{U_{i}}(D,{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$
$\displaystyle=$ $\displaystyle\sum_{j\in
J}\theta_{ij}(\overline{u}_{ij}(C,\sigma_{-i})-\overline{u}_{ij}(D,\sigma_{-i}))$
(11) $\displaystyle=$ $\displaystyle\sum_{j\in
J}\theta_{ij}\delta_{ij}(\sigma_{-i})$ (12) $\displaystyle=$
$\displaystyle{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}(\sigma_{-i})$
(13)

where
$\delta_{ij}(\sigma_{-i})=\overline{u}_{ij}(C,\sigma_{-i})-\overline{u}_{ij}(D,\sigma_{-i})$
and ${\boldsymbol{{\delta}}}_{i}(\sigma_{-i})=(\delta_{ij}(\sigma_{-i}))_{j\in
J}$. This difference expressed as a scalar product indicates the best action
for agent $i$: if it is strictly positive then the best action is $C$, if it
is strictly negative then the best action is $D$ and if it is equal to zero
then any mixed combination of $C$ and $D$ is a best response.

######  Definition 7 (Threshold strategy).

The vector ${\boldsymbol{{\delta}}}_{i}$ is called agent $i$’s threshold. A
threshold strategy $\sigma_{i}$ with threshold ${\boldsymbol{{\delta}}}_{i}$
for agent $i$ is a strategy such that:

$\displaystyle\sigma_{i}({\boldsymbol{{\theta}}}_{i})=\begin{cases}C&\text{${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}>0$}\\\
D&\text{${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}<0$}\\\
\alpha_{i}({\boldsymbol{{\theta}}}_{i})C+(1-\alpha_{i}({\boldsymbol{{\theta}}}_{i}))D&\text{${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}=0$},\end{cases}$
(14)

where $\alpha_{i}({\boldsymbol{{\theta}}}_{i})\in[0,1]$. Such a strategy is
also denoted by $(\sigma_{i},{\boldsymbol{{\delta}}}_{i},\alpha_{i})$.

The first and second cases
(${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}\neq 0$) are
called pure components of the strategy and the last case
(${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}=0$) is called
the mixed component. Notice that, as a direct consequence of what we
previously said, a best response is always a threshold strategy and thus any
Bayesian Nash Equilibrium $\sigma=(\sigma_{1},\sigma_{2},...,\sigma_{n})$ is
exclusively made of threshold strategies. Also, a threshold strategy is said
to be pure when $\forall{\boldsymbol{{\theta}}}_{i}$,
$\alpha_{i}({\boldsymbol{{\theta}}}_{i})\in\\{0,1\\}$.

###  2.3 Existence of pure Bayesian Nash Equilibrium

######  Theorem 3.

If a (normalized) uniform multigame $G_{m,n,2}$ with continuous type space and
continuous prior has a mixed strategy Nash Equilibrium
$(\sigma_{1},\sigma_{2},...,\sigma_{n})$ with non-zero threshold vectors for
all agents then it has a pure Bayesian Nash Equilibrium.

###### Proof.

Consider a mixed Nash Equilibrium
$\sigma=(\sigma_{1},\sigma_{2},...,\sigma_{n})$ that satisfies the condition
given in the theorem. We show that starting from the mixed strategy $\sigma$
we can derive $s=(s_{1},s_{2},...,s_{n})$ a pure strategy Nash Equilibrium.

First, we notice that $\sigma_{i}$’s are threshold strategies
$(\sigma_{i},{\boldsymbol{{\delta}}}_{i}^{*},\alpha_{i})$ with threshold
${\boldsymbol{{\delta}}}_{i}^{*}={\boldsymbol{{\delta}}}_{i}(\sigma_{-i})$ as
they are best responses for each agent given the opponents’ strategies. We
suppose that there is at least one agent $i$ such that $\sigma_{i}$ is a mixed
strategy ($\alpha_{i}\neq 0,1$) because otherwise $\sigma$ is already a pure
strategy Nash Equilibrium and the proof is over. For each $i\in I$, derive the
pure strategy $s_{i}$ from $\sigma_{i}$ by replacing the mixed component with
a pure action, i.e., by setting $\alpha_{i}\in\\{0,1\\}$. We now demonstrate
that $s=(s_{1},s_{2},...,s_{n})$ is a Bayesian Nash Equilibrium for $G$.

By construction, $s_{i}$’s are threshold strategies with the same threshold as
$\sigma_{i}$’s. So if we can show that
${\boldsymbol{{\delta}}}_{i}(\sigma_{-i})={\boldsymbol{{\delta}}}_{i}(s_{-i})$
for all agents $i$ then $s$ is a Bayesian Nash Equilibrium. For this purpose,
we prove that:

$\forall i\in I,\forall a_{-i}\in
A_{-i}.\quad\zeta^{a_{-i}}_{i}(\sigma_{-i})=\zeta^{a_{-i}}_{i}(s_{-i})$

by computing the difference:

$\displaystyle\zeta^{a_{-i}}_{i}(\sigma_{-i})-\zeta^{a_{-i}}_{i}(s_{-i})=\int_{{\boldsymbol{{\theta}}}_{-i}}f_{-i}({\boldsymbol{{\theta}}}_{-i})[\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})-s_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})]\,d{\boldsymbol{{\theta}}}_{-i}.$
(15)

Since ${\boldsymbol{{\delta}}}_{i}(\sigma_{-i})$ is a non zero vector, the set
$E_{i}=\\{{\boldsymbol{{\theta}}}_{i}\mid{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}(\sigma_{-i})=0\\}$
is contained in a hyperplane of $\mathds{R}^{m-1}$. Thus, for any agent $i$,
the set $\Theta_{1}\times...\times E_{i}\times...\times\Theta_{n}$ has zero
measure. Also, note that $\sigma_{-i}(a_{-i},{\boldsymbol{{\theta}}}_{-i})\neq
s_{-i}(a_{-i},{\boldsymbol{{\theta}}}_{-i})$ only when
${\boldsymbol{{\theta}}}_{-i}\in\bigcup_{k\neq i}\Theta_{-\\{i,k\\}}\times
E_{k}$ where the latter set is the finite union of nullsets. In other words,
$\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})$ and
$s_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})$ are equal almost everywhere. So
the difference expressed by the integral is zero. This shows that the
constructed pure strategy $s$ is a Nash Equilibrium solution.
∎

Theorem 3 provides a pure Bayesian Nash Equilibrium for uniform multigames
with 2 actions but it relies on a specific condition on mixed strategy
solutions. In practice, we do not seek to enumerate all possible mixed
solutions just to check whether any one of them has non-zero threshold vectors
for all agents. Fortunately, we can find conditions that don’t rely on the
mixed solutions but can help us to determine whether there exists pure
solutions.

######  Definition 8 (Purely cooperative/competitive local game).

A local game $j\in J$ is said to be purely cooperative for agent $i\in I$ if

$\forall a_{-i}\in A_{-i}.\quad u_{ij}(C,a_{-i})>u_{ij}(D,a_{-i})$

and to be purely competitive if

$\forall a_{-i}\in A_{-i}.\quad u_{ij}(C,a_{-i})<u_{ij}(D,a_{-i})$

This notion is equivalent to the condition that C (or D) is a strictly
dominant strategy for agent $i$ in game $j$.

######  Proposition 1.

An agent having at least one purely competitive (or cooperative) local game
will always play a threshold strategy with a non-zero threshold, whatever the
opponents’ strategy $\sigma_{-i}$.

###### Proof.

Assume that game $k$ is purely cooperative for agent $i$ (the same reasoning
applies to a purely competitive game). Let’s compute
$\delta_{ik}(\sigma_{-i})$:

$\displaystyle\delta_{ik}(\sigma_{-i})=\sum_{a_{-i}}(u_{ik}(C,a_{-i})-u_{ik}(D,a_{-i}))\zeta_{i}^{a_{-i}}(\sigma_{-i}).$
(16)

Since the terms $\zeta_{i}^{a_{-i}}(\sigma_{-i})$ express probabilities, they
are non-negative with $\sum_{a_{-i}}\zeta_{i}^{a_{-i}}(\sigma_{-i})=1$.
Because the local game $k$ is purely cooperative for agent $i$, we have
$u_{ik}(C,a_{-i})-u_{ik}(D,a_{-i})>0$ for all $k\in J$. Thus the sum is
strictly positive and $\delta_{ik}(\sigma_{-i})>0$ which implies
${\boldsymbol{{\delta}}}_{i}(\sigma_{-i})\neq 0$.

∎

In the light of Proposition 1 we easily deduce the following:

######  Theorem 4.

Any normalized uniform multigame $G_{m,n,2}$ with continuous type space and
continuous prior, with at least one purely competitive/cooperative local game
for each agent, has a pure Bayesian Nash Equilibrium.

###### Proof.

We note that, by Proposition 1, all agents must play a threshold strategy with
a non-zero threshold. So any mixed Nash Equilibrium must be made of threshold
strategies with non-zero thresholds. Thus the conditions of Theorem 3 hold,
and a pure Bayesian Nash Equilibrium exists. ∎

###  2.4 The Double Game Prisoner Dilemma

In this subsection, we define and study a more particular type of multigame
from [5] called Double Game Prisoner Dilemma (DGPD). On the discrete type
space section we will also refer to such multigames.

######  Definition 9.

The Double Game Prisoner Dilemma is a $(2,2,2)$-multigame (2 agents, 2 local
games, 2 actions) such that the first local game is a Prisoner’s Dilemma game
and the second local game is a social game motivating cooperation with the
following payoff matrices:

| agent 2
---|---
|  | $C$ | $D$
agent 1 | $C$ | $(r,r)$ | $(s,t)$
$D$ | $(t,s)$ | $(p,p)$
Table 1: Prisoner’s Dilemma Payoffs

| agent 2
---|---
|  | $C$ | $D$
agent 1 | $C$ | $(y,y)$ | $(y,z)$
$D$ | $(z,y)$ | $(z,z)$
Table 2: Social Game Payoffs

and such that

$s=z,\quad t>r>y>p>s,\quad r>(t+s)/2,\quad y>(r+p)/2$

There are 2 games, so we choose to denote the vector types of both agents with
$\begin{bmatrix}1-\theta_{1}\\\ \theta_{1}\end{bmatrix}$ and
$\begin{bmatrix}1-\theta_{2}\\\ \theta_{2}\end{bmatrix}$, $\theta_{i}$ is
called the pro-social coefficient of agent $i$.

Figure 1: Example of coefficients verifying the DGPD conditions

As a direct consequence of Theorem 4, we can easily deduce the existence of
pure Bayesian Nash Equilibrium.

######  Corollary 1.

For any DGPD with continuous type space and continuous prior, there exists a
pure Bayesian Nash Equilibrium (made of threshold strategies).

###### Proof.

This is a direct consequence of Theorem 4 as the social game is a purely
cooperative game for both agents. ∎

Replacing $u_{ij}(a_{i},a_{-i})$ and ${\boldsymbol{{\theta}}}_{i}$ in the
previous computations by DGPD parameters gives us:

$\displaystyle\overline{U_{i}}(C,\theta_{i},\sigma_{-i})$
$\displaystyle=(1-\theta_{i})\left[\zeta_{i}^{C}(\sigma_{-i})r+\zeta_{i}^{D}(\sigma_{-i})s\right]+\theta_{i}y$
(17) $\displaystyle\overline{U_{i}}(D,\theta_{i},\sigma_{-i})$
$\displaystyle=(1-\theta_{i})\left[\zeta_{i}^{C}(\sigma_{-i})t+\zeta_{i}^{D}(\sigma_{-i})p\right]+\theta_{i}s$
(18)

Note that for a given $\sigma_{-i}$, the expected values
$\overline{U_{i}}(C,\theta_{i},\sigma_{-i})$ and
$\overline{U_{i}}(D,{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$ are linear
functions in $\theta_{i}$ and they cross at
$\theta_{i}=\theta_{i}^{*}\in[0,1]$ since we have:

$y\geq
s,\quad\zeta_{i}^{C}(\sigma_{-i})r+\zeta_{i}^{D}(\sigma_{-i})s\leq\zeta_{i}^{C}(\sigma_{-i})t+\zeta_{i}^{D}(\sigma_{-i})p$

As a result of this, we can formulate a more convenient definition for
threshold strategy in the DGPD context.

######  Definition 10 (DGPD Threshold strategy).

A threshold strategy $\sigma_{i}$ with threshold $\theta_{i}^{*}$ for agent
$i$ is a strategy such that:

$\displaystyle\sigma_{i}(\theta_{i})=\begin{cases}D&\text{$\theta_{i}<\theta_{i}^{*}$}\\\
C&\text{$\theta_{i}>\theta_{i}^{*}$}\\\
\alpha_{i}C+(1-\alpha_{i})D&\text{$\theta_{i}=\theta_{i}^{*}$}\end{cases}$
(19)

Again, by construction, a best response must be a threshold strategy as we
have just rearranged the notation compared to the general definition. Note
that when the pro-social coefficient is low (i.e., below the threshold) agent
$i$ defects, and when the pro-social coefficient is high (i.e., above the
threshold) agent $i$ cooperates. Figure 2 summarizes the concept of threshold
strategy in the context of DGPD.

Figure 2: DGPD strategy summarized ($\lambda<\mu$).

We define the threshold function $\theta_{i}^{*}:[0,1]\rightarrow\mathds{R}$
by:

$\displaystyle\theta_{i}^{*}(x)$
$\displaystyle=\frac{x(t-r)+(1-x)(p-s)}{x(t-r)+(1-x)(p-s)+(y-s)}$ (20)

By a simple calculation, we conclude that, given the other agent strategy
$\sigma_{-i}$, agent $i$’s best response is a threshold strategy with
threshold $\theta_{i}^{*}=\theta_{i}^{*}(\zeta_{i}^{C}(\sigma_{-i}))$.

We now define $\lambda$ and $\mu$ that are combinations of DGPD payoff
parameters as in [6]:

$\displaystyle\mu:=\theta_{i}^{*}(0)=\frac{p-s}{p-s+y-s},\quad\quad\lambda:=\theta_{i}^{*}(1)=\frac{t-r}{t-r+y-s}$
(21)

######  Proposition 2 ($\theta_{i}^{*}$ monotonicity).

The threshold function $\theta_{i}^{*}:[0,1]\rightarrow\mathds{R}$ is
monotonic and is increasing if $\mu<\lambda$, decreasing if $\mu>\lambda$ and
is constant for $\mu=\lambda$.

###### Proof.

The monotonicity is straightforward. Then we just note that
$\theta_{i}^{*}(0)=\mu$ and $\theta_{i}^{*}(1)=\lambda$. ∎

######  Proposition 3.

For any DGPD with continuous type space and continuous prior, there exists a
pure Bayesian Nash Equilibrium. This equilibrium is made of threshold
strategies with thresholds
$\theta_{i}^{*}\in[\min(\lambda,\mu),\max(\lambda,\mu)]$.

###### Proof.

The predicate
$\theta_{i}^{*}=\theta_{i}^{*}(\zeta_{i}^{C}(\sigma_{-i}))\in[\min(\lambda,\mu),\max(\lambda,\mu)]$
results from the fact that $\zeta_{i}^{C}(\sigma_{-i})\in[0,1]$ and
$\theta_{i}^{*}(\zeta_{i}^{C}(x))$ is monotonic in $[0,1]$. ∎

###  2.5 Example for the SADP

Consider a simple situation with two companies, each having two different
visions and two possible actions. Assume, for example, that the first vision
is to protect the brand reputation and the second is to gain market shares.
Suppose that there’s an opportunity to establish a new production facility in
a controversial area. Seizing the opportunity will for sure help gain market
shares but will also impact negatively on the reputation. Each company can
either leave this opportunity (C) or compete to set up a new site in the area
(D). The following tables summarize this situation:

| company B
---|---
|  | $C$ | $D$
company A | $C$ | $(5,5)$ | $(0,9)$
$D$ | $(9,0)$ | $(2,2)$
Table 3: Market share Game

| company B
---|---
|  | $C$ | $D$
company A | $C$ | $(4,4)$ | $(4,0)$
$D$ | $(0,4)$ | $(0,0)$
Table 4: Reputation Game

Both companies have a continuous type space and prior. According to our last
result, there exists a pure Bayesian Nash Equilibrium made of threshold
strategies. By computing $\lambda=1/2$ and $\mu=1/3$, we also know that the
thresholds $\theta_{i}^{*}$ are in $[\frac{1}{3},\frac{1}{2}]$. If we add the
assumption that priors are uniform, we can show (see Section 2.7 on
Algorithmic results) that

$\theta_{1}^{*}=\theta_{2}^{*}=\frac{5-\sqrt{17}}{2}\approx 0.4384$

###  2.6 Application to Other 2-Players Games

In this section we present other examples of multigames for which we can apply
our result on the existence of pure NE.

####  2.6.1 A Chicken Game variation

In the Chicken Game (also called Hawk-Dove Game) [21] there are two agents
that can either go for the conflict (Conflict) or avoid it (Avoid). The best
outcome for an agent is to play Conflict while the other plays Avoid. As
opposed to the PD, if they both play Conflict, they both face the worst
outcome. An example is given in Table 5.

| Avoid | Conflict
---|---|---
Avoid | $(2,2)$ | $(1,3)$
Conflict | $(3,1)$ | $(0,0)$
Table 5: The Chicken Game payoff matrix

Because it is mainly a toy example like the PD, this game can only model very
specific situations. We suggest that the game can be understood as a
combination of two drivers: ego and survival. Under the ego consideration, we
want to play Conflict not to be considered the “chicken". What’s important is
to show that we dominate our opponent and have a stronger mind. Under the
survival consideration we mainly want to avoid the situation where both agents
play Conflict. An example of both games is given in Table 7 and 7. The double
game made of those two games with continuous priors has a pure Nash
Equilibrium because the ego game has a strictly dominant strategy (Conflict).

| agent 2
---|---
|  | Avoid | Conflict
agent 1 | Avoid | $(0,0)$ | $(-1,1)$
Conflict | $(1,-1)$ | $(0,0)$
Table 6: Ego Game

| agent 2
---|---
|  | Avoid | Conflict
agent 1 | Avoid | $(0,0)$ | $(0,0)$
Conflict | $(0,0)$ | $(-2,-2)$
Table 7: Survival Game

####  2.6.2 A Battle of Sexes Variation

In the Battle of Sexes (also called Bach or Stravinsky), there are two agents
that want to meet in a event but have opposed tastes. The main goal of both is
to spend time together but they also value the fact of going to the event they
like the most.

| Bach | Stravinsky
---|---|---
Bach | $(10,7)$ | $(2,2)$
Stravinsky | $(0,0)$ | $(7,10)$
Table 8: The Bach or Stravinsky payoff matrix

As presented in the previous example, we can try to decompose considerations
into Taste and Social. In the Taste Game (Table 10) both agents are motivated
to follow their taste no matter what the other does. In the Social Game (Table
10), the agents want to be at the same event, no matter which event it is.

| agent 2
---|---
|  | B | S
agent 1 | B | $(1,0)$ | $(1,1)$
S | $(0,0)$ | $(0,1)$
Table 9: Taste Game

| agent 2
---|---
|  | B | S
agent 1 | B | $(2,2)$ | $(0,0)$
S | $(0,0)$ | $(2,2)$
Table 10: Social Game

And like before, the double game made of those two games with continuous
priors has a pure Nash Equilibrium because the Taste Game has a strictly
dominant strategy (Bach for agent 1 and Stravinsky for agent 2).

####  2.6.3 An Assurance Game Variation

The Assurance Game (or Stag Hunt) is a 2-players game involving a conflict
between personal safety and social cooperation. An example of payoff matrix is
given in Table 11. By essence, this game is very similar to Prisoner Dilemma.
Thus we naturally combine it with a social game and get a variation of the
DGPD.

| Stag | Hunt
---|---|---
Stag | $(10,10)$ | $(1,8)$
Hunt | $(8,1)$ | $(5,5)$
Table 11: The Stag Hunt payoff matrix

###  2.7 Algorithmic results

####  2.7.1 Uniform prior

Recall the definition of $\zeta_{i}^{C}(\sigma_{-i})$ and
$\theta_{i}^{*}(\zeta_{i}^{C})$ that characterize the best response of an
agent given its opponent’s strategy (assuming that the both follow a threshold
strategy):

$\displaystyle\zeta_{i}^{C}(\sigma_{-i})=p_{-i}(\theta_{-i}\in[\max(\lambda,\mu),1])+\int_{\min(\lambda,\mu)}^{\max(\lambda,\mu)}f_{-i}(\theta_{-i})\sigma_{-i}(\theta_{-i},C)d\theta_{-i}$

$\displaystyle\theta_{i}^{*}(x)=\frac{x(t-r)+(1-x)(p-s)}{x(t-r)+(1-x)(p-s)+(y-s)}$

In the case of a uniform prior,
$p_{-i}(\theta_{-i}\in[\max(\lambda,\mu),1])=1-\max(\lambda,\mu)$. For
simplicity, we use the notation $\alpha=\min(\lambda,\mu)$ and
$\beta=\max(\lambda,\mu)$. Given that the opponent plays a threshold strategy
with the threshold $\theta_{-i}^{*}$, we have:

$\displaystyle\zeta_{i}^{C}(\sigma_{-i})$
$\displaystyle=1-\beta+\int_{\theta_{-i}^{*}}^{\beta}f_{-i}(\theta_{-i})d\theta_{-i}$
$\displaystyle=1-\beta+(\beta-\theta_{i}^{*})$
$\displaystyle=1-\theta_{i}^{*}$

Therefore, we can rewrite the threshold function $\theta_{i}^{*}$ as a
function of $\theta_{-i}^{*}$:

$\displaystyle\theta_{i}^{*}(\theta_{-i}^{*})$
$\displaystyle=\frac{(1-\theta_{-i}^{*})(t-r+s-p)+(p-s)}{(1-\theta_{-i}^{*})(t-r+s-p)+(p-s+y-s)}$
$\displaystyle=\frac{d(1-\theta_{-i}^{*})+e}{d(1-\theta_{-i}^{*})+e+f},$

where

$d:=t-r+s-p,\quad e:=p-s,\quad f:=y-s$

First, assume that the solution is symmetric for both players, meaning that
$\theta_{1}^{*}=\theta_{2}^{*}$:

$\displaystyle\theta_{i}^{*}=\frac{d(1-\theta_{i}^{*})+e}{d(1-\theta_{i}^{*})+e+f}$

which is reduced to:

$\displaystyle-d(\theta_{i}^{*})^{2}+(2d+e+f)\theta_{i}^{*}-(d+e)=0$ (22)

This is a quadratic equation. To evaluate the number of solutions we compute
the discriminant:

$\displaystyle\Delta$ $\displaystyle=(2d+e+f)^{2}-4d(d+e)$ (23)
$\displaystyle=(e+f)^{2}+4df$ (24)

If we search for non-symmetric solutions, the condition
$\theta_{i}^{*}=\theta_{-i}^{*}$ doesn’t hold anymore. By doing the same kind
of computation we end up with:

$\displaystyle-d(e+f)(\theta_{i}^{*})^{2}+((d+e+f)^{2}-d^{2})\theta_{i}^{*}-(e(d+e+f)+df)=0$
(25)

This is also a quadratic equation and we notice that it is the same quadratic
as the symmetric case but is multiplied by the constant $(e+f)\neq 0$. Hence,
both equations have exactly the same solutions.

######  Proposition 4.

Under the DGPD assumptions, the quadratic equations (23) and (25) always have
2 solutions.

###### Proof.

The discriminant of those quadratics can be written as
$\Delta=(e-f)^{2}+4(d+e)f$. By the constraints on the DGPD parameters, $f>0$
and $d+e=t-r>0$, and thus we have $\Delta>0$ and the quadratics have two
solutions $x_{-}=\frac{-(2d+e+f)-\sqrt{\Delta}}{-2d}$ and
$x_{+}=\frac{-(2d+e+f)+\sqrt{\Delta}}{-2d}$. ∎

Now, we need to check the validity of the solutions, i.e. $\alpha\leq
x_{sol}\leq\beta$.

######  Proposition 5.

Among the two solutions of the quadratics (23) and (25), $x_{+}$ is always
valid and $x_{-}$ is always invalid.

###### Proof.

By computing $x_{-}-\mu$ and $x_{-}-\lambda$ we can notice that depending on
the sign of $d$, we have either $x_{-}>\max(\mu,\lambda)$ or
$x_{-}<\min(\mu,\lambda)$. In both case the solution is not valid. With the
same kind of reasoning, we can show that depending on the sign of $d$, we have
either $\mu<x_{+}<\lambda$ or $\lambda<x_{+}<\mu$. Thus $x_{+}$ is always
valid. ∎

We end up with the fact that such games have always exactly one pure NE which
is symmetric (i.e. both players have the same threshold) where
$\theta_{1}^{*}=\theta_{2}^{*}=x_{+}$.

####  2.7.2 General solution

We denote by $F_{i}(x)$ the cumulative distribution function of agent $i$’s
prior $f_{-i}(\theta_{-i})$. In the case of uniform prior, we were able to
explicitly find $F_{i}(\cdot)$ and deduce an algebraic equation for the
solutions. To find a solution for any prior, we have to solve the follwing set
of equations:

$\displaystyle\theta_{1}^{*}$
$\displaystyle=\frac{A_{1}-dF_{1}(\theta_{2}^{*})}{B_{1}-dF_{1}(\theta_{2}^{*})}$
(26) $\displaystyle\theta_{2}^{*}$
$\displaystyle=\frac{A_{2}-dF_{2}(\theta_{1}^{*})}{B_{2}-dF_{2}(\theta_{1}^{*})}$
(27)

with

$\displaystyle\zeta_{i}^{C}(\sigma_{-i})$
$\displaystyle=F_{i}(1)-F_{i}(\theta_{-i}^{*})$ $\displaystyle A_{i}$
$\displaystyle=dF_{i}(1)+e$ $\displaystyle B_{i}$ $\displaystyle=A_{i}+f$

Therefore, for continuous type space, the NE search is equivalent to solving a
nonlinear multivariate equation:

$\displaystyle
f(\theta_{1}^{*},\theta_{2}^{*})=\left(\theta_{1}^{*}-\frac{A_{1}-dF_{1}(\theta_{2}^{*})}{B_{1}-dF_{1}(\theta_{2}^{*})},\theta_{2}^{*}-\frac{A_{2}-dF_{2}(\theta_{1}^{*})}{B_{2}-dF_{2}(\theta_{1}^{*})}\right)$
(28) find $(\theta_{1}^{*},\theta_{2}^{*})$ such that
$f(\theta_{1}^{*},\theta_{2}^{*})=0$ (29)

##  3 Uniform multigames with discrete type space

###  3.1 General Remarks

The type space is now assumed to be discrete. The term
$\overline{U}_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$, for $i\in
I$, is the same as the continuous prior except that the integral is now
replaced with a sum. Thus we keep the same notations and consider:

$\displaystyle\zeta_{i}^{a_{-i}}(\sigma_{-i}):=\sum_{{\boldsymbol{{\theta}}}_{-i}\in\Theta_{i}}p_{i}({\boldsymbol{{\theta}}}_{-i})\sigma_{-i}({\boldsymbol{{\theta}}}_{-i},a_{-i})\,d{\boldsymbol{{\theta}}}_{-i}$
(30)

$\displaystyle\overline{U}_{i}(a_{i},{\boldsymbol{{\theta}}}_{i},\sigma_{-i})$
$\displaystyle=\sum_{{\boldsymbol{{\theta}}}_{-i}\in\Theta_{-i}}p_{i}({\boldsymbol{{\theta}}}_{-i})U_{i}(a_{i},\sigma_{-i}({\boldsymbol{{\theta}}}_{-i}),{\boldsymbol{{\theta}}}_{i})$
$\displaystyle={\boldsymbol{{\theta}}}_{i}\cdot(\overline{u}_{ij}(a_{i},\sigma_{-i}))_{j\in
J}$

When there are only two actions, the notion of threshold strategy remains
exactly the same, but, since the type space is discrete, two strategies with
different thresholds can evaluate to the same value for types
${\boldsymbol{{\theta}}}_{i}\in\Theta_{i}$ and actions $a_{i}\in A_{i}$.

######  Definition 11 (Equivalent strategies and thresholds).

Two strategies $\sigma_{i}$ and $\sigma_{i}^{\prime}$, for player $i\in I$,
are said to be equivalent ($\sigma_{i}\sim\sigma_{i}^{\prime}$) if

$\forall({\boldsymbol{{\theta}}}_{i},a_{i})\in\Theta_{i}\times
A_{i},\quad\sigma_{i}({\boldsymbol{{\theta}}}_{i},a_{i})=\sigma_{i}^{\prime}({\boldsymbol{{\theta}}}_{i},a_{i})$

Given two threshold strategies $(\sigma_{i},{\boldsymbol{{\delta}}}_{i})$ and
$(\sigma_{i}^{\prime},{\boldsymbol{{\delta}}}_{i}^{\prime})$,
${\boldsymbol{{\delta}}}_{i}$ and ${\boldsymbol{{\delta}}}_{i}^{\prime}$ are
said to be equivalent
(${\boldsymbol{{\delta}}}_{i}\sim{\boldsymbol{{\delta}}}_{i}^{\prime}$) if
$\sigma_{i}\sim\sigma_{i}^{\prime}$.

Notice that the binary relation $\sim$ restricted to threshold strategies is
obviously an equivalence relation.

We also note that in contrast to the relation between strategies, the relation
between thresholds is not an equivalence relation. Indeed, if a threshold
leads to a mixed threshold strategy we cannot write
${\boldsymbol{{\delta}}}_{i}\sim{\boldsymbol{{\delta}}}_{i}$ because
$\alpha_{i}$ of Definition 7 is not constrained. In other words, two
strategies with the same threshold ${\boldsymbol{{\delta}}}_{i}$ can be
different (as long as the mixed case is reached by some
$\theta_{i}\in{\boldsymbol{{\Theta}}}_{i}$). Note that a threshold strategy
$\sigma_{i}$ is mixed if and only if there exists
${\boldsymbol{{\theta}}}_{i}\in\Theta_{i}$ such that
${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}=0$.

Given a threshold strategy $\sigma_{i}$, let
$S_{eq}(\sigma_{i}):=\\{\sigma_{i}^{\prime}\mid\sigma_{i}^{\prime}\sim\sigma_{i}\\}$
be the set of threshold strategies equivalent to $\sigma_{i}$. Given a
threshold ${\boldsymbol{{\delta}}}_{i}$, let
$T_{eq}({\boldsymbol{{\delta}}}_{i}):=\\{{\boldsymbol{{\delta}}}_{i}^{\prime}\mid{\boldsymbol{{\delta}}}_{i}^{\prime}\sim{\boldsymbol{{\delta}}}_{i}\\}$
be the set of thresholds equivalent to ${\boldsymbol{{\delta}}}_{i}$.

######  Proposition 6.

Suppose a threshold ${\boldsymbol{{\delta}}}_{i}$, for $i\in I$, leads to a
pure threshold strategy (i.e.
$\forall{\boldsymbol{{\theta}}}_{i}\in\Theta_{i}$
${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}\neq 0$). Then, we
have the following properties:

  1. 1.

$T_{eq}({\boldsymbol{{\delta}}}_{i})$ is a non-empty set.

  2. 2.

For any (strictly) positive $\lambda\in\mathds{R}^{*+}$,
$\lambda{\boldsymbol{{\delta}}}_{i}\in T_{eq}({\boldsymbol{{\delta}}}_{i})$.

  3. 3.

$T_{eq}({\boldsymbol{{\delta}}}_{i})$ is a convex set.

  4. 4.

If $\Theta_{i}$ is finite, $T_{eq}({\boldsymbol{{\delta}}}_{i})$ contains
vectors that are not collinear with ${\boldsymbol{{\delta}}}_{i}$.

###### Proof.

  1. 1.

We have: ${\boldsymbol{{\delta}}}_{i}\in T_{eq}({\boldsymbol{{\delta}}}_{i})$
and thus the latter set is non-empty.

  2. 2.

Since the strategy only depends on the sign of
${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}$, multiplying by
a strictly positive $\lambda$ has no impact on the resulting action.

  3. 3.

Take ${\boldsymbol{{\delta}}}_{i}^{1},{\boldsymbol{{\delta}}}_{i}^{2}\in
T_{eq}({\boldsymbol{{\delta}}}_{i})$, $\lambda\in[0,1]$ and
${\boldsymbol{{\delta}}}_{i}^{3}=\lambda{\boldsymbol{{\delta}}}_{i}^{1}+(1-\lambda){\boldsymbol{{\delta}}}_{i}^{2}$,
then notice that
${\boldsymbol{{\delta}}}_{i}^{3}\cdot{\boldsymbol{{\theta}}}_{i}=\lambda({\boldsymbol{{\delta}}}_{i}^{1}\cdot{\boldsymbol{{\theta}}}_{i})+(1-\lambda)({\boldsymbol{{\delta}}}_{i}^{2}\cdot{\boldsymbol{{\theta}}}_{i})$
has the same sign as
${\boldsymbol{{\delta}}}_{i}\cdot{\boldsymbol{{\theta}}}_{i}$, so that
${\boldsymbol{{\delta}}}_{i}^{3}\in T_{eq}({\boldsymbol{{\delta}}}_{i})$.

  4. 4.

Assume that $\Theta_{i}$ is finite and consider
$\epsilon=\frac{1}{m+1}\displaystyle\min_{{\boldsymbol{{\theta}}}_{i}\in\Theta_{i}}\left|{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}\right|$
and ${\boldsymbol{{\epsilon}}}=(\epsilon,\epsilon,...,\epsilon)$. Let
${\boldsymbol{{\delta}}}_{i}^{\prime}:={\boldsymbol{{\delta}}}_{i}+{\boldsymbol{{\epsilon}}}$:

$\displaystyle\left|{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}-{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}^{\prime}\right|=$
$\displaystyle\left|{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\epsilon}}}\right|$
$\displaystyle\leq$ $\displaystyle\,m\epsilon$ $\displaystyle<$
$\displaystyle\min_{{\boldsymbol{{\theta}}}_{i}\in\Theta_{i}}\left|{\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}\right|$

So ${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}$ and
${\boldsymbol{{\theta}}}_{i}\cdot{\boldsymbol{{\delta}}}_{i}^{\prime}$ have
the same sign for any ${\boldsymbol{{\theta}}}_{i}\in\Theta_{i}$ which
concludes the proof.

∎

###  3.2 The Double Game Prisoner Dilemma

We keep the same framework for the DGPD with a discrete type space. For each
$i\in I$, we have:

$\displaystyle\overline{U}_{i}(a_{i},\theta_{i},\sigma_{-i})$
$\displaystyle=\zeta_{i}^{C}(\sigma_{-i})U_{i}(a_{i},C,\theta_{i})+\zeta_{i}^{D}(\sigma_{-i})U_{i}(a_{i},D,\theta_{i})$
(31)

and

$\displaystyle\overline{U_{i}}(C,\theta_{i},\sigma_{-i})$
$\displaystyle=\zeta_{i}^{C}(\sigma_{-i})\left[(1-\theta_{i})r+\theta_{i}y\right]+\zeta_{i}^{D}(\sigma_{-i})\left[(1-\theta_{i})s+\theta_{i}y\right]$
(32) $\displaystyle\overline{U_{i}}(D,\theta_{i},\sigma_{-i})$
$\displaystyle=\zeta_{i}^{C}(\sigma_{-i})\left[(1-\theta_{i})t+\theta_{i}s\right]+\zeta_{i}^{D}(\sigma_{-i})\left[(1-\theta_{i})p+\theta_{i}s\right]$
(33)

######  Proposition 7.

Consider agent $i$ and let $\theta_{i}^{x}<\theta_{i}^{x+1}$ be two
consecutive types from $\Theta_{i}$. All threshold strategies $\sigma_{i}$
with a threshold $\theta_{i}^{*}$ such that
$\theta_{i}^{x}<\theta_{i}^{*}<\theta_{i}^{x+1}$ are equivalent.

###### Proof.

this follows from the fact that there exists no type $\theta_{i}\in\Theta_{i}$
between $\theta_{i}^{x}$ and $\theta_{i}^{x+1}$, so as long as we keep the
threshold between those two values we end up with the same actions for agent
$i$. ∎

Note that for threshold strategies, the third case
($\theta_{i}=\theta_{i}^{*}$) can only be reached if
$\theta_{i}^{*}\in\Theta_{i}$. So, if $\alpha_{i}\in\\{0,1\\}$ or
$\theta_{i}^{*}\notin\Theta_{i}$ then the strategy is pure.

The search for pure Nash Equilibrium in the discrete case requires a different
method since we do not have a general result for two-action multigames that
can be used as in the case of continuous type space. To go further, we assume
that the type space is finite. Recall, for player $i$, that
$\zeta_{i}^{a_{-i}}(\sigma_{-i})=\sum_{\theta_{-i}\in\Theta_{-i}}p_{i}(\theta_{-i})\sigma_{-i}(\theta_{-i},a_{-i})$
is the probability that the other agent’s action is $a_{-i}$ given that it
follows $\sigma_{-i}$.

######  Proposition 8 ($\zeta_{i}^{C}$ monotonicity).

Consider agent $i$ and suppose that the other agent follows a threshold
strategy $\sigma_{-i}$ with threshold $\theta_{-i}^{*}$. This threshold
strategy induces a value $\zeta_{i}^{C}(\sigma_{-i})$ for agent $i$. If the
other agent changes its strategy $\sigma_{-i}^{\prime}$ by increasing its
threshold $\theta^{*\prime}_{-i}$, then the induced value
$\zeta_{i}^{C}(\sigma^{\prime}_{-i})$ decreases.

###### Proof.

By increasing its threshold value, agent $-i$ decreases the probability of
playing C and thus decreases the value

$\zeta_{i}^{C}(\sigma_{-i}^{\prime})=\sum_{\theta_{-i}\in\Theta_{-i}}p_{i}(\theta_{-i})\sigma_{-i}^{\prime}(\theta_{-i},C)$

∎

For integers $K,L$ with $K\leq L$, let $\llbracket K,L\rrbracket$ denote the
set of integers, $K,K+1,\ldots,L$.

######  Lemma 1.

Suppose $f:\llbracket 0,M\rrbracket\rightarrow\llbracket 0,N\rrbracket$ and
$g:\llbracket 0,N\rrbracket\rightarrow\llbracket 0,M\rrbracket$ are both
increasing (or both decreasing). Then, there exists $c\in\llbracket
0,N\rrbracket$ such that $f(g(c))=c$.

###### Proof.

We first notice that $h:=f\circ g$ is increasing and $0\leq h(x)\leq N$ for
$0\leq x\leq N$. Hence, there exists a least non-negative integer $k$ such
that $c:=h^{k}(0)=h^{k+1}(0)$ and it follows that $h(c)=c$. ∎

######  Theorem 5.

For any DGPD with finite type space there exists a pure Bayesian Nash
Equilibrium made of threshold strategies such that for both agents, the
threshold $\theta_{i}^{*}\in[\min(\lambda,\mu),\max(\lambda,\mu)]$.

###### Proof.

We suppose that $\mu>\lambda$ (the reasoning for $\mu<\lambda$ is similar).
Suppose that agent $-i$ plays a threshold strategy
$(\sigma_{-i},\theta_{-i}^{*})$. Then the agent $i$’s best response is also a
threshold strategy $(\sigma_{i},\theta_{i}^{*})$. By the monotonicity of
$\theta_{i}^{*}$ and $\zeta_{i}^{C}$ (Propositions 2 and 8), if agent $-i$
increases its threshold then the threshold of agent $i$’s best response also
increases (if $\mu>\lambda$ then agent $i$’s best response threshold
decreases).

Now consider the partition of $[0,1]$ into intervals according to agents’ type
spaces:

$\displaystyle\Theta_{i}=\\{\theta_{i}^{1},\theta_{i}^{2},...,\theta_{i}^{n_{i}}\\}\quad\text{with}\quad
0\leq\theta_{i}^{1}<\theta_{i}^{2}<...<\theta_{i}^{n_{i}}\leq 1$ (34)
$\displaystyle I_{i}^{0}=[0,\theta_{i}^{1}],\quad
I_{i}^{1}=[\theta_{i}^{1},\theta_{i}^{2}],\quad...\quad
I_{i}^{n_{i}}=[\theta_{i}^{n_{i}},1]$ (35)

For agent $i$’s threshold strategy $(\sigma_{i},\theta_{i}^{*})$ and agent
$-i$’s best response $(\sigma_{-i},\theta_{-i}^{*})$, there exists (1)
$k_{i}\in\llbracket 0,n_{i}\rrbracket$ such that $\theta_{i}^{*}\in
I_{i}^{k_{i}}$ and (2) $k_{-i}\in\llbracket 0,n_{-i}\rrbracket$ such that
$\theta_{-i}^{*}\in I_{-i}^{k_{-i}}$. Note that if
$\theta_{-i}^{*}\in\Theta_{-i}$, then it belongs to two adjacent intervals
$I_{-i}^{k_{-i}}$ and $I_{-i}^{k_{-i}+1}$. In this case we arbitrarily choose
to take $I_{-i}^{k_{-i}}$.

We define the transition functions $t_{1\rightarrow 2}:\llbracket
0,n_{1}\rrbracket\rightarrow\llbracket 0,n_{2}\rrbracket$ and $t_{2\rightarrow
1}:\llbracket 0,n_{2}\rrbracket\rightarrow\llbracket 0,n_{1}\rrbracket$ such
that $k_{-i}=t_{i\rightarrow-i}(k_{i})$. In order to show that there exists a
pure Nash Equilibrium, we need to show that:

$\exists(k_{1},k_{2})\in\llbracket 0,n_{1}\rrbracket\times\llbracket
0,n_{2}\rrbracket\mid k_{1}=t_{2\rightarrow 1}(k_{2}),\quad
k_{2}=t_{1\rightarrow 2}(k_{1})$

Or equivalently we search for $k_{i}$ such that $k_{i}=t_{-i\rightarrow
i}(t_{i\rightarrow-i}(k_{i}))$. By Lemma 1 with $t_{1\rightarrow 2}$ and
$t_{2\rightarrow 1}$ as $f$ and $g$, we can find a solution $k_{i}$. ∎

###  3.3 Example

Suppose that $G$ is a Double Game Prisoner Dilemma with uniform prior such
that utilities for both agents are given according to Table 14 and 14 and type
space $\Theta_{i}=\\{t/60:t\in\llbracket 0,60\rrbracket\\}$ for $i=1,2$. We
obtain $\mu=1/5$ and $\lambda=1/4$.

| $C$ | $D$
---|---|---
C | $(16,16)$ | $(3,20)$
D | $(20,3)$ | $(6,6)$

Table 12: Utilities for the 1st game

| $C$ | $D$
---|---|---
C | $(15,15)$ | $(15,3)$
D | $(3,15)$ | $(3,3)$

Table 13: Utilities for the 2nd game

$\tfrac{1}{5}$$\tfrac{1}{4}$$1$$0$$\tfrac{1}{5}$$\tfrac{1}{4}$$1$$\tfrac{13}{60}$$\tfrac{14}{60}$$\tfrac{13}{60}$$\tfrac{14}{60}$$(D,C)$$(D,D)$$(C,C)$$(C,D)$
Table 14: Representation of both agent’s type space

To find a pure Bayesian NE, one has to find a pair $(s_{1},s_{2})$ of
threshold strategies such that $s_{1}$ is a best response to $s_{2}$ and
$s_{2}$ is a best response to $s_{1}$. By symmetry of the game, we can expect
that $s_{1}=s_{2}$ (i.e. they have the same threshold). We have:

$\displaystyle\theta_{i}^{*}(\zeta_{i}^{C})=\frac{\zeta_{i}^{C}(20-16)+(1-\zeta_{i}^{C})(6-3)}{\zeta_{i}^{C}(20-16)+(1-\zeta_{i}^{C})(6-3)+(15-3)}=\frac{\zeta_{i}^{C}+3}{\zeta_{i}^{C}+15}$

while $\zeta_{i}^{C}$ can take 3 different values:

$\displaystyle\theta_{-i}^{*}\in\left]\frac{1}{5},\frac{13}{60}\right[\implies\zeta_{i}^{C}=\frac{48}{61}$
$\displaystyle\theta_{-i}^{*}\in\left]\frac{13}{60},\frac{14}{60}\right[\implies\zeta_{i}^{C}=\frac{47}{61}$
$\displaystyle\theta_{-i}^{*}\in\left]\frac{14}{60},\frac{1}{4}\right[\implies\zeta_{i}^{C}=\frac{46}{61}$

Possible values for $\theta_{i}^{*}$ are $\theta_{i}^{*}(\frac{48}{61})\approx
0.239875$, $\theta_{i}^{*}(\frac{47}{61})\approx 0.239085$ or
$\theta_{i}^{*}(\frac{46}{61})\approx 0.238293$. Those three values are in the
interval $]\frac{14}{60},\frac{1}{4}[$. So the pair $(s_{1},s_{2})$ where

$\displaystyle
s_{1}(\theta_{1}^{*})=s_{2}(\theta_{2}^{*})=\begin{cases}\text{$D$ if
$\theta_{i}^{*}<\frac{1}{4}$}\\\ \text{$C$ if
$\theta_{i}^{*}\geq\frac{1}{4}$}\end{cases}$

is a pure (Bayesian) strategy Nash Equilibrium for the game $G$.

###  3.4 On a simple multigame classification

In this section, we consider $G_{2,2,2}$ multigames with finite type space.
Both actions are still denoted by C and D (even if they are not necessarily
associated to cooperation or defection). The payoff matrix $U$ is not
constrained as opposed to DGPD configuration. First, we define a simple
classification of such games according to properties of $U$.

######  Definition 12.

We denote the type space configuration by $(\Theta_{i},p_{i})$. Any payoff
matrix $U$ belongs to one of the following sets:

  1. 1.

The full set: payoff matrices $U$ such that for any type space configuration
the game $G=\langle U,(\Theta_{i},p_{i})\rangle$ has a pure Nash Equilibrium.

  2. 2.

The solutionless set: payoff matrices $U$ such that for any type space
configuration the game $G=\langle U,(\Theta_{i},p_{i})\rangle$ has no pure
Nash Equilibrium.

  3. 3.

The hybrid set: payoff matrices $U$ such that the existence of a pure NE for
$G=\langle U,(\Theta_{i},p_{i})\rangle$ depends on the type space
configuration.

######  Proposition 9.

The full set is not empty: it contains matrices $U$ with the DGPD payoff
constraints. The hybrid set is also not empty.

###### Proof.

The first set is obviously not empty in view of Theorem 5. The second set is
not empty as we can find $G$ and $G^{\prime}$ sharing the same payoff matrix
such that one has a pure NE and the other not (see next examples). ∎

Consider the uniform double game $G$ with utilities for agents $i=1,2$ given
by Table 15 with type space $\Theta_{1}=\\{0.2,0.5,0.6\\}$,
$\Theta_{2}=\\{0.2,0.4,0.8\\}$ and the prior $p_{1}$, $p_{2}$ such that:

$\displaystyle p_{1}(\theta_{1}=0.2)=0.3\quad p_{1}(\theta_{1}=0.5)=0.4\quad
p_{1}(\theta_{1}=0.6)=0.3$ $\displaystyle p_{2}(\theta_{2}=0.2)=0.3\quad
p_{2}(\theta_{2}=0.4)=0.4\quad p_{2}(\theta_{2}=0.8)=0.3$

| $C$ | $D$
---|---|---
C | $(3,4)$ | $(4,3)$
D | $(5,0)$ | $(1,1)$

| $C$ | $D$
---|---|---
C | $(2,4)$ | $(6,5)$
D | $(7,2)$ | $(5,2)$

Table 15: Utilities for both basic games.

This game has no pure Bayesian Nash Equilibrium. Consider a slight variation
$G^{\prime}$ of the game $G$ such that utilities for agents $i=1,2$ are given
by Table 15 with type space $\Theta_{1}=\\{0.2,0.5,0.7\\}$,
$\Theta_{2}=\\{0.2,0.4,0.8\\}$ and the prior $p_{1}$, $p_{2}$ such that:

$\displaystyle p_{1}(\theta_{1}=0.2)=0.3\quad p_{1}(\theta_{1}=0.5)=0.4\quad
p_{1}(\theta_{1}=0.7)=0.3$ $\displaystyle p_{2}(\theta_{2}=0.2)=0.3\quad
p_{2}(\theta_{2}=0.4)=0.4\quad p_{2}(\theta_{2}=0.8)=0.3$

Consider $\sigma_{1}$ a C/D threshold strategy with
$\theta_{1}^{*}\in]0.5,0.7[$ and $\sigma_{2}$ a C/D threshold strategy with
$\theta_{2}^{*}\in]0.2,0.4[$. The pair $(\sigma_{1},\sigma_{2})$ is a pure
Bayesian Nash Equilibrium for the game $G^{\prime}$.

Note that we don’t give any particular property for the solutionless set. We
postulate that this set is empty (see Section 3.5 on algorithmic results).
Recall the following formulae for the $G_{2,2,2}$ configuration:

$\displaystyle\overline{U_{i}}(a_{i},\theta_{i},\sigma_{-i})$
$\displaystyle=(1-\theta_{i})\overline{u}_{i1}(a_{i},\sigma_{-i})+\theta_{i}\overline{u}_{i2}(a_{i},\sigma_{-i})$
(36) $\displaystyle\overline{u}_{ij}(a_{i},\sigma_{-i})$
$\displaystyle=\zeta_{i}^{C}(\sigma_{-i})u_{ij}(a_{i},C)+(1-\zeta_{i}^{C}(\sigma_{-i}))u_{ij}(a_{i},D)$
(37)

Observe that with no assumption on the payoff matrix, there’s no guarantee
that $\overline{U_{i}}(C,\theta_{i},\sigma_{-i})$ and
$\overline{U_{i}}(D,\theta_{i},\sigma_{-i})$ will cross for a given
$\sigma_{-i}$. Moreover, the crossing point $\theta_{i}^{*}$ (if it exists) is
not guaranteed to be inside $[0,1]$ as illustrated by Figure 4 and Figure 4.
It cuts $\mathds{R}$ into two regions, one in which the best action is C and
the other in which the best action is D. If the left region is C then the
resulting strategy is a C/D strategy (Figure 4) and if the left region is D
then the resulting strategy is a D/C strategy (Figure 4). We call this the
strategy type. For any DGPD configuration, a best response is always a D/C
strategy.

Figure 3: Crossing point (threshold) inside $[0,1]$

Figure 4: Crossing point outside $[0,1]$

As we did for the DGPD, we define the threshold function
$\theta_{i}^{*}(\sigma_{-i})$ for agent $i$:

$\displaystyle\theta_{i}^{*}(\sigma_{-i})=\frac{\overline{u}_{i1}(C,\sigma_{-i})-\overline{u}_{i1}(D,\sigma_{-i})}{(\overline{u}_{i1}(C,\sigma_{-i})-\overline{u}_{i1}(D,\sigma_{-i}))-(\overline{u}_{i2}(C,\sigma_{-i})-\overline{u}_{i2}(D,\sigma_{-i}))}$
(38)

When
$\overline{u}_{i1}(C,\sigma_{-i})-\overline{u}_{i1}(D,\sigma_{-i})=\overline{u}_{i2}(C,\sigma_{-i})-\overline{u}_{i2}(D,\sigma_{-i})$,
both utility functions have the same slopes and the threshold function is not
defined. As long as
$\overline{u}_{i1}(C,\sigma_{-i})\neq\overline{u}_{i1}(D,\sigma_{-i})$,
utility functions are not equal so there is one best action (either C or D).
In this case the best response is also a threshold strategy with the threshold
$\theta_{i}^{*}=\pm\infty$. Otherwise, both utility functions are equal
(there’s an infinite number of crossing points). Because of the latter case,
we cannot state that any best response is made of threshold strategies
anymore.

######  Definition 13 (D/C threshold strategy).

A threshold D/C strategy $\sigma_{i}$ with threshold
$\theta_{i}^{*}\in\mathds{R}\cup\\{-\infty,+\infty\\}$ for agent $i$ is a
strategy such that:

$\displaystyle\sigma_{i}(\theta_{i})=\begin{cases}D&\text{$\theta_{i}<\theta_{i}^{*}$}\\\
C&\text{$\theta_{i}>\theta_{i}^{*}$}\\\
\alpha_{i}C+(1-\alpha_{i})D&\text{$\theta_{i}=\theta_{i}^{*}$}\end{cases}$
(39)

Now we can express the threshold as a function of $\zeta_{i}^{C}\in[0,1]$
instead of $\sigma_{-i}$:

$\displaystyle\theta_{i}^{*}(\zeta_{i}^{C})$
$\displaystyle=\frac{\delta_{i1}^{D}+\zeta_{i}^{C}(\delta_{i1}^{C}-\delta_{i1}^{D})}{\delta_{i1}^{D}-\delta_{i2}^{D}+\zeta_{i}^{C}(\delta_{i1}^{C}-\delta_{i1}^{D}+\delta_{i2}^{D}-\delta_{i2}^{C})}$
(40) $\displaystyle\mbox{where }\delta_{ij}^{a_{-i}}$
$\displaystyle:=u_{ij}(C,a_{-i})-u_{ij}(D,a_{-i})$ (41)

The case of equal slopes is reached at the forbidden value
$\widetilde{\zeta}_{i}^{C}$:

$\displaystyle\widetilde{\zeta}_{i}^{C}:=-\frac{\delta_{i1}^{D}-\delta_{i2}^{D}}{\delta_{i1}^{C}-\delta_{i2}^{C}+\delta_{i2}^{D}-\delta_{i1}^{D}}$
(42)

And therefore the case of equal utility functions happens when:

$\widetilde{\zeta}_{i}^{C}=\frac{\delta_{i1}^{D}}{\delta_{i1}^{D}-\delta_{i1}^{C}}$

We notice that the graph of $\theta_{i}^{*}(\zeta_{i}^{C})$ is split into two
regions by the forbidden value (Figure 6 and Figure 6). Each region is
associated with a different strategy type. Thus, if
$\widetilde{\zeta}_{i}^{C}$ is not in $[0,1]$ then agent $i$ will always play
the same strategy type notwithstanding its opponent’s strategy. In Figure 6
the forbidden value is outside $[0,1]$ so agent $i$ will only play D/C
strategy. In Figure 6, the forbidden value is in $[0,1]$, so agent $i$ may
play both strategy types depending on the opponent’s strategy $\sigma_{-i}$:
if $\zeta_{i}^{C}(\sigma_{-i})<\widetilde{\zeta}_{i}^{C}$ then agent $i$ plays
a C/D strategy and if $\zeta_{i}^{C}(\sigma_{-i})>\widetilde{\zeta}_{i}^{C}$
then agent $i$ plays a D/C strategy. Suppose that
$\widetilde{\zeta}_{i}^{C}\notin[0,1]$ for $i=1,2$. Both agents always stick
to the same strategy type and there are 3 cases: (1) both play C/D, (2) both
play D/C (like the DGPD) and (3) one plays C/D while the other plays D/C.

Figure 5: Forbidden value inside $[0,1]$

Figure 6: Forbidden value outside $[0,1]$

In order to characterize the variations of $\theta_{i}^{*}$, define:

$\displaystyle\Delta_{i}:=\delta_{i1}^{D}\delta_{i2}^{C}-\delta_{i1}^{C}\delta_{i2}^{D}$
(43)

######  Proposition 10 ($\theta_{i}^{*}$ monotonicity).

The threshold function $\theta_{i}^{*}(\zeta_{i}^{C})$ is monotonic and
satisfies:

  1. 1.

if $\Delta_{i}>0$ then $\theta_{i}^{*}(\zeta_{i}^{C})$ is increasing,

  2. 2.

if $\Delta_{i}<0$ then $\theta_{i}^{*}(\zeta_{i}^{C})$ is decreasing,

  3. 3.

if $\Delta_{i}=0$ then $\theta_{i}^{*}(\zeta_{i}^{C})$ is constant.

###### Proof.

Simply compute the derivative of the function $\theta_{i}^{*}(\zeta_{i}^{C})$
which is an homography $f:x\rightarrow\frac{ax+b}{cx+d}$ and get the condition
on $\Delta_{i}$. ∎

######  Proposition 11.

Let $U$ be the payoff matrix of a $2$-player double game such that:

  1. 1.

$\widetilde{\zeta}_{i}^{C}\notin[0,1]$ for $i=1,2$ where
$\widetilde{\zeta}_{i}^{C}$ is the forbidden value of
$\theta_{i}^{*}(\zeta_{i}^{C})$,

  2. 2.

$\Delta_{1}$ and $\Delta_{2}$ have the same sign if both agents play the same
strategy type, or have opposite sign otherwise.

Then for any type space configuration $(\Theta_{i},p_{i})$ the game $G=\langle
U,(\Theta_{i},p_{i})\rangle$ has a pure Bayesian Nash Equilibrium.

###### Proof.

The two conditions imply that (1) agents have a unique strategy type and (2)
their best response threshold functions have the same monotonicity, i.e.,
increasing or decreasing. Thus we can follow the same reasoning as we had for
DGPD to prove the existence of a pure Bayesian NE. ∎

###  3.5 Algorithmic results

In this section, we develop efficient algorithms to find pure Bayesian Nash
Equilibrium for finite type space $G_{2,2,2}$. The first part focuses on an
optimized version for DGPD while the second one focuses on a more general
version. In the third part, the complexity of both algorithms are evaluated
and compared to each other.

####  3.5.1 Algorithm for DGPD

Recall that the agents’ best response sets are only made of threshold
strategies. Thus, given a finite type space (with $n_{i}$ elements for agent
$i$) the search space is made of $n_{1}\times n_{2}$ threshold strategy pairs.
The pure Bayesian Nash Equilibrium search consists in finding a fixed point
(two strategies that are mutually best responses of each other) among those
combinations.

Figure 7: If agent 1 plays a threshold strategy with
$\theta_{1}^{*}\in[0.1,0.3]$, agent 2’s best response is a threshold strategy
with $\theta_{2}^{*}\in[0.1,0.4]$

For clarity, we formulate a graphical method to represent the solution search
that we call strategy diagram and looks like figure 7. There are two unit
intervals $[0,1]$, one for each agent’s type space. An arrow from agent $i$’s
interval $I_{i}$ to agent $-i$’s interval $I_{-i}$ indicates that if agent $i$
plays a threshold strategy with a threshold in $I_{i}$, the best response of
agent $-i$ is a threshold strategy with a threshold in $I_{-i}$. A solution is
then simply represented by two compatible arrows as displayed in Figure 8.

Figure 8: A pure Bayesian NE represented by compatible arrows.

We now introduce algorithm 1 for NE search on finite DGPD. For every threshold
strategy of agent $1$, we compute the associated best response of agent $2$
and then compute the best response of agent $1$ given the latter. Whenever for
any of agent $1$’s threshold strategy the computed best response is
equivalent, we obtain a pure NE. The procedure compute_cumul_proba() returns
the cumulative probabilities given a probability distribution. finder()
returns the index of the type space interval that contains a given threshold.
search_space_boundaries() computes $\alpha=min(\mu,\lambda)$ and
$\beta=max(\mu,\lambda)$ and then the associated indices in the type space. It
helps us optimize the overall algorithm by reducing the search space to
thresholds $\theta_{i}^{*}\in[\alpha,\beta]$. Finally, threshold_i() is the
threshold function of agent $i$.

Algorithm 1 Exhaustive NE search

0: $t,r,y,p,s,\Theta_{1},\Theta_{2},p_{1},p_{2}$

$cumul\\_proba\\_1\leftarrow compute\\_cumul\\_proba(p_{1})$

$cumul\\_proba\\_2\leftarrow compute\\_cumul\\_proba(p_{2})$

$start\\_1,end\\_1\leftarrow
search\\_space\\_boundaries(t,r,y,p,s,\Theta_{1})$

for $start\\_1\leq i<end\\_1+1$ do

$\zeta^{C}_{2}\leftarrow 1-cumul\\_proba\\_1[i]$

$\theta^{*}_{2}\leftarrow threshold\\_2(\zeta^{C}_{2})$

$k\leftarrow finder(\Theta_{2},\theta^{*}_{2})$

$\zeta^{C}_{1}\leftarrow 1-cumul\\_proba\\_2[k]$

$\theta^{*}_{1}\leftarrow threshold\\_1(\zeta^{C}_{1})$

if $\Theta_{1}[i-1]\leq\theta^{*}_{1}\leq\Theta_{1}[i]$ then

return $\theta^{*}_{1}$, $\theta^{*}_{2}$

end if

end for

return False

Figures 9 and 10 illustrate the finding of NE search for two situations that
we encounter. Note that when $\lambda<\mu$ we reverse the $2^{nd}$ agent’s
axis as the best response threshold monotonicity is reversed compared to
$\lambda>\mu$. Also note that there could be multiple solutions (Figure 10).
If we only seek one solution then we stop at the first finding to reduce the
computational cost.

Figure 9: Strategy diagram when $\lambda>\mu$ Figure 10: Strategy diagram when
$\lambda<\mu$

####  3.5.2 General algorithm

We now describe a different algorithm that can handle a broader range of games
but is more expensive. It can also handle DGPD games but is less optimal.

Figure 11: Search process for the discrete Double Game

Apart from the fact that we have to explore both C/D and D/C strategies, the
double game algorithm is very similar to the DGPD algorithm. For each type
space interval of agent 1, we compute the best response of agent 2 and the
best response of agent 1 given the latter. We check that we fall back to the
initial strategy by ensuring that the thresholds are in the same interval and
that the strategy types are the same. Of course, we cannot benefit from the
reduced search space with $\lambda$ and $\mu$ as they make no sense in the
general context. The overall procedure is summarized in Figure 11.

Given this general algorithm we explore some properties of payoff matrices. We
generated hundreds of random payoff matrices and thousands of type space
configurations and ran Nash Equilibrium searches. We experimentally classified
the payoff matrices thanks to the NE search results. Interestingly, we notice
that none of the generated matrices belongs to the solutionless set as we
postulated earlier. Secondly, we find that there exist matrices in the full
set that do not satisfy the conditions of Proposition 11: the set of
conditions is sufficient, but not necessary, for belonging to the full set.

Figure 12: Average number of solutions with respect to the input size of both
agents. Each curve corresponds to a payoff matrix. Among matrices belonging to
the full set, we distinguish those satisfying the conditions of Proposition 11
(left) from those not satisfying them (right).

Next, using a modified version of the NE search that doesn’t stop at the first
solution (if it exists) we computed the average number of solutions for
different type space configurations. Let input size denote the number of
elements in the type space for both players. In this context,
$n=card(\Theta_{1})$ and $m=card(\Theta_{2})$.

Figure 12 shows the results for a sample of payoff matrices randomly picked
from the full set (thanks to our previous classification). The first trivial
result is that the average never goes under 1 (otherwise it wouldn’t belong to
the full set). Secondly, it seems that the average number of solution can
either be constant, increase or decrease with the input size. In many cases we
even observe that the average number tends to stabilize around an arbitrary
value which seems to be an integer.

Figure 13: Average number of solutions with respect to the input size of both
agents. Each curve corresponds to a payoff matrix from the hybrid set.

We repeated this experiment with payoff matrices randomly picked from the
hybrid set. Figure 13 shows a sample of results for such matrices. As we said
earlier for the full set, it seems that the averages can either increase,
decrease or stay constant and that they converge to different values. This
time, those values are smaller than 1 and may not be integers.

####  3.5.3 Complexity comparison

In this part, we discuss the complexity of each algorithm and compare their
performances.

First of all, the left part of Figure 14 displays the complexity of DGPD NE
search for different variations of inputs. When $n=m$, both input sizes vary,
while when $n=10$ or $m=10$ only input size varies. Notice that when the first
agent’s input size is constant, the complexity is also constant. When $n$
varies, the complexity is linear and is almost independent of whether $m$
varies or not. In fact, the main driver of the complexity is the main loop
that iterates over the elements of $\Theta_{1}$. The procedure finder() has a
low computational cost as it consists in a binary search. In practice, for
imbalanced type space size, one should always consider the agent having the
smallest type space as the first agent.

Figure 14: DGPD time complexity (left) and comparison with general algorithm
(right)

The right part of Figure 14 illustrates the improved performance of DGPD
specific algorithm over the more general one. The latter also has a linear
complexity but with a much higher slope. One explanation comes from the fact
that for each element of $\Theta_{1}$ we consider both C/D and D/C strategies
as starting points. Also, we don’t reduce the search space with bounds like
$\mu$ and $\lambda$.

Figure 15: Complexity comparison for different input sizes through computation
time (left) and average number of iterations (right)

For the general algorithm, we also compare the complexity for different
variations of the input size as display in Figure 15 (left). Again the
complexity heavily relies on the first agent’s type space size. In contrast to
the DGPD algorithm, we notice that for $m=10$ the complexity is slightly below
the complexity when $n=m$. On the right side of Figure 15 we see that this
behaviour cannot be explained by a difference in the number of iterations on
the main loop. It is probably due to the cost of finder() that increases in
$\mathcal{O}(\log(m))$ when $m$ increases. This effect might also affect the
DGPD algorithm but is not significant in our experiment.

##  4 Conclusion

In this paper, we explored pure Bayesian Nash Equilibrium existence for a
subset of uniform multigames. We made the distinction between games according
to their type space, either continuous or discrete.

For continuous type space games with $2$ actions, we showed in Theorem 4 the
existence of a pure Bayesian Nash Equilibrium when there are local games
having a strictly dominant strategy for each agent. We illustrated its
application through the DGPD and SDAP examples that can model real situations
with more precision than toy examples usually presented. In Section 2.7 we
formulated a methodology to solve $2$ action games with any kind of prior.

For finite type space DGPD, we showed in Theorem 5 the existence of a pure
Bayesian Nash Equilibrium. Following this, we were able to provide efficient
algorithms to find pure Bayesian Nash Equilibrium and explore experimentally
our classification of discrete Double Multigames (Proposition 11).

Threshold Strategy is a core concept developed for both the continuous and the
discrete type space games with $2$ actions. As we saw, a threshold strategy is
fully characterized by its threshold and defines 3 regions in the type space:
one associated to a pure action C, one associated to a pure action D and one
associated to a mix. By construction, a best response must be a threshold
strategy. The threshold strategies presented for the DGPD are the more basic
version where we have: play D if $\theta_{i}<\theta_{i}^{*}$, play C if
$\theta_{i}>\theta_{i}^{*}$ and a mix of both if $\theta_{i}=\theta_{i}^{*}$.

As for future work, we could try to extend this notion to more that 2 actions.
In this case, we would consider the $\operatorname*{\arg\\!\max}_{a_{i}\in
A_{i}}{\boldsymbol{{\theta}}}_{i}\cdot(\overline{u}_{ij}(a_{i},\sigma_{-i}))_{j\in
J}$ to determine the action played by agent $i$ with type
${\boldsymbol{{\theta}}}_{i}$. When the highest value is reached by two or
more actions $a_{i}$, the response of agent $i$ would be a mixed combination
of such actions. This definition would still use the fact that a Nash
Equilibrium solution (be it pure or mixed) must be made of threshold
strategies.

## References

  * [1]
  * Carrozzo Magli et al. [2021] Alessio Carrozzo Magli, Pompeo Della Posta, and Piero Manfredi.  The tragedy of the commons as a prisoner’s dilemma. its relevance for sustainability games.  _Sustainability_ , 13(15), 2021.  ISSN 2071-1050.  doi:10.3390/su13158125.  URL https://www.mdpi.com/2071-1050/13/15/8125.
  * Daskalakis et al. [2009] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou.  The complexity of computing a Nash equilibrium.  _SIAM Journal on Computing 39(1)_ , 2009.
  * Dresher [1970] Melvin Dresher.  Probability of a pure equilibrium point in n-person games.  _Journal of Combinatorial Theory_ , 8(1):134–145, 1970.  ISSN 0021-9800.  doi:https://doi.org/10.1016/S0021-9800(70)80015-1.  URL https://www.sciencedirect.com/science/article/pii/S0021980070800151.
  * Edalat et al. [2012] Abbas Edalat, Ali Ghoroghi, and Georgios Sakellariou.  Multi-games and a double game extension of the prisoner’s dilemma.  _CoRR_ , abs/1205.4973, 2012.  URL http://arxiv.org/abs/1205.4973.
  * Edalat et al. [2018] Abbas Edalat, Samira Hossein Ghorban, and Ali Ghoroghi.  Ex post Nash equilibrium in linear Bayesian games for decision making in multi-environments.  _Games_ , 2018.
  * Einy and Haimanko [2023] Ezra Einy and Ori Haimanko.  Pure-strategy equilibrium in Bayesian potential games with absolutely continuous information.  _Games and Economic Behavior_ , 140:341–347, 2023.  ISSN 0899-8256.  doi:https://doi.org/10.1016/j.geb.2023.04.004.  URL https://www.sciencedirect.com/science/article/pii/S0899825623000556.
  * Ewerhart and Kovenock [2021] Christian Ewerhart and Dan Kovenock.  A class of n-player colonel blotto games with multidimensional private information.  _Operations Research Letters_ , 49(3):418–425, 2021.  ISSN 0167-6377.  doi:https://doi.org/10.1016/j.orl.2021.03.010.  URL https://www.sciencedirect.com/science/article/pii/S0167637721000511.
  * Flood [1958] Merrill M. Flood.  Some experimental games.  _Management Science_ , 5(1):5–26, 1958.  ISSN 00251909, 15265501.
  * Friedman [1998] Daniel Friedman.  On economic applications of evolutionary game theory.  _Journal of evolutionary economics_ , 8(1):15–43, 1998.
  * Hardin [1968] Garrett Hardin.  The tragedy of the commons.  _Science_ , 162(3859):1243–1248, 1968.  ISSN 00368075, 10959203.  URL http://www.jstor.org/stable/1724745.
  * Harsanyi [1967] John C. Harsanyi.  Games with incomplete information played by "Bayesian" players, i-iii. part i. the basic model.  _Management Science_ , 14(3):159–182, 1967.
  * Harsanyi [1968a] John C. Harsanyi.  Games with incomplete information played by "Bayesian" players, i-iii. part ii. Bayesian equilibrium points.  _Management Science_ , 14(5):320–334, 1968a.  ISSN 00251909, 15265501.
  * Harsanyi [1968b] John C. Harsanyi.  Games with incomplete information played by "Bayesian" players, i-iii. part iii. the basic probability distribution of the game.  _Management Science_ , 14(7):486–502, 1968b.  ISSN 00251909, 15265501.
  * He and Sun [2019] Wei He and Yeneng Sun.  Pure-strategy equilibria in Bayesian games.  _Journal of Economic Theory_ , 180:11–49, 2019.  ISSN 0022-0531.  doi:https://doi.org/10.1016/j.jet.2018.11.007.  URL https://www.sciencedirect.com/science/article/pii/S0022053118301716.
  * J. van den Assem et al. [2011] Martijn J. van den Assem, Dennie van Dolder, and Richard H. Thaler.  Split or steal? cooperative behavior when the stakes are large.  _Management Science, Vol. 58_ , 2011.
  * Krishna and Perry [1998] Vijay Krishna and Motty Perry.  Efficient mechanism design.  1998\.
  * Larson [2021] Jennifer M. Larson.  Networks of conflict and cooperation.  _Annual Review of Political Science_ , 24(1):89–107, 2021.  doi:10.1146/annurev-polisci-041719-102523.
  * Luenberger [1998] D. G. Luenberger.  _Investment Science_.  Oxford University Press, 1998.
  * Monderer and Shapley [1996] Dov Monderer and Lloyd S. Shapley.  Potential games.  _Games and Economic Behavior_ , 14(1):124–143, 1996.  ISSN 0899-8256.  doi:https://doi.org/10.1006/game.1996.0044.  URL https://www.sciencedirect.com/science/article/pii/S0899825696900445.
  * Osborne and Rubinstein [1994] Martin J. Osborne and Ariel Rubinstein.  _A Course in Game Theory_ , volume 1 of _MIT Press Books_.  The MIT Press, April 1994.  ISBN 9780262650403.
  * Papadimitriou [1994] Christos H. Papadimitriou.  On the complexity of the parity argument and other inefficient proofs of existence.  _Journal of Computer and System Sciences 48(3)_ , 1994.
  * Poundstone and von Neumann [1993] William Poundstone and John von Neumann.  Prisoner’s dilemma.  1993\.
  * Rabinovich et al. [2013] Zinovi Rabinovich, Victor Naroditskiy, Enrico H. Gerding, and Nicholas R. Jennings.  Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types.  _Artificial Intelligence_ , 195:106–139, 2013.  ISSN 0004-3702.  doi:https://doi.org/10.1016/j.artint.2012.09.007.  URL https://www.sciencedirect.com/science/article/pii/S0004370212001191.
  * Rinott and Scarsini [2000] Yosef Rinott and Marco Scarsini.  On the number of pure strategy Nash equilibria in random games.  _Games and Economic Behavior_ , 33(2):274–293, 2000.  ISSN 0899-8256.  doi:https://doi.org/10.1006/game.1999.0775.  URL https://www.sciencedirect.com/science/article/pii/S0899825699907753.
  * Shapiro [1989] Carl Shapiro.  The theory of business strategy.  _The Rand journal of economics_ , 20(1):125–137, 1989.
  * Stanford [1995] William Stanford.  A note on the probability of k pure Nash equilibria in matrix games.  _Games and Economic Behavior_ , 9(2):238–246, 1995.  ISSN 0899-8256.  doi:https://doi.org/10.1006/game.1995.1019.  URL https://www.sciencedirect.com/science/article/pii/S0899825685710196.
  * Stanford [1997] William Stanford.  On the distribution of pure strategy equilibria in finite games with vector payoffs.  _Mathematical Social Sciences_ , 33(2):115–127, 1997.  ISSN 0165-4896.  doi:https://doi.org/10.1016/S0165-4896(96)00826-8.  URL https://www.sciencedirect.com/science/article/pii/S0165489696008268.
  * Stanford [1999] William Stanford.  On the number of pure strategy Nash equilibria in finite common payoffs games.  _Economics Letters_ , 62(1):29–34, 1999.  ISSN 0165-1765.  doi:https://doi.org/10.1016/S0165-1765(98)00219-5.  URL https://www.sciencedirect.com/science/article/pii/S0165176598002195.
  * Székely et al. [2010] Tamás Székely, Allen J Moore, and Jan Komdeur.  _Social behaviour: genes, ecology and evolution_.  Cambridge University Press, 2010.
  * von Neumann and Morgenstern [1944] John von Neumann and Oskar Morgenstern.  _Theory of Games and Economic Behavior_.  New York: John Wiley and Sons, 1944.