(follow-up to: A correlated analogue to reflective oracles)

Motivation

Suppose players are playing in a correlated equilibrium using a reflective oracle distribution. How does the equilibrium they play in vary as a function of the parameters of the game, or of the players' policies? It turns out that the set of equilibria is a Kakutani map of the parameters to the game. This is a lot like it being a continuous map.

This might make it possible for players to reason about the effects of their policy on the equilibrium that they play (since the equilibrium is now a Kakutani map of the players' policies).

Definitions

Let $k$ be some natural number. We will consider reflective oracle distributions whose queries are parameterized on some vector in $\theta \in R^k$.

To do this, let the Turing machines $M$, instead of outputting a raw query, output a continuous function from $\theta \in R^k$ to the query. (The details of representing continuous functions don't seem that important). The reflectivity condition on oracle distributions is now relative to $\theta$ (since the queries depend on $\theta$).

Define the map

$$ParamsToDistrs\left(\theta \right):=\{D\in D|D\text{is reflective relative to}\theta \}$$

which maps the parameters $\theta$ to the set of reflective oracle distributions for $\theta$.

Theorem: $ParamsToDistrs$ is a Kakutani map.

Proof:

From the previous post, we have:

• For each $\theta$, $ParamsToDistrs\left(\theta \right)$ is nonempty (Theorem 1)
• For each $\theta$, $ParamsToDistrs\left(\theta \right)$ is convex (Theorem 2)

So it is sufficient to show that $ParamsToDistrs$ has a closed graph.

Let ${\theta }_1,{\theta }_2,...$ be an infinite sequence of $R^k$ values converging to ${\theta }_{\infty }$. Let $D_1,D_2,...$ be an infinite sequence of oracle distributions in $D$ converging to $D_{\infty }$. Assume that for each natural $n$, $D_n$ is reflective relative to ${\theta }_n$. We will show that $D_{\infty }$ is reflective relative to ${\theta }_{\infty }$; this is sufficient to show that $ParamsToDistrs$ has a closed graph.

Let $M\in M$. Let $a$ be such that $D_{\infty }\left(O\right(M)=a)>0$. Then $D_{\infty }\left(O\right(M)=a)>ϵ$ for some $ϵ>0$. By convergence, there is some $N$ such that for all $n\ge N$, $D_n\left(O\right(M)=a)>ϵ$. By reflectivity of each $D_n$ relative to ${\theta }_i$, we have, for each $n\ge N$,

$$a\in Eval\left(M\right)\left({\theta }_n\right)\left(Condition\right(D_n,M,a\left)\right)$$

Let $q^{\theta }:=Eval\left(M\right)\left(\theta \right)$. Rewriting the above statement:

$$a\in \arg \underset{i\in \{1,...,l(q\left)\right\}}{max}{E}_{D_n}\left[q_i^{{\theta }_n}\right(O\left)\right]$$

Consider the set $\left\{\right(\theta ,D)|a\in \arg {max}_{i\in \{1,...,l(q\left)\right\}}{E}_D[q_i^{\theta }\left(O\right)\left]\right\}$. This is the intersection of a finite number of sets of the form $\left\{\right(\theta ,D\left)|E_D\right[q_a^{\theta }\left(O\right)-q_i^{\theta }\left(O\right)]\ge 0\}$. Each of these sets is closed because $(\theta ,D)\mapsto E_D\left[q_a^{\theta }\right(O)-q_i^{\theta }(O\left)\right]$ is continuous. Therefore the set $\left\{\right(\theta ,D)|a\in \arg {max}_{i\in \{1,...,l(q\left)\right\}}{E}_D[q_i^{\theta }\left(O\right)\left]\right\}$ is closed.

In total, this is sufficient to show $a\in \arg {max}_{i\in \{1,...,l(q\left)\right\}}{E}_{D_{\infty }}\left[q_i^{{\theta }_{\infty }}\right(O\left)\right]$, as desired.

$\square$

An immediate consequence of this theorem is that the set of correlated equilibria of a normal-form game is a Kakutani map of the parameters of the game.