# Noisy Games: A Study on the Effect of Noise on Game Specifications

Constantinos Varsos
Centrum Wiskunde & Informatica
(CWI)
<EMAIL_ADDRESS>
&Giorgos Flouris
Foundation for Research and Technology-Hellas
(FORTH)
<EMAIL_ADDRESS>
∧ Marina Bitsaki
Institute of Computer Science, University of Crete
<EMAIL_ADDRESS>

###### Abstract

We consider misinformation games, i.e., multi-agent interactions where the
players are misinformed with regards to the game that they play, essentially
having an _incorrect_ understanding of the game setting, without being aware
of their misinformation. In this paper, we introduce and study a new family of
misinformation games, called Noisy games, where misinformation is due to
structured (white) noise that affects additively the payoff values of players.
We analyse the general properties of Noisy games and derive theoretical
formulas related to “behavioural consistency”, i.e., the probability that the
players behaviour will not be significantly affected by the noise. We show
several properties of these formulas, and present an experimental evaluation
that validates and visualises these results.

##  1 Introduction

A common assumption in game theory [17, 18] is that the abstract formulation
of the game (number of players, strategies available to the players and
payoffs depending on the chosen strategies) are publicly available to all
players. Even for games with incomplete information [26], the fact that
knowledge is incomplete, and the exact form of incompleteness, is embedded in
the game specification.

However, in several scenarios, it could be the case that the players may have
wrong information regarding the game setup, and at the same time being unaware
of the fact that their information is wrong, thus being _misinformed_. The
agents, being unaware of their misinformation, may make choices that are
unexpected and seem irrational from the external viewpoint, leading to
unexpected results. These games are called _misinformation games_ [25] (see
also Figure 1).

The main defining characteristic of misinformation games is that the players
have no reason to believe that they have the wrong payoff information, and
will play the game under the misconceived definition (payoffs) that they have.
Nevertheless, the payoff that they will get is the one provisioned by the
actual game. This makes the concept of misinformation games quite different
from other types of games that have been defined in the literature, in
particular games that incorporate uncertainty in their payoffs (e.g., Bayesian
games [26]); in games with incomplete information, although uncertainty makes
the players unsure as to their actual payoff for each different strategy, the
players are well-aware of that, and they accommodate their strategies
accordingly, in order to make the best out of the uncertainty that they have.
On the contrary, in misinformation games the players believe the information
that was given, and do not consider mitigation measures “just in case” the
information is wrong.

In previous works [25, 19], various different causes of misinformation are
identified, including deception and misleading reports, human errors,
deliberate attempts by the game designer to channel players into different
behaviours, erroneous sensor readings and random effects. In this paper, we
focus on a special case of misinformation, attributed to noise and signal
errors, a situation often occurring in distributed multiagent systems. This
class of misinformation games will be called _noisy games_.

Specifically, in distributed multiagent systems, agents111Note that we use the
terms “agent” and “player” interchangeably throughout the paper. are equipped
with an internal logic that allows them to autonomously solve problems of a
given nature. However, at deployment time, the precise specification of these
problems is often unknown; instead, the details are communicated as needed at
operation time, during the so-called “online phase” [8]. In such cases,
unexpected communication errors, malfunctions in the communication module or
noise may cause the agents to operate under a distorted problem specification,
leading to unexpected behaviour.

Figure 1: Visualisation of a misinformation/noisy game

For example, consider the scenario where we have two autonomous self-
interested agents, already deployed in an unfriendly environment. At some
point in time, the human controller asks each of the agents to choose among
two actions, also specifying the payoffs for each combination of choices. If
the communication goes through as expected, then the behaviour of the agents
is predictable by the well-known results of game theory. However, if one (or
both) of the agents’ communication module malfunctions, or if there is
unexpected noise in the communication channel, the signal may arrive
distorted. This could lead agents to receive an erroneous payoff matrix,
essentially causing them to believe that they play a game different than the
one communicated to them, with unpredictable results (Figure 1).

Note that, if, at deployment time, the designer had foreseen the possibility
for the agents to receive an erroneous game specification, then the agents
would have been programmed to treat all signals as uncertain (i.e., true under
a certain probability). In this case, the possibility of error is integrated
in the agents’ logic (even when no communication error occurs), and their
behaviour can be modelled using the rich results on Bayesian games and games
with incomplete information [26]. On the other hand, if such a scenario had
not been foreseen at deployment time, then the agents will operate under the
payoff matrices received, without considering the possibility that the payoff
matrices are not the correct ones. This is quite different, as the agents’
decisions will be totally misled by the erroneous setting, and will not
consider mitigation measures “just in case” the specification that they
received is wrong.

The aim of this paper is to provide the theoretical machinery necessary to
study scenarios of this kind. In particular, the main research question to be
addressed is: _given a game and a specific noise pattern affecting the
players’ perceived payoff matrices, compute the probability that players’
behaviour (i.e., chosen strategies) will be as close as possible (in a manner
to be formally defined later) to the behaviour that they would have in the
absence of noise_.

In summary, the main contributions of this paper are the following:

  1. 1.

The provision of motivation for the need to define misinformation in the
context of noisy games, by positioning our work with respect to other similar
efforts in the literature, in particular related to games with uncertainty,
and games where the players have some kind of misconception related to the
game’s payoffs (Section 2).

  2. 2.

The definition of a formal model for the description of misinformation in
noisy games (Section 4).

  3. 3.

The computation of the probability that the players’ behaviour is not
significantly affected by random noise, a feature that we call _behavioural
consistency_ (Section 5).

  4. 4.

A thorough analysis of the properties of these probabilities (Section 6).

  5. 5.

Experimentation to visualize and validate our results (Section 7).

##  2 Related Work

The works most related to the concept of noisy games are those of games with
misspecified views (e.g., [7], [12], [22]). Despite the fact that Bayesian
techniques are very popular in this stream of works, there is no consideration
about the structure of misinformation that results in these views. As opposed
to Bayesian games, where there is a rich literature that studies the influence
of the structure of uncertainty in the knowledge of the players to their
strategic behaviour. Thus, conceptually we are closer to the first group of
works. On the other hand though, we study too the effect of distributions in
the knowledge of the players as to their strategic behaviour, thus our results
can be related to the latter stream of works.

Bayesian games and games with incomplete information [26] have been introduced
to handle uncertainty about players’ payoffs. This uncertainty is represented
by probabilities over the alternative payoff matrices. Also, there are cases
where some payoffs are simply unknown. In all cases, the players are aware of
the fact that the information they have is incomplete, and their strategies
are adapted to cater for this incompleteness. This is the main difference with
regards to misinformation games, where information is complete, but incorrect.
That is, players are unaware of the fact that the information they have is
incorrect, and thus, their strategic choices are entirely based on it.

The works [13, 14, 15] are also relevant to ours. In these studies, the
authors consider non-atomic routing games, and suggest that the players
experience their own cost functions, which are potentially different from the
actual ones (e.g., to model player-specific biases). This setting is similar
to a misinformation game, except that, in our methodology, each player has a
potentially different view of the entire game (including the payoffs of the
other players), not just her own payoffs, and plays according to that view. In
addition, the two approaches have a quite different motivation: in [13]
authors assume that players modify their payoffs from the objective ones, by
themselves, for personal reasons (bias or some kind of personal preference);
in our case, the modifications are accidental, caused by communication errors.

In [4], the authors consider the impact of small fluctuations in the cost
functions or in players’ perceptions of the cost structure in congestion and
load balancing games, and study its effect on players’ behaviour. A
fluctuation is a departure from the classical viewpoint that treats payoffs as
a number; under [4], the payoff is a range of values “close” to the actual
payoff. An extension of [4] considered normal-form games, aiming to define a
new notion of equilibrium that maximizes the worst case outcome over possible
actions by other players [1] in the presence of fluctuations, whereas a
further extension ([5]) studied the robustness of this equilibrium solution,
utilizing the notion of approximations of payoffs using a fuzziness to the
values of payoff matrices. There are several differences of the concept of
fluctuation as compared to misinformation. First, the players are aware of the
fluctuations and, thus, take them into account while deciding on their
strategic choices. Second, fluctuations affect all players and all payoffs
uniformly. Third, fluctuations have a limited effect, whereas the noise
considered in our work may have unlimited effect (subject to a certain
probability function).

Further, in [8] the authors study how resilient is the strategic behaviour of
players when an unexpected communication loss occurs, and explore game
settings in which communication failures can/cannot cause harm in the
strategic behaviour of players. They introduce the notion of _proxy payoffs_
in order to funnel communication failures and show that, in several settings,
loss of information may cause arbitrary strategic behaviours. Our work has a
similar contribution as both works prove that in the presence of communication
inefficiencies any strategic behaviour is possible. Though, authors in [8]
focus on how the agents choose policies so as to cope with communication
failures, in this study we analyse the impact of disorder in the strategic
behaviour of the players. Also, we model communication failure using
probabilities, and provide formulas that quantify the probability of
arbitrariness in strategic behaviours, when information is degraded due to
noise.

Moreover, there is another stream of works considering random payoff matrices,
(i.e. [9, 24, 23, 21, 6, 10]) where the focus is on the distribution of pure
Nash equilibria. A tweak of this methodology is presented in [20] where
authors study the distribution of players’ average social utility.

##  3 Preliminaries

###  3.1 A brief refresher on probability theory

We provide here some basic knowledge on probability theory that will be useful
in the following sections. The interested reader is referred to [2] for
further details.

A random variable $X$ is characterised by its _probability density function
(pdf)_ , denoted by $f_{X}$, which represents the “intensity” of the
probability in each given point. The pdf can be used to compute the
probability that $X$ falls within a given range, say $[a,b]$, for any $a\leq
b$. Formally, $f_{X}$ is such that:

${\mathcal{P}}\boldsymbol{\left[\right.}a\leq X\leq
b\boldsymbol{\left.\right]}=\int^{b}_{a}f_{X}(x)dx$

We denote by $F_{X}$ the _cumulative distribution function (cdf)_ of a random
variable $X$, which equals the probability that the value of $X$ is at most
$x$. Formally:

$F_{X}(x)=\int^{x}_{-\infty}f_{X}(t)dt={\mathcal{P}}\boldsymbol{\left[\right.}X\leq
x\boldsymbol{\left.\right]}$

In this paper, we focus on random variables $X$ following the normal
distribution, denoted by $X\sim{\mathcal{N}}\left(\mu,d^{2}\right)$ (for some
mean $\mu\in\mathbb{R}$ and standard deviation222In probability theory,
standard deviation is typically denoted by $\sigma$. To avoid confusion with
the strategies of normal form games which use the same symbol (see Subsection
3.2), we use $d$ as a symbol for standard deviation in this paper. $d>0$). For
the special case where $\mu=0,d=1$ (i.e., when
$X\sim{\mathcal{N}}\left(0,1\right)$), we get the _standard normal
distribution_ , with the following pdf ($\phi$) and cdf ($\Phi$):

$\displaystyle\phi(x)=\tfrac{1}{\sqrt{2\pi}}e^{-\tfrac{x^{2}}{2}},\quad\Phi(x)=\tfrac{1}{\sqrt{2\pi}}\int^{x}_{-\infty}e^{-\frac{t^{2}}{2}}dt$
(1)

For the general case, where $X\sim{\mathcal{N}}\left(\mu,d^{2}\right)$, the
pdf and cdf are:

$\displaystyle
f_{X}(x)=\frac{1}{d}\phi\left(\frac{x-\mu}{d}\right)=\tfrac{1}{d\sqrt{2\pi}}e^{-\left(\tfrac{x-\mu}{d\sqrt{2}}\right)^{2}}$
(2) $\displaystyle
F_{X}(x)=\Phi\left(\frac{x-\mu}{d}\right)=\tfrac{1}{\sqrt{2\pi}}\int^{\tfrac{x-\mu}{d}}_{-\infty}e^{-\frac{t^{2}}{2}}dt$

It has been shown that, if
$X_{i}\sim{\mathcal{N}}\left(\mu_{i},d_{i}^{2}\right)$,
$c_{0},c_{i}\in\mathbb{R}$, then:

$c_{0}+\sum c_{i}X_{i}\sim{\mathcal{N}}\left(c_{0}+\sum c_{i}\mu_{i},\sum
c_{i}^{2}d_{i}^{2}\right)$ (3)

Given two events $A,B$, the symbol
${\mathcal{P}}\boldsymbol{\left[\right.}A|B\boldsymbol{\left.\right]}$ denotes
the _conditional probability of $A$ given $B$_, which amounts to the
probability that $A$ is true under the condition that $B$ is true.

When combining events, the following are true:

$\begin{split}&\text{General Conjunction Rule: }\\\ &\hskip
50.00008pt{\mathcal{P}}\boldsymbol{\left[\right.}A\wedge
B\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}B\boldsymbol{\left.\right]}\cdot{\mathcal{P}}\boldsymbol{\left[\right.}A|B\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}A\boldsymbol{\left.\right]}\cdot{\mathcal{P}}\boldsymbol{\left[\right.}B|A\boldsymbol{\left.\right]}\\\
&\text{Restricted Conjunction Rule: }\\\ &\hskip
50.00008pt{\mathcal{P}}\boldsymbol{\left[\right.}A\wedge
B\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}A\boldsymbol{\left.\right]}\cdot{\mathcal{P}}\boldsymbol{\left[\right.}B\boldsymbol{\left.\right]}\quad\text{(when
}A,B\text{ are mutually exclusive)}\\\ &\text{General Disjunction Rule: }\\\
&\hskip 50.00008pt{\mathcal{P}}\boldsymbol{\left[\right.}A\vee
B\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}A\boldsymbol{\left.\right]}+{\mathcal{P}}\boldsymbol{\left[\right.}B\boldsymbol{\left.\right]}-{\mathcal{P}}\boldsymbol{\left[\right.}A\wedge
B\boldsymbol{\left.\right]}\\\ &\text{Restricted Disjunction Rule: }\\\
&\hskip 50.00008pt{\mathcal{P}}\boldsymbol{\left[\right.}A\vee
B\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}A\boldsymbol{\left.\right]}+{\mathcal{P}}\boldsymbol{\left[\right.}B\boldsymbol{\left.\right]}\quad\text{(when
}A,B\text{ are mutually exclusive)}\\\ \end{split}$ (4)

###  3.2 Normal-form games

Normal-form games [17, 18] is the most commonly-studied class of games. A game
in normal-form is represented by a _payoff matrix_ that defines the payoffs of
all players for all possible combinations of pure strategies. Formally:

######  Definition 1 (Normal-form games).

A normal-form game $G$ is a tuple $G=\langle N,S,P\rangle$, where:

  * •

$N=\\{1,2,\dots,n\\}$ is the set of players.

  * •

$S=S_{1}\times\dots\times S_{n}$, $S_{i}$ is the set of pure strategies of
player $i\in N$.

  * •

$P=(P_{1}\mathchar 24635\relax\;\dots\mathchar 24635\relax\;P_{n})$,
$P_{i}\in\mathbb{R}^{|S_{1}|\times\ldots\times|S_{n}|}$ is the payoff matrix
of player $i\in\\{1,2,\dots,n\\}$.

In this paper we focus on _$2\times 2$ bimatrix games_, a popular class of
games defined as follows:

######  Definition 2 ($2\times 2$ bimatrix games).

A $2\times 2$ bimatrix game $G$ is a normal-form game $G=\langle
N,S,P\rangle$, such that:

  * •

$N=\\{r,c\\}$ is the set of players

  * •

$S=S_{r}\times S_{c}$, where $S_{r}=S_{c}=\\{s_{1},s_{2}\\}$

  * •

$P=(P_{r}\mathchar 24635\relax\;P_{c})$, $P_{r},P_{c}\in\mathbb{R}^{2\times
2}$

