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.

Figure 1: the feasibility set. (We'll assume the agents have access to mutual randomness, as in "60% chance you take action p and I take action P, 40% chance you take action q and I take action Q", so that the set is convex.)

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.

Figure 2: The Nash bargaining solution (point N).

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.

Figure 3: the acceptable sets for X (with fairness point N) and Y (with fairness point B), and the best mutually acceptable point E.

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:

Figure 4: the grid lines and grid points.

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.

Figure 5: Grid levels labeled objectively by color, and an arbitrary ordering of grid points (subject to the constraint that it respects the grid level ordering).

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.

Figure 6: Agent X will try Löbian cooperation in PA+1 at point 1, then PA+3 at point 3, PA+4 at point 4, PA+6 at point 6, and so on within its acceptable set. Agent Y will try Löbian cooperation in PA at point 0, PA+2 at point 2, PA+5 at point 5, PA+6 at point 6, and so on within its acceptable set. X and Y thus achieve Löbian cooperation at point 6.

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?