#  Alexandrov meets Lott–Villani–Sturm

Anton Petrunin

###### Abstract

Here I show compatibility of two definition of generalized curvature bounds —
the lower bound for sectional curvature in the sense of Alexandrov and lower
bound for Ricci curvature in the sense of Lott–Villani–Sturm.

## Introduction

Let me denote by $\text{\rm CD}[m,\upkappa]$ the class metric-measure spaces
which satisfy a weak curvature-dimension condition for dimension $m$ and
curvature $\upkappa$ (see preliminaries). By $\text{\rm Alex}^{m}[\upkappa]$,
I will denote the class of all $m$-dimensional Alexandrov spaces with
curvature $\geqslant\upkappa$ equipped with the volume-measure (so $\text{\rm
Alex}^{m}[\upkappa]$ is a class of metric-measure spaces).

Main theorem. $\text{\rm Alex}^{m}[0]\subset\text{\rm CD}[m,0]$.

The question appears first in [Lott–Villani, 7.48]. In [Villani], it is
formulated more generally: $\text{\rm Alex}^{m}[\upkappa]\subset\text{\rm
CD}[m,(m-1)\upkappa]$. The later statement can be proved, along the same
lines, but I do not write it down.

About the proof. The idea of the proof is the same as in Riemannian case (see
[CMS, 6.2] or [Lott–Villani, 7.3]). One only needs to extend certain calculus
to Alexandrov spaces. To do this, I used the same technique as in [Petrunin
03]. I will illustrate the idea on a very simple problem.

Let $M$ be a $2$-dimensional non-negatively curved Riemannian manifold and
$\upgamma_{\uptau}\colon[0,1]\to M$ be a continuous family of unit-speed
geodesics such that

$|\upgamma_{\uptau_{0}}(t_{0})\,\upgamma_{\uptau_{1}}(t_{1})|\geqslant|t_{1}-t_{0}|.$
➊

Set $\ell(t)$ to be the total length of curve
$\upsigma_{t}\colon\uptau\mapsto\upgamma_{\uptau}(t)$. Then $\ell(t)$ is a
concave function — that is easy to prove.

Now, assume you have $A\in\text{\rm Alex}^{2}[0]$ instead of $M$ and a non-
continuous family of unit-speed geodesics $\upgamma_{\uptau}(t)$ which
satisfies ➊ ‣ Introduction. Define $\ell(t)$ as the 1-dimensional Hausdorff
measure of image of $\upsigma_{t}$. In this case $\ell$ is also concave.

Here is an idea how one can proceed; it is not the simplest one but the one
which admits proper generalization. Consider two functions $\uppsi=\mathop{\rm
dist}\nolimits_{\mathop{\rm Im}\nolimits\upsigma_{0}}$ and
$\upvarphi=\mathop{\rm dist}\nolimits_{\mathop{\rm Im}\nolimits\upsigma_{1}}$.
Note that geodesics $\upgamma_{\uptau}(t)$ are also gradient curves of
$\uppsi$ and $\upvarphi$. It implies that $\Delta\upvarphi+\Delta\uppsi$
vanish almost everywhere on the image of the map
$(\uptau,t)\to\upgamma_{\uptau}(t)$ (the Laplasians $\Delta\upvarphi$ and
$\Delta\uppsi$ are Radon sign-measure). Then result follows from the second
variation formula from [Petrunin 98] and calculus on Alexandrov spaces
developed in [Perelman].

Remark. Although $\text{\rm CD}[m,\upkappa]$ is a very natural class of
metric-measure spaces, some basic tools in Ricci comparison can not work there
in principle. For instance, _there are $\text{\rm CD}[m,0]$-spaces which do
not satisfy the Abresch–Gromoll inequality_, (see [AG]). Thus, one has to
modify the definition of the class $\text{\rm CD}[m,\upkappa]$ to make it
suitable for substantial applications in Riemannian geometry.

I'm grateful to A. Lytchak and C. Villani, for their help.

##  1 Preliminaries

Prerequisite. The reader is supposed to be familiar with basic definition and
notion in optimal transport as in [Villani], measure theory in Alexandrov
spaces from [BGP], DC-structure on Alexandrov's spaces from [Perelman] and
technique and notation of gradient flow as in [Petrunin 07].

What needs to be proved. Let me recall the definition of class $\text{\rm
CD}[m,0]$ only — it is sufficient for understanding this paper. The definition
of $\text{\rm CD}[m,\upkappa]$ can be found in [Villani, 29.8].

Similar definitions were given in [Lott–Villani] and [Sturm]. The idea behind
these definitions — convexity of certain functionals in the Wasserstein space
over a Riemannian manifold, appears in [Otto–Villani], [CMS],
[Sturm–v.Renesse]. In the Euclidean context, this notion of convexity goes
back to [McCann]. More on the history of the subject can be found in
[Villani].

For a metric-measure space $X$, I will denote by $|xy|$ the distance between
points $x,y\in X$ and by $\mathop{\rm vol}\nolimits E$ the distinguished
measure of Borel subset $E\subset X$ (I will call it _volume_). Let us denote
by $\mathrm{P}_{\mskip-3.0mu2}X$ the set of all probability measures with
compact support in $X$ equipped with Wasserstein distance of order 2, see
[Villani, 6.1].

Further, we assume $X$ is proper geodesic space; in this case
$\mathrm{P}_{\mskip-3.0mu2}X$ is geodesic.

Let $\upmu$ be a probability measure on $X$. Denote by $\upmu^{r}$ the
absolutely continuous part of $\upmu$ with respect to volume. I.e. $\upmu^{r}$
coincides with $\upmu$ outside a Borel subset of volume zero and there is a
Borel function $\uprho\colon X\to\mathbb{R}$ such that
$\upmu^{r}=\uprho{\cdot}\mathop{\rm vol}\nolimits$. Define

$U_{m}\upmu\buildrel\hbox{\tiny\it
def}\over{=\joinrel=}\int\limits_{X}\uprho^{1-\frac{1}{m}}{\cdot}\,d\mathop{\rm
vol}\nolimits=\int\limits_{X}\frac{1}{\sqrt[m]{\uprho}}{\cdot}\,d\upmu^{r}.$

Then $X\in\text{\rm CD}[m,0]$ if the functional $U_{m}$ is concave in
$\mathrm{P}_{\mskip-3.0mu2}X$; i.e for any two measures
$\upmu_{0},\upmu_{1}\in\mathrm{P}_{\mskip-3.0mu2}X$, there is a geodesic path
$\upmu_{t}$, in $\mathrm{P}_{\mskip-3.0mu2}X$, $t\in[0,1]$ such that the real
function $t\mapsto U_{m}\upmu_{t}$ is concave.

Calculus in Alexandrov spaces. Let $A\in\text{\rm Alex}^{m}[\upkappa]$ and
$S\subset A$ be the subset of singular points; i.e. $x\in S$ if its tangent
space $\text{\rm T}_{x}$ is not isometric to Euclidean $m$-space
$\mathbb{E}^{m}$. The set $S$ has zero volume ([BGP, 10.6]). The set of
regular points $A\backslash S$ is convex ([Petrunin 98]); i.e. any geodesic
connecting two regular points consits only of regular points.

According to [Perelman], if $f\colon A\to\mathbb{R}$ is a semiconcave function
and $\Omega\subset A$ is an image of a $\mathrm{DC}_{0}$-chart, then
$\partial_{k}f$ and components of metric tensor $g^{ij}$ are functions of
locally bounded variation which are continuous in $\Omega\backslash S$.

Further, for almost all $x\in A$ the the Hession of $f$ is well defined. I.e.
there is a subset of full measure $\mathop{\rm Reg}\nolimits f\subset
A\backslash S$ such that for any $p\in\mathop{\rm Reg}\nolimits f$ there is a
bi-linear form111Note that $p\in A\backslash S$, thus $\text{\rm T}_{p}$ is
isometric to Euclidean $m$-space. $\operatorname{Hess}_{p}f$ on $\text{\rm
T}_{p}$ such that

$f(q)=f(p)+d_{p}f(v)+\operatorname{Hess}_{p}f(v,v)+o(|v|^{2}),$

where $v=\mathop{\rm log}\nolimits_{p}q$. Moreover, the Hessian can be found
using standard calculus in the $\mathrm{DC}_{0}$-chart. In particular,

$\text{\rm Trace}\operatorname{Hess}f\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\frac{\partial_{i}(\det g\cdot
g^{ij}\cdot\partial_{j}f)}{\det g}$

The following is an extract from second variation formula [Petrunin 98, 1.1B]
reformulated with formalism of ultrafilters. Let  be a nonprinciple
ultrafiler, $A\in\text{\rm Alex}^{m}[0]$ and $[pq]$ be a minimizing geodesic
in $A$ which is extendable beyond $p$ and $q$. Assume further that one of (and
therefore each) of points $p$ and $q$ is regular. Then there is a model
configuration $\tilde{p},\tilde{q}\in\mathbb{E}^{m}$ and isometries
$\imath_{p}\colon\text{\rm T}_{p}A\to\text{\rm T}_{\tilde{p}}\mathbb{E}^{m}$,
$\imath_{q}\colon\text{\rm T}_{q}A\to\text{\rm T}_{\tilde{q}}\mathbb{E}^{m}$
such that

$\mskip-3.0mu\left|\exp_{p}(\tfrac{1}{n}{\cdot}v)\,\exp_{q}(\tfrac{1}{n}{\cdot}w)\right|\leqslant\mskip-3.0mu\left|\exp_{\tilde{p}}\circ\imath_{p}(\tfrac{1}{n}{\cdot}v)\,\exp_{\tilde{q}}\circ\imath_{q}(\tfrac{1}{n}{\cdot}w)\right|+o(n^{2})$

for -almost all $n$ (once the left-hand side is well defined).

If $\tilde{\uptau}\colon\text{\rm T}_{\tilde{p}}\to\text{\rm T}_{\tilde{q}}$
is the parallel translation in $\mathbb{E}^{m}$, then the isometry
$\uptau\colon\text{\rm T}_{p}\to\text{\rm T}_{q}$ which satisfy identity
$\imath_{q}\circ\uptau=\tilde{\uptau}\circ\imath_{p}$ will be called
``parallel transportation'' from $p$ to $q$.

Laplacian of semiconcave function. Here are some facts from [Petrunin 03].

Given a function $f\colon A\to\mathbb{R}$, define its _Laplacian_ $\Delta f$
to be a Radon sign-measure which satisfies the following identity

$\int\limits_{A}u{\cdot}\,d\Delta f=-\int\limits_{A}\langle\nabla u,\nabla
f\rangle{\cdot}\,d\mathop{\rm vol}\nolimits$

for any Lipschitz function $u\colon A\to\mathbb{R}$.

1.1. Claim. Let $A\in\text{\rm Alex}^{m}[\upkappa]$ and $f\colon
A\to\mathbb{R}$ be $\uplambda$-concave Lipschitz function. Then Laplacian
$\Delta f$ is well defined and

$\Delta f\leqslant m{\cdot}\uplambda{\cdot}\mathop{\rm vol}\nolimits.$

In particular, $\Delta^{s}f$ — the singular part $\Delta f$ is negative.

Moreover,

$\Delta f=\text{\rm Trace}\operatorname{Hess}f{\cdot}\mathop{\rm
vol}\nolimits+\Delta^{s}f.$

Proof. Let us denote by $F_{t}\colon A\to A$ the $f$-gradient flow for time
$t$.

Given a Lipschitz function $u\colon A\to\mathbb{R}$, consider family
$u_{t}(x)=u\circ F_{t}(x)$. Clearly, $u_{0}\equiv u$ and $u_{t}$ is Lipschitz
for any $t\geqslant 0$. Further, for any $x\in A$ we have
$\bigl{|}{\tfrac{d^{+}}{dt}}u_{t}(x)|_{t=0}\bigr{|}\leqslant\mathrm{Const}$.
Moreover

$\tfrac{d^{+}}{dt}u_{t}(x)|_{t=0}\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}d_{x}u(\nabla_{x}f)\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\langle\nabla_{x}u,\nabla_{x}f\rangle.$

Further,

$\int\limits_{A}u_{t}{\cdot}\,d\mathop{\rm
vol}\nolimits=\int\limits_{A}u{\cdot}\,d(F_{t}\\#\mathop{\rm vol}\nolimits),$

where $\\#$ stands for push-forward. Since $|F_{t}(x)F_{t}(y)|\leqslant
e^{\uplambda t}{\cdot}|xy|$, for any $x,y\in A$ we have

$F_{t}\\#\mathop{\rm
vol}\nolimits\geqslant\exp(-m{\cdot}\uplambda{\cdot}t){\cdot}\mathop{\rm
vol}\nolimits.$

Therefore, for any non-negative Lipschitz function $u\colon A\to\mathbb{R}$,

$\int\limits_{A}u_{t}{\cdot}\,d\mathop{\rm
vol}\nolimits=\int\limits_{A}u{\cdot}\,d(F_{t}\\#\mathop{\rm
vol}\nolimits)\geqslant\exp(-m{\cdot}\uplambda{\cdot}t)\int\limits_{A}u{\cdot}\,d\mathop{\rm
vol}\nolimits.$

Therefore

$\int\limits_{A}\langle\nabla u,\nabla f\rangle{\cdot}\,d\mathop{\rm
vol}\nolimits=\mskip-3.0mu\left.\tfrac{d^{+}}{dt}\int\limits_{A}u_{t}{\cdot}\,d\mathop{\rm
vol}\nolimits\right|_{t=0}\geqslant-m{\cdot}\uplambda{\cdot}\int\limits_{A}u{\cdot}\,d\mathop{\rm
vol}\nolimits.$

I.e. there is a Radon measure $\upchi$ on $A$, such that

$\int\limits_{A}u{\cdot}\,d\upchi=\int\limits_{A}\mskip-3.0mu\left[\langle\nabla
u,\nabla f\rangle+m{\cdot}\uplambda{\cdot}u\right]{\cdot}\,d\mathop{\rm
vol}\nolimits$

Set $\Delta f=-\upchi+m{\cdot}\uplambda$, it is a Radon sign-measure and
$\upchi=-\Delta f+m{\cdot}\uplambda\geqslant 0$.

To prove the second part of theorem, assume $u$ is a non-negative Lipschitz
function with support in a DC0-chart $U\to A$, where $U\subset\mathbb{R}^{m}$
is an open subset. Then

$\displaystyle\int\limits_{A}\langle\nabla u,\nabla f\rangle$
$\displaystyle=\int\limits_{U}\det g\cdot
g^{ij}\cdot\partial_{i}u\cdot\partial_{j}f\cdot dx^{1}{\cdot}dx^{2}\cdots
dx^{m}=$ $\displaystyle=-\int\limits_{U}u\cdot\partial_{i}(\det g\cdot
g^{ij}\cdot\partial_{j}f)\cdot dx^{1}{\cdot}dx^{2}\cdots dx^{m},$

Thus

$\Delta f=\partial_{i}(\det g\cdot g^{ij}\cdot\partial_{j}f)\cdot
dx^{1}{\cdot}dx^{2}\cdots dx^{m}\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\text{\rm Trace}\operatorname{Hess}f.$

∎

Gradient curves. Here I extend notion of gradient curves to a family of
functions, see [Petrunin 07] for all necessary definitions.

Let $\mathbb{I}$ be an open real interval and
$\uplambda\colon\mathbb{I}\to\mathbb{R}$ be a continuous function. A one
parameter family of functions $f_{t}\colon A\to\mathbb{R}$, $t\in\mathbb{I}$
will be called _$\uplambda(t)$ -concave_ if the function $(t,x)\mapsto
f_{t}(x)$ is locally Lipschitz and $f_{t}$ is $\uplambda(t)$-concave for each
$t\in\mathbb{I}$.

We will write $\upalpha^{\pm}(t)=\nabla f_{t}$ if for any $t\in\mathbb{I}$,
the right/left tangent vector $\upalpha^{\pm}(t)$ is well defined and
$\upalpha^{\pm}(t)=\nabla_{\upalpha(t)}f_{t}$. The solutions of
$\upalpha^{+}(t)=\nabla f_{t}$ will be also called $f_{t}$-gradient curves.

The following is a slight generalization of [Petrunin 07, 2.1.2$\&$2.2(2)]; it
can be proved along the same lines.

1.2. Proposition-definition. Let $A\in\text{\rm Alex}^{m}[\upkappa]$,
$\mathbb{I}$ be an open real interval,
$\uplambda\colon\mathbb{I}\to\mathbb{R}$ be a continuous function and
$f_{t}\colon A\to\mathbb{R}$, $t\in\mathbb{I}$ be $\uplambda(t)$-concave
family.

Then for any $x\in A$ and $t_{0}\in\mathbb{I}$ there is an $f_{t}$-gradient
curve $\upalpha$ which is defined in a neighborhood of $t_{0}$ and such that
$\upalpha(t_{0})=x$.

More over, if $\upalpha,\upbeta\colon\mathbb{I}\to A$ $f_{t}$-gradient then
for any $t_{0},t_{1}\in\mathbb{I}$, $t_{0}\leqslant t_{1}$,

$|\upalpha(t_{1})\upbeta(t_{1})|\leqslant L|\upalpha(t_{0})\upbeta(t_{0})|,$

where
$L=\exp\mskip-3.0mu\left(\int_{t_{0}}^{t_{1}}\uplambda(t){\cdot}\,dt\right).$

Note that above proposition implies that the value $\upalpha(t_{0})$ of
$f_{t}$-gradient curve $\upalpha(t)$ uniquely determines it for all
$t\geqslant t_{0}$ in $\mathbb{I}$. Thus we can define _$f_{t}$ -gradient
flow_ — a family of maps $F_{{t_{0}},{t_{1}}}\colon A\to A$ such that

$F_{{t_{0}},{t_{1}}}(\upalpha(t_{0}))=\upalpha(t_{1})\ \ \text{if}\ \
\upalpha^{+}(t)=\nabla f_{t}.$

1.3. Claim. Let $f_{t}\colon A\to\mathbb{R}$ be a $\uplambda(t)$-concave
family and $F_{{t_{0}},{t_{1}}}$ be $f_{t}$-gradient flow. Let $E\subset A$ be
a bounded Borel set, fix $t_{1}$ and consider function $v(t)=\mathop{\rm
vol}\nolimits F^{-1}_{{t},{t_{1}}}(E)$. Then

$\bigl{.}v\bigr{|}_{t}^{t_{1}}=\int\limits_{t}^{t_{1}}\Delta
f_{\text{\it\c{t}}}\mskip-3.0mu\left[F^{-1}_{\text{\it\c{t}},{t_{1}}}(E)\right]{\cdot}\,d\text{\it\c{t}}$

Proof. Let $u\colon A\to\mathbb{R}$ be a Lipschitz function with compact
support. Set $u_{t}=u\circ F_{{t},{t_{1}}}$. Clearly all $(x,t)\mapsto
u_{t}(x)$ is locally Lipschitz. Thus, the function

$w_{u}\colon t\mapsto\int\limits_{A}u_{t}{\cdot}\,d\mathop{\rm vol}\nolimits$

is locally Lipschitz. Further

$w_{u}^{\prime}(t)\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}-\int\limits_{A}\langle\nabla u_{t},\nabla
f_{t}\rangle{\cdot}\,d\mathop{\rm
vol}\nolimits=\int\limits_{A}u_{t}{\cdot}\,d\Delta f_{t}.$

Therefore

$\bigl{.}w_{u}\bigr{|}_{t}^{t_{1}}=\int\limits_{t}^{t_{1}}d\text{\it\c{t}}\cdot\int\limits_{A}u_{t}{\cdot}\,d\Delta
f_{t}.$

The last formula extendeds to arbitrary Borel function $u\colon
A\to\mathbb{R}$ with bounded support. Applying it to characteristic function
of $E$ we get the result. ∎

##  2 Games with Hamilton–Jacobi shifts.

Let $A\in\text{\rm Alex}^{m}[0]$. For a function $f\colon
A\to\mathbb{R}\cup\\{+\infty\\}$, let us define its Hamilton–Jacobi
shift222There is a lot of similarity between Hamilton–Jacobi shift of function
and equidistant for hypersurface. $\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}f\colon A\to\mathbb{R}$
for time $t>0$,

$\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}f(x)\buildrel\hbox{\tiny\it
def}\over{=\joinrel=}\inf_{y\in
A}\mskip-3.0mu\left\\{f(y)+\tfrac{1}{2t}{\cdot}|xy|^{2}\right\\}.$

We say that $\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}f$ is well defined if the
above infimum is $>-\infty$ everywhere in $A$. Clearly,

$\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t_{0}+t_{1}}f=\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t_{1}}\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t_{0}}f,$ ➋

for any $t_{0},t_{1}>0$.

Note that for $t>0$, $f_{t}=\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}f$ forms a
$\tfrac{1}{t}$-concave family, thus, we can apply 1 and 1. The next theorem
gives a more delicate property of the gradient flow, for such families; it is
an analog of [Petrunin 07, 3.3.6].

2.1. Claim. Let $A\in\text{\rm Alex}^{m}[0]$, $f_{0}\colon A\to\mathbb{R}$ be
function and $f_{t}=\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}f_{0}$ is well defined
for $t\in(0,1)$. Assume $\upgamma\colon[0,1]\to A$ is a geodesic path which is
an $f_{t}$-gradient in $(0,1)$ and $\upalpha\colon(0,1)\to A$ is an other
$f_{t}$-gradient curve. Then if for some $t_{0}\in(0,1)$,
$\upalpha(t_{0})=\upgamma(t_{0})$ then $\upalpha(t)=\upgamma(t)$ for all
$t\in(0,1)$.

$x$$z$$y$$p$$\ell$$\upalpha$$\upgamma$$\upsigma$

Proof. Note that function $\ell=\ell(t)=|\upalpha(t)\upgamma(t)|$ is locally
Lipschitz in $(0,1)$. According to 1, it is sufficient to show that

$\ell^{\prime}\geqslant-[\tfrac{1}{t}+\tfrac{2}{1-t}]{\cdot}\ell$

for almost all $t$.

Since $\upalpha$ is locally Lipschitz, for almost all $t$, $\upalpha^{+}(t)$
and $\upalpha^{-}(t)$ are well defined and _opposite_ 333I.e.
$|\upalpha^{+}(t)|=|\upalpha^{-}(t)|$ and
$\measuredangle(\upalpha^{+}(t),\upalpha^{-}(t))=\uppi$ to each other.

Fix such $t$ and set $x=\upgamma(0)$, $z=\upgamma(t)$, $y=\upgamma(1)$,
$p=\upalpha(t)$, so $\ell(t)=|pz|$. Note that function

$f_{t}+\tfrac{1}{2(1-t)}{\cdot}\mathop{\rm dist}\nolimits^{2}_{y}$ ➌

has a minimum at $z$. Extend a geodesic $[zp]$ by a both-sides infinite unit-
speed quasigeodesic444A careful proof of existence of quasigeodesics can be
found in [Petrunin 07]. $\upsigma\colon\mathbb{R}\to A$, so $\upsigma(0)=z$
and $\upsigma^{+}(0)={\uparrow}_{\mskip-3.0mu[{z}{p}]}$. The function
$f_{t}\circ\upsigma\colon\mathbb{R}\to\mathbb{R}$ is $\tfrac{1}{t}$-concave
and from ➌ ‣ 2,

$f_{t}\circ\upsigma(s)\geqslant
f_{t}(z)+\langle\upgamma^{+}(t),{\uparrow}_{\mskip-3.0mu[{z}{p}]}\rangle{\cdot}s-\tfrac{1}{2(1-t)}{\cdot}s^{2}.$

It follows that

$\displaystyle\langle\nabla_{p}f_{t},\upsigma^{+}(\ell)\rangle$
$\displaystyle\geqslant d_{p}f_{t}(\upsigma^{+}(\ell))=$
$\displaystyle=(f_{t}\circ\upsigma)^{+}(\ell)\geqslant$
$\displaystyle\geqslant\langle\upgamma^{+}(t),{\uparrow}_{\mskip-3.0mu[{z}{p}]}\rangle-[\tfrac{1}{t}+\tfrac{2}{1-t}]{\cdot}\ell.$

Now,

  1. 1.

Vectors $\upsigma^{\pm}(\ell)$ are polar, thus
$\langle\upalpha^{\pm}(t),\upsigma^{+}(\ell)\rangle+\langle\upalpha^{\pm}(t),\upsigma^{-}(\ell)\rangle\geqslant
0$.

  2. 2.

Vectors $\upalpha^{\pm}(t)$ are opposite, thus
$\langle\upalpha^{+}(t),\upsigma^{\pm}(\ell)\rangle+\langle\upalpha^{-}(t),\upsigma^{\pm}(\ell)\rangle=0.$

  3. 3.

$\upalpha^{+}(t)=\nabla_{p}f_{t}$ and
$\upsigma^{-}(\ell)={\uparrow}_{\mskip-3.0mu[{p}{z}]}$

Thus,
$\langle\nabla_{p}f_{t},\upsigma^{+}(\ell)\rangle+\langle\upalpha^{+}(t),{\uparrow}_{\mskip-3.0mu[{p}{z}]}\rangle=0$.
Therefore

$\ell^{\prime}=-\langle\upalpha^{+}(t),{\uparrow}_{\mskip-3.0mu[{p}{z}]}\rangle-\langle\upgamma^{+}(t),{\uparrow}_{\mskip-3.0mu[{z}{p}]}\rangle\geqslant-[\tfrac{1}{t}+\tfrac{2}{1-t}]{\cdot}\ell.$

∎

2.2. Proposition. Let $A\in\text{\rm Alex}^{m}[0]$, $f\colon A\to\mathbb{R}$
be bounded and continuous function and $f_{t}=\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}f$. Assume
$\upgamma\colon(0,a)\to A$ is a $f_{t}$-gradient curve which is also a
constant-speed geodesic. Assume that function

$h(t)\buildrel\hbox{\tiny\it def}\over{=\joinrel=}\text{\rm
Trace}\operatorname{Hess}_{\upgamma(t)}f_{t}$

