$\displaystyle(\Delta^{k+1}m)_{n}=\int_{[0,1]}x^{n+1}(x-1)^{k}\,d\mu(x)-\int_{[0,1]}x^{n}(x-1)^{k}\,d\mu(x)=\int_{[0,1]}x^{n}(x-1)^{k+1}\,d\mu(x).$

From this we directly get that
$(-1)^{k}(\Delta^{k}m)_{n}=\int_{[0,1]}x^{n}(1-x)^{k}\,d\mu(x)$. Since we
integrate over $[0,1]$, the integrand is non-negative on the domain of
integration, and $(-1)^{k}(\Delta^{k}m)_{n}\geq 0$. ∎

While Hausdorff’s characterization works for distributions with support in
$[0,1]$, we are also interested in distributions supported in $[1,b]$ for some
$b>1$. Moment sequences behave somewhat differently in that case: For example,
while they are monotonically decreasing in the former case, they are
monotonically increasing in the latter, even growing without bound if there is
some mass to the right of $1$. We can obtain a first necessary criterion,
which looks similar to (17), for a sequence to be the moment sequence of such
a distribution:

######  Corollary 4.29.

For any moment sequence $m$ of a measure $\mu$ with support in [1, b], all
successive differences are non-negative:

$\displaystyle\forall n,k\in\mathbb{N}:(\Delta^{k}m)_{n}\geq 0.$ (18)

###### Proof.

As in the last proof, we have that
$(\Delta^{k}m)_{n}=\int_{[1,b]}x^{n}(x-1)^{k}\,d\mu(x)$. Since in this case,
$x-1>0$ for all $x\in[1,b]$, the integrand is non-negative, and
$(\Delta^{k}m)_{n}\geq 0$. ∎

Another necessary condition similar to (17) can be stated for moment sequences
of distributions on $[0,b]$, using a modified difference operator:

######  Lemma 4.30.

Let $b\geq 0$,
$\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
b$}}}\hskip
6.25963pt}:\mathbb{R}^{\mathbb{N}_{0}}\to\mathbb{R}^{\mathbb{N}_{0}}$,
$(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
b$}}}\hskip 6.25963pt}m)_{n}\coloneqq m_{n+1}-b\cdot m_{n}$. Then for any
moment sequence $m$ of a measure $\mu$ with support in $[0,b]$:

$\displaystyle\forall
n,k\in\mathbb{N}:(-1)^{k}(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
b$}}}\hskip 6.25963pt}^{k}m)_{n}\geq 0.$ (19)

###### Proof.

Analogously to the proof of 4.28, we can prove by induction that
$(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
b$}}}\hskip 6.25963pt}^{k}m)_{n}=\int_{[0,b]}x^{n}(x-b)^{k}\,d\mu(x)$. Since
the integrand in the expression
$(-1)^{k}(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
b$}}}\hskip 6.25963pt}^{k}m)_{n}=\int_{[0,b]}x^{n}(b-x)^{k}\,d\mu(x)$ is non-
negative, we can conclude
$(-1)^{k}(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
b$}}}\hskip 6.25963pt}^{k}m)_{n}\geq 0$. ∎

While Corollary 4.29 and Lemma 4.30 give necessary conditions, it would be
useful to have a condition that is also sufficient. However, we can use Lemma
4.30 to show that Corollary 4.29 is not sufficient, as the following example
demonstrates.

######  Example 4.31.

We construct a sequence that satisfies the condition of Corollary 4.29 and
alternates around a moment sequence: Let sequences $s,q$ be given by
$s_{n}=4^{n}$ for $n\in\mathbb{N}_{0}$, $q_{n}=(-1)^{n}\frac{1}{2^{n}}$ for
$n\in\mathbb{N}$ and $q_{0}=0$. $s$ is the moment sequence of $\delta_{4}$. We
show that $(s+q)$ satisfies the conditions of Corollary 4.29: Let
$k\in\mathbb{N}$. By induction, one can show that
$(\Delta^{k}s)_{n}=3^{k}4^{n}$ for all $n\in\mathbb{N}_{0}$, as well as
$(\Delta^{k}q)_{n}=3^{k}\frac{(-1)^{n+k}}{2^{n+k}}$ for $n\in\mathbb{N}$, and
$(\Delta^{k}q)_{0}=3^{k}\frac{(-1)^{k}}{2^{k}}-(-1)^{k}$. Since $\Delta$ is a
linear operator, we have
${(\Delta^{k}(s+q))_{n}}={(\Delta^{k}s)_{n}+(\Delta^{k}q)_{n}}$ for all
$n,k\in\mathbb{N}_{0}$. This sum is non-negative: If $n\geq 1$, we get
$(\Delta^{k}(s+q))_{n}=3^{k}\bigl{(}4^{n}+\frac{(-1)^{n+k}}{2^{n+k}}\bigr{)}\geq
0$, since $4^{n}\geq 1,\frac{(-1)^{n+k}}{2^{n+k}}>-1$. If $n=0$, we have
${(\Delta^{k}(s+q))_{n}}={3^{k}\bigl{(}1+\frac{(-1)^{k}}{2^{k}}\bigr{)}-(-1)^{k}}$,
which is non-negative as well: For $k=0$, this becomes ${1\cdot(1+1)-1=1}$.
For $k\geq 1$, we have $1+\frac{(-1)^{k}}{2^{k}}\geq\frac{1}{2}$ and therefore
$3^{k}\bigl{(}1+\frac{(-1)^{k}}{2^{k}}\bigr{)}-(-1)^{k}\geq\frac{3}{2}-(-1)^{k}>0$.

So $(s+q)$ satisfies the condition of Corollary 4.29. By construction, it
alternates around the moment sequence $s$, because $q$ alternates around 0. As
the sequence also satisfies $s_{0}+q_{0}=s_{0}=1$ (necessary to be the moment
sequence of a probability measure), these properties make it a candidate for a
counterexample to the tail order being total for probability measures with
non-negative, bounded support.

However, $(s+q)$ does not satisfy (19) for any reasonable choice of $b$: If
$(s+q)$ was the moment sequence of some measure $\mu\in\mathcal{D}_{\geq 0}$,
then $\mu\in\mathcal{D}_{[0,b]}$ would hold if and only if for all $n\geq
0:s_{n}+q_{n}<b^{n}$ (e.g. use Theorem 4.16 on $\mu,\delta_{b}$ for the “if”
part, also cf. [Sch17, Proposition 4.1]). We can take the bound
$s_{n}+q_{n}\leq 5^{n}$, which is satisfied since $s_{n}\leq 4^{n},q_{n}<1$.
So the support of $\mu$ must be a subset of $[0,5]$. However, calculations
show that
$(-1)^{2}(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
5$}}}\hskip 6.25963pt}^{2}(s+q))_{1}$ is negative: We have
$(s+q)_{1}=4-\frac{1}{2}=\frac{7}{2}$, $(s+q)_{2}=16+\frac{1}{4}=\frac{65}{4}$
and $(s+q)_{3}=64-\frac{1}{8}=\frac{511}{8}$. From this we get
$(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
5$}}}\hskip 6.25963pt}(s+q))_{1}=\frac{65}{4}-5\cdot\frac{7}{2}=-\frac{5}{4}$
and $(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
5$}}}\hskip
6.25963pt}(s+q))_{2}=\frac{511}{8}-5\cdot\frac{65}{4}=-\frac{139}{8}$, and
finally
$(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
5$}}}\hskip
6.25963pt}^{2}(s+q))_{1}=-\frac{139}{8}+5\cdot\frac{5}{4}=-\frac{89}{8}$.
Therefore,
$(-1)^{2}(\Delta{\mathrel{\raisebox{1.28032pt}{\scalebox{0.9}{$\scriptscriptstyle
5$}}}\hskip 6.25963pt}^{2}(s+q))_{1}=-\frac{89}{8}<0$, violating the necessary
condition of Lemma 4.30. So $(s+q)$ is not a moment sequence of a measure in
$\mathcal{D}_{[0,b]}$ even though the condition of Corollary 4.29 is
satisfied, therefore this condition is not sufficient. ∎

While the condition (18) is not sufficient, the condition (19) could well be:
Possibly, a proof of [Sch17, Theorem 3.14] for showing the sufficiency of the
complete monotonicity condition (17) could be altered to show the sufficiency
of (19). It is also important to note that other characterizations for moment
sequences of measures supported on an arbitrary compact interval $[a,b]$
exist, and two conditions are given in [Sch17, Theorem 3.13]. We will not
further go into these conditions, however: The reason we studied conditions
like (18) and (19) was that we hoped to show that two moment sequences
satisfying these conditions could not alternate around each other, and
therefore show that $\preccurlyeq_{\text{tail}}$ was a total order between
distributions in $\mathcal{D}_{\geq 0}$ with bounded support. However in the
meanwhile, a counterexample was constructed by Jeremias Epperlein, which will
be presented in the following: It constructs two discrete distributions with
infinite support in $[a,b]$, $0\leq a<b$, that have alternating moment
sequences. We first present a lemma needed for the construction, and then
proceed with the counterexample.

######  Lemma 4.32 ([Epp20]).

Let $0\leq a<b$. Let $n\in\mathbb{N}$ and $(c_{l})_{l\in[n]}$,
$(d_{l})_{l\in[n]}$ be initial parts of sequences in $[a,b)$. Then there is an
arbitrarily large $k\in\mathbb{N}$ and a $c_{n+1}\in(c_{n},b)$ such that

$\displaystyle\sum_{l=1}^{n}\frac{1}{2^{l}}d_{l}^{k}+\frac{1}{2^{n+1}}d_{n}^{k}+\sum_{l=n+2}^{\infty}\frac{1}{2^{l}}b^{k}\,<\,\sum_{l=1}^{n}\frac{1}{2^{l}}c_{l}^{k}+\sum_{l=n+1}^{\infty}\frac{1}{2^{l}}c_{n+1}^{k}.$
(20)

###### Proof.

If we let $c_{n+1}=b$, we can cancel out the equal infinite sums on both
sides, and then the inequality is equivalent to

$\displaystyle\sum_{l=1}^{n}\frac{1}{2^{l}}d_{l}^{k}+\frac{1}{2^{n+1}}d_{n}^{k}<\sum_{l=1}^{n}\frac{1}{2^{l}}c_{l}^{k}+\frac{1}{2^{n+1}}b^{k}.$
(21)

As $b>d_{n}>\dots>d_{1}>0$ and all $c_{i}$ are non-negative, the exponential
growth of $b^{k}$ makes the right-hand side dominate the left-hand side for
sufficiently large $k$. Therefore there exists a $\tilde{k}\in\mathbb{N}$ such
that with $k=\tilde{k}$, (21) holds, and therefore (20) holds for
$c_{n+1}\coloneqq b$. With $k=\tilde{k}$ fixed, the right side of (20) is
constant and the left side depends continuously on $c_{n+1}$. We can therefore
pick $c_{n+1}\in(c_{n},b)$ such that the inequality still holds. ∎

######  Example 4.33 ([Epp20]).

Two discrete probability measures with support in a bounded interval
$\mathbf{\boldsymbol{[a,b]\subseteq[0,\infty)}}$ that are not
$\preccurlyeq_{\text{tail}}$-comparable.

Let $0\leq a<b$. We will construct two sequences $x=(x_{l})_{l\in\mathbb{N}}$,
$y=(y_{l})_{l\in\mathbb{N}}$ in $[a,b]$ and define probability measures
$P_{x},P_{y}$ as sums of Dirac measures:

$\displaystyle
P_{x}\coloneqq\sum_{l=1}^{\infty}\frac{1}{2^{l}}\delta_{x_{l}},\quad
P_{y}\coloneqq\sum_{l=1}^{\infty}\frac{1}{2^{l}}\delta_{y_{l}}.$

The sequences are constructed recursively as follows: $x_{1},y_{1}\in[a,b)$
are chosen arbitrarily. For $n\in\mathbb{N}$, if $(n+1)$ is even, set
$y_{n+1}\coloneqq y_{n}$, and apply Lemma 4.32 to
$(x_{l})_{l\in[n]},(y_{l})_{l\in[n]}$ to obtain two numbers $k_{n+1}>k_{n}$,
$x_{n+1}\in(x_{n},b)$ that satisfy (20). If $(n+1)$ is odd, set
$x_{n+1}\coloneqq x_{n}$, and apply Lemma 4.32 to
$(y_{l})_{l\in[n]},(x_{l})_{l\in[n]}$ to obtain $k_{n+1}>k_{n}$,
${y_{n+1}\in(y_{n},b)}$ that satisfy (20). In summary, the sequences look like
this:

