MIRIx Stanford report

[jessicata]

This is a report from the second MIRIx at Stanford, which happened on Saturday May 9, 2015. The participants were Jessica Taylor, Alex Richard, Nate Thomas, James Cook, Helen Jiang, and Greg Nisbet.

We started by going over the reflective oracles/​game theory paper. Then we tried to find useful ways to apply game theory concepts to reflective oracles. Specificially, we looked at various game theory equilibria other than Nash equilibria and tried to see what they corresponded with in the setting of reflective oracles.

Trembling hand perfect equilibrium

Trembling hand perfect equilibrium is a variant of Nash equilibrium that forbids certain equilibria. Roughly, one could imagine that each player has a tiny chance of taking a random action, and require players’ actions to be rational even in this hypothetical. More formally, a Nash equilibrium is a trembling hand perfect equilibrium if there is a sequence of perturbed games (variants of the original game where each strategy must be played with at least $ϵ$ probability) converging to the original game whose Nash equilibria converge to the original Nash equilibrium. It is very straightforward to define the same notion for reflective oracles: we can define a sequence of “perturbed programs” that add a small amount of noise to oracle calls, with reflective oracles for each perturbed program converging to a trembling hand reflective oracle.

Evidential game theory

It is possible to define evidential game theory as a natural extension of evidential decision theory to game theory. Given $n$ players and a distribution $\Omega$ over pure strategy profiles, let $\omega \sim \Omega$ and define the utility for player $i$ taking action $a$ as $E\left[U_i\right(\omega )|{\omega }_i=a]$.

Let $\Omega$ be considered an $ϵ$-evidential equilibrium when, for each player, $E\left[U_i\right(\omega \left)\right]+ϵ\ge {max}_{a}E\left[U_i\right(\omega )|{\omega }_i=a]$.

We can say that $\Omega$ is an evidential equilibrium if there is a sequence of $ϵ$-evidential equilibria converging to $\Omega$ as $ϵ$ converges to 0. The use of $ϵ$ is necessary to avoid $0/0$ in conditional probabilities.

Mutual cooperation in the prisoner’s dilemma is actually a valid evidential equilibrium. To see why this is true, let ${\Omega }_i$ be a distribution that assigns $1/i$ probability to mutual defection and $(i-1)/i$ probability to mutual cooperation. Since the expected utility given that you cooperate is higher than the expected utility given that you defect, cooperating is the optimal action. We assign higher probability to both players cooperating as $i$ increases, so we can accordingly make $ϵ$ go to 0 in the limit, making this sequence converge to a distribution where the players always mutually cooperate.

Also note that every Nash equilibrium is an evidential equilibrium. This is because players’ actions are independent in a Nash equilibrium, so causal counterfactuals are the same as evidential counterfactuals.

While evidential game theory is not quite the UDT game theory that we would really like, it does seem to be related in that it allows an agent to take into account non-causal interactions between their action and others’ actions.

Correlated oracles

We attempted to define the equivalent of correlated equilibrium in the setting of reflective oracles.

An oracle could be described as a function of type $M\times Q\to [0,1]$. Alternatively, we could define an oracle distribution to be of type $\Delta (M\times Q\to \{0,1\left\}\right)$, a distribution over deterministic oracles. The reflection principle can be stated almost exactly as before. Let a distribution over deterministic oracles $\Omega$ be considered reflective iff $$P\left(M^O\right()=1)>p\Rightarrow P\left(O\right(M,p)=1)=1$$ $$P\left(M^O\right()=0)>1-p\Rightarrow P\left(O\right(M,p)=0)=1$$ where $O\sim \Omega$ is a random variable.

If we set up game theory the same way we did in the original reflective oracles paper, what resulting equilibrium do we get? This is not actually correlated equilibrium; rather, it’s an even more basic extension of Nash equilibrium. I don’t know if this has been studied, but I’ll call it a “joint Nash equilibrium” for the purposes of this post.

Let $\Omega$ be a distribution over pure strategy profiles. $\Omega$ is a joint Nash equilibrium iff, for each player $i$, any action in the support of ${\Omega }_i$ maximizes expected utility given that other players’ actions are distributed according to ${\Omega }_{-i}$. Because we construct causal counterfactuals for each of our actions, we ignore correlation between our actions and other players’ actions, but we still take into account correlation between other players’ actions.

This suggests that we may get additional equilibria (evidential equilibria, correlated equilibria, subjective correlated equilibria, coarse correlated equilibria) by asking different counterfactuals. The counterfactuals must not be causal counterfactuals, because this would lead to equilibria that ignore the correlation between our action and others’ actions. We ran out of time before figuring out how to construct these counterfactuals.

[orthonormal]

I think that evidential equilibria are equivalent to a much simpler property.

If $(a,b)$ is a joint strategy such that for each $a^{\prime }\ne a$ there exists $b^{\prime }$ such that $U(a^{\prime },b^{\prime })\le U(a,b)$, then $(a,b)$ is an evidential equilibrium. (Construct the probability distributions which assign $\delta$ mass to each $(a^{\prime },b^{\prime })$ and the rest to $(a,b)$, and let $\delta \to 0$.) And the converse is trivial too.

Am I missing something here?

[jessicata]

Yeah, it seems pretty likely that the definition I gave is wrong. Here’s an alternative:

A totally mixed evidential equilibrium must (a) assign nonzero probability to each outcome and (b) have each player maximize evidential expected utility. An evidential equilibrium is a totally mixed evidential equilibrium or a limit of them.

I’m pretty sure you can still have mutual cooperation on the prisoner’s dilemma, by iteratively changing probabilities assigned to C/​C C/​D D/​C D/​D so that players are indifferent between C and D in each totally mixed equilibrium.

EDIT: this one also seems wrong. It might be possible to create something similar to trembling hand perfect equilibria, where we have a sequence of perturbed games with people maximizing evidential utility on each perturbed game.