is defined for almost all $t\in(0,a)$. Then

$h^{\prime}\leqslant-\tfrac{1}{m}{\cdot}h^{2}$

in the sense of distributions; i.e. for any non-negative Lipschitz function
$u\colon(0,a)\to\nobreak\mathbb{R}$ with compact support

$\int\limits_{0}^{a}\mskip-3.0mu\left(\tfrac{1}{m}{\cdot}h^{2}{\cdot}u-h{\cdot}u^{\prime}\right){\cdot}\,dt\geqslant
0.$

Proof. Since $h$ are defined a.e., all $\text{\rm T}_{\upgamma(t)}$ for
$t\in(0,a)$ are isometric to Euclidean $m$-space. From ➋ ‣ 2,

$f_{t_{1}}(x)=\inf_{y\in
A}\mskip-3.0mu\left\\{f_{t_{0}}(y)+\frac{|xy|^{2}}{2{\cdot}(t_{1}-t_{0})}\right\\}.$

Thus, for a parallel transportation $\uptau\colon\text{\rm
T}_{\upgamma(t_{0})}\to\text{\rm T}_{\upgamma(t_{1})}$ along $\upgamma$, we
have

$\operatorname{Hess}_{\upgamma(t_{1})}f_{t_{1}}(y)\leqslant\operatorname{Hess}_{\upgamma(t_{0})}f_{t_{0}}(x)+\frac{|\uptau(x)\,y|^{2}}{2{\cdot}(t_{1}-t_{0})}$

for any $x\in\text{\rm T}_{\upgamma(t_{0})}$ and $y\in\text{\rm
T}_{\upgamma(t_{1})}$. Taking trace leads to the result. ∎

##  3 Proof of the main theorem

Let $A\in\text{\rm Alex}^{m}[0]$; in particular $A$ is proper geodesic space.
Let $\upmu_{t}$ be a family of probability measures on $A$ for $t\in[0,1]$
which forms a _geodesic path_ 555i.e. constant-speed minimizing geodesic
defined on $[0,1]$ in $\mathrm{P}_{\mskip-3.0mu2}A$ and both $\upmu_{0}$ and
$\upmu_{1}$ are absolutely continuous with respect to volume on $A$.

It is sufficient666It follows from [Villani, 30.32] since Alexandrov’s spaces
are nonbranching. to show that function

$\Theta\colon t\mapsto U_{m}\upmu_{t}$

is concave.

According to [Villani, 7.22], there is a probability measure $\Pi$ on the
space of all geodesic paths in $A$ which satisfy the following: If
$\Gamma=\mathop{\rm supp}\nolimits\text{\scriptsize$\Pi$}$ and
$e_{t}\colon\Gamma\to A$ is evaluation map
$e_{t}\colon\upgamma\mapsto\upgamma(t)$ then
$\upmu_{t}=e_{t}\\#\text{\scriptsize$\Pi$}$.

The measure $\Pi$ is called _dynamical optimal coupling_ for $\upmu_{t}$ and
the measure $\uppi=(e_{0},e_{1})\\#\text{\scriptsize$\Pi$}$ is the
corresponding _optimal transference plan_. The space $\Gamma$ will be
considered further equipped with the metric
$|\upgamma\,\upgamma^{\prime}|=\max_{t\in[0,1]}|\upgamma(t)\upgamma^{\prime}(t)|$.

First we present $\upmu_{t}$ as push-forward of each other for gradients flow
of a family of functions. According to [Villani, 5.10], there are optimal
price functions $\upvarphi,\uppsi\colon A\to\mathbb{R}$ such that

$\upvarphi(y)-\uppsi(x)\leqslant\tfrac{1}{2}{\cdot}|xy|^{2}$

for any $x,y\in A$ and equality holds for any $(x,y)\in\mathop{\rm
supp}\nolimits\uppi$. We can assume that $\uppsi(x)=+\infty$ for
$x\not\in\mathop{\rm supp}\nolimits\upmu_{0}$ and $\upvarphi(y)=-\infty$ for
$y\not\in\mathop{\rm supp}\nolimits\upmu_{1}$.

Consider two families of functions

$\uppsi_{t}=\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{t}\uppsi\ \ \ \ \text{and}\
\ \ \ \upvarphi_{t}=\mathop{\mathcal{H}\hbox
to0.0pt{$\displaystyle\phantom{I}$\hss}}\nolimits_{1-t}(-\upvarphi).$

Clearly, $\uppsi_{t}$ forms a $\tfrac{1}{t}$-concave family for $t\in(0,1]$
and $\upvarphi_{t}$ forms777Note that usually $\upvarphi_{t}$ is defined with
opposite sign, but I wanted to work with semiconcave functions only. a
$\tfrac{1}{1-t}$-concave family for $t\in[0,1)$.

It is straightforward to check that for any $\upgamma\in\Gamma$ and
$t\in(0,1)$

$\pm\langle\upgamma^{\pm}(t),v\rangle=d_{\upgamma(t)}\uppsi_{t}(v)=-d_{\upgamma(t)}\upvarphi_{t}(v);$

in particular,

$\upgamma^{+}(t)=\nabla\uppsi_{t}\ \ \ \ \text{and}\ \ \ \
\upgamma^{-}(t)=\nabla\upvarphi_{t}.$ ➍

For $0<t_{0}\leqslant t_{1}\leqslant 1$, let us consider the maps
$\Psi_{t_{0},t_{1}}\colon A\to A$ — the gradient flow of $\uppsi_{t}$, defined
by

$\Psi_{t_{0},t_{1}}\upalpha(t_{0})=\upalpha(t_{1})\ \ \ \ \text{if}\ \ \ \
\upalpha^{+}(t)=\nabla\uppsi_{t}.$

Similarly, $0\leqslant t_{0}\leqslant t_{1}<1$, define map
$\Phi_{t_{1},t_{0}}\colon A\to A$

$\Phi_{t_{1},t_{0}}\upbeta(t_{1})=\upbeta(t_{0})\ \ \ \ \text{if}\ \ \ \
\upbeta^{-}(t)=\nabla\upvarphi_{t}.$

According to 1,

$\Psi_{t_{0},t_{1}}\ \text{is}\ \tfrac{t_{1}}{t_{0}}\text{-Lipschitz\ \ \ \ \
and}\ \ \ \ \ \Phi_{t_{1},t_{0}}\ \text{is}\
\tfrac{1-t_{0}}{1-t_{1}}\text{-Lipschitz.}$ ➎

From ➍ ‣ 3, $e_{t_{1}}=\Psi_{t_{0},t_{1}}\circ e_{t_{0}}$ and
$e_{t_{0}}=\Phi_{t_{1},t_{0}}\circ e_{t_{1}}$. Thus, for any $t\in(0,1)$, the
map $e_{t}\colon\Gamma\to A$ is bi-Lipschits. In particular, for any measure
$\upchi$ on $A$, there is uniquely determined one-parameter family of ``pull-
back'' measures $\upchi_{t}^{*}$ on $\Gamma$, i.e. such that
$\upchi^{*}_{t}E=\upchi(e_{t}E)$ for any Borel subset $E\subset\Gamma$.

Fix some $z_{0}\in(0,1)$ (one can take $z_{0}=\tfrac{1}{2}$) and equip
$\Gamma$ with the measure $\upnu=\mathop{\rm vol}\nolimits_{z_{0}}^{*}$. Thus,
from now on ``almost everywhere'' has sense in $\Gamma$, $\Gamma\times(0,1)$
and so on.

Now we will represent $\Theta$ in terms of families of functions on $\Gamma$.
Note that $\upmu_{1}=\Psi_{t,1}\\#\upmu_{t}$ and $\Psi_{t,1}$ is
$\tfrac{1}{t}$-Lipschitz. Since $\upmu_{1}$ is absolutely continuous, so is
$\upmu_{t}$ for all $t$. Set $\upmu_{t}=\uprho_{t}{\cdot}\mathop{\rm
vol}\nolimits$. Note that from ➎ ‣ 3, we get that

$\mskip-3.0mu\left(\frac{1-t_{1}}{1-t_{0}}\right)^{m}\leqslant\frac{\uprho_{t_{1}}(\upgamma(t_{1})}{\uprho_{t_{0}}(\upgamma(t_{0})}\leqslant\mskip-3.0mu\left(\frac{t_{1}}{t_{0}}\right)^{m}$

for almost all $\upgamma\in\Gamma$ and $0<t_{0}<t_{1}<1$. For
$\upgamma\in\Gamma$ set $r_{t}(\upgamma)=\uprho_{t}(\upgamma(t))$. Then

$\Theta(t)=\int\limits_{A}\uprho_{t}^{-\frac{1}{m}}{\cdot}\,d\upmu_{t}=\int\limits_{\Gamma}r_{t}^{-\frac{1}{m}}{\cdot}\,d\text{\scriptsize$\Pi$}.$
➏

In particular, $\Theta$ locally Lipschitz in $(0,1)$.

Next we show that measure $\Delta\upvarphi_{t}$ is absolutely continuous on
$e_{t}\Gamma$ and that
$r_{t}(\upgamma(t))=\uprho_{t}(\upgamma(t)){\cdot}\Delta\upvarphi_{t}$ in some
weak sense. From ➎ ‣ 3, $\mathop{\rm
vol}\nolimits_{t}^{*}=e^{w_{t}}{\cdot}\upnu$ for some Borel function
$w_{t}\colon\Gamma\to\mathbb{R}$. Thus

$\mathop{\rm vol}\nolimits e_{t}E=\int\limits_{E}e^{w_{t}}{\cdot}\,d\upnu$

for any Borel subset $E\subset\Gamma$. Moreover, for almost all
$\upgamma\in\Gamma$, we have that function $t\mapsto w_{t}(\upgamma)$ is
locally Lipschitz in $(0,1)$ (more precicely, $t\mapsto w_{t}(\upgamma)$
coinsides with a Lipschitz function outside of a set of zero measure). In
particular $\frac{\partial w_{t}}{\partial t}$ is well defined a.e. in
$\Gamma\times(0,1)$ and moreover

$w_{t}\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\int\limits_{z_{0}}^{t}\frac{\partial
w_{\text{\it\c{t}}}}{\partial\text{\it\c{t}}}{\cdot}\,d\text{\it\c{t}}.$

Further, from 2, if $0<t_{0}\leqslant t_{1}<1$ then for any
$\upgamma\in\Gamma$,

$\Psi_{t_{0},t_{1}}(x)=\upgamma(t_{1})\ \ \Longleftrightarrow\ \
x=\upgamma({t_{0}}),$ $\Phi_{t_{1},t_{0}}(x)=\upgamma({t_{0}})\ \
\Longleftrightarrow\ \ x=\upgamma({t_{1}}).$

Thus, for any Borel subset $E\subset\Gamma$,

$e_{t_{1}}E=\Psi_{t_{0},t_{1}}\circ
e_{t_{0}}E=\Phi^{-1}_{t_{1},t_{0}}\mskip-3.0mu\left(e_{t_{0}}E\right),$
$e_{t_{0}}E=\Phi_{t_{1},t_{0}}\circ
e_{t_{1}}E=\Psi^{-1}_{t_{0},t_{1}}\mskip-3.0mu\left(e_{t_{1}}E\right)$

Set

$v(t)\buildrel\hbox{\tiny\it def}\over{=\joinrel=}\mathop{\rm vol}\nolimits
e_{t}E=\int\limits_{E}e^{w_{t}}{\cdot}\,d\upnu.$

From 1,

$v^{\prime}(t)\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\Delta\uppsi_{t}(e_{t}E)\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}-\Delta\upvarphi_{t}(e_{t}E).$

Thus, $\Delta\uppsi_{t}+\Delta\upvarphi_{t}=0$ everywhere on $e_{t}\Gamma$.
From 1,

$\Delta\uppsi_{t}\leqslant\tfrac{m}{t}{\cdot}\mathop{\rm vol}\nolimits,\ \ \ \
\ \ \ \ \Delta\upvarphi_{t}\leqslant\tfrac{m}{1-t}{\cdot}\mathop{\rm
vol}\nolimits.$

Thus, both restrictions $\Delta\uppsi_{t}|_{e_{t}\Gamma}$ and
$\Delta\upvarphi_{t}|_{e_{t}\Gamma}$ are absolutely continuous with respect to
volume. Therefore

$v^{\prime}(t)\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\int\limits_{e_{t}E}\text{\rm
Trace}\operatorname{Hess}\upvarphi_{t}{\cdot}\,d\mathop{\rm vol}\nolimits.$

For one parameter family of functions $h_{t}(\upgamma)=\text{\rm
Trace}\operatorname{Hess}_{\upgamma(t)}\upvarphi_{t}$, we have

$\bigl{.}v\bigr{|}_{z_{0}}^{t}=\int\limits_{E}(e^{w_{t}}-1){\cdot}\,d\upnu=\int\limits_{z_{0}}^{t}d\text{\it\c{t}}\cdot\int\limits_{E}h_{\text{\it\c{t}}}{\cdot}e^{w_{\text{\it\c{t}}}}{\cdot}\,d\upnu$

or any Borel set $E\subset\Gamma$. Equivalently,

$\frac{\partial w_{t}}{\partial t}\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}h_{t}$

