Modal Bargaining Agents

[-]jimrandomh11yΩ240

Point (1) seems to be a combination of an issue of working around the absence of a mathematically-elegant communication channel in the formalism, and an incentive to choose some orderings over others because of (2). If (2) is solved and they can communicate, then they can agree on an ordering without any trouble because they're both indifferent to which one is chosen.

If you don't have communication but you have solved (2), I think you can solve the problem by splitting agents into two stages. In the first stage, agents try to coordinate on an ordering over the points. To do this, the two agents X and Y each generate a bag of orderings Ox and Oy that they think might be Schelling points. Agent X first draws an ordering from Ox and tries to prove coordination on it in PA+1, then draws another with replacement and tries to prove coordination on it in PA+2, then draws another with replacement and tries to prove coordination on it in PA+3, etc. Agent Y does the same thing, with a different bag of proposed orderings. If there is overlap between their respective sets, then the odds that they will fail to find a coordination point fall off exponentially, albeit slowly.

Then in the second stage, after proving in PA+n for some n that they will both go through the same ordering, each will try to prove coordination on point 1 in PA+n+1, on point 2 in PA+n+2, etc, for the points they find acceptable.

[-]orthonormal11yΩ000

I think your proposal is more complicated than, say, mutually randomly choosing an ordering in one step. Does it have any superior properties to just doing that?

[-]jimrandomh11yΩ120

I don't think the mechanics of the problem, as specified, let them mutually specify random things without something like an externally-provided probability distribution. This is aimed at eliminating that requirement. But it may be that this issue isn't very illuminating and would be better addressed by adjusting the problem formulation to provide that.

[-]orthonormal11yΩ000

We already assumed a source of mutual randomness in order to guarantee that the feasible set is convex (caption to Figure 1).

[-]jimrandomh11yΩ000

To clarify, what I meant was not that they need a source of shared randomness, but that they need a shared probability distribution; ie, having dice isn't enough, they also need to coordinate on a way of interpreting the dice, which is similar to the original problem of coordinating on an ordering over points.

[-]jimrandomh11yΩ230

Regarding (2), the main problem is that this creates an incentive for agents to choose orderings that favor themselves when there is overlap between the acceptable regions, and this creates a high chance that they won't be able to agree on an ordering at all. Jessica Taylor's solution solves the problem of not being able to find an ordering, but at the cost of all the surplus utility that was in the region of overlap. For example, if Janos and I are deciding how to divide a dollar, I offer that Janos keeps it, and Janos offers that I keep it, that solution would have us set it on fire instead.

Instead, perhaps we could redefine the algorithm so that "cooperation at point N" means entering another round of negotiation, where only points that each agent finds at least as good as N are considered, and negotiation continues until it reaches a fixed point.

How to actually convert this into an algorithm? I haven't figured out all the technical details, but I think the key is having agents prove things of the form "we'll coordinate on a point I find at least as good as point N".

[-]orthonormal11yΩ110

I thought about that at some point, in the case where they're biased in their own directions, but of course there it just reintroduces the incentive for playing hardball. In the case where they're each overly generous, they already have the incentive to bias slightly more in their own direction.

However, there's not an obvious way to translate the second round of negotiation into the modal framework...

[-]János Kramár11yΩ120

How about a gridless scheme like:

The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.

Now discretize the possible "rectangle areas": let them be $A_{1} > . . . > A_{m} = 0$ . (This requires a way to agree on that, but this seems easier than agreeing on grid points; the finer the better, basically. Perhaps the most obvious way to do it is to have these be evenly spaced from $A_{m} = 0$ to $A_{1}$ ; then only $A_{1}$ and $m$ need to be agreed upon.)

X will do the following:

let $A_{i_{0}}$ be the first area in this list that is achieved by a feasible point on X's fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)

for $i = i_{0}, \dots, m - 1$ , let $(x_{i}, y_{i})$ be the "fair" utility distribution that achieves area $A_{i}$ ; let $(x_{m}, y_{m}) = (0, 0)$ .

let $y$ be Y's output.

# Speculative phase:

if $P A + 1$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{1} x_{i_{0}}, y)$ is feasible, return $\frac{m}{1} x_{i_{0}}$ .

else if $P A + 2$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{2} x_{i_{0}}, y)$ is feasible, return $\frac{m}{2} x_{i_{0}}$ .

$⋮$

else if $P A + m$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{m} x_{i_{0}}, y)$ is feasible, return $\frac{m}{m} x_{i_{0}}$ .

# Bargaining phase:

else if $P A + m + i_{0}$ proves $y \leq y_{i_{0}}$ and $(x_{i_{0}}, y)$ is feasible, return $x_{i_{0}}$ .

else if $P A + m + i_{0} + 1$ proves $y \leq y_{i_{0} + 1}$ and $(x_{i_{0} + 1}, y)$ is feasible, return $x_{i_{0} + 1}$ .

$⋮$

else if $P A + m + m - 1$ proves $y \leq y_{m - 1}$ and $(x_{m - 1}, y)$ is feasible, return $x_{m - 1}$ .

else return $x_{i_{0}}$ .

If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent's fairness curve.

Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area $\geq A_{i}$ for some $i$ and X and Y follow the protocol then on the $P A + m + i$ step, they will be able to agree on the coordinatewise min of their proposed feasible points with area $A_{i}$ .

If they're both really generous and their fairness curves don't intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.

[-]orthonormal11yΩ110

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 $A_{1}$ includes (3,2), and $A_{2}$ includes (2,3); then $A_{1}$ is the first rectangle considered fair by X, and $A_{2}$ is the first rectangle considered fair by Y.

Then X, running the algorithm above, first tries to show in PA+1 that $y \leq 2$ and that (3, y) is in the feasible set; if it succeeds, it outputs 3. Meanwhile, Y tries to show that $x \leq 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 \leq 2$ and that (3/2, y) is feasible; if so, it outputs 3/2. Y likewise tries to show in PA+2 that $x \leq 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?

[-]János Kramár11yΩ120

You did miss something: namely from PA+2 X wants to show feasibility of $(\frac{m}{2} x_{i_{0}}, y)$ , not $(\frac{m}{2}, y)$ . In your example, $x_{i_{0}} = 3$ , so the Löbian circle you describe will fail.

I'll walk through what will happen in the example.

The $A_{i}$ are just areas (ie $x_{i} y_{i}$ ), not rectangles. In this example, $A_{1} = 6$ is enough to contain $(2, 3)$ and $(3, 2)$ . For conciseness let's have $A_{1} = 6$ , $A_{2} = 4$ , and $m = 3$ (so $A_{3} = 0$ ).

Both X and Y have $i_{0} = 1$ . According to X, $(x_{1}, y_{1}) = (3, 2)$ , $(x_{2}, y_{2}) = (2, 2)$ , and $(x_{3}, y_{3}) = (0, 0)$ .

First the speculative phase will happen:

X will try to prove in PA+1 that $y \leq 2$ and that $(\frac{3}{1} \cdot 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 \leq 2$ and that $(\frac{3}{2} \cdot 3, y)$ is in the feasible set. This too is immediately false.

Next, X will try to prove in PA+3 that $y \leq 2$ and that $(\frac{3}{3} \cdot 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 \leq 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 \leq 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.

[-]orthonormal11yΩ000

OK! You were right, I misinterpreted, and I do like this proposal!

I concur that in the limit as $m \to \infty$ , 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...

[-]János Kramár11yΩ120

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 $x y z = A_{i}$ surfaces to get the $(x_{i}, y_{i}, z_{i})$ 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- $x y z$ 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.

[-]orthonormal11yΩ000

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 $A_{i}$ pre-coordinated is neat.

[-]János Kramár11yΩ000

What's the harm in requiring prior coordination, considering there's already a prior agreement to follow a particular protocol involving $A_{i}$ s? (And something earlier on in the context about a shared source of randomness to ensure convexity of the feasible set.)

[-]orthonormal11yΩ000

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.)

[-]jessicata11yΩ120

Quick point on 2: we could define acceptable solutions as those that are Pareto-inferior to the fair point. This ensures that there is only one Pareto optimal feasible point that is acceptable to everyone. Of course, it does result in worse solutions, but doing something like this seems like a good step towards solving 1.

[-]orthonormal10yΩ000

I now think we can do this without prior coordination, in some sense, by using pseudorandom bitstrings and lots of oracle calls. (Idea came from a conversation with Alex Mennen.)

Intuition: if both players are sampling their acceptable outcome sets in random fashion, and each is heavily biased toward sampling points where they do better, then the first time that they both check the same point at the same level is very probably going to be near Eliezer's fairness point.

(As noted in Quinn's example, we'll need to make the map from output-time to outcome injective, but we can do this via the transform suggested in that draft.)

Consider the distribution over the agent's acceptable outcome set with probability density proportional to a positive exponential of the agent's utility function $U_{A}$ :

$p (a, b) \propto exp (K u_{A} (a, b))$ if $(a, b)$ acceptable to $A$ , 0 otherwise.

Our agents need to be deterministic, so we'll have a vast family of them parametrized by sequences of draws from this distribution. Given a large $N \in N$ and a sequence of ${(a_{i}, b_{i}) : 0 \leq i \leq N$ drawn from that distribution, we have the agent

def A():
  for i in range(N):
    if PA+i proves A()=a_i implies B()=b_i:
      return a_i
  else return default Nash equilibrium

(If we want to do this even more generally and not assume they're considering the same set of ordered pairs, we can instead ask for proofs that $A () = a_{i} \to U_{A} () \geq u_{A} (a_{i}, b_{i})$ , where $U_{A}$ is the actual utility of the universe from A's perspective and $u_{A}$ is the utility of a particular point in the feasible set.)

If two such agents are playing against one another, then the probability (with respect to the sequence of draws that defined each agent) of a mutually acceptable ordered pair $(a, b)$ being chosen at each step is proportional to $exp (K_{A} u_{A} (a, b) + K_{B} u_{B} (a, b))$ , which is maximized at Eliezer's acceptable point, and they have $N$ chances to get it. For $K_{A}$ and $K_{B}$ large, and for $N$ very large, with high probability two such agents will coordinate near Eliezer's acceptable point.

[-]orthonormal10yΩ000

Note: this requires a further "injectivity" assumption to work; see Quinn's post.

[-]János Kramár11y00

How about a gridless scheme like:

The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.

X will do the following:

let $A_{i_{0}}$ be the first area in this list that is achieved by a feasible point on X's fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)

for $i = i_{0}, \dots, m - 1$ , let $(x_{i}, y_{i})$ be the "fair" utility distribution that achieves area $A_{i}$ ; let $(x_{m}, y_{m}) = (0, 0)$ .

let $y$ be Y's output.

# Speculative phase:

if $P A + 1$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{1} x_{i_{0}}, y)$ is feasible, return $\frac{m}{1} x_{i_{0}}$ .

else if $P A + 2$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{2} x_{i_{0}}, y)$ is feasible, return $\frac{m}{2} x_{i_{0}}$ .

$⋮$

else if $P A + m$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{m} x_{i_{0}}, y)$ is feasible, return $\frac{m}{m} x_{i_{0}}$ .

# Bargaining phase:

else if $P A + m + i_{0}$ proves $y \leq y_{i_{0}}$ and $(x_{i_{0}}, y)$ is feasible, return $x_{i_{0}}$ .

else if $P A + m + i_{0} + 1$ proves $y \leq y_{i_{0} + 1}$ and $(x_{i_{0} + 1}, y)$ is feasible, return $x_{i_{0} + 1}$ .

$⋮$

else if $P A + m + m - 1$ proves $y \leq y_{m - 1}$ and $(x_{m - 1}, y)$ is feasible, return $x_{m - 1}$ .

else return $x_{i_{0}}$ .

If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent's fairness curve.

[-]János Kramár11yΩ000

How about a gridless scheme like:

The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.

X will do the following:

let $A_{i_{0}}$ be the first area in this list that is achieved by a feasible point on X's fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)

for $i = i_{0}, \dots, m - 1$ , let $(x_{i}, y_{i})$ be the "fair" utility distribution that achieves area $A_{i}$ ; let $(x_{m}, y_{m}) = (0, 0)$ .

let $y$ be Y's output.

# Speculative phase:

if $P A + 1$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{1} x_{i_{0}}, y)$ is feasible, return $\frac{m}{1} x_{i_{0}}$ .

else if $P A + 2$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{2} x_{i_{0}}, y)$ is feasible, return $\frac{m}{2} x_{i_{0}}$ .

$⋮$

else if $P A + m$ proves $y \leq y_{i_{0}}$ and $(\frac{m}{m} x_{i_{0}}, y)$ is feasible, return $\frac{m}{m} x_{i_{0}}$ .

# Bargaining phase:

else if $P A + m + i_{0}$ proves $y \leq y_{i_{0}}$ and $(x_{i_{0}}, y)$ is feasible, return $x_{i_{0}}$ .

else if $P A + m + i_{0} + 1$ proves $y \leq y_{i_{0} + 1}$ and $(x_{i_{0} + 1}, y)$ is feasible, return $x_{i_{0} + 1}$ .

$⋮$

else if $P A + m + m - 1$ proves $y \leq y_{m - 1}$ and $(x_{m - 1}, y)$ is feasible, return $x_{m - 1}$ .

else return $x_{i_{0}}$ .

If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent's fairness curve.

LESSWRONG
LW

LESSWRONG
LW

14

Modal Bargaining Agents

14

Ω 9

14

Ω 9

Bargaining and Fairness

Bargaining Away from the Pareto Frontier

Modal Bargaining Agents

Open questions and nagging issues: