# Modal Bargaining Agents

Sum­mary: Bar­gain­ing prob­lems are in­ter­est­ing in the case of Löbian co­op­er­a­tion; Eliezer sug­gested a ge­o­met­ric al­gorithm for re­solv­ing bar­gain­ing con­flicts by leav­ing the Pareto fron­tier, and this al­gorithm can be made into a modal agent, given an ad­di­tional sug­ges­tion by Benja.

# Bar­gain­ing and Fairness

When two agents can read each oth­ers’ source code be­fore play­ing a game, Löbian co­op­er­a­tion can trans­form many games into pure bar­gain­ing prob­lems. Ex­plic­itly, the al­gorithm of “if I can prove you choose X, then I choose Y, oth­er­wise I choose Z” makes it pos­si­ble for an agent to offer a deal bet­ter for both par­ties than a Nash equil­ibrium, then de­fault to that Nash equil­ibrium if the deal isn’t ver­ifi­ably taken. In the sim­ple case where there is a unique Nash equil­ibrium, two agents with that sort of al­gorithm can effec­tively re­duce the de­ci­sion the­ory prob­lem to a ne­go­ti­a­tion over which point on the Pareto fron­tier they will se­lect.

How­ever, if two agents in­sist on differ­ent deals (e.g. X in­sists on point D, Y in­sists on point A), then it falls through and we’re back to the Nash equil­ibrium O. And if you try and patch this by offer­ing sev­eral deals in se­quence along the Pareto fron­tier, then a savvy op­po­nent is just go­ing to grab whichever of those is best for them. So we’d like both a no­tion of the fair out­come, and a way to still make deals with agents who dis­agree with us on fair­ness (with­out fal­ling back to the Nash equil­ibrium, and with­out in­cen­tiviz­ing them to play hard­ball with us).

Note that util­ity func­tions are only defined up to af­fine trans­for­ma­tions, so any solu­tion should be in­var­i­ant un­der in­de­pen­dent rescal­ings of the play­ers’ util­ities. This re­quire­ment, plus a few oth­ers (wind­ing up on the Pareto fron­tier, in­de­pen­dence of ir­rele­vant al­ter­na­tives, and sym­me­try) are all satis­fied by the Nash solu­tion to the bar­gain­ing prob­lem: choose the point on the Pareto fron­tier so that the area of the rec­t­an­gle from O to that point is max­i­mized.

This gives us a pretty plau­si­ble an­swer to the first ques­tion, but leaves us with the sec­ond: are we sim­ply at war with agents that have other ideas of what’s fair? (Let’s say that X thinks that the Nash solu­tion N is fair, but Y thinks that B is fair.) Other the­o­rists have come up with other defi­ni­tions of the fair solu­tion to a bar­gain­ing prob­lem, so this is a live ques­tion!

And the ques­tion of in­cen­tives makes it even more difficult: if you try some­thing like “50% my fair equil­ibrium, 50% their fair equil­ibrium”, you cre­ate an in­cen­tive for other agents to bias their defi­ni­tion of fair­ness in their own fa­vor, since that boosts their pay­off.

# Bar­gain­ing Away from the Pareto Frontier

Eliezer’s sug­ges­tion in this case is as fol­lows: an agent defines its set of ac­cept­able deals as “all points in the fea­si­ble set for which my op­po­nent’s score is at most what they would get at the point I think is fair”. If each agent’s defi­ni­tion of fair­ness is bi­ased in their own fa­vor, the in­ter­sec­tion of the agents’ ac­cept­able deals has a cor­ner within the fea­si­ble set (but not on the Pareto fron­tier un­less the agents agree on the fair point), and that is the point where they should ac­tu­ally achieve Löbian co­op­er­a­tion.

Note that in this setup, you get no ex­tra util­ity for re­defin­ing fair­ness in a self-serv­ing way. Each agent winds up get­ting the util­ity they would have had at the fair­ness point of the other agent. (Ac­tu­ally, Eliezer sug­gests a very slight slope to these lines, in the di­rec­tion that makes it worse for the op­po­nent to in­sist on a more ex­treme fair­ness point. This sets up good in­cen­tives for meet­ing in the mid­dle. But for sim­plic­ity, we’ll just con­sider the in­cen­tive-neu­tral ver­sion here.)

More­over, this ex­tends to games in­volv­ing more than two agents: each one defines a set of ac­cept­able deals by the con­di­tion that no other agent gets more than they would have at the agent’s fair­ness point, and the in­ter­sec­tion has a cor­ner in the fea­si­ble set, where each agent gets the min­i­mum of the pay­offs it would have achieved at the other agents’ fair­ness points.