Let us now fix some player $x\in\\{r,c\\}$. A _strategy_ of $x$ is a pair
$\sigma_{x}=(\sigma_{x,1},\sigma_{x,2})$, where $(\sigma_{x,1},\sigma_{x,2})$
form a discrete probability distribution over $S_{x}$ (i.e.,
$\sigma_{x,1},\sigma_{x,2}\in[0,1],\sigma_{x,1}+\sigma_{x,2}=1$). When
$\sigma_{x,1},\sigma_{x,2}\in(0,1)$ the strategy is called a _mixed strategy_
; otherwise, it is called a _pure strategy_. The _support_ of a strategy
$\sigma_{x}$, denoted by $supp(\sigma_{x})$, is the set of pure strategies
(from $S_{x}$) that are played with positive probability on $\sigma_{x}$
(thus, $supp(\sigma_{x})\subseteq S_{x}$). We denote by $\Sigma_{x}$ the set
of all possible strategies of player $x$. Apparently, for $2\times 2$ bimatrix
games, $\Sigma_{x}=\\{(p,1-p)\mid 0\leq p\leq 1\\}$.

A _strategy profile_ is a pair $\sigma=(\sigma_{r},\sigma_{c})$, for
$\sigma_{r}\in\Sigma_{r},\sigma_{c}\in\Sigma_{c}$. We denote by $\Sigma$ the
set of all strategy profiles, i.e., $\Sigma=\Sigma_{r}\times\Sigma_{c}$. A
strategy profile is called _pure_ if it consists of pure strategies only,
_mixed_ if it consists of mixed strategies only, and _hybrid_ if it consists
of a pure and a mixed strategy.

The _payoff function_ of player $x$, under a given strategy profile
$\sigma=(\sigma_{r},\sigma_{c})$, $u_{x}\mathrel{\mathop{\mathchar
58\relax}}\Sigma\to\mathbb{R}$, is defined as:

$u_{x}(\sigma_{r},\sigma_{c})=\sigma_{r}^{T}P_{x}\sigma_{c}$

where $\sigma_{r}^{T}$ represents the transposition of vector $\sigma_{r}$.

For $x\in\\{r,c\\}$, we denote by $\bar{x}$ the other player, i.e.,
$\bar{r}=c,\bar{c}=r$. Given a strategy $\sigma_{x}$ of $x\in\\{r,c\\}$, the
_best response_ of $\bar{x}$ is the strategy $\sigma_{\bar{x}}$ that maximizes
her payoff, given $\sigma_{x}$. A _Nash equilibrium_ is a strategy profile for
which any unilateral change in the strategy of any given player would not
produce a better payoff for that player. In other words, a Nash equilibrium is
a strategy profile where each player plays her best response, given the other
player’s strategic choice. For bimatrix games, this notion can be formalised
as follows:

######  Definition 3 (Nash equilibrium [16]).

A strategy profile $\sigma^{*}=(\sigma^{*}_{r},\sigma^{*}_{c})$ is a _Nash
equilibrium_ if and only if, for any $\hat{\sigma}_{r}\in\Sigma_{r}$,
$\hat{\sigma}_{c}\in\Sigma_{c}$,

${\sigma^{*}_{r}}^{T}P_{r}\sigma^{*}_{c}\geq\hat{\sigma}_{r}^{T}P_{r}\sigma^{*}_{c}\quad\text{
and
}\quad{\sigma^{*}_{r}}^{T}P_{c}\sigma^{*}_{c}\geq{\sigma^{*}_{r}}^{T}P_{c}\hat{\sigma}_{c}$

It has been shown that all games possess at least one Nash equilibrium [16].
If $\sigma^{*}=(\sigma^{*}_{r},\sigma^{*}_{c})$ is a Nash equilibrium, then
$\sigma^{*}_{r},\sigma^{*}_{c}$ are called _Nash equilibrium strategies_. We
denote by $NE(G)$ the set of all Nash equilibria for a game $G$, and by
$NE_{x}(G)$ the Nash equilibrium strategies of player $x$ in $G$.

A $2\times 2$ bimatrix game is called _degenerate_ if and only if there is a
pure strategy that has two pure best responses.

In the seminal work of [11], the authors defined a metric, the Price of
Anarchy (PoA), that measures the efficiency of a system with non-cooperative
players. Let $SW(\sigma)$ be the social welfare function defined as the sum of
players’ payoffs for the strategy profile $\sigma$, and $opt$ the socially
optimal strategy profile, i.e.,
$opt=\operatorname*{arg\,max}_{\sigma}SW(\sigma)$. Then, $PoA$ is defined as
follows:

######  Definition 4.

Given a normal-form game $G$, the _Price of Anarchy (PoA)_ is defined as:

$PoA=\frac{SW(opt)}{\min_{\scriptscriptstyle\sigma\in ne}SW(\sigma)}$ (5)

###  3.3 Notational conventions and shorthands

To avoid confusion caused by the use of multiple indices in subsequent
sections, we will use the notation $A[i,j]$ to refer to the element in the
$i^{th}$ row and $j^{th}$ column of a matrix $A$, i.e., if $A=(a_{ij})$, then
$A[i,j]=a_{ij}$.

We will use boldface to indicate tables whose elements are all equal to a
certain value. For example $\boldsymbol{[b]}_{n\times m}$ represents the
$n\times m$ table $B$, such that $B[i,j]=b$ for all $i,j$. The $n\times m$
subscript will be omitted when obvious from the context.

For three tables $A,M,D$ of the same dimensions, we write
$A\sim{\mathcal{N}}\left(M,D\right)$ to indicate that
$A[i,j]\sim{\mathcal{N}}\left(M[i,j],D[i,j]\right)$ for all $i,j$.

Analogously, we extend the notation used in limits ($x\to a$) for tables. In
particular, for two tables $X,A$ of the same dimension, we write $X\to A$ to
denote $X[i,j]\to A[i,j]\;\forall i,j$. We extend the notation to include
infinity, e.g., $X\to\boldsymbol{[+\infty]}$ is equivalent to
$X[i,j]\to+\infty$ for all $i,j$.

We define operators on payoff matrices as follows. Consider a $2\times 2$
bimatrix game $G=\langle N,S,P\rangle$, where $P=(P_{r}\mathchar
24635\relax\;P_{c})$. Then:

  * •

For $2\times 2$ tables $M_{r},M_{c},D_{r},D_{c}$, the expression
$G\sim{\mathcal{N}}\left((M_{r}\mathchar 24635\relax\;M_{c}),(D_{r}\mathchar
24635\relax\;D_{c})\right)$ indicates that
$P_{r}\sim{\mathcal{N}}\left(M_{r},D_{r}\right),P_{c}\sim{\mathcal{N}}\left(M_{c},D_{c}\right)$

  * •

For a $2\times 2$ bimatrix $A=(A_{r}\mathchar 24635\relax\;A_{c})$ and
$\lambda\in\mathbb{R}$, the result of the operation $\lambda G+A$ is the
$2\times 2$ bimatrix game $G^{\prime}=\langle
N^{\prime},S^{\prime},P^{\prime}\rangle$, where
$N^{\prime}=N,S^{\prime}=S,P^{\prime}=\lambda P+A$

##  4 Misinformation Games and Noisy Games

###  4.1 Basic Definitions

_Misinformation games_ have been originally defined in [25]. In this section,
we extend the main definitions and concepts for the case of noisy games.

Misinformation games have been defined to capture the idea that different
players may have a different view of the game they play (see Figure 1). This
leads to the following definition:

######  Definition 5 (Misinformation game).

A _misinformation normal-form game_ (or simply _misinformation game_) is a
tuple $mG=\langle G^{0},G^{1},\ldots,G^{n}\rangle$, where all $G^{i}$ are
normal-form games and $G^{0}$ contains $n$ players.

In the above definition, $G^{0}$ is called the _actual game_ (corresponding to
the game actually being played), whereas $G^{i}$ is the _game of player $i$_
(corresponding to the game that player $i$ thinks that it is being played).

In [25], it was shown that, without loss of generality, we only need to
concentrate ourselves in the special class of _canonical misinformation
games_. A misinformation game $\langle G^{0},G^{1},\ldots,G^{n}\rangle$ is
called _canonical_ if and only if:

  * •

In $G^{0}$, all players have an equal number of pure strategies

  * •

For any $x\in\\{1,\dots,n\\}$, $G^{0},G^{x}$ differ only in their payoff
matrices

_Noisy games_ are a special class of misinformation games, where
misinformation is due to a random distortion in the original payoff matrix.
Formally:

######  Definition 6 (Noisy game).

A _noisy game_ is a canonical misinformation game $mG=\langle
G^{0},G^{1},\ldots,G^{n}\rangle$, where $G^{i}=G^{0}+\Delta^{i}$ for some
matrix $\Delta^{i}$ whose elements follow a certain probability distribution.

Note that the restriction of a noisy game being canonical implies that noise
affects only the payoff matrix. In a more general scenario, noise could also
affect the number of players and/or the strategies that a player understands
(knows) regarding a game. However, as shown in [25], we can restrict ourselves
to canonical games for simplicity.

In this paper, we concentrate on noisy games whose actual game is a $2\times
2$ bimatrix game, and where each element of $\Delta^{i}$ follows the normal
distribution. We call such games _normal noisy games_. Therefore:

######  Definition 7 (Normal noisy game).

A _normal noisy game_ is a tuple $mG=\langle G^{0},G^{r},G^{c}\rangle$, where:

  * •

$G^{0},G^{r},G^{c}$ are $2\times 2$ bimatrix games

  * •

For $x\in\\{r,c\\}$, $G^{x}=G^{0}+\Delta^{x}$, where $\Delta^{x}$ is a
bimatrix whose elements follow the normal distribution (possibly for a
different mean and standard deviation)

For $M=(M_{r}\mathchar 24635\relax\;M_{c})$, $D=(D_{r}\mathchar
24635\relax\;D_{c})$, we write $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$ to
indicate a normal noisy game $mG=\langle G^{0},G^{r},G^{c}\rangle$, where
$G^{x}=G^{0}+\Delta^{x}$,
$\Delta^{x}\sim{\mathcal{N}}\left(M_{x},D_{x}\right)$. Formula 3 implies that,
when $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, then
$G^{x}\sim{\mathcal{N}}\left(G^{0}+M_{x},D_{x}\right)$.

###  4.2 Strategies, strategy profiles and equilibria in misinformation games

We define strategies and equilibrium concepts for the case of normal noisy
games of two players. Our formulation can be extended to apply to arbitrary
misinformation games.

Consider a canonical normal noisy game $mG$. A _misinformed strategy_
$\sigma_{x}$ for player $x$ in $mG$ is a strategy in $G^{x}$. A _misinformed
strategy profile_ results by the agglomeration of misinformed strategies for
the individual game, and is defined as a pair
$\sigma=(\sigma_{r},\sigma_{c})$, where $\sigma_{x}$ is a misinformed strategy
of $x\in\\{r,c\\}$. Pure/mixed misinformed strategies, and pure/mixed/hybrid
strategy profiles are defined analogously to their standard counterparts (see
Subsection 3.2). Since $mG$ is canonical, a misinformed strategy (and
misinformed strategy profile) is also a strategy (strategy profile) in
$G^{0}$. Thus, we simply use $\Sigma_{x}$ to denote the set of misinformed
strategies of player $x$ in $mG$, and $\Sigma$ to denote the set of
misinformed strategy profiles of $mG$.

It is important to note that, although the decisions of a player are made
based on his own payoff matrix (the one in $G^{x}$), payoffs are computed on
the basis of the actual payoff matrix (the one in $G^{0}$). This is reflected
in the definition of payoffs and equilibria below.

Let $P^{0}=(P_{r}^{0}\mathchar
24635\relax\;P_{c}^{0}),P^{r}=(P_{r}^{r}\mathchar
24635\relax\;P_{c}^{r}),P^{c}=(P_{r}^{c}\mathchar 24635\relax\;P_{c}^{c})$ be
the payoff matrices of $G^{0},G^{r},G^{c}$ respectively. Then:

  * •

The _actual payoff function_ of player $x$, under a given strategy profile
$\sigma=(\sigma_{r},\sigma_{c})$, $u_{x}\mathrel{\mathop{\mathchar
58\relax}}\Sigma\to\mathbb{R}$, is defined as:

$u_{x}(\sigma_{r},\sigma_{c})=\sigma_{r}^{T}P_{x}^{0}\sigma_{c}$

  * •

The _misinformed payoff function_ of player $x$, under the viewpoint of player
$y$ and the strategy profile $\sigma=(\sigma_{r},\sigma_{c})$,
$u^{y}_{x}\mathrel{\mathop{\mathchar 58\relax}}\Sigma\to\mathbb{R}$, is
defined as:

$u^{y}_{x}(\sigma_{r},\sigma_{c})=\sigma_{r}^{T}P_{x}^{y}\sigma_{c}$

Note that the actual payoff function represents the payoff that player $x$
will receive as a response to her strategic choices. On the contrary, the
misinformed payoff function represents the payoff that player $x$ believes
that she will receive, under the (erroneous) view of the game that player $y$
has.

A notion of equilibrium, defined in [25], considers misinformed equilibrium
simply as the agglomeration of the Nash equilibrium strategies of each player
in her own game:

######  Definition 8 (Natural misinformed equilibrium (nme)).

A misinformed strategy, $\sigma^{*}_{x}$, of player $x$, is a _natural
misinformed equilibrium strategy_ , if and only if it is a Nash equilibrium
strategy for $x$ in $G^{x}$. A misinformed strategy profile $\sigma^{*}$ is
called a _natural misinformed equilibrium (nme)_ if it consists of natural
misinformed equilibrium strategies.

The natural misinformed equilibrium will occur in one-off settings, i.e., when
each player just picks a (seemingly optimal) strategy based on his own
viewpoint. It is easy to see that at least one natural misinformed equilibrium
exists in any misinformation game.

Inspired by [11], the authors of [25] defined a metric to measure the effect
of misinformation compared to the social optimum, based on a social welfare
function $SW$. This metric is called _Price of Misinformation (PoM)_ , and is
defined as follows:

######  Definition 9.

Given a misinformation game $mG$, the _Price of Misinformation (PoM)_ is
defined as:

$PoM=\frac{SW(opt)}{\min_{\scriptscriptstyle\sigma\in nme}SW(\sigma)}$ (6)

Apparently, if $PoM=1$, the players adopt optimal behaviour, due to
misinformation. Moreover, interesting results can be derived by comparing the
$PoA$ of $G^{0}$ with the PoM of $mG$: if $PoM<PoA$, then misinformation has a
beneficial effect on social welfare, as the players are inclined (due to their
misinformation) to choose socially better strategies; on the other hand, if
$PoM>PoA$, then misinformation leads to a worse outcome, from the perspective
of social welfare.

###  4.3 Behavioural Consistency and $\varepsilon$-closeness

The misinformed equilibria of a normal noisy game may be different than the
Nash equilibria of the actual game. We define a metric to quantify the
distance among these equilibria and their respective strategies, essentially
measuring the effect of noise on the behaviour of the players. For the
definition, we use the infinite norm distance for vectors; formally, for a
vector $\vec{v}=(v_{1},v_{2})$, the infinite norm distance
$\|\vec{v}\|_{\infty}=\max\\{v_{1},v_{2}\\}$. The notion of
$\varepsilon$-closeness is now defined as follows:

######  Definition 10 ($\varepsilon$-closeness).

Let $\sigma=(\sigma_{1},\sigma_{2})$,
$\sigma^{\prime}=(\sigma_{1}^{\prime},\sigma_{2}^{\prime})$ be two strategies
and $\varepsilon\geq 0$. Then we say that $\sigma,\sigma^{\prime}$ are
_$\varepsilon$ -close_ if and only if $supp(\sigma)=supp(\sigma^{\prime})$ and
$\|\sigma-\sigma^{\prime}\|_{\infty}\leq\varepsilon$. For strategy $\sigma$,
the set of strategies that are $\varepsilon$-close to it, is denoted by
$Cl^{\varepsilon}(\sigma)$.

Intuitively, the definition states that two strategies are $\varepsilon$-close
if and only if they have identical supports and the allocation imposed by the
players’ strategies does not differ by more than $\varepsilon$ in any
dimension. The fact that $\varepsilon$-closeness requires identical supports
is based on the idea that adding (or removing) a pure strategy to (from) the
support of a strategy is considered a major change in the player’s behaviour.

Note also that the above definition applies on strategies in general, and,
thus, allows us to apply it also to check $\varepsilon$-closeness among
strategies and/or misinformed strategies, as long as in each strategy profile
each player has the same number of pure strategies.