$\displaystyle
x=(x_{1},x_{2},x_{2},x_{4},x_{4},x_{6},\dots),\leavevmode\nobreak\
y=(y_{1},y_{1},y_{3},y_{3},y_{5},y_{5},\dots).$

Condition (20) ensures that the moment sequences of $P_{x},P_{y}$ alternate:
For $n\geq 1$, if $(n+1)$ is even,

$m_{k_{n+1}}(P_{x})=\sum_{l=1}^{\infty}\frac{1}{2^{l}}(x_{l})^{k_{n+1}}\geq\sum_{l=1}^{n}\frac{1}{2^{l}}(x_{l})^{k_{n+1}}+\sum_{l=n+1}^{\infty}\frac{1}{2^{l}}(x_{n+1})^{k_{n+1}}\\\
\underset{\eqref{eq:tailOrderTotalCounterexample-
lemmaCondition}}{>}\,\sum_{l=1}^{n}\frac{1}{2^{l}}(y_{l})^{k_{n+1}}+\frac{1}{2^{n+1}}(y_{n})^{k_{n+1}}+\sum_{l=n+2}^{\infty}\frac{1}{2^{l}}b^{k_{n+1}}\geq\sum_{l=1}^{\infty}\frac{1}{2^{l}}(y_{l})^{k_{n+1}}=m_{k_{n+1}}(P_{y}).$

By a symmetric argument, if $(n+1)$ is odd, then
$m_{k_{n+1}}(P_{y})>m_{k_{n+1}}(P_{x})$. ∎

######  Example 4.34.

Two absolutely continuous probability measures with support in a bounded
interval $\mathbf{\boldsymbol{[a,b]\subseteq[0,\infty)}}$ that are not
$\preccurlyeq_{\text{tail}}$-comparable.

The previous example requires only slight modifications to produce two
absolutely continuous distributions in $\mathcal{D}_{[a,b]}$ that are
incomparable by $\preccurlyeq_{\text{tail}}$. First as in Example 4.23, let
$h$ be a continuous density on $[0,1]$, and for real numbers $c<d$ define the
scaled version $h_{[c,d]}$.

For two sequences of intervals
$([\underaccent{\bar}{x}_{l},\bar{x}_{l}])_{l\in\mathbb{N}}$,
$([\underaccent{\bar}{y}_{l},\bar{y}_{l}])_{l\in\mathbb{N}}$, define densities
$f=\sum_{l=1}^{\infty}\frac{1}{2^{l}}h_{[\underaccent{\bar}{x}_{l},\bar{x}_{l}]}$,
$g=\sum_{l=1}^{\infty}\frac{1}{2^{l}}h_{[\underaccent{\bar}{y}_{l},\bar{y}_{l}]}$,
and $P_{x},P_{y}$ as the probability distributions with these densities. One
can easily calculate that the following bounds hold for $m_{k}(P_{x})$ and
$m_{k}(P_{y})$:

$\displaystyle\sum_{l=1}^{\infty}\frac{1}{2^{l}}\bar{x}_{l}^{k}\,\geq\,m_{k}(P_{x})\,\geq\,\sum_{l=1}^{\infty}\frac{1}{2^{l}}\underaccent{\bar}{x}_{l}^{k},\quad\sum_{l=1}^{\infty}\frac{1}{2^{l}}\bar{y}_{l}^{k}\,\geq\,m_{k}(P_{y})\,\geq\,\sum_{l=1}^{\infty}\frac{1}{2^{l}}\underaccent{\bar}{y}_{l}^{k}$
(22)

We apply the trick of the previous example in modified form: If $(n+1)$ is
even, set $y_{n+1}\coloneqq y_{n}$, and apply Lemma 4.32 to
$(\underaccent{\bar}{x}_{l})_{l\in[n]},(\bar{y}_{l})_{l\in[n]}$ to obtain
$\underaccent{\bar}{x}_{n+1},k_{n+1}$. If $(n+1)$ is odd, set
$x_{n+1}\coloneqq x_{n}$ and apply Lemma 4.32 to
$(\underaccent{\bar}{y}_{l})_{l\in[n]},(\bar{x}_{l})_{l\in[n]}$ to obtain
$\underaccent{\bar}{y}_{n+1},k_{n+1}$. We also make sure that
$\underaccent{\bar}{x}_{n+1}>\bar{x}_{n},\underaccent{\bar}{y}_{n+1}>\bar{y}_{n}$,
and pick
$\bar{x}_{n+1}\in(\underaccent{\bar}{x}_{n+1},b),\bar{y}_{n+1}\in(\underaccent{\bar}{y}_{n+1},b)$
arbitrarily. Then the estimates in (22) and calculations as in the previous
example ensure that for even $(n+1)$, $m_{k_{n+1}}(P_{y})<m_{k_{n+1}}(P_{x})$,
and for odd $(n+1)$, $m_{k_{n+1}}(P_{y})>m_{k_{n+1}}(P_{x})$.

When we constructed a density in a similar way in Example 4.23, we could
ensure the continuity of the sum by uniform convergence. In the current
example, it is not clear if uniform convergence can be achieved in the
definitions of $f$ and $g$. We would need to show that the
$[\underaccent{\bar}{x}_{l},\bar{x}_{l}]$ can be chosen in such a way that
their lengths approach zero slower than the probability masses
$\frac{1}{2^{l}}$: Otherwise the maxima of the functions
$\frac{1}{2^{l}}h_{[\underaccent{\bar}{x}_{l},\bar{x}_{l}]}$ would not
converge to zero, and $f$ would be discontinuous at the right endpoint $b$
(and similarly for $g$). We will not pursue this issue here, so whether the
additional requirement of continuous density functions makes
$\preccurlyeq_{\text{tail}}$ total is a question for further work. ∎

###  10 Nash Equilibria in Tail-Ordered Games

We will now analyze Nash equilibria of distribution-valued games with respect
to the stochastic tail order. An important result of this section is that,
unlike their real-valued counterparts, these games fail to have mixed-strategy
Nash equilibria in general.

We restrict our attention to games with finitely supported distributions as
payoffs, and we will show that such games already fail to have mixed-strategy
Nash equilibria in many cases. As shown in Corollary 4.20, for finitely
supported distributions, the tail order can be reduced to a lexicographic
comparison. To make our discussion notationally easier, we represent payoff
distributions with finite common support as real-valued vectors of
probabilities, ordered by the reflected lexicographic order. This is justified
since the distribution-valued game and its corresponding vector-valued game
are isomorphic and therefore have the Nash equilibria, as the subsequent lemma
shows.

######  Definition 4.35.

A _vector-valued game_ of dimension $m\in\mathbb{N}$ is a game $G$ with
generalized payoffs in $\mathbb{R}^{m}$. If it is equipped with the preorder
$\leq_{\textsc{Rlex}}$, we call it a _reflected-lexicographically ordered_
(also _ref-lex-ordered_) game.

######  Notation 4.36.

If $G$ is a distribution-valued game, we write

$\displaystyle\operatorname{supp}(G)\coloneqq\bigcup\limits_{\begin{subarray}{c}s\in
S,\\\ k\in[n]\end{subarray}}\operatorname{supp}(u_{k}(s))$

for the common support of its payoff distributions.

######  Definition 4.37.

Let $G$ be a distribution-valued game with finite common payoff support
$\operatorname{supp}(G)=\\{x_{1},\dots,x_{m}\\}$, $x_{1}<\dots<x_{m}$. For
each $k\in[n],s\in S$, let the payoff $u_{k}(s)$ have the probability mass
function $f_{k,s}$. Then the _probability vector game corresponding to $G$_ is
the vector-valued game $H$ with the same strategies as $G$ that has the
payoffs $v_{k}(s)\coloneqq(f_{k,s}(x_{1}),\dots,f_{k,s}(x_{m}))$ for all
$k\in[n],s\in S$.

######  Lemma 4.38.

Let $G$ be a distribution-valued game such that $\operatorname{supp}(G)$ is
finite, and $\operatorname{supp}(G)\subseteq[1,\infty)$. Let $H$ be the
probability vector game corresponding to $G$. Then
$G_{\preccurlyeq_{\text{tail}}}$ and $H_{\leq_{\textsc{Rlex}}}$ are
isomorphic.

###### Proof.

Let $\mathcal{D}_{\operatorname{supp}(G)}$ denote the measures from
$\mathcal{D}$ supported on $\operatorname{supp}(G)$. Denote by
$B\coloneqq\\{(p_{1},\dots,p_{m})\in[0,1]^{m}\mid\sum_{i=1}^{m}p_{i}=1\\}\subseteq\mathbb{R}^{m}$
the set of $m$-dimensional probability vectors. Then
$\varphi:\mathcal{D}_{\operatorname{supp}(G)}\to
B,P\mapsto(P(\\{x_{1}\\}),\dots,P(\\{x_{n}\\}))$ is a bijective function,
satisfying $\varphi(u_{k}(s))=v_{k}(s)$ for all $k\in[n],s\in S$ by
construction of $v_{k}(s)$. Since the payoffs of $G$ are from
$\mathcal{D}_{\geq 1}$, we can apply Corollary 4.20: This shows that for all
$s,t\in S,k\in[n]$, it holds that $u_{k}(s)\preccurlyeq_{\text{tail}}u_{k}(t)$
if and only if $v_{k}(s)\leq_{\textsc{Rlex}}v_{k}(t)$. ∎

######  Definition 4.39.

Let $G$ be an $m$-dimensional vector-valued game. For $i\in[m]$, let its _$i$
-th coordinate projected game_ be defined as the real-valued game $G_{i}$ with
the same strategies as $G$, and payoffs $u^{i}_{k}(s)\coloneqq(u_{k}(s))_{i}$
for all $k\in[n],s\in S$.

####  10.1 Existence Conditions for Mixed-Strategy Nash Equilibria in
Lexicographically-Ordered Games

Not all ref-lex-ordered games have mixed-strategy Nash equilibria, which is an
important difference from the theory of real-valued games. We will first
illustrate this with an example, and then work out under which circumstances
such Nash equilibria _do_ exist.

######  Example 4.40.

The following game is an example of a ref-lex-ordered game:

| $b_{1}$ | $b_{2}$
---|---|---
$a_{1}$ | (0.1, 0.8, 0.1) | (0.1, 0.7, 0.2)
$a_{2}$ | (0.6, 0.1, 0.3) | (0.8, 0.1, 0.1)
(26)

The game is a two-player matrix game (i.e. zero-sum), so we only specify
payoffs for the first player. An isomorphic tail-ordered distribution-valued
game can be constructed from it for any specified support set of size 3 that
lies in $[1,\infty)$, and which specific support is chosen does not matter for
the tail order.

This game has no Nash equilibria with respect to $\leq_{\textsc{Rlex}}$. To
see this, we will first take a closer look at the highest coordinate,
projecting the game to it: Consider the projected game $G_{3}$ represented by
$\left(\begin{smallmatrix}0.1&0.2\\\ 0.3&0.1\end{smallmatrix}\right)$, which
is a real-valued zero-sum game that we can solve with standard techniques.

