Bachelor Thesis – Distribution-Valued Games Vincent Bürgin

---

University of Passau
Faculty of Computer Science and Mathematics
Chair of Computer Networks & Communications
Prof. Dr.-Ing. Hermann de Meer
Chair of Dynamical Systems
Prof. Dr. Fabian Wirth

Bachelor Thesis

Distribution-Valued Games
Overview, Analysis, and a Segmentation-Based Approach

Vincent Bürgin

Date: September 25, 2020 Supervisors: Prof. Dr.-Ing. Hermann de Meer Prof. Dr.
Fabian Wirth Ali Alshawish, M. Sc.

###### Abstract

The paper [Ras15] introduced _distribution-valued games_. This game-theoretic
model uses probability distributions as payoffs for games in order to express
uncertainty about the payoffs. The player’s preferences for different payoffs
are expressed by a stochastic order which we call the _tail order_.

This thesis formalizes distribution-valued games with preferences expressed by
general stochastic orders, and specifically analyzes properties of the tail
order. It identifies sufficient conditions for tail-order preference to hold,
but also finds that some claims in [Ras15] about the tail order are incorrect,
for which counter-examples are constructed. In particular, it is demonstrated
that a proof for the totality of the order on a certain set of distributions
contains an error; the thesis proceeds to show that the ordering is not total
on the slightly less restricted set of distributions with non-negative bounded
support. It is also shown that not all tail-ordered games have mixed-strategy
Nash equilibria, and in fact almost all tail-ordered games with finitely-
supported payoff distributions can only have a Nash equilibrium if they have a
pure-strategy Nash equilibrium.

The thesis subsequently extends an idea from [AM19] and proposes a new
solution concept for distribution-valued games. This concept is based on
constructing multi-objective real-valued games from distribution-valued games
by segmenting their payoff distributions.

###### Contents

  1. 1 Introduction
    1. 0.0.1 Related Work
  2. 2 Mathematical Preliminaries: Probability and Decision Theory
    1. 1 Probability Theory
    2. 2 Decision Theory
  3. 3 Non-Cooperative Game Theory
    1. 3 Solution Concepts
    2. 4 Mixed-Strategy Extensions
    3. 5 Proof of Existence of a Mixed-Strategy Nash Equilibrium
    4. 6 Computation of Nash Equilibria
      1. 6.1 Exact Computation
        1. 6.1.1 Complexity Considerations
      2. 6.2 Approximate Computation: Fictitious Play
  4. 4 Games with Distributional Payoffs
    1. 7 Normal-Form Games with Generalized Payoffs
    2. 8 Distribution-Valued Normal-Form Games
    3. 9 The Stochastic Tail Order
      1. 9.1 Definition and Basic Properties
      2. 9.2 Sufficient Conditions for Tail Order Preference
        1. 9.2.1 Counterexamples to Equivalences in the Sufficient Conditions for the Tail Order
      3. 9.3 Can the Tail Order Be Made a Total Order?
        1. 9.3.1 The Moment Problem and its Variants
        2. 9.3.2 Non-Totality in the Stieltjes Case
        3. 9.3.3 Distributions with Non-Negative Bounded Support
    4. 10 Nash Equilibria in Tail-Ordered Games
      1. 10.1 Existence Conditions for Mixed-Strategy Nash Equilibria in Lexicographically-Ordered Games
        1. 10.1.1 Nash Equilibria in Distribution-Valued Tail-Order Games
      2. 10.2 Probability that Lexicographically-Ordered Games have Nash Equilibria
      3. 10.3 Kakutani’s Theorem and Lexicographically-Ordered Games
  5. 5 Tweaking the Stochastic Order: Segmenting Loss Distributions
    1. 11 The Tweakable Stochastic Order
    2. 12 Games with Multiple Distribution Segments as Objectives
      1. 12.1 Multi-Objective Games and Pareto-Nash Equilibria
      2. 12.2 Multi-Objective Segmented-Distribution Games
  6. 6 Conclusion

##  Chapter 1 Introduction

Game theory studies _games_ that are played by multiple independent players
with different objectives, and analyzes the players’ strategic possibilities.
It has a wide range of applications in economics and risk management, and can
be fruitfully used in cyber security as well. A _game_ models a situation that
is determined by the actions its players take independently: Every player has
a set of strategies to choose from, and the _outcomes_ (or _payoffs_) the
players obtain depend on the combination of all the strategies the players
choose. In the classical setting, the payoffs are represented by numbers: A
numeric payoff can for example be interpreted as a monetary reward the player
gets, or as a more abstract _utility_ the outcome situation has for the
player.

However real-world settings tend to involve a lot of uncertainty, and it may
be hard to specify a clear-cut number as outcome of a certain situation. The
economical branch of decision theory provides tools for dealing with
stochastic outcomes instead: It uses _preference relations_ between
_lotteries_ to formalize rational decisions in such situations.

A natural idea is to extend the existing theory of real-valued games by
allowing probability distributions as payoffs, and such a model will be the
basis for this bachelor thesis. This model of _distribution-valued games_ was
first introduced and used in several papers by Stefan Rass et al (e.g. [Ras15,
RKS16]). The idea is that the outcomes of the players are stochastic
experiments, modeled by probability distributions, and each player’s
preferences for particular outcomes are represented by a preference relation
on the distributions, a _stochastic order_. As an example, the preference of a
player might express that the player tries to maximize the expected gain, but
is also willing to sacrifice some expected gain if this reduces the risk of
very unfortunate outcomes. The thesis focuses on a particular stochastic
order, which we call the tail order: It was introduced in [Ras15] together
with distribution-valued games, and expresses preferences that are maximally
risk-averse. It is intended to be used on loss (instead of payoff)
distributions, and it prefers one distribution over another if the other
distribution assigns some (arbitrarily tiny) larger probability to a higher
loss: In other words, its aim is to minimize the worst-case loss. The ordering
is defined based on moment sequences, and an analysis of its properties makes
up a substantial part of this thesis. In particular, we show that not all of
its properties that were claimed when it was first introduced hold true: For
one, we show that an asserted characterization of the ordering based on the
density functions of the involved distributions only holds in one direction in
form of a sufficient condition. This result leads to the interesting question
between which distributions the ordering is total: In particular, the thesis
shows that even the set of distributions with bounded non-negative support
contains elements that are incomparable by the ordering. The second issue we
go into is that not all distribution-valued games with tail-order preferences
have Nash equilibria: In particular, we show that they can only have mixed-
strategy equilibria under very specific conditions. Finally, the thesis
presents an alternative stochastic ordering based on segmenting loss
distributions which was constructed by Ali Alshawish: This ordering was
introduced with the goal of tweaking the tail order such that risk attitudes
not maximally pessimistic are possible. The thesis then proposes a new
approach of using the segmentation idea to turn a distribution-valued game
into a multi-objective real-valued game, and shows how such games can be
solved via the existing theory of Pareto-Nash equilibria.

The primary contributions of this thesis are that it presents a complete
formalization of distribution-valued games (Sections 7 and 8), critically
analyzes the tail order, provides counterexamples to several misconceptions in
the original publications about this ordering (Sections 9 and 10), and
proposes the Pareto-Nash equilibria of a game obtained by distribution
segmentation as an alternative solution concept for distribution-valued games
(Chapter 5). To provide the basis for the discussions in those chapters,
Chapter 3 reviews the basics of classical non-cooperative game theory. This
serves as an introduction to the concepts that are later generalized, and we
also introduce some results that are needed for the analysis of Nash
equilibria with respect to the tail order. Chapter 2 introduces mathematical
preliminaries: We shortly go over important concepts from probability theory
that the subsequent chapters rely on, and review basic notions from decision
theory.

#####  0.0.1 Related Work

Directly related to this work are the papers by Stefan Rass et al
bib:rassGameRiskManagI,bib:rassGameRiskManagII,bib:rassTotalOrderingOnLossDistributions
that introduce the tail order and use it in the context of risk management,
and by Ali Alshawish et al [AAd19, AM19] which use the tail order and define
the related _tweakable stochastic order_ , which serves as a basis for the
ideas of Chapter 5.

Regarding further related work, there are of course many publications on
classical (real-valued) game theory, and the books mainly used for this thesis
are
bib:fudenbergGameTheory,bib:nisanAlgorithmicGameTheory,bib:matsumotoGameTheory.
There is also literature on stochastic orders, e.g. [SS07]. There are however
surprisingly few publications that concern models similar to distribution-
valued games, or even other generalized payoffs that are not real numbers.
There are multiple well-known types of games that include randomness, but none
of them match the model of distribution-valued games: There is the notion of
_stochastic games_ (see [Sha53]) which are played in multiple rounds and
include a game state that changes between the rounds and determines the payoff
structure. In these games, only the state transitions depend on chance, but
not the payoffs. Another variant are _moves by nature_ in the theory of
_extensive-form games_ , which occur for example in _Bayesian games_ (see
[FT91, Chapter 6 and Section 8.3]): While payoffs can depend on chance in such
models, an important difference lies in their equilibrium concepts, since the
payoff distributions are condensed to an expected value before comparing them,
unlike the comparison by _stochastic orders_ in our model. The models closest
to Rass’ distribution-valued games published prior to it seem to be
_stochastic cooperative games_ which use distribution-valued outcomes rated by
stochastic orders, and _non-cooperative games with fuzzy-number payoffs_. The
former (e.g. [Sui+99, FPZ02]) however concern only cooperative games whose
theory differs from the theory of non-cooperative games that our model lives
in. The latter uses fuzzy numbers instead of probability distributions (e.g.
[Mae00, CA10]): The exact relationship between fuzzy and probabilistic methods
is rather complicated (see e.g. the discussion in [KMP95]), yet they are
certainly different concepts.

There is also not much literature on the more general case of games with
payoffs in an arbitrary set ordered by a preorder. This thesis defines its own
generalized model in Section 7 so we can properly work with such games without
ambiguity about the definitions. Similar definitions are given in [Roz10], and
apparently already in the much older Russian-language article [Vor70] it
cites, but at least [Roz10] does not include a definition for mixed extensions
as general as we need. It should be remarked though that [TV07, Section 1.2.1]
mentions an even more general model which, instead of using payoffs, defines
the players’ preferences directly between the strategy profiles.

The tail-ordered games defined by Rass are closely related to games with
vector-valued payoffs ordered by a lexicographic order, as will be worked out
in Section 10. No literature on such lexicographically-ordered games could be
found either: The closest examples are the articles bib:salvadorLeximin,
bib:quantPropernessProtectiveness about _leximin_ preferences used in social
choice theory and the related concept of _protective behavior_ in games, and
the article [Bou+12] which concerns graph games and orders objectives
lexicographically (among other ways). The tail order itself is defined based
on moment sequences of probability distributions: A relevant question for the
thesis thus is which real sequences are moment sequences, a question known as
the _moment problem_. The literature on this subject is rich, and there are
both classical and more recent publications, e.g. [Hau23, Akh65, Chi68,
Sch17]. However the question whether two moment sequences can alternate, which
is relevant to the tail order and is answered in Section 9.3, seems not to
have been considered in the literature before.

Finally, the theory of multi-objective games and Pareto-Nash equilibria we put
to use in Chapter 5 is well-developed, starting with the papers [Bla56] and
[SR59]. The more recent [LSZ05] generalizes some theorems from the earlier
papers. Furthermore, an overview of solution concepts other than Pareto-Nash
equilibria is given in [GP89].

##  Chapter 2 Mathematical Preliminaries: Probability and Decision Theory

The following pages present basic concepts from probability and decision
theory that are relevant as background for the thesis. The first section
contains standard definitions from probability and measure theory that can be
found in textbooks such as [Bil12]. The section about decisions under
uncertainty and risk is adopted from [Dör07, Sections 3.5 - 5.3] and [Wak10,
Sections I.1, I.2]. The thesis uses standard mathematical notation, yet some
notations used are worth mentioning: We write $\mathbb{N}=\\{1,2,3,\dots\\}$
for the natural numbers not including zero, and
$\mathbb{N}_{0}\coloneqq\mathbb{N}\cup\\{0\\}$. The non-negative real numbers
are denoted by $\mathbb{R}_{\geq 0}$. If $n\in\mathbb{N}$, we write
$[n]\coloneqq\\{1,2,\dots,n\\}$ for the first $n$ natural numbers. If
$A\subseteq\mathbb{R}$ is a set, we write $\mathds{1}_{A}$ for its
_characteristic function_ that is defined by $\mathds{1}_{A}(x)=1$ iff $x\in
A$, and $\mathds{1}_{A}(x)=0$ otherwise. We say that two real sequences
$(a_{n})_{n\in\mathbb{N}_{0}}$, $(b_{n})_{n\in\mathbb{N}_{0}}$ _alternate_ if
for every $K\in\mathbb{N}_{0}$ there are indices $m,l\geq K$ such that
$a_{m}>b_{m}$ and $a_{l}<b_{l}$. We say that two functions
$f,g:\mathbb{R}\to\mathbb{R}$ _alternate_ on an interval $[a,b]$ if for every
$x_{0}\in(a,b)$ there are $x_{1},x_{2}\in(x_{0},b)$ such that
$f(x_{1})<g(x_{1})$ and $f(x_{2})>g(x_{2})$.

###  1 Probability Theory

Probability theory presents a framework to do calculations with probabilities
assigned to the outcomes of probabilistic experiments. It uses measure theory
to unify the different settings needed for finitely, countably infinitely and
uncountably infinitely many outcomes ([Bil12, Section 1]). This section
quickly goes over the basic concepts needed in the thesis.

Assume $\Omega$ is some set, usually representing probabilistic outcomes. A
_sigma algebra_
$\operatorname{\mathcal{A}}\subseteq\operatorname{\mathcal{P}}(\Omega)$
represents probabilistic events and is a non-empty system of subsets of
$\Omega$ which is closed under complements and countable intersections. A
_signed measure_ $\mu$ on $(\Omega,\operatorname{\mathcal{A}})$ is a map
$\mu:\operatorname{\mathcal{A}}\to\mathbb{R}\cup\\{-\infty,\infty\\}$ that
satisfies $\mu(\emptyset)=0$, and
$\mu(\bigcup_{n\in\mathbb{N}}A_{n})=\sum_{n\in\mathbb{N}}\mu(A_{n})$ for any
countable collection $(A_{n})_{n\in\mathbb{N}}$ of pairwise-disjoint sets from
$\operatorname{\mathcal{A}}$ [Bil12, Problem 32.12]. $\mu$ is a _measure_ if
it only takes non-negative values, and is _finite_ if $\mu(\Omega)<\infty$. A
_probability measure_ $P$ is a measure that satisfies $P(\Omega)=1$. The tuple
$(\Omega,\operatorname{\mathcal{A}},P)$ forms a _probability space_ , and for
any set $A\in\operatorname{\mathcal{A}}$, $P(A)$ represents its probability
[Bil12, Section 2]. A convex combination (_mixture_) $\alpha
P_{1}+(1-\alpha)P_{2},\,\alpha\in[0,1]$ of probability measures $P_{1},P_{2}$
is again a probability measure.

If $\Omega=\mathbb{R}$, one needs to find a suitable sigma algebra: While the
power set $\operatorname{\mathcal{P}}(\mathbb{R})$ is a sigma algebra, it is
“too large” as it contains non-well behaved sets which prevent useful measures
(_Vitali’s Theorem_). One resorts to the _Borel sigma algebra_ $\mathcal{B}$,
defined as the smallest sigma algebra containing all intervals
$[a,b]\subseteq\mathbb{R}$. The sets $B\in\mathcal{B}$ are called _Borel sets_
, and measures on $\mathcal{B}$ are called _Borel measures_. An ubiquitous
Borel measure is the _Lebesgue measure_ $\lambda$ which assigns Borel sets
their natural “volume” and is uniquely determined as the Borel measure that
maps closed intervals to their length, i.e. $\lambda([a,b])\coloneqq b-a$,
$a\leq b$. The _point-mass_ (or _Dirac_) _measure_ $\delta_{x}$ is the Borel
probability measure that assigns all probability mass to one point
$x\in\mathbb{R}$, i.e. $\delta_{x}(B)=\mathds{1}_{B}(x)$. [Bil12, p.23,
p.45-47, p.177]

A function $f:\Omega\to\mathbb{R}$ is _Borel-measurable_ if $\forall
B\in\mathcal{B}:f\operatorname{{}^{-1}}(B)\in\operatorname{\mathcal{A}}$. Its
_Lebesgue integral with respect to a Borel measure $\mu$_, denoted by $\int
f\,d\mu$, can be defined in three cases: First, the integral can be defined if
$f$ only takes non-negative values. Secondly it can be defined if $f$ takes
negative values, but either its positive part $f^{+}=\max(0,f)$ or its
negative part $f^{-}=\max(0,-f)$ have a finite integral. If both parts have a
finite integral, $f$ is called _integrable_. This is equivalent to
$\int\left|f\right|\,d\mu<\infty$. In contrast, one part has an infinite
integral, the integral of $f$ is either $\infty$ or $-\infty$; if both parts
have infinite integrals, the integral cannot be defined (for example,
$\operatorname{id}:x\mapsto x$ has no integral). The integration can be
restricted to a set $A\in\operatorname{\mathcal{A}}$, denoted as
$\int_{A}f\,d\mu\coloneqq\int\mathds{1}_{A}\cdot f\,d\mu$. To specify the
integration variable, one writes $\int_{A}f(x)\,d\mu(x)$. If $\mu=\lambda$ and
$\Omega=\mathbb{R}$, the integral coincides with the Riemann integral in many
cases that occur in practice, in particular if $f$ is bounded, has bounded
domain and is Riemann-integrable. [Bil12, Sections 13, 15-17]

