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.

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

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:

$\text{else}$ if $PA+1$ proves $y\le y_{i_0}$ and $(\frac{m}{1}{x}_{i_0},y)$ is feasible, return $\frac{m}{1}{x}_{i_0}$.

else if $PA+2$ proves $y\le y_{i_0}$ and $(\frac{m}{2}{x}_{i_0},y)$ is feasible, return $\frac{m}{2}{x}_{i_0}$.

$\text{else}⋮$

else if $PA+m$ proves $y\le y_{i_0}$ and $(\frac{m}{m}{x}_{i_0},y)$ is feasible, return $\frac{m}{m}{x}_{i_0}$.

# Bargaining phase:

else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0},y{)}_{+1}$ is feasible, return $x_{i_0}$.

else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0+1},y)$ is feasible, return $x_{i_0+1}$.

$\text{else}⋮$

else if $PA+m+m-1$ proves $y\le 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 $\ge A_i$ for some $i$ and X and Y follow the protocol then on the $PA+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.

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.

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 \left(K{u}_A\right(a,b\left)\right)$ 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 $\left\{\right(a_i,b_i):0\le i\le 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\left(\right)=a_i\to U_A\left(\right)\ge 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 \left(K_A{u}_A\right(a,b)+K_B{u}_B(a,b\left)\right)$, 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.

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

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:

$\text{else}$ if $PA+1$ proves $y\le y_{i_0}$ and $(\frac{m}{1}{x}_{i_0},y)$ is feasible, return $\frac{m}{1}{x}_{i_0}$.

else if $PA+2$ proves $y\le y_{i_0}$ and $(\frac{m}{2}{x}_{i_0},y)$ is feasible, return $\frac{m}{2}{x}_{i_0}$.

$\text{else}⋮$

else if $PA+m$ proves $y\le y_{i_0}$ and $(\frac{m}{m}{x}_{i_0},y)$ is feasible, return $\frac{m}{m}{x}_{i_0}$.

# Bargaining phase:

else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0},y{)}_{+1}$ is feasible, return $x_{i_0}$.

else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0+1},y)$ is feasible, return $x_{i_0+1}$.

$\text{else}⋮$

else if $PA+m+m-1$ proves $y\le 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 $\ge A_i$ for some $i$ and X and Y follow the protocol then on the $PA+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.

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:

$\text{else}$ if $PA+1$ proves $y\le y_{i_0}$ and $(\frac{m}{1}{x}_{i_0},y)$ is feasible, return $\frac{m}{1}{x}_{i_0}$.

else if $PA+2$ proves $y\le y_{i_0}$ and $(\frac{m}{2}{x}_{i_0},y)$ is feasible, return $\frac{m}{2}{x}_{i_0}$.

$\text{else}⋮$

else if $PA+m$ proves $y\le y_{i_0}$ and $(\frac{m}{m}{x}_{i_0},y)$ is feasible, return $\frac{m}{m}{x}_{i_0}$.

# Bargaining phase:

else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0},y{)}_{+1}$ is feasible, return $x_{i_0}$.

else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0+1},y)$ is feasible, return $x_{i_0+1}$.

$\text{else}⋮$

else if $PA+m+m-1$ proves $y\le 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 $\ge A_i$ for some $i$ and X and Y follow the protocol then on the $PA+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.