We extend Definition 10 to (misinformed and non-misinformed) strategy profiles
(and equilibria), in the obvious manner: $\sigma=(\sigma_{r},\sigma_{c})$ is
$\varepsilon$-close to
$\sigma^{\prime}=(\sigma_{r}^{\prime},\sigma_{c}^{\prime})$ if and only if
$\sigma_{r}$ is $\varepsilon$-close to $\sigma_{r}^{\prime}$ and $\sigma_{c}$
is $\varepsilon$-close to $\sigma_{c}^{\prime}$. We denote by
$Cl^{\varepsilon}(\sigma)$ the strategy profiles that are $\varepsilon$-close
to $\sigma$. For a set of strategy profiles $\Sigma^{*}$, we set
$Cl^{\varepsilon}(\Sigma^{*})=\bigcup_{\sigma\in\Sigma^{*}}Cl^{\varepsilon}(\sigma)$,
i.e., the strategy profiles that are $\varepsilon$-close to at least one of
the strategy profiles in $\Sigma^{*}$.

The definition of $\varepsilon$-closeness gives formal substance to the idea
of the behaviour of the players (expressed as an equilibrium) being “similar”:
two equilibria that are $\varepsilon$-close are “similar” (and vice-versa).
This notion allows us to formally define the behavioural consistency of
players in the presence of noise, which amounts to checking whether the
equilibria of the noisy game are similar (i.e., $\varepsilon$-close) to the
“expected” ones under the actual game. Formally:

######  Definition 11.

Consider a normal noisy game $mG$ and some _tolerance_ $\varepsilon\geq 0$.
Then,

  * •

$mG$ is _$\varepsilon$ -misinformed_ iff for every natural misinformed
equilibrium $\sigma^{*}$ of $mG$, there is a Nash equilibrium $\sigma^{0}$ of
$G^{0}$, such that $\sigma^{*}\in Cl^{\varepsilon}(\sigma^{0})$.

  * •

$mG$ is _inverse- $\varepsilon$-misinformed_ iff for every Nash equilibrium
$\sigma^{0}$ of $G^{0}$, there is a natural misinformed equilibrium
$\sigma^{*}$ of $mG$, such that $\sigma^{*}\in Cl^{\varepsilon}(\sigma^{0})$.

###  4.4 Running example

The following example will be used as a running example for the rest of the
paper to illustrate our results.

######  Example 1.1 (Running example).

We consider two autonomous robotic agents $r,c$, deployed in a remote
environment. At some point in time, the human controller asks each of the
agents to choose among two actions $s_{1},s_{2}$, also specifying the payoffs
for each combination of choices, as shown in matrix $P^{0}$ below.

$P^{0}=\left(\begin{array}[]{cc}(3,2)&(0,0)\\\ (0,0)&(2,3)\\\
\end{array}\right)$

The above payoff matrix corresponds to the well-known Battle of the Sexes
(BoS) game333See
https://en.wikipedia.org/wiki/Battle_of_the_sexes_(game_theory)., which has
three Nash equilibria, namely $\sigma^{0}_{1}=((1,0),(1,0))$,
$\sigma^{0}_{2}=((0,1),(0,1))$, $\sigma^{0}_{3}=((0.6,0.4),(0.4,0.6))$.

However, one of the components of the central communication module has
received damage, unknowingly to the agents or the human controller, causing it
to introduce a random noise ($\delta\sim{\mathcal{N}}\left(0,1\right)$) to
each of the values in $P^{0}$ during transmission. The above setting can be
modelled as a normal noisy game $mG=\langle G^{0},G^{r},G^{c}\rangle\sim
G^{0}+{\mathcal{N}}\left(M^{x}_{y},D^{x}_{y}\right)$, where the payoff matrix
of $G^{0}$ is $P^{0}$, and $M^{x}_{y}=\boldsymbol{[0]}_{2\times
2},D^{x}_{y}=\boldsymbol{[1]}_{2\times 2}$ for all $x,y\in\\{r,c\\}$.

Our objective here is to compute the probability that the robotic agents will
exhibit behavioural consistency (Definition 11), despite the noise caused by
the malfunction. This question will be addressed in Section 5 below.

##  5 Probabilities for behavioural consistency

In this section, we will compute the probabilities for a normal noisy game
being (inverse-)$\varepsilon$-misinformed. For better readability, we split
our analysis in 3 subsections. In Subsection 5.1, we recast some known results
from game theory in a way that is more suitable for our analysis, whereas in
Subsection 5.2, we develop some results that determine necessary and
sufficient conditions for a misinformation game to be
(inverse-)$\varepsilon$-misinformed. These results are then employed in
Subsection 5.3 to compute the required probabilities. The respective results
are summarized in Table 1 (for Subsection 5.1), Table 2 (for Subsection 5.2)
and Tables 3, 4 and 5 (for Subsection 5.3).

###  5.1 Determining Equilibrium Strategies

For a $2\times 2$ bimatrix game $G$, we denote by $\text{{ugain}}^{G}(x,i)$
the _utility gain_ of strategy $s_{1}$ (compared to $s_{2}$) for player
$x\in\\{r,c\\}$ when her opponent plays $s_{i}$, in game $G$. The reference to
$G$ will be omitted when obvious from the context. Note that
$\text{{ugain}}(x,i)$ is determined by the elements of the payoff matrix of
$G$ (say $P=(P_{r}\mathchar 24635\relax\;P_{c})$) as follows:

  * •

For $x=r$, $\text{{ugain}}(r,i)=P_{r}[1,i]-P_{r}[2,i]$

  * •

For $x=c$, $\text{{ugain}}(c,i)=P_{c}[i,1]-P_{c}[i,2]$

Intuitively, $\text{{ugain}}(x,i)>0$ would mean that player $x$ would play
$s_{1}$, if her opponent chooses to play $s_{i}$, i.e., that $s_{1}$ is the
best response (for $x$) to $s_{i}$. Similarly, $\text{{ugain}}(x,i)<0$ would
mean that player $x$ would play $s_{2}$, if her opponent chooses to play
$s_{i}$, i.e., that $s_{2}$ is the best response (for $x$) to $s_{i}$.
Finally, when $\text{{ugain}}(x,i)=0$, then player $x$ is indifferent as to
whether to play $s_{1}$ or $s_{2}$, i.e., it has two pure best responses for
her opponent’s pure strategy $s_{i}$, indicating that the game is degenerate.

######  Example 1.2 (Running example).

From Example 1.1 we have that, for $G^{0}$, the following hold:
$\text{{ugain}}(r,1)=3$, $\text{{ugain}}(r,2)=-2$, $\text{{ugain}}(c,1)=2$,
and $\text{{ugain}}(c,2)=-3$.

Some well-known results from game theory for bimatrix games can be recast
using the concept of $\text{{ugain}}(x,i)$. For example, the following
proposition gives an equivalent formulation of the degeneracy criterion for
$2\times 2$ bimatrix games444Proofs for all results appear in the Appendix.:

######  Proposition 1.

A $2\times 2$ bimatrix game $G$ is degenerate if and only if
$\text{{ugain}}(x,i)=0$ for some $x\in\\{r,c\\},i\in\\{1,2\\}$.

When a non-degenerate $2\times 2$ bimatrix game has a mixed Nash equilibrium,
then its value is determined by $\text{{ugain}}(x,i)$:

######  Proposition 2.

Consider a non-degenerate $2\times 2$ bimatrix game $G=\langle N,S,P\rangle$,
for $P=(P_{r}\mathchar 24635\relax\;P_{c})$. If $(p,1-p)\in NE_{x}(G)$ for
some $0<p<1$, $x\in\\{r,c\\}$, then:

$p=\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}$

Now consider a non-degenerate $2\times 2$ bimatrix game $G$ and some player
$x\in\\{r,c\\}$. From classical results in game theory, we know that there are
4 possible cases for $NE_{x}(G)$, namely $NE_{x}(G)=\\{(1,0)\\}$,
$NE_{x}(G)=\\{(0,1)\\}$, $NE_{x}(G)=\\{(p,1-p)\\}$ for some $0<p<1$ and
$NE_{x}(G)=\\{(1,0),(0,1),(p,1-p)\\}$ for some $0<p<1$. If the game is
degenerate, then there is one additional possibility, namely that
$NE_{x}(G)=\\{(p,1-p)\mid 0\leq p\leq 1\\}=\Sigma_{x}$.

For non-degenerate games, the value of $NE_{x}(G)$ can be determined using the
following:

  * •

$NE_{x}(G)=\\{(1,0)\\}$ if and only if $s_{1}$ is dominant for $x$, or $s_{i}$
is dominant for $\bar{x}$ and $s_{1}$ is the best response for $x$ on $s_{i}$.

  * •

$NE_{x}(G)=\\{(0,1)\\}$ if and only if $s_{2}$ is dominant for $x$, or $s_{i}$
is dominant for $\bar{x}$ and $s_{2}$ is the best response for $x$ on $s_{i}$.

  * •

$NE_{x}(G)=\\{(p,1-p)\\}$ for some $0<p<1$ if and only if no strategy is
dominant for either player and no pure Nash equilibrium exists.

  * •

$NE_{x}(G)=\\{(1,0),(0,1),(p,1-p)\\}$ for some $0<p<1$ if and only if no
strategy is dominant for either player and two pure Nash equilibria exist.

The above conditions can also be expressed in terms of $\text{{ugain}}(x,i)$,
as shown in Table 1. In the table, the various (mutually exclusive) cases are
visualised for player $r$ and for a non-degenerate game. The small figure in
the rightmost column shows the depicted condition in terms of the relative
order among the elements of $P_{r}$ (blue lines) or $P_{c}$ (yellow lines),
which is determined by the sign (positive or negative) of
$\text{{ugain}}(x,i)$. The first column provides a reference to the
formulation of Proposition 3, where the above are formally stated and proved.

Before showing Proposition 3, for brevity, we introduce the following
predicates to refer to the different cases with regards to the value of
$NE_{x}(G)$:

  * •

_Only-pure_ : $\text{{op}}^{G}_{x}(i)$, which is true if and only if the only
equilibrium strategy for player $x$ in game $G$ is to play $s_{i}$, i.e.:

$\begin{split}&\text{{op}}^{G}_{x}(1)\text{ iff }NE_{x}(G)=\\{(1,0)\\}\text{
and }\text{{op}}^{G}_{x}(2)\text{ iff }NE_{x}(G)=\\{(0,1)\\}\end{split}$

  * •

_Only-mixed_ : $\text{{om}}^{G}_{x}(p)$, which is true if and only if the only
equilibrium strategy for player $x$ in game $G$ is $(p,1-p)$ (where $0<p<1$),
i.e.:

$\text{{om}}^{G}_{x}(p)\text{ iff }NE_{x}(G)=\\{(p,1-p)\\}$

  * •

_Pure-and-mixed_ : $\text{{pm}}^{G}_{x}(p)$, which is true if and only if
player $x$ has 3 equilibrium strategies in game $G$, two pure and one mixed,
and the mixed one is $(p,1-p)$ (where $0<p<1$), i.e.:

$\text{{pm}}^{G}_{x}(p)\text{ iff }NE_{x}(G)=\\{(1,0),(0,1),(p,1-p)\\}$

  * •

_Ranged-only-mixed_ : $\text{{rom}}^{G}_{x}(\omega_{1},\omega_{2})$, which is
true if and only if $\text{{om}}^{G}_{x}(p)$ is true for some
$\omega_{1}<p<\omega_{2}$, i.e.:

$\text{{rom}}^{G}_{x}(\omega_{1},\omega_{2})\text{ iff
}NE_{x}(G)=\\{(p,1-p)\\}\text{ for some }p\text{ such that
}\omega_{1}<p<\omega_{2}$

  * •

_Ranged-pure-and-mixed_ : $\text{{rpm}}^{G}_{x}(\omega_{1},\omega_{2})$, which
is true if and only if $\text{{pm}}^{G}_{x}(p)$ is true for some
$\omega_{1}<p<\omega_{2}$, i.e.:

$\begin{split}&\text{{rpm}}^{G}_{x}(\omega_{1},\omega_{2})\text{ iff
}NE_{x}(G)=\\{(1,0),(0,1),(p,1-p)\\}\text{ for some }p\text{ such that
}\omega_{1}<p<\omega_{2}\end{split}$

  * •

_Infinite-Nash_ : $\text{{in}}^{G}_{x}$, which is true if and only if player
$x$ has an infinite number of equilibrium strategies, namely the entire
$\Sigma_{x}$ (note that this is possible only for degenerate games), i.e.:

$\text{{in}}^{G}_{x}\text{ iff }NE_{x}(G)=\Sigma_{x}$

When the game $G$ is obvious from the context, we will omit the superscript
$G$ from the above. Now we can formally state Proposition 3, which formalises
the intuition of Table 1:

Table 1: Visualising the cases of Proposition 3, for $x=r$.

Case (from Value of $\text{{ugain}}(x,i)$, for: Nash equilibrium Schematic
Proposition $x=r$ $x=r$ $x=c$ $x=c$ strategies for $x=r$ depiction 3) $i=1$
$i=2$ $i=1$ $i=2$ ($NE_{r}(G)$) of the case (1a) ${>}0$ ${>}0$ ${<>}0$ ${<>}0$
$\\{{(1,0)}\\}$ $(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$ $>$$>$$<>$$<>$ (1b) ${>}0$
${<}0$ ${>}0$ ${>}0$ $\\{{(1,0)}\\}$ $(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$
$>$$<$$>$$>$ (1c) ${<}0$ ${>}0$ ${<}0$ ${<}0$ $\\{{(1,0)}\\}$ $(1,1)$ $(1,2)$
$(2,1)$ $(2,2)$ $<$$>$$<$$<$ (2a) ${<}0$ ${<}0$ ${<>}0$ ${<>}0$
$\\{{(0,1)}\\}$ $(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$ $<$$<$$<>$$<>$ (2b) ${<}0$
${>}0$ ${>}0$ ${>}0$ $\\{{(0,1)}\\}$ $(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$
$<$$>$$>$$>$ (2c) ${>}0$ ${<}0$ ${<}0$ ${<}0$ $\\{{(0,1)}\\}$ $(1,1)$ $(1,2)$
$(2,1)$ $(2,2)$ $>$$<$$<$$<$ (3a) ${>}0$ ${<}0$ ${<}0$ ${>}0$
$\\{{(p,1-p)}\\}$
${p=\frac{\text{{ugain}}(c,2)}{\text{{ugain}}(c,2)-\text{{ugain}}(c,1)}}$
$(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$ $>$$<$$<$$>$ (3b) ${<}0$ ${>}0$ ${>}0$ ${<}0$
$\\{{(p,1-p)}\\}$
${p=\frac{\text{{ugain}}(c,2)}{\text{{ugain}}(c,2)-\text{{ugain}}(c,1)}}$
$(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$ $<$$>$$>$$<$ (4a) ${>}0$ ${<}0$ ${>}0$ ${<}0$
$\\{{(1,0),(0,1),(p,1-p)}\\}$
${p=\frac{\text{{ugain}}(c,2)}{\text{{ugain}}(c,2)-\text{{ugain}}(c,1)}}$
$(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$ $>$$<$$>$$<$ (4b) ${<}0$ ${>}0$ ${<}0$ ${>}0$
$\\{{(1,0),(0,1),(p,1-p)}\\}$
${p=\frac{\text{{ugain}}(c,2)}{\text{{ugain}}(c,2)-\text{{ugain}}(c,1)}}$
$(1,1)$ $(1,2)$ $(2,1)$ $(2,2)$ $<$$>$$<$$>$

######  Proposition 3.

For any non-degenerate $2\times 2$ bimatrix game the following hold:

  1. 1.

$\text{{op}}_{x}(1)$ if and only if either one of the following is true:

    1. (a)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)>0)$

    2. (b)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)<0)\bigwedge(\text{{ugain}}(\bar{x},1)>0)\bigwedge(\text{{ugain}}(\bar{x},2)>0)$

    3. (c)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)>0)\bigwedge(\text{{ugain}}(\bar{x},1)<0)\bigwedge(\text{{ugain}}(\bar{x},2)<0)$

  2. 2.

$\text{{op}}_{x}(2)$ if and only if either one of the following is true:

    1. (a)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)<0)$

    2. (b)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)>0)\bigwedge(\text{{ugain}}(\bar{x},1)>0)\bigwedge(\text{{ugain}}(\bar{x},2)>0)$

    3. (c)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)<0)\bigwedge(\text{{ugain}}(\bar{x},1)<0)\bigwedge(\text{{ugain}}(\bar{x},2)<0)$

  3. 3.