A _real-valued random variable_ on $(\Omega,\operatorname{\mathcal{A}})$ is a
function $X:\Omega\to\mathbb{R}$ which is Borel-measurable, i.e. $\forall
B\in\mathcal{B}:X\operatorname{{}^{-1}}(B)\in\operatorname{\mathcal{A}}$. A
convenient notation for such preimages is $\\{X\in B\\}\coloneqq
X\operatorname{{}^{-1}}(B)$, such that $P(\\{X\in B\\})$ denotes the
probability that “$X$ takes a value in $B$”. $X$ induces a Borel probability
measure, its _distribution_ or _pushforward measure_ $P^{X}:B\mapsto P(\\{X\in
B\\})$. One can think of $P^{X}$ as only describing the random variable’s
distribution while ignoring the details of the underlying $(\Omega,P)$.
Closely related is the _(cumulative) distribution function_ (cdf)
$F_{X}:\mathbb{R}\to[0,1],x\mapsto P(\\{X\leq x\\})$. $P^{X}$ and $F_{X}$
uniquely determine each other and both represent the distribution of $X$; on
the other hand, there can be many different random variables on a fixed
probability space that all have the same distribution. Yet many properties of
$X$ only depend on $P^{X}$, and can therefore be formulated in terms of
probability measures. [Bil12, Sections 14, 20]

Let $P$ be a Borel probability measure. $P$ is _discrete_ if $P(S)=1$ for a
countable set $S=\\{x_{1},x_{2},\dots\\}$: It can then be represented by its
_probability mass function_ (pmf) $f:\mathbb{R}\to[0,1],x\mapsto P(\\{x\\})$
that satisfies $\sum_{x_{i}\in S}f(x_{i})=1$, and $x\notin S\Rightarrow
f(x)=0$. $P$ is _absolutely continuous_ (AC) if it has a _(probability)
density function_ (pdf) $f:\mathbb{R}\to\mathbb{R}_{\geq 0}$, such that
$\forall B\in\mathcal{B}:P(B)=\int_{B}f(x)\,d\lambda(x)$. $P$ is _continuous_
if its distribution function $F$ is continuous, or equivalently
$P(\\{X=c\\})=0$ for all $c\in\mathbb{R}$. Absolutely continuous probability
measures are continuous, but the converse is not true in general (a
counterexample is the _Cantor distribution_): In particular, there are
probability measures which are neither AC nor discrete (nor a mixture of AC
and discrete measures). Both absolute continuity and discreteness are special
cases of a more general concept: $P$ has a density $f$ _with respect to a
measure $\mu$_ if $\forall B\in\mathcal{B}:P^{X}(B)=\int_{B}f(x)\,d\mu(x)$;
For discrete distributions, the mass function $f$ can be seen as a density
with respect to the _counting measure_ $\\#$ which assigns to each set its
cardinality. If $P$ has a $\mu$-density $f$, this allows to compute the
integral of some $P$-integrable function $g$ with respect to $P$ as
$\int_{A}g\,dP=\int_{A}fg\,d\mu$. [Bil12, Sections 16, 20, 31]

Some set $A\subseteq\mathbb{R}$ is _null set_ with respect to measure $\mu$ if
$A$ is contained in a measurable set $\tilde{A}$ with $\mu(\tilde{A})=0$. A
condition holds _almost surely_ with respect to a probability measure $P$ if
the set where it does not hold is a null set. If $P$ has a $\mu$-density $f$,
this implies that all null sets with respect to $\mu$ are null sets with
respect to $P$ ($P$ is _absolutely continuous_ with respect to $\mu$). A
probability measure $P$ is _supported_ on a measurable set $A$ if $P(A)=1$. If
$P$ is a Borel probability measure on $\mathbb{R}$, we write
$\operatorname{supp}(P)$ for the _support_ of $P$: We use the convention that
$\operatorname{supp}(P)$ is the smallest closed set with probability one, i.e.
the intersection of all closed $B\in\mathcal{B}$ such that $P(B)=1$. [Bil12,
p.63, p.170, Theorem 31.7]

The _expected value_ of a random variable is denoted by
$E(X)\coloneqq\int_{\Omega}X\,dP=\int_{\mathbb{R}}x\,dP^{X}(x)$. It is only
defined if $X$ is integrable, i.e.
$E(\left|X\right|)=\int_{\Omega}\left|X\right|\,dP<\infty$. We write
$E(P)\coloneqq\int_{\mathbb{R}}x\,dP(x)$ if $P$ is a Borel probability measure
and $\int_{\mathbb{R}}\left|x\right|\,dP(x)<\infty$. The expected value is the
first of the distribution’s _moments_ : If $p\in\mathbb{N}_{0}$, we say that
$X$ is _$p$ -integrable_, or $X\in\mathcal{L}^{p}$, if
$E(\left|X\right|^{p})<\infty$; In this case, define the _$p$ -th moment_ of
$X$ as $E(X^{p})$. Analogously, define the $p$-th moment of a Borel measure
$P$ by $m_{p}(P)\coloneqq\int_{\mathbb{R}}x^{p}\,dP(x)$ if
$\int_{\mathbb{R}}\left|x\right|^{p}\,dP(x)<\infty$. $P$ is a probability
measure if and only if $m_{0}(P)=1$, because $m_{0}(P)=P(\mathbb{R})$. While
$\mathcal{L}^{p}$ contains all random variables over a fixed probability space
that have a moment of $p$-th order, there is no standard notation for the set
of Borel probability measures that have moments of $p$-th order. In this
thesis, we denote this set by $M^{p}$, and write
$M\coloneqq\bigcap_{p\in\mathbb{N}}M^{p}$ for the set of Borel probability
measures that have moments of all orders. [Bil12, Section 21]

###  2 Decision Theory

Decision theory is the theory of selecting one of multiple alternatives in a
scenario where the exact outcomes of the alternatives are uncertain. There is
a state space $S$, also called _states of nature_ : Exactly one of the states
is considered to be true, but it is unknown which. There is a set of
_outcomes_ which we will assume to be $\mathbb{R}$. The alternatives one has
to decide between are called _prospects_ or _lotteries_ , and are modeled as
maps $x:S\to\mathbb{R}$. Prospects are assumed to only take finitely many
values. There is a short notation for prospects: E.g. if
$S=\\{s_{1},s_{2},s_{3}\\}$, one writes $(s_{1}:50,s_{2}:30,s_{3}:121)$ for
the prospect that assigns to the three states the values $50,30$, and $21$,
respectively. [Wak10, Section 1.1]

The theory distinguishes between _decisions under uncertainty_ and _decisions
under risk_. The difference is that under _risk_ , the states of nature have
probabilities assigned to them, while under _uncertainty_ , no probabilities
are assumed. A common way to transform a probability under uncertainty into
one under risk is to assume that all states of nature are equally likely
(_Laplace’s method_). There are other methods to make a decision under
uncertainty, for example the _maximin_ and _maximax_ methods, _Huwicz’ rule_ ,
and the _Savage-Niehans_ or _regret minimization rule_. [Dör07, Section 4]

For decisions under risk, the short notation is changed to represent the
probabilities instead of the states, e.g. $(5\%:50,10\%:30,85\%:121)$.
Prospects can be interpreted as random variables in this model, and it seems
natural to compare them by their _expected values_. However, this method is
not considered to accurately represent every decision maker’s attitude to
risk: For example, it seems plausible that many people would prefer the
certain payoff (100%: 10 000 €) over the gamble (1%: 1 000 001 €, 99%: 0 €),
even though the latter prospect has a greater expected value. Bernoulli argued
that monetary rewards have diminishing marginal returns: The more money
someone gets, the less he or she cares about getting one additional unit. In
other words, the _utility_ the money has for the decision maker increases less
than proportionally to the amount. In formal terms, one associates with a
decision maker a _utility function_ $u:\mathbb{R}\to\mathbb{R}$, defined as a
monotonically increasing function from the outcome set to the reals. To decide
between two prospects by _expected utility_ , one applies a utility function
$u$ to the outcomes and decides between the resulting prospects by expected
value. A utility function that is _concave_ , i.e. grows slower than
proportionally to its argument, is associated with _risk-averse_ behavior. On
the other hand, a _convex_ utility function is associated with _risk-seeking_
behavior. Commonly, functions such as $x\mapsto x^{2},x\mapsto\sqrt{x}$, or
$x\mapsto\ln(x)$ are used. [Sections 2.1, 2.2]bib:wakkerProspectTheory[Section
5]bib:doersamGrundlagenDerEntscheidungstheorie

More general preferences between prospects can be captured by defining a
binary _preference relation_ $\preccurlyeq$ between prospects: A relationship
$x\succcurlyeq y$ expresses that the decision maker “is willing to choose $x$
from $\\{x,y\\}$” ([Wak10, p. 14]). Reasonable assumptions for preference
relations include _reflexivity_ and _transitivity_ , in which case the
preference relation is a _preorder_ on the prospects. The theory as described
in [Wak10] restricts prospects such that they can only take finitely many
values. If interpreted as random variables, this means that only random
variables with finite support are considered. In Chapter 4, we will drop this
restriction and define preference relations between arbitrary Borel
probability distributions on the real numbers, then called _stochastic orders_
(e.g. [SS07]).

##  Chapter 3 Non-Cooperative Game Theory

In this chapter, we will introduce the basic notions of non-cooperative game
theory. Game theory is applied in scenarios where multiple agents, called
_players_ , make decisions independently of another, and each tries to achieve
the best outcome for themselves. This theory is called _non-cooperative game
theory_ , and it is characterized by players not being able to make
enforceable agreements [HS88, p.1]. In contrast, there is _cooperative game
theory_ which lets players cooperate and form coalitions to achieve a better
outcome. The underlying theory of the two variants is quite different, and
this thesis focuses only on the non-cooperative theory. The classical example
of a non-cooperative game is the _prisoner’s dilemma_ :

######  Example 3.1 (Prisoner’s Dilemma).

Two criminals were caught and are being held in different cells. The police
does not have substantial evidence against them, so a deal is offered to each
of the two: If one prisoner confesses to the crime and hands over evidence
that helps prosecuting his partner, the prisoner can go into a witness
protection program and stay out of prison, while the partner will be sentenced
to five years in prison. Yet if both prisoners choose to confess, the
prosecution does not need a key witness, and both will have to serve an (only
slightly reduced) sentence of four years. However, if both prisoners refuse to
confess, the prosecutors, based on the little evidence they have, will only be
able to sentence them to one year in prison each.

The game can be represented by a table: The rows represent the first player’s
strategies, the columns the second player’s strategies, and the cells contains
the years the first and second player face in prison, respectively.

| Prisoner 2 does not confess | Prisoner 2 confesses
---|---|---
Prisoner 1 does not confess | 1 / 1 | 5 / 0
Prisoner 1 confesses | 0 / 5 | 4 / 4

So what should the prisoners do? If they were able to make a binding contract
about the situation, they would surely agree not to confess, and both only
spend one year in prison. But since there is no way to do so, each prisoner’s
fate depends on the decision of his partner, and both have to watch out not to
be betrayed by their partner and get an even longer prison sentence than by
confessing. Therefore in non-cooperative game theory, somewhat counter-
intuitively, the solution to the game is that both prisoners confess and both
face four years in prison instead of just one. They both have to accept going
to prison for four years, since they cannot make a binding agreement, and this
is the only way to avoid being betrayed by the other prisoner.

We will now define such games and their solution concepts mathematically.

######  Definition 3.2 (see
[p.4]bib:fudenbergGameTheory[p.19]bib:matsumotoGameTheory[p.9]bib:nisanAlgorithmicGameTheoryCh1Basic).

A real-valued _normal form game_
$G=(n,(S_{1},\dots,S_{n}),(u_{1},\dots,u_{n}))$ consists of

  * •

the number of players $n\in\mathbb{N}$,

  * •

for each player $k\in[n]$, a set $S_{k}$ of available strategies,

  * •

for each player $k\in[n]$, a payoff function $u_{k}:S\to\mathbb{R}$, where
$S=\bigtimes\limits_{i\in[n]}S_{i}$ denotes the set of all possible
combinations of the players’ strategies.

Elements of $S_{k}$ are called _strategies_ , elements of $S$ are called
_strategy profiles_. $G$ is called _finite_ if $S$ is a finite set.

######  Remark 3.3.

In this chapter, with the term _game_ we always mean a real-valued normal form
game as in Definition 3.2.

Instead of specifying payoff functions $u_{k}$, we can specify cost functions
$c_{k}$ with the semantics that players want to maximize payoffs, but minimize
costs. For example, the “years in prison” in Example 3.1 correspond to costs
instead of payoffs. We can switch between those viewpoints by setting
$u_{k}=-c_{k}$. For a strategy profile $s=(s_{1},\dots,s_{n})\in S$ and some
player $k$, it is sometimes convenient to use the notation $s_{-k}$ for $s$
with the $k$-th coordinate omitted, and write $u_{k}(s_{k},s_{-k})$ instead of
$u_{k}(s)$. [TV07, p.9-10]

######  Notation 3.4.

In finite two-player games, it is convenient to specify payoffs by matrices:
We will then use matrices $A=(a_{ij})_{\scriptscriptstyle
i\in[\left|S_{1}\right|],\,j\in[\left|S_{2}\right|]},B=(b_{ij})_{\scriptscriptstyle
i\in[\left|S_{1}\right|],\,j\in[\left|S_{2}\right|]}$ such that $a_{ij}$ and
$b_{ij}$ correspond to the first/second player’s payoffs under the $i$-th
strategy of the first player and the $j$-th strategy of the second player.

A common special case are zero-sum games:

######  Definition 3.5 ([FT91, p.4]).

A _two-player zero-sum game_ is a game with two players, such that

$\displaystyle\forall s\in S:u_{1}(s)+u_{2}(s)=0.$

In a zero-sum game, the two players play strictly “against each other”, and
are adversaries in every possible scenario: one player wins exactly what the
other loses, and there is no outcome that corresponds to mutual benefit. As
[FT91] notes, the important feature of these games is that the payoffs sum to
a constant. Choosing this constant as zero is only for normalization.

###  3 Solution Concepts

Reasoning about rational strategies, as done in Example 3.1, is formalized by
_solution concepts_. The most prominent one is the concept of _Nash
equilibria_. Before we introduce Nash equilibria, we start with the simpler
solution concept of _dominant strategies_ , where a player’s best strategy is
independent the other players’ actions.

######  Definition 3.6 (Dominant strategy, see [TV07]).

Let $G$ be a game with $n$ players. A strategy $s_{k}\in S_{k}$ for a player
$k\in[n]$ is a _dominant strategy for player $k$_ if

$\displaystyle\forall\tilde{s}\in S:u_{k}(s_{k},\tilde{s}_{-k})\geq
u_{k}(\tilde{s}).$

A strategy profile $(s_{1},\dots,s_{n})\in S$ is a _dominant strategy
solution_ if all its individual strategies $s_{i}$ are dominant strategies.

In the prisoner’s dilemma 3.1, confessing is a dominant strategy for both
prisoners: For example, if player 2 confesses, then player 1 is best off by
confessing as well. If on the other hand player 2 does not confess, player 1
is _also_ best off by confessing, i.e. betraying player 2 and going into
witness protection without a prison sentence. Dominant strategies lead to a
obvious solution of the game if they exist, but many games do not have a
dominant-strategy solution. A more sophisticated solution concept are Nash
equilibria, which encode that for a given strategy profile, no player has an
incentive to change their strategy when all other player’s strategies stay as
before. Nash equilibria represent a certain form of stability in a strategy
profile.

######  Definition 3.7 (Nash equilibrium, see [FT91, p.11]).

Let $G$ be a game with $n$ players. A strategy profile $s\in S$ is a _Nash
equilibrium_ if

$\displaystyle\forall k\in[n],\forall\tilde{s}_{k}\in
S_{k}:\leavevmode\nobreak\ u_{k}(s_{k},s_{-k})\geq
u_{k}(\tilde{s}_{k},s_{-k}).$

######  Lemma 3.8 (Row/Column Criterion, see [MS16, p.14]).

In a finite two-player game with payoff matrices $A,B$, the Nash equilibria
correspond exactly to the indices $(i,j)$ where $a_{ij}$ is maximal in its
column, and $b_{ij}$ is maximal in its row. If the game is zero-sum, these are
just the indices where $a_{ij}$ is both maximal in its column and minimal in
its row.

###### Proof.

The criterion follows directly from the definition: Let $s_{1,i}\in S_{1}$ and
$s_{2,j}\in S_{2}$ be the $i$-th/$j$-th strategy, respectively. $a_{ij}$ is
maximal in its column if and only if $u_{1}(s_{1,i},s_{2,j})\geq
u_{1}(s_{1,\tilde{i}},s_{2,j})$ for all $s_{1,\tilde{i}}\in S_{1}$. Likewise,
$b_{ij}$ is maximal in its row if and only if $u_{1}(s_{1,i},s_{2,j})\geq
u_{1}(s_{1,i},s_{2,\tilde{j}})$ for all $s_{2,\tilde{j}}\in S_{2}$. In the
zero-sum case, as $a_{ij}=-b_{ij}$, maximizing $b_{ij}$ over all $j$ is
equivalent to minimizing $a_{ij}$ over all $j$. ∎

######  Lemma 3.9.

In a two-player zero-sum game, all Nash equilibria have the same payoff. The
unique payoff of player 1 under a Nash equilibrium is then called the _value_
of the game.

###### Proof.

[MS16, p.15] gives a proof for the case of finitely many strategies using the
row-column criterion, but the argument works in the general setting: Let
$(s_{1},s_{2})$, $(\tilde{s}_{1},\tilde{s}_{2})$ be two Nash equilibria. Then

$\displaystyle u_{1}(s_{1},s_{2})\geq
u_{1}(\tilde{s}_{1},s_{2})=-u_{2}(s_{2},\tilde{s}_{1})\geq-
u_{2}(\tilde{s}_{2},\tilde{s}_{1})=u_{1}(\tilde{s}_{2},\tilde{s}_{1}).$

