Distributed Cooperation

post by Diffractor · 2018-03-18T05:46:56.000Z · LW · GW · 2 comments

Contents

    Definitions:
  Cell Set and Cell Product:
  Game Theory Definitions, With Cells:
    The Procedure:
    Proof of Above-Mentioned Hard Part:
None
2 comments

Reflective oracles can be approximated by computing Nash equilibria. But is there some procedure that produces a Pareto-optimal equilibrium in a game, aka, a point produced by a Cooperative oracle? It turns out there is. There are some interesting philosophical aspects to it, which will be typed up in the next post.

The result is not original to me, it's been floating around MIRI for a while. I think Scott, Sam, and Abram worked on it, but there might have been others. All I did was formalize it a bit, and generalize from the 2-player 2-move case to the n-player n-move case. With the formalism here, it's a bit hard to intuitively understand what's going on, so I'll indicate where to visualize an appropriate 3-dimensional object.

---

Definitions:

First, we will define cell sets and cell products.

Cell Set and Cell Product:

A family of sets is a cell set of some convex polytope in finite-dimensional euclidean space, iff all elements of the family are compact convex polytopes, the union of the family equals the original convex polytope, and for all pairs of elements of the family, the intersection has Lebesgue measure 0.

More intuitively, a cell set is just a set of cells where they perfectly cover some space you want, the cells only overlap at boundaries, and the cells are all finitely big, convex, and include their boundaries (so a point may be part of multiple cells if it's on a boundary, that's intentional). If you make a big cube out of a bunch of little cubes arranged in a space-filling honeycomb pattern, the set of all those little cubes is a cell set of the big cube.

Now the cell product will be defined. Fix two cell sets, $A^{\diamond }$ and $B^{\diamond }$. Index their elements with the index sets $I_A$ and $I_B$. Let $C_{A,i}$ be the cell in $A^{\diamond }$ with the index $i\in I_A$. Define the cell product $\tilde{\times }$ as follows:

$$A^{\diamond }\tilde{\times }{B}^{\diamond }:=\{C_{A,i}\times C_{B,j}|(i,j)\in I_A\times I_B\}$$

This family of sets has the following properties:

1: All elements are compact convex polytopes, because the product of two convex compact polytopes is a convex and compact polytope.

2: Given a point in $A\times B$, the projection of that point to $A$ lies inside some cell in $A^{\diamond }$, and the same goes for $B$. Therefore, the point lies in the cell that is the product of the cells in $A^{\diamond }$ and $B^{\diamond }$ it was projected into. Similarly, given some arbitrary point in an arbitrary cell of the product, that cell is associated with a pair of indices, so the projection of the point to the space containing $A$ lies in the cell associated with the first index, so it lies in $A$. A similar argument applies for $B$. Therefore, the union of all cells in the cell product of $A^{\diamond }$ and $B^{\diamond }$ equals the space $A\times B$.

3: The intersection of two cells with indices $(i,j)$ and $(k,l)$ is the product of the intersection of cell $i$ and cell $k$, and the intersection of cell $j$ and cell $l$. All these intersections have Lebesgue measure 0, so the intersection of those two cells must also have Lebesgue measure 0.

Therefore, the cell product of any two cell sets $A^{\diamond }$ and $B^{\diamond }$ is a cell set of $A\times B$.

Now, let's visualize a concrete example of a cell product. Let $A$ be the unit side length triangle, and $A^{\diamond }$ be the set of $ϵ$-length triangles in the triangular tessellation of $A$. Let $B$ be the unit length line segment, and $B^{\diamond }$ be the set of $ϵ$-length line segments that go end-to-end to cover the unit length line segment. The set $A\times B$ would be a unit side length triangular prism.

The cell product $A^{\diamond }\tilde{\times }{B}^{\diamond }$ would be the set of little triangular prisms of side length $ϵ$. These little cells completely fill the big triangular prism, each one of them is the product of a cell from $A^{\diamond }$ and a cell from $B^{\diamond }$, and all pairs of indices from the index sets correspond to a unique little triangular prism.

Given a sequence of $m$ cell sets, let $A_{\le m}^{\diamond }$ be the cell product of the sequence.

$$A_{\le m}^{\diamond }:=\widetilde{\prod _{k\le m}}{A}_k^{\diamond }$$

Game Theory Definitions, With Cells:

${\Delta }_m$ is the probability distribution over possible moves for player $m$. ${\Delta }_m\left(A\right)$ is the probability of player $m$ playing move $A$

$S:={\Delta }_1\times {\Delta }_2...\times {\Delta }_n$ is the space of strategies for the finite game, a product of probability distributions over finitely many moves for each player.

$ϵ$ is some small finite number of the form $\frac{1}{x}$ where x is a large integer.

Given some probability distribution ${\Delta }_m$, divide it into cells as follows:

Slice it along the lines/planes/spaces where ${\Delta }_m\left(A\right)=ϵ,2ϵ...,1-ϵ$, and the lines/planes/spaces where ${\Delta }_m\left(B\right)=ϵ,2ϵ...,1-ϵ$, and so on. As a simple example, in the 2-move case, this is splitting a line segment into smaller line segments, in the 3-move case, this is splitting a triangle into smaller triangles via a triangular tiling, and in the 4-move case, this is splitting a tetrahedron into tetrahedra and octahedra via the tetrahedral-octahedral honeycomb.

${\Delta }_m^{\diamond }$ is the resulting cell set of ${\Delta }_m$. Let $I_m$ be the index set for some indexing of the cells in ${\Delta }_m^{\diamond }$.

$S^{\diamond }$ is defined in the obvious way, as the cell product of the cell sets for each player, which is also a canonical cell set for $S$.

Let $\overrightarrow{I}:={\prod }_{m\le n}{I}_m$. This is the index set for $S^{\diamond }$. An element of this set, $\overrightarrow{i}$, specifies a particular cell $C_{\overrightarrow{i}}\in S^{\diamond }$. Let ${\overrightarrow{i}}_m$ be the $m$'th element of the sequence $\overrightarrow{i}$. This is an element of $I_m$ and specifies a particular cell $C_{{\overrightarrow{i}}_m}\in {\Delta }_m^{\diamond }$.

Given a point $s\in S$, let $s_k\in {\Delta }_k$ be the $k$'th component of the point.

A Kakutani strategy for player $m$ is a function $f_m:S\to P\left({\Delta }_m\right)$ that is nonempty, convex, and has closed graph, for all inputs.

If all players are using a Kakutani strategy, then the function $f$ where $f\left(s\right):={\prod }_{m\le n}{f}_m\left(s\right)$ is nonempty, convex, and has closed graph, for all inputs, and by Kakutani's fixed point theorem, there are some fixed points in $S$.

Given a Kakutani strategy $f_m$ for player $m$, let the function $F_m:S\to P\left(S\right)$ be the function such that:

$$F_m\left(s\right):=\left(\prod _{k\le n,k\ne m}\right\{s_k\left\}\right)\times f_m\left(s\right)$$

This could be thought of as the function where everyone else has locked in their move, and only player $m$ may respond with some other move.

A cell is ruled out by player $m$ if there is no point $s$ in the cell such that $s\in F_m\left(s\right)$. Pretty much, no matter the point in the cell, if everyone else tries to play it, player $m$ will go "nope, not playing this point". If a cell is ruled out by some player, the fixed point of $f$ cannot lie within that cell.

Given some utility function for each player over the outcome of the game, $\overrightarrow{U}\left(C_{\overrightarrow{i}}\right)$ is the utility vector made of the utility each player attains, assuming the center point of the cell $C_{\overrightarrow{i}}$ is played in the game. Yes, not all points in $C_{\overrightarrow{i}}$ attain the same utility, but for a sufficiently small $ϵ$, the cell is really small, and for any player, the utility over the cell is well-approximated by the utility attained at the middle point in the cell. $\overrightarrow{U}(C_{\overrightarrow{i}}{)}_m$ is the utility that the $m$'th player attains.

Every player also has a ranking of cells, $R_m:S^{\diamond }\to N$ that works as follows:

$$\overrightarrow{U}(C_{\overrightarrow{i}}{)}_m<\overrightarrow{U}(C_{{\overrightarrow{i}}^{\prime }}{)}_m\to R_m\left(C_{\overrightarrow{i}}\right)<R_m\left(C_{{\overrightarrow{i}}^{\prime }}\right)$$

In short, the ranking is ordered by player $m$'s utility function first and foremost.

Also, if $C_{{\overrightarrow{i}}^{\prime }}$ is a Pareto improvement on $C_{\overrightarrow{i}}$, then

$$R_m\left(C_{\overrightarrow{i}}\right)<R_m\left(C_{{\overrightarrow{i}}^{\prime }}\right)$$.

This can be extended to a ranking of a subset of cells in the obvious way, by just removing all cells outside of the subset.

The Procedure:

The following game is played: There is a set of ruled out cells in $S^{\diamond }$. A random number generator is consulted, and used to assign every player a set of ruled out cells that they are responsible for. The players may modify their strategy $f_m$ to whatever they want, subject to three constraints.

1: Their new strategy must be a Kakutani function.

2: Their new strategy must rule out all cells that they are responsible for.

3: The set of cells that haven't been ruled out yet, that their new strategy rules out, must be an initial segment of the ranking made by applying $R_m$ to the set of cells that aren't ruled out.

If there is a player who cannot modify their strategy accordingly, or if no additional cells can be removed, then the game repeats with a new random assignment, and only ends if one cell is left.

The starting set of ruled out cells is $\varnothing$.

Intuitively, the game is something like "everyone sorts the list of outcomes by their own utility first, and by everyone else's second, and then you loop through game rounds where everyone has to implement a realistic strategy that rules out some strategies that someone else has vowed to rule out first, and also rules out personally abhorrent points if it's possible, until it's narrowed down and everyone agrees which cell to play".

This isn't quite as cooperative as it seems. Sorting equivalent outcomes by Pareto-optimality for everyone else isn't motivated by purely selfish interest, but it's at least compatible with it. Everyone can simulate what strategy everyone else picked, so everyone knows which cells have gotten ruled out. And taking responsibility for ruling out someone else's cells isn't really an imposition, because if the game ended right there, those cells couldn't possibly have been played anyways.

If this process eventually converges to one cell remaining, then the cell must be on the Pareto frontier of the set of cells. The argument is very simple. If there was a Pareto improvement on the final cell, then it would have had a higher rank than the final cell in everybody's ranking, so it can't possibly have been eliminated.

The hard part is showing that this process eventually converges to one cell remaining and doesn't get stuck. It will be proved by assuming there are at least 2 cells that have not been ruled out, and showing that there exists an assignment of cells to players that result in at least one more cell getting ruled out, so the game can always progress.

Proof of Above-Mentioned Hard Part:

Let $C_R$ be the set of ruled-out cells.

Assuming there is some cell $C_{{\overrightarrow{i}}^{\prime }}$ being used as a backup cell:

Let the domain of player $m$, be the set of cells

$$D_m:=\left({\Delta }_{\le m}^{\diamond }\tilde{\times }\widetilde{\prod _{m<k\le n}}\right\{C_{{\overrightarrow{i}}_k^{\prime }}\left\}\right)/\left({\Delta }_{<m}^{\diamond }\tilde{\times }\widetilde{\prod _{m\le k\le n}}\right\{C_{{\overrightarrow{i}}_k^{\prime }}\left\}\right)$$

By the way the cell product was defined, both of these sets are subsets of $S^{\diamond }$. To visualize it, consult this image of a cube in Minecraft. The glowstone is the backup cell, the green is the domain of player 3, the black is the domain of player 2, and the purple is the domain of player 1. This can be verified by plugging $m=n=3$ into the definition of domain. The first half of the domain specifies all the cells in the cube, and the second half specifies the plane of cells where their third coordinates equal the third coordinate of the cube, ${\overrightarrow{i}}_3^{\prime }$. Thus, all the cells that don't share the same plane as the backup point are green/in the domain of player 3. For $m=2,n=3$, this equation specifies the plane of black cells, minus the column of purple cells. And so on.

Let the ruled out cells for player $n$ be $C_R\cap D_n$, the ruled out cells for player $n-1$ be $C_R\cap D_{n-1}$, and so on.

Fix some $\delta <<ϵ$. Consider the function $f_m$ that takes a point $s$ as input, measures the distance $d$ to the nearest cell in $C_R\cap D_m$, gets the point $s_m\in {\Delta }_m$, and plays the point that is $max(\frac{-d}{\delta }+1,0)$ distance along the vector between $s_m$ and the center point of $C_{{\overrightarrow{i}}_m^{\prime }}\in {\Delta }_m^{\diamond }$.

This function is nonempty for all inputs. It is convex for all inputs because it plays a set consisting of a single point. It has closed graph because it is continuous. Therefore, it is a Kakutani function. The center point of $C_{{\overrightarrow{i}}_m^{\prime }}$ picks out the series of cells where the $m$'th cell of the product that defines them is $\left\{C_{{\overrightarrow{i}}_m^{\prime }}\right\}$, so the point that this function maps towards is outside $D_m$. Furthermore, for all points in the set of cells $C_R\cap D_m$, $d=0$, so the point is moved 1 unit away from its starting point, so all these cells are ruled out. Finally, for all cells outside of $C_R\cap D_m$, select a point on the interior of the cell that is more than $\delta$ away from any cells that must be ruled out. Then this function doesn't change any coordinates of that point, so $F_m$ has a fixed point in that cell, so this cell has not been ruled out. This argument applies for all $m$.

Therefore, conditions 1 and 2 are fulfilled by this assignment of cells. To go back to the Minecraft cube, if you pick out some subset of the green glass cubes as ones to be prevented, all points in or really close to that subset would get mapped towards the plane of black glass cubes by player 3. Similarly, if you pick out some subset of the black glass cubes as ones to be prevented by player 2, player 2 would map all points on or really close to those cubes towards the column of purple glass cubes. Of course, the players don't have to use this exact Kakutani function, it just proves that for every player, there is some Kakutani function that lets them fulfill their obligations.

Finally, we will show that if there are at least 2 cells remaining, there is always a pair of cells $C_{\overrightarrow{i}}$ and $C_{{\overrightarrow{i}}^{\prime }}$ such that $C_{\overrightarrow{i}}$ is minimally ranked for some player $m$, and when $C_{{\overrightarrow{i}}^{\prime }}$ is fixed as a backup cell, $C_{\overrightarrow{i}}\in D_m$ (which means it can be eliminated by player $m$ in the same Kakutani way as detailed before, finishing up the proof by showing that a cell gets eliminated)

Take player $n$, and let $C_{\overrightarrow{i}}$ be their least-favored cell. If there exists some other cell $C_{{\overrightarrow{i}}^{\prime }}$ that isn't ruled out, and ${\overrightarrow{i}}_n\ne {\overrightarrow{i}}_n^{\prime }$ (ie, the detested cell and the backup cell have different final indices), then it can be the backup cell. Because both these cells have different final indices, $C_{\overrightarrow{i}}\in D_n$.

The quick visual version of this is that if you delete some blocks out of the cube in the Minecraft image (these block holes correspond to cells that aren't ruled out yet), then if the most-hated block hole has a different player 3 coordinate than some other block hole, then you can plug the other block hole with the glowing block, and the resulting black plane won't contain the most-hated block hole, and the most-hated block hole will be in the green (which means it can be safely eliminated, just adopt a kakutani function that maps everything in or near that cell to the black plane).

But what if all the cells remaining/holes in the Minecraft cube have the same final index in $I_n$/lie in the same plane? This makes it so player $n$ doesn't have a backup cell that lets them eliminate their least favorite one.

Consider player $n-1$. By the same argument as before, player $n-1$ can eliminate their most detested cell, unless all the non-eliminated cells have both the same player $n$ index, and the same player $n-1$ index.

Consider player $n-2$, and so on. Either there is some player that can get a crack at eliminating their least favorite cell if the random number generator assigns things right, or the sequence of indices that indexes both cells is the exact same. That would mean these two distinct cells are the same cell, which is impossible.

2 comments

Comments sorted by top scores.