Cooperative Oracles

The long-awaited continuation of this sequence.

Credit to Sam, Tsvi, Nisan, Scott, me, and Giles (who helped make the figures)

It may or may not become a paper, but if it doesn’t, it’s best for it to not be locked in a folder of drafts. This will also recap material from previous posts and papers.

Refresher on Reflective Oracles

Let $M$ denote an arbitrary probabilistic Turing machine with oracle access, and $M^{O}$ refer to the same machine equipped with the oracle $O$ . It is important to remember that $M$ refers to a randomized algorithm, while $M^{O}$ refers to the algorithm equipped with a particular oracle, so it doesn’t make sense to ask what the output of $M$ is, only what the output of $M^{O}$ is.

Reflective oracles as originally defined here are oracles which accurately answer queries about whether a probabilistic Turing machine with access to the same oracle, $M^{O}$ , output a 1 with probability greater than or less than $p$ , by outputting 1 for “yes”, 0 for “no”, and randomizing between the two if the probability of $M^{O}$ outputting 1 is exactly $p$ . This is more expressive than it may seem at first, because it is possible to query the oracle about a probabilistic oracle machine that runs $M^{O}$ and checks whether the output has some arbitrary computable property.

It is also possible to use reflective oracles to make the probability distribution over the output of one algorithm vary continuously with respect to the probability distribution over the output of another algorithm, via repeated oracle calls and randomization, as demonstrated here.

Reflective oracles can be thought of as akin to halting oracles, except that they accurately answer questions about the class of probabilistic Turing machines with access to the same oracle, which halting oracles cannot do. If the diagonalization argument against the existence of a halting oracle is applied to a reflective oracle, where an algorithm invokes the oracle on itself, and outputs the bit which it is the least likely to output, a reflective oracle will randomize between outputting 0 and 1, but for any $p < 0.5$ , if the oracle is asked whether the algorithm outputs 1 with greater than probability $p$ , it will respond “yes”.

This ability to accurately answer questions about themselves makes reflective oracles well-suited for studying the unbounded computing power limit of game theory, and situations where an agent reasons about a surrounding environment which contains itself. In particular, if a set of agents in a game all use a reflective oracle to perfectly predict the behavior of all other agents in the game, and then select the optimal action, a Nash equilibrium will be played in the game. This will be called the shortsighted best response algorithm.

To begin, there is a canonical way to translate any game theory problem into the setting of probabilistic oracle machines. As a concrete example, take a game of Prisoner’s Dilemma, with an exchange of source code between agents. Let $p l a y e r_{A}$ and $p l a y e r_{B}$ refer to the source code of the two players in a Prisoner’s Dilemma game. Then the game may be thought of as the two probabilistic oracle machines $p l a y e r_{A} (‘ ‘ p l a y e r_{B} ")$ and $p l a y e r_{B} (‘ ‘ p l a y e r_{A} ")$ calling the reflective oracle on each other, and outputting 0 for “defect” and 1 for “cooperate”. In general, any game can be expressed by expressing all players as a pair of two algorithms, one of which outputs a strategy, and one of which takes no input and computes the utility via oracle calls. By fixing a suitable input for the algorithm which generates the strategy, which represents the information a player has, all strategy algorithms become inputless probabilistic oracle machines which make oracle calls to other players.

More formally, let a player $P$ be a pair of a probabilistic oracle machine $M$ , and a probabilistic oracle machine $U$ which halts with probability 1 regardless of the choice of oracle, and outputs 0 or 1. $M$ is interpreted as the algorithm which produces the strategy of the player, and $U$ is interpreted as the utility function. Fixing an oracle $O$ , the probability of $U^{O}$ outputting 1 is the utility of the player $P$ .

There are many different variants of a reflective oracle, which are essentially equivalent. There is the standard single-bit reflective oracle, presented here but multi-bit reflective oracles may also be defined. Here, I used the semimeasure formulation of reflective oracles, which accurately answers any question about prefixes of a Turing machine output, and assume that the outputs of the Turing machine form a semimeasure over the set of finite bitstrings.