By a symmetric argument, $u_{1}(\tilde{s}_{2},\tilde{s}_{1})\geq
u_{1}(s_{1},s_{2})$, and therefore
$u_{1}(\tilde{s}_{2},\tilde{s}_{1})=u_{1}(s_{1},s_{2})$. ∎

The next example illustrates the solution concepts we introduced:

######  Example 3.10 (Dominant Strategy Solutions and Nash Equilibria).

In example 3.1 we saw a game with a dominant strategy solution, which in fact
also is the unique Nash equilibrium of the game. Now the game in (a) shows
that Nash equilibria and dominant strategy solutions are indeed different
concepts. The first player has no dominant strategy, so there is no dominant
strategy solution. But the game does have a Nash equilibrium: If both players
play their first strategy, the payoff 1 for the first player is maximal in its
column, and the payoff 1 for the second player is maximal in its row.

The game in (b) shows that Nash equilibria need not be unique: Both the upper-
left and the lower-right cell correspond to Nash equilibria.

| b1 | b2
---|---|---
a1 | 1 / 1 | 0 / 0
a2 | 0 / 3 | 1 / 2
(a) Game with Nash equilibrium, but no dominant strategy solution.

| b1 | b2
---|---|---
a1 | 1 / -1 | 0 / -2
a2 | 0 / -2 | 5 / 3
(b) Game with two Nash equilibria.

###  4 Mixed-Strategy Extensions

The example games up to here always had a finite number of strategies for each
player. However, such finite games do not always have Nash equilibria. We next
introduce the concept of _mixed strategies_ : We will allow each player to
“mix” between multiple strategies, interpreted as playing each of them with a
certain probability. The next example shows how mixed strategies can be used
to find an equilibrium for the Rock-Paper-Scissors game.

######  Example 3.11 (Rock-Paper-Scissors).

In this game-theoretic formulation of the well-known game _Rock-Paper-
Scissors_ , the players have strategy sets
$S_{1}=S_{2}=\\{\text{Rock},\text{Paper},\text{Scissors}\\}$, where paper
beats rock, rock beats scissors, and scissors beat paper. The game is zero-
sum, and can be represented by the first player’s payoff matrix:

| Rock | Paper | Scissors
---|---|---|---
Rock | 0 | -1 | 1
Paper | 1 | 0 | -1
Scissors | -1 | 1 | 0

There is no Nash equilibrium if the players only have those three strategies
available: For example, if player 1 plays rock, player 2 can beat it by
playing paper; but if player 2 plays paper, player 1 has an incentive to
switch to scissors, and so on. Exactly this kind of instability is not allowed
for a Nash equilibrium, so this example shows that not all games have Nash
equilibria.

Instead of committing to a single hand gesture and play it, players should
rather play one of the three gestures unpredictably: While a player committed
to a single one of the three strategies can be easily beaten, this is not the
case if the player picks each of the three strategies with equal probability.

We will now define mixed-strategy extensions, where the randomization
described in the example becomes possible: The strategy of playing each of the
three gestures with probability $\frac{1}{3}$ becomes a valid strategy itself,
a _mixed strategy_. The original strategies where no mixing occurs are then
called _pure strategies_. The strategies in a mixed-strategy extension are
functions that assign to each pure strategy a probability, and the payoffs are
calculated as expected values.

######  Definition 3.12 (Mixed Extensions, e.g. [MS16]).

Let $G=(n{,}(S_{1}{,\dots,}S_{n}){,}(u_{1}{,\dots,}u_{n}))$ be a finite
normal-form game. Its _mixed extension_
$\hat{G}=(n,(\Delta_{1},\dots,\Delta_{n}),(\hat{u}_{1},\dots,\hat{u}_{n}))$ is
defined by the following components for each player $k\in[n]$:

  * •

The strategy set $\Delta_{k}$ represents _mixed strategies_ : 111The exact
notation used differs across the literature. Our notation $\Delta_{k}$ for the
mixed-strategy sets is used, for example, in [Qua+09].

$\displaystyle\Delta_{k}\coloneqq\biggl{\\{}\delta:S_{k}\to\mathbb{R}_{\geq
0}\biggm{|}\sum_{s_{k}\in
S_{k}}\delta(s_{k})=1\biggr{\\}}\subseteq\mathbb{R}_{\geq 0}^{S_{k}}.$

  * •

$\Delta\coloneqq\bigtimes\limits_{i\in[n]}\Delta_{i}$ denotes the set of
_mixed strategy profiles_.

  * •

The utility function $\hat{u}_{k}:\Delta\to\mathbb{R}$ maps to each mixed
strategy profile the _expected value_ of the $k$-th player’s payoff under that
strategy profile:

$\displaystyle\hat{u}_{k}:(\delta_{1},\dots,\delta_{n})\mapsto\sum_{(s_{1},\dots,s_{n})\in
S}\biggl{(}\prod_{i=1}^{n}\delta_{i}(s_{i})\biggr{)}\cdot
u_{k}((s_{1},\dots,s_{n})).$ (1)

The _support_ of a mixed strategy $\delta_{k}\in\Delta_{k}$ is the set
$\operatorname{supp}\delta_{k}\coloneqq\\{s\in S_{k}\mid\delta_{k}(s)>0\\}$ of
pure strategies it mixes between with positive probability.

######  Remark 3.13.

  1. 1.

We denote the mixed strategies as functions $\delta:S_{k}\to\mathbb{R}_{\geq
0}$, assigning to each strategy $s_{k}\in S_{k}$ its probability
$\delta(s_{k})$ of being played. An alternative point of view is to interpret
$\Delta_{k}$ as a subset of $\mathbb{R}^{\left|S_{k}\right|}$, where each
mixed strategy is a probability vector. In this view, $\Delta_{k}$ is the
standard $(\left|S_{k}\right|-1)$-simplex. There is no difference between the
two variants except for notation, and we will switch to the variant using
probability vectors wherever it is more useful.

  2. 2.

The map $\hat{u}_{k}$ as defined in $\eqref{eq:mixedStrategyUtility}$ is
linear in its coordinates (more formally, a restriction of a linear map on the
convex set of valid probability vectors): Let
$\delta=(\delta_{1},\dots,\delta_{n})\in S$, $k\in[n]$, and
$\delta_{k}\in\Delta_{k}$ be a convex combination of the form
$\delta_{k}=\alpha_{1}\delta_{k,1}+\alpha_{2}\delta_{k,2}$ with strategies
$\delta_{k,1},\delta_{k,2}\in\Delta_{k}$. Then

$\displaystyle\hat{u}_{k}(\delta_{k},\delta_{-k})\leavevmode\nobreak\ $
$\displaystyle=\sum_{(s_{1},\dots,s_{n})\in S}\biggl{(}\prod_{i=1,i\neq
k}^{n}\delta_{i}(s_{i})\biggr{)}\cdot(\alpha_{1}\delta_{k,1}(s_{k})+\alpha_{2}\delta_{k,2}(s_{k}))\cdot
u_{k}((s_{1},\dots,s_{n}))$
$\displaystyle=\sum_{j=1,2}\alpha_{j}\left(\sum_{(s_{1},\dots,s_{n})\in
S}\biggl{(}\prod_{i=1,i\neq
k}^{n}\delta_{i}(s_{i})\biggr{)}\cdot\delta_{k,j}(s_{k})\cdot
u_{k}((s_{1},\dots,s_{n}))\right)$
$\displaystyle=\alpha_{1}\hat{u}_{k}(\delta_{k,1},\delta_{-k})+\alpha_{2}\hat{u}_{k}(\delta_{k,2},\delta_{-k}).$

  3. 3.

When a game is specified by a table or matrix of payoffs, the usual
interpretation from now on is that the matrix represents the corresponding
mixed-extension game. To distinguish between properties of a finite game and
its mixed extension, we say that the game has a certain property _in pure
strategies_ or _in mixed strategies_ : For example, we could say that rock-
paper-scissors has no Nash equilibrium in pure strategies, but it does have
one in mixed strategies. Keep in mind that the mixed extension game $\hat{G}$
is still a game that fits Definition 3.2: Where possible, we will state
results for general games without making distinctions for pure-strategy and
mixed-strategy games, and use the notations $S_{k}$ and $u_{k}$ instead of
$\Delta_{k}$ and $\hat{u}_{k}$ (so by writing $S_{k}$ or $u_{k}$, we do _not_
automatically refer only to finite games).

######  Definition 3.14.

The mixed extension $\hat{G}$ of a finite game $G$ is called a _bimatrix
game_. If $G$ is a zero-sum game, $\hat{G}$ is called a _matrix game_.

Allowing mixed strategies is crucial for the existence of Nash equilibria, as
there are many games that do not have pure Nash equilibria. There are results
that show that randomly chosen games have pure Nash equilibria with decreasing
probability as the game size grows, which are as summarized in the following
theorem:

######  Theorem 3.15 ([GGN68], also cf. [p.15]bib:matsumotoGameTheory[Exercise
1.2]bib:nisanAlgorithmicGameTheoryCh1Basic).

  1. 1.

Consider finite two-player _matrix_ (i.e. zero-sum) games with $m$ and $n$
pure strategies for player 1 and 2, where all the $mn$ payoffs are picked iid
from the same continuous probability distribution. The probability that such a
game has a Nash equilibrium in pure strategies is
$p_{m,n}=\frac{m!n!}{(m+n-1)!}$ which approaches zero for large $m,n$.

  2. 2.

Consider finite _bimatrix_ games with $m$ and $n$ pure strategies for player 1
and 2, where all the $2mn$ payoffs are picked iid from the same continuous
probability distribution. The probability that such a game has a Nash
equilibrium in pure strategies is
$\hat{p}_{m,n}=1-\sum_{k=0}^{\min(m,n)}(-1)^{k}k!\binom{m}{k}\binom{n}{k}\left(\frac{1}{mn}\right)^{k}$,
which approaches $1-1/e\approx 0.632$ for large $m,n$.

To give some example numbers: In the zero-sum case,
$p_{2,2}=\frac{2}{3},p_{3,3}=\frac{3}{10}$, and $p_{10,10}\approx 0.01\%$. In
the bimatrix case, $\hat{p}_{2}=\frac{7}{8},\hat{p}_{3}\approx
78.6\%,\hat{p}_{10}\approx 67.2\%$. The theorem shows that in the two-player
case, increasingly large random zero-sum games have pure-strategy Nash
equilibria with a probability converging to zero. Random non-zero-sum games
have pure-strategy Nash equilibria with a surprisingly high probability, but
in the limit, still over one third of those games do not have pure Nash
equilibria.

On the other hand, bimatrix games always have at least one mixed-strategy Nash
equilibrium. This is one of the core results of non-cooperative game theory,
and was famously proved by John Nash in [Nas50].

######  Theorem 3.16 (Existence of Mixed-Strategy Nash Equilibria, e.g. [FT91,
Section 1.3.1]).

Every mixed extension of a finite game has a Nash equilibrium.

We will give a proof of this theorem in Section 5, but first introduce some
more concepts relevant for the proof.

######  Example 3.17.

The Rock-Paper-Scissors game from Example 3.11 has the mixed-strategy Nash
equilibrium
$\bigl{(}(\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},\frac{1}{3})\bigr{)}$.
We will later see a way to prove this, and partially go through the proof,
when looking at methods to compute Nash equilibria.

A different way to characterize Nash equilibria, which has interesting
consequences for mixed-strategy games, is by _best responses_.

######  Definition 3.18 (Best responses, see [FT91]).

Let $G$ be a game. For each $k\in[n]$, define

$\displaystyle
r_{k}:S\to\operatorname{\mathcal{P}}(S_{k}),\leavevmode\nobreak\
r_{k}(s)=\biggl{\\{}s_{k}\in
S_{k}\bigm{|}u_{k}(s_{k},s_{-k})=\max_{\tilde{s}_{k}\in
S_{k}}u_{k}(\tilde{s}_{k},s_{-k})\biggr{\\}}.$

We call a strategy $s_{k}\in r_{k}(s)$ a _best response_ to the strategy
profile $s\in S$ (or alternatively to $s_{-k}$). Since $r_{k}(s)$ depends only
on $s_{-k}$, we also write $r_{k}(s_{-k})$ instead of $r_{k}(s)$ where more
convenient [FT91]. 222Nevertheless, $r_{k}$ takes arguments from $S$ as this
will notationally simplify the proof of Theorem 3.16.

Using this definition, a Nash equilibrium can be characterized as a strategy
profile in which the strategy for each player is a best response to the
profile.

######  Theorem 3.19.

Let $G$ be a game. A strategy profile $(s_{1},\dots,s_{n})\in S$ is a Nash
equilibrium if and only if

$\displaystyle\forall k\in[n]:s_{k}\in r_{k}(s).$

###### Proof.

If $s_{k}\in r_{k}(s)$ for all players $k\in[n]$, then $\forall
k\in[n],\forall\tilde{s}_{k}\in S_{k}:u_{k}(s_{k},s_{-k})\geq
u_{k}(\tilde{s}_{k},s_{-k})$, making $s$ a Nash equilibrium. Otherwise if for
some $k$, $s_{k}\notin r_{k}(s)$, there exists some strategy $\tilde{s}_{k}$
such that $u_{k}(\tilde{s}_{k},s_{-k})\geq u_{k}(s_{k},s_{-k})$, so $s$ is not
a Nash equilibrium. ∎

An important fact is that best-response mixed strategies always mix between
best-response pure strategies:

######  Theorem 3.20 (see [Pap07, Theorem 2.1]).

Let $G$ be the mixed extension of a finite game. Let $s_{k}\in\Delta_{k}$ be a
mixed strategy with $\operatorname{supp}s_{k}=\\{s_{k,1},\dots,s_{k,m}\\}$,
i.e. $s_{k}$ is a convex combination
$s_{k}=\sum_{i=1}^{m}\alpha_{i}s_{k,i},\leavevmode\nobreak\
\sum_{i=1}^{m}\alpha_{i}=1$. Then for any strategy profile $s\in S$:

$\displaystyle s_{k}\in r_{k}(s)\Leftrightarrow\forall j\in[m]:s_{k,j}\in
r_{k}(s).$

###### Proof.

Because $u_{k}(\,\cdot\,,s_{-k})$ is linear (see Remark 3.13), we get
$u_{k}(s_{k},s_{-k})=\sum_{i=1}^{m}\alpha_{i}u_{k}(s_{k,i},s_{-k})$. Assume
that one $s_{k,j}$ has a smaller payoff than $s_{k}$: Then some other
$s_{k,i}$ must have a greater payoff than $s_{k}$, as else
$\sum_{i=1}^{n}\alpha_{i}u_{k}(s_{k,i},s_{-k})<u_{k}(s_{k},s_{-k})$ because
the sum is a weighted average. Because there is a strategy with greater
payoff, $s_{k}$ is not a best response, leading to a contradiction. For the
converse, assume that all $s_{k,j}$ are best responses, i.e. have equal
payoffs. By the linearity, $s_{k}$ has the same payoff, making it a best
response as well. ∎

######  Corollary 3.21.

If $s=(s_{1},\dots,s_{n})\in S$ is a Nash equilibrium, and the $k$-th player’s
strategy $s_{k}$ mixes between pure strategies
$s_{k,1},\dots,s_{k,m}\in\Delta_{k}$, then the payoff of all the $s_{k,j}$
with respect to $s_{-k}$ is equal; Furthermore, the payoff of any strategy
mixing between them is the same as well:

$\displaystyle\forall j:u_{k}(s_{k,j},s_{-k})=u_{k}(s_{k},s_{-k}),$ (2)
$\displaystyle\forall\tilde{s}_{k}\in\Delta_{k}:\operatorname{supp}\tilde{s}_{k}\subseteq\operatorname{supp}s_{k}\Rightarrow
u_{k}(\tilde{s}_{k},s_{-k})=u_{k}(s_{k},s_{-k}).$ (3)

###### Proof.

Since $s$ is a Nash equilibrium, the mixed strategy $s_{k}$ is a best response
to $s$ by theorem 3.19. By theorem 3.20, all pure strategies $s_{k,j}$ are
best responses as well. By the definition of best responses, they therefore
must all have the same payoff. By the linearity of $u_{k}(\,\cdot\,,s_{-k})$,
a mixed strategy mixing between pure strategies with equal payoff has the same
payoff. ∎

A possible interpretation of Theorem 3.20 and Corollary 3.21 is that a player,
given some strategies $s_{-k}$ of other players, does not mix his own
strategies in order to achieve a better payoff; the purpose of mixing
strategies is rather to enable a Nash equilibrium, since only the right mixing
leads to a situation where the other players have no incentive to deviate. We
will need these results in later chapters when analyzing more general games
with lexicographically-ordered outcomes, but most importantly, we will see how
they can be applied to compute Nash equilibria later in this chapter.

###  5 Proof of Existence of a Mixed-Strategy Nash Equilibrium

The existence of a mixed-strategy Nash equilibrium in every bimatrix game
(Theorem 3.16) was first proved by John Nash in a one-page article [Nas50].
His proof is based on the characterization of Nash equilibria by best
responses (Theorem 3.19) and non-constructively finds an equilibrium point by
Kakutani’s Fixed Point Theorem, a generalization of Brouwer’s Fixed Point
Theorem to set-valued functions.

######  Definition 3.22 (e.g. [FT91, p.30]).

Let $S\subseteq\mathbb{R}^{n}$. A set-valued function
$\varphi:S\to\operatorname{\mathcal{P}}(S)$ _has a closed graph_ if for all
convergent sequences $(x_{n})_{n\in\mathbb{N}}$, $(y_{n})_{n\in\mathbb{N}}$ in
$S$,

$\displaystyle(\forall
n:y_{n}\in\varphi(x_{n}))\implies\lim\limits_{n\rightarrow\infty}y_{n}\in\varphi\left(\lim\limits_{n\rightarrow\infty}x_{n}\right).$