$\text{{om}}_{x}(p)$ if and only if
$p=\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}$
and either one of the following is true:

    1. (a)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)<0)\bigwedge(\text{{ugain}}(\bar{x},1)<0)\bigwedge(\text{{ugain}}(\bar{x},2)>0)$

    2. (b)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)>0)\bigwedge(\text{{ugain}}(\bar{x},1)>0)\bigwedge(\text{{ugain}}(\bar{x},2)<0)$

  4. 4.

$\text{{pm}}_{x}(p)$ if and only if
$p=\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}$
and either one of the following is true:

    1. (a)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)<0)\bigwedge(\text{{ugain}}(\bar{x},1)>0)\bigwedge(\text{{ugain}}(\bar{x},2)<0)$

    2. (b)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)>0)\bigwedge\text{{ugain}}(\bar{x},1)<0)\bigwedge(\text{{ugain}}(\bar{x},2)>0)$

An analogous set of conditions determines whether the “ranged” versions of the
above predicates are true:

######  Corollary 1.

Given a non-degenerate $2\times 2$ bimatrix game $G$, the following hold:

  1. 1.

$\text{{rom}}_{x}(\omega_{1},\omega_{2})$ if and only if
$\omega_{1}<\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}<\omega_{2}$
and either one of the following is true:

    1. (a)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)<0)\bigwedge(\text{{ugain}}(\bar{x},1)<0)\bigwedge(\text{{ugain}}(\bar{x},2)>0)$

    2. (b)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)>0)\bigwedge(\text{{ugain}}(\bar{x},1)>0)\bigwedge(\text{{ugain}}(\bar{x},2)<0)$

  2. 2.

$\text{{rpm}}_{x}(\omega_{1},\omega_{2})$ if and only if
$\omega_{1}<\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}<\omega_{2}$
and either one of the following is true:

    1. (a)

$(\text{{ugain}}(x,1)>0)\bigwedge(\text{{ugain}}(x,2)<0)\bigwedge(\text{{ugain}}(\bar{x},1)>0)\bigwedge(\text{{ugain}}(\bar{x},2)<0)$

    2. (b)

$(\text{{ugain}}(x,1)<0)\bigwedge(\text{{ugain}}(x,2)>0)\bigwedge(\text{{ugain}}(\bar{x},1)<0)\bigwedge(\text{{ugain}}(\bar{x},2)>0)$

######  Example 1.3 (Running example).

Continuing Example 1.1, we note that the signs of the various
$\text{{ugain}}(x,i)$ (as computed in Example 1.2) indicate that case (4a) of
Table 1 holds. Thus, the actual game $G^{0}$ has both pure and mixed Nash
equilibria. Given that
$\frac{\text{{ugain}}(c,2)}{\text{{ugain}}(c,2)-\text{{ugain}}(c,1)}=0.6$, it
follows that $\text{{pm}}_{r}(0.6)$ is true. Analogously, since
$\frac{\text{{ugain}}(r,2)}{\text{{ugain}}(r,2)-\text{{ugain}}(r,1)}=0.4$, it
follows that $\text{{pm}}_{c}(0.4)$ is true.

###  5.2 Misinformation Games

In this subsection, we provide necessary and sufficient conditions for a
misinformation game to be _(inverse-) $\varepsilon$-misinformed_. These are
given in Propositions 4, 5, and use the notation previously introduced. Note
that the propositions apply for all canonical misinformation games, not just
noisy games. The results of this subsection are summarized in Table 2.

######  Proposition 4.

Consider a canonical misinformation game $mG=\langle
G^{0},G^{r},G^{c}\rangle$, where $G^{0}$ is a $2\times 2$ bimatrix game and
$G^{r},G^{c}$ are non-degenerate. Then, $mG$ is $\varepsilon$-misinformed if
and only if, for all $x\in\\{r,c\\}$, one of the following is true:

  1. 1.

$\text{{op}}^{G^{0}}_{x}(i)$ and $\text{{op}}^{G^{x}}_{x}(i)$ for some
$i\in\\{1,2\\}$

  2. 2.

$\text{{om}}^{G^{0}}_{x}(p^{0})$ for some $0<p^{0}<1$ and
$\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$, where
$\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$

  3. 3.

$\text{{pm}}^{G^{0}}_{x}(p^{0})$ for some $0<p^{0}<1$ and
$\text{{op}}^{G^{x}}_{x}(1)\bigvee\text{{op}}^{G^{x}}_{x}(2)\bigvee\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\bigvee\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$,
where $\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$

  4. 4.

$\text{{in}}^{G^{0}}_{x}$

######  Proposition 5.

Consider a canonical misinformation game $mG=\langle
G^{0},G^{r},G^{c}\rangle$, where $G^{0}$ is a $2\times 2$ bimatrix game and
$G^{r},G^{c}$ are non-degenerate. Then, $mG$ is
inverse-$\varepsilon$-misinformed if and only if, for all $x\in\\{r,c\\}$, one
of the following is true:

  1. 1.

$\text{{op}}^{G^{0}}_{x}(i)$ and
$\text{{op}}^{G^{x}}_{x}(i)\bigvee\text{{rpm}}^{G^{x}}_{x}(0,1)$ for some
$i\in\\{1,2\\}$

  2. 2.

$\text{{om}}^{G^{0}}_{x}(p^{0})$ for some $0<p^{0}<1$ and
$\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\bigvee\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$,
where $\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$

  3. 3.

$\text{{pm}}^{G^{0}}_{x}(p^{0})$ for some $0<p^{0}<1$ and
$\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$, where
$\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$

  4. 4.

$\text{{in}}^{G^{0}}_{x}$ and $\varepsilon>0.5$ and
$\text{{rpm}}^{G^{x}}_{x}(\omega_{1}^{\prime},\omega_{2}^{\prime})$, where
$\omega_{1}^{\prime}=\max\\{0,1-\varepsilon\\}$,
$\omega_{2}^{\prime}=\min\\{1,\varepsilon\\}$

Table 2: Scenarios for $\varepsilon$-misinformed and inverse-$\varepsilon$-misinformed Condition on $G^{0}$ | Condition on $G^{x}$
---|---
|  For $\varepsilon$-misinformed |  For inverse-$\varepsilon$-misinformed
$\text{{op}}^{G^{0}}_{x}(i)$ |  $\text{{op}}^{G^{x}}_{x}(i)$ |  $\text{{op}}^{G^{x}}_{x}(i)$ $\bigvee$
$\text{{rpm}}^{G^{x}}_{x}(0,1)$
$\text{{om}}^{G^{0}}_{x}(p^{0})$ |  $\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ |  $\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ $\bigvee$
$\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$
$\text{{pm}}^{G^{0}}_{x}(p^{0})$ |  $\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ $\bigvee$
$\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ $\bigvee$
$\text{{op}}^{G^{x}}_{x}(1)$ $\bigvee$
$\text{{op}}^{G^{x}}_{x}(2)$ |  $\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$
$\text{{in}}^{G^{0}}_{x}$ |  Always true |  If $\varepsilon<0.5$: always false
If $\varepsilon\geq 0.5$:
$\text{{rpm}}^{G^{x}}_{x}(\omega_{1}^{\prime},\omega_{2}^{\prime})$
In all the above:
$0<p^{0}<1$,
$\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$,
$\omega_{1}^{\prime}=\max\\{0,1-\varepsilon\\}$,
$\omega_{2}^{\prime}=\min\\{1,\varepsilon\\}$

###  5.3 Probabilities

We will now exploit the results of the previous subsections, in order to
compute the probabilities associated to various events, eventually leading up
to the computation that a given normal noisy game $mG$ is
(inverse-)$\varepsilon$-misinformed. The results are summarized in Table 5,
whereas intermediate results necessary to compute the above probabilities
appear in Tables 3 and 4.

For a normal noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, we
define the family of random variables $U(y,x,i)$, such that, for any
$x,y\in\\{r,c\\},i\in\\{1,2\\}$:

$U(y,x,i)=\text{{ugain}}^{G^{y}}(x,i)$

Applying formula (3) from Subsection 3.1, we observe that
$U(y,x,i)\sim{\mathcal{N}}\left(\mu_{U(y,x,i)},d_{U(y,x,i)}\right)$ for
$\mu_{U(y,x,i)},d_{U(y,x,i)}$ as shown in Table 3. The cdf and pdf of
$U(y,x,i)$ (as resulting from formula (2) in Subsection 3.1), as well as the
probabilities for $U(y,x,i)$ taking certain values are also shown in the same
table.

######  Example 1.4 (Running example).

Continuing our running example (Example 1.1), we can now compute the
distribution followed by the random variables $U(y,x,i)$ for
$x,y\in\\{r,c\\}$, $i\in\\{1,2\\}$, using Table 3. Indeed, by Table 3,
$\mu_{U(y,x,i)}=\text{{ugain}}(x,i)$ and $d_{U(y,x,i)}=\sqrt{2}$ for all
$x,y\in\\{r,c\\}$, $i\in\\{1,2\\}$.
As a more specific example, let us consider $U(r,r,1)$, which corresponds to
the random variable representing the utility gain of strategy $s_{1}$ (as
opposed to $s_{2}$), for player $r$ under the viewpoint of player $r$. By
Table 3, and the values for $M,D$ (Example 1.1), we conclude that
$\mu_{U(r,r,1)}=3$, $d_{U(r,r,1)}=\sqrt{2}$. Analogously, we can compute the
rest.From this, and formulas 2 in subsection 3.1, we get that the pdf and cdf
of $U(r,r,1)$ are:

$\displaystyle
f_{U(r,r,1)}(x)=\tfrac{1}{2\sqrt{\pi}}e^{-\left(\tfrac{x-3}{2}\right)^{2}}\quad\text{
and }\quad
F_{U(r,r,1)}(x)=\tfrac{1}{\sqrt{2\pi}}\int^{\tfrac{x-3}{\sqrt{2}}}_{-\infty}e^{-\frac{t^{2}}{2}}dt$

Table 3: Formulas related to $U(y,x,i)$ for a given $mG\sim
G^{0}+{\mathcal{N}}\left(M,D\right)$. Results related to $U(y,x,i)$
---
μ$U(y,r,i)$=(P0r[1,i] + Myr[1,i]) - (P0r[2,i] + Myr[2,i])
$d$$U(y,r,i)$=($D$yr[1,i])2\+ ($D$yr[2,i])2μ$U(y,c,i)$=(P0c[i,1] + Myc[i,1]) -
(P0c[i,2] + Myc[i,2]) $d$$U(y,c,i)$=($D$yc[i,1])2\+
($D$yc[i,2])2f$U(y,x,i)$(u)
=1$d$$U(y,x,i)$ϕ(u-μ$U(y,x,i)$$d$$U(y,x,i)$)F$U(y,x,i)$(u)
=Φ(u-μ$U(y,x,i)$$d$$U(y,x,i)$)${\mathcal{P}}\boldsymbol{\left[\right.}U(y,x,i)<0\boldsymbol{\left.\right]}$
=F$U(y,x,i)$(0)
${\mathcal{P}}\boldsymbol{\left[\right.}U(y,x,i)>0\boldsymbol{\left.\right]}$
=1 - F$U(y,x,i)$(0)
${\mathcal{P}}\boldsymbol{\left[\right.}U(y,x,i)=0\boldsymbol{\left.\right]}$
=0

Propositions 1 and 3 can now be employed to determine the probability that
$NE_{x}(G^{x})$ takes a certain value, based on the probabilities that
$U(y,x,i)$ take certain values. More precisely, Lemma 6 is the counterpart of
Proposition 1:

######  Proposition 6.

In any normal noisy game $mG=\langle G^{0},G^{r},G^{c}\rangle$, the
probability that $G^{x}$ is degenerate (for $x\in\\{r,c\\}$) is $0$.

To formulate the counterpart of Proposition 3, the following lemma will prove
helpful:

######  Lemma 1.

Consider two independent random variables
$X\sim{\mathcal{N}}\left(\mu_{X},d_{X}\right),Y\sim{\mathcal{N}}\left(\mu_{Y},d_{Y}\right)$,
with pdfs $f_{X},f_{Y}$ respectively, and some
$\Omega_{1},\Omega_{2}\in\mathbb{R}\cup\\{-\infty\\}$ such that
$-\infty\leq\Omega_{1}<\Omega_{2}\leq 0$. Then:

$\begin{split}&{\mathcal{P}}\boldsymbol{\left[\right.}\Omega_{1}\leq\frac{X}{Y}\leq\Omega_{2},X<0,Y>0\boldsymbol{\left.\right]}=\int_{0}^{+\infty}\left(\int_{\Omega_{1}y}^{\Omega_{2}y}\\!f_{X}(x)\,\mathrm{d}x\right)\frac{f_{Y}(y)}{y}\,\mathrm{d}y\\\
&{\mathcal{P}}\boldsymbol{\left[\right.}\Omega_{1}\leq\frac{X}{Y}\leq\Omega_{2},X>0,Y<0\boldsymbol{\left.\right]}=\int_{-\infty}^{0}\left(\int_{\Omega_{1}y}^{\Omega_{2}y}\\!f_{X}(x)\,\mathrm{d}x\right)\frac{f_{Y}(y)}{y}\,\mathrm{d}y\\\
\end{split}$

Table 4: Various probabilities pertaining to a given $mG\sim
G^{0}+{\mathcal{N}}\left(M,D\right)$ (see also Proposition 7). Results related
to $NE_{x}(G^{x})$ (Proposition 7)
---
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(1)\boldsymbol{\left.\right]}$
=(1 - F$U(x,x,1)$(0)) ⋅(1 - F$U(x,x,2)$(0)) + (1 - F$U(x,x,1)$(0))
⋅F$U(x,x,2)$(0) ⋅(1 - F$U(x,\bar{x},1)$(0)) ⋅(1 - F$U(x,\bar{x},2)$(0)) +
F$U(x,x,1)$(0) ⋅(1 - F$U(x,x,2)$(0)) ⋅F$U(x,\bar{x},1)$(0)
⋅F$U(x,\bar{x},2)$(0)
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(2)\boldsymbol{\left.\right]}$
=F$U(x,x,1)$(0) ⋅F$U(x,x,2)$(0) + F$U(x,x,1)$(0) ⋅(1 - F$U(x,x,2)$(0)) ⋅(1 -
F$U(x,\bar{x},1)$(0)) ⋅(1 - F$U(x,\bar{x},2)$(0)) + (1 - F$U(x,x,1)$(0))
⋅F$U(x,x,2)$(0) ⋅F$U(x,\bar{x},1)$(0) ⋅F$U(x,\bar{x},2)$(0)
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$
=(1 - F$U(x,x,1)$(0)) ⋅F$U(x,x,2)$(0) ⋅∫0+∞(∫ω1\- 1ω1u2ω2\- 1ω2u2
f$U(x,\bar{x},1)$(u1) du1)f$U(x,\bar{x},2)$(u2)u2du2\+ F$U(x,x,1)$(0) ⋅(1 -
F$U(x,x,2)$(0)) ⋅∫-∞0(∫ω1\- 1ω1u2ω2\- 1ω2u2 f$U(x,\bar{x},1)$(u1)
du1)f$U(x,\bar{x},2)$(u2)u2du2${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$
=(1 - F$U(x,x,1)$(0)) ⋅F$U(x,x,2)$(0) ⋅∫-∞0(∫ω1\- 1ω1u2ω2\- 1ω2u2
f$U(x,\bar{x},1)$(u1) du1)f$U(x,\bar{x},2)$(u2)u2du2\+ F$U(x,x,1)$(0) ⋅(1 -
F$U(x,x,2)$(0)) ⋅∫0+∞(∫ω1\- 1ω1u2ω2\- 1ω2u2 f$U(x,\bar{x},1)$(u1)
du1)f$U(x,\bar{x},2)$(u2)u2du2${\mathcal{P}}\boldsymbol{\left[\right.}\text{{in}}^{G^{x}}_{x}\boldsymbol{\left.\right]}$
=0

The next proposition determines the probability that $NE_{x}(G^{x})$ will have
each of its possible values (see also Table 4):

######  Proposition 7.

Consider a normal noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, and
some $x\in\\{r,c\\}$. Then, the probabilities
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(1)\boldsymbol{\left.\right]}$,
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(2)\boldsymbol{\left.\right]}$,
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$,
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$
and
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{in}}^{G^{x}}_{x}\boldsymbol{\left.\right]}$
are as shown in Table 4.