Computations done with the game-theoretic library included in the mathematical
software SageMath (which implements the enumeration support algorithm from
Section 6.1, see [Sag20]) show that $G_{3}$ has exactly one Nash equilibrium,
with mixed strategies $s_{1}=\bigl{(}\frac{2}{3},\frac{1}{3}\bigr{)}$ for
player 1 and $s_{2}=\bigl{(}\frac{1}{3},\frac{2}{3}\bigr{)}$ for player 2,
yielding a payoff of $\frac{1}{6}$ to player 1. Applying this strategy to our
original game $G$ yields the payoff vector
$u=\bigl{(}\frac{28}{90},\frac{47}{90},\frac{1}{6}\bigr{)}$. From Corollary
3.21 we know that in the real-valued game $G_{3}$, if any player unilaterally
deviates from this strategy profile, the payoff stays the same: For example,
if player 1 plays the pure strategy $(1,0)$ and player 2 sticks with $s_{2}$,
the payoff for player 1 will still be $\frac{1}{6}$. However the payoff does
not stay the same in the vector-valued game $G$: With the new strategy of
player 1, the payoff is
$\bigl{(}\frac{9}{90},\frac{66}{90},\frac{1}{6}\bigr{)}>_{\textsc{Rlex}}u$,
making her payoff more preferable with respect to $\leq_{\textsc{Rlex}}$. If
instead player 1 keeps her strategy $s_{1}$ and player 2 plays the pure
strategy $(0,1)$, the payoff for player 1 becomes
$\bigl{(}\frac{30}{45},\frac{45}{90},\frac{1}{6}\bigr{)}<_{\textsc{Rlex}}u$,
which is more preferable for player 2. Therefore, $(s_{1},s_{2})$ is not a
Nash equilibrium for $G$.

Also, there can be no other Nash equilibria, as $(s_{1},s_{2})$ is the only
Nash equilibrium for the projected game $G_{3}$: Assume there is another set
of strategies $(t_{1},t_{2})\neq(s_{1},s_{2})$ which _is_ a Nash equilibrium
for $G$. But since $(t_{1},t_{2})$ is not a Nash equilibrium for $G_{3}$,
there is an incentive for some player to deviate from $(t_{1},t_{2})$ which
improves their outcome for $G$ in the highest coordinate, thus also improving
it with respect to $\leq_{\textsc{Rlex}}$, which is a contradiction. At the
core of this problem is that the projected games in the different coordinates
have different mixed-strategy Nash equilibria. Specifically, while $G_{3}$ has
the Nash equilibrium $((\frac{2}{3},\frac{1}{3}),(\frac{1}{3},\frac{2}{3}))$,
$G_{2}$ instead has the Nash equilibrium $((1,0),(0,1))$, and $G_{1}$ has the
Nash equilibrium $((0,1),(1,0))$.∎

Example 4.40 already gives an idea why different Nash equilibria in different
coordinates can keep ref-lex-ordered games from having Nash equilibria. The
rest of this subsection formalizes and refines the conditions seen in the
example. While the example concerned a zero-sum game, i.e. a vector-valued
game with respect to the orders
${(\leq_{\textsc{Rlex}},\geq_{\textsc{Rlex}})}$ (see Definition 4.4), we will
instead focus on games with respect to
${(\leq_{\textsc{Rlex}},\leq_{\textsc{Rlex}})}$ for simplicity. This is not an
essential difference: For any vector-valued bimatrix game $G$, we can define
$\hat{G}$ as the game where the payoffs of player 2 are negated – then
$G_{{(\leq_{\textsc{Rlex}},\geq_{\textsc{Rlex}})}}$ and
$\hat{G}_{{(\leq_{\textsc{Rlex}},\leq_{\textsc{Rlex}})}}$ are isomorphic, and
we can apply the following results to
$\hat{G}_{{(\leq_{\textsc{Rlex}},\leq_{\textsc{Rlex}})}}$ and thereby obtain
information about the Nash equilibria of
$G_{{(\leq_{\textsc{Rlex}},\geq_{\textsc{Rlex}})}}$. The same approach of
course works for $G_{{(\geq_{\textsc{Rlex}},\leq_{\textsc{Rlex}})}}$, which
captures the assumption of loss distributions instead of payoff distributions
made in [Ras15]. Also, we use the _reflected_ lexicographic order instead of
the usual lexicographic order merely because it corresponds to the tail order
more naturally; all results in this section can be rephrased for vector-valued
games ordered by $\leq_{\textsc{Lex}}$. Recall from Definition 4.12 that we
write $G_{\leq_{\textsc{Rlex}}}$ as a short notation for
$G_{(\leq_{\textsc{Rlex}},\leq_{\textsc{Rlex}})}$.

######  Lemma 4.41.

Let $G$ be a vector-valued bimatrix game with values in $\mathbb{R}^{m}$. Then
any Nash equilibrium $(s_{1},s_{2})$ of $G_{\leq_{\textsc{Rlex}}}$ is also a
Nash equilibrium of $G_{m}$.

###### Proof.

Suppose $G_{m}$ does not have $(s_{1},s_{2})$ as a Nash equilibrium. Then one
of the players, say (without loss of generality) player 1, has an incentive to
deviate in $G_{m}$: This means that for some strategy $\tilde{s}_{1}\in
S_{1}$, $u_{1}^{m}(\tilde{s}_{1},s_{2})>u_{1}^{m}(s_{1},s_{2})$. But then for
the payoffs in $G$,

$\displaystyle
u_{1}(\tilde{s}_{1},s_{2})=\bigl{(}u_{1}^{1}(\tilde{s}_{1},s_{2}),\dots,u_{1}^{m}(\tilde{s}_{1},s_{2})\bigr{)}>_{\textsc{Rlex}}\bigl{(}u_{1}^{1}(s_{1},s_{2}),\dots,u_{1}^{m}(s_{1},s_{2})\bigr{)}=u_{1}(s_{1},s_{2}).$

∎

######  Corollary 4.42.

Let $G$ be a vector-valued bimatrix game with values in $\mathbb{R}^{m}$, and
suppose that $G_{m}$ has exactly one Nash equilibrium $(s_{1},s_{2})$. Then

$\displaystyle G_{\leq_{\textsc{Rlex}}}\text{ has a Nash equilibrium
}\Leftrightarrow\quad G_{\leq_{\textsc{Rlex}}}\text{ has the Nash equilibrium
}(s_{1},s_{2}).$

######  Theorem 4.43.

Let $G$ be a vector-valued bimatrix game with values in $\mathbb{R}^{m}$.
Suppose that $G_{m}$ has the Nash equilibrium $(s_{1},s_{2})$. Then the
following implication holds:

$\displaystyle\forall i\in[m-1]:G_{i}\text{ has the Nash equilibrium
}(s_{1},s_{2})$ (27) $\displaystyle\Rightarrow\quad$ $\displaystyle
G_{\leq_{\textsc{Rlex}}}\text{ has the Nash equilibrium }(s_{1},s_{2}).$ (28)

###### Proof.

Assume that (27) holds. Let $k\in[n]$ be an arbitrary player, and
$\tilde{s}_{k}\in S_{k}$ an alternative strategy. Then for each projected game
$G_{i}$, because $(s_{1},s_{2})$ is a Nash equilibrium of $G_{i}$, we have
$u_{k}^{i}(\tilde{s}_{k},s_{-k})\leq u_{k}^{i}(s_{k},s_{-k})$. Therefore in
$G$,

$u_{k}(\tilde{s}_{k},s_{-k})=\bigl{(}u_{k}^{1}(\tilde{s}_{k},s_{-k}),\dots,u_{k}^{m}(\tilde{s}_{k},s_{-k})\bigr{)}\\\
\leq_{\textsc{Rlex}}\bigl{(}u_{k}^{1}(s_{k},s_{-k}),\dots,u_{k}^{m}(s_{k},s_{-k})\bigr{)}=u_{k}(s_{k},s_{-k}).$

∎

In Example 4.40, the reason why the game did not have a Nash equilibrium was
that the highest-coordinate and the second-highest-coordinate projections had
different Nash equilibria. Keeping this in mind, it seems as if (27) may not
only be a sufficient, but also a necessary condition for the existence of Nash
equilibria. This is not the case, however: There is a similar, but weaker
necessary condition that ref-lex-games with Nash equilibria need to satisfy.
The next example illustrates how a ref-lex-game can have a Nash equilibrium
even though the mixed-strategy equilibrium in the highest-coordinate
projection is not reflected in the second-highest coordinate.

######  Example 4.44.

Consider the ref-lex-ordered bimatrix game $G$ with the following payoffs for
player 1/player 2, respectively:

| $b_{1}$ | $b_{2}$ | $b_{3}$
---|---|---|---
$a_{1}$ | (1, 1) | (2, 2) | (3, 3)
$a_{2}$ | (2, 2) | (1, 1) | (3, 3)
$a_{3}$ | (3, 0) | (3, 0) | (3, 3)
| $b_{1}$ | $b_{2}$ | $b_{3}$
---|---|---|---
$a_{1}$ | (1, -1) | (2, -2) | (3, -3)
$a_{2}$ | (2, -2) | (1, -1) | (3, -3)
$a_{3}$ | (3, 0) | (3, 0) | (3, -3)

The projected game $G_{2}$ is a zero-sum game with payoffs
$\pm\left(\begin{smallmatrix}1&2&3\\\ 2&1&3\\\ 0&0&3\end{smallmatrix}\right)$,
and in the projected game $G_{1}$ both players have the same payoff matrix
$\left(\begin{smallmatrix}1&2&3\\\ 2&1&3\\\ 3&3&3\end{smallmatrix}\right)$. It
can be computed that the only Nash equilibrium for $G_{2}$ is
$(s_{1},s_{2})\coloneqq\bigl{(}(\frac{1}{2},\frac{1}{2},0),(\frac{1}{2},\frac{1}{2},0)\bigr{)}$.
This is not a Nash equilibrium for $G_{1}$, since for any player, deviating to
$(0,0,1)$ gives a better payoff (the last row/column have strictly higher
payoffs for both players). However $(s_{1},s_{2})$ indeed _is_ a Nash
equilibrium for $G$: Any deviation that does not mix in the last row or column
(for example, if player 1 deviates to $(0.3,0.7,0)$) will keep the payoffs the
same for both players in both coordinates; any deviation that does mix in the
last row or column will make the payoff for the respective player worse in the
highest coordinate, and therefore also with respect to $\leq_{\textsc{Rlex}}$.
∎

This example shows the obstacle when trying to turn (27) into an equivalence.
More or less, the idea applied in Example 4.40 was that player 1 deviated from
the highest-coordinate Nash equilibrium $(s_{1},s_{2})$, but the new strategy
still mixed between the pure strategies in $\operatorname{supp}(s_{1})$. That
way, the payoff in the highest coordinate stayed the same while the second-
coordinate payoff improved. However in Example 4.44, only deviating within the
support of $s_{1}$ (or $s_{2}$ for player 2) of course keeps the high-
coordinate payoff the same, but the low-coordinate payoff can only be improved
by playing a strategy outside of the support. So although the low-coordinate
game $G_{1}$ does not have $(s_{1},s_{2})$ as a Nash equilibrium, the
equilibrium still holds for $G$, as no deviation that mixes only between the
strategies in $\operatorname{supp}(s_{1})$ gives an
$\leq_{\textsc{Rlex}}$-better payoff. With this observation, we can get the
aforementioned weaker necessary condition by restricting the lower-coordinate
projections to subgames: We take out the rows and columns which are outside
the support of the highest-coordinate Nash equilibrium.

######  Definition 4.45.

Let $G=(n,(\Delta_{1},\dots,\Delta_{n}),(u_{1},\dots,u_{n}))$ be a real-valued
game with pure-strategy sets $S_{1},\dots,S_{n}$. For each $k\in[n]$, let
$\bar{S_{k}}\subseteq S_{k}$ be a subset of the $k$-th player’s strategies.
Then the _subgame_ corresponding to these strategy sets is the game
$\bar{G}\coloneqq(n,(\bar{S_{1}},\dots,\bar{S_{n}}),(\bar{u}_{1},\dots,\bar{u}_{n}))$,
where $\bar{S}\coloneqq\bigtimes_{k\in[n]}\bar{S}_{k}$, and for all $k\in[n]$,
$\bar{u}_{k}\coloneqq u_{k}|_{\bar{S}}$ is the restriction of $u_{k}$ to the
new strategy space.

######  Notation 4.46.

Let $G$ be an $m$-dimensional vector-valued bimatrix game with pure-strategy
sets $S_{1},S_{2}$. Let $G_{m}$ have the Nash equilibrium $(s_{1},s_{2})$. In
this case we write $T_{1}\coloneqq\operatorname{supp}(s_{1})\subseteq
S_{1},T_{2}\coloneqq\operatorname{supp}(s_{2})\subseteq S_{2}$ for the
supports of $s_{1}$ and $s_{2}$, and $\bar{G}_{i}$ for the subgame
corresponding to $T_{1},T_{2}$ of the $i$-th coordinate projection $G_{i}$. We
also write $t_{1},t_{2}$ for the strategies $s_{1},s_{2}$ restricted to
$T_{1}$ and $T_{2}$, respectively. (All of these notations depend on
$(s_{1},s_{2})$, even though this is not explicitly written out every time for
simplicity.)

######  Theorem 4.47.

Let $G$ be an $m$-dimensional vector-valued bimatrix game, let $G_{m}$ have
the Nash equilibrium $(s_{1},s_{2})$. Then the following implication holds:

$\displaystyle G_{\leq_{\textsc{Rlex}}}\text{ has the Nash equilibrium
}(s_{1},s_{2})$ $\displaystyle\Rightarrow\quad$ $\displaystyle\forall
i\in[m-1]:\bar{G}_{i}\text{ has the Nash equilibrium }(t_{1},t_{2}).$ (31)

If additionally in $G_{m}$, all pure-strategy best responses to $s_{1}$ are in
$T_{2}$, and all pure-strategy best responses to $s_{2}$ are in $T_{1}$, the
reverse direction holds as well.

###### Proof.

We use the contrapositive to show “$\Rightarrow$”. Assume (31) does not hold,
and let $l$ be the maximal index such that $G_{l}$ does not have the Nash
equilibrium $(t_{1},t_{2})$. Then one player $k$ has an improving strategy
$\tilde{t}_{k}\in T_{k}$, i.e.
$\bar{u}_{k}^{l}(\tilde{t}_{k},t_{-k})>\bar{u}_{k}^{l}(t_{k},t_{-k})$.
Furthermore since $l$ is maximal, for all $i\in\\{l+1,\dots,m\\}$,
$\bar{G}_{i}$ has $(t_{1},t_{2})$ as a Nash equilibrium. So by Theorem 3.20,
$\bar{u}_{k}^{i}(\tilde{t}_{k},t_{-k})=\bar{u}_{k}^{i}(t_{k},t_{-k})$.

Denote by $\tilde{s}_{k}\in S_{k}$ the strategy for $G$ corresponding to the
restricted strategy $\tilde{t}_{k}$. Obviously for all $i\in[m-1]$,
$\bar{u}_{k}^{i}(\tilde{t}_{k},t_{-k})=u_{k}^{i}(\tilde{s}_{k},s_{-k})$. Since
all projected-game payoffs for $i>l$ stay equal by switching from $s_{k}$ to
$\tilde{s}_{k}$, but the $l$-th payoff increases, we have:

$u_{k}(\tilde{s}_{k},s_{-k})=\bigl{(}u_{k}^{1}(\tilde{s}_{k},s_{-k}),\dots,u_{k}^{l}(\tilde{s}_{k},s_{-k}),\dots,u_{k}^{m}(\tilde{s}_{k},s_{-k})\bigr{)}\\\
>_{\textsc{Rlex}}\bigl{(}u_{k}^{1}(s_{k},s_{-k}),\dots,u_{k}^{l}(s_{k},s_{-k}),\dots,u_{k}^{m}(s_{k},s_{-k})\bigr{)}=u_{k}(s_{k},s_{-k}).$

So $(s_{1},s_{2})$ is not a Nash equilibrium of $G$.

For “$\Leftarrow$”, assume that the additional condition holds. Without loss
of generality, consider an alternative strategy $\tilde{s}_{1}$ for player 1,
for which we want to show
$u_{1}(\tilde{s}_{1},s_{2})\leq_{\textsc{Rlex}}u_{1}(s_{1},s_{2})$. If
$\operatorname{supp}(\tilde{s}_{1})\nsubseteq T_{1}$, by the additional
condition, $\tilde{s}_{1}$ has in its support a non-best-response strategy to
$s_{2}$ in $G_{m}$, so it cannot be a best response by Theorem 3.20. Therefore
$u_{1}^{m}(\tilde{s}_{1},s_{2})<u_{1}^{m}(s_{1},s_{2})$. If instead
$\operatorname{supp}(\tilde{s}_{1})\subseteq T_{1}$, and $\tilde{t}_{1}\in
T_{1}$ denotes the corresponding restricted strategy, we have
$u_{1}^{m}(\tilde{s}_{1},s_{2})=u_{1}^{m}(s_{1},s_{2})$, and $\forall
i\in[m-1]:u_{1}^{i}(\tilde{s}_{1},s_{2})=\bar{u}_{1}^{i}(\tilde{t}_{1},t_{2})\leq\bar{u}_{1}^{i}(t_{1},t_{2})=u_{1}^{i}(s_{1},s_{2})$
because $(t_{1},t_{2})$ is a Nash equilibrium in every $\bar{G}_{i}$.
Therefore $u_{1}(\tilde{s}_{1},s_{2})\leq_{\textsc{Rlex}}u_{1}(s_{1},s_{2})$.
∎

The additional condition for equivalence holds in particular if $G_{m}$ is
non-degenerate (see Definition 3.24).

######  Corollary 4.48.

Let $G$ be an $m$-dimensional vector-valued bimatrix game, let $G_{m}$ have
the Nash equilibrium $(s_{1},s_{2})$ and be non-degenerate. Then
$G_{\leq_{\textsc{Rlex}}}$ has the Nash equilibrium $(s_{1},s_{2})$ if and
only if for all $i\in[m-1]$, $\bar{G}_{i}$ has the Nash equilibrium
$(t_{1},t_{2})$.

###### Proof.

Since $G_{m}$ is non-degenerate, $s_{1}$ has at most $\left|T_{1}\right|$
pure-strategy best responses, and $s_{2}$ has at most $\left|T_{2}\right|$
pure-strategy best responses. By Theorem 3.20, all strategies in $T_{2}$ are
best responses to $s_{1}$, and all strategies in $T_{1}$ are best responses to
$s_{2}$. Therefore $\left|T_{2}\right|\leq\left|T_{1}\right|$ and
$\left|T_{1}\right|\leq\left|T_{2}\right|$, which implies
$\left|T_{1}\right|=\left|T_{2}\right|$. Since neither $s_{1}$ nor $s_{2}$ can
have more than $\left|T_{1}\right|=\left|T_{2}\right|$ pure best responses,
the additional condition of Theorem 4.47 is satisfied, which yields the
equivalence. ∎

If $G_{m}$ is non-degenerate, we can also characterize _pure-strategy_ Nash
equilibria of $G_{\leq_{\textsc{Rlex}}}$.

######  Corollary 4.49.

Let $G$ be an $m$-dimensional vector-valued bimatrix game. If $G_{m}$ is non-
degenerate and $s_{1},s_{2}$ are pure strategies, the following equivalence
holds:

$G_{\leq_{\textsc{Rlex}}}$ has the Nash equilibrium
$(s_{1},s_{2})\Leftrightarrow G_{m}$ has the Nash equilibrium $(s_{1},s_{2})$.

###### Proof.

“$\Rightarrow$” holds by Lemma 4.41. For “$\Leftarrow$”, we use Corollary
4.48: Since
$\left|\operatorname{supp}s_{1}\right|=\left|\operatorname{supp}s_{2}\right|=1$,
all subgames $\bar{G}_{i},i\in[m-1]$ are games with only one strategy for each
player. They therefore trivially all have $(t_{1},t_{2})$ as Nash equilibrium.
Therefore $G_{\leq_{\textsc{Rlex}}}$ has the Nash equilibrium $(s_{1},s_{2})$.
∎

The additional condition in Theorem 4.47 cannot be left out, as the next
example shows.

######  Example 4.50.

Consider the ref-lex-game with the following player 1/player 2 payoffs:

| $b_{1}$ | $b_{2}$ | $b_{3}$
---|---|---|---
$a_{1}$ | (0, 1) | (0, 2) | (0, -1)
$a_{2}$ | (0, 2) | (0, 1) | (0, -2)
$a_{3}$ | (1, 2) | (1, 1) | (1, -3)
| $b_{1}$ | $b_{2}$ | $b_{3}$
---|---|---|---
$a_{1}$ | (0, 2) | (0, 1) | (0, 0)
$a_{2}$ | (0, 1) | (0, 2) | (0, 0)
$a_{3}$ | (-1, -1) | (-1, -1) | (-1, 0)

The game $G_{2}$ has payoffs $\left(\begin{smallmatrix}1&2&-1\\\ 2&1&-2\\\
2&1&-3\end{smallmatrix}\right)/\left(\begin{smallmatrix}\phantom{-}2&\phantom{-}1&0\\\
\phantom{-}1&\phantom{-}2&0\\\ -1&-1&0\end{smallmatrix}\right)$, and the
unique Nash equilibrium is
$(s_{1},s_{2})=\bigl{(}(\frac{1}{2},\frac{1}{2},0),(\frac{1}{2},\frac{1}{2},0)\bigr{)}$.
However not just the first and second rows are pure best responses of player 1
to $s_{2}$, but the third row is a best response as well. The game $G_{1}$ is
a simple zero-sum game with payoffs $\pm\left(\begin{smallmatrix}0&0&0\\\
0&0&0\\\ 1&1&1\end{smallmatrix}\right)$, where the third row is obviously
preferable for player 1, and player 2 has no choice over the outcomes. In the
projected subgame $\bar{G}_{1}$ with payoffs
$\pm\left(\begin{smallmatrix}0&0\\\ 0&0\end{smallmatrix}\right)$,
$(t_{1},t_{2})=\bigl{(}(\frac{1}{2},\frac{1}{2}),(\frac{1}{2},\frac{1}{2})\bigr{)}$
is clearly a Nash equilibrium, so (31) is satisfied. However in $G$, $s_{1}$
is not a best response to $s_{2}$ (giving player 1 a payoff of $(0,1.5)$),
since the strategy $(0,0,1)$ gives an $\leq_{\textsc{Rlex}}$-better payoff of
$(1,1.5)$, so $(s_{1},s_{2})$ is not a Nash equilibrium of $G$. ∎

To summarize our results: Any Nash equilibrium of a ref-lex-game $G$ must be a
Nash equilibrium of its highest-coordinate game $G_{m}$. If $G_{m}$ has a Nash
equilibrium $(s_{1},s_{2})$, then the following chain of implications holds:

$\displaystyle\forall i\in[m-1]:G_{i}\text{ has the Nash equilibrium
}(s_{1},s_{2})$ $\displaystyle\Rightarrow\quad$ $\displaystyle
G_{\leq_{\textsc{Rlex}}}\text{ has the Nash equilibrium }(s_{1},s_{2})$
$\displaystyle\Rightarrow\quad$ $\displaystyle\forall
i\in[m-1]:\bar{G}_{i}\text{ has the Nash equilibrium }(t_{1},t_{2}).$

The second implication clearly places strict requirements on ref-lex-games to
have mixed-strategy Nash equilibria. For any such game
$G_{\leq_{\textsc{Rlex}}}$, there are two possibilities: Either $G_{m}$, and
therefore $G_{\leq_{\textsc{Rlex}}}$, has a pure Nash equilibrium. Otherwise
if $G_{m}$ only has a mixed Nash equilibrium, the same equilibrium must be
supported by all projected subgames $\bar{G}_{i}$ in order for
$G_{\leq_{\textsc{Rlex}}}$ to have a Nash equilibrium at all.

#####  10.1.1 Nash Equilibria in Distribution-Valued Tail-Order Games

These results for ref-lex-ordered games have the important consequence for
distribution-valued games that even those distribution-valued games whose
payoff distributions have only finite support do not have Nash equilibria in
general. A concrete example of this was already given in Example 4.40: The
payoff vectors all sum to $1$ (i.e. represent probability distributions), so
the game is isomorphic to a distribution-valued game. As the existence of Nash
equilibria already fails to hold in the case of such simple distributions, it
also fails to hold in more general cases. For example, any game where the
payoffs have finite common support can be converted to an isomorphic game with
absolutely continuous payoffs by performing a convolution with an absolutely
continuous distribution supported on $[-\varepsilon,\varepsilon]$ for some
small enough $\varepsilon$. This is illustrated in Figure 4. Therefore, games
with absolutely continuous payoffs certainly also fail to have Nash equilibria
in general.

$\shortrightarrow$