From 2,

$\frac{\partial h_{t}}{\partial t}\leqslant-\tfrac{1}{m}{\cdot}h_{t}^{2}$

Thus, for almost all $\upgamma\in\Gamma$, the following inequality holds in
the sense of distributions:

$\frac{\partial^{2}}{\partial
t^{2}}\exp\mskip-3.0mu\left(\frac{w_{t}(\upgamma)}{m}\right)=\mskip-3.0mu\left(\tfrac{1}{m^{2}}{\cdot}{h_{t}^{2}}+\tfrac{1}{m}{\cdot}\frac{\partial
h_{t}}{\partial
t}\right){\cdot}\exp\mskip-3.0mu\left(\frac{w_{t}(\upgamma)}{m}\right)\leqslant
0;$

i.e. $t\mapsto\exp\mskip-3.0mu\left(\frac{w_{t}(\upgamma)}{m}\right)$ is
concave — more precisely,
$t\mapsto\exp\mskip-3.0mu\left(\frac{w_{t}(\upgamma)}{m}\right)$ coinsides
with a concave function almost everywhere.

Clearly, for any $t$ we have $\upmu=r_{t}{\cdot}e^{w_{t}}{\cdot}\upnu$. Thus,
for almost all $\upgamma$ there is a non-negative Borel function
$a\colon\Gamma\to\mathbb{R}_{\geqslant}$ such that
$r_{t}\buildrel\hbox{\tiny\it a.e.}\over{=\joinrel=}a{\cdot}e^{-w_{t}}$.
Continue ➏ ‣ 3,

$\Theta(t)=\int\limits_{\Gamma}r_{t}^{-\frac{1}{m}}{\cdot}\,d\text{\scriptsize$\Pi$}=\int\limits_{\Gamma}{e^{\frac{w_{t}}{m}}}{\cdot}{\sqrt[m]{a}}{\cdot}\,d\text{\scriptsize$\Pi$}$

I.e. $\Theta$ is concave as an average of concave functions. Again, more
precisely, $\Theta$ coinsides with a concave function a.e., but since $\Theta$
is locally Lipschitz in $(0,1)$ we get that $\Theta$ is concave. ∎

## References

  * [AG] Abresch, U., Gromoll, D., On complete manifolds with nonnegative Ricci curvature, J. Amer. Math. Soc. 3 (1990), no 2 355–374.
  * [Bertrand] Bertrand, J., Existence and uniqueness of optimal maps on Alexandrov spaces. Adv. Math. 219, 3 (2008), 838–851.
  * [BGP] Burago, Yu.; Gromov, M.; Perelman, G., A. D. Aleksandrov spaces with curvatures bounded below. (Russian) Uspekhi Mat. Nauk 47 (1992), no. 2(284), 3–51, 222; translation in Russian Math. Surveys 47 (1992), no. 2, 1–58
  * [CMS] Cordero-Erausquin, D.; McCann,R.; Schmuckenschlager, M., A Riemannian interpolation inequality a la Borell, Brascamp and Lieb, Invent. Math. 146 (2001), 219–257.
  * [McCann] McCann, R.J., A convexity principle for interacting gases. Adv. Math. 128 (1997), 153–179
  * [Lott–Villani] Lott, J.; Villani, C., Ricci curvature for metric-measure spaces via optimal transport. in press.
  * [Otto–Villani] Otto, F.; Villani, C., Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. J. Funct. Anal. 173 (2000), 361-400
  * [Perelman] Perelman, G., DC Structure on Alexandrov Space,
http://www.math.psu.edu/petrunin/

  * [Petrunin 98] Petrunin, A., Parallel transportation for Alexandrov space with curvature bounded below. GAFA, Vol. 8 (1998) 123–148
  * [Petrunin 03] Petrunin, A., Harmonic functions on Alexandrov space and its applications, ERA American Mathematical Society, 9 (2003)
  * [Petrunin 07] Petrunin, A. Semiconcave Functions in Alexandrov's Geometry, Surveys in Differential Geometry XI.
  * [Villani] Villani, C., Optimal transport, old and new, Grundlehren der mathematischen Wissenschaften, Vol. 338, Springer, 2008.
  * [Sturm] Sturm, K.-T. On the geometry of metric measure spaces. I–II. Acta Math. 196, 1 (2006), 65–177.
  * [Sturm–v.Renesse] Sturm, K.-Th.; von Renesse, M.-K., Transport inequalities, gradient estimates, entropy and Ricci curvature. Comm. Pure Appl. Math. 58 (2005), 923–940


# Ordinal Imitative Dynamics

George Loginov111Department of Economics, Augustana University, 2001 S Summit
Ave, Sioux Falls, SD 57197, USA. Email<EMAIL_ADDRESS>
###### Abstract

This paper introduces an evolutionary dynamics based on imitate the better
realization (IBR) rule. Under this rule, agents in a population game imitate
the strategy of a randomly chosen opponent whenever the opponent‘s realized
payoff is higher than their own. Such behavior generates an ordinal mean
dynamics which is polynomial in strategy utilization frequencies. We
demonstrate that while the dynamics does not possess Nash stationarity or
payoff monotonicity, under it pure strategies iteratively strictly dominated
by pure strategies are eliminated and strict equilibria are locally stable. We
investigate the relationship between the dynamics based on the IBR rule and
the replicator dynamics. In trivial cases, the two dynamics are topologically
equivalent. In Rock-Paper-Scissors games we conjecture that both dynamics
exhibit the same types of behavior, but the partitions of the game set do not
coincide. In other cases, the IBR dynamics exhibits behaviors that are
impossible under the replicator dynamics.

##  1 Introduction

When information about the available strategies and their payoffs is limited,
it may be reasonable for players in a population game to copy the behavior of
their opponents if it yields or at least seems to yield better payoffs. Such
copying gives rise to a family of imitative revision protocols, in which a
player’s decision to switch strategies depends on some summary of the relative
performance of a random sample of opponents the player gets to observe.

The two components that comprise any imitative protocol are the sampling
procedure which determines the candidates to be imitated, and the conditional
imitation rate which describes the likelihood of imitation given the
information about the candidates’ strategies and payoffs. With respect to the
payoff information one can distinguish between protocols that rely on average
payoffs and ones that only depend on realized payoffs from a small number of
matches.

This paper studies the imitative protocol with the fewest information
requirements. A player who gets a revision opportunity observes one opponent
from the population at random and switches to that opponent’s strategy
whenever the opponent’s realized payoff is higher than his or her own. This
revision rule labeled imitate the better realization (IBR) was first studied
in Izquierdo and Izquierdo, (2013) in the context of two-strategy games. (We
elaborate on their results in Section 3.) It gives rise to ordinal mean
dynamics since it ignores the magnitudes of payoff differences, and the
resulting dynamics is polynomial in strategy utilization frequencies.

The disregard of the payoff differences deprives the dynamics of some common
cardinal properties. For instance, the Nash equilibria of the base game need
not be the rest points of the dynamics, and the average payoffs need not
improve along the solution trajectories. At a rest point, instead of
equilibrating the average payoffs of the surviving strategies, the dynamics
balances the flows to and from each surviving strategy.

Despite not being monotone in average payoffs, the dynamics still eliminates
pure strategies iteratively dominated by pure strategies. Weakly dominated
strategies and pure strategies dominated by mixed strategies, on the contrary,
may survive. In addition, we demonstrate that strict equilbria are locally
stable.

The dynamics generated by the IBR rule in many cases qualitatively resembles
the replicator dynamics, which can be derived from the pairwise proportional
imitation rule of Schlag, (1998). Under the PPI rule a revising agent observes
one opponent from the population at random and switches to that opponent’s
strategy at a rate proportional to the payoff advantage of that strategy.
Thus, both the IBR and the PPI rule are based on comparisons of realized
payoffs, but the magnitudes of payoffs matter only under the latter rule.

In two-strategy games the IBR dynamics and the replicator dynamics are
topologically equivalent: they have the same number of rest points, and their
stability and convergence properties are the same. In the Rock-Paper-Scissors
games both dynamics exhibit one of the three possible behaviors: global
convergence to the rest point, global convergence to the boundary, or closed
orbits around the rest point222In the first two cases we make a conjecture
about global behavior based on local stability analysis and simulations. In
the third case we prove the statement formally., but these behaviors need to
be the same. In other cases, for instance in Zeeman’s game, the number of
interior rest points the two dynamics possess is different.

The study of ordinal imitative dynamics originated with Hofbauer, (1995) and
Schlag, (1998), in which the imitate if better (IB) dynamics – the average
payoff counterpart of imitate the better realization – were introduced and
their main properties established. In particular, Hofbauer, (1995)
demonstrates that in the Rock-Paper-Scissors games the IB dynamics behaves
similarly to the replicator dynamics. A surprising result is that IB need not
eliminate dominated strategies.

Finally, put in the larger context, the imitate the better realization rule
can be viewed as an analogue of the word-of-mouth communication model (Ellison
and Fudenberg (1993)) for strategic environments: agents can learn about the
relative merits of strategies from others’ experiences, but need not be able
to find out the exact advantage of a particular strategy. For instance, one
can learn about a better route from a neighbor or a better mode of behavior
from an elder.

##  2 The Imitate the Better Realization protocol and its properties

Suppose that a continuum of agents of mass 1 are randomly matched to play a
symmetric two-player game with the payoff matrix $A$. Let $S=\\{1,\ldots,n\\}$
be the set of strategies, and for $i,j\in S$ let $\pi_{ij}$ be the payoff of
strategy $i$ against strategy $j$. At any instant, the population state
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})$ describes the proportion of players
choosing each strategy. The set of all such population states is the
$(n-1)$-dimensional simplex $\Delta=\\{\mathbf{x}\text{
}|\sum_{i=1}^{n}x_{i}=1,x_{i}\geq 0\\}$.

Assume that the agents do not know the structure of the game, they are not
aware of all the available strategies, and they don’t keep the record of the
strategies they used in the past or the payoffs they received in their
previous interactions. In addition, they don’t know the current population
state and they are not capable of correctly anticipating the way it will
evolve. The only piece of information they possess and are able to retain is
their current payoff, and the only way they can learn about alternative modes
of behavior is by observing the strategies of others.

The only objective of the agents compatible with these assumptions is
maximizing their current payoffs. As usual in a population setting, they are
only able to switch their strategies infrequently, and once a strategy
revision opportunity arises, the revising agent observes one opponent from the
population at random and switches to that opponent‘s strategy whenever the
opponent‘s realized payoff is higher than his or her own.

Effectively, the revising agent gets to compare their current payoff to a
sample payoff of some other strategy without learning the circumstance under
which that sample payoff was obtained. Thus agents cannot distinguish between
strategies that perform better on average and favorable circumstances in which
worse strategies outperform better ones. Besides, upon switching to the
candidate strategy the agent’s payoff may differ from the sample payoff he or
she got to observe. As a result, such “blind” imitation may not be improving
in terms of average payoffs, and yet it eliminates dominated strategies.

Given this imitate the better realization revision protocol, the switch rate
$\rho_{ij}$ from strategy $i$ to strategy $j$ can be expressed as the
probability that a payoff drawn from the $j$-th row of the payoff matrix $A$
exceeds a payoff drawn from the $i$-th row, with the population state
$\mathbf{x}$ serving as the probability distribution:

$\rho_{ij}(\mathbf{x},A)=x_{j}\sum_{k=1}^{n}x_{k}\sum_{m=1}^{n}x_{m}\mathbf{1}_{\\{\pi_{jk}>\pi_{im}\\}}$

The population setting offers the following interpretation: the realized
payoff of a revising agent playing strategy $i$ equals $\pi_{im}$ with
probability $x_{m}$ for $m\in S$. Such an agent would observe a payoff
realization $\pi_{jk}$ for strategy $j$ with probability $x_{j}x_{k}$ for
$k\in S$. Summing over $m$ and $k$ and counting the cases in which the payoff
to the candidate strategy $j$ is better yields the probability of switching
$\rho_{ij}(\mathbf{x},A)$.

A stochastic process that emerges when agents in the population independently
receive revision opportunities can be approximated by its mean dynamics which
describes the expected change in the proportion of agents playing each
strategy (Benaïm and Weibull, (2003)). The mean dynamics of the process
governed by imitation of the better realization is

$\dot{x}_{i}=\sum_{j=1}^{n}x_{j}\rho_{ji}(\mathbf{x},A)-x_{i}\sum_{j=1}^{n}\rho_{ij}(\mathbf{x},A)$
$=x_{i}\sum_{j=1}^{n}x_{j}\left(\sum_{k=1}^{n}x_{k}\sum_{m=1}^{n}x_{m}(\mathbf{1}_{\\{\pi_{jk}<\pi_{im}\\}}-\mathbf{1}_{\\{\pi_{jk}>\pi_{im}\\}})\right)$