Kakutani’s original paper does not use the closed graph property, but instead
uses the concept of _upper semi-continuity_ , which is equivalent in the case
we are looking at. This is because in the following theorem $S$ is compact,
and $\varphi:S\to\operatorname{\mathcal{P}}(S)$ takes only closed (and
therefore compact) sets as values (see
bib:kakutaniFixedPointTheorem[Proposition 11.9,
(a)-(b)]bib:borderFixedPointTheorems).

######  Theorem 3.23 (Kakutani’s Fixed Point Theorem, see [Kak41], [FT91,
p.29f]).

Let $S\subseteq\mathbb{R}^{n}$. Let
$\varphi:S\to\operatorname{\mathcal{P}}(S)$ be a function with the following
properties:

  1. 1.

$S$ is non-empty, compact and convex.

  2. 2.

$\forall s\in S:\varphi(s)$ is non-empty, convex and closed.

  3. 3.

$\varphi$ has a closed graph.

Then $\varphi$ has a fixed point $x$, i.e. an $x\in S$ such that
$x\in\varphi(x)$.

We are not giving a proof for Kakutani’s Theorem, but equipped with it, we can
prove Theorem 3.16 that every bimatrix game has a Nash equilibrium in mixed
strategies.

###### Proof of Theorem 3.16, cf. [FT91, p.29].

In the context of this proof, let each player $k\in[n]$ have $m_{k}$ different
pure strategies and set $m\coloneqq m_{1}+\dots+m_{n}$. We represent mixed
strategy profiles as points in $\mathbb{R}^{m}$: Let
$\Delta_{k}\coloneqq\\{(p_{1},\dots,p_{m_{k}})\in\mathbb{R}^{m_{k}}\mid\sum_{i=1}^{m_{k}}p_{i}=1\\}$
(the standard $(m_{k}-1)$-simplex) and let
$\Delta\coloneqq\bigtimes_{k=1}^{n}\Delta_{k}\subseteq\mathbb{R}^{m}$. In
other words, here we do not view mixed strategies as functions
$\delta:S_{k}\to\mathbb{R}_{\geq 0}$, but instead interpret them as real
vectors.

Next we define $r:\Delta\to\operatorname{\mathcal{P}}(\Delta)$ as the _best-
response correspondence_. Recall that ${r_{k}:\Delta\to\Delta_{k}}$ maps
mixed-strategy profiles to the set of _best-response mixed strategies_ for the
$k$-th player. Now $r$ incorporates this information for all players at once,
mapping mixed-strategy profiles to the set of _best-response mixed-strategy
profiles_ :

$\displaystyle
r:\Delta\to\operatorname{\mathcal{P}}(\Delta),(\delta_{1},\dots,\delta_{n})\mapsto
r_{1}(\delta_{1},\dots,\delta_{n})\times\dots\times
r_{n}(\delta_{1},\dots,\delta_{n}).$ (4)

By Theorem 3.19, mixed-strategy Nash equilibria are exactly the fixed points
of $r$, i.e. strategy profiles that are best responses to themselves: So if we
show that the conditions of Kakutani’s Fixed Point Theorem are satisfied, this
shows that $r$ has a fixed point, and we have proved that mixed-strategy Nash
equilibria always exist.

On 1 (conditions on $\Delta$): The $\Delta_{k}$ are clearly non-empty, compact
and convex as simplices. Therefore $\Delta$ is also non-empty, as well as
compact and convex as the finite Cartesian product of compact and convex sets.

On 2 (the set $r(s)$ of best-response profiles is non-empty, convex and closed
for all $s\in\Delta$): It suffices to show that these conditions hold for each
$r_{k}(s)$, since $r(s)$ is the finite product of those. Let $k\in[n]$. By
Theorem 3.20, best-response mixed strategies are exactly the convex
combinations of best-response pure strategies. Therefore $r_{k}(s)$ is the
convex hull of the $k$-th player’s pure best response strategies to $s_{-k}$.
As a convex hull of a finite set, $r_{k}(s)$ is convex and closed.
Furthermore, $r_{k}(s)$ is non-empty: Mixed strategies cannot have larger
payoffs than the best pure strategy in their support. Since there are only
finitely many pure strategies in the support, at least one of them maximizes
$u(\,\cdot\,,s_{-k})$.

On 3 ($r$ has a closed graph): We need to show that if a sequence of mixed-
strategy profiles converges, and a corresponding sequence of best-response
profiles also converges, then the limit of the best responses is a best
response to the limit of the strategy profiles. Let
$\left(s^{(i)}\right)_{i\in\mathbb{N}}$ be a convergent sequence of strategy
profiles, and $\left(t^{(i)}\right)_{i\in\mathbb{N}}$ a convergent sequence of
best responses to the $s^{(i)}$:

$\displaystyle
s^{(i)}=\left(s_{1}^{(i)},\dots,s_{n}^{(i)}\right)\xrightarrow{\;i\to\infty\;}(s_{1},\dots,s_{n})=:s,$
$\displaystyle
t^{(i)}=\left(t_{1}^{(i)},\dots,t_{n}^{(i)}\right)\xrightarrow{\;i\to\infty\;}(t_{1},\dots,t_{n})=:t,\quad\forall
i:t^{(i)}\in r\left(s^{(i)}\right).$

If we show that $t_{k}\in r_{k}(s)$ for all players $k$, we get $t\in r(s)$ by
(4). Let $\tilde{t}_{k}\in\Delta_{k}$ be some arbitrary response. We show that
$\tilde{t}_{k}$ is not a better response than $t_{k}$: First, for any
$i\in\mathbb{N}$, $t^{(i)}_{k}$ is a best response to $s^{(i)}_{-k}$, so

$\displaystyle u_{k}\left(t^{(i)}_{k},s^{(i)}_{-k}\right)\geq
u_{k}\left(\tilde{t}_{k},s^{(i)}_{-k}\right).$

The payoff function $u_{k}$ is continuous, since it is a restriction of a
linear function between finite-dimensional spaces. Therefore in the limit as
$i\to\infty$, the left side converges to $u_{k}(t_{k},s_{-k})$ while the right
side converges to $u_{k}(\tilde{t}_{k},s_{-k})$. Recall that the ordering
$\geq$ on the reals is preserved under limits (in other words, it is closed as
a subset of $\mathbb{R}\times\mathbb{R}$). 333A consequence of the “sandwich
theorem”. We emphasize this here since this continuity property does not hold
for general orderings on topological spaces: in particular, it will be
important later that it does _not hold_ for the lexicographic ordering on
$\mathbb{R}^{n}$. Therefore,

$\displaystyle u_{k}(t_{k},s_{-k})\geq u_{k}(\tilde{t}_{k},s_{-k}).$

So $t_{k}$ maximizes the payoff over all responses to $s_{-k}$, therefore
$t_{k}\in r(s_{-k})$. This shows that $r$ has a closed graph. Thus $r$
satisfies the conditions of Kakutani’s theorem and therefore has a fixed
point, which is a Nash equilibrium for the game by Theorem 3.19. ∎

###  6 Computation of Nash Equilibria

It is important to have a way to compute Nash equilibria, especially for
practical purposes, but also for theoretical justification of Nash equilibria
as a prediction of rational behavior: As [Pap07, p.30] cites Kamal Jain, “If
your laptop cannot find it, neither can the market.” There are various exact
and numerical algorithms to compute Nash equilibria, and for the two-player
case we will look at the simple exact method called the _support enumeration
algorithm_ which can be executed by hand, and also the numerical _fictitious
play algorithm_ which approximates a Nash equilibrium by simulating several
rounds of play and refining the strategies over time based on the past
actions.

####  6.1 Exact Computation

Mixed Nash equilibria in bimatrix games can be computed exactly by a simple
method called the _support enumeration algorithm_. Our presentation follows
[Ste07]. We assume the game’s payoffs are specified by matrices
$A,B\in\mathbb{R}^{n\times m}$, and the players have pure strategies
$S_{1}=\\{s_{1},\dots,s_{n}\\}$, $S_{2}=\\{t_{1},\dots,t_{m}\\}$,
respectively. Observe that (1) simplifies in the following way: If
$x=(x_{1},\dots,x_{n})\in\mathbb{R}_{\geq 0}^{n}$ represents a mixed strategy
of player 1 and $y=(y_{1},\dots,y_{m})\in\mathbb{R}_{\geq 0}^{m}$ one of
player 2, then the players’ payoffs are given by $u_{1}(x,y)=x^{T}Ay$ and
$u_{2}(x,y)=x^{T}By$.

If $(x,y)$ is a Nash equilibrium, then the first player’s pure strategies in
$\operatorname{supp}(x)$ must all be best responses to $y$, i.e. they all have
equal payoff, and no other pure strategy can have greater payoff under $y$.
This is a consequence of Theorem 3.20, and in [Ste07, p.55] is stated in the
following form:

$\displaystyle\forall
i:x_{i}>0\Rightarrow(Ay)_{i}=\max_{\tilde{i}}(Ay)_{\tilde{i}}.$ (5)

The same holds with the player roles reversed.

Suppose we want to find a Nash equilibrium where player one mixes between rows
with indices in $I\subseteq[n]$, and player 2 mixes between columns with
indices in $J\subseteq[m]$. Then player 1 must mix in a way that makes player
2 indifferent between the columns in $J$, and player 2 must mix in a way that
makes player 1 indifferent between the rows in $I$. This is expressed in two
linear systems of equations, where
$i_{1}\coloneqq\min(I),j_{1}\coloneqq\min(J)$ are the smallest indices in $I$
and $J$, respectively:

$\displaystyle(Ay)_{i_{k}}=(Ay)_{i_{1}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\forall i_{k}\in
I\setminus\\{i_{1}\\}),\qquad\;\,\sum_{j\in J}y_{j}=1$ (6)
$\displaystyle(xB)_{j_{k}}=(xB)_{j_{1}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\forall j_{k}\in
J\setminus\\{j_{1}\\}),\qquad\sum_{i\in I}x_{i}=1$ (7)

If some strategy profile $(x,y)$ solves this system of equations, it is a
candidate for a mixed-strategy Nash equilibrium. It remains to check that all
probabilities in the solution are non-negative. Also we have to make sure the
mixed strategies actually have maximal payoffs as demanded by (5): For each
$\tilde{i}\in I^{\complement}$ we have to check that
$(Ay)_{\tilde{i}}\leq(Ay)_{i_{1}}$, and analogously for $J$.

The algorithm we discuss needs one additional assumption, that the games
involved are _non-degenerate_ :

######  Definition 3.24 ([Ste07, Definition 3.2]).

A mixed extension $G$ of a two-player finite game is _degenerate_ if one
player has a mixed strategy of support size $m$ that has more than $m$ pure
best responses by the other player. Otherwise, it is _non-degenerate_.

In [Ste07, p.54], it is noted that “almost all” (two-player mixed-extension)
games are non-degenerate. We can now put together the _support enumeration
algorithm_ [Ste07, Algorithm 3.4]: We iterate over all possible pairs of
support indices $(I,J)$ with $\left|I\right|=\left|J\right|$, for each one go
through the steps outlined above, and output all solutions of the linear
system that satisfy the two additional properties (no negative probabilities
and only best-response pure strategies in the support). The assumption that
the game is non-degenerate assures that the linear systems that occur in the
algorithm do not have more than one solution: If we included degenerate games,
we could not simply output all solutions, since there could be infinitely
many. There are ways to deal with degenerate games as well which we will not
go into here (see [Ste07, p.65], where an algorithm is discussed in detail).

######  Example 3.25 (Computation of Rock-Paper-Scissors Equilibrium).

We can compute the rock-paper-scissors Nash equilibrium from Example 3.11
using the support enumeration algorithm. We will not go through the whole
computation, but only look at the cases $(I,J)=(\\{1,2\\},\\{1,2\\})$,
$(I,J)=(\\{2,3\\},\\{1,2\\})$ (which are not Nash equilibria) and
$(I,J)=(\\{1,2,3\\},\\{1,2,3\\})$ (which is a Nash equilibrium). Remember that
the payoff matrices are given by $\pm\left(\begin{smallmatrix}0&-1&1\\\
1&0&-1\\\ -1&1&0\end{smallmatrix}\right)$. We denote by $p_{1},p_{2},p_{3}$
the probabilities the strategy of player 1 assigns to the rows, and by
$q_{1},q_{2},q_{3}$ the probabilities the strategy of player 2 assigns to the
columns.

For the first pair of indices, $p_{1},p_{2}$ should be chosen in a way that
makes player 2 indifferent between the first two columns. The corresponding
equations are $0p_{1}-1p_{2}=1p_{1}+0p_{2}$ and $p_{1}+p_{2}=1$. There is no
solution, so this pair does not lead to a Nash equilibrium.

For the second pair, the corresponding equations are
$-p_{2}+p_{3}=-p_{3},p_{2}+p_{3}=1$ with the solution
$p_{2}=\frac{2}{3},p_{3}=\frac{1}{3}$. The payoff player 2 has for each of the
first two columns in this case is $-\frac{1}{3}$. However the payoff player 2
has for the third column is $\frac{2}{3}$, so the first two columns are not
best responses: This combination does also not lead to a Nash equilibrium.

Finally for the third pair of indices, the equations are
$-p_{2}+p_{3}=p_{1}-p_{3}$, $-p_{2}+p_{3}=-p_{1}+p_{3}$, and
$p_{1}+p_{2}+p_{3}=1$, with the solution $p_{1}=p_{2}=p_{3}=\frac{1}{3}$.
Similarly the equations for player 2 to make player 1 indifferent between all
rows are $-q_{2}+q_{3}=q_{1}-q_{3}$, $-q_{2}+q_{3}=-q_{1}+q_{2}$, and
$q_{1}+q_{2}+q_{3}=1$, again with the solution
$q_{1}=q_{2}=q_{3}=\frac{1}{3}$. Since all solutions are positive, and no
other rows/columns could be better responses, this shows that
$\left((\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},\frac{1}{3})\right)$
is a Nash equilibrium of the Rock-Paper-Scissors game.

#####  6.1.1 Complexity Considerations

The support enumeration algorithm is obviously quite inefficient, since it
enumerates all subsets of the pure strategy sets for both players, and
therefore is exponential in the number of strategies. [Ste07] investigates
more sophisticated methods: The _vertex enumeration algorithm_ finds possible
supports of mixed strategies by iterating over the vertices of certain
polyhedra (“best-response polytypes”) and outputs all Nash equilibria. The
_Lemke-Howson algorithm_ finds one Nash equilibrium by traversing a path in
those polytypes. However, these improvements still have exponential worst-case
complexities, and complexity-theoretic results suggest that finding Nash
equilibria in general, even in two-player games, is an intractable problem. As
discussed in detail in [Pap07], the problem Nash of finding a Nash equilibrium
is complete for the complexity class PPAD, which contains other problems for
which an efficient algorithm is thought unlikely to exist, like finding fixed
points in the context of Brouwer’s fixed point theorem. Finding Nash
equilibria does not fit into the more common intractability notion of NP
completeness, because Nash equilibria are guaranteed to exist – the problem
can therefore not be stated suitably as a decision problem. However, there are
a number of closely related variations where existence is not guaranteed and
which are known to be NP-complete: For example, deciding whether a game has
more than one Nash equilibrium, whether a Nash equilibrium with at least a
given utility exists, and whether a Nash equilibrium exists with a given
strategy in (or not in) its support, are all NP-complete problems ([GZ89],
cited in [Pap07]).

####  6.2 Approximate Computation: Fictitious Play

A different approach for finding Nash equilibria is to simulate repeated play
of the game by players that are learning from past outcomes. We follow the
presentation of [Das11]. We again assume a bimatrix game with payoff matrices
$A,B$. In every new round, each player averages over the past strategies of
their opponent. Under the assumption that the opponent will play this average
mixed strategy, the players picks their own pure strategy for this round that
maximizes their payoff. Formally, denote by $s^{(k)}\in S_{1},t^{(k)}\in
S_{2}$ the strategies played in the $k$-th round, and $x^{(k)},y^{(k)}$ the
corresponding average strategies, defined iteratively by:

$\displaystyle x^{(k)}=\frac{1}{k}\sum_{i=1}^{k}s^{(i)},\quad
y^{(k)}=\frac{1}{k}\sum_{i=1}^{k}t^{(i)},$ $\displaystyle s^{(1)}\in
S_{1},\;t^{(1)}\in S_{2}\text{ arbitrary},$ $\displaystyle
s^{(k+1)}\in\mathop{\operatorname{argmax}}\limits_{\tilde{s}\in
S_{1}}(u_{1}(\tilde{s},y^{(k)})),\quad
t^{(k+1)}\in\mathop{\operatorname{argmax}}\limits_{\tilde{t}\in
S_{2}}(u_{2}(x^{(k)},\tilde{t})).$

Where there are multiple strategies that could be pick, we arbitrarily define
the algorithm to always prefer the one with the lowest index.

In the special case of zero-sum games, this process was shown to converge by
[Rob51]; we will state the result without proof. In the non-zero-sum case,
however, there are examples of bimatrix games for which fictitious play does
not converge.

######  Theorem 3.26 (Convergence of Fictitious Play, [Rob51]).

If the game is a zero-sum game, i.e. $A=-B$, then

  1. 1.

The sequence $(u_{1}(x_{k},y_{k}))_{k\in\mathbb{N}}$ converges towards the
value of the game.

  2. 2.

The sequence $((x_{k},y_{k}))_{k\in\mathbb{N}}$ converges towards a Nash
equilibrium $(x,y)$.

Note that it is quite possible that for no value of $k$, $(x_{k},y_{k})$
actually forms a Nash equilibrium. To deal with situations like this, there is
the notion of $\varepsilon$-approximate Nash equilibria, where deviation from
the equilibrium gains players at most $\varepsilon$ additional payoff.