# Mo­dal Bar­gain­ing Agents

Now, how do we set this bar­gain­ing al­gorithm up as a modal de­ci­sion the­ory? We can only con­sider finitely many op­tions, though we’re al­lowed to con­sider com­putably mixed strate­gies. Let’s as­sume that our game has finitely many pure strate­gies for each player. As above, we’ll as­sume there is a unique Nash equil­ibrium, and set it at the ori­gin.

Then there’s a nat­u­ral set of points we should con­sider: the grid points within the fea­si­ble set (the con­vex hull formed by the Nash equil­ibrium and the Pareto op­ti­mal points above it) whose co­or­di­nates cor­re­spond to util­ities of the pure strate­gies on the Pareto fron­tier. This is eas­ier to see than to read:

Now all we need is to be sure that Löbian co­op­er­a­tion hap­pens at the point we ex­pect. There’s one sig­nifi­cant prob­lem here: we need to worry about sync­ing the proof lev­els that differ­ent agents are us­ing.

(If you haven’t seen this be­fore, you might want to work out what hap­pens if any two of the fol­low­ing three agents are paired with one an­other:

• X re­turns A if PA proves its op­po­nent re­turns A, else X re­turns D.

• Y re­turns B if PA proves its op­po­nent re­turns B, else Y re­turns A if PA proves its op­po­nent re­turns A, else Y re­turns D.

• Z re­turns C if PA proves its op­po­nent re­turns C, else Z re­turns A if PA + Con(PA) proves its op­po­nent re­turns A, else Z re­turns D.

Re­sults in rot13: Nal gjb qvss­r­erag ntragf no­bir erghea Q nt­nvafg rnpu bgure, orpn­hfr CN pna’g ce­bir vgf bja pbafvf­grapl, naq gur­ers­ber gur snpg gung n cebbs frnepu va CN snvyf pna ar­ire or ce­birq va CN.)

Benja sug­gested one way to en­sure that Löbian co­op­er­a­tion hap­pens at the right point: we as­sume that in ad­di­tion to the pay­off ma­trix, the agents are mu­tu­ally aware of an or­der­ing re­la­tion on the grid points. In or­der to land on the best mu­tu­ally ac­cept­able point (in the Pareto sense), it’s merely nec­es­sary for the or­der­ing to re­spect the “level” of grid points, defined as the to­tal num­ber of grid lines tra­versed along ei­ther axis from O to the grid point.

Then, we sim­ply have each player look for co­op­er­a­tion at proof level N at the Nth point, skip­ping those points that are un­ac­cept­able to it. Since the best mu­tu­ally ac­cept­able point is the only ac­cept­able point at its level (or any prior level), it will be cho­sen.

Again, this works for modal de­ci­sion prob­lems with more than two play­ers.

# Open ques­tions and nag­ging is­sues:

1. Is there a bet­ter way to re­solve bar­gain­ing with­out in­cen­tiviz­ing other agents to take ex­treme po­si­tions?

2. Is there some rea­son­able way to make this work with­out pro­vid­ing the canon­i­cal or­der­ing of grid points?

3. If agents are each bi­ased in their op­po­nent’s di­rec­tion, this al­gorithm still gets a re­sult, but in this case there is more than one grid point on the high­est level of the mu­tu­ally ac­cept­able re­gion, and thus the canon­i­cal or­der­ing ac­tu­ally chooses the out­come!

4. If an agent’s “fair­ness point” on the Pareto fron­tier is it­self a mixed strat­egy pro­file rather than a pure one, and the other agent doesn’t know which point that is, can this still work? In par­tic­u­lar, if there is an or­der­ing on the en­tire fea­si­ble set, and if two agents each add ex­tra grid lines to the set based on their own fair­ness points (with­out know­ing the oth­ers), is there an al­gorithm for se­lect­ing proof lev­els which guaran­tees that they will meet at the best mu­tu­ally ac­cept­able point that ap­pears in both of their grids?

• Point (1) seems to be a com­bi­na­tion of an is­sue of work­ing around the ab­sence of a math­e­mat­i­cally-el­e­gant com­mu­ni­ca­tion chan­nel in the for­mal­ism, and an in­cen­tive to choose some or­der­ings over oth­ers be­cause of (2). If (2) is solved and they can com­mu­ni­cate, then they can agree on an or­der­ing with­out any trou­ble be­cause they’re both in­differ­ent to which one is cho­sen.

