MIRIx Stanford report

post by jessicata (jessica.liu.taylor) · 2015-05-11T06:11:26.000Z · LW · GW · 2 comments

Contents

  Trembling hand perfect equilibrium
  Evidential game theory
  Correlated oracles
None
2 comments

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.

2 comments

Comments sorted by top scores.