######  Definition 3.27.

Let $\varepsilon>0$. A strategy profile $s=(s_{1},\dots,s_{n})\in S$ is an
_$\varepsilon$ -approximate Nash equilibrium_ if

$\displaystyle\forall k:\forall\tilde{s_{k}}\in S_{k}:u_{k}(s_{k},s_{-k})\geq
u_{k}(\tilde{s_{k}},s_{-k})-\varepsilon.$

The second result of 3.26 can now be stated as follows:

######  Corollary 3.28.

If the game is zero-sum, for any $\varepsilon>0$, there is some
$K\in\mathbb{N}$ such that for all $k\geq K$, the result after $k$ rounds of
fictitious play $(x_{k},y_{k})$ is an $\varepsilon$-Nash equilibrium.

##  Chapter 4 Games with Distributional Payoffs

The previous chapter established the basic concepts of standard game theory,
where payoffs are real numbers. The goal of this chapter is to introduce and
analyze a theory of games that instead have probability distributions as
payoffs. To specify the players’ preferences for outcomes in this setting, we
use stochastic orders which compare probability distributions. The model of
distribution-valued games was first introduced by Stefan Rass in the context
of IT security ([Ras15, Ras15a, Ras17]), and in this model probabilistic
outcomes are rated based on a stochastic order we call the _tail order_
([RKS16]). We start with a generalization of this model and first introduce
games with an arbitrary payoff set, where preferences are expressed by
preorders on this set, and define distribution-valued games as a special case
of these. We then focus on the tail order, discuss its properties as an
ordering, and analyze the existence of Nash equilibria in distribution-valued
games with tail order preferences.

###  7 Normal-Form Games with Generalized Payoffs

As a general framework, we define games where the payoffs lie in an arbitrary
set. The players’ preferences between payoffs are expressed by preorders on
the payoff set.

######  Definition 4.1 (Preorder).

A _preorder_ $\leq$ on some set $A$ is a reflexive and transitive binary
relation on $A$:

$\displaystyle\forall a\in A:a\leq a.$ (Reflexivity) $\displaystyle\forall
a,b,c\in A:a\leq b,b\leq c\implies a\leq c.$ (Transitivity)

Additional properties of orders that a preorder does _not_ need to satisfy
are:

$\displaystyle\forall a,b\in A:a\leq b,a\geq b\implies a=b.$ (Antisymmetry)
$\displaystyle\forall a,b\in A:a\leq b\vee a\geq b.$ (Totality)

We define $a\geq b\coloneqq b\leq a$ and
$a<b\mathrel{\vcentcolon\Leftrightarrow}a\leq b\wedge\neg(a\geq b)$. If both
$a\leq b$ and $a\geq b$, we say that $\leq$ is _indifferent_ between the two
elements. Antisymmetric preorders are never indifferent between different
elements. Total preorders order any pair of elements, so no two elements are
incomparable. Since neither property is required, preorders in general may
exhibit indifference as well as incomparability.

######  Definition 4.2 (Game with Generalized Payoffs).

A _game with generalized payoffs in $A$_,
$G=(n,A,(S_{1},\dots,S_{n}),(u_{1},\dots,u_{n}))$ with $n$ players consists of
a payoff set $A$, strategy sets $S_{k}$ and a payoff function $u_{k}:S\to A$
for each player $k\in[n]$, where $S\coloneqq\bigtimes_{k\in[n]}S_{k}$. Such a
game can be _equipped with preorders_ $(\leq_{1},\dots,\leq_{n})$, written
$G_{(\leq_{1},\dots,\leq_{n})}$, where each $\leq_{k}$ is a preorder on $A$
and represents the preferences of player $k\in[n]$ for the payoffs in $A$. If
all players have the same preference preorder $\leq$, we write $G_{\leq}$. $G$
is _finite_ if $S$ is a finite set.

We adopt the convention that the greater payoff with respect to a preorder is
preferred, i.e. if $x\leq y$, then $y$ is preferred. However as in real-valued
games, it will sometimes be more convenient to talk about costs instead of
utility (cf. Definition 3.2). We cannot simply define $c_{k}=-u_{k}$ in the
general setting of a preordered set $A$, however we can effectively treat the
payoffs as costs by choosing the preference preorders accordingly.

######  Definition 4.3 (Nash Equilibrium of Game with Generalized Payoffs).

Let $G$ be a game with generalized payoffs that is equipped with preorders
$(\leq_{1},\dots,\leq_{n})$. A _Nash equilibrium of_
$G_{(\leq_{1},\dots,\leq_{n})}$ (or a _Nash equilibrium of $G$ with respect to
$(\leq_{1},\dots,\leq_{n})$_) is a strategy profile $s=(s_{1},\dots,s_{n})\in
S$ such that for each player $k\in[n]$:

$\displaystyle\forall\tilde{s}_{k}\in
S_{k}:u_{k}(s_{k},s_{-k})\geq_{k}u_{k}(\tilde{s}_{k},s_{-k}).$ (8)

Similar as in the real-valued theory, we are especially interested in two-
player zero-sum games. But we are in some trouble defining what zero-sum is
supposed to mean: Obviously, in our general setting we have no notion of two
payoffs $a_{1},a_{2}\in A$ summing to zero. We can base our definition on
another crucial property of zero-sum games: Zero-sum games are _antagonistic_
– when one player wins, the other loses (see [And76]). This property _can_ be
generalized to our model.

######  Definition 4.4 (Antagonistic and Zero-Sum Games).

A two-player game with generalized payoffs $G_{(\leq_{1},\leq_{2})}$ is
_antagonistic_ if

$\displaystyle\forall s,t\in S:\leavevmode\nobreak\
u_{1}(s)\geq_{1}u_{1}(t)\leavevmode\nobreak\
\Leftrightarrow\leavevmode\nobreak\ u_{2}(s)\leq_{2}u_{2}(t).$

$G_{(\leq_{1},\leq_{2})}$ is _zero-sum_ if $u_{1}=u_{2}$, and
$\leq_{2}{=}\geq_{1}$: The players always get equal payoffs, but prefer them
just in reverse order.

The advantage of zero-sum games over antagonistic games is that the zero-sum
property is preserved when taking mixed extensions (which we will define
shortly), while the mixed extension of an antagonistic game needs not be
antagonistic. This is analogous to real-valued games, where mixed extensions
also preserve the zero-sum property, but not necessarily the antagonism
property (see [And76]). 444Note that not only zero-sum satisfy this property,
but constant-sum games as well, so our naming convention seems a bit
arbitrary. Yet “zero-sum” appears like the most recognizable and easily-
understood term for this concept, so we’ll stick to this name even though
nothing actually sums to zero.

It is possible to define mixed extensions if the payoff set $A$ has additional
vector-space structure. Since mixed strategies correspond to convex
combinations of pure strategies, we require $A$ be a convex subset of a real
vector space.

######  Definition 4.5 (Mixed extension).

Let $A$ be a convex subset of a real vector space. Let
$G=(n,A,(S_{1},\dots,S_{n}),(u_{1},\dots,u_{n}))$ be a finite game with
generalized payoffs in $A$. Its _mixed extension_
$\hat{G}=(n,A,(\Delta_{1},\dots,\Delta_{n}),(\hat{u}_{1},\dots,\hat{u}_{n}))$
consists of the following components for each player $k\in[n]$:

  * •

$\Delta_{k}\coloneqq\biggl{\\{}\delta\in\mathbb{R}_{\geq
0}^{S_{k}}\biggm{|}\sum_{s_{k}\in S_{k}}\delta(s_{k})=1\biggr{\\}}$ are the
_mixed strategies_ , $\Delta\coloneqq\bigtimes\limits_{i\in[n]}\Delta_{i}$ the
_mixed strategy profiles_.

  * •

The utility function $\hat{u}_{k}:\Delta\to A$ maps each mixed strategy
profile to its payoff:

$\displaystyle\hat{u}_{k}:(\delta_{1},\dots,\delta_{n})\mapsto\sum_{(s_{1},\dots,s_{n})\in
S}\biggl{(}\prod_{i=1}^{n}\delta_{i}(s_{i})\biggr{)}\cdot
u_{k}((s_{1},\dots,s_{n})).$ (9)

######  Remark 4.6.

As for real-valued games, we can specify payoffs by one or more matrices. We
use terms analogous to the real-valued theory, see Remark 3.13, 3: When
talking about the _bimatrix game_ specified by two matrices, we mean the mixed
extension of the finite game corresponding to the matrices. In the zero-sum
case, where only one matrix is specified, we will talk about _matrix games_.

As a last concept, we define the notion of _isomorphic_ games, which lets us
switch between different payoff sets that behave the same with respect to
compatible orderings.

######  Definition 4.7.

Let $G$, $H$ be two $n$-player games with generalized payoffs sharing the same
strategy sets $S_{k}$, where $G$ has payoffs $u_{k}:S\to A$ and $H$ has
payoffs $v_{k}:S\to B$. Let $G$ be equipped with
$(\leq_{1}^{\scriptscriptstyle G},\dots,\leq_{n}^{\scriptscriptstyle G})$, and
$H$ be equipped with $(\leq_{1}^{\scriptscriptstyle
H},\dots,\leq_{n}^{\scriptscriptstyle H})$. Then
$G_{(\leq_{1}^{\scriptscriptstyle G},\dots,\leq_{n}^{\scriptscriptstyle G})}$
is _isomorphic_ to $H_{(\leq_{1}^{\scriptscriptstyle
H},\dots,\leq_{n}^{\scriptscriptstyle H})}$ if there is a bijection
$\varphi:A\to B$ such that

$\displaystyle\forall k\in[n]:\leavevmode\nobreak\ v_{k}=\varphi\circ u_{k},$
(10) $\displaystyle\forall k\in[n]:\leavevmode\nobreak\ \forall a_{1},a_{2}\in
A:a_{1}\leq_{k}^{\scriptscriptstyle
G}a_{2}\Leftrightarrow\varphi(a_{1})\leq_{k}^{\scriptscriptstyle
H}\varphi(a_{2}).$ (11)

######  Remark 4.8.

The isomorphism property is symmetric: $G_{(\leq_{1}^{\scriptscriptstyle
G},\dots,\leq_{n}^{\scriptscriptstyle G})}$ is isomorphic to
$H_{(\leq_{1}^{\scriptscriptstyle H},\dots,\leq_{n}^{\scriptscriptstyle H})}$
iff $H_{(\leq_{1}^{\scriptscriptstyle H},\dots,\leq_{n}^{\scriptscriptstyle
H})}$ is isomorphic to $G_{(\leq_{1}^{\scriptscriptstyle
G},\dots,\leq_{n}^{\scriptscriptstyle G})}$, as we can use the bijection
$\varphi\operatorname{{}^{-1}}$. Therefore we can say that two games _are
isomorphic_ without specifying a direction.

The reason we use the concept of isomorphic games is that it lets us change
the payoff set of a game while preserving its Nash equilibria. This is shown
by the next lemma.

######  Lemma 4.9.

If two games with generalized payoffs $G_{(\leq_{1}^{\scriptscriptstyle
G},\dots,\leq_{n}^{\scriptscriptstyle G})}$, $H_{(\leq_{1}^{\scriptscriptstyle
H},\dots,\leq_{n}^{\scriptscriptstyle H})}$ are isomorphic, they have the same
Nash equilibria.

###### Proof.

Let $s=(s_{1},\dots,s_{n})\in S$ be a Nash equilibrium of
$G_{(\leq_{1}^{\scriptscriptstyle G},\dots,\leq_{n}^{\scriptscriptstyle G})}$.
We show that $s$ is a Nash equilibrium of $H_{(\leq_{1}^{\scriptscriptstyle
H},\dots,\leq_{n}^{\scriptscriptstyle H})}$. Let $k\in[n]$, $\tilde{s}_{k}\in
S_{k}$. We have
$v_{k}(\tilde{s}_{k},s_{-k})=\varphi(u_{k}(\tilde{s}_{k},s_{-k}))$. Because
$s$ is a Nash equilibrium of $G_{(\leq_{1}^{\scriptscriptstyle
G},\dots,\leq_{n}^{\scriptscriptstyle G})}$, we get
$u_{k}(\tilde{s}_{k},s_{-k})\leq_{k}^{\scriptscriptstyle
G}u_{k}(s_{k},s_{-k})$. By (11), this implies
$\varphi(u_{k}(\tilde{s}_{k},s_{-k}))\leq_{k}^{\scriptscriptstyle
H}\varphi(u_{k}(s_{k},s_{-k}))=v_{k}(s_{k},s_{-k})$. So
$v_{k}(\tilde{s}_{k},s_{-k})\leq_{k}^{\scriptscriptstyle
H}v_{k}(s_{k},s_{-k})$, proving the claim. By the symmetry pointed out in the
previous remark, it also holds that any Nash equilibrium of
$H_{(\leq_{1}^{\scriptscriptstyle H},\dots,\leq_{n}^{\scriptscriptstyle H})}$
is a Nash equilibrium of $G_{(\leq_{1}^{\scriptscriptstyle
G},\dots,\leq_{n}^{\scriptscriptstyle G})}$, concluding the proof. ∎

###  8 Distribution-Valued Normal-Form Games

In this section we use the framework from the previous section to introduce
distribution-valued games. This comes down to picking the right payoff set and
choosing a preorder on it. For the payoff set, let $\mathcal{D}$ denote the
set of Borel probability measures on $\mathbb{R}$:

$\displaystyle\mathcal{D}\coloneqq\\{P:\mathcal{B}\to\mathbb{R}_{\geq 0}\mid
P\text{ is a probability measure on }(\mathbb{R},\mathcal{B})\\}.$

Each element of $\mathcal{D}$ represents a probability distribution on the
real numbers. We write $\mathcal{D}_{\geq 0}$, $\mathcal{D}_{\geq 1}$, or
$\mathcal{D}_{[a,b]}$ for the subsets of $\mathcal{D}$ whose elements’
supports are contained in $[0,\infty)$, $[1,\infty)$, or some interval
$[a,b]$, respectively. Recall that for $k\in\mathbb{N}$,
$M^{k}\coloneqq\\{P\in\mathcal{D}\mid\int_{\mathbb{R}}\left|x\right|^{k}\,dP(x)<\infty\\}$
denotes the set of measures in $\mathcal{D}$ that have a finite moment of
order $k$.

######  Definition 4.10 (Stochastic Order).

A preorder on $\mathcal{D}$ is called a _stochastic order_. 555The reference
on stochastic orders [SS07] defines stochastic orders between random
variables, but for our purposes it is more convenient to define them between
distributions instead.

######  Example 4.11.

  1. 1.

Let $\preccurlyeq_{E}$ be the ordering that compares distributions by expected
value:

$\displaystyle
P_{1}\preccurlyeq_{E}P_{2}\mathrel{\vcentcolon\Leftrightarrow}\text{
$P_{1},P_{2}\in M^{1}$ and $E(P_{1})\leq E(P_{2})$}.$

Then $\preccurlyeq_{E}$ is a stochastic ordering, but neither antisymmetric
nor total. Antisymmetry fails to hold since many distributions can have the
same expected value, in which case $\preccurlyeq_{E}$ is indifferent between
them. Totality fails because not all distributions have a well-defined
expected value. However $\preccurlyeq_{E}$ is a total stochastic order on
$M^{1}$, which includes all distributions with bounded support.

  2. 2.

Let the _usual stochastic order_ $\preccurlyeq_{\text{st}}$ (see [SS07]) be
defined by

$\displaystyle
P_{1}\preccurlyeq_{\text{st}}P_{2}\mathrel{\vcentcolon\Leftrightarrow}\forall
x\in\mathbb{R}:P_{1}((x,\infty))\leq P_{2}((x,\infty)).$

Phrased in terms of distribution functions, this holds iff $F_{1}\geq F_{2}$
point-wise: For any $x\in X$, $F_{1}(x)\geq F_{2}(x)\Leftrightarrow
P_{1}((-\infty,x])\geq P_{2}((-\infty,x])$, which is equivalent to
$P_{1}((x,\infty))\leq P_{2}((x,\infty))$. The ordering captures a strong
notion of one distribution tending to take smaller values than the other.
Because of this strong requirement, it is not surprising that
$\preccurlyeq_{\text{st}}$ is not total and there are many pairs of
incomparable distributions. However the ordering is antisymmetric, because
$\preccurlyeq_{\text{st}}$ is indifferent only between probability measures
with equal distribution functions, and a distribution function uniquely
determines the probability measure.

######  Definition 4.12 (Distribution-Valued Game).

A game $G$ with generalized payoffs in $\mathcal{D}$ is called a
_distribution-valued game_.

The underlying semantics are that a distribution-valued game models a
situation where the outcomes have some probabilistic uncertainty associated
with them, whose distribution is known before-hand: When playing the game,
first an outcome distribution for each player is determined by the selected
strategies, and then the players gets their actual real-valued payoff drawn
from their distributions independently. However, the drawing from the outcome
distributions at the last step is not explicitly modeled. The stochastic
orders of the players reflect how each player values particular outcome
distributions. Figure 2 illustrates the definition with an example of the
first player’s payoffs in a distribution-valued game.

| $b_{1}$ | $b_{2}$
---|---|---
$a_{1}$ |  $\scriptstyle U([0,5])$ |  Half-Normal distribution
$a_{2}$ |  $\scriptstyle\text{Geom}(1/3)$ |  $\scriptstyle U(\\{1,2,3\\})$
Figure 2: Player 1 payoff matrix in a distribution-valued 2x2-game with both
AC and discrete distributions as payoffs (represented by their distribution
functions).

The definitions of Nash equilibria, zero-sum games and mixed extensions of
distribution-valued games can be adopted from Section 7. In particular, mixed
extensions can be defined because $\mathcal{D}$ is a convex subset of the real
vector space of signed finite Borel measures: A convex combination of several
distributions from $\mathcal{D}$, obtained by a mixed strategy, corresponds to
a mixture of the involved distributions.