If you don’t have com­mu­ni­ca­tion but you have solved (2), I think you can solve the prob­lem by split­ting agents into two stages. In the first stage, agents try to co­or­di­nate on an or­der­ing over the points. To do this, the two agents X and Y each gen­er­ate a bag of or­der­ings Ox and Oy that they think might be Schel­ling points. Agent X first draws an or­der­ing from Ox and tries to prove co­or­di­na­tion on it in PA+1, then draws an­other with re­place­ment and tries to prove co­or­di­na­tion on it in PA+2, then draws an­other with re­place­ment and tries to prove co­or­di­na­tion on it in PA+3, etc. Agent Y does the same thing, with a differ­ent bag of pro­posed or­der­ings. If there is over­lap be­tween their re­spec­tive sets, then the odds that they will fail to find a co­or­di­na­tion point fall off ex­po­nen­tially, albeit slowly.

Then in the sec­ond stage, af­ter prov­ing in PA+n for some n that they will both go through the same or­der­ing, each will try to prove co­or­di­na­tion on point 1 in PA+n+1, on point 2 in PA+n+2, etc, for the points they find ac­cept­able.

• I think your pro­posal is more com­pli­cated than, say, mu­tu­ally ran­domly choos­ing an or­der­ing in one step. Does it have any su­pe­rior prop­er­ties to just do­ing that?

• I don’t think the me­chan­ics of the prob­lem, as speci­fied, let them mu­tu­ally spec­ify ran­dom things with­out some­thing like an ex­ter­nally-pro­vided prob­a­bil­ity dis­tri­bu­tion. This is aimed at elimi­nat­ing that re­quire­ment. But it may be that this is­sue isn’t very illu­mi­nat­ing and would be bet­ter ad­dressed by ad­just­ing the prob­lem for­mu­la­tion to provide that.

• We already as­sumed a source of mu­tual ran­dom­ness in or­der to guaran­tee that the fea­si­ble set is con­vex (cap­tion to Figure 1).

• To clar­ify, what I meant was not that they need a source of shared ran­dom­ness, but that they need a shared prob­a­bil­ity dis­tri­bu­tion; ie, hav­ing dice isn’t enough, they also need to co­or­di­nate on a way of in­ter­pret­ing the dice, which is similar to the origi­nal prob­lem of co­or­di­nat­ing on an or­der­ing over points.

• Re­gard­ing (2), the main prob­lem is that this cre­ates an in­cen­tive for agents to choose or­der­ings that fa­vor them­selves when there is over­lap be­tween the ac­cept­able re­gions, and this cre­ates a high chance that they won’t be able to agree on an or­der­ing at all. Jes­sica Tay­lor’s solu­tion solves the prob­lem of not be­ing able to find an or­der­ing, but at the cost of all the sur­plus util­ity that was in the re­gion of over­lap. For ex­am­ple, if Janos and I are de­cid­ing how to di­vide a dol­lar, I offer that Janos keeps it, and Janos offers that I keep it, that solu­tion would have us set it on fire in­stead.

In­stead, per­haps we could re­define the al­gorithm so that “co­op­er­a­tion at point N” means en­ter­ing an­other round of ne­go­ti­a­tion, where only points that each agent finds at least as good as N are con­sid­ered, and ne­go­ti­a­tion con­tinues un­til it reaches a fixed point.

How to ac­tu­ally con­vert this into an al­gorithm? I haven’t figured out all the tech­ni­cal de­tails, but I think the key is hav­ing agents prove things of the form “we’ll co­or­di­nate on a point I find at least as good as point N”.

• I thought about that at some point, in the case where they’re bi­ased in their own di­rec­tions, but of course there it just rein­tro­duces the in­cen­tive for play­ing hard­ball. In the case where they’re each overly gen­er­ous, they already have the in­cen­tive to bias slightly more in their own di­rec­tion.

How­ever, there’s not an ob­vi­ous way to trans­late the sec­ond round of ne­go­ti­a­tion into the modal frame­work...

• How about a grid­less scheme like:

The agents agree that they will each out­put how much util­ity they will get, and if they fail to choose a fea­si­ble point they both get 0.

Now dis­cretize the pos­si­ble “rec­t­an­gle ar­eas”: let them be . (This re­quires a way to agree on that, but this seems eas­ier than agree­ing on grid points; the finer the bet­ter, ba­si­cally. Per­haps the most ob­vi­ous way to do it is to have these be evenly spaced from to ; then only and need to be agreed upon.)