Thus in general the IBR dynamics is a quartic polynomial in $n$ variables
$\\{x_{1},x_{2},\ldots,x_{n}\\}$, but in certain cases, as shown in the next
subsection, it reduces to the replicator dynamics which is cubic in $x_{i}$
and is the mean dynamics for a number of more information-demanding imitative
rules (Imitation via pairwise comparisons of Helbing, (1992) and Schlag,
(1998), imitation driven by dissatisfaction of Björnerstedt and Weibull,
(1996), and imitation of success of Hofbauer, (1995), see also Section 5.4.2
in Sandholm, (2010)).

###  2.1 Relation to the replicator dynamics

The connection between the IBR dynamics and the replicator dynamics can be
established via the pairwise proportional imitation protocol (PPI) introduced
in Schlag, (1998). Under the PPI the revising agent observes one opponent from
the population at random and imitates that opponent’s strategy at a rate
proportional to its payoff advantage. Compared to the PPI rule based on
realized payoffs, the IBR rule suppresses any payoff differences, thus under
the IBR rule all conditional switch rates to strategies that exhibit higher
outcomes are the same, whereas under the PPI rule the switch rate is higher
the higher the outcome.

Under the PPI rule based on realized payoffs, an agent whose strategy $i$
yields payoff $\pi_{im}$ for some $m\in S$ switches to strategy $j$ if the
observed payoff realization $\pi_{jk}$ exceeds $\pi_{im}$, with a conditional
switch rate proportional to the payoff advantage of $j$, which is
$[\pi_{jk}-\pi_{im}]_{+}$. Accounting for the likelihood of each payoff
realization $\pi_{jk}$ one can express the switch rate from strategy $i$ to
strategy $j$ as

$\rho_{ij}(\mathbf{x},A)=x_{j}\sum_{k=1}^{n}x_{k}\sum_{m=1}^{n}x_{m}[\pi_{jk}-\pi_{im}]_{+}$

The PPI rule based on average payoffs generates the switch rates in the form

$\rho_{ij}(\mathbf{x},A)=x_{j}[\pi_{j}-\pi_{i}]_{+}$

where $x_{j}$ is the probability of sampling an agent whose strategy is $j$,
and the term $[\pi_{j}-\pi_{i}]_{+}$ is the (average) payoff advantage of
strategy $j$ over $i$. Due to linearity of average payoffs in strategy
utilization frequencies $x_{i}$, both kinds of proportional imitation generate
the replicator dynamics as their mean dynamics (Theorem 3 of Schlag, (1998)):

$\dot{x}_{i}=x_{i}\left(\pi_{i}-\bar{\pi}\right)$

The difference in the conditional switch rates under the IBR and the PPI rules
leads to a significant dissimilarity in the resulting mean dynamics. The rest
points of the replicator dynamics are the restricted equilibria of the
underlying game, so the average payoffs to all active strategies are the same
and the agents have no incentives to switch between them. The rest points of
the IBR dynamics, on the other hand, are “ordinal restricted equilibria” in
which the net flow for each strategy is zero. Yet it is possible that the
flows between the active strategies are positive at a rest point, and the
average payoffs to strategies need not be the same. Thus in general, the sets
of the rest points for the replicator and the IBR dynamics do not coincide.
However, as the following proposition states, when the cardinality of the set
of payoffs is low the IBR dynamics coincides with the replicator dynamics up
to a constant change of speed.

######  Proposition 1.

If the payoff matrix $A$ contains only two distinct payoffs, the IBR dynamics
reduces to the replicator dynamics up to a constant change of speed.

###### Proof.

Suppose WLOG that the set of payoffs is $\\{\pi_{ij}\\}=\\{0,k\\}$ for some
$k>0$. Then for any pair of strategy profiles involving the strategies $i$ and
$j$ the conditional switch rates from $i$ to $j$ under the IBR rule are
proportional to those under the PPI rule. For any
$i,j,k,m\in\\{1,2,\ldots,n\\}$ the following holds:

$[\pi_{jk}-\pi_{im}]_{+}=k\cdot\mathbf{1}_{\\{\pi_{jk}>\pi_{im}\\}},$

therefore $\rho_{ij}^{PPI}(\mathbf{x},A)=k\cdot\rho_{ij}^{IBR}(\mathbf{x},A)$,
so the IBR dynamics is the replicator dynamics scaled by $\frac{1}{k}$. ∎

The converse of Proposition 1 need not be true. Example 1 contains a game with
four distinct payoffs in which both protocols generate the same dynamics.

######  Example 1.

Consider the coordination game with the payoff matrix

$\left(\begin{tabular}[]{cc}4&1\\\ 3&2\end{tabular}\right)$

Both the IBR and the PPI protocols generate the same dynamics:
$\dot{x}=x(1-x)(2x-1)$. Under the PPI rule an agent with payoff $\pi_{22}=2$
who observes a candidate with payoff $\pi_{11}=4$ is twice as likely to switch
to strategy 1 than an agent with payoff $\pi_{21}=3$, but at the same time an
agent with payoff $\pi_{12}=1$ is twice as likely to switch to strategy 2 when
he or she observes a candidate with payoff $\pi_{21}=3$ rather than a
candidate with payoff $\pi_{22}=2$. These higher switch rates annihilate each
other, so in the end the flows between the strategies are identical to those
under the IBR rule, when all switch rates upon observing a better outcome are
the same. $\square$

Section 4.1 presents another example in which the two dynamics draw closer: in
the standard Rock-Paper-Scissors game the IBR dynamics can be obtained from
the replicator dynamics by a positive non-constant change of speed. But
Example 1 and the standard RPS game are an exception to the general rule.

###  2.2 Payoff monotonicity and payoff positivity

In this section it is shown that the IBR dynamics need not preserve such
cardinal properties as payoff monotonicity and payoff positivity. Payoff
monotonicity (Nachbar, (1990)) requires that the order of growth rates be the
same as the order of average payoffs (if $\pi_{i}>\pi_{j}$ then
$\frac{\dot{x_{i}}}{x_{i}}>\frac{\dot{x_{j}}}{x_{j}}$). Payoff positivity
(Nachbar, (1990)) is a weaker requirement that a strategy have a positive
growth rate if and only if its payoff is higher than the average payoff in the
population. Weak payoff positivity (Weibull, (1995)) is an even weaker
requirement that among the strategies with above-average payoffs there is one
with a positive growth rate. The next example demonstrates that all these
properties are violated for the IBR dynamics even in two-strategy games:

######  Example 2.

Consider the coordination game with the payoff matrix $A$

$A=\left(\begin{tabular}[]{cc}10&0\\\ 3&3\end{tabular}\right)$

Let $x$ be the frequency of the first (top) strategy in the population. The
mixed strategy equilibrium in game $A$ is $x^{*}=0.3$, and for all $x>x^{*}$
the average payoff of the first strategy is higher than that of the second
strategy. But the IBR dynamics for $A$ is

$\dot{x}=x(1-x)(2x-1),$

so for all $x<0.5$ the proportion of agents playing the first strategy is
decreasing. Thus, for instance, when $x=0.4$ $\pi_{1}=4>3=\pi_{2}$, but
$\dot{x}(0.4)<0$, and so the IBR dynamics is neither payoff monotone nor
payoff positive. $\square$

Depending on the payoffs, any state $x^{*}\in(0,1)$ can be the mixed Nash
equilibrium of the game which has the same order of payoffs as game $A$ from
the Example 2. Yet for all such games the IBR dynamics selects $x=0.5$ as the
rest point, so the monotonicity and positivity properties are violated
precisely at the states between $x^{*}$ and $0.5$.

When the population state is between $x^{*}$ and $0.5$, the first strategy
already has a higher average payoff yet the majority of agents playing it
receive the lowest payoff and thus would treat switching to the other strategy
as an improvement. The switches in the opposite direction are less likely
since the agents currently playing the second strategy would only imitate the
minority of strategy 1 agents who currently receive the overall highest
payoff. In the remainder of the state space the vector fields of the IBR
dynamics and the replicator dynamics point in the same direction. For this to
happen, a strategy with a higher average payoff needs to guarantee a better
payoff for a larger share of agents than the other strategy.

This intuition also paves the way for the next result: elimination of
dominated strategies. If strategy 1 dominates strategy 2, then at any interior
population state there will be a positive flow from 2 to 1, and the net inflow
from any other strategy would be higher for 1 than for 2. Together these
effects result in the ultimate extinction of strategy 2.

###  2.3 Elimination of dominated strategies

This section sharpens the results on elimination of dominated strategies for
imitative dynamics. As established by Nachbar, (1990) and Samuelson and Zhang,
(1992), “cardinal” imitative dynamics, including the replicator dynamics,
eliminate pure strategies (iteratively) dominated by other pure strategies due
to payoff monotonicity. The IBR dynamics, on the contrary, is a non-monotone
imitative dynamics which still eliminates such dominated strategies. In terms
of the comparison between the PPI and the IBR rules, this result means that
imitation alone can be sufficient for the elimination of dominated strategies.
In addition, Hofbauer and Sandholm, (2011) demonstrate that under most
dynamics not based on imitation dominated pure strategies can survive, in part
because the agents in a population setting may be unable to recognize
dominated strategies and thus avoid them. In the case of the IBR dynamics, the
available payoff information is also insufficient to identify dominated
strategies, and yet the agent switch away from them in the course of the play.

######  Proposition 2.

If a strategy is (iteratively) dominated by another pure strategy, then it is
eliminated along any interior solution of the IBR dynamics.

###### Proof.

Suppose that strategy $j$ is dominated by strategy $i$. Fix
$k\in\\{1,\ldots,n\\}$, by dominance $\pi_{ik}>\pi_{jk}$. Take a strategy
$p\neq i,j$ and consider all possible strategy profiles $(p,q)$ that might
arise in a match involving an agent playing this strategy. For a fixed
$q\in\\{1,\ldots,n\\}$ the payoff $\pi_{pq}$ would fall into one of these
three categories:

  1. 1.

$\pi_{pq}\leq\pi_{jk}<\pi_{ik}$, in which case there is an inflow into each
strategy: $(x_{p}x_{q}x_{k})x_{i}$ into strategy $i$ and
$(x_{p}x_{q}x_{k})x_{j}$ into $j$. Let $P_{k}x_{i}$ and $P_{k}x_{j}$ denote
the total flows in this case.

  2. 2.

$\pi_{jk}<\pi_{pq}\leq\pi_{ik}$, so there is outflow from strategy $j$ and
inflow into strategy $i$, with total flows expressed as some $Q_{k}x_{i}$ and
$Q_{k}x_{j}$.

  3. 3.

$\pi_{jk}<\pi_{ik}<\pi_{pq}$, so there is outflow from both strategies, with
total outflow expressed by $R_{k}x_{i}$ and $R_{k}x_{j}$.

In addition, there is net inflow $Tx_{i}x_{j}$ from strategy $j$ to $i$ which
includes at least the terms $x_{k}^{2}x_{i}x_{j}$.

In terms of these flow components the change in the population proportion for
the strategies $i$ and $j$ can be expressed as

$\displaystyle\dot{x}_{i}$
$\displaystyle=\sum_{k=1}^{n}\left(P_{k}x_{i}+Q_{k}x_{i}-R_{k}x_{i}\right)+Tx_{i}x_{j}$
$\displaystyle\dot{x}_{j}$
$\displaystyle=\sum_{k=1}^{n}\left(P_{k}x_{j}-Q_{k}x_{j}-R_{k}x_{j}\right)-Tx_{i}x_{j}$

and so the change in the difference $d$ in growth rates of the two strategies
is always positive:

$\dot{d}=\frac{\dot{x}_{i}}{x_{i}}-\frac{\dot{x}_{j}}{x_{j}}=2\sum_{k=1}^{n}Q_{k}+T(x_{i}+x_{j})>0$

Therefore, using the standard method (see, for instance, Proposition 1 in
Viossat, (2015)), $d\to+\infty$ as $t\to\infty$, and thus strategy $j$ is
eliminated.

In the restricted game in which strategy $j$ is eliminated, one can apply the
same reasoning to demonstrate that any strategy that becomes dominated will be
eliminated as well. Thus by continuity of the IBR dynamics in the neighborhood
of the edge opposite to the vertex $x_{j}=1$ in the original game (this edge
corresponds to the simplex of the restricted game) the dynamics will select
against the iteratively dominated strategies. See game $A_{2}$ in the example
3 for an illustration to this argument. ∎

With a slight adjustment ($\pi_{ik}>\pi_{jk}$ would hold for at least one $k$,
but not necessary all $k\in\\{1,\ldots,n\\}$) the argument can be applied to
weakly dominated strategies as well, but one should only consider weakly
dominated strategies after all strictly dominated strategies are eliminated.
Otherwise, a strategy that is weakly dominated only with respect to a strictly
dominated strategy may survive, as illustrated by game $A_{1}$ in the
following example.

######  Example 3.

Consider333The figures in this and other examples are generated in EvoDyn-3s.
See Izquierdo et al., (2018). the games $A_{1}$ and $A_{2}$

$A_{1}=\left(\begin{tabular}[]{ccc}1&1&2\\\ 1&1&1\\\ 0&0&0\end{tabular}\right)$ |  | $A_{2}=\left(\begin{tabular}[]{ccc}3&2&0\\\ 2&1&3\\\ 1&0&2\end{tabular}\right)$
---|---|---

|  |
---|---|---
Figure 1: Some solution trajectories in games $A_{1}$ (left) and $A_{2}$
(right).

In the game $A_{1}$ strategy 3 is dominated by both 1 and 2, strategy 2 is
weakly dominated by 1, but once strategy 3 is eliminated, both 1 and 2
coexist.

From the perspective of an agent playing strategy 3 the remaining two
strategies are equally good. The only case when strategy 1 gains advantage
over strategy 2 is when an agent playing strategy 2 gets to imitate someone
playing 1 against 3. The probability of observing such a candidate is
$x_{1}x_{3}$, so the switch rate from strategy 2 to strategy 1 is low near the
pure state $x_{3}=1$ and near the edge $x_{3}=0$. It is relatively high near
the center of the simplex where the expression $x_{1}x_{2}x_{3}$ is maximized.

In the game $A_{2}$ strategy 3 is dominated by strategy 2, and after strategy
3 is eliminated, strategy 2 is dominated by strategy 1. In this game the
solution trajectories originating near the pure state $x_{3}=1$ first move in
the direction of the pure state $x_{2}=1$, since when most agents choose
strategy 3 almost no one gets to imitate strategy 1 as the majority of
strategy 1 agents receive the lowest payoff. But after the population state
gets sufficiently close to $x_{2}=1$ and the strategy 3 becomes almost
extinct, agents begin to realize the advantage of 1 over 2. $\square$

Another example that complements the result of Proposition 2 demonstrates that
a strategy dominated by mixed strategies may survive.

######  Example 4.

Consider the games $A_{3}$ and $A_{4}$ with $\alpha\in(1,4)$:

$A_{3}=\left(\begin{tabular}[]{ccc}4&4&1\\\ $\alpha$&$\alpha$&$\alpha$\\\ 1&1&4\end{tabular}\right)$ |  | $A_{4}=\left(\begin{tabular}[]{ccc}1&1&4\\\ $\alpha$&$\alpha$&$\alpha$\\\ 4&4&1\end{tabular}\right)$
---|---|---

Compared to game $A_{3}$, the order of payoffs in game $A_{4}$ is reversed. In
both games strategy 2 is always the second best, and when $\alpha<2.5$, it is
dominated by a mixed strategy of 1 and 3.

The IBR dynamics in game $A_{3}$ is

$\displaystyle\dot{x}$ $\displaystyle=x(1-x)(1-2z)$ $\displaystyle\dot{y}$
$\displaystyle=y(z-x)(1-2z)$ $\displaystyle\dot{z}$
$\displaystyle=z(1-z)(2z-1)$

where $x,y$, and $z$ are the proportions of strategies 1, 2, and 3,
respectively. When exactly half of the population $(z=\frac{1}{2})$ chooses
strategy 3, strategy 2 can survive. In the game $A_{3}$, strategy 2 is
otherwise eliminated: strategy 1 is better than 2 when $z<\frac{1}{2}$, while
3 is better than 2 when $z>\frac{1}{2}$.

|  |
---|---|---
Figure 2: Some solution trajectories in games $A_{3}$ (left) and $A_{4}$
(right). The critical region is $z=\frac{1}{2}$.

In game $A_{4}$ with the reversed order of payoffs the critical region
$z=\frac{1}{2}$ becomes absorbing, which suggests that strategy 2 survives
along any trajectory originating in the interior of the state space.$\square$

###  2.4 Stability of strict equilibria

We conclude this section with a stability property for strict equilibria. If a
strategy $i$ is the unique best response to itself, then in the neighborhood
of a pure state $x_{i}=1$ any agent who currently employs a strategy $j\neq i$
would be most likely matched against an opponent playing strategy $i$, and
upon receiving a revision opportunity would most likely observe a candidate
earning $\pi_{ii}$ and as a consequence switch to $i$. The behavior of such
agents would create an inflow into the strategy $i$ which is of higher order
than any potential outflow caused by payoff advantages of other strategies
over $i$, so the proportion of agents playing $i$ would increase, making the
state $x_{i}=1$ a stable rest point.

######  Proposition 3.

Strict symmetric equilibria are locally stable with a basin of attraction that
includes all states with $x_{i}>1-\tfrac{1}{\sqrt{2}}$.

###### Proof.

Suppose that the strategy profile $(i,i)$ is a strict equilibrium. To show
that it is locally stable it is enough to demonstrate that $\dot{x}_{i}>0$ in
some neighborhood of the pure state $x_{i}=1$ as this implies that the
function $L(x)=x_{i}$ is a strict local Lyapunov function for the state
$x_{i}=1$. To do so, construct the lower bound on $\dot{x}_{i}$ by considering
a game with the lowest net inflow into the strategy $i$.

Let $x_{i}=1-\epsilon$. Since $(i,i)$ is a strict equilibrium, for any $j\neq
i$ we have $\pi_{ii}>\pi_{ji}$, so strategy $i$ would be imitated by any agent
who currently obtains $\pi_{ji}$ and who observes a candidate obtaining
$\pi_{ii}$. Such switches to strategy $i$ create an inflow of
$x_{i}^{3}\sum_{j\neq i}x_{j}=(1-\epsilon)^{3}\epsilon$, which is a lower
bound on the inflow into strategy $i$.

To obtain a lower bound on $\dot{x}_{i}$, assume that in all other cases
strategy $i$ performs worse than its alternatives, i.e. $\pi_{im}<\pi_{jk}$
for any $m\in S$ and $j,k\neq i$ and $\pi_{ik}<\pi_{ji}$ for any $j,k\neq i$.
In the former case the outflow from strategy $i$ is
$\sum_{m=1}^{n}x_{i}x_{m}\sum_{j,k\neq i}x_{j}x_{k}=(1-\epsilon)\epsilon^{2}$,
and in the latter it is $\sum_{k\neq i}x_{i}x_{k}\sum_{j\neq
i}x_{j}x_{i}=(1-\epsilon)^{2}\epsilon^{2}$. The sum of these two components is
the upper bound on the outflow from strategy $i$.

Subtracting the highest outflow from the lowest inflow yields the desired
lower bound:

$\displaystyle\dot{x}_{i}$
$\displaystyle=\sum_{j=1}^{n}x_{j}\rho_{ji}(\mathbf{x},A)-x_{i}\sum_{j=1}^{n}\rho_{ij}(\mathbf{x},A)$
$\displaystyle=x_{i}\sum_{j=1}^{n}x_{j}\sum_{k=1}^{n}x_{k}\sum_{m=1}^{n}x_{m}\mathbf{1}_{\\{\pi_{jk}<\pi_{im}\\}}-x_{i}\sum_{j=1}^{n}x_{j}\sum_{k=1}^{n}x_{k}\sum_{m=1}^{n}x_{m}\mathbf{1}_{\\{\pi_{jk}>\pi_{im}\\}}$
$\displaystyle\geq x_{i}^{3}\sum_{j\neq
i}x_{j}\mathbf{1}_{\\{\pi_{ji}<\pi_{ii}\\}}-x_{i}\sum_{m=1}^{n}x_{m}\sum_{j,k\neq
i}x_{j}x_{k}\mathbf{1}_{\\{\pi_{jk}>\pi_{im}\\}}-x_{i}^{2}\sum_{k\neq
i}x_{k}\sum_{j\neq i}x_{j}\mathbf{1}_{\\{\pi_{ik}<\pi_{ji}\\}}$
$\displaystyle\geq(1-\epsilon)^{3}\epsilon-(1-\epsilon)\epsilon^{2}-(1-\epsilon)^{2}\epsilon^{2}$
$\displaystyle\geq\epsilon(1-\epsilon)\left(1-4\epsilon+2\epsilon^{2}\right)$
$\displaystyle\geq 0\text{ when }\epsilon<1-\tfrac{1}{\sqrt{2}}.$

Thus whenever $\epsilon<1-\tfrac{1}{\sqrt{2}}$ the trajectory from an initial
condition with $x_{i}=1-\epsilon$ converges to $x_{i}=1$, so any strict
symmetric equilibrium is locally stable. ∎

##  3 Two-strategy games

In this section we completely characterize the behavior of the IBR dynamics
for two-strategy games. This topic was first studied in Izquierdo and
Izquierdo, (2013), in which the dynamics is used to approximate the behavior
of a finite population of agents who employ the IBR rule in the Hawk-Dove
game. Izquierdo and Izquierdo, (2013) also derive the general IBR equation for
two-strategy games. Our paper complements their findings by identifying all
possible rest points of the dynamics, and by demonstrating its equivalence to
the replicator dynamics in terms of the number of rest points and the local
behavior around them.

For two-strategy games with two distinct payoffs the IBR dynamics and the
replicator dynamics coincide. The table below presents all possible cases with
3 or 4 distinct payoffs, grouped by the game type: D – game with a dominant
strategy, W – game with a weakly dominant strategy, C – coordination game, A –
anticoordination game.

$D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$
---|---|---|---|---|---
$\left(\begin{tabular}[]{cc}4&3\\\ 2&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}4&3\\\ 1&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}4&2\\\ 3&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&4\\\ 2&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&4\\\ 1&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}2&4\\\ 1&3\end{tabular}\right)$
$D_{7}$ | $D_{8}$ | $D_{9}$ | $D_{10}$ | $D_{11}$ | $D_{12}$
$\left(\begin{tabular}[]{cc}3&3\\\ 2&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&3\\\ 1&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&2\\\ 2&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}2&3\\\ 1&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&2\\\ 1&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}2&3\\\ 1&1\end{tabular}\right)$
$W_{1}$ | $W_{2}$ | $W_{3}$ | $W_{4}$ | $W_{5}$ | $W_{6}$
$\left(\begin{tabular}[]{cc}3&2\\\ 3&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}2&3\\\ 1&3\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&2\\\ 1&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}2&3\\\ 2&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&1\\\ 2&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}1&3\\\ 1&2\end{tabular}\right)$
$C_{1}$ | $C_{2}$ | $C_{3}$ | $C_{4}$ | $C_{5}$ | $C_{6}$
$\left(\begin{tabular}[]{cc}4&2\\\ 1&3\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}4&1\\\ 3&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}4&1\\\ 2&3\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&2\\\ 1&3\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&1\\\ 2&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}3&1\\\ 1&2\end{tabular}\right)$
$A_{1}$ | $A_{2}$ | $A_{3}$ | $A_{4}$ | $A_{5}$ | $A_{6}$
$\left(\begin{tabular}[]{cc}2&4\\\ 3&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}1&4\\\ 3&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}1&4\\\ 2&3\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}2&3\\\ 3&1\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}1&3\\\ 2&2\end{tabular}\right)$ | $\left(\begin{tabular}[]{cc}1&3\\\ 2&1\end{tabular}\right)$

Table 1: types of two-strategy games with 3 or 4 distinct payoffs

In games with a (weakly) dominant strategy the set of rest points is
$\\{0,1\\}$, and trajectories from any interior state converge to state $x=1$.

types | mean dynamics
---|---
$D_{1},D_{2},D_{4},D_{5},D_{7},D_{8},D_{11},D_{12}$ | $\dot{x}=x(1-x)$
$D_{3},D_{6}$ | $\dot{x}=x(1-x)[x^{2}+(1-x)^{2}]$
$D_{9}$ | $\dot{x}=x(1-x)[x+(1-x)^{2}]$
$D_{10}$ | $\dot{x}=x(1-x)[x^{2}+(1-x)]$
$W_{1},W_{6}$ | $\dot{x}=x(1-x)^{3}$
$W_{2},W_{5}$ | $\dot{x}=x^{3}(1-x)$
$W_{3}$ | $\dot{x}=x^{2}(1-x)(1+x)$
$W_{4}$ | $\dot{x}=x(1-x)^{2}(1+x)$

Table 2: the mean dynamics for the games with (weakly) dominant strategies

In coordination games the set of rest points is
$\\{0,1-\frac{\sqrt{2}}{2},\frac{3-\sqrt{5}}{2},\frac{1}{2},1\\}$. The
interior rest points are repelling, and trajectories from the interior states
converge to the boundary states.

types | mean dynamics | interior RP
---|---|---
$C_{1}$ | $\dot{x}=x(1-x)[-2x^{2}+4x-1]$ | $x=1-\frac{\sqrt{2}}{2}\approx 0.293$
$C_{2},C_{3},C_{5}$ | $\dot{x}=x(1-x)[2x-1]$ | $x=\frac{1}{2}$
$C_{4},C_{6}$ | $\dot{x}=x(1-x)[-x^{2}+3x-1]$ | $x=\frac{3-\sqrt{5}}{2}\approx 0.382$

Table 3: the mean dynamics for coordination games

In anticoordination games the set of rest points is
$\\{0,\frac{1}{2},\frac{\sqrt{5}-1}{2},\frac{1}{\sqrt{2}},1\\}$. Essentially,
the rest points in coordination and anticoordination games are the same save
for the order of the strategies. The trajectories from the interior states
converge to the interior rest point.

types | mean dynamics | interior RP
---|---|---
$A_{1}$ | $\dot{x}=x(1-x)[1-2x^{2}]$ | $x=\frac{1}{\sqrt{2}}\approx 0.707$
$A_{2},A_{3},A_{5}$ | $\dot{x}=x(1-x)[1-2x]$ | $x=\frac{1}{2}$
$A_{4},A_{6}$ | $\dot{x}=x(1-x)[-x^{2}-x+1]$ | $x=\frac{\sqrt{5}-1}{2}\approx 0.618$

Table 4: the mean dynamics for anticoordination games

Thus, the IBR dynamics exhibits the same properties as the replicator
dynamics: in games with a dominant strategy both dynamics select it; in
coordination games trajectories from the interior converge to one of the two
pure states, while in anticoordination games trajectories converge to the
interior rest point.

As a corollary, this characterization also describes the behavior of the IBR
dynamics on the boundary of the state space in a three-strategy game, since
once one of the three strategies becomes extinct it is never reintroduced.
Thus each boundary of the two-dimensional simplex can only have at most one
rest point, unless the whole boundary is the rest area (which is possible in
degenerate cases). Besides, this characterization shows that the interior rest
points of the dynamics can only take one of the five possible values, and
suggests that similar sets of rest points can be identified for games with
more strategies.

##  4 Rock-Paper-Scissors games

###  4.1 Symmetric RPS games

First consider the symmetric RPS game with the payoff matrix $A$ and $a,b>0$.

$A=\left(\begin{tabular}[]{ccc}0&$-a$&$b$\\\ $b$&0&$-a$\\\
$-a$&$b$&0\end{tabular}\right)$

For any values of the payoff parameters the game $A$ induces the same order of
payoffs as the standard RPS game, for which the replicator dynamics is

$\displaystyle\dot{x}$ $\displaystyle=x(z-y),$ $\displaystyle\dot{y}$
$\displaystyle=y(x-z),$ $\displaystyle\dot{z}$ $\displaystyle=z(y-x),$

where $x$, $y$, and $z$ are the shares of agents playing Rock, Paper, and
Scissors, respectively.

The mean dynamics in game $A$ generated by the IBR protocol is

$\displaystyle\dot{x}$ $\displaystyle=x(z-y)(1-xy-xz-yz),$
$\displaystyle\dot{y}$ $\displaystyle=y(x-z)(1-xy-xz-yz),$
$\displaystyle\dot{z}$ $\displaystyle=z(y-x)(1-xy-xz-yz)$

Thus in the standard RPS game the IBR dynamics is the replicator dynamics with
speed adjusted by the positive non-constant function $(1-xy-xz-yz)$. This
relationship helps identify the global behavior of the IBR dynamics in
symmetric RPS games.

######  Proposition 4.

In all symmetric RPS games the trajectories under the IBR dynamics are closed
orbits around the unique interior rest point
$(\frac{1}{3},\frac{1}{3},\frac{1}{3})$.

###### Proof.

Clearly, the only interior solution to the system (RPS) is
$x^{*}=y^{*}=z^{*}=\frac{1}{3}$.

Since the IBR dynamics is the speed-adjusted replicator dynamics for this
game, the Lyapunov function
$H(\mathbf{x})=x^{*}\log\frac{x}{x^{*}}+y^{*}\log\frac{y}{y^{*}}+z^{*}\log\frac{z}{z^{*}}$
(introduced in Theorem 6 in Zeeman, (1980)) would be constant along the
solutions of the IBR dynamics for all symmetric RPS games. ∎

Intuitively, in the standard RPS game the average payoff to a strategy (the
information about the candidate strategy that a player receives under the
proportional imitation rule based on the average payoffs) is equivalent to
learning about the difference in shares of winners and losers under that
strategy. So the average payoff under the PPI rule is higher whenever the
likelihood of switching under the IBR rule is higher.

###  4.2 Ordered RPS games

In general under the replicator dynamics the behavior of the system in the
Rock-Paper-Scissors game solely depends on the determinant of the payoff
matrix $A$. If $\det A=0$, the solution trajectories form closed orbits around
the interior steady state. If $\det A>0$, the interior steady state is a
global attractor, whereas if $\det A<0$ it is repelling (Zeeman, (1980)).

Under the IBR dynamics we conjecture444We provide the proof of that statement
for the closed orbits case, and state it as a conjecture for the remaining two
cases based on simulations. that the global behavior of the system can be one
of the same three types: either all solutions converge to the interior steady
state, or form closed orbits around it, or converge to the boundary. The
difference is, the behavior depends on the order of payoffs, so for a fixed
RPS game one can have any combination of behaviors under the replicator and
the IBR dynamics.

In Table 5 we consider the nine possible orderings over the payoffs in the RPS
game. In all cases Rock yields the highest positive payoff.

$A_{1}=\left(\begin{tabular}[]{ccc}0&-3&3\\\ 2&0&-2\\\ -1&1&0\end{tabular}\right)$ | $A_{2}=\left(\begin{tabular}[]{ccc}0&-2&3\\\ 2&0&-1\\\ -3&1&0\end{tabular}\right)$ | $A_{3}=\left(\begin{tabular}[]{ccc}0&-1&3\\\ 2&0&-3\\\ -2&1&0\end{tabular}\right)$
---|---|---
$B_{1}=\left(\begin{tabular}[]{ccc}0&-3&3\\\ 1&0&-1\\\ -2&2&0\end{tabular}\right)$ | $B_{2}=\left(\begin{tabular}[]{ccc}0&-1&3\\\ 1&0&-2\\\ -3&2&0\end{tabular}\right)$ | $B_{3}=\left(\begin{tabular}[]{ccc}0&-2&3\\\ 1&0&-3\\\ -1&2&0\end{tabular}\right)$
$C_{1}=\left(\begin{tabular}[]{ccc}0&-1&3\\\ 2&0&-2\\\ -3&1&0\end{tabular}\right)$ | $C_{2}=\left(\begin{tabular}[]{ccc}0&-3&3\\\ 2&0&-1\\\ -2&1&0\end{tabular}\right)$ | $C_{3}=\left(\begin{tabular}[]{ccc}0&-2&3\\\ 2&0&-3\\\ -1&1&0\end{tabular}\right)$

Table 5: The interior steady state is repelling in A1-A3, an attractor in
B1-B3, and a center in C1-C3.

Each B game is obtained from an A game with the same index by reversing the
order of payoffs and subsequently relabelling the strategies. This procedure
reverses the flows along the solution trajectories, so the repelling rest
points in games of type A become attractors in games of type B. The next
proposition states this result formally.

|  |
---|---|---
Figure 3: Some solution trajectories for games A1, B3, and C2.

######  Proposition 5.

i) The unique interior rest point in any A game is repelling.
ii) For any $i\in\\{1,2,3\\}$ the game $B_{i}$ can be obtained from the game
$(-A_{i})$ by relabeling the strategies.

###### Proof.

i) The statement is proved for the game $A_{1}$ by direct computation. The
proofs for games $A_{2}$ and $A_{3}$ are similar.

The IBR dynamics in game $A_{1}$ can be written as

$\displaystyle F(x,y,z)=\left(\begin{matrix}\dot{x}\\\ \dot{y}\\\
\dot{z}\end{matrix}\right)=\left(\begin{matrix}x(z-y)(x^{2}+y+z)\\\
y(x-z)(x^{2}+y+z)+yz(y-x)(x+z)\\\
z(y-x)(x^{2}+y+z)-yz(y-x)(x+z)\end{matrix}\right)$

To identify the interior rest points notice that $\dot{x}=0$ requires $y=z$,
in which case $\dot{y}=0$ reduces to

$\displaystyle(x-y)\left(x^{2}+2y-y(x+y)\right)=0.$

Plugging in $x=1-2y$ results in the equation

$\displaystyle(1-3y)\left(5y^{2}-3y+1\right)=0,$

with the only real solution $y=\frac{1}{3}$. Thus the unique interior rest
point of the system $F$ is $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$.

To identify the local behavior of the system $F$ around the interior steady
state, project it from $\mathbb{R}^{3}$ onto $\Delta_{3}$, the two-dimensional
simplex, to obtain the system

$\displaystyle\hat{F}(x,y)=\left(\begin{matrix}x(1-x-2y)(x^{2}-x+1)\\\
y(2x+y-1)(y^{2}-y+1)+2xy(y-x)(1-x-y)\end{matrix}\right)$

The Jacobian of this system evaluated at the rest point
$(\frac{1}{3},\frac{1}{3})$ is

$\displaystyle
D\hat{F}\left(\frac{1}{3},\frac{1}{3}\right)=\frac{1}{27}\left(\begin{matrix}-7&-14\\\
12&9\end{matrix}\right)$

with the eigenvalues $\frac{1\pm 2i\sqrt{26}}{27}$. Since both eigenvalues
have positive real parts the rest point is repelling.
ii) To see the relationship between $A_{1}$ and $B_{1}$, write the matrices
$A_{1},-A_{1}$, and $B_{1}$ side by side:

$A_{1}=\left(\begin{tabular}[]{ccc}0&-3&3\\\ 2&0&-2\\\ -1&1&0\end{tabular}\right)$ | $-A_{1}=\left(\begin{tabular}[]{ccc}0&3&-3\\\ -2&0&2\\\ 1&-1&0\end{tabular}\right)$ | $B_{1}=\left(\begin{tabular}[]{ccc}0&-3&3\\\ 1&0&-1\\\ -2&2&0\end{tabular}\right)$
---|---|---

The game $B_{1}$ can be obtained from $(-A_{1})$ by relabeling strategies 2
and 3. Formally the IBR dynamics in game $B_{1}$ can be written as

$\displaystyle G(x,y,z)=\left(\begin{matrix}\dot{x}\\\ \dot{y}\\\
\dot{z}\end{matrix}\right)=\left(\begin{matrix}x(z-y)(x^{2}+y+z)\\\
y(x-z)(x^{2}+y+z)-yz(x-z)(x+y)\\\
z(y-x)(x^{2}+y+z)+yz(x-z)(x+y)\end{matrix}\right)$

so $-F(x,y,z)=G(x,z,y)$. Thus the system $G$ is the time-reversed system $F$,
so the eigenvalues of the Jacobian evaluated at the interior rest point of
$\hat{G}$ both have negative real parts, and that rest point is an attractor.
∎

Games of type $C$ require a different approach, since in them the eigenvalues
of the Jacobian at the interior rest point are purely imaginary, so the local
stability analysis using the Jacobian does not produce an unambiguous result.
However, this obstacle can be overcome once one notices that up to the
strategy labels, reversing the order in any C game results in the same game.

######  Proposition 6.

The unique interior rest point in any C game is a center, and any trajectory
from the interior forms a closed orbit around it.

###### Proof.

The proposition is proved for the game $C_{2}$. The proof for games $C_{1}$
and $C_{3}$ is similar.

Observe that the negative of the game $C_{2}$ is $C_{2}$ with strategies 2 and
3 interchanged.

$C_{2}=\left(\begin{tabular}[]{ccc}0&-3&3\\\ 2&0&-1\\\ -2&1&0\end{tabular}\right)$ |  | $-C_{2}=\left(\begin{tabular}[]{ccc}0&3&-3\\\ -2&0&1\\\ 2&-1&0\end{tabular}\right)$
---|---|---

Formally, the IBR dynamics in $C_{2}$

$\displaystyle H(x,y,z)=\left(\begin{matrix}\dot{x}\\\ \dot{y}\\\
\dot{z}\end{matrix}\right)=\left(\begin{matrix}x(z-y)(x^{2}+y+z)\\\
y(x-z)(x^{2}+y+z)-yz(x^{2}-xy-xz-yz)\\\ z(y-x)(x^{2}+y+z)+yz(x^{2}-xy-xz-
yz)\end{matrix}\right)$

has the property $-H(x,y,z)=H(x,z,y)$.

To identify the interior rest points of the system $H$ observe that
$\dot{x}=0$ requires $z=y$, so that $x=1-y-z=1-2y$. Plugging the expressions
for $x$ and $z$ into $\dot{y}=0$ yields the equation

$1-6y+16y^{2}-19y^{3}=0,$

which only has one root $y\approx 0.374$ in the interval $[0,1]$. Thus
$\mathbf{x^{*}}\approx(0.252,0.374,0.374)$ is the unique interior rest point
of the system $H$.

To show that the solution trajectories originating in the interior of the
simplex form closed orbits around the rest point $\mathbf{x^{*}}$, we first
show that any such solution circles around $\mathbf{x^{*}}$ and then apply the
“self-negating” property to conclude that any circular solution trajectory
must be indeed a closed orbit.

Figure 4: Left: the nullclines divide the simplex into 6 regions. Right:
solution trajectories from the marked points have to remain within the red
areas.

Observe that the x-nullcline is the x-bisector, while the y-nullcline and
z-nullcline originate at states $y=1$ and $z=1$, respectively, pass through
the interior rest point $\mathbf{x^{*}}$ and hit the opposite edges of the
simplex. Together the nullclines divide the simplex into six regions: $x$ is
decreasing in regions 1, 2, and 3, and increasing in regions 4, 5, and 6; $y$
is decreasing in 3, 4, and 5, and increasing in 6, 1, and 2; $z$ is decreasing
in regions 5, 6, and 1, and increasing in regions 2, 3, and 4.