The definition of zero-sum games may need some additional discussion: The
argument for the definition given in Section 7 was that without knowing more
about the structure of the payoff set, we could not define zero-sum games by
requiring that payoffs actually sum to zero. On the other hand, now that we
have a more concrete payoff set, possibly a more natural definition could be
made. However several seemingly “natural candidates” for such a definition do
not work: Let $s\in S$ be some strategy profile. Clearly, we cannot require
$u_{1}(s)+u_{2}(s)=0$ (the zero-everywhere measure), since probability
measures only assign non-negative values. If instead we let $X_{1}\sim
u_{1}(s),X_{2}\sim u_{2}(s)$ be independent random variables modeling the
random payoffs for the players, and require that $X_{1}+X_{2}=0$ almost
surely, this also fails: This condition will never hold except for trivial
distributions, because the sum of independent random variables is distributed
as the convolution of their distributions. Alternatively, we could require
that the distributions $u_{1}(s),u_{2}(s)$ are symmetric mirror images around
the origin, in the sense that for all Borel sets $B$,
$u_{1}(s)(B)=u_{2}(s)(-B)$. For distributions with densities $f_{1},f_{2}$,
this would mean $f_{1}(x)=f_{2}(-x)$ for (almost) all $x$. While this
requirement seems to make sense, this symmetry is not necessarily reflected by
the stochastic orders: There is no requirement for stochastic orders to
satisfy $P_{1}(\,\cdot\,)\preccurlyeq P_{2}(\,\cdot\,)\Leftrightarrow
P_{1}(-\,\cdot\,)\succcurlyeq P_{2}(-\,\cdot\,)$. So if we chose this
definition, there could be zero-sum games without the antagonism property,
where a certain strategy profile is preferred to another profile by both
players. For the same reason, we cannot base our definition on requiring the
expected values $E(u_{1}(s)),E(u_{2}(s))$ to sum to zero: It is possible that
$E(u_{1}(s))+E(u_{2}(s))=E(u_{1}(t))+E(u_{2}(t))=0$, yet
$u_{1}(s)\prec_{1}u_{1}(t)$ and $u_{2}(s)\prec_{2}u_{2}(t)$. Since no
alternative definition seems meaningful, we stick to the zero-sum definition
made in Definition 4.4.

In the classical real-valued model discussed in Chapter 3, mixed strategies
are rated by their expected payoff. It is worth noting that this classical
model emerges as a special case of the distribution-valued model if we choose
the right stochastic orderings.

######  Example 4.13.

Let $\delta_{x}:A\mapsto\mathds{1}_{A}(x)$ denote the Dirac probability
measure. For a given finite real-valued game $G^{(\mathbb{R})}$ with payoffs
$u_{k}^{(\mathbb{R})}$, define its distribution-valued finite counterpart
$G^{(\mathcal{D})}$ to have payoffs

$\displaystyle\forall k\in[n]:\leavevmode\nobreak\
u_{k}^{(\mathcal{D})}(s)\coloneqq\delta_{u_{k}^{(\mathbb{R})}(s)}.$

Then the real-valued mixed extension $\hat{G}^{(\mathbb{R})}$ is isomorphic to
the distribution-valued mixed extension $\hat{G}^{(\mathcal{D})}$ with respect
to $\preccurlyeq_{E}$ (see Example 4.11).

Games constructed like $\hat{G}^{(\mathcal{D})}$ in the previous example might
be interesting in their own right, with respect to other stochastic orders
than $\preccurlyeq_{E}$: The model allows to talk about the “payoff
distribution” of the real-valued game $G$, and rate outcomes by other orders
than the expected value. In decision-theoretic terms, this allows to model
risk-averse and risk-seeking attitudes, as opposed to the risk-neutral
attitude of expected value. We will however not further pursue this line of
thought, as our main interest lies in mixed extensions of games where the
pure-strategy payoffs already are non-trivial distributions.

###  9 The Stochastic Tail Order

We have laid out the foundations of distribution-valued games in the last
section, but the usefulness of the model mostly depends on choosing the right
stochastic orders. The stochastic orders we have seen so far are not
satisfying in many cases: The expected value ordering $\preccurlyeq_{E}$
basically leads us back to the theory of real-valued games by taking expected
values. The usual stochastic order $\preccurlyeq_{\text{st}}$ takes more
information from the distributions into account, but fails to compare many
distributions since a decision is only made for distributions where one
distribution function dominates the other in a strong way. In an attempt to
extend the idea of the usual stochastic order $\preccurlyeq_{\text{st}}$,
Stefan Rass in a series of papers ([Ras15, Ras15a, RKS16]) defined an ordering
which we call the _stochastic tail order_ and denote by
$\preccurlyeq_{\text{tail}}$ 666The papers by Rass do not give a name to the
ordering. We use the name _tail order_ because it compares distributions by
their tails, which will become clear soon.. It was introduced in the context
of risk assessment for critical infrastructure, where risks with higher impact
are to be avoided at all costs, even if very unlikely. Therefore it is usually
not applied to compare _payoff distributions_ , but rather to compare _loss_
(or _cost_) _distributions_. This detail does not affect our presentation of
the theory, however, as we can simply consider or distribution-valued games to
be ordered with respect $\succcurlyeq_{\text{tail}}$ instead of
$\preccurlyeq_{\text{tail}}$ if the “payoffs” are supposed to represent
losses. The tail order is defined based on moment sequences, but we will later
show that in many cases, it can be understood as a kind of lexicographic
ordering: The original goal for its introduction was to have an ordering that
applies the criterion of $\preccurlyeq_{\text{st}}$, but only from some point
$x_{0}$ on, so that more distributions are actually comparable (see [RKS16]).
This works to some extent, however in this section we will also see that some
properties of the ordering claimed in [RKS16] can fail in pathological cases.

####  9.1 Definition and Basic Properties

Recall that $m_{k}(P)\coloneqq\int_{R}x^{k}\,dP$ denotes the $k$-th moment of
$P\in\mathcal{D}$ if $\int_{R}\left|x\right|^{k}\,dP<\infty$, and $M$ denotes
the set of probability measures from $\mathcal{D}$ that have moments of all
orders.

######  Definition 4.14 (Stochastic Tail Order, cf. [RKS16, Definition 2]).

The _stochastic tail order_ $\preccurlyeq_{\text{tail}}$ is defined for
$P_{1},P_{2}\in\mathcal{D}$ by the following condition:

$P_{1}\preccurlyeq_{\text{tail}}P_{2}\mathrel{\vcentcolon\Leftrightarrow}\\\
(P_{1}=P_{2})\vee\bigl{(}(P_{1},P_{2}\in M)\wedge(m_{k}(P_{1})\leq
m_{k}(P_{2})\text{ for all but finitely many $k\in\mathbb{N}_{0}$})\bigr{)}.$

The definition differs slightly from [RKS16, Definition 2] in that we do not
model payoffs by random variables, but instead by probability measures, and we
relax the assumptions on orderings to be comparable: According to the original
definition, only distributions in $\mathcal{D}_{\geq 1}$ with bounded support
that are either discrete, or absolutely continuous with continuous density
function, should be comparable. To keep our discussion as general as possible,
we avoid these rather strict assumptions and only demand that comparable
distributions must have moments of all orders. However it must be noted, and
will become clear in the theorems of this section, that
$\preccurlyeq_{\text{tail}}$ in its original intention to generalize
$\preccurlyeq_{\text{st}}$ only makes sense for elements of $\mathcal{D}_{\geq
1}\cap M$.

######  Lemma 4.15.

The tail order $\preccurlyeq_{\text{tail}}$ is a stochastic order, i.e. a
preorder on $\mathcal{D}$.

###### Proof.

The tail order is reflexive since for any $P_{1}\in\mathcal{D}$,
$P_{1}\preccurlyeq_{\text{tail}}P_{1}$ by definition. It is also transitive:
If $P_{1},P_{2},P_{3}\in\mathcal{D}$ and
$P_{1}\preccurlyeq_{\text{tail}}P_{2},P_{2}\preccurlyeq_{\text{tail}}P_{3}$,
then $P_{1},P_{2},P_{3}\in M$. Therefore $m_{k}(P_{1})\leq m_{k}(P_{2})$ for
all $k\geq K_{1}$ and $m_{k}(P_{2})\leq m_{k}(P_{3})$ for all $k\geq K_{2}$,
and $m_{k}(P_{1})\leq m_{k}(P_{3})$ for all $k\geq\max(K_{1},K_{2})$, so
$P_{1}\preccurlyeq_{\text{tail}}P_{3}$. ∎

The next question is whether $\preccurlyeq_{\text{tail}}$ is antisymmetric
and/or total. In the general context, it has neither of the properties: The
order is trivially not total on $\mathcal{D}$ as it can only compare
distributions from $M$. From Definition 4.14 it is clear that two
distributions from $M$ are incomparable iff their moment sequences alternate.
Moment sequences of two distributions from $M$ can alternate because
distributions can take negative values – as an example, consider the Dirac
distributions $\delta_{-1}$ and $\delta_{0}$: The moment sequence of the
former is given by $(-1)^{n}$, alternating around the sequence of the latter
which is constantly $0$, making the distributions not
$\preccurlyeq_{\text{tail}}$-comparable.

Antisymmetry does not hold on all of $M$ neither: There exist examples of
different distributions in $M$ which have equal moment sequences (an example
is given in [RS86, Example 3.15]). On the other hand, if a probability measure
$P_{1}\in\mathcal{D}$ has bounded support, then no other probability measure
from $\mathcal{D}$ has the same moment sequence (cf. [Sch17, Corollary 4.2]).
This even holds with the weaker condition that the moment-generating function
of the probability measure exists in a neighborhood of 0 (cf. [Lemma
2.3]bib:rassGameRiskManagI[p.414]bib:billingsleyProbabilityAndMeasure) 777The
moment-generating function of a probability measure $P\in\mathcal{D}$ is given
by $M(s)\coloneqq\int_{\mathbb{R}}e^{sx}\,dP(x)$ for $s\in\mathbb{R}$ if the
integral is finite, cf. [Bil12, (21.21)]. However, these results do not
guarantee the antisymmetry of $\preccurlyeq_{\text{tail}}$ on the respective
subset of $\mathcal{D}$, as $\preccurlyeq_{\text{tail}}$ could be indifferent
between two distributions with different moment sequences if they disagree
only finitely often. It is not clear if such a case can actually occur, so
whether or not $\preccurlyeq_{\text{tail}}$ is antisymmetric between
distributions with bounded support, or another sufficiently large subset of
$\mathcal{D}$, remains open.

In a similar way, we can try to identify a sufficiently large class of
distributions on which $\preccurlyeq_{\text{tail}}$ is total. We will discuss
this question in more detail later in Section 9.3.

####  9.2 Sufficient Conditions for Tail Order Preference

Before we do so, let us first get a better understanding of what the tail
order means apart from moment sequences. In [Ras15], the discussion is
restricted to random variables taking values in $[1,\infty)$, since the
behavior of moment sequences differs greatly for values between $[0,1)$, or
even negative values. Additionally, the support is assumed to be bounded.
Also, the discussion focuses only on discrete distributions with finite
support, or absolutely continuous distributions with additional
continuity/differentiability constraints on the densities. We will not need
such strict assumptions everywhere, and will always mention the exact
requirements.

An important intuition for understanding the tail order is that it behaves
essentially like a lexicographic ordering on the density functions in many
cases: Specifically, if the density function of one distribution overtakes the
density function of another at some point, and dominates from there on, then
the first distribution is greater with respect to
$\preccurlyeq_{\text{tail}}$. That vague intuition will be formalized in the
following theorems in the form of sufficient conditions, and an equivalence in
the case of finite support.

######  Theorem 4.16.

Let $P_{1},P_{2}\in\mathcal{D}_{\geq 1}\cap M$. Assume there is some
$x_{0}\geq 1$ such that

$\displaystyle\forall B\in\mathcal{B},$ $\displaystyle\leavevmode\nobreak\
B\subseteq[x_{0},\infty):P_{1}(B)\leq P_{2}(B),$ (12)
$\displaystyle\leavevmode\nobreak\
P_{1}([x_{0},\infty))<P_{2}([x_{0},\infty)).$ (13)

Then $P_{1}\prec_{\text{tail}}P_{2}$.

###### Proof.

To show that $m_{k}(P_{1})<m_{k}(P_{2})$ for all $k$ large enough, we show
that $m_{k}(P_{2})-m_{k}(P_{1})>0$ for all $k$ large enough. The proof will
proceed as follows: $m_{k}(P_{2})-m_{k}(P_{1})$ corresponds to an integral
expression, and we decompose the integration domain $[1,\infty)$ into
intervals $[1,x_{1}]$, $(x_{1},x_{0})$, and $[x_{0},\infty)$. We then show
that the integral over $[x_{0},\infty)$ grows at least proportionally to
$-x_{0}^{k}$ and the integral over $[1,x_{1}]$ shrinks at most proportionally
to $-x_{1}^{k}$. We pick $x_{1}$ close enough to $x_{0}$ such that the
integral over $(x_{1},x_{0})$, which is estimated to shrink at most
proportionally to $x_{0}^{k}$, does not cancel out the one over
$[x_{0},\infty)$. Since $x_{1}<x_{0}$, the positive growth of $x_{0}^{k}$
dominates the negative growth of $x_{1}^{k}$ eventually, showing that
$m_{k}(P_{2})-m_{k}(P_{1})>0$ for large enough $k$.

We start by calculating the difference of moments as follows:

$\displaystyle m_{k}(P_{2})-m_{k}(P_{1})$
$\displaystyle=\int_{\mathbb{R}}x^{k}\,dP_{2}(x)-\int_{\mathbb{R}}x^{k}\,dP_{1}(x)$
$\displaystyle=\biggl{(}\int_{[1,x_{0})}x^{k}\,dP_{2}(x)-\int_{[1,x_{0})}x^{k}\,dP_{1}(x)\biggr{)}+\int_{[x_{0},\infty)}x^{k}\,d\underset{\eqqcolon\mu}{\underbrace{(P_{2}-P_{1})}}(x).$

We define
$\mu\coloneqq{\left.\kern-1.2pt(P_{2}-P_{1})\vphantom{\big{|}}\right|_{\mathcal{B}\cap[x_{0},\infty)}}$
as the difference ($P_{2}-P_{1})$ restricted to the Borel sub-$\sigma$-algebra
on $[x_{0},\infty)$. By (12), $\mu$ is non-negative and therefore a measure,
and by (13), it is not the zero measure. We can now estimate

$\displaystyle\int_{[x_{0},\infty)}x^{k}\,d\mu(x)\geq\int_{[x_{0},\infty)}x_{0}^{k}\,d\mu(x)=x_{0}^{k}\cdot\mu([x_{0},\infty)).$

Next we want to pick $x_{1}<x_{0}$ close enough to $x_{0}$ such that
$P_{1}((x_{1},x_{0}))<\mu([x_{0},\infty))$. We can represent the interval
$[1,x_{0})$ as $[1,x_{0})=\bigcup_{n\in\mathbb{N}}[1,x_{0}-\frac{1}{n}]$. By
continuity from below of the probability measure $P_{1}$, we get
$\lim\limits_{n\to\infty}P_{1}([1,x_{0}-\frac{1}{n}])=P_{1}([1,x_{0}))$.
Therefore we find an $x_{1}<x_{0}$ such that
$P_{1}([1,x_{1}])>P_{1}([1,x_{0}))-\mu([x_{0},\infty))$, i.e.
$P_{1}((x_{1},x_{0}))<\mu([x_{0},\infty))$. With this we estimate

$\displaystyle\int_{[1,x_{0})}x^{k}\,dP_{2}(x)-\int_{[1,x_{0})}x^{k}\,dP_{1}(x)\geq-\int_{[1,x_{0})}x^{k}\,dP_{1}(x)$
$\displaystyle=-$
$\displaystyle\int_{[1,x_{1}]}x^{k}\,dP_{1}(x)-\int_{(x_{1},x_{0})}x^{k}\,dP_{1}(x)\geq-\int_{[1,x_{1}]}x_{1}^{k}\,dP_{1}(x)-\int_{(x_{1},x_{0})}x_{0}^{k}\,dP_{1}(x)$
$\displaystyle=-$ $\displaystyle x_{1}^{k}\cdot
P_{1}([1,x_{1}])-x_{0}^{k}\cdot P_{1}((x_{1},x_{0})).$

In summary, we get

$m_{k}(P_{2})-m_{k}(P_{1})\geq
x_{0}^{k}\cdot\mu([x_{0},\infty))-x_{0}^{k}\cdot
P_{1}((x_{1},x_{0}))-x_{1}^{k}\cdot P_{1}([1,x_{1}])\\\
=x_{0}^{k}\bigl{(}\underset{>0}{\underbrace{\mu([x_{0},\infty))-P_{1}((x_{1},x_{0}))}}\bigr{)}-x_{1}^{k}\cdot
P_{1}([1,x_{1}]),$

which is greater than zero for all $k$ large enough, because $x_{1}<x_{0}$. ∎

Special cases of this theorem hold for absolutely continuous and discrete
distributions. Recall for the next proof that we write $\lambda$ for the
Lebesgue measure.

######  Theorem 4.17.

Let $P_{1},P_{2}\in\mathcal{D}_{\geq 1}\cap M$ be absolutely continuous, with
densities $f,g$.

  1. 1.

If there is some $x_{0}\geq 1$ such that on the interval $[x_{0},\infty)$ we
have $f\leq g$ almost everywhere, yet not $f=g$ almost everywhere, then
$P_{1}\prec_{\text{tail}}P_{2}$.

  2. 2.

If there are $x_{0}\geq 1,\delta>0$ such that $f\leq g$ on $[x_{0},\infty)$
and $f<g$ on $[x_{0},x_{0}+\delta]$, then $P_{1}\prec_{\text{tail}}P_{2}$.

###### Proof.

1: Our assumptions imply that $\lambda(\\{f>g\\}\cap[x_{0},\infty))=0$ and
${\lambda(\\{f<g\\}\cap[x_{0},\infty))}>0$. Let
$B\in\mathcal{B},B\subseteq[x_{0},\infty)$. Then $f\leq g$ almost everywhere
on $B$. So $P_{1}(B)=\int_{B}f\,d\lambda\leq\int_{B}g\,d\lambda=P_{2}(B)$. On
the other hand,

$\displaystyle P_{1}([x_{0},\infty))$
$\displaystyle=\int_{[x_{0},\infty)\cap\\{f<g\\}}f\,d\lambda+\int_{[x_{0},\infty)\cap\\{f=g\\}}f\,d\lambda$
$\displaystyle<\int_{[x_{0},\infty)\cap\\{f<g\\}}g\,d\lambda+\int_{[x_{0},\infty)\cap\\{f=g\\}}g\,d\lambda=P_{2}(B).$

So the conditions for Theorem 4.16 are satisfied, and
$P_{1}\prec_{\text{tail}}P_{2}$.

2: This is as a special case of the previous condition. We have that
$\lambda(\\{f>g\\}\cap[x_{0},\infty))=\lambda(\emptyset)=0$, and
$\lambda(\\{f<g\\}\cap[x_{0},\infty))>\lambda([x_{0},x_{0}+\delta])>0$, so the
conditions of the first part are satisfied and
$P_{1}\prec_{\text{tail}}P_{2}$. ∎

######  Theorem 4.18.

Let $P_{1},P_{2}\in\mathcal{D}_{\geq 1}\cap M$ be discrete, with probability
mass functions $f,g$.

  1. 1.

If there is some $x_{0}\geq 1$ such that $f(x_{0})<g(x_{0})$, and $\forall
x>x_{0}:f(x)\leq g(x)$, then $P_{1}\prec_{\text{tail}}P_{2}$.

  2. 2.

If $P_{1},P_{2}$ both have finite support, an equivalence holds:

$\displaystyle P_{1}\prec_{\text{tail}}P_{2}\Leftrightarrow\exists x_{0}\geq
1:f(x_{0})<g(x_{0})\wedge\forall x>x_{0}:f(x_{0})\leq g(x_{0}).$ (14)

###### Proof.

1: We can view discrete distributions as absolutely continuous with respect to
the counting measure $\\#$, and e.g. write $P_{1}(B)=\int_{B}f\,d\\#$. Let
$B\in\mathcal{B},B\subseteq[x_{0},\infty)$. Then analogously to the previous
proof, we get $P_{1}(B)=\int_{B}f\,d\\#\leq\int_{B}g\,d\\#=P_{2}(B)$. Also,
$P_{1}([x_{0},\infty))=f(x_{0})+P_{1}((x_{0},\infty))\leq
f(x_{0})+P_{2}((x_{0},\infty))<g(x_{0})+P_{2}((x_{0},\infty))=P_{2}([x_{0},\infty))$.
This shows that the conditions of Theorem 4.16 hold, and
$P_{1}\prec_{\text{tail}}P_{2}$.

2: We show that in the finite case the condition is not only sufficient, but
also necessary. Suppose $P_{1}\prec_{\text{tail}}P_{2}$, let
$v_{1}<\dots<v_{m}$ denote the values in the common support. Let $n$ be the
maximal index such that $f(v_{n})\neq g(v_{n})$: Such an $n$ must exist; else,
$f(v_{i})=g(v_{i})$ for all $i$ would imply $P_{1}=P_{2}$ in contradiction to
our assumption. Since by the above sufficient condition, $f(v_{n})>g(v_{n})$
would imply $P_{1}\succ_{\text{tail}}P_{2}$, we must have $f(v_{n})<g(v_{n})$.
So $x_{0}\coloneqq v_{n}$ fulfills the desired property. ∎

In the special case of finite supports, a comparison by
$\preccurlyeq_{\text{tail}}$ is equivalent to comparing the probability masses
of the support points lexicographically from the right. The next definition
defines such a lexicographic ordering $\leq_{\textsc{Rlex}}$ on vectors, and
the subsequent corollary shows how comparisons by $\preccurlyeq_{\text{tail}}$
and $\leq_{\textsc{Rlex}}$ are equivalent.

######  Definition 4.19.

Let $\leq_{\textsc{Rlex}}$ denote the _reflected lexicographic order_ on
$\mathbb{R}^{m}$:

$\displaystyle(x_{1},\dots,x_{m})\leq_{\textsc{Rlex}}(y_{1},\dots,y_{m})\mathrel{\vcentcolon\Leftrightarrow}x=y\vee(\exists
k\in[m]:x_{k}<y_{k}\wedge x_{i}=y_{i}\leavevmode\nobreak\ \forall i>k).$

$\leq_{\textsc{Rlex}}$ is similar to the usual lexicographic order, but starts
comparing from the right instead of from the left 888There seems to be no
consistent name for this ordering in the literature; The term _reflected
lexicographic order_ is used by [Oei12].. Just as the lexicographic order, it
is antisymmetric and total.

######  Corollary 4.20.

Let $P_{1},P_{2}\in\mathcal{D}_{\geq 1}$ be discrete distributions with
probability mass functions $f,g$ and finite common support
$(\operatorname{supp}P_{1}\cup\operatorname{supp}P_{2})=\\{v_{1},\dots,v_{m}\\}$,
$v_{1}<\dots<v_{m}$. Then

$\displaystyle P_{1}\preccurlyeq_{\text{tail}}P_{2}\Leftrightarrow
v^{f}\coloneqq(f(v_{1}),\dots,f(v_{m}))\leq_{\textsc{Rlex}}(g(v_{1}),\dots,g(v_{m}))\eqqcolon
v^{g}.$ (15)

###### Proof.

From Theorem 4.18, 2, it follows directly that
$P_{1}\prec_{\text{tail}}P_{2}\Leftrightarrow(\exists
k\in[m]:f(v_{k})<g(v_{k})\wedge f(v_{i})=g(v_{i})\leavevmode\nobreak\ \forall
i>k)$. Since $\leq_{\textsc{Rlex}}$ is antisymmetric, by the definition of
$\leq_{\textsc{Rlex}}$ this is equivalent to $v^{f}<_{\textsc{Rlex}}v^{g}$. If
instead $P_{1}\preccurlyeq_{\text{tail}}P_{2}$, but not
$P_{1}\prec_{\text{tail}}P_{2}$, this is equivalent to $P_{1}=P_{2}$: This is
because if $P_{1}\neq P_{2}$, the sufficient condition of Theorem 4.18 implies
either $P_{1}\prec_{\text{tail}}P_{2}$ or $P_{1}\succ_{\text{tail}}P_{2}$.
$P_{1}=P_{2}$ then is equivalent to $v^{f}=v^{g}$, so in summary,
$P_{1}\preccurlyeq_{\text{tail}}P_{2}\Leftrightarrow
v^{f}\leq_{\textsc{Rlex}}v^{g}$. ∎

In particular, this characterization shows that $\preccurlyeq_{\text{tail}}$
is antisymmetric and total on the set of distributions with finite support.

#####  9.2.1 Counterexamples to Equivalences in the Sufficient Conditions for
the Tail Order

While finite support allows us to turn the sufficient condition for the tail
order into an equivalent condition, this does not work in the general case of
distributions in $\mathcal{D}_{\geq 1}\cap M$. To show that none of the
sufficient conditions from Theorems 4.17 and 4.18, 1 can be turned into
equivalences, we construct several counterexamples. The original motivation of
these counterexamples was to disprove a statement made in [Ras15] (and
reproduced in [RKS16]): An old version of [Ras15] contained a condition
similar to Theorem 4.17, and claimed that it was equivalent, not only
sufficient, for a $\preccurlyeq_{\text{tail}}$-relationship between two
distributions. The proof wrongly assumed that of two density functions, one
always dominates the other from some point on until the end of the support. An
updated version was meanwhile uploaded to arXiv that clarifies this issue.
Since the paper only concerns discrete and absolutely continuous distributions
with bounded support, and in the absolutely continuous case with continuous
density functions, we construct counterexamples with these properties: Define

$\displaystyle\tilde{\mathcal{D}}\coloneqq\\{P\in\mathcal{D}:\text{$\exists
b:P\in\mathcal{D}_{[1,b]}$, $P$ discrete or AC with continuous density
function}\\}.$

When we introduced the tail order, we motivated it as a replacement for the
usual stochastic order $\preccurlyeq_{\text{st}}$ that works on a wider range
of distributions. However, the reader might have noticed that the definition
of $\preccurlyeq_{\text{st}}$ used distribution function dominance (see
Example 4.11), yet all our sufficient conditions use dominance of the mass or
density functions. It is not clear whether a sufficient condition in the form
of

$\displaystyle F_{1}(x)\geq F_{2}(x)\leavevmode\nobreak\ \forall x\geq
x_{0},\lambda({F_{1}>F_{2}}\cap[x_{0},\infty))>0\implies
P_{1}\prec_{\text{tail}}P_{2}$

holds, either on all of $(\mathcal{D}_{\geq 1}\cap M)$ or on the subset of
distributions with bounded support. We will not further investigate this
issue, but it might be an interesting question for follow-up work. However, we
will also show with our counterexamples that even if such a condition was
sufficient, it could not be turned into an equivalence. [Ras15, Theorem 2.15]
shows that the reverse direction holds on $\tilde{\mathcal{D}}$ under the
assumption that one density eventually dominates, but we show that it does not
hold in general.

The specific statements we disprove in our counterexamples are as follows,
where we assume that $P_{1},P_{2}\in\tilde{\mathcal{D}}$, $P_{1}\neq P_{2}$
and $P_{1},P_{2}$ have probability mass functions or probability density
functions $f,g$, and distribution functions $F,G$, respectively.

  1. (1a)

“If $P_{1},P_{2}$ are discrete, then there exists an $x_{0}$ such that either
$\forall x\geq x_{0}:f(x)\geq g(x)$, or $\forall x\geq x_{0}:f(x)\leq g(x)$.”

  2. (1b)

“If $P_{1},P_{2}$ are discrete, then there exists an $x_{0}$ such that either
$\forall x\geq x_{0}:F(x)\leq G(x)$, or $\forall x\geq x_{0}:F(x)\geq G(x)$.”

  3. (2a)

“If $P_{1},P_{2}$ are discrete and $P_{1}\prec_{\text{tail}}P_{2}$, then
$\exists x_{0}:\forall x\geq x_{0}:f(x)\leq g(x)$.”

  4. (2b)

“If $P_{1},P_{2}$ are discrete and $P_{1}\prec_{\text{tail}}P_{2}$, then
$\exists x_{0}:\forall x\geq x_{0}:F(x)\geq G(x)$.”

  5. (3a)

“If $P_{1},P_{2}$ are AC and $P_{1}\prec_{\text{tail}}P_{2}$, then $\exists
x_{0}:\forall x\geq x_{0}:f(x)\leq g(x)$.”

  6. (3b)

“If $P_{1},P_{2}$ are AC and $P_{1}\prec_{\text{tail}}P_{2}$, then $\exists
x_{0}:\forall x\geq x_{0}:F(x)\geq G(x)$.”

The first counterexample disproves the statements (1a) and (1b), the second
one disproves the statements (2a) and (2b), and the third one disproves the
statements (3a) and (3b).

######  Example 4.21.

An infinite family of discrete distributions with pairwise alternating mass
and distribution functions and bounded support.

This first example disproves claims (1a) and (1b). It is not strictly
necessary since the next counter example is more general and even disproves
the weaker claims (2a) and (2b). In this example, on the other hand, the mass
and density functions of two distributions are shown to alternate, but it
could not be shown that one moment sequence dominates the other. The example
is included nonetheless because it involves an interesting graphical proof of
the fact that the distribution functions alternate, and the distributions
involved are less artificial than in the other examples. 999In particular,
$P_{c}$ from the example can be obtained as follows: If $X\sim\text{Geom}(p)$
is a random variable that is geometrically distributed on $\mathbb{N}$, then
$2-(1-p)^{X}\sim P_{1/(1-p)}$.

For $c>1$, let $P_{c}$ be defined by
$P_{c}\biggl{(}\biggl{\\{}2-\bigl{(}\frac{1}{c}\bigr{)}^{k}\biggr{\\}}\biggr{)}=(c-1)\bigl{(}\frac{1}{c}\bigr{)}^{k}$
for all $k\in\mathbb{N}$, and zero everywhere else. These probability masses
are constructed to sum to $1$ by the geometric series. We let
$a_{k}\coloneqq\bigl{(}\frac{1}{c}\bigr{)}^{k}$, and will later use that
$\sum_{j=1}^{k}a_{j}=\frac{1-\left(\frac{1}{c}\right)^{k}}{c-1}=\frac{1-a_{k}}{c-1}$.
The distribution function $F_{c}$ of $P_{c}$ can be written as a sum of
indicator functions as

In particular, on the interval (1, 2), $F_{c}$ is bounded from above by the
line $x\mapsto x-1$, touching it exactly at its discontinuity points, i.e.
$F_{c}(2-a_{k})=1-a_{k}$. This lets us prove graphically that distribution
functions of such distributions can alternate: If we choose $c,d$ such that
the sets $\\{2-\frac{1}{c^{k}}\mid k\in\mathbb{N}\\},\\{2-\frac{1}{d^{k}}\mid
k\in\mathbb{N}\\}$ are disjoint, then $F_{c},F_{d}$ alternate as seen in 3(a).
This is because at every discontinuity, one distribution function overtakes
the other since it jumps to the diagonal while the other function is strictly
smaller. In particular, $\\{P_{p}\mid p\text{ prime}\\}$ is an infinite family
of distributions with pairwise alternating distribution functions. It is clear
that the corresponding mass functions $f,g$ alternate as well, because every
discontinuity of $F$ or $G$ corresponds to a non-zero probability mass in one
distribution, while the other distribution assigns zero mass to that point.

The $n$-th moment of $P_{c}$ can be expressed as a sum with finitely many
terms:

$\displaystyle m_{n}(P_{c})$ $\displaystyle=\sum_{k\geq
1}(c-1)\frac{1}{c^{k}}(2-\frac{1}{c^{k}})^{n}=\sum_{k\geq
1}(c-1)\frac{(2c^{k}-1)^{n}}{c^{kn+k}}$
$\displaystyle=(c-1)\sum_{j=0}^{n}\binom{n}{j}2^{n-j}(-1)^{j}\biggl{(}\sum_{k\geq
1}\frac{c^{-jk}}{c^{k}}\biggr{)}=(c-1)\sum_{j=0}^{n}\binom{n}{j}2^{n-j}(-1)^{j}\frac{1}{c^{j+1}-1}.$

To also disprove the claims (2a) and (2b) with this example, we would have to
show $P_{c}\prec_{\text{tail}}P_{d}$ for all $1<c<d$. While computer
calculations suggest that $m_{n}(P_{c})$ increases monotonically with $c$, it
seems hard to show this rigorously. We therefore leave the question open
whether the construction from this example can also be used to disprove the
statements (2a) and (2b). ∎

(a) Geometric series construction 4.21: Distribution functions $F_{c}$,
$c=2,3$.

(b) General discrete construction 4.22: Distribution functions
($s_{k}=1-\frac{1}{k+1},f(s_{k})=\frac{1}{2^{k}}$).

(c) Absolutely continuous construction: Densities (4.23)/corresponding mass
functions (4.22, scaled by a factor of 30 to be visible).

(d) Distribution functions of absolutely continuous construction 4.23.

Figure 3: Plots for the counterexamples 4.21 \- 4.23

######  Example 4.22.

A $\preccurlyeq_{\text{tail}}$-ascending sequence of discrete distributions
with alternating mass and distribution functions for consecutive elements and
bounded support.

In this more general counterexample, we start with a discrete distribution $P$
whose support can be written as $\operatorname{supp}P=\\{s_{i}\mid
i\in\mathbb{N}\\}\subseteq[a,b)$, $1<a<b$, with the $s_{i}$ in increasing
order, and whose probability mass function $f$ is strictly decreasing on the
support, i.e. $\forall i<j:f(s_{i})>f(s_{j})$. We construct $\tilde{P}$ with
mass function $g$, where each support point is shifted slightly to the right,
with its probability adjusted to be only a little smaller, giving the
remaining probability mass to the point $t_{0}\coloneqq\frac{1+a}{2}$. First,
set $t_{i}\coloneqq\frac{s_{i}+s_{i+1}}{2},i\in\mathbb{N}$. We adjust the
probability of $t_{i}$ by a factor $c_{i}<1$, i.e. $g(t_{i})=c_{i}f(s_{i})$,
chosen such that the following properties are satisfied:

  1. 1.

$c_{i}\geq\frac{s_{i}}{t_{i}}$,

  2. 2.

$c_{i}\geq 1-\frac{1}{2^{i}}$,

  3. 3.

$c_{i}\geq\frac{f(s_{i+1})}{f(s_{i})}$.

As we will show shortly, the first property ensures that $\tilde{P}$ has
greater moments than $P$, the second property ensures that the distribution
functions alternate, and the third property ensures that $g$ is monotonic on
its support as well (so the process can again be applied to $\tilde{P}$). In
summary, we define $g$ as follows:

$\displaystyle g(t_{i})=c_{i}f(s_{i}),\quad
c_{i}\coloneqq\max\biggl{\\{}\frac{s_{i}}{t_{i}},1-\frac{1}{2^{i}},\frac{f(s_{i+1})}{f(s_{i})}\biggr{\\}}<1,\quad
g(t_{0})=\sum_{i\geq 1}(1-c_{i})f(s_{i}).$

Obviously the mass functions $f,g$ alternate, as $f(s_{i})>0,g(s_{i})=0$ and
$g(t_{i})>0,f(t_{i})=0$ for all $i\in\mathbb{N}$. We now show that the moments
of $\tilde{P}$ dominate the moments of $P$, and the distribution functions
alternate. The first property of the $c_{i}$ implies that $\forall
i\in\mathbb{N}:g(t_{i})t_{i}\geq f(s_{i})s_{i}$, so for the moments we have:

$m_{n}(\tilde{P})-m_{n}(P)=g(t_{0})t_{0}^{n}+\sum_{i\geq
1}g(t_{i})t_{i}^{n}-f(s_{i})s_{i}^{n}\geq g(t_{0})t_{0}^{n}+\sum_{i\geq
1}g(t_{i})t_{i}s_{i}^{n-1}-f(s_{i})s_{i}^{n}\\\ =g(t_{0})t_{0}^{n}+\sum_{i\geq
1}s_{i}^{n-1}\underset{\geq 0}{\underbrace{(g(t_{i})t_{i}-f(s_{i})s_{i})}}\geq
g(t_{0})t_{0}^{n}>0.$

Secondly, the distribution functions alternate, see 3(b): On the one hand for
$k\in\mathbb{N}$,

$G(t_{k})=g(t_{0})+\sum_{i=1}^{k}c_{i}f(s_{i})=g(t_{0})-\biggl{(}\sum_{i=1}^{k}(1-c_{i})f(s_{i})\biggr{)}+F(s_{k})\\\
=\biggl{(}\sum_{i\geq
k+1}(1-c_{i})f(s_{i})\biggr{)}+F(s_{k})>F(s_{k})=F(t_{k}).$

On the other hand,

$G(s_{k})=g(t_{0})+\sum_{i=1}^{k-1}c_{i}f(s_{i})=g(t_{0})+\sum_{i=1}^{k-1}f(s_{i})-\sum_{i=1}^{k-1}(1-c_{i})f(s_{i})\\\
=F(s_{k})-f(s_{k})+g(t_{0})-\sum_{i=1}^{k-1}(1-c_{i})f(s_{i})=F(s_{k})-f(s_{k})+\sum_{i\geq
k}(1-c_{i})f(s_{i}).$

Using the second property of $c_{i}$, the strict monotonicity of $f$ on its
support, and the geometric sum identity $\sum_{i\geq
k}\frac{1}{2^{i}}=\frac{1}{2^{k-1}}$, we further get:

$\displaystyle\sum_{i\geq k}(1-c_{i})f(s_{i})\leq\sum_{i\geq
k}\frac{1}{2^{i}}f(s_{i})<\sum_{i\geq
k}\frac{1}{2^{i}}f(s_{k})=\frac{1}{2^{k-1}}f(s_{k})\leq f(s_{k}).$

This shows that $G(s_{k})<F(s_{k})$. So in summary we have
$P\prec_{\text{tail}}\tilde{P}$, and their probability mass, as well as
distribution functions alternate. Furthermore, $\tilde{P}$ again satisfies the
conditions we originally made on $P$: By repeating the process, we get a whole
sequence of distributions which is ascending with respect to
$\prec_{\text{tail}}$ and for any two consecutive distributions in it, the
mass and distribution functions alternate (so in particular, the sufficient
condition of Theorem 4.17 is not satisfied). ∎

######  Example 4.23.

Two $\preccurlyeq_{\text{tail}}$-comparable absolutely continuous
distributions with alternating density and distribution functions, continuous
densities and bounded support.

For the absolutely continuous counterexample, we start with two discrete
distributions $P_{1},P_{2}$ where $P_{2}$ is obtained from $P_{1}$ by the
process from Example 4.22: In particular, we require that
$P_{1}\prec_{\text{tail}}P_{2}$,
$\operatorname{supp}(P_{1})=\\{s_{1},s_{2},\dots\\}$,
$\operatorname{supp}(P_{2})=\\{t_{0},t_{1},t_{2},\dots\\}$ with
$1<t_{0}<s_{1}<t_{1}<s_{2}<t_{2}<\dots<b$, and that their distribution
functions $F,G$ alternate with $\forall k\geq
1:F(s_{k})>G(s_{k}),F(t_{k})<G(t_{k})$.

We then shift the probability mass $P_{1}$ gives to each point $s_{k}$ to an
interval to the left of $s_{k}$, and the probability mass $P_{2}$ gives to
each point $t_{k}$ to an interval to the right of $t_{k}$, which preserves the
order of the moments (illustrated in 3(c)). We do it in such a way that the
distribution functions are again alternating, and the new density functions
are continuous (3(d)). We will call the new absolutely continuous
distributions $\tilde{P}_{1},\tilde{P}_{2}$, their density functions
$\tilde{f},\tilde{g}$, and their distribution functions $\tilde{F},\tilde{G}$.

To formalize this, let
$h:\mathbb{R}\to\mathbb{R},x\mapsto(6x-6x^{2})\mathds{1}_{[0,1]}(x)$. The
function $h$ is a probability density function
($\int_{\mathbb{R}}h\,d\lambda=1$) supported on $[0,1]$, which is continuous
since $h(0)=h(1)=0$. Denote by
$h_{[a,b]}:x\mapsto\frac{1}{b-a}h\bigl{(}\frac{x-a}{b-a}\bigr{)}$ the version
of $h$ scaled to the interval $[a,b]$ in a way such that it still integrates
to 1. Also, let $m_{k}=\frac{t_{k-1}+s_{k}}{2}$. Using this notation, we
define $\tilde{f},\tilde{g}$ by:

$\displaystyle\tilde{f}=\sum_{k\geq
1}f(s_{k})h_{[m_{k},s_{k}]},\quad\tilde{g}=\sum_{k\geq
0}g(t_{k})h_{[t_{k},m_{k+1}]}.$ (16)

By construction, it is clear that
$\int_{\mathbb{R}}\tilde{f}\,d\lambda=\int_{\mathbb{R}}\tilde{g}\,d\lambda=1$,
since both of the sequences $(f(s_{k}))_{k\geq 1},g(t_{k}))_{k\geq 0}$ sum to
$1$. The distribution functions alternate: For $k\geq 1$,

$\displaystyle\tilde{F}(s_{k})=\int_{[1,s_{k}]}\tilde{f}\,d\lambda=\sum_{i=1}^{k}f(s_{k})=F(s_{k})>G(s_{k})=\sum_{i=1}^{k-1}g(t_{k})=\tilde{G}(s_{k}),$
$\displaystyle\tilde{G}(m_{k+1})=\int_{[1,m_{k+1}]}\tilde{g}\,d\lambda=\sum_{i=1}^{k}g(t_{k})=G(t_{k})>F(t_{k})=\sum_{i=1}^{k}f(s_{k})=\tilde{F}(m_{k+1}).$

The ordering of the moments is preserved:

$m_{n}(\tilde{P_{1}})=\sum_{k\geq
1}\int_{[m_{k},s_{k}]}x^{n}h_{[m_{k},s_{k}]}(x)\,d\lambda(x)<\sum_{k\geq
1}f(s_{k})\cdot s_{k}^{n}\\\ =m_{n}(P_{1})<m_{n}(P_{2})\\\ =\sum_{k\geq
0}g(t_{k})\cdot t_{k}^{n}<\sum_{k\geq
0}\int_{[t_{k},m_{k+1}]}x^{n}h_{[t_{k},m_{k+1}]}(x)\,d\lambda(x)=m_{n}(\tilde{P_{2}}).$

If the series in (16) converge uniformly, continuity is preserved. For this we
additionally require $\left\lVert
f(s_{k})h_{[m_{k},s_{k}]}\right\rVert_{\infty}=\frac{f(s_{k})}{s_{k}-m_{k}}\xrightarrow{\;k\to\infty\;}0$,
and similarly for $g$, which is the case if the probability masses $f(s_{k})$
approach zero asymptotically faster than the consecutive differences of the
$s_{k}$. For example, we can set
$s_{k}=2-\frac{1}{k+1},f(s_{k})=\frac{1}{2^{k}}$, and use $g,(t_{k})_{k}$
constructed from it as in Example 4.22. ∎

####  9.3 Can the Tail Order Be Made a Total Order?

When we introduced the tail order in Section 9.1, we shortly discussed its
antisymmetry and totality properties: In short, $\preccurlyeq_{\text{tail}}$
is neither total nor antisymmetric on $M$. For antisymmetry, counterexamples
of different distributions with equal moment sequences exist. Different
distributions with equal moment sequences necessarily have unbounded support,
and we do not know whether $\preccurlyeq_{\text{tail}}$ is antisymmetric on
the subset of distributions with bounded support because it is not clear if
the moment sequences of two different such distributions can disagree only
finitely often. We can ask a similar question about the totality of
$\preccurlyeq_{\text{tail}}$: While $\preccurlyeq_{\text{tail}}$ is not total
on all of $M$, a natural question is if there is some useful subset of
$\mathcal{D}$ where $\preccurlyeq_{\text{tail}}$ is total, and we will discuss
this question on the following pages. Corollary 4.20 shows that
$\preccurlyeq_{\text{tail}}$ is total if only distributions with finite
support are considered, yet limiting ourselves to finitely-supported
distributions is quite restrictive. Since our only example of incomparable
distributions so far relied on negative values in the support, one might hope
that $\preccurlyeq_{\text{tail}}$ is total on $\mathcal{D}_{\geq 0}\cap M$.
However, we will show shortly that this is not the case.

In [Ras15, RKS16], the discussion focuses on the particular subset of
distributions that have _bounded support in $[1,\infty)$_ and are either
_discrete with finite support_ , or _absolutely continuous with a continuous
density function_. The lemmas [RKS16, Lemma 2] and [Ras15, Lemma 2.4] wrongly
claim that such distributions are always
$\preccurlyeq_{\text{tail}}$-comparable: A proof is given for the absolutely
continuous case; but as already discussed to motivate the previous
counterexamples, it contains an error, as it implicitly assumes that of two
density functions, one always dominates the other from some point on. This
statement was disproved by the counterexamples 4.21 \- 4.23. Note that the
latter paper was meanwhile updated to correct the error. Since the proof is
erroneous, it is an interesting question whether the totality of
$\preccurlyeq_{\text{tail}}$ on the set of distributions with bounded support
in $[1,\infty)$ can be shown in another way, since it would be desirable for
the application of $\preccurlyeq_{\text{tail}}$ to distribution-valued games
if such a theorem could be proven. Unfortunately, it turns out that
$\preccurlyeq_{\text{tail}}$ is not total on that set, and it is also not
total if only absolutely continuous distributions are considered. It was
conjectured during most the writing process of this thesis that this totality
statement does hold, and the steps taken towards the desired proof are
included on the following pages. However towards the end of the writing
process, a counterexample was constructed by Jeremias Epperlein, and we will
use this example at the end of this subsection to show that
$\preccurlyeq_{\text{tail}}$ is not total on the set of distributions with
bounded support in $[1,\infty)$.

#####  9.3.1 The Moment Problem and its Variants

Since our questions depend on moment sequences by the definition
$\preccurlyeq_{\text{tail}}$, it will be helpful to know about the properties
of such sequences. The question to find out if a given sequence
$(m_{n})_{n\in\mathbb{N}_{0}}$ is a moment sequence for some Borel measure
$\mu$ on $\mathbb{R}$ is known as the _moment problem_ , and there are several
variants studied in the literature: The _Hamburger moment problem_ concerns
measures supported on a subset of $\mathbb{R}$, the _Stieltjes moment problem_
is about measures supported on a subset of $[0,\infty)$, and the _Hausdorff
moment problem_ deals with measures supported on a subset of $[0,1]$. For all
three versions, conditions are known that are both sufficient and necessary
for $(m_{n})_{n\in\mathbb{N}_{0}}$ to be a moment sequence of the respective
kind. The moment problem has been extensively analyzed in the literature, for
example in [ST43], [Akh65], or the more recent [Sch17].

#####  9.3.2 Non-Totality in the Stieltjes Case

The Hamburger moment problem is too general for our case, since negative
values in the support can lead to alternating moment sequences, making the
tail order non-total. However, we can make use of a result relating Stieltjes
and Hamburger moment sequences: A moment sequence is called _Hamburger-_
/_Stieltjes-determinate_ if there is a _unique_ measure of the respective type
with that moment sequence [Sch17, p.68] 101010More specifically, a unique
_Radon measure_ , see [Sch17, A.1] for a definition. This makes no difference
in our case: Every (locally) finite Borel measure on $\mathbb{R}$, and
therefore every probability measure in $\mathcal{D}$, is a Radon measure (e.g.
[Mal95, Proposition II.3.1]). Also, a moment sequence belongs to a probability
measure if and only if $m_{0}=1$.. The result we will use is that Stieltjes-
determinateness in general does not imply Hamburger-determinateness:

######  Theorem 4.24 (See [Lin17, Fact A], citing [Akh65, p.240] and [Chi68]).

There exists a moment sequence that is Stieltjes-determinate, but not
Hamburger-determinate.

######  Corollary 4.25.

There exist probability measures $P_{1},P_{2}\in M$ that have equal moment
sequences and satisfy $P_{1}\in\mathcal{D}_{\geq
0},P_{2}\notin\mathcal{D}_{\geq 0}$.

###### Proof.

Let $(m_{n})_{n\geq 0}$ be a moment sequence which is Stieltjes-determinate,
but not Hamburger-determinate. Let $\mu_{1}$ be the unique measure in
$\mathcal{D}_{\geq 0}$ with that moment sequence. Let $\mu_{2}\neq\mu_{1}$ be
a different measure with that moment sequence, which exists since the sequence
is not Hamburger-determinate. Since $\mu_{1}$ is unique in the Stieltjes
sense, the support of $\mu_{2}$ must overlap with $(-\infty,0)$. If $m_{0}\neq
1$, the measures constructed are not probability measures: We normalize them
and define $P_{1}=\frac{1}{m_{0}}\mu_{1},P_{2}=\frac{1}{m_{0}}\mu_{2}$, which
are probability measures which both have the moment sequence
$(\frac{m_{n}}{m_{0}})_{n\geq 0}$. ∎

This result allows us to show that two Stieltjes moment sequences can
alternate:

######  Example 4.26.

Let $P_{1},P_{2}\in M$ be measures that satisfy $P_{1}\in\mathcal{D}_{\geq
0},P_{2}\notin\mathcal{D}_{\geq 0}$ and have the same moment sequence
$(m_{n})_{n\geq 0}$, as constructed in Corollary 4.25. Define a measure
$\tilde{P}_{2}:A\mapsto
P_{2}\bigl{(}A\cap[0,\infty)\bigr{)}+\mathds{1}_{A}(0)P_{2}\bigl{(}(\infty,0)\bigr{)}$,
which shifts the probability mass $P_{2}$ puts on the negative semi-axis to
the point $0$, and has support in $[0,\infty)$. Then its moment sequence
$(\tilde{m}_{n})_{n\geq 0}$ is given by $\tilde{m}_{0}=1$, and for $n>0$:

$\displaystyle\tilde{m}_{n}=\int_{[0,\infty)}x^{n}\,d\tilde{P}_{2}=\int_{[0,\infty)}x^{n}\,dP_{2}=\int_{\mathbb{R}}x^{n}\,dP_{2}-\int_{(-\infty,0)}x^{n}\,dP_{2}=m_{n}-\int_{(-\infty,0)}x^{n}\,dP_{2}.$

By construction of $P_{2}$, the term $\int_{(-\infty,0)}x^{n}\,dP_{2}$ is
strictly positive for $n$ even, and strictly negative for $n$ odd. Therefore
$(\tilde{m}_{n})_{n\geq 0}$ alternates around $(m_{n})_{n\geq 0}$, and both
sequences are moment sequences of probability measures supported on a subset
of $[0,\infty)$.

This shows that the set $(\mathcal{D}_{\geq 0}\cap M)$ of probability measures
supported on a subset of $[0,\infty)$ that have moments of all orders is still
too large for $\preccurlyeq_{\text{tail}}$ to be total.

#####  9.3.3 Distributions with Non-Negative Bounded Support

Next we look at distributions with support in a bounded interval $[a,b]$,
$0\leq a<b$. This is related to the Hausdorff moment problem where the bounded
interval is $[0,1]$. A sufficient and necessary condition for a sequence to be
a Hausdorff moment sequence is based on repeatedly taking differences of
successive terms.

######  Definition 4.27.

The _difference operator_
$\Delta:\mathbb{R}^{\mathbb{N}_{0}}\to\mathbb{R}^{\mathbb{N}_{0}}$ maps a
sequence of real numbers to the sequence of its successive differences:

$\displaystyle\Delta((s_{n})_{n\in\mathbb{N}_{0}})\coloneqq(s_{n+1}-s_{n})_{n\in\mathbb{N}_{0}},\leavevmode\nobreak\
\text{ also written as }\,(\Delta s)_{n}\coloneqq s_{n+1}-s_{n}.$

######  Theorem 4.28 ([Hau23]).

A sequence $m=(m_{n})_{n\in\mathbb{N}_{0}}$ is a Hausdorff moment sequence,
i.e. is the moment sequence of a measure $\mu$ on with support in $[0,1]$, if
and only if

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

A sequence that satisfies (17) is called _completely monotonic_ [Wid46,
Section III.4].

###### Proof (necessity).

We only show here that condition (17) is necessary, which is the easier part
of the proof. Let $\mu$ be the measure with support in $[0,1]$ which has $m$
as its moment sequence. We first prove by induction over $k$ that
$(\Delta^{k}m)_{n}=\int_{[0,1]}x^{n}(x-1)^{k}\,d\mu(x)$: The statement holds
for $k=0$, since

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

For the induction step, assume the statement holds for $k\in\mathbb{N}$. Then
for $k+1$: