Superrationality in arbitrary games

[Vanessa Kosoy]

This post is an informal summary of ideas that Scott and I discussed on my recent visit to Los Angeles, meant to serve as a temporary “savepoint” and reference. The approach outlined here, albeit very promising in my opinion, requires a more work to become mature.

Abstract

We introduce a new type of game theoretic equilibrium, which is a candidate game theoretic desideratum for decision theory. This can be regarded as a generalization of Hofstadter’s superrationality to arbitrary games. This equilibrium can be interpreted as the outcome of games between transparent agents running CDT with restricted self-modification but also as the outcome of games between transparent agents employing a certain type of logical counterfactuals. We suggest it should be possible to use the formalism of optimal predictors to rigorously construct a logical decision theory which implements the latter interpretation.

Introduction

It is commonly assumed that two agents running the correct decision theory would cooperate in a transparent Prisoner’s dilemma, that is, in a game of prisoner’s dilemma in which each player knows the source code of the other player${}^1$. It is possible to argue this behavior will indeed arise in UDT, at least for sufficiently similar players, but the argument is unrigorous since an agreed upon formalisation of UDT is lacking. It is also possible to formally prove this behavior for certain set-ups of proof-based decision theory. However, it is not presently clear what is the correct desideratum for decision theory in arbitrary games, especially games that are asymmetric.

The correct decision theory is likely to use logical counterfactuals but current understanding of logical counterfactuals is poor. On the other hand, it is much easier to model causal counterfactuals. Although CDT often leads to bad outcomes (and in particular defects in prisoner’s dilemma) it is reflectively unstable and given the chance is expected to self-modify into some kind of better decision theory${}^2$. We will now see that a naive formalisation of this idea fails to achieve satisfactory game-theoretic properties. This failure is later amended by restricting the “self-modification” to only produce programs of a certain form, arriving at what we hope is the correct desideratum.

Self-modifying CDT

Fix a universal Turing machine to be used for representing Turing machines as words (programs).

Consider a game $G$ in normal form between $n$ players. Denote ${\Sigma }_i$ the set of pure strategies for the $i$-th player and $u_i:{\prod }_{j=1}^n{\Sigma }_j\to R$ the utility function of the $i$-th player.

Given $t\in N$, we define the associated self-modification game $G^{SM\left(t\right)}$ as follows. The pure strategies of the $i$-th player are ${\Sigma }_i^{SM\left(t\right)}:=\{0,1{\}}^t$. These strategy represent programs that receive the strategies of the other players as input, run for $t$ time steps and produce a strategy in the original game, possibly using random coin flips. The utility function of the $i$-th player is given by

$$u_i^{SM\left(t\right)}({\pi }_1,{\pi }_2\dots {\pi }_n):=E_{U^{nt}}\left[u_i\right(e{v}^t({\pi }_1;{\pi }_2,{\pi }_3\dots {\pi }_n,x_1),e{v}^t({\pi }_2;{\pi }_1,{\pi }_3\dots {\pi }_n,x_2)\dots e{v}^t({\pi }_n;{\pi }_1,{\pi }_2\dots {\pi }_{n-1},x_n)\left)\right]$$

For example, denoting the prisoner’s dilemma $G_{PD}$ and taking $t>>0$, there are Nash equilibria in $G_{PD}^{SM\left(t\right)}$ which corresponds to the outcome $(C,C)$ in $G_{PD}$. For example take $q$ to be “cliquebot” program, constructed using quining:

$$q\left(\pi \right):=\{\begin{array}{c}C\text{if}q\text{is a prefix of}\pi \\ D\text{otherwise}\end{array}$$

Then obviously $(q_1,q_2)$ is a Nash equilibrium of $G_{PD}^{SM\left(t\right)}$ for any $q_1,q_2\in \{0,1{\}}^t$ s.t.$q$ is a prefix of $q_1$ and $q_2$. However, the “defectbot” $d\left(\pi \right):=D$ also gives a Nash equilibrium. More generally, for any $p\in [0,1]$ a dyadic rational we can define the $p$-cliquebot to be

$$q_p\left(\pi \right):=\{\begin{array}{c}C\text{with probability}p\text{if}{q}_p\text{is a prefix of}\pi \\ D\text{otherwise}\end{array}$$

The defectbot equilibrium turns out to be unstable in the sense that it’s not a thermodynamic equilibrium at zero temperature (see below). However $p$-cliquebots for $p>0$ yield equilibria which are stable in this sense. This is a deficiency of the formalism which is avoided by the metathreat hierarchy (see below).

Thermodynamic Game Equilibria

Consider a game $G$ in normal form as before. Denote ${\Delta }_i$ the set of mixed strategies of the $i$-th player i.e.

$${\Delta }_i:=\{\mu :{\Sigma }_i\to [0,1]\mid \sum _{a\in {\Sigma }_i}\mu (a)=1\}$$

Consider $T\in (R^{>0}{)}^n$. A thermodynamic equilibrium of $G$ at temperature $T$ is $\mu :=({\mu }_1,{\mu }_2\dots {\mu }_n)\in {\prod }_{i=1}^n{\Delta }_i$ s.t.

$${\mu }_i\left(a\right)=Z_i^{-1}\exp \left(\frac{E_{\mu }\left[u_i\right(a_1,a_2\dots a\dots a_n\left)\right]}{T_i}\right)$$

where $Z_i\in R$ are normalization constants. Alternatively, $\mu$ is a thermodynamic equilibrium iff

$${\mu }_i=\arg \underset{\mu \in {\Delta }_i}{max}\left(E_{\mu }\right[u_i(a_1,a_2\dots a_n)]+T_{i}S[{\mu }_i\left]\right)$$

where $S\left[{\mu }_i\right]$ is the information-theoretic entropy of ${\mu }_i$.

At least one thermodynamic equilibrium exists for any game and temperature, as a consequence of Brouwer’s fixed-point theorem.

$\mu \in {\prod }_{i=1}^n{\Delta }_i$ is called a thermodynamic equilibrium of $G$ at zero temperature when there is a sequence $\left\{\right({\mu }^k\in {\prod }_{i=1}^n{\Delta }_i,T^k\in \left(R^{>0}{)}^n\right){\}}_{k\in N}$ s.t. ${lim}_{k\to \infty }{\mu }^k=\mu$, ${lim}_{k\to \infty }{T}^k=0$ and ${\mu }^k$ is a thermodynamic equilibrium at temperature $T^k$.

At least one thermodynamic equilibrium at zero temperature exists for any game, as a consequence of the Bolzano-Weierstrass theorem. Any thermodynamic equilibrium at zero temperature is a trembling hand equilibrium but the converse is false in general. We believe that for finite extensive-form games, a thermodynamic equilibrium at zero temperature is a subgame perfect equilibrium.

We believe $(d,d)$ is a trembling hand equilibrium in $G_{PD}^{SM\left(t\right)}$ but not a thermodynamic equilibrium at zero temperature. On the other hand $(q_p,q_p)$ is a thermodynamic equilibrium at zero temperature for $p>0$ (when random bits are appended to $q_p$ until it becomes a string of length $t$).

Thermodynamic equilibria are interesting because it is possible to implement them using a natural decision theory (that is, a decision theory that treats everything as a 1-player game by modeling the other players). Games between transparent CDT agents using reflective oracles lead to Nash equilibria, and it should be straightforward to “thermalize” the decision theory and get thermodynamic equilibria at finite temperature. A similar result should be possible using optimal predictor schemes instead of reflective oracles.

The Metathreat Hierarchy

The $p$-cliquebot can be informally regarded as an infinite tower of threats of increasing level of “meta”. The 1st level says any strategy other than cooperation with probability $p$ will be answered by defection. The $k+1$-st level says that failure to produce the $k$-th level threat will be answered by defection. This way the players blackmail each other into complying with this suboptimal strategy. However, if we had a way to truncate the tower at any finite level, it would apart: there would be no justification for each player to produce the highest level threat and it would unwind downwards recursively. The metathreat hierarchy is a formal method to implement this truncation.

Consider a game $G$ in normal form as before. Fix $m\in N$. The associated level $0$ metathreat game with $m$ coin-flips is just $G$ itself: $G^{MT(0,m)}:=G$. We define the associated level $k+1$ metathreat game with $m$ coin-flips $G^{MT(k+1,m)}$ recursively. The pure strategies of the $i$-th player are

$${\Sigma }_i^{MT(k+1,m)}:=\{\pi :\prod _{j\ne i}{\Sigma }_j^{MT(k,m)}\times \{0,1{\}}^m\to {\Sigma }_i^{MT(k,m)}\mid \exists a\in {\Sigma }_i^{MT(k,m)}\forall b\in \prod _{j\ne i}{\Sigma }_j^{MT(k,m)}\exists x\in \{0,1{\}}^m:\pi (b,x)=a\}$$

Consider $\pi \in {\prod }_{i=1}^n{\Sigma }_i^{MT(k+1,m)}$. Then there is ${\mu }^{\pi }\in {\prod }_{i=1}^n{\Delta }_i^{MT(k,m)}$ unique s.t.

$${\mu }_i^{\pi }\left(a\right)=P{r}_{{\mu }^{\pi }\times U^m}\left[{\pi }_i\right(b,x)=a]$$

It exists because of Brouwer’s fixed-point theorem and is unique because of standard results about Markov chains ($\pi$ defines a Markov chain on ${\prod }_{i=1}^n{\Sigma }_i^{MT(k,m)}$, ${\mu }^{\pi }$ is a stationary distribution of this chain and it has to be unique because of the properties of the chain that follow from the condition on ${\pi }_i$). This allows us to define the utility functions

$$u_i^{MT(k+1,m)}\left(\pi \right)=E_{{\mu }^{\pi }}\left[u_i^{MT(k,m)}\right(a\left)\right]$$

Denote ${\Gamma }^{MT(k,m)}$ the space of correlated mixed outcomes of $G^{MT(k,m)}$:

$${\Gamma }^{MT(k,m)}:=\{\nu :\prod _{i=1}^n{\Sigma }_i^{MT(k,m)}\to [0,1]\mid \sum _{\pi \in {\prod }_{i=1}^n{\Sigma }_i^{MT(k,m)}}\nu (\pi )=1\}$$

There is a natural sense in which ${\prod }_{i=1}^n{\Delta }_i^{MT(k,m)}\subseteq {\Gamma }^{MT(k,m)}$.

For $k>j$ we define the unwinding operator ${\omega }^{MT(k\to j,m)}:{\Gamma }^{MT(k,m)}\to {\Gamma }^{MT(j,m)}$ recursively by

$${\omega }^{MT(k+1\to k,m)}\left(\nu \right):=\sum _{\pi \in {\prod }_{i=1}^n{\Sigma }_i^{MT(k+1,m)}}\nu \left(\pi \right){\mu }^{\pi }$$

$${\omega }^{MT(k\to j,m)}\left(\nu \right):={\omega }^{MT(j+1\to j,m)}\left({\omega }^{MT(k\to j+1,m)}\right(\nu \left)\right)$$

Consider $\nu \in \Gamma$, a correlated mixed outcome of $G$. $\nu$ is called a level $k$ metathreat equilibrium when there is a sequence $\left\{\right(m^i\in N,{\mu }^i\in {\prod }_{i=1}^n{\Delta }_i^{MT(k,m^i)}){\}}_{i\in N}$ s.t. ${lim}_{i\to \infty }{m}_i=\infty$, ${lim}_{i\to \infty }{\omega }^{MT(k\to 0,m_i)}\left({\mu }^i\right)=\nu$ and ${\mu }^i$ is a thermodynamic equilibrium of $G^{MT(k,m^i)}$ at zero temperature. The Bolzano-Weierstrass theorem ensures such $\nu$ exists for any game and value of $k$.

We believe that for $m>>0$, $G_{PD}^{MT(1,m)}$ has a unique thermodynamic equilibrium at zero temperature which is a mixture of $\pi$ s.t.

$$P{r}_{U^m}\left[\pi \right(C,x)=C]=1$$

$$P{r}_{U^m}\left[\pi \right(D,x)=C]=2^{-m}$$

Therefore $(C,C)$ is the unique level $1$ metathreat equilibrium of $G_{PD}$.

Some questions for further research:

• Does the set of level $k$ metathreat equilibria stabilize for $k>>0$?

• Are level $k$ metathreat equilibria guaranteed to be Pareto efficient for $k>>0$? Or even already for $k>0$?

• How do level $k$ metathreat equilibria look like for $G_{PD}$ in ${\Sigma }^{MT(k,m)}$-space for $k>1$?

• Does anything change for $k>>0$ if we explicitly introduce shared random bits? It seems plausible that shared random bits can always be replaced by going to higher values of $k$.

One decision theoretic interpretation of metathreat equilibria is in terms of self-modifying CDT. The elements of ${\Sigma }^{MT(k,m)}$ can be interpreted as programs that use reflective oracles or optimal predictor schemes to make predictions about the opposing programs and decide on a strategy accordingly. Thus our self-modification is restricted by the programs in this class.

Another interpretation is in terms of logical decision theory, at least for $k=1$. Such a decision theory consists of two stages. In the first stage the agent computes logical conditional expected utility (using an optimal predictor scheme) where the condition corresponds to selection of a given element in $\pi \in {\Sigma }^{MT(k,1)}$. It then performs a sequence of logical coin flips to decide on $\pi$ according to a probability distribution designed to yield a thermodynamic equilibrium. In the second stage the agent uses an optimal predictor scheme to guess the strategy of its opponent and acts according to $\pi$, this time providing so much resources to the optical predictor scheme that the result of the first stage for the opposing agent is certain. Such a decision theory is not entirely natural since it explicitly uses the concept of “opponent actions”, but hopefully it can be used as a foundation for constructing a fully natural logical decision theory.

${}^1$ The historical origin of this idea is Hofstadter “superrationality”.

${}^2$ We don’t expect the limit of this self-modification process to be entirely reasonable since in some situations self-modification cannot save CDT, for example if self-modification only begins after the agent is inspected by Omega in Newcomb’s paradox. However, it seems plausible to specify assumptions under which self-modifying CDT will make the right choices e.g. Newcomb’s paradox where self-modification is allowed before inspection by Omega.

[paulfchristiano]

Do thermodynamic equilibria differ meaningfully from proper equilibria?

[Vanessa Kosoy]

Another case which is important is games with infinite strategy spaces. In particular see my recent post where I use the notion of thermodynamic equilibrium in a way which cannot be trivially mimicked (I think) by a proper equilibrium.

[Vanessa Kosoy]

Good question. One obvious difference is that thermodynamic equilibria are naturally defined for games with appropriate continuous strategy spaces, but it’s probably not important for intelligent agent theory.

It seems plausible that for zero temperature they don’t.

For positive temperature thermodynamic equilibria are more rigid than $ϵ$-proper profiles but I’m not sure it’s important.

[Stuart_Armstrong]

Very interesting! I’m eager to see where this will lead.

If the PD has different values (thus is non-symmetric), but still has the same ordinal relations on outcomes (player 1 prefers (D,C) to (C,C) to (D,D) to (C,D), etc...), is (C,C) still the unique level 1 metathreat equilibrium?

And what inspired this “thermodynamic” approach?

[Vanessa Kosoy]

The metathreat equilibrium definitely depends on the cardinal utilities, for example if $u_{CC}<\frac{u_{CD}+u_{DC}}{2}$ then the “nicer bots” are not an equilibrium since both agents want to lower the probability of cooperation.

The thermodynamic approach is needed since we need a way to rule out some of the metathreat Nash equilibria. A pair of defect bots is a Nash equilibrium in the level 1 metathreat game but this equilibrium is “unstable” since there are bots that are equally good against the defect bot but do better against other bots. So we need some notion of equilibrium stability, but the usual trembling hand is not good enough since for trembling hand equilibrium stability wrt an arbitrary totally mixed perturbation is sufficient (and it is possible to construct perturbations that stabilize “bad” equilibria). The thermodynamic equilibrium works by considering perturbations in which lower utility alternatives get higher order infinitesimal probabilities. Together with the ease to achieve this equilibrium in a natural decision theory, it becomes an attractive choice.

[paulfchristiano]

Does this equilibrium notion differ meaningfully from proper equilibria?