Table 5: Probabilities for $\varepsilon$-misinformed and
inverse-$\varepsilon$-misinformed
($\mathcal{P}_{r}^{mis}\cdot\mathcal{P}_{c}^{mis}$ and
$\mathcal{P}_{r}^{inv}\cdot\mathcal{P}_{c}^{inv}$ respectively – see also
Theorems 8, 9). Condition on $G^{0}$
(value of $NE_{x}(G^{0})$) |  Probability $\mathcal{P}_{x}^{mis}$ ($x\in\\{r,c\\}$) for $\varepsilon$-misinformed
(Theorem 8) |  Probability $\mathcal{P}_{x}^{inv}$ ($x\in\\{r,c\\}$) for inverse-$\varepsilon$-misinformed
(Theorem 9)
---|---|---
$\text{{op}}^{G^{0}}_{x}(i)$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}$ $+$ ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$
$\text{{om}}^{G^{0}}_{x}(p^{0})$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$ $+$
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$
$\text{{pm}}^{G^{0}}_{x}(p^{0})$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$ $+$
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$
$+$
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(1)\boldsymbol{\left.\right]}$
$+$
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(2)\boldsymbol{\left.\right]}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$
$\text{{in}}^{G^{0}}_{x}$ |  1 |  If $\varepsilon\leq 0.5$: 0
If $\varepsilon>0.5$:
${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1}^{\prime},\omega_{2}^{\prime})\boldsymbol{\left.\right]}$
In all the above:
$i\in\\{1,2\\}$, $0<p^{0}<1$,
$\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$,
$\omega_{1}^{\prime}=\max\\{0,1-\varepsilon\\}$,
$\omega_{2}^{\prime}=\min\\{1,\varepsilon\\}$

######  Example 1.5 (Running example).

Continuing Example 1.1, we can now compute the probabilities that each of the
robotic agents will believe that they play a game with pure, mixed or pure and
mixed strategies. We start with the computation of the relevant
$F_{U(y,x,i)}(0)$ quantities for $x,y\in\\{r,c\\}$, $i\in\\{1,2\\}$, which are
based on the respective pdf/cdf that were computed in Example 1.4:

  * •

For the $r$ agent:

    * $F_{U(r,r,1)}(0)=0.017$, $F_{U(r,r,2)}(0)=0.921$, $F_{U(r,c,1)}(0)=0.078$, $F_{U(r,c,2)}(0)=0.983$

  * •

For the $c$ agent:

    * $F_{U(c,c,1)}(0)=0.078$, $F_{U(c,c,2)}(0)=0.983$, $F_{U(c,r,1)}(0)=0.921$, $F_{U(c,r,2)}(0)=0.016$

Regarding the two double integrals in the third and fourth formulas in Table 4
our computations yield the values $0.001$ and $0.229$ for $r$ respectively.
Similarly, for $c$ we take the values $0.001$ and $0.189$.

Using the above results it is now easy to compute the following quantities,
using the formulas of Table 4:

  * •

For the $r$ agent:

    * ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{r}}_{r}(1)\boldsymbol{\left.\right]}=0.091$, ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{r}}_{r}(2)\boldsymbol{\left.\right]}=0.085$, ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{r}}_{r}(0.5,0.7)\boldsymbol{\left.\right]}=0.001$, ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{r}}_{r}(0.5,0.7)\boldsymbol{\left.\right]}=0.207$

  * •

For the $c$ agent:

    * ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{c}}_{c}(1)\boldsymbol{\left.\right]}=0.091$, ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{c}}_{c}(2)\boldsymbol{\left.\right]}=0.085$, ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{c}}_{c}(0.3,0.5)\boldsymbol{\left.\right]}=0.001$, ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{c}}_{c}(0.3,0.5)\boldsymbol{\left.\right]}=0.171$

Not unexpectedly, the largest probability is that the agents retain the
behaviour predicted by the original game (i.e., playing pure and mixed), but
not significantly so.

Proposition 7 (and the respective Table 4), combined with Proposition 4 (and
the respective Table 2) easily leads to the following theorems (summarized in
Table 5):

######  Theorem 8.

Consider a normal noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$.
Then:

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}=\mathcal{P}_{r}^{mis}\cdot\mathcal{P}_{c}^{mis}$

where, for $x\in\\{r,c\\}$, $\mathcal{P}_{x}^{mis}$ is determined by the
second column of Table 5.

######  Theorem 9.

Consider a normal noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$.
Then:

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}=\mathcal{P}_{r}^{inv}\cdot\mathcal{P}_{c}^{inv}$

where, for $x\in\\{r,c\\}$, $\mathcal{P}_{x}^{inv}$ is determined by the third
column of Table 5.

######  Example 1.6 (Running example).

Returning to our running example (Example 1.1), let us now compute the
probability for the respective noisy game to be (inverse-)$\varepsilon$\-
misinformed, for $\varepsilon=0.1$. To do so, we plug in the formulas from
Table 5 into Theorems 8-9, and, using the previously computed probabilities
from Example 1.5, we take:

  * $\mathcal{P}_{r}^{mis}=0.386$, $\mathcal{P}_{r}^{inv}=0.207$, $\mathcal{P}_{c}^{mis}=0.349$, $\mathcal{P}_{c}^{inv}=0.171$

Thus,

  * ${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar 58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}=0.135$

  * ${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar 58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}=0.035$.

Thus, the conclusion of this analysis is that, the “Battle of the Sexes” (BoS)
game, when receiving noise that follows the standard normal distribution
(${\mathcal{N}}\left(0,1\right)$) in each of its payoffs and for each player,
will be $0.1$-misinformed with probability $13.5\%$ and
inverse-$0.1$-misinformed with probability $3.5\%$.

Note that the original BoS game has 3 Nash equilibria, two pure and one mixed.
Thus, the above results imply that, by defining closeness using
$\varepsilon=0.1$:

  * •

With probability $13.5\%$, all (misinformed) equilibrium points of the noisy
game will be close to one of the expected equilibria (in BoS). Thus, under
this probability, the agents will have one or more natural misinformed
equilibria, all of which will be close to one of the BoS’ Nash equilibria.
This means that, with probability $13.5\%$, the agents’ behaviour (no matter
which of their equilibrium points they choose) will be close to the expected
one.

  * •

With probability $3.5\%$, for each of the three equilibria of BoS, there will
be at least one (misinformed) equilibrium point that is close to it. Thus,
under this probability, there will be at least 3 natural misinformed
equilibria, although the agents may also have other (misinformed) equilibria
as well that are not close to any Nash equilibrium of BoS. This means that,
with probability $3.5\%$, all equilibria of BoS are within the valid options
(modulo the closeness assumption) for the agents.

##  6 Results for noisy games

The results of Section 5 provide the formulas to compute the probability of a
given normal noisy game to be (inverse-)$\varepsilon$-misinformed (i.e.,
behaviourally consistent). In this section, we explore the properties of these
formulas, to understand better their behaviour.

To do so, we first observe that the probability of a normal noisy game $mG\sim
G^{0}+{\mathcal{N}}\left(M,D\right)$ being behaviourally consistent is
essentially a function of:

  * •

The tolerance $\varepsilon$.

  * •

The payoff matrix of the actual game of $mG$. This affects the probabilities
in two ways: first, because it determines the equilibria of $G^{0}$, and,
thus, the case to consider in Table 5; second, because it affects
$\mu_{U(y,x,i)}$ (see Table 3).

  * •

The noise pattern, determined by the matrices $M,D$.

In the following subsections, we study the effect of each of these parameters
on the probability of $mG$ being (inverse-)$\varepsilon$-misinformed.

###  6.1 Effect of modifying tolerance ($\varepsilon$)

With regards to tolerance ($\varepsilon$), we expect that larger values of
tolerance would translate to higher probability of behavioural consistency.
Although this is true, we also observe that there are several cases where
increasing tolerance does not affect the probability of behavioural
consistency. The following proposition clarifies the situation:

Table 6: Effect of tolerance on behavioural consistency (monotonicity).  Condition on $G^{0}$ | Monotonicity properties
---|---
(value of $NE(G^{0})$) |  For $\varepsilon$-misinformed |  For inverse-$\varepsilon$-misinformed
$\text{{op}}^{G^{0}}_{r}(i)\wedge\text{{op}}^{G^{0}}_{c}(j)$ for some
$i,j\in\\{1.2\\}$ |  Constant for all $\varepsilon\geq 0$
$\text{{om}}^{G^{0}}_{r}(p^{0})\wedge\text{{om}}^{G^{0}}_{c}(q^{0})$ for some
$0<p^{0}<1,0<q^{0}<1$ |  Strictly increasing for $0\leq\varepsilon\leq\max\\{p^{0},q^{0},1-p^{0},1-q^{0}\\}$,
constant otherwise
$\text{{pm}}^{G^{0}}_{r}(p^{0})\wedge\text{{pm}}^{G^{0}}_{c}(q^{0})$ for some
$0<p^{0}<1,0<q^{0}<1$ |  Strictly increasing for $0\leq\varepsilon\leq\max\\{p^{0},q^{0},1-p^{0},1-q^{0}\\}$,
constant otherwise
$\text{{in}}^{G^{0}}_{r}\vee\text{{in}}^{G^{0}}_{c}$ |  Constant for all $\varepsilon\geq 0$ |  Strictly increasing for $0.5\leq\varepsilon\leq 1$, constant otherwise

######  Proposition 10.

Consider some $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$ and
$\varepsilon_{1},\varepsilon_{2}$, such that
$0\leq\varepsilon_{1}<\varepsilon_{2}$. Then:

  1. 1.

If $NE(G^{0})$ contains a single pure strategy, then:

     * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

     * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

  2. 2.

If $NE(G^{0})$ is finite and $((p^{0},1-p^{0}),(q^{0},1-q^{0}))\in NE(G^{0})$
for some $0<p^{0}<1$, $0<q^{0}<1$, then:

    1. (a)

If $\max\\{p^{0},q^{0},1-p^{0},1-q^{0}\\}\leq\varepsilon_{1}$, then:

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

    2. (b)

If $\max\\{p^{0},q^{0},1-p^{0},1-q^{0}\\}>\varepsilon_{1}$, then:

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}<{\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}<{\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

  3. 3.

If $NE(G^{0})$ is infinite, then:

    1. (a)

If $\varepsilon_{1}\geq 1$ or $\varepsilon_{2}\leq 0.5$, then:

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

    2. (b)

If $\varepsilon_{1}<1$ and $\varepsilon_{2}>0.5$, then:

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

       * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{1}\text{-misinformed}\boldsymbol{\left.\right]}<{\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon_{2}\text{-misinformed}\boldsymbol{\left.\right]}$

Table 7: Minimal and maximal values for the probabilities of $mG$ being
(inverse-)$\varepsilon$-misinformed (resulting by multiplying
$\mathcal{P}_{r}^{mis}$ with $\mathcal{P}_{c}^{mis}$ and
$\mathcal{P}_{r}^{inv}$ with $\mathcal{P}_{c}^{inv}$ respectively)

Condition on $G^{0}$
(value of $NE_{x}(G^{0})$) |  Minimal value for probability
$P_{x}$ ($x\in\\{r,c\\}$) for $\varepsilon$-misinformed |  Minimal value for probability
$P_{x}$ ($x\in\\{r,c\\}$) for inverse-$\varepsilon$-misinformed
---|---|---
$\text{{op}}^{G^{0}}_{x}(i)$ for some
$i\in\\{1,2\\}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}$ $+$ ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$
$\text{{om}}^{G^{0}}_{x}(p^{0})$ for some
$0<p^{0}<1$ |  $0$ |  $0$
$\text{{pm}}^{G^{0}}_{x}(p^{0})$ for some
$0<p^{0}<1$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(1)\boldsymbol{\left.\right]}$ $+$ ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(2)\boldsymbol{\left.\right]}$ |  $0$
$\text{{in}}^{G^{0}}_{x}$ |  $1$ |  $0$
(a) Minimal values

Condition on $G^{0}$
(value of $NE_{x}(G^{0})$) |  Maximal value for probability
$P_{x}$ ($x\in\\{r,c\\}$) for $\varepsilon$-misinformed |  Maximal value for probability
$P_{x}$ ($x\in\\{r,c\\}$) for inverse-$\varepsilon$-misinformed
---|---|---
$\text{{op}}^{G^{0}}_{x}(i)$ for some
$i\in\\{1,2\\}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}$ $+$ ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$
$\text{{om}}^{G^{0}}_{x}(p^{0})$
for some
$0<p^{0}<1$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$ $+$ ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$
$\text{{pm}}^{G^{0}}_{x}(p^{0})$ for some
$0<p^{0}<1$ |  $1$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$
$\text{{in}}^{G^{0}}_{x}$ |  $1$ |  ${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(0,1)\boldsymbol{\left.\right]}$
(b) Maximal values

Proposition 10 has several interesting consequences. First, we note that the
probability for a given $mG$ to be (inverse-)$\varepsilon$-misinformed is non-
decreasing with respect to $\varepsilon$. When there is a pure Nash
equilibrium, the choice of $\varepsilon$ is irrelevant to the value of these
probabilities. When there is a mixed Nash equilibrium (case 2 of the
proposition), there is a limit above which $\varepsilon$ does not affect the
value of the related probability; this limit depends on the actual mixed
equilibrium, but it is always equal to, or larger than $0.5$, and smaller than
$1$. Finally, in the case where there is an infinite number of equilibria,
$\varepsilon$ affects the probabilities only for certain values (between $0.5$
and $1$, and only for the inverse-$\varepsilon$-misinformed case), as detailed
in case 3 of Proposition 10. These are summarised in Table 6.

Our results (and Table 6) indicate that the minimal value for the probability
of $mG$ being (inverse-)$\varepsilon$-misinformed is given for
$\varepsilon=0$. Its maximal value is taken for an appropriate $\varepsilon$
(depending on the case); in all cases $\varepsilon=1$ would also give that
maximal value. These maximal/minimal values can be easily deduced by Table 5
for the above choices of $\varepsilon$, and are given in Table 7 for
convenience. Note that the actual result for the minimal/maximal values
results by multiplying $\mathcal{P}_{r}^{mis}$ with $\mathcal{P}_{r}^{mis}$,
and $\mathcal{P}_{r}^{inv}$ with $\mathcal{P}_{r}^{inv}$ for
$\varepsilon$-misinformed and inverse-$\varepsilon$-misinformed respectively.

Another important result (albeit relatively obvious) is that the probability
of $mG$ being (inverse-)$\varepsilon$-misinformed, viewed as a function of
$\varepsilon$, is continuous. This is a direct consequence of the results in
Tables 3, 4, 5. An important consequence of this fact, by well-known results
of calculus, is that, for any given target value for the probabilities of
(inverse-)$\varepsilon$-misinformed (within the bounds shown in Table 7),
there exists some $\varepsilon$ whose application would result to that value
for the respective probability.

###  6.2 Effect of changing the game ($G^{0}$) and the mean ($M$)

Consider a misinformation game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$,
and let us informally ponder on the effect of bias in the noise of a game. A
biased noise is noise whose mean $M$ is non-zero, i.e.,
$M\neq\boldsymbol{[0]}$. Let us consider only player $r$, for simplicity. In
such a scenario, we know that $G^{r}\sim
G^{0}+{\mathcal{N}}\left(M^{r},D^{r}\right)$. Observe that this is the same as
writing
$G^{r}\sim(G^{0}+M^{r})+{\mathcal{N}}\left(\boldsymbol{[0]},D^{r}\right)$.
Using this simple reasoning, the computation of the probabilities of
behavioural consistency for $mG$ for biased noise can be reduced to
computations related to some $\overline{mG}$ with unbiased noise
($M=\boldsymbol{[0]}$), whose actual game will be the sum of $G^{0}$ and
$M^{x}$.