Figure 4: Masses of discrete distributions $P_{1},P_{2}$ (gray/green) on
$\\{2,\dots,6\\}$, and densities of corresponding absolutely continuous
distributions $\tilde{P}_{1},\tilde{P}_{2}$ obtained by convolution. Here
$P_{1}\succ_{\text{tail}}P_{2}$, and equivalently
$\tilde{P}_{1}\succ_{\text{tail}}\tilde{P}_{2}$.

The results of this section contradict an algorithm given in [Ras15a, Section
3.1] which supposedly calculates Nash equilibria of distribution-valued games
111111More precisely, _multi-goal security strategies_ (MGSS) for
distribution-valued games. This is in a model where multiple objectives in
form of multiple distributions are allowed, but the definition of a MGSS given
in [Ras15, Definition 4.1] coincides with a Nash equilibrium if the number of
objectives is one.. A similar algorithm is implemented in the R package
_HyRiM_ (see [RKA20]), a package that implements algorithms for distribution-
valued games and which we will use in the next chapter. It is not completely
clear what solutions the algorithm outputs for games without Nash equilibria,
but it appears as if a Nash equilibrium of the highest-coordinate projection
$G_{m}$ is calculated.

####  10.2 Probability that Lexicographically-Ordered Games have Nash
Equilibria

In light of the strict requirements for ref-lex games to have non-pure Nash
equilibria, one may wonder “how many” ref-lex games even have such equilibria.
It even seems plausible that “almost no” ref-lex game has a non-pure Nash
equilibrium. This is indeed the case in a certain precise sense, and is
formalized here in probabilistic way, similar to Theorem 3.15: We show that
the probability that a randomly chosen $G_{\leq_{\textsc{Rlex}}}$ has a Nash
equilibrium is the same as the probability that $G_{m}$ has a _pure_ Nash
equilibrium, or in other words, that $G_{\leq_{\textsc{Rlex}}}$ has a non-pure
Nash equilibrium with probability zero.

######  Theorem 4.51.

Let $m\geq 2$ be fixed and let $P\in\mathcal{D}$ be an absolutely continuous
probability distribution. Let $G$ be an $m$-dimensional vector-valued bimatrix
game where all entries of all payoff vectors are picked iid from the
distribution $P$. Then

$\displaystyle P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a Nash
equilibrium}\\})=P(\\{\textit{\small$G_{m}$ has a pure Nash equilibrium}\\}),$
(34) $\displaystyle P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a non-
pure Nash equilibrium}\\})=0.$ (35)

###### Proof.

If $G_{\leq_{\textsc{Rlex}}}$ has a Nash equilibrium, we first distinguish
whether or not it has a pure equilibrium. If it has a pure equilibrium, by
Corollary 4.49 this is equivalent to $G_{m}$ having a pure equilibrium.
Therefore we get:

$\displaystyle P(\\{\textit{$G_{\leq_{\textsc{Rlex}}}$ \small has a Nash
equilibrium}\\})=P(\\{\textit{\small$G_{m}$ has a pure Nash equilibrium}\\})$
$\displaystyle+\leavevmode\nobreak\ $ $\displaystyle
P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a non-pure Nash equilibrium
and no pure Nash equilibria}\\}).$

The second probability on the right can be bounded from above by leaving out
one condition:

$P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a non-pure Nash equilibrium
and no pure Nash equilibria}\\})\\\ \leq
P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a non-pure Nash
equilibrium}\\})$

To conclude the proof of both (34) and (35), it remains to show that this
probability vanishes. One can show that $P(\\{\textit{\small$G_{m}$ is
degenerate}\\})=0$ (this is hinted at in [Ste07, p.54], which states that
“almost all” games with real-valued payoffs are non-degenerate; we refrain
from giving a proof here). Since $G_{m}$ is non-degenerate almost surely, we
can assume that $G_{m}$ is non-degenerate in our calculations without changing
the probabilities.

Assume $G_{\leq_{\textsc{Rlex}}}$ has a non-pure Nash equilibrium. By
Corollary 4.48, since we assume $G_{m}$ is non-degenerate, this is equivalent
to the statement that $G_{m}$ has a non-pure Nash equilibrium $(s_{1},s_{2})$
such that for all $i\in[m-1]:\bar{G}_{i}\text{ has the Nash equilibrium
}(t_{1},t_{2})$. Denote by $N_{G_{m}}$ the set of Nash equilibria of $G_{m}$.
We can now further calculate the probabilities:

$\displaystyle P(\\{\textit{\small$G$ has a non-pure Nash equilibrium}\\})$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
P(\\{\textit{\small$\exists s\in N_{G_{m}}$ non-pure such that $\forall
i\in[m-1]:\bar{G}_{i}$ has the Nash equilibrium $t$}\\})$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
P(\\{\textit{\small$\exists s\in N_{G_{m}}$ non-pure such that $\bar{G}_{m-1}$
has the Nash equilibrium $t$}\\}).$ (36)

Next we show that for any specific non-pure strategy profile
$s=(s_{1},s_{2})\in N_{G_{m}}$, there is zero probability that $\bar{G}_{m-1}$
has the Nash equilibrium $t=(t_{1},t_{2})$. Since $s$ is non-pure and $G_{m}$
can be assumed to be non-degenerate, we have that
$r\coloneqq\left|\operatorname{supp}s_{1}\right|=\left|\operatorname{supp}s_{2}\right|\geq
2$. We decompose the restricted strategy $t_{2}$ of player 2 into the weights
it assigns to the pure strategies: $t_{2}\eqqcolon(q_{1},\dots,q_{r})$. Assume
that $\bar{G}_{m-1}$ has payoff matrices $(X_{ij})_{i,j\in[r]}$ for player 1
and $(Y_{ij})_{i,j\in[r]}$ for player 2, where the $X_{ij}$, $Y_{ij}$ are the
randomly-picked, iid absolutely-continuously-distributed payoff entries. By
the equation (6), if $\bar{G}_{m-1}$ has the equilibrium $(t_{1},t_{2})$, it
is necessary that $t_{2}$ makes player 1 indifferent between the first two
rows:

$\displaystyle\sum_{j=1}^{r}X_{1j}q_{j}=\sum_{j=1}^{r}X_{2j}q_{j}.$

Therefore,

$\displaystyle P(\\{\textit{\small$\bar{G}_{m-1}$ has the Nash equilibrium
$t$}\\})\leq
P\biggl{(}\biggl{\\{}X_{1j}=\frac{1}{q_{j}}\biggl{(}\sum_{j=1}^{r}X_{2j}q_{j}-\sum_{j=2}^{r}X_{1j}q_{j}\biggr{)}\biggr{\\}}\biggr{)}.$

The last probability can further be represented as the probability that
$\tilde{X}\coloneqq(X_{11},\dots,X_{1r},X_{21},\dots,X_{2r})$ lies on a
specific hyperplane in $\mathbb{R}^{2r}$. The Lebesgue measure of such a plane
is zero. The random vector $\tilde{X}$ is absolutely continuous as a tuple of
independent, absolutely continuous random variables. This implies that the
probability that $\tilde{X}$ lies in a Lebesgue null set is zero. We can
therefore conclude that $P(\\{\textit{\small$\bar{G}_{m-1}$ has the Nash
equilibrium $t$}\\})=0$.

We use this to show that the probability in (36) is zero. Recall from the
algorithm in Section 6.1 that in a non-degenerate game, there can be at most
one Nash equilibrium for each pair of index sets $(I,J)$ indexing the pure
strategy sets $S_{1},S_{2}$ with $\left|I\right|=\left|J\right|$. Write
$\mathcal{I}$ for the set of all such $(I,J)$ with
$\left|I\right|=\left|J\right|\geq 2$. For some $(I,J)\in\mathcal{I}$, write
$s_{I,J}$ for the Nash equilibrium of $G_{m}$ supported in $I,J$ if it exists,
and $s_{I,J}\coloneqq\bot$ (“undefined”) otherwise. Write $t_{I,J}$ for the
respective restricted strategy profile. With this notation, we can calculate:

$\displaystyle P(\\{\textit{\small$\exists s\in N_{G_{m}}$ non-pure such that
$\bar{G}_{m-1}$ has the Nash equilibrium $t$}\\})$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
P\left(\bigcup_{(I,J)\in\mathcal{I}}\\{\textit{\small$G_{m}$ non-degenerate,
$s_{I,J}\neq\bot,\bar{G}_{m-1}$ has the Nash equilibrium $t_{I,J}$}\\}\right)$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\sum_{(I,J)\in\mathcal{I}}P(\\{\textit{\small$G_{m}$ non-
degenerate, $s_{I,J}\neq\bot,\bar{G}_{m-1}$ has the Nash equilibrium
$t_{I,J}$}\\})$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{(I,J)\in\mathcal{I}}0=0.$

These calculations show that $P(\\{\textit{\small$G$ has a non-pure Nash
equilibrium}\\})=0$. ∎

######  Remark 4.52.

We can use Theorem 3.15 to calculate the probability that $G_{m}$ has a pure
Nash equilibrium: If the players have $l$ and $n$ pure strategies, (34) gives

$\displaystyle P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a Nash
equilibrium}\\})=1-\sum_{k=0}^{\min(l,n)}(-1)^{k}k!\binom{l}{k}\binom{n}{k}\left(\frac{1}{nl}\right)^{k}\xrightarrow{l,n\to\infty}1-\frac{1}{e}.$

If we consider randomly-generated zero-sum games instead, the proof of Theorem
4.51 works as well. In this case,

$\displaystyle P(\\{\textit{\small$G_{\leq_{\textsc{Rlex}}}$ has a Nash
equilibrium}\\})=\frac{l!n!}{(l+n-1)!}\xrightarrow{l,n\to\infty}0.$

####  10.3 Kakutani’s Theorem and Lexicographically-Ordered Games

In [Ras15, p.29-30] and [RKS15, Theorem 3], it is argued that the existence of
mixed-strategy Nash equilibria for distribution-valued games follows from
_Glicksberg’s Theorem_ (see [FT91, Theorem 1.3]). This theorem is a
generalization of Nash’s existence theorem, as it guarantees the existence of
Nash equilibria for games with continuous payoff functions and strategy sets
that are compact subsets of a metric space. However it assumes real-valued
payoffs and can not simply be applied to distribution-valued payoffs.

Glicksberg’s theorem extends Kakutani’s fixed point theorem that was used in
the proof of Theorem 3.16 to show that all real-valued games have a mixed-
strategy Nash equilibrium. The application of Kakutani’s theorem, however, did
not depend on the payoff space: The proof idea of Theorem 3.16 can in
principle be applied to other, arbitrary payoff models. This is because
Kakutani’s fixed point theorem worked on the best-reply correspondence
$r:\Delta\to\operatorname{\mathcal{P}}(\Delta)$, which maps real-valued
vectors to sets of real-valued vectors. Since these real-valued vectors do not
represent payoffs, but mixed-strategy profiles, the function signature of $r$
does not depend on the payoffs being real numbers.

Since the theorem could in principle be applied, but tail-ordered
distribution-valued games (and more specifically, ref-lex-ordered vector-
valued games) do not have mixed-strategy Nash equilibria in general, some
condition of Kakutani’s theorem must be violated. It turns out that the
property that fails to hold with a lexicographic ordering is that $r$ must
have a _closed graph_. The inherent reason for this is that
$\leq_{\textsc{Rlex}}$ is not closed as a subset of $(\mathbb{R}^{m})^{2}$:
For example, $(0,1/n)\geq_{\textsc{Rlex}}(1,0)\leavevmode\nobreak\ \forall
n\in\mathbb{N}$, but in the limit as $n\to\infty$,
$(0,0)<_{\textsc{Rlex}}(1,0)$. (Recall that in the proof where Kakutani’s
theorem was used, we explicitly mentioned that $\leq$ as subset of
$\mathbb{R}^{2}$ is closed – often stated as the “sandwich theorem” – but this
does not hold for a lexicographic ordering).

