Fixed points in mortal population games

post by ViktoriaMalyasova · 2023-03-14T07:10:11.571Z · LW · GW · 0 comments

This is a link post for https://www.lesswrong.com/posts/dPmmuaz9szk26BkmD/vanessa-kosoy-s-shortform?commentId=2y7Zt2x4dJEFihxNs

Contents

  Definition (distance between histories)
  Definition (distance between measures)
  Definition.
  Lemma.
  Proof.
  Proposition
  Proof
  Lemma
  Proof
  Theorem
  Proof
  Proposition 
  Proof  
None
No comments

I wrote this post during the first part of the SERI MATS winter school, in Vanessa Kosoy's research stream. This is just an explanation of my intended research direction and the motivation behind it, and write down proofs for the statements in Vanessa's comment [LW(p) · GW(p)] describing the research direction.

The motivation behind infra-Bayesianism is to develop a better theory of intelligence.

Why do we need a theory of intelligence? When we build superhuman AIs, we can have two kinds of reasons to believe in their safety:
- empirical evidence coming from experiments with less capable AIs;
- mathematically proven guarantees of its performance.

Empirical evidence on its own may be unreliable, because, as the system capabilities improve, results may fail to generalize as we expected. We need a theory to give us performance guarantees and tell us how to correctly extrapolate observed results to new conditions.

Why do we need a better theory? The ideal Bayesian agent, known as AIXI, has several shortcomings, and one of them is realizability assumption. In order for a Bayesian agent to have performance guarantees: the true hypothesis must have a positive probability in the agent's prior. However, this is unachievable in the real world, because the agent is contained in the environment, and so trying to have a true hypothesis about the environment runs into self-reference problems and computational constraints.

A related problem in game theory is the grain-of-truth problem. The term comes from the paper by Ehud Kalai and Ehud Lehrer [1], in which they prove that in an infinitely repeated game, subjectively rational players - i.e. players maximizing their expected reward according to their subjective beliefs about what strategies the opponent is likely to play - will learn to predict their opponents' moves and their strategies will converge to Nash equilibrium strategies, provided that the "grain of truth" requirement is met: each player must assign a positive prior probability to any set of histories that has a positive chance of occurringk in the game.

Unfortunately, the "grain of truth" requirement is very strict, and when it's not met, learning fails. Foster and Young [2] prove that in a repeated 2-player game with uncertain payoff, rational agents will fail to learn each other's strategies and fail to converge to a Nash equilibrium, except for a set of games of measure 0. John H Nachbar [3] demonstrates that, loosely speaking, for any sufficiently rich set of strategies, it is impossible for each player to both predict their opponent's strategy and have their own strategy be the best response to their beliefs about their opponent at the same time.

Infra-Bayesianism is a possible solution to the "grain of truth problem", as it allows agents to have partial models of their environment. In this way, infra-Bayesian beliefs are similar to physical laws. For example, Newton's laws of motion can predict the path of a falling object, but not the weather tomorrow or the outcome of an election. Instead of using a single probability distribution, Infra-Bayesianism defines hypotheses as convex sets of probability distributions. This allows Infra-Bayesian hypotheses to be agnostic about certain parts of the world.

Our hypothesis is that infra-Bayesian agents will have an advantage in iterated games over Bayesian agents. I want to try and compare their performance in iterated game setting. It will be interesting to see if infra-Bayesian agents have better convergence to Nash equilibria.

The folk theorem states that any payoff vector above the minimax of each player can be achieved by a subgame-perfect equilibrium of a repeated game. For 2-player games, minimax and maximin payoffs in mixed strategies are the same. Therefore the best guaranteed payoff in a 2-player game is the maximin payoff. However, achieving it would not be very interesting, because to receive a maximin payoff, the agent only needs to learn its own rewards, and doesn't need to learn about other agents' policies.

