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 A1>...>Am=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 Am=0 to A1; then only A1 and m need to be agreed upon.)
X will do the following:
let Ai0 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=i0,…,m−1, let (xi,yi) be the “fair” utility distribution that achieves area Ai; let (xm,ym)=(0,0).
let y be Y’s output.
# Speculative phase:
else if PA+1 proves y≤yi0 and (m1xi0,y) is feasible, return m1xi0.
else if PA+2 proves y≤yi0 and (m2xi0,y) is feasible, return m2xi0.
else ⋮
else if PA+m proves y≤yi0 and (mmxi0,y) is feasible, return mmxi0.
# Bargaining phase:
else if PA+m+i0+1 proves y≤yi0+1 and (xi0,y)+1 is feasible, return xi0.
else if PA+m+i0+1 proves y≤yi0+1 and (xi0+1,y) is feasible, return xi0+1.
else ⋮
else if PA+m+m−1 proves y≤ym−1 and (xm−1,y) is feasible, return xm−1.
else return xi0.
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 ≥Ai 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 Ai.
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 A1>...>Am=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 Am=0 to A1; then only A1 and m need to be agreed upon.)
X will do the following:
let Ai0 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=i0,…,m−1, let (xi,yi) be the “fair” utility distribution that achieves area Ai; let (xm,ym)=(0,0).
let y be Y’s output.
# Speculative phase:
else if PA+1 proves y≤yi0 and (m1xi0,y) is feasible, return m1xi0.
else if PA+2 proves y≤yi0 and (m2xi0,y) is feasible, return m2xi0.
else ⋮
else if PA+m proves y≤yi0 and (mmxi0,y) is feasible, return mmxi0.
# Bargaining phase:
else if PA+m+i0+1 proves y≤yi0+1 and (xi0,y)+1 is feasible, return xi0.
else if PA+m+i0+1 proves y≤yi0+1 and (xi0+1,y) is feasible, return xi0+1.
else ⋮
else if PA+m+m−1 proves y≤ym−1 and (xm−1,y) is feasible, return xm−1.
else return xi0.
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 ≥Ai 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 Ai.
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.