This missing property of the ordering in turn leads to $r$ not having a closed
graph. For example, again consider the game from Example 4.40, with a Nash
equilibrium
$(s_{1},s_{2})=\left((\frac{2}{3},\frac{1}{3}),(\frac{1}{3},\frac{2}{3})\right)$.
If we define a sequence of player-2-strategies converging to $s_{2}$ by
$s_{2}^{(n)}\coloneqq\left(\frac{1}{3}+\frac{1}{2n},\frac{2}{3}-\frac{1}{2n}\right),n\in\mathbb{N}$,
then one can calculate that in $G_{3}$, player 1’s only best response to each
$s_{2}^{(n)}$ is the strategy $(0,1)$, since the second row gives slightly
bigger payoff than the first row (yet, both converge to the same limit with
increasing $n$, one from above and one from below). Therefore $(0,1)$ is also
the unique best response in $G$. However in the limit, the highest-coordinate
payoffs of both rows become equal, and the second coordinate makes the first
row preferable by $\leq_{\textsc{Rlex}}$ (as already calculated in Example
4.40 before). Therefore $(1,0)$ is the unique best response to $s_{2}$. This
shows that $r$ does not have a closed graph.

##  Chapter 5 Tweaking the Stochastic Order: Segmenting Loss Distributions

###  11 The Tweakable Stochastic Order

A modification of the ideas on distribution-valued games and the stochastic
order was proposed by Ali Alshawish in [AM19]. The motivation for the proposed
idea is the insight that the tail order can only capture a pessimistic
viewpoint: As its name says, the decision is based entirely on the _tail_ of
the distribution. Since it is applied to loss functions, an arbitrarily small
probability of a high loss can overshadow everything further to the left. In
other words, the ordering only takes the worst-case scenario into account.

The _tweakable stochastic order_ defined in [AM19], on the other hand, is
designed such that it can be tweaked to a decision maker’s risk attitude,
represented by a utility function. For finitely-supported distributions, it
can represent as special cases the maximally risk-averse
$\preccurlyeq_{\text{tail}}$, and the expected-value-ordering
$\preccurlyeq_{E}$ (see Example 4.11) which is considered risk-neutral.

We define the tweakable stochastic order $\preccurlyeq_{\text{\tiny
tw,$\scriptscriptstyle\mathcal{I}$}}$, slightly adjusted to match the
framework presented so far. Let $[a,b]$ be an interval where $a<b$. Let
$\mathcal{I}$ be an partition of that interval, i.e. a finite subset of
$[a,b]$ with elements $a=x_{1}<x_{2}<\dots<x_{m}<x_{m+1}=b$. For
$P\in\mathcal{D}$ and some Borel set $A\in\mathcal{B}$, let
$E_{A}(P)\coloneqq\int_{A}x\,dP(x)$ be its expected value if restricted to
$A$.

######  Definition 5.1.

Let $P_{1},P_{2}\in\mathcal{D}_{[a,b]}$ be probability measures. Then the
_tweakable stochastic order_ $\preccurlyeq_{\text{\tiny
tw,$\scriptscriptstyle\mathcal{I}$}}$ given the partition $\mathcal{I}$ is
defined by

$\displaystyle P_{1}\preccurlyeq_{\text{\tiny
tw,$\scriptscriptstyle\mathcal{I}$}}P_{2}\mathrel{\vcentcolon\Leftrightarrow}\bigl{(}E_{[x_{1},b]}(P_{1}),\dots,E_{[x_{m},b]}(P_{1})\bigr{)}\leq_{\textsc{Rlex}}\bigl{(}E_{[x_{1},b]}(P_{2}),\dots,E_{[x_{m},b]}(P_{2})\bigr{)}.$

Distributions not in $\mathcal{D}_{[a,b]}$ are incomparable by
$\preccurlyeq_{\text{\tiny tw,$\scriptscriptstyle\mathcal{I}$}}$.

The definition uses overlapping intervals
$[x_{1},b],[x_{2},b],\dots,[x_{m},b]$. In each of these intervals, it takes
the expected value; the resulting vectors are compared by the reflected
lexicographic order. Alternatively, we can partition $[a,b]$ into intervals
$[x_{1},x_{2}),[x_{2},x_{3}),\dots,[x_{m},b]$, which is equivalent since a
lexicographic comparison is used:

######  Lemma 5.2.

Let $P_{1},P_{2}\in\mathcal{D}_{[a,b]}$. Then

$\displaystyle\bigl{(}E_{[x_{1},x_{2})}(P_{1}),\dots,E_{[x_{m},b]}(P_{1})\bigr{)}\;$
$\displaystyle\leq_{\textsc{Rlex}}\bigl{(}E_{[x_{1},x_{2})}(P_{2}),\dots,E_{[x_{m},b]}(P_{2})\bigr{)}$
$\displaystyle\Longleftrightarrow\quad$
$\displaystyle\bigl{(}E_{[x_{1},b]}(P_{1}),\dots,E_{[x_{m},b]}(P_{1})\bigr{)}$
$\displaystyle\leq_{\textsc{Rlex}}\bigl{(}E_{[x_{1},x_{2})}(P_{2}),\dots,E_{[x_{m},b]}(P_{2})\bigr{)}.$

###### Proof.

Observe that for any $P_{l}$ ($l=1,2$),
$E_{[x_{k},b]}(P_{l})=\bigl{(}\sum_{i=k}^{m-1}E_{[x_{i},b)}(P_{l})\bigr{)}+E_{[x_{m},b]}(P_{l})$
for all $k\in[m]$. The reflected lexicographic ordering considers the $k$-th
coordinate if and only if all higher coordinates are equal in both vectors: In
this case, above sum representation implies that
$E_{[x_{k},b]}(P_{1})<E_{[x_{k},b]}(P_{2})\Leftrightarrow
E_{[x_{k},x_{k+1})}(P_{1})<E_{[x_{k},x_{k+1})}(P_{2})$, and analogously
$E_{[x_{k},b]}(P_{1})=E_{[x_{k},b]}(P_{2})\Leftrightarrow
E_{[x_{k},x_{k+1})}(P_{1})=E_{[x_{k},x_{k+1})}(P_{2})$. In other words, it
does not matter for the ordering if values of higher coordinates are
added/subtracted to lower coordinates consistently on both sides. ∎

Considering that $\preccurlyeq_{\text{tail}}$ is “essentially lexicographic”
in the sense of Theorems 4.17, 4.18, and Corollary 4.20,
$\preccurlyeq_{\text{\tiny tw,$\scriptscriptstyle\mathcal{I}$}}$ can be
understood as a coarser version of the tail order, in which the ordering
decision is made considering probabilities in larger regions lexicographically
instead of only considering single points. Since $\leq_{\textsc{Rlex}}$ is
total, $\preccurlyeq_{\text{\tiny tw,$\scriptscriptstyle\mathcal{I}$}}$ is a
total order on $\mathcal{D}_{[a,b]}$ (yet obviously not on $\mathcal{D}$). It
is not antisymmetric, since it is indifferent between any two distributions
with equal expected values in each of the partition intervals.

The order can be “tweaked” to a decision maker’s risk attitude by choosing
suitable partitioning points $\mathcal{I}$. [AM19] presents a method based on
the decision-theoretic tool of utility functions that model risk-averse or
risk-seeking behavior. The utility function $u:[a,b]\to\mathbb{R}$ is assumed
to be continuous, monotonically increasing, and without loss of generality
$u([a,b])=[0,1]$. The proposed method partitions the range $[0,1]$ of $u$ into
$m$ equally-sized intervals, with partition points
$\\{\frac{1}{m},\dots,\frac{m-1}{m}\\}$, and constructs
$\mathcal{I}=\\{a,x_{2},x_{3},\dots,x_{m},b\\}$ such that
$u(x_{i})=\frac{i-1}{m}$ for $i=2,\dots,m$. In other words, the points $x_{i}$
in $\mathcal{I}$ are defined as the $\frac{i-1}{m}$-quantiles of $u$,
analogously to quantiles of probability distribution functions. Then
$\preccurlyeq_{\text{\tiny tw,$\scriptscriptstyle\mathcal{I}$}}$ is the
tweakable stochastic order tweaked to the utility function $u$.

###  12 Games with Multiple Distribution Segments as Objectives

The stochastic order $\preccurlyeq_{\text{\tiny
tw,$\scriptscriptstyle\mathcal{I}$}}$ can of course be used to order
distribution-valued games in the sense of Definition 4.12, which was the
approach chosen in [AM19]. In a new approach, we will use the segmentation
idea in a different way and define multi-objective games: Each of the
segments’ expected values will be viewed as a distinct objective to be
minimized.

####  12.1 Multi-Objective Games and Pareto-Nash Equilibria

Of course in such a multi-objective setting, one cannot hope to be able to
minimize all objectives at once. Quite possibly, one objective can only take
on its minimal value if another objective is not minimal. A common way to deal
with this is to consider _Pareto-optimal_ solutions: A vector is Pareto-
optimal if no improvement in any coordinate is possible without making another
coordinate worse. Phrased in a different way, a vector is Pareto-optimal if no
other of the vectors in consideration _dominates_ it in all coordinates. For
example, if one considers the set
$\\{v_{1}=(4,2,4),v_{2}=(2,2,2),v_{3}=(0,0,5)\\}$, the Pareto-minimal vectors
are $v_{2}$ and $v_{3}$, while $v_{1}$ is dominated by $v_{2}$ which has
smaller or equal values in all coordinates.

######  Definition 5.3.

Define the preorder

$\displaystyle x\leq_{\text{par}}y\leavevmode\nobreak\ $
$\displaystyle\mathrel{\vcentcolon\Leftrightarrow}\leavevmode\nobreak\ \exists
i:x_{i}<y_{i}\vee x=y.$

We have $x\leq_{\text{par}}y$ if $x$ is dominated by $y$ in at least one
coordinate. Note that $\leq_{\text{par}}$ is not antisymmetric: E.g. if
$x_{1}<y_{1}$ and $y_{2}<x_{2}$, then $x\leq_{\text{par}}y$ and
$y\leq_{\text{par}}x$. We have $x<_{\text{par}}y$ iff $x\leq_{\text{par}}y$
and not $y\geq_{\text{par}}x$, i.e. if $x$ is dominated by $y$ in all
coordinates, and strictly dominated in at least one. The set of Pareto-minimal
elements in a set $S\subseteq\mathbb{R}^{m}$ is given by:

$\displaystyle\\{x\in S\mid\forall y\in S:x\leq_{\text{par}}y\\}.$

The notion of multi-objective games was pioneered by David Blackwell in
[Bla56], and Lloyd Shapley defined the concept of multi-objective equilibria
in the Pareto-optimal sense in [SR59] (yet the terminology of Pareto
optimality was only later associated with it). We can use our framework of
games with generalized payoffs together with the order $\leq_{\text{par}}$ to
formalize this equilibrium concept.

######  Definition 5.4.

Let $G$ be a vector-valued game as in Definition 4.35, i.e. a game with
generalized payoffs in $\mathbb{R}^{m}$. We call the Nash equilibria of $G$
with respect to $\leq_{\text{par}}$ _Pareto-Nash equilibria_ (cf. [LSZ05]). In
this context, we also call $G$ a _multi-objective game_.

######  Remark 5.5.

A Pareto-Nash equilibrium can be interpreted as a strategy profile where no
player can deviate to a different strategy and get a strictly better payoff in
one coordinate without getting a strictly poorer payoff in another. Definition
5.4 does not allow different players to have a different number of objectives
$m_{1},\dots,m_{n}$: We do not explicitly model this case to avoid cumbersome
additional notation. However such payoffs can be represented by letting
$m\coloneqq\max_{i\in[n]}m_{i}$, and padding all lower-dimensional payoff
vectors with zeroes so they lie in $\mathbb{R}^{m}$.

An important result from Shapley’s paper [SR59] is that Pareto-Nash equilibria
can be found by transforming the multi-objective game into a real-valued game
via a weighted sum of the different objectives. In particular, the Pareto-Nash
equilibria are exactly the equilibria of such weighted games for different
weight vectors.

######  Theorem 5.6 (Characterization of Pareto-Nash equilibria, cf. [SR59,
LSZ05]).

