(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 be some natural number. We will consider reflective oracle distributions whose queries are parameterized on some vector in .

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

Define the map

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

Theorem: is a Kakutani map.

Proof:

From the previous post, we have:

  • For each , is nonempty (Theorem 1)
  • For each , is convex (Theorem 2)

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

Let be an infinite sequence of values converging to . Let be an infinite sequence of oracle distributions in converging to . Assume that for each natural , is reflective relative to . We will show that is reflective relative to ; this is sufficient to show that has a closed graph.

Let . Let be such that . Then for some . By convergence, there is some such that for all , . By reflectivity of each relative to , we have, for each ,

Let . Rewriting the above statement:

Consider the set . This is the intersection of a finite number of sets of the form . Each of these sets is closed because is continuous. Therefore the set is closed.

In total, this is sufficient to show , as desired.

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.

Oracle AI
Personal Blog

1

New Comment