This is why it is interesting to consider another simple kind of repeated game: a population game [LW(p) · GW(p)]. Instead of a fixed set of agents playing with each other, we consider $K$ populations of agents. At each turn, a random agent is selected from each population to participate in a one-shot game with $K$ players, which we refer to as the stage game. It is assumed that all populations are sufficiently large that the effect of any individual agent violating from their policy on the distribution of histories of other agents would be negligible.

In an immortal population game, the expected rewards of future games are discounted by a time factor of $\gamma$. In a mortal population game, the rewards are not discounted but instead each agent has a chance $1-\gamma$ of dying after each turn. Each turn all dead agents are replaced with new agents with empty histories.

Let us introduce some notations:

$A_i,i=1,\dots ,N$ is the set of pure strategies (actions) of the $i$th agent in the game. We assume $A_i$ are finite sets.

[I'll deal with deterministic rewards first, then see what happens in more complicated situations. For a deterministic reward, we can assume that a player knows his reward function.]

$O={\prod }_{i=1}^K{A}_i$ is the set of pure outcomes of a stage game. We assume that each player knows his own deterministic reward function $R_i:O\to [0,1]$.

The set of $n$-round outcome histories is $O^n$ and $O^{\ast }={\bigcup }_n{O}^n$ is the set of all finite-length histories. 

$|h|$ is the length of a history. is the length of a history $h\in O^{\ast }$.

Definition (distance between histories)

The distance between partial histories $h_1,h_2\in O^{\ast }$ is defined as

$d(h_1,h_2)={\alpha }^{t(h_1,h_2)}$,

where $\alpha \in (0,1)$ is some constant, $t(h_1,h_2)$ is the first time the histories diverge, i.e. the smallest $t$ such that exactly one of the histories has fewer than $t$ steps, or they both have at least $t$ steps and their step $t$ is different. If the histories are identical, the distance is defined to be 0. It is easy to see that this is indeed a metric.

$\Delta O^{\ast }$ represents the set of probability distributions on $O^{\ast }$.

Definition (distance between measures)

The Kantorovich-Rubinstein (KR) metric on the space $\Delta O^{\ast }$ is defined as follows:

$d(m,m^{\prime })={sup}_f|m\left(f\right)-m^{\prime }\left(f\right)|,$

where supremum is taken over all 1-Lipschitz 
functions $f:O^{\ast }\to [-1,1]$.

${\pi }_i:O^{\ast }\to \Delta A_i$ is the policy of player number i. It determines which mixed strategy player number $i$ chooses, given the full history it has seen so far. Upon seeing history $h$, the probability that player $i$ will choose action $a$ is ${\pi }_i\left(h\right)\left(\right\{a\left\}\right)$, which I may also write down as ${\pi }_i\left(a|h\right)$ for brevity.

${\mu }_i^n\in \Delta O^{\ast }$ is the distribution of histories in the i-th population at the $n$th turn of the repeated game.

Note how it is entirely possible for distributions of histories for different players to be different. For example, suppose that player 1 has two possible actions, and his policy is  to take action in the first game randomly with probability 50% each, and then always repeat this action. Then histories of players in distribution 1 will have repeated actions for player 1, while histories of players in distribution 2 will have random actions for player 1, because player 1 is sampled randomly from the distribution 1, and each move is equally likely.

Definition.

A set of policies is said to be in equilibrium if playing a different strategy ${\pi }_i^{\prime }$ for any agent, while all other agents (including other agents in population $i$) stick to their policies, does not result in greater expected reward. 

What does an equilibrium look like? Populations are assumed to be sufficiently large that an effect of any individual agent's action on the distribution of histories in the population is negligible. At turn $n$, opponent number $j$ is going to play a mixed strategy ${\pi }_j\left(h_j\right)$ with probability ${\mu }_j^n\left(h\right)$. So his moves follow probability distribution ${\pi }_j^n={\sum }_h{\mu }_j^n\left(h\right){\pi }_j\left(h\right)$. It means that the best policy for an individual agent in population $i$ is to choose a best response policy to mixed policies ${\pi }_1^n,\dots ,{\overline{\pi }}_i^n,\dots ,{\pi }_K^n$ at turn $n$. ("Bar" notation means the element in list is skipped). Since each agent follows a best response policy, their probabilistic mixture ${\pi }_i^n$ is also a best response policy. So the weighted averages of the players' policies at every turn are in a Nash equilibrium strategy for the single-turn game. 

It is interesting to find out if choosing ${\pi }_i$ to be learning strategies will result in convergence to a Nash equilibrium in the limit of $\gamma \to 1$.

 

The evolution rule  $T_i:(\Delta O^{\ast }{)}^K\to \Delta O^{\ast }$ that produces ${\mu }_i^{n+1}$ from ${\mu }_1^n,\dots ,{\mu }_K^n$ works as follows. 

For the first step, for each $j=1,\dots ,K$ we sample a history for player $j$ from ${\mu }_j^n.$ Then we sample actions according to policies ${\pi }_j:O^{\ast }\to \Delta A_j$. We append the outcome of the game to the history of player number $i$. 

For the second step, each player dies with probability $1-\gamma$ and is replaced with a new player with an empty history.

The first step is described by the formula 

${\mu }_i^{n+1}\left(h\right)={\hat{T}}_i({\mu }_1^n,\dots ,{\mu }_K^n)\left(h\right)$, where

${\hat{T}}_i({\mu }_1,\dots ,{\mu }_K)\left(h\right)={\mu }_i\left(h^{\prime }\right){\pi }_i\left(h^{\prime }\right)\left(a_i\right){\sum }_{h_1}\dots {\overline{\sum }}_{h_i}\dots {\sum }_{h_K}{\prod }_{j\ne i}{\mu }_j\left(h_j\right){\pi }_j\left(a_j|h_j\right)$,

where $h^{\prime }$ stands for history $h$ without the last step, $a=(a_1,\dots ,a_K)$ for the actions taken at the last step of h, and the sums on the right-hand side are taken over histories of all players except for player $i$.

The second step is obtained by

$T_i({\mu }_1,\dots ,{\mu }_K)=\gamma {\hat{T}}_i({\mu }_1,\dots ,{\mu }_K)+(1-\gamma ){\delta }_{\varnothing }$

where ${\delta }_{\varnothing }$ stands for the Dirac delta measure of an empty history.

Lemma.

$T_i$ is continuous.

Proof.

$T_i$ is obtained from ${\hat{T}}_i$ by a linear transformation, so it is enough to prove continuity of ${\hat{T}}_i$.

I am going to write down a proof for $K=3$, it generalizes straightforwardly to any $K$.

For any 1-Lipschitz function $f:O^{\ast }\to [-1,1]$,

${\hat{T}}_1({\mu }_1,{\mu }_2,{\mu }_3)\left(f\right)-{\hat{T}}_1({\mu }_1^{\prime },{\mu }_2^{\prime },{\mu }_3^{\prime })\left(f\right)$

$={\sum }_{|h|\ge 1}f\left(h\right){\mu }_1\left(h^{\prime }\right){\pi }_1\left(a_1|h^{\prime }\right){\sum }_{h_2}{\mu }_2\left(h_2\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}{\mu }_3\left(h_3\right){\pi }_3\left(a_3|h_3\right)$

$-{\sum }_{|h|\ge 1}f\left(h\right){\mu }_1^{\prime }\left(h^{\prime }\right){\pi }_1\left(a_1|h^{\prime }\right){\sum }_{h_2}{\mu }_2^{\prime }\left(h_2\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}{\mu }_3^{\prime }\left(h_3\right){\pi }_3\left(a_3|h_3\right)$

$={\sum }_{|h|\ge 1}f\left(h\right){\mu }_1\left(h^{\prime }\right){\pi }_1\left(a_1|h^{\prime }\right){\sum }_{h_2}{\mu }_2^{\prime }\left(h_2\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}\left({\mu }_3\right(h_3)-{\mu }_3^{\prime }(h_3\left)\right){\pi }_3\left(a_3|h_3\right)$

$+{\sum }_{|h|\ge 1}f\left(h\right){\mu }_1\left(h^{\prime }\right){\pi }_1\left(a_1|h^{\prime }\right){\sum }_{h_2}\left({\mu }_2\right(h_2)-{\mu }_2^{\prime }(h_2\left)\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}{\mu }_3\left(h_3\right){\pi }_3\left(a_3|h_3\right)$

 $+{\sum }_{|h|\ge 1}f\left(h\right)\left({\mu }_1\right(h^{\prime })-{\mu }_1^{\prime }(h^{\prime }\left)\right){\pi }_1\left(a_1|h^{\prime }\right){\sum }_{h_2}{\mu }_2^{\prime }\left(h_2\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}{\mu }_3^{\prime }\left(h_3\right){\pi }_3\left(a_3|h_3\right)$  (1)

Let us look at the second summand.

${\sum }_{|h|\ge 1}f\left(h\right){\mu }_1\left(h^{\prime }\right){\pi }_1\left(a_1|h^{\prime }\right){\sum }_{h_2}\left({\mu }_2\right(h_2)-{\mu }_2^{\prime }(h_2\left)\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}{\mu }_3\left(h_3\right){\pi }_3\left(a_3|h_3\right)$

$\le {\sum }_{|h|\ge 1}{\mu }_1\left(h^{\prime }\right){\sum }_{h_2}|{\mu }_2\left(h_2\right)-{\mu }_2^{\prime }\left(h_2\right)|$

because $|f|\le 1,$ $|{\pi }_1\left(a_1|h^{\prime }\right)|\le 1,$ $|{\pi }_2\left(a_2|h_2\right)|\le 1$ and ${\sum }_{h_3}{\mu }_3\left(h_3\right){\pi }_3\left(a_3|h_3\right)\le {\sum }_{h_3}{\mu }_3\left(h_3\right)=1$.

Choose $t=t\left({\mu }_2\right)$ such that ${\sum }_{|h|>t}{\mu }_2\left(h\right)\le ϵ/\left(9|A|\right)$. 

Then the sum

${\sum }_h|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|={\sum }_{|h|\le t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|+{\sum }_{|h|>t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|$

$\le {\sum }_{|h|\le t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|+{\sum }_{|h|>t}{\mu }_2\left(h\right)+{\sum }_{|h|>t}{\mu }_2^{\prime }\left(h\right)$                          (2)

Let us upper bound the first summand in (2):

${\sum }_{|h|\le t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|=2{\alpha }^{-t}{\sum }_{h}g\left(h\right)\left({\mu }_2\right(h)-{\mu }_2^{\prime }(h\left)\right)$,

where $g\left(h\right)=0.5{\alpha }^t\text{sign}\left({\mu }_2\right(h)-{\mu }_2^{\prime }(h\left)\right)$ if $|h|\le t$ and 0 otherwise.

Then $g$ is a 1-Lipschitz function from $O^{\ast }$ to [-1, 1]. 

Indeed, $|g\left(h\right)|\le 0.5{\alpha }^{|h|}$, so for any two histories $h_1$ and $h_2$,  $|g\left(h_1\right)-g\left(h_2\right)|\le {\alpha }^{max(|h_1|,|h_2|)}\le d(h_1,h_2)$

Therefore, this expression can be bounded from above by

$2{\alpha }^{-t}{\sum }_{h}g\left(h\right)\left({\mu }_2\right(h)-{\mu }_2^{\prime }(h\left)\right)\le 2{\alpha }^{-t}d({\mu }_2,{\mu }_2^{\prime })$

Now for the last summand in (2):

 ${\sum }_{|h|>t}{\mu }_2^{\prime }\left(h\right)=1-{\sum }_{|h|\le t}{\mu }_2^{\prime }\left(h\right)\le$

$\le 1-{\sum }_{|h|\le t}{\mu }_2\left(h\right)+{\sum }_{|h|\le t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|$

$={\sum }_{|h|>t}{\mu }_2\left(h\right)+{\sum }_{|h|\le t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|$

Bringing them together:

$|{\sum }_{h\in O^{\ast }}\left({\mu }_2\right(h)-{\mu }_2^{\prime }(h\left)\right)|\le 2{\sum }_{|h|\le t}|{\mu }_2\left(h\right)-{\mu }_2^{\prime }\left(h\right)|+2{\sum }_{|h|>t}{\mu }_2\left(h\right)\le$

$\le 4{\alpha }^{-t}d({\mu }_1,{\mu }_2)+2ϵ/\left(9|A|\right)$

If follows that for any ${\mu }_2^{\prime }$ such that $d({\mu }_2,{\mu }_2^{\prime })<1/4{\alpha }^{t\left({\mu }_2\right)}\ast ϵ/\left(9|A|\right)$, this sum is less than $ϵ/\left(3|A|\right)$.

Since every history has $|A|$ possible successors after 1 step, ${\sum }_{h\in O^{\ast },|h|\ge 1}{\mu }_1\left(h^{\prime }\right)={\sum }_{h_1\in O^{\ast }}{\mu }_1\left(h_1\right)\ast |A|=|A|$ 

We proved that for any ${\mu }_2^{\prime }$ such that $d({\mu }_2,{\mu }_2^{\prime })<1/4{\alpha }^t\ast ϵ/\left(9|A|\right)$ the second summand in (1) is bounded from above by 

${\sum }_{|h|\ge 1}{\mu }_1\left(h^{\prime }\right){\sum }_{h_2}|{\mu }_2\left(h_2\right)-{\mu }_2^{\prime }\left(h_2\right)|$

$\le {\sum }_{|h|\ge 1}{\mu }_1\left(h^{\prime }\right)ϵ/\left(3|A|\right)\le ϵ/\left(3|A|\right)\ast |A|=ϵ/3$

The same argument proves that for any ${\mu }_3^{\prime }$ such that $d({\mu }_3,{\mu }_3^{\prime })<1/4{\alpha }^{t\left({\mu }_3\right)}\ast ϵ/\left(9|A|\right)$, the first summand is bounded from above by $ϵ/3$.

Now let us upper bound the last summand in (1).

It can be written down as

${\sum }_{|h|\ge 1}f\left(h\right)\left({\mu }_1\right(h^{\prime })-{\mu }_1^{\prime }(h^{\prime }\left)\right)P\left(h|h^{\prime }\right)$

where 

$P\left(h|h_1\right)={\pi }_1\left(a_1|h_1\right){\sum }_{h_2}{\mu }_2^{\prime }\left(h_2\right){\pi }_2\left(a_2|h_2\right){\sum }_{h_3}{\mu }_3^{\prime }\left(h_3\right){\pi }_3\left(a_3|h_3\right)$ if $h_1=h^{\prime }$,

                    0 if $h_1\ne h^{\prime }$

is the probability that player $1$ with a history $h^{\prime }$ will end up with history $h$ after one step. We can rewrite this expression as

${\sum }_h{\sum }_{h_1}f\left(h\right)\left({\mu }_1\right(h_1)-{\mu }_1^{\prime }(h_1\left)\right)P\left(h|h_1\right)$

because if $h_1$ is not equal to the history $h$ without the last step, the probability $P\left(h|h_1\right)$ is equal to zero. Now rewrite this as

${\sum }_{h_1}\left({\mu }_1\right(h_1)-{\mu }_1^{\prime }(h_1\left)\right){\sum }_{h}P\left(h|h_1\right)f\left(h\right)=({\mu }_1-{\mu }_1^{\prime })\left(\tilde{f}\right)$,

where $\tilde{f}\left(h_1\right)={\sum }_{h}P\left(h|h_1\right)f\left(h\right)$.

Let us prove that if $f$ is a 1-Lipschitz function $O^{\ast }\to [-1,1]$, the same is true of $\tilde{f}$.

The inequalities $-1\le \tilde{f}\le 1$ are obvious. For any two different histories $h_1$ and $h_2$, any their two continuation histories $h_1{a}_1$ and $h_2{a}_2$ are at the same distance $d(h_1{a}_1,h_2{a}_2)=d(h_1,h_2)$, and therefore $|f\left(h_1{a}_1\right)-f\left(h_2{a}_2\right)|\le d(h_1{a}_1,h_2{a}_2)=d(h_1,h_2)$. Since the integrands are close, the integrals must be close too:

$\tilde{f}\left(h_1\right)-\tilde{f}\left(h_2\right)\le {sup}_{h_1^{\prime }}f\left(h_1^{\prime }\right)-{inf}_{h_2^{\prime }}f\left(h_2^{\prime }\right)\le d(h_1,h_2)$

The same way,

$\tilde{f}\left(h_2\right)-\tilde{f}\left(h_1\right)\le {sup}_{h_2^{\prime }}f\left(h_2^{\prime }\right)-{inf}_{h_1^{\prime }}f\left(h_1^{\prime }\right)\le d(h_1,h_2),$

and so $\tilde{f}$ is 1-Lipschitz.

Therefore, the third summand is bounded from above by $d({\mu }_1,{\mu }_1^{\prime })$, so if we choose ${\mu }_1^{\prime }$ so that $d({\mu }_1,{\mu }_1^{\prime })\le ϵ/3$, ${\mu }_2^{\prime }$ so that $d({\mu }_2,{\mu }_2^{\prime })\le 1/4{\alpha }^{t\left({\mu }_2\right)}\ast ϵ/\left(9|A|\right)$ and ${\mu }_3^{\prime }$ so that $d({\mu }_3,{\mu }_3^{\prime })\le 1/4{\alpha }^{t\left({\mu }_3\right)}\ast ϵ/\left(9|A|\right)$, we'll get ${\hat{T}}_1({\mu }_1,{\mu }_2,{\mu }_3)\left(f\right)-{\hat{T}}_1({\mu }_1^{\prime },{\mu }_2^{\prime },{\mu }_3^{\prime })\left(f\right)\le ϵ$. Qed.

Notice how we also proved that if ${\mu }_2$ and ${\mu }_3$ are kept fixed, ${\hat{T}}_1$ does not increase the distance, and therefore $T_1$ is a contraction.

---

Combining all components gives us the map $T=(T_1,\dots ,T_K):(\Delta O^{\ast }{)}^K\to (\Delta O^{\ast }{)}^K$.

We can extend a finite history to an infinite history by appending an infinite number of blank or "placeholder" turns represented by the symbol $\perp$ at the end of the original history. With this notation, $O^{\ast }$ is a subset of $(O\bigsqcup \{\perp \}{)}^{\omega }$. The set $O\bigsqcup \{\perp \}$  (with discrete topology) is compact, and therefore their product $(O\bigsqcup \{\perp \}{)}^{\omega }$ is a compact space by the Tychonoff's theorem. $\Delta O^{\ast }$can be seen as a subset of $\Delta \left(\right(O\bigsqcup \{\perp \}{)}^w)$: we take a probability distribution $\mu$ on $O^{\ast }$ and for any subset $E\subset (O\bigsqcup \{\perp \}{)}^w$ define$\mu \left(E\right):=\mu (E\cap O^{\ast })$.

The distance on $(O\bigsqcup \{\perp \}{)}^{\omega }$ is defined just like on $O^{\ast }$: the distance between two histories is ${\alpha }^t$ where $t$ is the first time the two histories diverge. 

Proposition

The topology induced on $(O\bigsqcup \{\perp \}{)}^w$ by this metric is the product topology on $(O\bigsqcup \{\perp \}{)}^{\omega }$.

Proof

The product topology on $(O\bigsqcup \{\perp \}{)}^{\omega }$ can be generated by basis sets $U(x,M)={\prod }_{i=1}^M{x}_i\times {\prod }_{i=M+1}^{\infty }(O\bigsqcup \{\perp \left\}\right)$. The metric topology is generated by the unit balls $B(x,r)=\{y\in (O\bigsqcup \{\perp \}{)}^{\omega }:d(x,y)<r\}$. These two families coincide, since $B(x,r)=U(x,M)$, where $M$ is the smallest integer such that ${\alpha }^{M+1}<r$. Therefore the topologies also coincide.

vggf

Since $(O\bigsqcup \{\perp \}{)}^{\omega }$ is compact, it must also be a complete space. The set of sequences with finitely many non-$\perp$ elements is countable and dense in $(O\bigsqcup \{\perp \}{)}^{\omega }$. So $(O\bigsqcup \{\perp \}{)}^{\omega }$ is a separable space. This means that $(O\cup \{\perp \}{)}^{\omega }$ is a separable, completely metrizable topological space, also known as a Polish space.

Because $(O\cup \{\perp \}{)}^{\omega }$ is compact, the space of probability distributions over it, $\Delta (O\bigsqcup \{\perp \}{)}^{\omega }$ is compact in the weak* topology. (See theorem 10.2 in [3])

However, we are looking for fixed points among probability distributions on $O^{\ast }$ and, unfortunately, $\Delta O^{\ast }$ is not compact as $O^{\ast }$ is not closed in ($O\bigsqcup \{\perp \}{)}^{\omega }$. (A sequence of finite histories that are continuations of each other has a limit in $(O\bigsqcup \{\perp \}{)}^{\omega }$, but it's not a finite history.)

On the other hand, we can observe that a fixed distribution in $(\Delta O^{\ast }{)}^K$ has the following property:

If the proportion of players in population with a history length of $t$ is $x$ in the $n$th generation, then the proportion of players in population  with a history length of $t+1$ in the next generation will be $\gamma$ x, since $\gamma$ is the proportion of players with a $t$-long history that survive the turn. This implies that in a fixed distribution the age-distribution $\zeta$ must satisfy $\zeta (t+1)=\gamma \zeta \left(t\right)$. This means that $\zeta \left(t\right)={\gamma }^t(1-\gamma )$.

We call $P$ the subset of $\Delta O^{\ast }\subset \Delta \left(\right(O\bigsqcup \{\perp \}{)}^{\omega })$ in which every population's age distribution is $\zeta$.

Lemma

$P$ is closed in the weak* topology.

Proof

Suppose ${\mu }_n\to \mu$ is a converging sequence of measures, ${\mu }_n\in P$. It means that for any continuous function $f:(O\bigsqcup \{\perp \}{)}^{\omega }\to R$, 
$\int fd{m}_n\to \int fdm$.

For elements of $(O\bigsqcup \{\perp \}{)}^w$, we can define length as the number of symbols before the first ocurrence of symbol $\perp$ (if there is no symbol $\perp$, the length is infinite).
For a fixed nonnegative integer $t$, consider the function $f\left(h\right)$ which is equal to 1 if $h$  has length $t$, and 0 otherwise. It is continuous, because if length of a history $h$ is $t$, $\forall h^{\prime }:d(h,h^{\prime })<{\alpha }^t⟹h=h^{\prime }⟹|f\left(h\right)-f\left(h^{\prime }\right)|=0$. The integral $\int fd{m}_n$ measures the proportion of histories in the distribution $m_n$ which have length $t$; the limit distribution $m$ then must preserve the age distribution and also belong in the set $P$

As a closed subset of a compact set, $P$ is compact. It is also easy to see that $P$ is convex. 

Theorem

 $T=(T_1,\dots ,T_K):P\to P$ has a fixed point.

Proof

The Schauder fixed-point theorem implies that a continuous map from a compact convex subset of a Hausdorff topological vector space to itself has a fixed point. We showed that P is compact and convex, and T is continuous. 

The set  $\Delta \left(\right(O\bigsqcup \{\perp \}{)}^{\omega })$ is a subset of the topological vector space $M\left(\right(O\bigsqcup \{\perp \}{)}^{\omega })$ of all finite signed measures on $(O\bigsqcup \{\perp \}{)}^{\omega }$ with weak* topology. Let us show that this vector space is Hausdorff. Take any two signed measures $m_1=m_1^{+}+m_1^{-}$ and $m_2=m_2^{+}+m_2^{-}$, and suppose that no continuous function $f$ on $(O\bigsqcup \{\perp \}{)}^w$ separates them: $\int fd{m}_1=\int fd{m}_2$. Then $\int fd(m_1^{+}-m_2^{-})=\int fd(-m_1^{-}+m_2^{+})$. The functional $L\left(f\right)=\int fd(m_1^{+}-m_2^{-})$ is a positive linear functional on $C\left(\right(O\bigsqcup \{\perp \}{)}^{\omega })$. The space $(O\bigsqcup \{\perp \}{)}^{\omega }$ is metric and therefore Hausdorff; it is compact and therefore locally compact. Therefore, by the Riesz representation theorem, the measure corresponding to this functional is unique: $m_1^{+}-m_2^{-}=-m_1^{-}+m_2^{+}$ and therefore $m_1=m_2$.

---

Another possibly interesting observation is that the age distribution of histories is going to converge to the limit distribution.

Proposition 

The age distribution of histories $m\left(t\right)={\sum }_{|h|=t}\mu \left(h\right)$ converges to the distribution $\zeta \left(t\right)={\gamma }^t(1-\gamma )$ in the norm $d(m_1,m_2)={\sum }_t|m_1\left(t\right)-m_2\left(t\right)|$.

Proof  

Since the map $T_i$ adds 1 step to every history and then replaces each agent with a newborn with probability $1-\gamma$, it induces a map on age distributions:

 $T_i\left(m\right)\left(t\right)=\gamma m(t-1)$ for $t>0$

                      $1-\gamma$ for $t=0$ 

on age distributions.  For this map $\zeta$ is a fixed point and $d\left(T\right(m_1),T(m_2\left)\right)=\gamma d(m_1,m_2)$. It follows that any initial age distribution converges to $\zeta$.

What happens in the fixed points? In a fixed point, the distribution of opponents stays the same each term. It means that a player observes a sequence of independent identically distributed (IID) outcomes of their policy. Suppose that the policy $\pi$ satisfies the following property: upon observing an IID sequence of games, it converges to the optimal response in the limit of $\gamma \to \infty$. Then in this limit, fixed points will also be Nash equilibria. 
The property above can be satisfied even by very simple algorithms, for example, one that assumes that opponent's move is randomly sampled from the set of his previous moves. Any Bayesian agent that includes all IID processes in its prior will satisfy this property.

Some interesting questions for research are:

Are any/all of the fixed points attractors?

Does convergence to a fixed point occur for all or at least almost all initial conditions?

Do all Nash equilibria correspond to fixed points? 

Do stronger game theoretic solution concepts (e.g. proper equilibria) have corresponding dynamical properties?

[1] Kalai, Ehud, and Ehud Lehrer. "Rational learning leads to Nash equilibrium." Econometrica: Journal of the Econometric Society (1993): 1019-1045.
[2] Dean P Foster and H Peyton Young. "On the
impossibility of predicting the behavior of rational agents." Proceedings of the National
Academy of Sciences, 98(22):12848–12853,
2001.
[3] Nachbar, John H. "Beliefs in repeated games." Econometrica 73.2 (2005): 459-480.
[4] Hadfield-Menell D. et al. Cooperative inverse reinforcement learning //Advances in neural information processing systems. – 2016. – Т. 29.
[5]Hadfield-Menell D. et al. The off-switch game //Workshops at the Thirty-First AAAI Conference on Artificial Intelligence. – 2017.
[6]Ergodic Theory by Charles Walkden, lecture 10

0 comments

Comments sorted by top scores.