X will do the fol­low­ing:

let be the first area in this list that is achieved by a fea­si­ble point on X’s fair­ness curve. (We will as­sume the fair­ness curve is weakly con­vex and weakly in­creas­ing.)

for , let be the “fair” util­ity dis­tri­bu­tion that achieves area ; let .

let be Y’s out­put.

# Spec­u­la­tive phase:

if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

# Bar­gain­ing phase:

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else re­turn .

If both agents fol­low pro­to­col, the re­sult is guaran­teed to be fea­si­ble and to not be above ei­ther agent’s fair­ness curve.

Fur­ther­more, if the in­ter­sec­tion of the fair­ness curves is at a fea­si­ble point that pro­duces rec­t­an­gle area for some and X and Y fol­low the pro­to­col then on the step, they will be able to agree on the co­or­di­nate­wise min of their pro­posed fea­si­ble points with area .

If they’re both re­ally gen­er­ous and their fair­ness curves don’t in­ter­sect in­side the fea­si­ble re­gion, the given pro­to­col will agree on ap­prox­i­mately the high­est fea­si­ble mul­ti­ple of how much they thought they were fairly due, avoid­ing util­ity sac­ri­fice.

• I don’t think I get this. Let’s walk though an ex­am­ple that looks ab­surd to me, and let me know if I’m mis­in­ter­pret­ing some­thing along the way:

We start with the fea­si­ble set as the con­vex 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 al­gorithm (and by the modal in­stan­ti­a­tion), they would end up at (2,2).

Let’s say that in­cludes (3,2), and in­cludes (2,3); then is the first rec­t­an­gle con­sid­ered fair by X, and is the first rec­t­an­gle con­sid­ered fair by Y.

Then X, run­ning the al­gorithm above, first tries to show in PA+1 that and that (3, y) is in the fea­si­ble set; if it suc­ceeds, it out­puts 3. Mean­while, Y tries to show that and that (x,3) is in the fea­si­ble set; if it suc­ceeds, it out­puts 3. Nei­ther of these proof searches can suc­ceed (since PA+1 doesn’t know its own con­sis­tency, each agent thinks the other might out­put 3 by the Prin­ci­ple of Ex­plo­sion).

Now we move to the next stage. X tries to show in PA+2 that and that (3/​2, y) is fea­si­ble; if so, it out­puts 32. Y like­wise tries to show in PA+2 that and that (x, 32) is fea­si­ble; if so, it out­puts 32. Now we have a Lo­bian cir­cle; both suc­cess­fully prove that the other out­puts 32, and thus out­put 32 them­selves. And so the agents co­or­di­nate at (3/​2, 32), rather than at (2,2) or any­thing bet­ter.

Did I miss some­thing?

• You did miss some­thing: namely from PA+2 X wants to show fea­si­bil­ity of , not . In your ex­am­ple, , so the Löbian cir­cle you de­scribe will fail.

I’ll walk through what will hap­pen in the ex­am­ple.

The are just ar­eas (ie ), not rec­t­an­gles. In this ex­am­ple, is enough to con­tain and . For con­cise­ness let’s have , , and (so ).

Both X and Y have . Ac­cord­ing to X, , , and .

First the spec­u­la­tive phase will hap­pen:

X will try to prove in PA+1 that and that is in the fea­si­ble set. The lat­ter is im­me­di­ately false, so this will fail.

Next, X will try to prove in PA+2 that and that is in the fea­si­ble set. This too is im­me­di­ately false.

Next, X will try to prove in PA+3 that and that is fea­si­ble (in short, that ), and re­turn 3 if so. This will fail to reach a cy­cle.

Then the bar­gain­ing phase:

Next, X will try to prove in PA+4 that and that is fea­si­ble, and re­turn 3 if so. This will fail iden­ti­cally.

Next, X will try to prove in PA+5 that and that is fea­si­ble, and re­turn 2 if so. This will reach a Löbian cir­cle, and X and Y will both re­turn 2, which is what we want.

• OK! You were right, I mis­in­ter­preted, and I do like this pro­posal!

I con­cur that in the limit as , this does hit the in­ter­sec­tion of the fair­ness curves if the agents are bi­ased in their own fa­vor, and hits the Pareto curve lin­ear mul­ti­ple of each agent’s re­quest if they’re bi­ased in each oth­ers’ fa­vor. More­over, both of these be­hav­iors are in­var­i­ant un­der rescal­ings of util­ity func­tions, so we’re good on that front too!

I haven’t yet thought about whether this works analo­gously in three-player games, but it feels like it should...

• If the fair­ness con­straints are all pair­wise (ie each player has fair­ness curves for each op­po­nent), then the scheme gen­er­al­izes di­rectly. Slightly more gen­er­ally, if each player’s fair­ness set is weakly con­vex and closed un­der com­po­nen­t­wise max, the scheme still gen­er­al­izes di­rectly (in effect the com­po­nen­t­wise max cre­ates a fair­ness curve which can be in­ter­sected with the sur­faces to get the points.

In or­der to gen­er­al­ize fully, the agents should each pre­com­mu­ni­cate their fair­ness sets. In fact, af­ter do­ing this, the al­gorithm is very sim­ple: player X can com­pute what it be­lieves is the op­ti­mal- fea­si­ble-and-fair-ac­cord­ing-to-ev­ery­one point (which is unique be­cause these are all con­vex sets), and if PA proves the out­come will be fair-ac­cord­ing-to-X, then out­put ; oth­er­wise out­put 0.

• I’d like for this to work with as lit­tle prior co­or­di­na­tion as pos­si­ble, so I’m not keen on as­sum­ing the agents pre­com­mu­ni­cate their fair­ness sets. But the gen­er­al­iza­tion with only the pre-co­or­di­nated is neat.

• What’s the harm in re­quiring prior co­or­di­na­tion, con­sid­er­ing there’s already a prior agree­ment to fol­low a par­tic­u­lar pro­to­col in­volv­ing s? (And some­thing ear­lier on in the con­text about a shared source of ran­dom­ness to en­sure con­vex­ity of the fea­si­ble set.)

• The ac­tual prob­lem we want to work to­ward is one where all the prior co­or­di­na­tion info is in the en­vi­ron­ment in­de­pen­dent of the par­tic­u­lar agents (e.g. the ex­is­tence of Schel­ling points), and the agents are just de­duc­ing things about each other. For in­stance, two FairBots work in a source code swap Pri­soner’s Dilemma against one an­other even if writ­ten in differ­ent pro­gram­ming lan­guages.

I’m will­ing to ac­cept “ac­cept­ing a nat­u­ral or­der­ing on the pay­off set” and “ac­cept­ing a nat­u­ral set of out­come prod­ucts” as things that could con­ceiv­ably be Schel­ling points in a sim­ple en­vi­ron­ment, but “know the shape of each oth­ers’ fair­ness sets” looks like an in­finite pre-ex­change of in­for­ma­tion that can­not be gleaned from the en­vi­ron­ment.

(And “gen­er­ate mu­tual ran­dom bits” is a co­op­er­a­tive thing that can be viewed as an atomic ac­tion in the en­vi­ron­ment.)

• Quick point on 2: we could define ac­cept­able solu­tions as those that are Pareto-in­fe­rior to the fair point. This en­sures that there is only one Pareto op­ti­mal fea­si­ble point that is ac­cept­able to ev­ery­one. Of course, it does re­sult in worse solu­tions, but do­ing some­thing like this seems like a good step to­wards solv­ing 1.

• I now think we can do this with­out prior co­or­di­na­tion, in some sense, by us­ing pseu­do­ran­dom bit­strings and lots of or­a­cle calls. (Idea came from a con­ver­sa­tion with Alex Men­nen.)

In­tu­ition: if both play­ers are sam­pling their ac­cept­able out­come sets in ran­dom fash­ion, and each is heav­ily bi­ased to­ward sam­pling points where they do bet­ter, then the first time that they both check the same point at the same level is very prob­a­bly go­ing to be near Eliezer’s fair­ness point.

(As noted in Quinn’s ex­am­ple, we’ll need to make the map from out­put-time to out­come in­jec­tive, but we can do this via the trans­form sug­gested in that draft.)

Con­sider the dis­tri­bu­tion over the agent’s ac­cept­able out­come set with prob­a­bil­ity den­sity pro­por­tional to a pos­i­tive ex­po­nen­tial of the agent’s util­ity func­tion :

if ac­cept­able to , 0 oth­er­wise.

Our agents need to be de­ter­minis­tic, so we’ll have a vast fam­ily of them parametrized by se­quences of draws from this dis­tri­bu­tion. Given a large and a se­quence of drawn from that dis­tri­bu­tion, we have the agent

def A():
for i in range(N):
if PA+i proves A()=a_i im­plies B()=b_i:
re­turn a_i
else re­turn de­fault Nash equil­ibrium


(If we want to do this even more gen­er­ally and not as­sume they’re con­sid­er­ing the same set of or­dered pairs, we can in­stead ask for proofs that , where is the ac­tual util­ity of the uni­verse from A’s per­spec­tive and is the util­ity of a par­tic­u­lar point in the fea­si­ble set.)

If two such agents are play­ing against one an­other, then the prob­a­bil­ity (with re­spect to the se­quence of draws that defined each agent) of a mu­tu­ally ac­cept­able or­dered pair be­ing cho­sen at each step is pro­por­tional to , which is max­i­mized at Eliezer’s ac­cept­able point, and they have chances to get it. For and large, and for very large, with high prob­a­bil­ity two such agents will co­or­di­nate near Eliezer’s ac­cept­able point.

• Note: this re­quires a fur­ther “in­jec­tivity” as­sump­tion to work; see Quinn’s post.

• How about a grid­less scheme like:

The agents agree that they will each out­put how much util­ity they will get, and if they fail to choose a fea­si­ble point they both get 0.

Now dis­cretize the pos­si­ble “rec­t­an­gle ar­eas”: let them be . (This re­quires a way to agree on that, but this seems eas­ier than agree­ing on grid points; the finer the bet­ter, ba­si­cally. Per­haps the most ob­vi­ous way to do it is to have these be evenly spaced from to ; then only and need to be agreed upon.)

X will do the fol­low­ing:

let be the first area in this list that is achieved by a fea­si­ble point on X’s fair­ness curve. (We will as­sume the fair­ness curve is weakly con­vex and weakly in­creas­ing.)

for , let be the “fair” util­ity dis­tri­bu­tion that achieves area ; let .

let be Y’s out­put.

# Spec­u­la­tive phase:

if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

# Bar­gain­ing phase:

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else re­turn .

If both agents fol­low pro­to­col, the re­sult is guaran­teed to be fea­si­ble and to not be above ei­ther agent’s fair­ness curve.

Fur­ther­more, if the in­ter­sec­tion of the fair­ness curves is at a fea­si­ble point that pro­duces rec­t­an­gle area for some and X and Y fol­low the pro­to­col then on the step, they will be able to agree on the co­or­di­nate­wise min of their pro­posed fea­si­ble points with area .

If they’re both re­ally gen­er­ous and their fair­ness curves don’t in­ter­sect in­side the fea­si­ble re­gion, the given pro­to­col will agree on ap­prox­i­mately the high­est fea­si­ble mul­ti­ple of how much they thought they were fairly due, avoid­ing util­ity sac­ri­fice.

• How about a grid­less scheme like:

The agents agree that they will each out­put how much util­ity they will get, and if they fail to choose a fea­si­ble point they both get 0.

Now dis­cretize the pos­si­ble “rec­t­an­gle ar­eas”: let them be . (This re­quires a way to agree on that, but this seems eas­ier than agree­ing on grid points; the finer the bet­ter, ba­si­cally. Per­haps the most ob­vi­ous way to do it is to have these be evenly spaced from to ; then only and need to be agreed upon.)

X will do the fol­low­ing:

let be the first area in this list that is achieved by a fea­si­ble point on X’s fair­ness curve. (We will as­sume the fair­ness curve is weakly con­vex and weakly in­creas­ing.)

for , let be the “fair” util­ity dis­tri­bu­tion that achieves area ; let .

let be Y’s out­put.

# Spec­u­la­tive phase:

if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

# Bar­gain­ing phase:

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else if proves and is fea­si­ble, re­turn .

else re­turn .

If both agents fol­low pro­to­col, the re­sult is guaran­teed to be fea­si­ble and to not be above ei­ther agent’s fair­ness curve.

Fur­ther­more, if the in­ter­sec­tion of the fair­ness curves is at a fea­si­ble point that pro­duces rec­t­an­gle area for some and X and Y fol­low the pro­to­col then on the step, they will be able to agree on the co­or­di­nate­wise min of their pro­posed fea­si­ble points with area .

If they’re both re­ally gen­er­ous and their fair­ness curves don’t in­ter­sect in­side the fea­si­ble re­gion, the given pro­to­col will agree on ap­prox­i­mately the high­est fea­si­ble mul­ti­ple of how much they thought they were fairly due, avoid­ing util­ity sac­ri­fice.