Intelligent Agent Foundations Forumsign up / log in
Cooperative Oracles: Stratified Pareto Optima and Almost Stratified Pareto Optima
post by Scott Garrabrant 196 days ago | Vadim Kosoy, Patrick LaVictoire and Stuart Armstrong like this | 8 comments

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)=2q-p\) and \(U_2(p,q)=2p-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,\ldots, 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\prec P_j\) if \(P_i\in D_j\), and we take the transitive closure, so \(P_i\prec P_k\) whenever \(P_i\prec P_j\) and \(P_j\prec P_k\). We also say that \(P_i\prec P_i\) for all \(i\).

We say that \(r^\prime\) is a stratified Pareto improvement over \(r\) for player \(P_i\) if:

  1. \(U_i(r^\prime)>U_i(r)\)
  2. \(U_j(r^\prime)\geq U_j(r)\) for all \(P_j\prec P_i\)
  3. \(r^\prime_k=r_k\) \(P_i\not\prec 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^\prime\in F\) such that \(r^\prime\) 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=\bigcap_{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\prec P_j\), and there is no \(P_i\in S\), \(P_k\not\in S\) with \(P_k\prec 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}\Delta_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^\prime\) is a stratified Pareto improvement over \(r\) for \(P_i\). Consider the set of players \(P_k\) with \(P_k\prec 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\prec P_i\). Thus \(P_i\) is in the set of players locked in on the last step. Notice that in this case \(r^\prime\) being a stratified Pareto improvement is equivalent to \(r^\prime\) 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. \(\square\)

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\mathbb{Z}\). Each player outputs a single probability \(r_i\in\Delta_i=[0,1]\) of outputting \(\top\) (as opposed to \(\bot\)). The utility function \(U_i(r)\) is just equal to \(r_i\), the probability that that player outputs \(\top\). 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\prec 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^\prime\) for \(P_i\) given by \(r^\prime_i=1\), \(r^\prime_j=0\) for \(j<i\), and \(r^\prime_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. \(\square\)

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.




This notion of dependency seems too binary to me. Concretely, let’s modify your example from the beginning so that \(P_3\) must grant an extra \(10^{-10}\) utility to either \(P_1\) or \(P_2\), and gets to decide which. Now, everyone’s utility depends on everyone’s actions, and the game is still zero-sum, so again, so any strategy profile with \(p=q\) will be a stratified Pareto optimum. But it seems like \(P_1\) and \(P_2\) should ignore still ignore \(P_3\).

reply

by Scott Garrabrant 195 days ago | link

I agree with this. I think that the most interesting direction of future work is to figure out how to have better notions of dependency. I plan on writing some on this in the future, but basically we have not successfully figured out how to deal with this.

reply

by Stuart Armstrong 191 days ago | link

Can you use the maximum “swing” from the other player’s decisions to get a non-binary measure of dependency?

It’s similar to my idea here.

Then the dependency of player \(P_i\) on \(P_j\) would be \(\max_{a_j} U_i - \min_{a_j} U_i\), where \(a_j\) are the actions of \(P_j\).

reply

by Stuart Armstrong 191 days ago | link

How about using some conception of “coalition-stable”? In which an option has that property if there is no sub-coalition of players that can unilaterally increase their utility, whatever all the other players choose to do.

reply

by Paul Christiano 187 days ago | Stuart Armstrong likes this | link

This is basically the core, though it’s usually defined for cooperative games, where (a) utility is transferrable and (b) adding a new player never makes an existing player worse off. It’s easy to generalize though.

reply

by Vadim Kosoy 163 days ago | link

In the infinite game example, I think that something doesn’t add up in the definition of \(f\). A single-valued Kakutani map into a compact space is just a continuous map, but \(f\) is not continuous.

reply

by Alex Appel 145 days ago | link

It looks legitimate, actually.

Remember, \(f\) is set-valued, so if \(r_{i-1}=0\), \(f(r)=[0,1]\). In all other cases, \(f(r)=\frac{r_{i-1}}{2}\). \(f\) is a nonempty convex set-valued function, so all that’s left is to show the closed graph property. If the limiting value of \(r_{i-1}\) is something other than 0, the closed graph property holds, and if the limiting value of \(r_{i-1}\) is 0, the closed graph property holds because \(0\in[0,1]\).

reply

by Vadim Kosoy 129 days ago | link

Hi Alex!

I agree that the multimap you described is Kakutani and gives the correct fair set, but in the OP it says that if \(r_{i-1}=0\) then \(f(r)=r_i\), not \(f(r)=[0,1]\). Maybe I am missing something about the notation?

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

This is exactly the sort of
by Stuart Armstrong on Being legible to other agents by committing to usi... | 0 likes

When considering an embedder
by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
by Abram Demski on Policy Selection Solves Most Problems | 0 likes

Looking "at the very
by Abram Demski on Policy Selection Solves Most Problems | 0 likes

Without reading closely, this
by Paul Christiano on Policy Selection Solves Most Problems | 1 like

>policy selection converges
by Stuart Armstrong on Policy Selection Solves Most Problems | 0 likes

Indeed there is some kind of
by Vadim Kosoy on Catastrophe Mitigation Using DRL | 0 likes

Very nice. I wonder whether
by Vadim Kosoy on Hyperreal Brouwer | 0 likes

Freezing the reward seems
by Vadim Kosoy on Resolving human inconsistency in a simple model | 0 likes

Unfortunately, it's not just
by Vadim Kosoy on Catastrophe Mitigation Using DRL | 0 likes

>We can solve the problem in
by Wei Dai on The Happy Dance Problem | 1 like

Maybe it's just my browser,
by Gordon Worley III on Catastrophe Mitigation Using DRL | 2 likes

At present, I think the main
by Abram Demski on Looking for Recommendations RE UDT vs. bounded com... | 0 likes

In the first round I'm
by Paul Christiano on Funding opportunity for AI alignment research | 0 likes

Fine with it being shared
by Paul Christiano on Funding opportunity for AI alignment research | 0 likes

RSS

Privacy & Terms