I don’t think I get this. Let’s walk though an example that looks absurd to me, and let me know if I’m misinterpreting something along the way:
We start with the feasible set as the convex hull of (0,0), (2,3), and (3,2). X thinks that (3,2) is fair, while Y thinks that (2,3) is fair. By Eliezer’s algorithm (and by the modal instantiation), they would end up at (2,2).
Let’s say that A1 includes (3,2), and A2 includes (2,3); then A1 is the first rectangle considered fair by X, and A2 is the first rectangle considered fair by Y.
Then X, running the algorithm above, first tries to show in PA+1 that y≤2 and that (3, y) is in the feasible set; if it succeeds, it outputs 3. Meanwhile, Y tries to show that x≤2 and that (x,3) is in the feasible set; if it succeeds, it outputs 3. Neither of these proof searches can succeed (since PA+1 doesn’t know its own consistency, each agent thinks the other might output 3 by the Principle of Explosion).
Now we move to the next stage. X tries to show in PA+2 that y≤2 and that (3/2, y) is feasible; if so, it outputs 3⁄2. Y likewise tries to show in PA+2 that x≤2 and that (x, 3⁄2) is feasible; if so, it outputs 3⁄2. Now we have a Lobian circle; both successfully prove that the other outputs 3⁄2, and thus output 3⁄2 themselves. And so the agents coordinate at (3/2, 3⁄2), rather than at (2,2) or anything better.
You did miss something: namely from PA+2 X wants to show feasibility of (m2xi0,y), not (m2,y). In your example, xi0=3, so the Löbian circle you describe will fail.
I’ll walk through what will happen in the example.
The Ai are just areas (ie xiyi), not rectangles. In this example, A1=6 is enough to contain (2,3) and (3,2). For conciseness let’s have A1=6, A2=4, and m=3 (so A3=0).
Both X and Y have i0=1. According to X, (x1,y1)=(3,2), (x2,y2)=(2,2), and (x3,y3)=(0,0).
First the speculative phase will happen:
X will try to prove in PA+1 that y≤2 and that (31⋅3,y) is in the feasible set. The latter is immediately false, so this will fail.
Next, X will try to prove in PA+2 that y≤2 and that (32⋅3,y) is in the feasible set. This too is immediately false.
Next, X will try to prove in PA+3 that y≤2 and that (33⋅3,y) is feasible (in short, that y=2), and return 3 if so. This will fail to reach a cycle.
Then the bargaining phase:
Next, X will try to prove in PA+4 that y≤2 and that (3,y) is feasible, and return 3 if so. This will fail identically.
Next, X will try to prove in PA+5 that y≤2 and that (2,y) is feasible, and return 2 if so. This will reach a Löbian circle, and X and Y will both return 2, which is what we want.
OK! You were right, I misinterpreted, and I do like this proposal!
I concur that in the limit as m→∞, this does hit the intersection of the fairness curves if the agents are biased in their own favor, and hits the Pareto curve linear multiple of each agent’s request if they’re biased in each others’ favor. Moreover, both of these behaviors are invariant under rescalings of utility functions, so we’re good on that front too!
I haven’t yet thought about whether this works analogously in three-player games, but it feels like it should...
If the fairness constraints are all pairwise (ie each player has fairness curves for each opponent), then the scheme generalizes directly. Slightly more generally, if each player’s fairness set is weakly convex and closed under componentwise max, the scheme still generalizes directly (in effect the componentwise max creates a fairness curve which can be intersected with the xyz=Ai surfaces to get the (xi,yi,zi) points.
In order to generalize fully, the agents should each precommunicate their fairness sets. In fact, after doing this, the algorithm is very simple: player X can compute what it believes is the optimal-xyz feasible-and-fair-according-to-everyone point (x,y,z) (which is unique because these are all convex sets), and if PA proves the outcome will be fair-according-to-X, then output x; otherwise output 0.
I’d like for this to work with as little prior coordination as possible, so I’m not keen on assuming the agents precommunicate their fairness sets. But the generalization with only the Ai pre-coordinated is neat.
What’s the harm in requiring prior coordination, considering there’s already a prior agreement to follow a particular protocol involving Ais? (And something earlier on in the context about a shared source of randomness to ensure convexity of the feasible set.)
The actual problem we want to work toward is one where all the prior coordination info is in the environment independent of the particular agents (e.g. the existence of Schelling points), and the agents are just deducing things about each other. For instance, two FairBots work in a source code swap Prisoner’s Dilemma against one another even if written in different programming languages.
I’m willing to accept “accepting a natural ordering on the payoff set” and “accepting a natural set of outcome products” as things that could conceivably be Schelling points in a simple environment, but “know the shape of each others’ fairness sets” looks like an infinite pre-exchange of information that cannot be gleaned from the environment.
(And “generate mutual random bits” is a cooperative thing that can be viewed as an atomic action in the environment.)
I don’t think I get this. Let’s walk though an example that looks absurd to me, and let me know if I’m misinterpreting something along the way:
We start with the feasible set as the convex hull of (0,0), (2,3), and (3,2). X thinks that (3,2) is fair, while Y thinks that (2,3) is fair. By Eliezer’s algorithm (and by the modal instantiation), they would end up at (2,2).
Let’s say that A1 includes (3,2), and A2 includes (2,3); then A1 is the first rectangle considered fair by X, and A2 is the first rectangle considered fair by Y.
Then X, running the algorithm above, first tries to show in PA+1 that y≤2 and that (3, y) is in the feasible set; if it succeeds, it outputs 3. Meanwhile, Y tries to show that x≤2 and that (x,3) is in the feasible set; if it succeeds, it outputs 3. Neither of these proof searches can succeed (since PA+1 doesn’t know its own consistency, each agent thinks the other might output 3 by the Principle of Explosion).
Now we move to the next stage. X tries to show in PA+2 that y≤2 and that (3/2, y) is feasible; if so, it outputs 3⁄2. Y likewise tries to show in PA+2 that x≤2 and that (x, 3⁄2) is feasible; if so, it outputs 3⁄2. Now we have a Lobian circle; both successfully prove that the other outputs 3⁄2, and thus output 3⁄2 themselves. And so the agents coordinate at (3/2, 3⁄2), rather than at (2,2) or anything better.
Did I miss something?
You did miss something: namely from PA+2 X wants to show feasibility of (m2xi0,y), not (m2,y). In your example, xi0=3, so the Löbian circle you describe will fail.
I’ll walk through what will happen in the example.
The Ai are just areas (ie xiyi), not rectangles. In this example, A1=6 is enough to contain (2,3) and (3,2). For conciseness let’s have A1=6, A2=4, and m=3 (so A3=0).
Both X and Y have i0=1. According to X, (x1,y1)=(3,2), (x2,y2)=(2,2), and (x3,y3)=(0,0).
First the speculative phase will happen:
X will try to prove in PA+1 that y≤2 and that (31⋅3,y) is in the feasible set. The latter is immediately false, so this will fail.
Next, X will try to prove in PA+2 that y≤2 and that (32⋅3,y) is in the feasible set. This too is immediately false.
Next, X will try to prove in PA+3 that y≤2 and that (33⋅3,y) is feasible (in short, that y=2), and return 3 if so. This will fail to reach a cycle.
Then the bargaining phase:
Next, X will try to prove in PA+4 that y≤2 and that (3,y) is feasible, and return 3 if so. This will fail identically.
Next, X will try to prove in PA+5 that y≤2 and that (2,y) is feasible, and return 2 if so. This will reach a Löbian circle, and X and Y will both return 2, which is what we want.
OK! You were right, I misinterpreted, and I do like this proposal!
I concur that in the limit as m→∞, this does hit the intersection of the fairness curves if the agents are biased in their own favor, and hits the Pareto curve linear multiple of each agent’s request if they’re biased in each others’ favor. Moreover, both of these behaviors are invariant under rescalings of utility functions, so we’re good on that front too!
I haven’t yet thought about whether this works analogously in three-player games, but it feels like it should...
If the fairness constraints are all pairwise (ie each player has fairness curves for each opponent), then the scheme generalizes directly. Slightly more generally, if each player’s fairness set is weakly convex and closed under componentwise max, the scheme still generalizes directly (in effect the componentwise max creates a fairness curve which can be intersected with the xyz=Ai surfaces to get the (xi,yi,zi) points.
In order to generalize fully, the agents should each precommunicate their fairness sets. In fact, after doing this, the algorithm is very simple: player X can compute what it believes is the optimal-xyz feasible-and-fair-according-to-everyone point (x,y,z) (which is unique because these are all convex sets), and if PA proves the outcome will be fair-according-to-X, then output x; otherwise output 0.
I’d like for this to work with as little prior coordination as possible, so I’m not keen on assuming the agents precommunicate their fairness sets. But the generalization with only the Ai pre-coordinated is neat.
What’s the harm in requiring prior coordination, considering there’s already a prior agreement to follow a particular protocol involving Ais? (And something earlier on in the context about a shared source of randomness to ensure convexity of the feasible set.)
The actual problem we want to work toward is one where all the prior coordination info is in the environment independent of the particular agents (e.g. the existence of Schelling points), and the agents are just deducing things about each other. For instance, two FairBots work in a source code swap Prisoner’s Dilemma against one another even if written in different programming languages.
I’m willing to accept “accepting a natural ordering on the payoff set” and “accepting a natural set of outcome products” as things that could conceivably be Schelling points in a simple environment, but “know the shape of each others’ fairness sets” looks like an infinite pre-exchange of information that cannot be gleaned from the environment.
(And “generate mutual random bits” is a cooperative thing that can be viewed as an atomic action in the environment.)