Let $G$ be a mixed-extension multi-objective game with $n$ players and payoffs
in $\mathbb{R}^{m}$. For some $0\neq w_{1},\dots,w_{n}\in\mathbb{R}_{\geq
0}^{m}$, denote by $\tilde{G}^{w_{1},\dots,w_{n}}$ the real-valued game with
payoff functions $\tilde{u}_{k}:s\mapsto\left\langle
u_{k}(s),w_{k}\right\rangle$ (taking the weighted sum of objectives in
$u_{k}(s)$ by weights in $w_{k}$;
$\left\langle\,\cdot\,,\,\cdot\,\right\rangle$ denotes the dot product on
$\mathbb{R}^{m}$). Then some strategy profile $s\in S$ is a Pareto-Nash
equilibrium of $G$ if and only if it is a Nash equilibrium of
$\tilde{G}^{w_{1},\dots,w_{n}}$ for some weights $w_{1},\dots,w_{n}$.
121212The theorem can be generalized further, see [SR59, LSZ05]: Instead of
mixed-extension games, we could allow arbitrary games with continuous payoff
functions defined on some convex strategy set. Also we can restrict ourselves
to weight vectors whose entries sum to 1, as scaling the payoffs of a real-
valued game by a positive scalar preserves equilibria.

The characterization gives rise to a simple algorithm which finds one Pareto-
Nash equilibrium, as we can simply pick arbitrary weights $w_{1},\dots,w_{m}$
and apply one of the usual algorithms to find Nash equilibria in real-valued
games. However, it also shows that the equilibrium heavily depends on how the
players weigh their objectives. Since there are infinitely many weight
vectors, we cannot rule out that there can be infinitely many Pareto-Nash
equilibria.

It is not in the scope of this work to examine the set of Pareto-Nash
equilibria in detail, but it is interesting to at least have some idea of its
possible structure, the number of different equilibria and their
relationships. To get some intuition of which Pareto-Nash equilibria a game
can have, we experiment with different weights and visualize the resulting
equilibria profiles in a plot where the strategies in the profile are
represented as dots. Figure 5 shows examples of such plots for randomly
generated 2-player games with 3 pure strategies for each player, and a varying
number $m$ of objectives: For each equilibrium profile, the strategies of
player 1/2 are represented by a red/green dot, respectively, projected from
the two-dimensional mixed-strategy-simplex in three-dimensional space to the
plane (the corners represent pure strategies). The examples showcase the
possible complexity of the set of Pareto-Nash equilibria: In one of the games,
all equilibria mix between at most two of the three strategies; in others,
equilibria seem to follow certain patterns which can be recognized in the
visual representation. One could hope that while Pareto-Nash equilibria are
not unique, they at least concentrate on a small number of points – however
the examples show that this is not the case in general, as there are many
different equilibrium points in all examples. Another observation is that in
all cases, there are equilibrium profiles far apart from another, so Pareto-
Nash equilibria of the same game obtained by different weightings need not be
“close”, but can be completely different. In particular, this motivates that
for an algorithm which calculates a specific Pareto-Nash equilibrium, it is
reasonable to take a weighting vector as input instead of choosing one on its
own.

(a) Zero-Sum Game, $m=5$

(b) Zero-Sum Game, $m=2$

(c) Non-Zero-Sum Game, $m=3$

(d) Zero-Sum Game, $m=5$, no equilibria mixing between all three strategies
found

Figure 5: Different sets of Pareto-Nash equilibria visualized (10 000 points
each)

####  12.2 Multi-Objective Segmented-Distribution Games

Putting the pieces together, we construct the multi-objective game based on
loss distribution segments as follows: Let $G$ be a distribution-valued
bimatrix game with payoffs from $\mathcal{D}_{[a,b]}$, $a<b$, and let
$\mathcal{I}=\\{a,x_{2},x_{3},\dots,x_{m},b\\}$ be a partition of the interval
$[a,b]$.

Define the _segment game_ $G_{\text{seg,$\mathcal{I}$}}$ as a multi-objective
game with the same strategies as in $G$, where each player $k$ has the utility
function:

$\displaystyle
u_{\text{seg},k}:S\to\mathbb{R}^{m},s\mapsto-\bigl{(}E_{[a,x_{2})}(u_{k}(s)),E_{[x_{2},x_{3})}(u_{k}(s)),\dots,E_{[x_{m},b]}(u_{k}(s))\bigr{)}.$
(37)

We negate the vector as we are in the context of loss distributions, but want
to stick to the convention that utilities should be maximized. As outlined in
the previous section, we can find Pareto-Nash equilibria of
$G_{\text{seg,$\mathcal{I}$}}$ by weighing the different objectives and then
solving the resulting real-valued game. This approach is implemented for the
thesis in the language R, and the following describes the details of the
implementation.

The R package _HyRiM_ [RKA20] by Stefan Rass, Sandra König and Ali Alshawish
was developed along with the papers [Ras15, Ras15a, Ras17] and implements data
structures and algorithms for distribution-valued games. In particular, it
provides the class lossDistribution that represents finitely-supported
discrete and absolutely continuous loss distributions. Absolutely continuous
distributions are approximated by a kernel density estimation method: Given a
finite number of samples, their distribution’s density function is
approximated as a convex combination of Gaussian densities. The package also
provides the class mosg that represents distribution-valued games, and
implements the computation of Nash equilibria for real-valued games. The
abbreviation stands for _multi-objective security game_ , as the package
(unlike the presentation in this thesis) allows to define games with multiple
distribution-valued objectives.

We implement the multi-objective segmentation-based games in the context of
the HyRiM package, and as a possible extension to it. As the package focuses
on zero-sum games, we also restrict ourselves to zero-sum segmented games.
Multi-objective segmented games are represented by the moseg class. Such a
game can be created from a single-objective distribution-valued game of the
built-in mosg class, and a vector of partition points. Loss distributions are
turned into real-valued expectation vectors by (37): This is implemented in
the function segmentedLossDistribution, which takes in a lossDistribution
object and the partition points and returns the expectation vector. Computing
the expected value is straightforward in the case of finitely-supported
discrete distributions as a sum. For absolutely continuous distributions, the
numerical integration function integrate provided by R is used. Finally, the
method moseg.paretoNashEquilibrium computes a Pareto-Nash equilibrium of a
moseg game, given a vector of weights as inputs. It first scalarizes the game
based on the weights. Then for the actual equilibrium computation, it utilizes
the HyRiM built-in method mgss which implements equilibrium computation for
real-valued games.

The three methods are implemented in the file multiobjectiveSegmentGame.R. The
source code is shown on the following pages.

###### Creation of Segmented Game

The code for creating a moseg game:

⬇

