Cooperative Oracles: Stratified Pareto Optima and Almost Stratified Pareto Optima

In this post, we generalize the notions in Cooperative Oracles: Nonexploited Bargaining to deal with the possibility of introducing extra agents that have no control but have preferences. We further generalize this to infinitely many agents. (Part of the series started here.)

Consider example 1 from the previous post: $P_{1}$ and $P_{2}$ are in a prisoners dilemma. Their utility functions are $U_{1} (p, q) = 2 q - p$ and $U_{2} (p, q) = 2 p - q$ . Their fair sets are $F_{1} = {(p, q) \in R | p \leq q}$ and $F_{2} = {(p, q) \in R | q \leq p}$ . We will introduce one extra player $P_{3}$ which has no options.

However, he will have preferences, $U_{3} = - U_{1} - U_{2}$ . Since he has no actions, his fair set must be everything.

Now, since the game is zero sum, every outcome is Pareto Optimal, so using the method described in the previous post, any equilibrium in which $p = q$ will be valid. We will modify the framework to make this no longer the case, and make $p = q = 1$ the only valid solution. For this, we will define a “stratified Pareto optimum.”

We will still have a finite number of players $P_{1}, \dots, P_{n}$ . Each player will specify a subset of players they will depend on. Let $D_{i}$ be set of players that $P_{i}$ depends on. $U_{i}$ must only be a function of the actions of players in $D_{i}$ , and $F_{i}$ must be closed under changing the actions of any player not in $D_{i}$ .

We define a preorder on the agents. We say that $P_{i} ≺ P_{j}$ if $P_{i} \in D_{j}$ , and we take the transitive closure, so $P_{i} ≺ P_{k}$ whenever $P_{i} ≺ P_{j}$ and $P_{j} ≺ P_{k}$ . We also say that $P_{i} ≺ P_{i}$ for all $i$ .