Given the signs of the nullclines, the possible directions of motion in each
of the six regions are restricted to a particular 60-degree wedge. For
instance, in region 1, $x$ and $z$ must be decreasing, while $y$ is
increasing, so a solution originating from a point inside region 1 can only
move toward the boundary $z=0$ or the nullcline $\dot{z}=0$. But as the
solution gets closer to the boundary, the speed $\dot{z}$ approaches 0, while
the speeds $\dot{x}$ and $\dot{y}$ are bounded away from 0 within the red area
that restricts the feasible directions of motion (Formally, as $z\rightarrow
0$, $\dot{x}\rightarrow-xy(x^{2}+y)$; $\dot{y}\rightarrow xy(x^{2}+y)$;
$\dot{z}\rightarrow 0$, so near the edge $z=0$ the direction of motion is
almost parallel to the edge.) Thus a solution originating inside region 1 has
to exit it via the z-nullcline. Similarly, the solutions originating in
regions 3 and 5 have to escape them via the x- and the y-nullclines,
correspondingly.

Solutions originating in region 2 cannot reach the boundary as $z$ must be
increasing. But it is not immediately obvious that they cannot hit the rest
point $\mathbf{x^{*}}$. To exclude this possibility, one has to show that the
y-component of every point in the region 2 is at least as high as the
y-component of $\mathbf{x^{*}}$, so that $\mathbf{x^{*}}$ can not be reached
as $y$ must be increasing. This will be the case if the slope of the
z-nullcline at $\mathbf{x^{*}}$ is not lower than the slope of the line
$y=const$. To compute that slope, simplify the system $H$ to

$\displaystyle H(x,y,z)=\left(\begin{matrix}\dot{x}\\\ \dot{y}\\\
\dot{z}\end{matrix}\right)=\left(\begin{matrix}x(z-y)(x^{2}+y+z)\\\
y(x-z)(x^{2}+y+z^{2})+2xy^{2}z\\\
z(y-x)(x^{2}+y^{2}+z)-2xyz^{2}\end{matrix}\right)$

so that the equation for the z-nullcline becomes
$(y-x)(x^{2}+y^{2}+z)-2xyz=0$. Using $z=1-x-y$, apply the Implicit Function
Theorem to compute the slope of the z-nullcline:

$\displaystyle\frac{dy}{dx}=\frac{x^{2}+y^{2}+z-(y-x)(2x-1)+2yz-2xy}{x^{2}+y^{2}+z+(y-x)(2y-1)-2xz+2xy}$

The rest point $\mathbf{x^{*}}$ is characterized by $z=y$ and $x=1-2y$, so the
slope of the z-nullcline at $\mathbf{x^{*}}$ can be expressed solely in terms
of $y$:

$\displaystyle\frac{dy}{dx}|_{\mathbf{x}=\mathbf{x^{*}}}$
$\displaystyle=\frac{(1-2y)^{2}+y^{2}+y-(3y-1)(1-4y)+2y^{2}-2y(1-2y)}{(1-2y)^{2}+y^{2}+y+(3y-1)(2y-1)}$
$\displaystyle=\frac{23y^{2}-12y+2}{11y^{2}-8y+2}>0$

Thus at the rest point $\mathbf{x^{*}}$ the z-nullcline has a positive slope,
whereas the slope of the line $y=const$ is 0 (in standard coordinates).
Therefore at any point in the interior of region 2, $y>y(\mathbf{x^{*}})$, and
the trajectories originating in that region have to escape it via the
y-nullcline.

Similarly, in region 4 the slope of the x-nullcline $z-y=0$ equal to
$-\tfrac{1}{2}$ exceeds the slope of the line $z=const$ equal to $-1$, and in
the region 6 the slope of the y-nullcline $(x-z)(x^{2}+y+z^{2})+2xyz=0$ is

$\displaystyle\frac{dy}{dx}=-2\frac{x^{2}+y+z^{2}+(x-z)^{2}+2yz-2xy}{x^{2}+y+z^{2}+(x-z)(1-2z)+2xz-2xy}$

so that at $\mathbf{x^{*}}$ it becomes

$\displaystyle\frac{dy}{dx}|_{\mathbf{x}=\mathbf{x^{*}}}$
$\displaystyle=-2\frac{17y^{2}-10y+2}{11y^{2}-8y+2}<0$

whereas the line $x=const$ is vertical. Hence the trajectories originating in
both regions 4 and 6 have to escape them via the nullclines. Therefore the
solution trajectory from any interior initial condition circles around the
interior rest point $\mathbf{x^{*}}$ by sequentially entering and exiting each
of the six regions via the nullclines.

Figure 5: The solution trajectory from $\mathbf{x_{0}}$ (blue) and the time-
reversed solution trajectory from $\mathbf{x_{0}}$ (red).

The final step of the proof is to show that every solution trajectory is a
closed orbit. Since all trajectories circle around $\mathbf{x^{*}}$, it
suffices to consider a solution originating at some point $\mathbf{x_{0}}$ on
the x-bisector between the rest point $\mathbf{x^{*}}$ and the state $x=1$.
Suppose that once this solution completes a loop around the rest point, it
hits the x-bisector again at some point $\mathbf{x_{1}}$, whereas if one were
to reverse the flow it would hit the bisector at a point $\mathbf{x_{-1}}$.
The “self-negating” property of $C_{2}$ implies that the mirror image of the
phase portrait of the negative of $C_{2}$ is the phase portrait of $C_{2}$
(the x-bisector being the axis of symmetry). In particular, the mirror image
of the segment of the solution trajectory between $\mathbf{x_{-1}}$ and
$\mathbf{x_{0}}$ has to be the segment between $\mathbf{x_{0}}$ and
$\mathbf{x_{1}}$. Therefore $\mathbf{x_{-1}}=\mathbf{x_{1}}$, but that is only
possible if $\mathbf{x_{-1}}=\mathbf{x_{0}}=\mathbf{x_{1}}$, as otherwise
$\mathbf{x_{-1}}$ and $\mathbf{x_{1}}$ must be on the opposite sides of
$\mathbf{x_{0}}$. Therefore all solution trajectories must form closed orbits
around $\mathbf{x^{*}}$. ∎

The Proposition 6 suggests that if a three-strategy game has the “self-
negating” property, the solution trajectories and the time-reversed solution
trajectories “meet”, which implies that the trajectories form closed orbits
around an interior steady state. This observation provides a link between
self-negating games under the IBR dynamics and zero-sum games under the
replicator dynamics. In a zero-sum game with an interior equilibrium, every
interior solution trajectory is confined to a level set of a Kullback-Leibler
divergence function (see Sec. 9.1.1 of Sandholm, (2010)). This means the rest
point is Lyapunov stable but not asymptotically stable, and that other
interior solution trajectories do not converge. The latter need not be the
case under the IBR dynamics: game $W$ in Example 5 is a self-negating game, in
which some interior solution trajectories form closed orbits, while others
converge to a pure rest point.

In games with more than three strategies one might not get as much mileage out
of self-negation. With only three strategies, the self-negating property
implies an axisymmetric phase portrait, since there must be a pair of
strategies that is relabeled when the order of payoffs is reversed. With four
or more strategies it is possible that more than one pair of strategies are
relabeled, and it is not entirely clear what this possibility implies.

##  5 Other examples

In this section we provide two more examples that relate the IBR and the
replicator dynamics. First, we show that the game from the example 1 of Zeeman
(1980) admits two interior rest points under the IBR dynamics. Such behavior
is impossible under the replicator dynamics, under which in non-degenerate
games there can be at most one interior rest point (Theorem 3 in Zeeman,
(1980)). Second, we construct a self-negating game in which the interior is
split into two regions, one containing closed orbits around the interior rest
point, and the other being a basin of attraction for a pure rest point. Up to
the position of the rest point, both dynamics are equivalent.

######  Example 5.

Consider the games $Z$ and $W$:

$Z=\left(\begin{tabular}[]{ccc}0&6&-4\\\ -3&0&5\\\ -1&3&0\end{tabular}\right)$ |  | $W=\left(\begin{tabular}[]{ccc}0&4&3\\\ 1&3&5\\\ 3&2&6\end{tabular}\right)$
---|---|---

Game $Z$ is the game from the Example 1 in Zeeman, (1980). The IBR dynamics in
it

$\displaystyle\dot{x}$ $\displaystyle=x(1-x)\left(x^{2}+y-z\right)-2x^{2}yz$
$\displaystyle\dot{y}$ $\displaystyle=-y(1-y)\left(x+y^{2}-z\right)+2x^{2}yz$
$\displaystyle\dot{z}$ $\displaystyle=z(x-y)\left(z-x^{2}-y^{2}\right)$

yields two distinct interior rest points
$\mathbf{z_{1}}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ and
$\mathbf{z_{2}}\approx(0.575,0.088,0.338)$. At $\mathbf{z_{1}}$ the relevant
eigenvalues are $\tfrac{1}{27}\left(-1\pm 2i\sqrt{5}\right)$, so this rest
point is stable, whereas at $\mathbf{z_{2}}$ the eigenvalues are 0.41 and
-0.041, so it is unstable.

|  |
---|---|---
Figure 6: Some solution trajectories in games $Z$ (left) and $W$ (right).

Game $W$ has the self-negating property, so there are closed orbits around the
interior rest point, but a part of the interior of the simplex is the basin of
attraction of the state $x_{3}=1$. In the time-reversed game $x_{1}=1$ becomes
the attractor, while the interior rest point preserves its region with the
closed orbits.

##  6 Conclusion

This paper investigated the properties of an imitative rule that ignores any
cardinal information about the game’s payoffs. Agents switch to strategies
which they perceive as better based on the comparison of their realized
payoffs to that of a random member of the population. Since this behavioral
rule bears a similarity to the pairwise proportional imitation of Schlag,
(1998), the resulting ordinal imitative dynamics begs comparison with the
replicator dynamics arising from the PPI.

We demonstrate that while the IBR dynamics does not possess the payoff
monotonicity and Nash stationarity properties of the replicator dynamics in
general, the two dynamics are topologically equivalent in two-strategy games.
We also conjecture that they generate the same types of behavior in Rock-
Paper-Scissors games. In other cases, the IBR dynamics can generate behavior
that is impossible under the replicator dynamics.

Better understanding the relationship between the two dynamics and
investigating the self-negating property in games with more than three
strategies would be the two most important directions for future research.

## References

  * Benaïm and Weibull, (2003) Benaïm, M. and Weibull, J. W. (2003).  Deterministic approximation of stochastic evolution in games.  Econometrica, 71:873–903.
  * Björnerstedt and Weibull, (1996) Björnerstedt, J. and Weibull, J. W. (1996).  Nash equilibrium and evolution by imitation.  In Arrow, K. J. et al., editors, The Rational Foundations of Economic Behavior, pages 155–181. St. Martin’s Press, New York.
  * Helbing, (1992) Helbing, D. (1992).  A mathematical model for behavioral changes by pair interactions.  In Haag, G., Mueller, U., and Troitzsch, K. G., editors, Economic Evolution and Demographic Change: Formal Models in Social Sciences, pages 330–348. Springer, Berlin.
  * Hofbauer, (1995) Hofbauer, J. (1995).  Imitation dynamics for games.  Unpublished manuscript, University of Vienna.
  * Hofbauer and Sandholm, (2011) Hofbauer, J. and Sandholm, W. H. (2011).  Survival of dominated strategies under evolutionary dynamics.  Theoretical Economics, 6:341–377.
  * Izquierdo et al., (2018) Izquierdo, L. R., Izquierdo, S. S., and Sandholm, W. H. (2018).  Evodyn-3s: A mathematica computable document to analyse evolutionary dynamics in 3-strategy games.  Unpublished manuscript.
  * Izquierdo and Izquierdo, (2013) Izquierdo, S. S. and Izquierdo, L. R. (2013).  Stochastic approximation to understand simple simulation models.  Journal of Statistical Physics, 151(1):254–276.
  * Nachbar, (1990) Nachbar, J. H. (1990).  ’Evolutionary’ selection dynamics in games: Convergence and limit properties.  International Journal of Game Theory, 19:59–89.
  * Samuelson and Zhang, (1992) Samuelson, L. and Zhang, J. (1992).  Evolutionary stability in asymmetric games.  Journal of Economic Theory, 57:363–391.
  * Sandholm, (2010) Sandholm, W. H. (2010).  Population Games and Evolutionary Dynamics.  Cambridge: MIT Press.
  * Schlag, (1998) Schlag, K. H. (1998).  Why imitate, and if so, how? A boundedly rational approach to multi-armed bandits.  Journal of Economic Theory, 78:130–156.
  * Viossat, (2015) Viossat, Y. (2015).  Evolutionary dynamics and dominated strategies.  Economic Theory Bulletin, 3:91––113.
  * Weibull, (1995) Weibull, J. W. (1995).  Evolutionary Game Theory.  MIT Press, Cambridge.
  * Zeeman, (1980) Zeeman, E. C. (1980).  Population dynamics from game theory.  In Nitecki, Z. and Robinson, C., editors, Global Theory of Dynamical Systems, pages 471–497, Berlin, Heidelberg. Springer Berlin Heidelberg.