13moseg <- function(sosg, partitionPoints) {

14 moseg <- NULL

15 if (sosg$dim != 1) {

16 stop("only single-objective games can be turned into a multi-objective
segment game.")

17 }

18 # Convert the loss-distribution payoffs into expectation vectors of the
segments

19 moseg$losses <- mapply(

20 function(l) segmentedLossDistribution(l, partitionPoints),

21 sosg$losses)

22 moseg$partitionPoints <- partitionPoints

23

24 # Copy other properties from the original game

25 moseg$nDefenses <- sosg$nDefenses

26 moseg$nAttacks <- sosg$nAttacks

27 moseg$defensesDescriptions <- sosg$defensesDescriptions

28 moseg$attacksDescriptions <- sosg$attacksDescriptions

29 class(moseg) <- "moseg"

30 moseg

31}

###### Computing Expectation Vectors

The code for converting a lossDistribution to a segment expectation vector is
given in the next listing. The implementation relaxes the requirement made in
the definition of $G_{\text{seg,$\mathcal{I}$}}$ that the interval $[a,b]$
must cover the whole support of all distributions involved: Since absolutely
continuous distributions are estimated as combination of Gaussian kernels,
their support will always be the whole real line. Instead of placing an
arbitrary restriction on the partition (e.g., 99% of the probability mass must
lie in $[a,b]$), we prefer to give the user the flexibility to choose the
partition freely. To make this behavior consistent, the same is allowed for
discrete distributions. Unlike in (37), the expectation vectors need not be
negated in the implementation, because the HyRiM packages already interprets
payoffs as losses.

⬇

67segmentedLossDistribution <- function(lossDistribution, partitionPoints) {

68 segmentedDistribution <- NULL

69 expectedValues <- rep(0, length(partitionPoints) - 1)

70

71 # Check that there are at least two partition points

72 if (length(partitionPoints) <= 1) {

73 stop("at least two partition points required.")

74 }

75 # Check that the partition points are in ascending order

76 for (i in 1:(length(partitionPoints) - 1)) {

77 if (partitionPoints[i+1] <= partitionPoints[i]) {

78 stop("partition points must be in ascending order.")

79 }

80 }

81

82 # Compute expected values in the discrete, finitely-supported case

83 if (lossDistribution$is.discrete) {

84 supp <- lossDistribution$supp

85 pdf <- lossDistribution$dpdf

86 i <- 1 # Index of the current support point

87 j <- 2 # Index of the right end of the current partition

88

89 # Skip support points left of the first partition

90 while (supp[i] < partitionPoints[1]) {

91 i <- i + 1

92 }

93

94 while (i <= length(supp) && j <= length(partitionPoints)) {

95 # All intervals except the last one are half-open, the last one is closed.

96 if (supp[i] < partitionPoints[j] || (supp[i] == partitionPoints[j] && j ==
length(partitionPoints))) {

97 expectedValues[j - 1] <- expectedValues[j - 1] + supp[i] * pdf[i]

98 i <- i + 1 # Go to the next support point

99 } else {

100 j <- j + 1 # Go to the next partition

101 }

102 }

103 }

104 # Compute expected values in the absolutely-continuous case

105 else {

106 density <- lossDistribution$lossdistr

107 # Go over all partition intervals

108 for (i in 1:(length(partitionPoints) - 1)) {

109 # Numerically calculate the integral. The normalizationFactor is
calculated by HyRiM since the kernel-estimated densities often do not
integrate to 1 on the specified support.

110 integral <- integrate(density, partitionPoints[i], partitionPoints[i+1])

111 expectedValues[i] <- integral$value * lossDistribution$normalizationFactor

112 }

113 }

114 segmentedDistribution$expectedValues <- expectedValues

115 class(segmentedDistribution) <- "segmentedLossDistribution"

116 return(segmentedDistribution)

117}

###### Computing Pareto-Nash Equilibria

The code for computing Pareto-Nash equilibrium of a moseg based on weights is
shown in the next listing.

⬇

42moseg.paretoNashEquilibrium <- function(moseg, weights) {

43 if (length(weights) != length(moseg$partitionPoints) - 1) {

44 stop(sprintf("there are %d segments, but %d weights were specified.",

45 length(moseg$partitionPoints) - 1, length(weights)))

46 }

47 # Scalarize the game with the given weights

48 scalarLosses <- rep(0, length(moseg$losses))

49 for (i in 1:length(scalarLosses)) {

50 scalarLosses[i] <- moseg$losses[i]$expectedValues %*% weights

51 }

52 scalarGame <- mosg(n=moseg$nDefenses, m=moseg$nAttacks, goals=1,
losses=scalarLosses)

53 # Compute an equilibrium of the scalar game using HyRiM’s built-in
algorithm

54 mgss(scalarGame)

55}

###### Examples

Examples of using the code are supplied in the file _mosegExamples.R_. There
are two examples: The first example constructs a 2x2 two-player zero-sum game
with discrete distributions supported on $\\{1,\dots,10\\}$ as payoffs. The
second example constructs a 2x2 two-player zero-sum game with absolutely
continuous distributions as payoffs. In both cases, a segmented game is
created and the Pareto-Nash equilibrium given a fixed weights vector is
computed. For comparison, the “MGSS” (_Multi-Goal Security Strategy_) solution
the HyRiM-built-in method mgss computes is output as well.

##  Chapter 6 Conclusion

The model of distribution-valued games provides a valuable tool to model games
in uncertain situations where the exact outcomes cannot be known beforehand,
but can only be modeled on a stochastic basis. Of course, the usefulness of
this model depends heavily on the ability to specify suitable preferences in
the form of stochastic orders, and the thesis shows that this is a critical
point and that the currently considered orderings have some shortcomings. In
particular, two problems with the tail order were identified: The first issue
is that the order is not total unless one restricts the order space, and in
particular for any non-degenerate interval $[a,b]\subseteq[0,\infty)$, there
are incomparable distributions supported on $[a,b]$. The second issue is that
tail-ordered games can fail to have Nash equilibria, and that mixed-strategy
Nash equilibria only exist for games with a specific structure.

Neither of the two issues is grave enough to stop the tail order from being
useful: The first problem is rather of mathematical than of practical
importance, and it seems plausible that the cases where the order exhibits
incomparability will rarely, if ever, occur in practice. The problem can even
be circumvented altogether if one identifies a smaller class of admissible
distributions, and shows that the ordering is total within that class (of
course, some work is required if one wants to show the totality on such a
smaller class – further work could try to identify easy-to-check sufficient
conditions for the order to be total on such a class). The second problem is
more severe: The famous theorem by John Nash that all real-valued games have
at least one Nash equilibrium is a cornerstone of the classical theory, and it
certainly has practical implications that there is no equivalent for tail-
ordered distribution-valued games. Yet the fact that the strict conditions
only apply to mixed-strategy Nash equilibria somewhat mitigates the issue,
since many distribution-valued games can still have pure Nash equilibria. So
both problems can be circumvented to a certain extent – anyway, their
existence shows that some care has to be taken when using tail-ordered games,
and that not all guarantees that make life easy in the real-valued theory
continue to hold in the distribution-valued case.

It must also be kept in mind that the tail order is only one approach to
expressing preferences in distribution-valued games, and a route for further
work on the topic could be to analyze the behavior with respect to different
orderings. An example of this is the tweakable stochastic order
$\preccurlyeq_{\text{\tiny tw,$\scriptscriptstyle\mathcal{I}$}}$ we showed in
Chapter 5. We subsequently introduced a method to turn a distribution-valued
game into a multi-objective game and used Pareto-Nash equilibria to solve it:
This is an example of how a different solution concept can be used to
guarantee the existence of solutions. However, this solution concept does not
use a lexicographic comparison anymore. Further work could try to find another
solution concept more fitting than the Nash equilibrium for distribution-
valued games, that still uses lexicographic comparisons in the spirit of tail-
order Nash equilibria, yet is guaranteed to always exist.

In summary, this thesis analyzed the model of distribution-valued games and
the tail order from a mathematical point of view. Some questions about
distribution-valued games could be cleared up, yet there is a lot of potential
for future work on the subject, especially with regard to proving totality of
the tail order on smaller classes of distributions, examining different
preference orderings for distribution-valued games, and possibly formulating
different solution concepts.

## References

  * [AAd19] Ali Alshawish, Mohamed Amine Abid and Hermann de Meer  “Quasi-purification of mixed game strategies: Sub-optimality of equilibria in security games”  In _Computers & Security_ 87, 2019, pp. 101575  DOI: https://doi.org/10.1016/j.cose.2019.101575
  * [Akh65] Naum Ilyich Akhiezer  “The classical moment problem and some related questions in analysis”  Oliver & Boyd, 1965
  * [AM19] Ali Alshawish and Hermann Meer  “Tweakable Stochastic Orders for Cyber Insurances” Submitted (Review Pending), 2019
  * [And76] Lowell B. Anderson  “Antagonistic games”, 1976
  * [Bil12] Patrick Billingsley  “Probability and Measure”  John Wiley & Sons, Inc., 2012
  * [BJ88] Salvador Barbara and Matthew Jackson  “Maximin, leximin, and the protective criterion: Characterizations and comparisons”  In _Journal of Economic Theory_ 46, 1988, pp. 34–44
  * [Bla56] David Blackwell  “An analog of the minimax theorem for vector payoffs.”  In _Pacific Journal of Mathematics_ 6.1 Pacific Journal of Mathematics, 1956, pp. 1–8
  * [Bor85] Kim C. Border  “Fixed point theorems with applications to economics and game theory”  Cambridge University Press, 1985
  * [Bou+12] Patricia Bouyer, Romain Brenguier, Nicolas Markey and Michael Ummels  “Concurrent games with ordered objectives”  In _International Conference on Foundations of Software Science and Computational Structures_ , 2012, pp. 301–315  Springer
  * [CA10] Adem C. Cevikel and Mehmet Ahlatçıoğlu  “Solutions for fuzzy matrix games”  In _Computers & Mathematics with Applications_ 60.3 Elsevier, 2010, pp. 399–410
  * [Chi68] Theodore Chihara  “On indeterminate Hamburger moment problems”  In _Pacific Journal of Mathematics_ 27.3 Mathematical Sciences Publishers, 1968, pp. 475–484
  * [Das11] Constantinos Daskalakis  “Topics in Algorithmic Game Theory (Lecture Notes), Lecture 4”  MIT, 2011  URL: http://people.csail.mit.edu/costis/6853fa2011/lec4.pdf
  * [Dör07] Peter Dörsam  “Grundlagen der Entscheidungstheorie”  In _PD-Verlag, Heidenau_ 3, 2007
  * [Epp20] Jeremias Epperlein, Private Communication. Counterexample constructed in $[1,2]$ originally, relayed to me via e-mail., 2020
  * [FPZ02] Francisco R. Fernández, Justo Puerto and M.. Zafra  “Cores of stochastic cooperative games with stochastic orders”  In _International Game Theory Review_ 4.03 World Scientific, 2002, pp. 265–280
  * [FT91] Drew Fudenberg and Jean Tirole  “Game Theory”  MIT Press, 1991
  * [GGN68] K. Goldberg, A.. Goldman and M. Newman  “The probability of an equilibrium point”  In _Journal of Research of the National Bureau of Standards_ 72.2, 1968, pp. 93–101
  * [GP89] Debasish Ghose and U.. Prasad  “Solution concepts in two-person multicriteria games”  In _Journal of Optimization Theory and Applications_ 63.2 Springer, 1989, pp. 167–189
  * [GZ89] Itzhak Gilboa and Eitan Zemel  “Nash and correlated equilibria: Some complexity considerations”  In _Games and Economic Behavior_ 1.1 Elsevier, 1989, pp. 80–93
  * [Hau23] Felix Hausdorff  “Momentprobleme für ein endliches Intervall.”  In _Mathematische Zeitschrift_ 16.1 Springer, 1923, pp. 220–248
  * [HS88] John Harsanyi and Reinhard Selten  “A General Theory of Equilibrium Selection in Games”  MIT Press, 1988
  * [Kak41] Shizuo Kakutani  “A generalization of Brouwer’s fixed point theorem”  In _Duke Mathematical Journal_ 8.3 Duke University Press, 1941, pp. 457–459  DOI: 10.1215/S0012-7094-41-00838-4
  * [KMP95] Abraham Kandel, Alejandro Martins and Roberto Pacheco  “Discussion: on the very real distinction between fuzzy and statistical methods”  In _Technometrics_ 37.3 Taylor & Francis Group, 1995, pp. 276–281
  * [Lin17] Gwo Dong Lin  “Recent developments on the moment problem”  In _Journal of Statistical Distributions and Applications_ 4.1 SpringerOpen, 2017, pp. 1–17
  * [LSZ05] D. Lozovanu, D. Solomon and A. Zelikovsky  “Multiobjective Games and Determining Pareto-Nash Equilibria”  In _Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica_ , 2005, pp. 115–122
  * [Mae00] Takashi Maeda  “Characterization of the equilibrium strategy of the bimatrix game with fuzzy payoff”  In _Journal of Mathematical Analysis and Applications_ 251.2 Elsevier, 2000, pp. 885–896
  * [Mal95] Paul Malliavin  “Integration and Probability”  Springer New York, 1995
  * [MS16] Akio Matsumoto and Ferenc Szidarovszky  “Game Theory and Its Applications”  Springer Japan, 2016
  * [Nas50] John F. Nash  “Equilibrium Points in N-Person Games.”  In _Proceedings of the National Academy of Sciences of the United States of America_ 36 1, 1950, pp. 48–9
  * [Nis+07] “Algorithmic Game Theory”  Cambridge University Press, 2007
  * [Oei12] OeisWiki Contributors  “Ordering — OeisWiki, Wiki of The On-Line Encyclopedia of Integer Sequences”, 2012  URL: https://oeis.org/wiki/Orderings
  * [Pap07] Christos H. Papadimitriou  “Basic Solution Concepts and Computational Issues”  In _Algorithmic Game Theory_ Cambridge University Press, 2007, pp. 29–52
  * [Qua+09] M. Quant, Peter Borm, G. Fiestras-Janeiro and F. Megen  “On properness and protectiveness in two-person multicriteria games”  In _Journal of Optimization Theory and Applications_ 140.3 Springer, 2009, pp. 499
  * [Ras15] Stefan Rass  “On Game-Theoretic Risk Management (Part One)”, 2015  arXiv:1506.07368 [q-fin.EC]
  * [Ras15a] Stefan Rass  “On Game-Theoretic Risk Management (Part Two)”, 2015  arXiv:1511.08591 [q-fin.EC]
  * [Ras17] Stefan Rass  “On Game-Theoretic Risk Management (Part Three)”, 2017  arXiv:1711.00708 [q-fin.EC]
  * [RKA20] Stefan Rass, Sandra König and Ali Alshawish  “HyRiM: Multicriteria Risk Management using Zero-Sum Games with vector-valued payoffs that are probability distributions” R package version 2.0.0, 2020  URL: https://cran.r-project.org/package=HyRiM
  * [RKS15] Stefan Rass, Sandra König and Stefan Schauer  “Uncertainty in games: Using probability-distributions as payoffs”  In _International Conference on Decision and Game Theory for Security_ , 2015, pp. 346–357  Springer
  * [RKS16] Stefan Rass, Sandra König and Stefan Schauer  “Decisions with Uncertain Consequences – A Total Ordering on Loss-Distributions”  In _PLoS ONE_ 11.12, 2016
  * [Rob51] Julia Robinson  “An Iterative Method of Solving a Game”  In _Annal of Mathematics_ 54.2, 1951
  * [Roz10] Viktor Vladimirovich Rozen  “Equilibrium points in Games with ordered outcomes”  In _Contributions to Game Theory and Management_ 3.0, 2010, pp. 368–386
  * [RS86] Joseph P. Romano and Andrew F. Siegel  “Counterexamples in probability and statistics”  CRC Press, 1986
  * [Sag20] SageMath project  “Normal form games with N players — Sage 9.1 Reference Manual”, 2020  URL: https://doc.sagemath.org/html/en/reference/game_theory/sage/game_theory/normal_form_game.html
  * [Sch17] Konrad Schmüdgen  “The Moment Problem” 277, Graduate Texts in Mathematics  Springer, 2017
  * [Sha53] Lloyd S. Shapley  “Stochastic games”  In _Proceedings of the National Academy of Sciences_ 39.10 National Acad Sciences, 1953, pp. 1095–1100
  * [SR59] Lloyd S. Shapley and Fred D. Rigby  “Equilibrium points in games with vector payoffs”  In _Naval Research Logistics Quarterly_ 6.1 Wiley Online Library, 1959, pp. 57–61
  * [SS07] Moshed Shaked and J. Shanthikumar  “Stochastic Orders”  Springer Science+Business Media, 2007
  * [ST43] James Alexander Shohat and Jacob David Tamarkin  “The Problem of Moments”, Mathematical Surveys 1  American Mathematical Soc., 1943
  * [Ste07] Bernhard Stengel  “Equilibrium Computation for Two-Player Games in Strategic and Extensive Form”  In _Algorithmic Game Theory_ Cambridge University Press, 2007, pp. 53–78
  * [Sui+99] Jeroen Suijs, Peter Borm, Anja De Waegenaere and Stef Tijs  “Cooperative games with stochastic payoffs”  In _European Journal of Operational Research_ 113, 1999, pp. 193–205
  * [TV07] Éva Tardos and Vijay V. Vazirani  “Basic Solution Concepts and Computational Issues”  In _Algorithmic Game Theory_ Cambridge University Press, 2007, pp. 3–28
  * [Vor70] N.. Vorob‘ev  “The present state of game theory” Original title and text in Russian  In _Uspehi Mat._ 25.2 (152), 1970, pp. 81–140
  * [Wak10] Peter P. Wakker  “Prospect theory: For risk and ambiguity”  Cambridge University Press, 2010
  * [Wid46] David Vernon Widder  “The Laplace Transform”  Princeton University Press, 1946