We say that $r^{'}$ is a stratified Pareto improvement over $r$ for player $P_{i}$ if:

$U_{i} (r^{'}) > U_{i} (r)$
$U_{j} (r^{'}) \geq U_{j} (r)$ for all $P_{j} ≺ P_{i}$
$r_{k}^{'} = r_{k}$ $P_{i} ⊀ P_{k}$

We say that $r$ is stratified Pareto optimal in $F \subseteq R$ for player $P_{i}$ if there is no alternate outcome $r^{'} \in F$ such that $r^{'}$ is a stratified Pareto improvement over $r$ for player $P_{i}$ . If $r$ is stratified Pareto optimal for all players, we say it is stratified Pareto optimal.

Claim: The set $F = ⋂_{i \leq n} F_{i}$ has a stratified Pareto optimum.

Proof: Consider some nonempty subset of players $S$ with the property that for all $P_{i}, P_{j} \in S$ , $P_{i} ≺ P_{j}$ , and there is no $P_{i} \in S$ , $P_{k} \notin S$ with $P_{k} ≺ P_{i}$ . We know that such a subset exists, since the preorder over players induces a poset over equivalence classes of players (where every player in an equivalence class transitively depends on every other player), and this poset must have a minimal element.

We then take an element of $\prod_{P_{i} \in S} Δ_{i}$ , which is Pareto optimal for all the players in $S$ . Note that it is important here that the players in $S$ have utility functions and fair sets that only depend on the other players in $S$ . We can then lock in all the players in $S$ as behaving according to this local Pareto optimum. We will treat them a constants, and effectively remove from the game, and repeat the process with the remaining players.

Take $r$ found by above process. Assume by way of contradiction that $r^{'}$ is a stratified Pareto improvement over $r$ for $P_{i}$ . Consider the set of players $P_{k}$ with $P_{k} ≺ P_{i}$ . We can restrict the game to only those players, which makes sense since these players only have utility functions and fair sets that refer to each other. Thus, we may assume without loss of generality that every player $P_{k} ≺ P_{i}$ . Thus $P_{i}$ is in the set of players locked in on the last step. Notice that in this case $r^{'}$ being a stratified Pareto improvement is equivalent to $r^{'}$ being a Pareto improvement for the players locked in on the last step, while fixing all the actions that were already locked in on previous steps, which contradicts the Pareto optimality of the distributions chosen in the last step. $□$

Now, we can give a new bargaining procedure, which is the same as from the previous post, except instead of choosing a Pareto optimal point in $F$ , we choose a stratified Pareto optimal point in $F$ . Observe that in the above 3 player game, we end up with the first two players cooperating, since they do not depend on the third player.

Unfortunately, the above construction depends heavily on the fact that there only finitely many players. Indeed, if you extend the above definitions to infinitely many players in the obvious way, stratified Pareto optima need not exist:

Consider a game with a player $P_{i}$ for all $i \in Z$ . Each player outputs a single probability $r_{i} \in Δ_{i} = [0, 1]$ of outputting $⊤$ (as opposed to $⊥$ ). The utility function $U_{i} (r)$ is just equal to $r_{i}$ , the probability that that player outputs $⊤$ . The fair set $F_{i}$ is the set of points such that either $r_{i} = r_{i - 1} / 2$ or $r_{i - 1} = 0$ . This is a valid fair set, since we can use the strategy $f (r) = r_{i}$ if $r_{i - 1} = 0$ and $f (r) = r_{i - 1} / 2$ otherwise, which is in fact Kakutani. Observe that $P_{i} ≺ P_{j}$ iff $i \leq j$ .

The set $F$ , which is the intersection of all the fair sets of all the players is still closed and nonempty. (And this is still true for arbitrary games with infinitely many players) We have that $r \in F$ if either $r_{i} = 0$ for all $i$ or if there is some first nonzero $r_{i}$ , and all $r_{j}$ for $j > i$ are equal to $r_{j} / 2^{j - i}$ . Either way, there is some $i$ such that $r_{j} = 0$ for all $j < i$ . Consider the stratified Pareto improvement $r^{'}$ for $P_{i}$ given by $r_{i}^{'} = 1$ , $r_{j}^{'} = 0$ for $j < i$ , and $r_{j}^{'} = 2^{i - j}$ for $j > i$ .

We therefore need a weaker notion than stratified Pareto optimal for infinitely many players. Note that we can still get stratified Pareto optima if there are no infinite descending chains of strict dependency. (e.g. if the above example grounded out and only had positive integers)

The way that we weaken stratified Pareto Optima is to take the (point wise) closure of the notion of stratified Pareto Optima for player $P$ . We say that $r$ is an almost stratified Pareto Optimum (ASPO) in $F$ for player $P$ if it is in the point wise closure of the set of all stratified Pareto optima for player $P$ . We say that $r$ is ASPO in $F$ if it is ASPO for $P$ for all players $P$ .

Claim: In a game with possibly infinitely many points, the set $F$ of fair points fair for all players is nonempty and there exists an ASPO in $F$ .

Proof: First, observe that for any finite subset of players, the set of points fair for all those players is compact and nonempty by the Kakutani fixed point theorem. By compactness, the set $F$ of points fair for all players is also compact and non-empty.

Now, observe that for any finite subset $S$ of players, there exists an $r \in F$ which is stratified Pareto optimal in $F$ for each all players in $S$ , using the argument from the finite case. Thus, the subset of $F$ which is ASPO for all players in $S$ is nonempty and compact. Again by compactness, this means that the subset of $F$ which is ASPO for all players is also nonempty and compact. Thus, there exists an $r \in F$ which is ASPO in $F$ for all players. $□$

At first this weakening may seem unnatural. Notice that the all 0′s vector in the above example is ASPO, even though there are many Pareto improvements and stratified Pareto improvements. (Locally, it is arbitrarily close to points with all small positive probabilities that cannot be improved.) However, we think that this condition is actually pretty natural, and the most you could hope for. The point of the players having Kakutani responses and continuous utility functions was to set them up to only have continuous(ish) access to the game state. We similarly need our notion of Pareto optimal to be such that you only violate the notion if you can point out a Pareto improvement in a continuous way, which roughly corresponds to taking the interior of the notion of Pareto improvement, and thus the closure of the notion of Pareto optimal.

In the next post, I plan to connect this up with the existing notion of reflective oracles, to define cooperative oracles.