Instead of the queries consisting of a ${M, p}$ pair, they consist of a ${P, p, x}$ triple, asking about the probability of the $M^{O}$ component of $P^{O}$ halting with a bitstring that has $x$ as a prefix. Let $P (P^{O} = x y)$ be the probability that $M^{O}$ halts with a bitstring that has $x$ as a prefix, and let $P (P^{O} = \neg x y)$ be the probability that $M^{O}$ halts with a bitstring that doesn’t have $x$ as a prefix. Let $q_{O} (P, p, x)$ be the probability of the oracle $O$ returning a 1 in response to the query $(P, p, x)$ . Then one of the defining properties of a reflective oracle is that, for all bitstrings $x$ , rational probabilities $p$ , and players $P$ :

$P (P^{O} = x y) > p \to q_{O} (P, p, x) = 1$

$P (P^{O} = \neg x y) > (1 - p) \to q_{O} (P, p, x) = 0$

If a probabilistic oracle machine halts with a certain probability distribution, it will be accurately captured by this variant of reflective oracle, but nonhalting probability mass may be assigned to an arbitrary distribution over bitstrings, as long as it makes a semimeasure.

Cooperative Oracles:

In the particular case where the two agents in a Prisoner’s Dilemma both use shortsighted best response, the set of fixed points is the set of Nash equilibria, so they will mutually defect.

However, different algorithms may be used by the players. As long as each player’s set of responses to everyone else’s strategies is nonempty, convex, and has closed graph, Kakutani’s fixed point theorem guarantees the existence of an “equilibrium set” where all players respond to knowledge of all other player strategies with the exact strategy that all other players predicted. This is the same as the fair set from here.

If we consider two agents in the Prisoner’s Dilemma implementing the algorithm “cooperate with the same probability as my opponent cooperates”, there is a continuum of reflective oracles for all probabilities of cooperation in $Q \cap [0, 1]$ . Intuitively, mutual cooperation should be selected. This splits the problem of formalizing Functional Decision Theory in the unbounded case into the problem of finding an algorithm for the agent to use, and the problem of finding an oracle which causes a Pareto optimal element of the equilibrium set to be played.

A naive implementation, where we select a reflective oracle that is Pareto optimal for all players, fails. This is because all utility functions have an opposing one, which makes all outcomes Pareto optimal, because there is no outcome that makes one player better off without making another player worse off. In the Prisoner’s Dilemma, if there is a third player, a jailer who wants to maximize jail time, but cannot otherwise influence the outcome of the game, all outcomes are Pareto optimal, because there is no choice which makes a prisoner better off that doesn’t also leave the jailer worse off, and vice-versa. Therefore, the optimality notion must somehow restrict to the set of players who are actually participating in a game, instead of the set of all players.

To clarify what it means to talk about the set of players who participate in a game, we can look at the structure of which players make oracle calls to other players. If there is a game with finitely many players, the utility functions of all players should make oracle calls to the output of all players, to compute a utility.

Let the dependency set of player $P_{i}$ be the set of all players that either the strategy algorithm or the utility function of $P_{i}$ may query the oracle about, as well as $P_{i}$ itself. Let the relation $≺$ be the minimal relation such that if $P_{j}$ is in $P_{i}$ ’s dependency set, $P_{i} ≺ P_{j}$ . The transitive closure of this relation, $⪯$ , induces a poset over equivalence classes of players.

Minimal elements in this poset correspond to sets of players whose strategies and utility functions only depend on each other. Players in a self-contained game have this property. A non-minimal equivalence class in this poset corresponds to a game where the utility functions of some participants are affected by what happens in a different game they cannot influence. Due to these properties, $⪯$ is a natural choice to define the boundaries of a game, and to formalize the desideratum that our notion of optimality should not be Pareto optimal for spectators.

Now, the notion of stratified Pareto optimality may be defined. Let $U_{O, i}$ be the utility of the player $P_{i}$ , upon being equipped with the oracle $O$ . A reflective oracle $R O^{'}$ is a stratified Pareto improvement on another reflective oracle $R O$ , for a player $P_{i}$ , iff:

(1): $U_{R O, i} < U_{R O^{'}, i}$

(2): $P_{j} ⪯ P_{i} \to U_{R O, j} \leq U_{R O^{'}, j}$

(3): $P_{i} ⪯/ P_{j} \to U_{R O, j} = U_{R O^{'}, j}$

The first condition is that a stratified Pareto improvement for $P_{i}$ must make $P_{i}$ better off.

The second condition is that all players that $P_{i}$ depends on, even indirectly, must be unaffected or better off. In the case of a finite and minimal equivalence class of players under $⪯$ , this says that all other players in the game must be unaffected or better off, so all stratified Pareto improvements are Pareto improvements for this game. In the case of the jailer in the Prisoner’s Dilemma, it says that both prisoners must receive the same or greater utility, because the jailer’s utility function makes an oracle query about their output.

The third condition is that a change in oracles should only affect players whose strategy algorithm or utility function depends on the outcome of a game, and leave all other players unaffected. This condition is used to forbid cases where selecting a better oracle in a game of Stag Hunt makes the players in a totally unrelated game of Chicken worse off, because the same oracle is used by all players.

A point is stratified Pareto optimal (SPO) for a set of players $P_{G}$ if there are no stratified Pareto improvements for any players in $P_{G}$ . In the particular case of a Prisoner’s Dilemma with a jailer, a stratified Pareto optimum will involve both prisoners selecting a Pareto optimal outcome in their equilibrium set, and ignoring the jailer.

However, even stratified Pareto optima aren’t enough in all cases, by the case of the chain of infinitely many players detailed here

Let an almost stratified Pareto optimum for a set of players $P_{G}$ be a reflective oracle that is in the closure of the set of stratified Pareto optimal oracles for all players in $P_{G}$ . In the case of the infinitely descending chain of players, an almost stratified Pareto optimal reflective oracle would report that all players had probability 0 of outputting 1, because that is the limit of a sequence of SPO oracles for a player, which move the “first player which outputs 1” arbitrarily far back in the sequence.

Theorem 1 (weak form): There exists a reflective oracle that is almost stratified Pareto optimal for all players.

A proof sketch for Theorem 1 is as follows:

Given an arbitrary finite set of players, $P_{G}$ , there is a finite poset of equivalence classes of players in $P_{G}$ under $⪯$ . Given some initial set of reflective oracles, it is possible to construct a subset that is Pareto optimal for all players in a minimal equivalence class $E$ , and a Pareto optimal subset of that for a minimal equivalence class $F$ in the poset with $E$ removed from it, and so on. This process repeats until there is a set of SPO reflective oracles for all players in $P_{G}$ . Now that existence has been shown, take the closure of the set of SPO reflective oracles for $P_{G}$ . The resulting set is a compact set of ASPO reflective oracles for $P_{G}$ . This argument works for all finite $P_{G}$ . Because there is a compact and nonempty set of ASPO reflective oracles for all finite sets of players, by compactness, there must be a compact and nonempty set of ASPO reflective oracles for all players.

This is pretty much the old proof of “there’s an ASPO point for all players”, the only difference is that this proof takes place in reflective-oracle space, instead of the space of the actions of all players. Let a weak cooperative oracle be a reflective oracle with this property.

Let a well-founded equivalence class $E$ be an equivalence class of players under $⪯$ composed of finitely many players, such that players within $E$ only make oracle calls to other well-founded equivalence classes. Minimal equivalence classes under $⪯$ , of finitely many players, are well-founded. It is possible to strengthen Theorem 1 to:

Theorem 1: There exists a reflective oracle that is ASPO for all players, and SPO for all players in a well-founded equivalence class.

This is proved by constructing a suitable set of reflective oracles that are SPO for all players in a well-founded equivalence class, and then using this as the initial set in the previous proof sketch. The resulting set of ASPO reflective oracles is a subset, and inherits this property.

An oracle of this type is called a strong cooperative oracle. Almost all games of interest in game theory involve finitely many players playing against each other. This is the condition for a minimal finite equivalence class under $⪯$ , all of which are well-founded. Therefore, a strong cooperative oracle is an SPO oracle for any reasonable game that doesn’t have non-well-founded chains of infinitely many players.

However, the proof of the existence of a cooperative oracle involves the infinite-dimensional space of reflective oracles, so it is not immediately linked to practical game theory. By imposing several natural conditions, it is possible to link the two settings. (Also, it is unclear whether the final condition of strategy continuity is necessary).

Theorem 2: In a game of finitely many players, which all have finitely many possible outputs, have oracle access to each other and no other players, halt with probability 1 given oracle access to the other players, and have continuous strategies w.r.t everyone’s probability distribution over outputs, all points in the equilibrium set have reflective oracles which result in that point being played in the game.

Corollary 2: If the conditions of Theorem 2 hold, then for any point on the Pareto frontier of the equilibrium set, there is a strong cooperative oracle which results in that point being played in the game.

Therefore, the equilibrium selection problem is solved by the use of a special type of reflective oracle which results in Pareto optimal outcomes within the equilibrium set whenever it is used, aka a strong cooperative oracle.

However, there is still an open question about which algorithms result in something “FDT-like” when used with a cooperative oracle. To make partial progress towards a result, we will now look at the Ultimatum Game. In the Ultimatum Game, there is a pool of money, such as 100 dollars, and player A specifies a split of money between player A and player B, and then player B can either choose to accept the offer, or reject it, in which case both players get 0 dollars.

Imagine player B is implementing the strategy “I will reject the money unless I get 90 dollars or more”. If player A would offer a ¹⁰⁄₉₀ split in response to this strategy, and this is known to player B, this provides an incentive for player B to implement this extortionate strategy. Similarly, by viewing the game from the perspective of player B, accepting a split of money where 90 dollars goes to player A incentivises player A to offer a ⁹⁰⁄₁₀ split.

Additionally, if the strategies of player A and player B act to acquire 90 dollars, by proposing a ⁹⁰⁄₁₀ split, and rejecting all offers short of a ¹⁰⁄₉₀ split, the game outcome will be A offering a ⁹⁰⁄₁₀ split, and B rejecting it, so both players walk away with no money. Extortionate strategies fail when they go against each other.

Is there a strategy that does not incentivize extortion? There is, in a certain sense, as long as there is some notion of a “fair outcome”, such as the Nash bargaining solution. As an example, in the Ultimatum Game, if a ⁵⁰⁄₅₀ split is considered to be a fair outcome by player B, they could implement the strategy “if the money I am offered, $x$ , is less than 50 dollars, reject the offer with a $\frac{y (50 - x)}{100 - x}$ probability, where $1 \leq y \leq 2$ ”. Against this strategy, the optimal offer is a ⁵⁰⁄₅₀ split of money, because in expectation, money is lost by offering any split that is more self-favoring than ⁵⁰⁄₅₀. Each marginal dollar that goes towards player A in the initial split is compensated by an increase in the probability of player B rejecting the offer, making the expected value of taking one more dollar from the split zero or negative. Therefore, extortion beyond the “fair outcome” is disincentivized.

Another advantage of this strategy is that it is robust against different agents having different notions of a “fair outcome”. If player A thinks that a ⁶⁰⁄₄₀ split is a fair outcome, and player B thinks that a ⁵⁰⁄₅₀ split is a fair outcome, and $y = 1$ , then player B will reject the offer with a $\frac{1}{6}$ probability, leading to an expected gain of 50 dollars for player A and $33 \frac{1}{3}$ dollars for player B, instead of a guaranteed rejection of the offer.

Red is the strategy of player A, blue is the strategy of player B, the display is over utility-space, player B is implementing a coercion-proof strategy.

However, this class of strategies does not have an elegant way of a-priori selecting the “fair point” that it will attempt to enforce. Intuitively, in the Ultimatum Game, there’s a tradeoff where enforcing a strict demand, like an ³⁰⁄₇₀ split, means that there are more possible opponents which will reject the offer, while enforcing a weak demand, like a ⁷⁰⁄₃₀ split, means that there are more possible opponents which will exploit this. The Nash bargaining solution is a candidate “fair point”, but it is unknown whether there is an algorithm that would naturally attain it under appropriate circumstances.

The insight of “be increasingly vengeful when the opposing players cause you to lose utility” will likely be a component of the true solution, and generalizes to other games such as the Prisoner’s Dilemma and Chicken, but it is not a complete account, as will be shown in the next section. Humans also seem to act according to this strategy to some degree, instead of following the Homo Economicus strategy of accepting any offer greater than 0 dollars.

On the Prisoner’s Dilemma, a natural choice for an extortion-proof strategy is “cooperate with the same probability that the opponent cooperates”. This leads to mutual cooperation against a copy of itself, when equipped with a cooperative oracle, as seen in Figure 2.

Prisoner’s Dilemma, mutual cooperation is the Pareto-optimal point in the equilibrium set where the strategies intersect.

If the probability of player A cooperating is $x$ , then if player B implements the strategy “cooperate with probability $max (x - ε, 0)$ for some $ε > 0$ ”, mutual defection will occur, as that is the only fixed point. This appears suboptimal, but permitting exploitation, even in a mild form, incentivizes opponents to modify their strategy to an exploiting strategy. If Player B uses shortsighted best response, then mutual defection will occur. This is because player B will always play defect because it is a dominant strategy, and player A will play defect as retaliation. If Player B always cooperates, then Player A will cooperate as well. This shows that implementing an extortion-proof strategy is not enough. A satisfactory strategy should lead to defection against a player which cooperates regardless of opponent.

A similar strategy applies to the game of Chicken. The strategy is “play Straight with the same probability that the opponent plays Straight, unless the probability of them playing Swerve is greater than $\frac{5}{6}$ , in which case, play Straight.” This leads to crashing into an opponent which goes straight, which incentivizes the opponent to avoid strategies such as tossing their steering wheel out the window. If two agents of this type play against each other, then by Figure 3, they both get $\frac{25}{12}$ expected utility with a $\frac{5}{6}$ probability of swerving. This is a Pareto improvement on the mixed-strategy Nash equilibrium where both players get 2 expected utility with a $\frac{2}{3}$ probability of swerving. If this player plays against a player B using shortsighted best-response, a cooperative oracle will result in the outcome where player A goes straight and player B swerves, for an expected utility of 3 and 2, respectively.

The game of chicken.

Consider the cooperation game where player A has a preference for going to a movie, and player B has a preference for going home to play a board game. They also have a preference for going to the same event, and going to a movie leads to nonzero utility even if the moviegoer is alone.

If both players implement the strategy “consult the oracle, and go to whichever event the other player has a higher probability of going to, with a rapid change of strategy around 50 percent”, then the Pareto frontier of the equilibrium set consists of the two points where both players coordinate on an action. The choice of cooperative oracle determines which action is selected, and coordination occurs because both players are using the same oracle. This is similar to the choice of reflective oracle determining which Nash equilibrium is played in a game.

A cooperation game. Of the 3 points in the equilibrium set, the choice of cooperative oracle ensures that the outcome is coordination on an activity.

By looking at these examples, there are two further directions for designing a strategy which effectively makes use of a cooperative oracle. The first direction is developing a general criteria which allows a player to exploit some exploitable opponents. In the Prisoner’s Dilemma, against an opponent which cooperates with 10 percent greater probability than you cooperate, the desired action is to cooperate with 90 percent probability. The second direction for improvement is finding a single decision rule, like $a r g m a x$ for Nash equilibria, that produces an exploitation-proof strategy incentivizing opponents to play at a Pareto optimal point, instead of customizing a strategy of that type for each game separately.

(Proofs were omitted because they’re quite long. I can post them if there is interest.)