However, there are two caveats here. First, since $M^{r}$ may be different
than $M^{c}$, our original misinformation game is essentially reduced to two
different misinformation games (say $\overline{mG_{r}},\overline{mG_{c}}$),
i.e., one per player. Second, in the case where the equilibria of $G^{0}$ are
different than the equilibria of $G^{0}+M^{x}$, care should be taken to
consult the proper line in Table 5 while computing the probability of $mG$
being (inverse-)$\varepsilon$-misinformed. In particular, the line to consider
should be the one related to the equilibria of $G^{0}$, not $G^{0}+M^{x}$.
This means that the probability of $mG$ being
(inverse-)$\varepsilon$-misinformed may not be the same as the respective
probability for $\overline{mG_{r}},\overline{mG_{c}}$.

To prove the above ideas formally, we start with the following proposition:

######  Proposition 11.

Consider two noisy games $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$,
$\overline{mG}\sim\overline{G^{0}}+{\mathcal{N}}\left(\overline{M},D\right)$.
Suppose that there exists $a\in\mathbb{R}$, $x\in\\{r,c\\}$ such that
$G^{0}+M^{x}=\overline{G^{0}}+\overline{M^{x}}+\boldsymbol{[a]}$. Then:

  * •

For any $i\in\\{1,2\\}$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{\overline{G^{x}}}_{x}(i)\boldsymbol{\left.\right]}$

  * •

For any $0\leq\omega_{1}\leq\omega_{2}\leq 1$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{\overline{G^{x}}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$

  * •

For any $0\leq\omega_{1}\leq\omega_{2}\leq 1$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{\overline{G^{x}}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$

Proposition 11 implies that, given a noisy game $mG\sim
G^{0}+{\mathcal{N}}\left(M,D\right)$ and a player $x\in\\{r,c\\}$, we can
generate some other noisy game (say $\overline{mG}$), whose probabilities
related to the various outcomes (equilibria) of the game $\overline{G^{x}}$ of
$\overline{mG}$ are identical to the respective ones for $G^{x}$ (in $mG$). As
a matter of fact, there is an infinite number of noisy games that satisfy this
property: for any given $\overline{G^{0}}$ we can find an infinite number of
$\overline{M}$ that do this, and for any given $\overline{M}$ we can find an
infinite number of $\overline{G^{0}}$ that do this. This observation motivates
us to consider some interesting special cases, formalised as corollaries
below.

The first interesting case is when $\overline{M}=\boldsymbol{[0]}$. Given a
noisy game $mG$, the following corollary shows that the probabilities related
to the various outcomes (equilibria) of the game $G^{x}$ in $mG$ can be
predicted by looking at a properly defined noisy game $\overline{mG}$ where
the noise is unbiased (i.e., $\overline{M}=\boldsymbol{[0]}$). Formally:

######  Corollary 2.

Consider a noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, and some
$x\in\\{r,c\\}$. Set $\overline{G^{0}}=G^{0}+M^{x}$, and
$\overline{mG}\sim\overline{G^{0}}+{\mathcal{N}}\left(\boldsymbol{[0]},D\right)$.
Then:

  * •

For any $i\in\\{1,2\\}$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{\overline{G^{x}}}_{x}(i)\boldsymbol{\left.\right]}$

  * •

For any $0\leq\omega_{1}\leq\omega_{2}\leq 1$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{\overline{G^{x}}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$

  * •

For any $0\leq\omega_{1}\leq\omega_{2}\leq 1$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{\overline{G^{x}}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$

Combining Corollary 2 with Theorems 8, 9, it is easy to compute the
probability that $mG$ is (inverse-)$\varepsilon$-misinformed, using the
respective probabilities for $\overline{mG}$. This is one of the main results
of this subsection, as it allows us to restrict our study to noisy games with
unbiased noise only.

An interesting observation is that Corollary 2 applies for some
$x\in\\{r,c\\}$. Thus, we need to define two different $\overline{mG}$ (one
for each player $x\in\\{r,c\\}$) in order to compute the probability that $mG$
is (inverse-)$\varepsilon$-misinformed. The following corollary holds for both
$x\in\\{r,c\\}$ (and thus foregoes this need), but applies only when
$M^{r}=M^{c}$, i.e., when the noise received by the two players has the same
bias:

######  Corollary 3.

Consider a noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, where
$M=(M^{*}\mathchar 24635\relax\;M^{*})$. Set $\overline{G^{0}}=G^{0}+M^{*}$,
and
$\overline{mG}\sim\overline{G^{0}}+{\mathcal{N}}\left(\boldsymbol{[0]},D\right)$.
Then:

  * •

For any $i\in\\{1,2\\}$ and $x\in\\{r,c\\}$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{G^{x}}_{x}(i)\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{op}}^{\overline{G^{x}}}_{x}(i)\boldsymbol{\left.\right]}$

  * •

For any $0\leq\omega_{1}\leq\omega_{2}\leq 1$ and $x\in\\{r,c\\}$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{rom}}^{\overline{G^{x}}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$

  * •

For any $0\leq\omega_{1}\leq\omega_{2}\leq 1$ and $x\in\\{r,c\\}$,

${\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\text{{rpm}}^{\overline{G^{x}}}_{x}(\omega_{1},\omega_{2})\boldsymbol{\left.\right]}$

Proposition 11 and Corollary 2 provide the probability of the different events
to occur (e.g., the probability that $G^{x}$ has a certain equilibrium), but
do not directly provide the probability for $mG$ being
(inverse-)$\varepsilon$-misinformed. Indeed, since $G^{0}$ and
$\overline{G^{0}}$ may have different equilibria, the computation of the
probabilities for $mG$ and $\overline{mG}$ being
(inverse-)$\varepsilon$-misinformed may use different rows in Table 5. This is
unnecessary only when the two games have the same equilibria:

######  Corollary 4.

Consider a noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$. Set:

$\overline{G^{0}}=G^{0}+M^{r}$, $\widehat{G^{0}}=G^{0}+M^{c}$,
$\overline{mG}\sim\overline{G^{0}}+{\mathcal{N}}\left(\boldsymbol{[0]},D\right)$,
$\widehat{mG}\sim\widehat{G^{0}}+{\mathcal{N}}\left(\boldsymbol{[0]},D\right)$

If $NE(G^{0})=NE(\overline{G^{0}})=NE(\widehat{G^{0}})$ then:

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}=\overline{\mathcal{P}_{r}^{mis}}\cdot\widehat{\mathcal{P}_{c}^{mis}}$

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}=\overline{\mathcal{P}_{r}^{inv}}\cdot\widehat{\mathcal{P}_{c}^{inv}}$

where $\overline{\mathcal{P}_{r}^{mis}}$, $\overline{\mathcal{P}_{r}^{inv}}$,
$\widehat{\mathcal{P}_{c}^{mis}}$, $\widehat{\mathcal{P}_{c}^{inv}}$ are the
probabilities of Table 5 for $\overline{mG}$, $\widehat{mG}$ respectively.

Note that, in Corollary 4, the computation of the probability for $mG$ to be
(inverse-)$\varepsilon$-misinformed, occurs via the combination of quantities
from two different noisy games ($\overline{mG},\widehat{mG}$). As with
Corollary 2, this can be avoided when the noise received by the two players
has the same bias, in which case we get a direct computation of the related
probability:

######  Corollary 5.

Consider the noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, where
$M=(M^{*}\mathchar 24635\relax\;M^{*})$. Set $\overline{G^{0}}=G^{0}+M^{*}$
and
$\overline{mG}\sim\overline{G^{0}}+{\mathcal{N}}\left(\boldsymbol{[0]},D\right)$.
If $NE(G^{0})=NE(\overline{G^{0}})$ then:

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

Corollary 5 is the most specific result, as it gives us a method of computing
the probabilities of a noisy game being (inverse-)$\varepsilon$-misinformed
using the respective probabilities of another noisy game, under specific
assumptions.

The last proposition of this subsection follows easily from Proposition 11,
and shows an elegant, and expected, property of noisy games. In particular,
changing the payoff matrix of a game by adding any fixed constant number to
all payoffs, does not modify the probability of the respective noisy game to
be (inverse-)$\varepsilon$-misinformed (for a fixed noise pattern). This is
expected, because the addition of a fixed number in the payoffs does not
change the structure of the game, and, thus, the two games are considered
“equivalent” in standard game theory. The proposition below proves a more
complex version of this statement, showing that the same is true for the noise
pattern: adding a fixed amount of bias across the board does not modify the
respective probabilities. Formally:

######  Proposition 12.

Consider a noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$, and
constant numbers $a_{G},a_{r},a_{c}\in\mathbb{R}$. Set
$\overline{G^{0}}=G^{0}+\boldsymbol{[a_{G}]}$ and
$\overline{M}=(\overline{M^{r}}\mathchar 24635\relax\;\overline{M^{c}})$,
where $\overline{M^{x}}=M^{x}+\boldsymbol{[a_{x}]}$ for $x\in\\{r,c\\}$.
Moreover, set
$\overline{mG}\sim\overline{G^{0}}+{\mathcal{N}}\left(\overline{M},D\right)$.
Then:

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

###  6.3 Effect of modifying noise intensity ($D$)

Although adding a fixed constant number to the game’s payoffs does not modify
the respective probabilities (Proposition 12), this is not the case when
changing the “scale” of a game (by multiplying all its payoffs by a constant
number, say $\lambda>0$). In particular, changing the scale of a game will
affect its “resilience” to noise, without changing the game’s properties and
behaviour, because it increases the “amount of noise” necessary to change the
sign of the various $\text{{ugain}}(y,x)i$. As a matter of fact, multiplying
the payoffs by a sufficiently large number would minimize the effect of the
noise, as its effects on the payoffs would be, comparatively smaller
(analogously, using a sufficiently small positive number would maximize the
effect of the noise).

In Proposition 13 (and especially in Corollary 6), we quantify this effect, by
showing that we need to multiply the noise intensity (standard deviation) by
$\lambda^{2}$ in order for the noise to have the same effect on a game scaled
by $\lambda$. Formally:

######  Proposition 13.

Consider a normal noisy game $mG\sim G^{0}+{\mathcal{N}}\left(M,D\right)$ and
some $\lambda>0$. Set: $\overline{G^{0}}=\lambda G^{0}$, $\overline{M}=\lambda
M$ and $\overline{}D=\lambda^{2}D$, and consider the normal noisy game
$\overline{mG}=\overline{G^{0}}+{\mathcal{N}}\left(\overline{M},\overline{}D\right)$.
Then:

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

An obvious and interesting corollary of Propositions 12 and 13 is the
following:

######  Corollary 6.

Consider a normal noisy game $mG\sim
G^{0}+{\mathcal{N}}\left(\boldsymbol{[0]},D\right)$ and some $\lambda>0$,
$k\in\mathbb{R}$. Set: $\overline{G^{0}}=\lambda G^{0}+k$ and
$\overline{}D=\lambda^{2}D$, and consider the normal noisy game
$\overline{mG}=\overline{G^{0}}+{\mathcal{N}}\left(\boldsymbol{[0]},\overline{}D\right)$.
Then:

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

  * •

${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\overline{mG}\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$

From the previous theoretical results, the effect of noise in the outcome of
an abstract $2\times 2$ bimatrix game has the following characteristics: for
small values of the noise intensity (standard deviation), players almost
surely have the same behaviour as in the actual game, whereas for large noise
intensity, the behaviour of players cannot be predicted as their games will be
almost random. Also, observe that the formulas giving the probabilities for
(inverse)-$\varepsilon$-misinformed are continuous with respect to the
standard deviation. Given the above, one would expect that, by increasing the
standard deviation, we would monotonically transit from the first extreme to
the second. However, this does not always hold, as the following counter-
example shows.

######  Example 2.

Consider as actual game the classical Prisoner’s Dilemma (see Figure 3(a)),
which has a pure Nash equilibrium with strategy profile $((0,1),(0,1))$. We
produce a noisy game, in which the noise only affects the upper left elements
of the actual payoff matrix, where we add noise according to a random variable
following the normal distribution ${\mathcal{N}}\left(0,d^{2}\right)$. From
Theorems 8, 9, we can compute the probabilities for this game to be
(inverse-)$\varepsilon$-misinformed. The result is shown in Figure 2, where we
plot ${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$ (blue
line) and ${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$
(orange line), for $d\in(0,10)$. As is obvious by this figure, these functions
are not monotonic with respect to $d$.

Figure 2: Example showing that
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$ (blue),
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$
(orange) (vertical axis) have non-monotonic dependence to noise (horizontal
axis).

##  7 Discussion and experiments

In this section we report on experiments that validate our basic results, and
we investigate the effect of noise on the players’ decisions, for the four
$2\times 2$ bimatrix games shown in Figure 3. The games were chosen to capture
the following cases: i) dominant equilibrium (Prisoner’s Dilemma), ii) unique
mixed Nash equilibrium (Matching Pennies), iii) multiple Nash equilibria
(Battle of the Sexes), and iv) dominant equilibrium that coincides with the
optimal outcome (Win-Win).

$\left(\begin{array}[]{cc}(2,2)&(0,3)\\\ (3,0)&(1,1)\end{array}\right)$ (a)
Prisoners’ Dilemma

$\left(\begin{array}[]{cc}(1,-1)&(-1,1)\\\ (-1,1)&(1,-1)\end{array}\right)$
(b) Matching Pennies

$\left(\begin{array}[]{cc}(2,1)&(0,0)\\\ (0,0)&(1,2)\end{array}\right)$ (c)
Battle of the Sexes

$\left(\begin{array}[]{cc}(3,2)&(4,4)\\\ (1,1)&(2,3)\end{array}\right)$ (d)
Win-Win

Figure 3: Games to be used for the experimental evaluation.

###  7.1 Theoretical and Experimental Computation of the Probability that a
Game is (Inverse-)$\varepsilon$-misinformed

We consider that the actual game undergoes an additive noise that follows the
normal distribution $\mathcal{N}(\boldsymbol{[0]},\boldsymbol{[d^{2}]})$ where
$d\in\\{0.001,0.5,1,\ldots,10\\}$.

We compare the theoretical values of probabilities that we get from Theorems
8, 9, with the respective values calculated through Monte Carlo simulations.
The Monte Carlo simulations were conducted as follows: we generate a game
$G^{0}$, which can be one of the four games shown in Figure 3. Then, for each
of the above values for $d$, we create the respective noisy game
$mG=G^{0}+{\mathcal{N}}\left(\boldsymbol{[0]},\boldsymbol{[d^{2}]}\right)$. To
be more precise, we generate a misinformation game, where the misinformation
stems from the incorporation of additive noise stemming from one random
experiment that follows the above distribution
(${\mathcal{N}}\left(\boldsymbol{[0]},\boldsymbol{[d^{2}]}\right)$). We derive
the natural misinformed equilibrium and check about $\varepsilon$-closeness.
We perform $3,000$ repetitions of the above process and calculate:

  1. a)

the percentage of games that are $\varepsilon$-misinformed (i.e., all nmes of
$mG$ are $\varepsilon$-close to one Nash equilibrium of $G^{0}$, according to
the first bullet of Definition 11),

  2. b)

the percentage of games that are inverse $\varepsilon$-misinformed (i.e., all
Nash equilibria of $G^{0}$ are $\varepsilon$-close to one nme of $mG$,
according to the second bullet of Definition 11).

We repeat the simulations for two different values of $\varepsilon$
($\varepsilon\in\\{10^{-2},10^{-3}\\}$). The results are shown in Figures 4-6.
As the Prisoner’s Dilemma and the Win-Win games both have a unique pure Nash
equilibrium, their behavioural consistency is similar. Hence, Figure 4 shows
both cases. In all subplots, we have plots of two colours. The blue ones
depict the computations for $\varepsilon=10^{-2}$, whereas the red ones depict
the computations for $\varepsilon=10^{-3}$.

In part (a) of the figures, the horizontal axis depicts the different values
for the standard deviation $d$ of the noise, and the vertical axis depicts the
probability of a game being $\varepsilon$-misinformed according to Theorem 8
(solid line) or the probability of a game being $\varepsilon$-misinformed
according to the Monte Carlo simulations (dotted lines). The same hold for
part (b) of the figures, but for the inverse-$\varepsilon$-misinformed case
(Theorem 9). In both subfigures, a high value of the probability calculated in
the vertical axis implies a small effect of noise on players’ decisions. As
expected, the theoretical results are very close to the experimental ones.

These figures give rise to various remarks concerning the influence of noise
to players’ strategic choices. Although some general patterns emerge, the
effect of noise in the behavioural consistency of the game greatly depends on
the type and number of Nash equilibria that it has, so we split our analysis
in 3 different cases.

Case 1: Unique Pure Nash equilibrium

The case of a unique pure Nash equilibrium appears in the Prisoner’s Dilemma
and Win-Win games, whose behaviour is depicted in Figure 4.

(a) $\varepsilon$ misinformed. (b) Inverse $\varepsilon$ misinformed. Figure
4: Monte Carlo (MC) simulation and probabilistic formulas for Prisoner’s
Dilemma and Win-Win games. Vertical axis: (4(a))
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$, (4(b))
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$.
Horizontal axis: noise intensity $d$.

For Prisoner’s Dilemma, we observe that, for small values of the standard
deviation ($d\ll 1$), the nme of $mG$ will usually be the same as the NE of
the original game ($G^{0}$). Thus, both probabilities
${\mathcal{P}}_{emis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ and
${\mathcal{P}}_{invemis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ will have values close to
$1$. As $d$ increases, noise will produce misinformation games $G^{r},G^{c}$
with different Nash equilibria than that of the actual game (different means
non-close, by definition, in this case) with an increasing probability,
thereby reducing the probability for behavioural consistency.

As $d$ increases further, each of the different possible sets of equilibria
will appear with almost equal probability in $G^{r},G^{c}$, leading to a
convergence in the plots of Figure 4. In particular,
${\mathcal{P}}_{emis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ converges to approximately
14%, whereas ${\mathcal{P}}_{invemis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ converges to approximately
25%. This can be theoretically predicted by observing Table 1. For a large
enough noise, the original orderings among the elements of the payoff matrix
become increasingly irrelevant, and the actual orderings in each of
$G^{r},G^{c}$ become totally random. As a result, the equilibrium strategy for
$r$ in $G^{r}$ will be a pure one with a probability of 6/8 (3/8 for each
strategy), a mixed one with 1/8 probability, and pure-and-mixed with 1/8
probability. The same is true of course for $c$ in $G^{c}$. Combining these
observations with Table 5 and Theorems 8, 9, we get the above numbers for the
convergence of ${\mathcal{P}}_{emis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$,
${\mathcal{P}}_{invemis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$.

Similar remarks hold for the Win-Win game that has one pure Nash equilibrium
strategy profile (namely, $((1,0),(0,1))$).

Case 2: Unique Mixed Nash equilibrium

The case of a unique mixed Nash equilibrium appears in the Matching Pennies
game, which has one Nash equilibrium strategy profile $((1/2,1/2),(1/2,1/2))$,
and whose behaviour is depicted in Figure 5.

(a) $\varepsilon$ misinformed. (b) Inverse $\varepsilon$ misinformed. Figure
5: Monte Carlo (MC) simulation and probabilistic formulas for Matching
Pennies. Vertical axis: (5(a))
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$, (5(b))
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$.
Horizontal axis: noise intensity $d$.

As in case 1, we observe that for small values of the standard deviation
($d\ll 1$), $mG$ will have the same $nme$ as the NE in $G^{0}$. Thus, both
probabilities ${\mathcal{P}}_{emis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ and
${\mathcal{P}}_{invemis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ will have values close to
$1$. As $d$ increases, noise will produce games $G^{r},G^{c}$ with different
Nash equilibria than that of the actual game $G^{0}$, and the respective
probabilities fall sharply (much faster compared to the Prisoner’s Dilemma
case), converging to a value close to $0$ for large values of the standard
deviation. This is explained by the fact that, although a mixed nme is
achieved in some of the produced games, this is often not close to the actual
mixed one, leading to games that are (usually) not
(inverse-)$\varepsilon$-misinformed. For example, for $\varepsilon=10^{-2}$,
the function ${\mathcal{P}}_{emis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ convergences at around
$0.03\%$.

Case 3: Multiple Nash equilibria

The case of two pure and one mixed Nash equilibrium appears in the Battle of
the Sexes game, whose behaviour is depicted in Figure 6. The Nash equilibrium
strategy profiles of Battle of the Sexes are:
$\\{((1,0),(1,0)),((0,1),(0,1)),\\\ ((2/3,1/3),(1/3,2/3))\\}$.

(a) $\varepsilon$ misinformed. (b) Inverse $\varepsilon$ misinformed. Figure
6: Monte Carlo (MC) simulation and probabilistic formulas for Battle of the
Sexes. Vertical axis: (6(a))
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$, (6(b))
${\mathcal{P}}\boldsymbol{\left[\right.}mG\mathrel{\mathop{\mathchar
58\relax}}\text{inverse-}\varepsilon\text{-misinformed}\boldsymbol{\left.\right]}$.
Horizontal axis: noise intensity $d$.

Unlike other games, we observe that the Battle of the Sexes has zero
probability of being $\varepsilon$-misinformed for small values of $d$. This
is explained by the fact that, for small values of $d$, $G^{r},G^{c}$ will be
very similar to $G^{0}$, each giving 3 equilibrium strategies (for the
respective player). Thus, there are 9 nmes, one for each combination of
equilibrium strategies (see Definition 8), so some of them will not be
$\varepsilon$-close to one of the three equilibria of $G^{0}$. By Definition
11 this means that the respective game is not $\varepsilon$-misinformed, so
${\mathcal{P}}_{emis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$ will be close to $0$.

As $d$ increases, and the games $G^{r},G^{c}$ become less and less
predictable, the probability of being $\varepsilon$-misinformed becomes
larger, reaching a plateau at around 72%. The explanation here is analogous to
the one given for the other two cases: in order for a misinformation game to
_not_ be $\varepsilon$-misinformed, it should either have one pure equilibrium
(but not one of the two that are in the equilibria of $G^{0}$), or it should
have one mixed equilibrium (but not $\varepsilon$-close to the one of
$G^{0}$). Based on the analysis of the Prisoner’s Dilemma game, the
probability of the former is around 28%; based on the analysis of the Matching
Pennies game, the probability of the latter is close to $0$; combining these
observations, we conclude that a plateau at around 72% is reasonable.

For the inverse-$\varepsilon$-misinformed case (part (b) of Figure 6), small
values of $d$ result to high values for
${\mathcal{P}}_{invemis}\boldsymbol{\left[\right.}mG\mathchar
24635\relax\;\varepsilon\boldsymbol{\left.\right]}$, as expected. As $d$
increases, the probability decreases at a rate even faster than the one
observed for Matching Pennies, eventually converging at a value close to $0$.
This is explained by the fact that, in order for the game to be
inverse-$\varepsilon$-misinformed, it should have, among other things, also a
mixed equilibrium that is close to the respective mixed of $G^{0}$. As we
established in Case 2 above, this has a very low probability for large values
of $d$.

###  7.2 Optimal strategy profiles in terms of efficiency

In this subsection, we report on experiments that investigate whether the
misinformation game $mG$ that results from a given actual game $G^{0}$ has
natural misinformed equilibria that are best or worst in terms of efficiency
(social welfare). We then evaluate the effect of noise on each of the four
games under consideration.

We performed Monte Carlo simulations as in the previous section and
calculated:

  1. a)

the percentage $P_{best}$ of misinformation games that have a natural
misinformed equilibrium that maximizes social welfare (best nme),

  2. b)

the percentage $P_{worst}$ of misinformation games that have a natural
misinformed equilibrium that minimizes social welfare (worst nme).

We repeat the simulations for all values of $d$ in $\\{0.02,0.04,\ldots,10\\}$
and for $\varepsilon=10^{-2}$. The results are shown in Figures 7(a) and 7(b).

(a) Percentage of misinformation games that result in the best nme. (b)
Percentage of misinformation games that result in the worst nme. Figure 7:
Strategy profiles in terms of efficiency.

In Matching Pennies, as it is a constant-sum game, all strategy profiles
provide the same level of social welfare, so the respective line is flat,
regardless of the value of $d$ (see Figures 7(a) and 7(b)). In other words,
the noise has no effect with respect to the optimal outcome.

In Prisoners’ Dilemma, the best strategy profile is $((1,0),(1,0))$ and the
worst one is $((0,1),(0,1))$ which coincides with the pure NE of the actual
game $G^{0}$. We observe that, for small values of $d$, only a few repetitions
provide the best nme (Figure 7(a)), while most of them provide the worst nme
(Figure 7(b)); this is in line with the results given in the previous
subsection. As $d$ increases, the percentage of games resulting in the best
strategy increases too, implying that noise has a positive effect on
Prisoners’ Dilemma.

In the Battle of the Sexes, the best strategy profiles are $((1,0),(1,0))$ and
$((0,1),(0,1))$ (these are also the pure Nash equilibria of the actual game),
and the worst strategy profiles are $((1,0),(0,1))$ and $((0,1),(1,0))$. We
observe that, for small values of $d$, most of the misinformation games result
in one of the best strategy profiles (Figure 7(a)). As $d$ increases, this
percentage decreases, implying that noise has a negative effect on the Battle
of the Sexes: players are not forced to choose better strategies.

In the Win-Win game, the best strategy profile is $((1,0),(0,1))$ and the
worst one is $((0,1),(1,0))$. The same observations as in the Battle of the
Sexes hold for the Win-Win game.

To summarize, as the percentage $P_{best}$ increases (or $P_{worst}$
decreases) with respect to $d$, noise is beneficial. This is the case for
Prisoners’ Dilemma. On the contrary, noise deteriorates the efficiency of the
system if the percentage $P_{best}$ decreases (or $P_{worst}$ increases) with
respect to $d$ as in Win-Win and Battle of the Sexes games. Finally, the
efficiency of the system is independent of the noise in the Matching Pennies
game.

Given the above, as expected, noise deteriorates the social welfare in games
where the original Nash equilibrium is already “good” for the social welfare
(Battle of the Sexes, Win-Win), as it induces a more “random” behaviour. On
the contrary, it improves the situation in games where the original
equilibrium is “bad” (e.g., Prisoner’s Dilemma). In constant sum games (e.g.,
Matching Pennies), noise has no effect with regards to the social welfare.

###  7.3 PoM vs PoA

In this subsection, we compare the price of anarchy $PoA$ with the price of
misinformation $PoM$ for the four games of interest. Both metrics measure
social welfare, with or without misinformation respectively, and take values
that are higher than or equal to $1$.

Given a bimatrix game $G$ with payoff matrix $P=(P_{r}\mathchar
24635\relax\;P_{c})$ we use Definition 9 to compute $PoM$ for all values of
pairs $(p,q)$, where $p,q\in[0,1]$. The values of $p,q$ are non other than the
values in the joint strategy profile
$\sigma=(\vec{\mathbf{p}},\vec{\mathbf{q}})$ $=((p,1-p),(q,1-q))$. In formula
6, the quantities in the fraction are given by the formula $SW(\sigma)={\bf
p}^{T}(P_{r}+P_{c}){\bf q}$. The respective graphs are shown in Figures
8(a)-8(d).

(a) PoM plane for the Prisoner’s Dilemma. (b) PoM plane for the Matching
Pennies.
(c) PoM plane for the Battle of the Sexes. (d) PoM plane for the Win-Win.
Figure 8: PoM plane for games in Table 3.

We can make the following observations on social welfare planes of Figures
8(a)-8(d) that present the range of values of $PoM$:

  1. 1.

In Prisoner’s Dilemma we note that the social welfare plane is monotonic (see
Figure 8(a)). The minimum value is in the bottom left corner (“bluest”) and
the maximum value is in the upper right corner (“redest”). We know that the
$PoA$ in this game is $2$, which is equal to the minimum social welfare, so
any distortion in the payoff matrices of the game does not deteriorate the
efficiency of the game, and $PoM\leq PoA$, for every level of noise.

  2. 2.

In Matching Pennies we observe that the social welfare plane is constant
(Figure 8(b)). That is, $PoM$ remains constant as any combination of the
values of the payoff matrix results in the same social welfare value. Thus,
noise may affect the strategic behaviour of players, but keeps the social
welfare constant. Note that, in zero-sum games such as Matching Pennies, the
value of $PoM$ and $PoA$ cannot be calculated (the denominator of the
respective formulas takes the value of zero). To mitigate this inconvenience
we add proper values to each element of the payoff matrices and produce a
constant-sum game, without affecting the strategic behaviour of players.

  3. 3.

In Battle of the Sexes we observe that the two pure Nash equilibria of the
game are the optimal strategic behaviours (Figure 8(c)). Thus, $PoA$ depends
on the mixed Nash equilibrium, and noise could improve or degrade the
efficiency of the system.

  4. 4.

In Win-Win, the unique Nash equilibrium coincides with the optimal one, thus
$PoA=1$ (Figure 8(d)). Therefore, any misinformation cannot improve the
outcome of this game, and $PoM\geq PoA$.

##  8 Conclusion and Future Work

In this paper we studied a novel game-theoretic setting, where players receive
the information regarding the game’s payoffs with a distortion that affects
the elements of the payoff matrix. This distortion was assumed to be due to
additive noise that follows a normal distribution, and could be due to
communication errors that may appear when the game’s parameters are
communicated through a noisy channel, or when some malfunction in the sender
or receiver distorts this information. In such noisy settings, it is possible
that each player knows a different game compared to her opponent and compared
to the actual (originally communicated) one.

We model this situation using misinformation games, an appropriate theoretical
setting introduced previously in [25], and define a subclass of misinformation
games called _noisy games_ (see Section 4). The main problem considered in
this setting is the computation of the probability for behavioural
consistency, i.e., the probability that the agents’ behaviour will be “close”
(under some formal definition of closeness) to the one expected according to
the original game, despite the noise. Towards this, two alternative formal
definitions of behavioural consistency are given (Subsection 4.3) and the
respective probabilities are computed in Section 5. Note that, due to the
complexity of the formulas, we restricted ourselves to 2-player bimatrix games
with 2 strategies per player.

We elaborate on those formulas and prove a number of related results (Section
6), which help understand their properties. Such properties include the effect
of the definition of closeness and/or the noise structure in the respective
probabilities for behavioural consistency, as well as a study of how different
interventions and modifications on the original game would affect these
probabilities.

Moreover, we perform several numerical experiments using four well-known
bimatrix games as benchmarks (see Figure 3). Initially, we compare the
probabilistic formulas with Monte Carlo simulation to verify their
correctness. Then, we derive general remarks as to the efficiency of the
system regarding the additive noise, in terms of social welfare. To do so, we
use the _Price of Misinformation_ metric, which is inspired by the well-known
Price of Anarchy metric and quantifies how benevolent/malevolent is the
misinformation caused by the noise with regards to game performance (related
to social welfare).

Undeniably, the 2 players’ bimatrix games with 2 strategies per player is a
very restricting setting. Unsurprisingly however, even in this simple setting
our analysis highlighted the richness, intricacy and interdependence of the
probabilistic events, mathematical objects and techniques that were involved,
leading to complex mathematical computations and stiff formulations as regards
the end results. Having said that, we plan to consider more complex settings
in the future, i.e., scenarios with more than two players and/or scenarios
where each player may have more than two strategies. Further, we could
consider deriving analogous probabilistic formulas for other classes of noise
distributions (e.g., poisson or laplacian).

Moreover, an immediate future step is to provide tools to quantify the
_sensitivity_ of a game to random noise, i.e., determine “how much noise” the
game can withstand so that the behaviour of the players remains close (under
the sense of behavioural consistency) to the expected ones, with a certain
probability. A related research question is how sensitivity is affected by
inconsequential changes in the game specification (e.g., change of scale); in
this direction, results like Proposition 13 can help. This analysis could be
used as a tool for game designers to improve their designs and make them more
robust to unexpected circumstances and noise in the communication channels.

##  Appendix A Proofs for the Results Appearing in the Paper

###  A.1 Normal Form Games

Proof of Proposition 1
Let’s consider $G=\langle N,S,P\rangle$, for $P=(P_{c}\mathchar
24635\relax\;P_{c})$. Suppose that $G$ is degenerate. By definition, there is
a pure strategy (say $s_{i}$, by player $x\in\\{r,c\\}$) that has two pure
best responses. Suppose that $x=r,i=1$. Then, since $s_{1},s_{2}$ are equally
preferred by $c$, it follows that $P_{c}[1,1]=P_{c}[1,2]$, i.e.,
$\text{{ugain}}(c,1)=0$. The other cases (i.e., when $x=c$ and/or $i=2$) are
analogous.
For the opposite, suppose that $\text{{ugain}}(r,1)=0$. Then
$P_{c}[1,1]=P_{c}[1,2]$, so $c$ has two pure best responses for the strategy
$s_{1}$ of $r$, which means that $G$ is degenerate. The proof is analogous for
the other cases. $\Box$

Proof of Proposition 2
Suppose that $x=r$. From classical game theoretic results (e.g., see [17],
[18]), and our assumptions, we get that $p$ will satisfy the following
equation:

$p\cdot P_{c}[1,1]+(1-p)\cdot P_{c}[2,1]=p\cdot P_{c}[1,2]+(1-p)\cdot
P_{c}[2,2]$

The result now follows trivially by solving this equation and applying the
definition of $\text{{ugain}}(c,i)$.
Analogously, for the case where $x=c$, we get the following equation:

$p\cdot P_{r}[1,1]+(1-p)\cdot P_{r}[1,2]=p\cdot P_{r}[2,1]+(1-p)\cdot
P_{r}[2,2]$

Solving it, as above, will give the required result. $\Box$

Proof of Proposition 3
By Proposition 1, we conclude that $\text{{ugain}}(x,i)\neq 0$ for all
$x\in\\{r,c\\},i\in\\{1,2\\}$. This means that the different (mutually
exclusive) cases of the formulation of the proposition cover all possible
cases for a non-degenerate game (see also Table 1). Thus, it suffices to show
the “only if” part for each different case.
For (1a), note that player $x$ will play $(1,0)$ (i.e., $s_{1}$) regardless of
the choice of $\bar{x}$, so $NE_{x}(G)=\\{(1,0)\\}$ and $\text{{op}}_{x}(1)$
is true.
For (1b), note that the only Nash equilibrium of $G$ is $((1,0),(1,0))$, which
proves the result.
Next, (1c) is analogous to (1b).
The cases (2a), (2b), (2c) are analogous to (1a), (1b), (1c) respectively.
With regards to (3a), it can be easily shown that the game can have no pure
Nash equilibrium. Thus, it must have a mixed one (by the result of Nash [16]).
Moreover, it cannot have more than one mixed, as this would render it
degenerate555Immediate consequence of Corollary 3.7 [17]. (see [17],[3],[18]).

Thus, $NE_{x}(G)=\\{(p,1-p)\\}$, for some $0<p<1$. By Proposition 2, it
follows that
$p=\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}$,
which shows the result.
The case (3b) is analogous.
For (4a), we observe that the values of $\text{{ugain}}(x,i)$ imply that the
game has exactly two pure Nash equilibria, namely: $((1,0),(1,0))$ and
$((0,1),(0,1))$. By [17], [18], it must also have one (unique) mixed
equilibrium, as we examine a non-degenerate case.
Thus, $NE_{x}(G)=\\{(1,0),(0,1),(p,1-p)\\}$ for some $0<p<1$. Again, using
Proposition 2, it follows that
$p=\frac{\text{{ugain}}(\bar{x},2)}{\text{{ugain}}(\bar{x},2)-\text{{ugain}}(\bar{x},1)}$,
which shows the result.
For (4b) the proof is analogous, except that here the pure Nash equilibria of
$G$ are: $((1,0),(0,1))$ and $((0,1),(1,0))$. $\Box$

###  A.2 Misinformation Games and Noisy games

Proof of Proposition 4
By definition, $mG$ is $\varepsilon$-misinformed if and only if for all
$\sigma^{*}=(\sigma_{r}^{*},\sigma_{c}^{*})\in NME(mG)$ there exists
$\sigma^{0}=(\sigma_{r}^{0},\sigma_{c}^{0})\in NE(G^{0})$ such that
$\sigma^{*},\sigma^{0}$ are $\varepsilon$-close. More formally:

$\begin{split}&mG\mathrel{\mathop{\mathchar 58\relax}}\varepsilon\text{
misinformed }\\\ &\hskip
2.84544pt\Leftrightarrow\forall\sigma^{*}=(\sigma_{r}^{*},\sigma_{c}^{*})\in
NME(mG)\;\exists\sigma^{0}=(\sigma_{r}^{0},\sigma_{c}^{0})\in
NE(G^{0})\mathrel{\mathop{\mathchar 58\relax}}\sigma^{*}\in
Cl^{\varepsilon}(\sigma^{0})\\\ &\hskip
2.84544pt\Leftrightarrow\forall\sigma^{*}=(\sigma_{r}^{*},\sigma_{c}^{*})\in
NME(mG),\sigma^{*}\in Cl^{\varepsilon}(NE(G^{0}))\\\ &\hskip
2.84544pt\Leftrightarrow\forall\sigma^{*}=(\sigma_{r}^{*},\sigma_{c}^{*})\in
NME(mG)\left(\sigma_{r}^{*}\in
Cl^{\varepsilon}(NE_{r}(G^{0}))\wedge\sigma_{c}^{*}\in
Cl^{\varepsilon}(NE_{c}(G^{0}))\right)\\\ &\hskip
2.84544pt\Leftrightarrow\forall\sigma_{r}^{*}\in
NE_{r}(G^{r}),\sigma_{r}^{*}\in
Cl^{\varepsilon}(NE_{r}(G^{0}))\wedge\forall\sigma_{c}^{*}\in
NE_{c}(G^{c}),\sigma_{c}^{*}\in Cl^{\varepsilon}(NE_{c}(G^{0}))\\\ &\hskip
2.84544pt\Leftrightarrow\forall x\in\\{r,c\\}\enspace\forall\sigma_{x}^{*}\in
NE_{x}(G^{x}),\sigma_{x}^{*}\in Cl^{\varepsilon}(NE_{x}(G^{0}))\\\
\end{split}$

Now let us fix some $x$ and consider the different cases with regards to
$NE_{x}(G^{0})$:

  * •

If $NE_{x}(G^{0})$ contains a single pure strategy, i.e.,
$\text{{op}}^{G^{0}}_{x}(i)$ is true for some $i\in\\{1,2\\}$, then the
expression $\forall\sigma_{x}^{*}\in NE_{x}(G^{x}),\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(G^{0}))$ is true if and only if $NE_{x}(G^{x})$
contains the same pure strategy, and no other, i.e., if and only if
$\text{{op}}^{G^{x}}_{x}(i)$ is true.

  * •

If $NE_{x}(G^{0})$ contains a single mixed strategy, i.e.,
$\text{{om}}^{G^{0}}_{x}(p^{0})$ is true for some $0<p^{0}<1$, then the
expression $\forall\sigma_{x}^{*}\in NE_{x}(G^{x}),\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(G^{0}))$ is true if and only if $NE_{x}(G^{x})$
contains a single mixed strategy that is $\varepsilon$-close to
$(p^{0},1-p^{0})$, i.e., $\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ is
true, where $\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$. Note that the $\max,\min$ are
necessary to cater for the case where $p^{0}-\varepsilon$, $p^{0}+\varepsilon$
are smaller than $0$ or greater than $1$, respectively.

  * •

If $NE_{x}(G^{0})$ contains two pure and one mixed strategies, i.e.,
$\text{{pm}}^{G^{0}}_{x}(p^{0})$ is true for some $0<p^{0}<1$, then the
expression $\forall\sigma_{x}^{*}\in NE_{x}(G^{x}),\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(G^{0}))$ is true if and only if $NE_{x}(G^{x})$
contains either a pure or a mixed strategy that is $\varepsilon$-close to
$(p^{0},1-p^{0})$. This is expressed by the expression in bullet #3 of the
proposition.

  * •

If $NE_{x}(G^{0})=\Sigma_{x}$, i.e., $\text{{in}}^{G^{0}}_{x}$ is true, then,
no matter the contents of $NE_{x}(G^{x})$, the expression
$\forall\sigma_{x}^{*}\in NE_{x}(G^{x}),\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(G^{0}))$ is true.

This, combined with the fact that these are the only cases with regards to the
value of $NE_{x}(G^{0})$, conclude the proof. $\Box$

Proof of Proposition 5
By definition, $mG$ is inverse-$\varepsilon$-misinformed if and only if for
all $\sigma^{0}=(\sigma_{r}^{0},\sigma_{c}^{*})\in NE(G^{0})$ there exists
$\sigma^{*}=(\sigma_{r}^{*},\sigma_{c}^{*})\in NME(mG)$ such that
$\sigma^{*},\sigma^{0}$ are $\varepsilon$-close. More formally:

$\begin{split}&mG\mathrel{\mathop{\mathchar 58\relax}}\text{
inverse-}\varepsilon\text{-misinformed }\\\ &\hskip
2.84544pt\Leftrightarrow\forall\sigma^{0}=(\sigma_{r}^{0},\sigma_{c}^{0})\in
NE(G^{0})\;\exists\sigma^{*}=(\sigma_{r}^{*},\sigma_{c}^{*})\in
NME(mG)\mathrel{\mathop{\mathchar 58\relax}}\sigma^{*}\in
Cl^{\varepsilon}(\sigma^{0})\\\ &\hskip
2.84544pt\Leftrightarrow\left(\forall\sigma_{r}^{0}\in
NE_{r}(G^{0})\;\exists\sigma_{r}^{*}\in
NE_{r}(G^{r})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{r}^{*}\in
Cl^{\varepsilon}(NE_{r}(\sigma_{r}^{0}))\right)\\\ &\hskip
28.45274pt\wedge\left(\forall\sigma_{c}^{0}\in
NE_{c}(G^{0})\;\exists\sigma_{c}^{*}\in
NE_{c}(G^{c})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{c}^{*}\in
Cl^{\varepsilon}(NE_{c}(\sigma_{c}^{0}))\right)\\\ &\hskip
2.84544pt\Leftrightarrow\forall x\in\\{r,c\\}\forall\sigma_{x}^{0}\in
NE_{x}(G^{0})\;\exists\sigma_{x}^{*}\in
NE_{x}(G^{x})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(\sigma_{x}^{0}))\\\ \end{split}$

Now let us fix some $x$ and consider the different cases with regards to
$NE_{x}(G^{0})$:

  * •

If $NE_{x}(G^{0})$ contains a single pure strategy, i.e.,
$\text{{op}}^{G^{0}}_{x}(i)$ is true for some $i\in\\{1,2\\}$, then the
expression $\forall\sigma_{x}^{0}\in NE_{x}(G^{0})\;\exists\sigma_{x}^{*}\in
NE_{x}(G^{x})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(\sigma_{x}^{0}))$ is true if and only if
$NE_{x}(G^{x})$ contains the same pure strategy, possibly in addition to
others, i.e., (given that $G^{x}$ is non-degenerate) if and only if
$\text{{op}}^{G^{x}}_{x}(i)\bigvee\text{{rpm}}^{G^{x}}_{x}(0,1)$ is true.

  * •

If $NE_{x}(G^{0})$ contains a single mixed strategy, i.e.,
$\text{{om}}^{G^{0}}_{x}(p^{0})$ is true for some $0<p^{0}<1$, then the
expression $\forall\sigma_{x}^{0}\in NE_{x}(G^{0})\;\exists\sigma_{x}^{*}\in
NE_{x}(G^{x})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(\sigma_{x}^{0}))$ is true if and only if
$NE_{x}(G^{x})$ contains a mixed strategy that is $\varepsilon$-close to
$(p^{0},1-p^{0})$, possibly in addition to others, i.e., (given that $G^{x}$
is non-degenerate) $\text{{rom}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ is true,
where $\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$. Note that the $\max,\min$ are
necessary to cater for the case where $p^{0}-\varepsilon$, $p^{0}+\varepsilon$
are smaller than $0$ or greater than $1$, respectively.

  * •

If $NE_{x}(G^{0})$ contains two pure and one mixed strategies, i.e.,
$\text{{pm}}^{G^{0}}_{x}(p^{0})$ is true for some $0<p^{0}<1$, then the
expression $\forall\sigma_{x}^{0}\in NE_{x}(G^{0})\;\exists\sigma_{x}^{*}\in
NE_{x}(G^{x})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(\sigma_{x}^{0}))$ is true if and only if
$NE_{x}(G^{x})$ contains two pure and a mixed strategy that is
$\varepsilon$-close to $(p^{0},1-p^{0})$, i.e., (given that $G^{x}$ is non-
degenerate) $\text{{rpm}}^{G^{x}}_{x}(\omega_{1},\omega_{2})$ is true, where
$\omega_{1}=\max\\{0,p^{0}-\varepsilon\\}$,
$\omega_{2}=\min\\{1,p^{0}+\varepsilon\\}$.

  * •

If $NE_{x}(G^{0})=\Sigma_{x}$, i.e., $\text{{in}}^{G^{0}}_{x}$ is true, then,
$\forall\sigma_{x}^{0}\in NE_{x}(G^{0})\;\exists\sigma_{x}^{*}\in
NE_{x}(G^{x})\mathrel{\mathop{\mathchar 58\relax}}\sigma_{x}^{*}\in
Cl^{\varepsilon}(NE_{x}(\sigma_{x}^{0}))$ is true if and only if at least one
of the strategies in $NE_{x}(G^{x})$ is $\varepsilon$-close to each strategy
in $NE_{x}(G^{0})$. Given that $NE_{x}(G^{x})$ is finite (because $G^{x}$ is
non-degenerate), this can only hold if $\text{{pm}}^{G^{x}}_{x}(p^{x})$ for
some $p^{x}$ such that $(p,1-p)\in Cl^{\varepsilon}((p,1-p))$ for all $0<p<1$.
From the latter, we conclude that $\varepsilon\geq 0.5$ and
$\max\\{0,p^{0}-\varepsilon\\}<p^{x}<\min\\{1,p^{0}+\varepsilon\\}$, which
leads to the requirement in bullet #4 of the proposition.

This, combined with the fact that these are the only cases with regards to the
value of $NE_{x}(G^{0})$, conclude the proof. $\Box$

###  A.3 Probabilities

Proof of Proposition 6
The result is direct from Proposition 1 and the fact that
${\mathcal{P}}\boldsymbol{\left[\right.}U(x,y,i)=0\boldsymbol{\left.\right]}=0$
for any $x,y\in\\{r,c\\}$, $i\in\\{1,2\\}$. $\Box$

Proof of Lemma 1
For the first result, we observe that, since $\Omega_{1}<\Omega_{2}\leq 0$:

$\begin{split}\Omega_{1}\leq\frac{X}{Y}\leq\Omega_{2}\bigwedge X<0\bigwedge
Y>0\Leftrightarrow\Omega_{1}\leq\frac{X}{Y}\leq\Omega_{2}\bigwedge
Y>0\end{split}$

Thus, it suffices to compute the probability of the latter (simpler) event.
Now, set $Z=\frac{X}{Y}$. Then $f_{Z|Y}(z|y)=f_{X}(zy)$, so:

$f_{ZY}(z,y)=f_{Z|Y}(z|y)\cdot f_{Y}(y)=f_{X}(zy)\cdot f_{Y}(y)$

Therefore:

$\begin{split}&{\mathcal{P}}\boldsymbol{\left[\right.}\Omega_{1}\leq\tfrac{X}{Y}\leq\Omega_{2},X<0,Y>0\boldsymbol{\left.\right]}={\mathcal{P}}\boldsymbol{\left[\right.}\Omega_{1}\leq
Z\leq\Omega_{2},Y>0\boldsymbol{\left.\right]}\\\ &\hskip