If you don’t know the name of the game, just tell me what I mean to you

Fol­low­ing: Let’s split the Cake

tl;dr: Both the Nash Bar­gain­ing solu­tion (NBS), and the Kalai-Smorod­in­sky Bar­gain­ing Solu­tion (KSBS), though ac­cept­able for one-off games that are fully known in ad­vance, are strictly in­fe­rior for in­de­pen­dent re­peated games, or when there ex­ists un­cer­tainty as to which game will be played.

Let play a bar­gain­ing game, you and I. We can end up with you get­ting €1 and me get­ting €3, both of us get­ting €2, or you get­ting €3 and me get­ting €1. If we fail to agree, nei­ther of us gets any­thing.

Oh, and did I for­get to men­tion that an­other op­tion was for you to get an air­craft car­rier and me to get noth­ing?

Think of that shiny new air­craft car­rier, loaded full with jets, pi­lots, weapons and sailors; think of all the things you could do with it, all the fun you could have. Places to bomb or city har­bours to cruise ma­jes­ti­cally into, with the lo­cals gap­ing in awe at the sleek pow­er­ful lines of your very own ship.

Then for­get all about it, be­cause Kalai-Smorod­in­sky says you can’t have it. The Kalai-Smorod­in­sky bar­gain­ing solu­tion to this game is 12 of a chance of get­ting that ship for you, and 12 of a chance of get­ting €3 for me (the Nash Bar­gain­ing Solu­tion is bet­ter, but still not the best, as we’ll see later). This might be fair; af­ter all, un­less you have some way of re­mu­ner­at­ing me for let­ting you have it, why should I take a dive for you?

But now imag­ine we are about to start the game, and we don’t know the full rules yet. We know about the €’s in­volved, that’s all fine, we know there will be an offer of an air­craft car­rier; but we don’t know who is go­ing to get the offer. If we wanted to de­cide on our bar­gain­ing the­ory in ad­vance, what would we do?

Ob­vi­ously not use the KSBS; it gives 14 of an air­craft car­rier to each player. One ex­cel­lent solu­tion is sim­ple: who­ever has the op­tion of the air­craft car­rier… gets it. This gives us both an ex­pected gain of 12 air­craft car­rier be­fore the game be­gins, su­pe­rior to the other ap­proaches.

Let for­mal­ise this un­cer­tainty over pos­si­ble games. A great game (GG) is a situ­a­tion where we are about to play one of games gj, each with prob­a­bil­ity pj. My util­ity func­tion is U1, yours is U2. Once we choose a bar­gain­ing equil­ibrium which re­sults in out­comes oj with util­ities (aj,bj) for each game, then our ex­pected util­ity gain is (Σpj aj, Σpj bj)=Σpj(aj, bj) Since the out­come util­ities for each games are in­di­vi­d­u­ally con­vex, the set S of pos­si­ble out­come (ex­pected) util­ities for the GG are also con­vex.

Now, we both want a bar­gain­ing equil­ibrium that will be Pareto op­ti­mal for GG. What should we do? Well, first, define:

  • A μ-sum max­imis­ing bar­gain­ing solu­tion (μSMBS) is one that in­volves max­imis­ing the ex­pec­ta­tion of (U1+µU2) in each game, for a pos­i­tive μ.

We’ll ex­tend the defi­ni­tion to μ=∞ by set­ting that to be the bar­gain­ing solu­tion that in­volves max­imis­ing U2. Now this defi­ni­tion isn’t com­plete; there are situ­a­tions where max­imis­ing (U1+µU2) doesn’t give a sin­gle solu­tion (such as those where µ=1, we have to split €10 be­tween us, and we both have util­ities where 1 util­i­ton=1€). Th­ese situ­a­tions are rare, but we’ll as­sume here that any μSMBS comes com­plete with a tie-breaker method for se­lect­ing unique solu­tions in these cases.

The first (ma­jor) re­sult is:

  • For any pos­i­tive µ, μSMBS is Pareto-op­ti­mal for any GG.

To prove this, let oj be the out­comes for game gj, us­ing μSMB, with ex­pected util­ities (aj,bj). The GG has ex­pected util­ities (a,b) =∑pj (aj,bj). Let fµ be the func­tion that maps (x,y) to x+µy. The μSMBS is equiv­a­lent with max­imis­ing the value of fµ for each game.

So now let qj be an­other pos­si­ble out­come set, and ex­pected util­ity (c,d), as­sume to be strictly su­pe­rior, for both play­ers, to (a,b). Now, be­cause µ is pos­i­tive, (c,d) > (a,b) im­plies c>a and µd>µb, so im­plies fµ(c,d) > fµ(a,b). How­ever, by the defi­ni­tion of μSMBS, we must have fµ(aj,bj) ≥ fµ(cj,dj). Since fµ is lin­ear, fµ(a,b)=∑pj fµ(aj,bj) ≥ ∑pj fµ(cj,dj) = fµ(c,d). This con­tra­dicts the as­sump­tion that (c,d) > (a,b), and hence proves that (a,b) is Pareto-op­ti­mal.

This strong re­sult has a con­verse, namely:

  • For any bar­gain­ing solu­tion that is Pareto-op­ti­mal for a given GG, there is a μSMBS that pro­duces the same out­come, in each game gj.

Let oj be the out­comes for a given Pareto-op­ti­mal bar­gain­ing solu­tion, with ex­pected util­ities (aj,bj), and GG hav­ing ex­pected util­ities (a,b) =∑pj (aj,bj). The set S of pos­si­ble ex­pected util­ities for GG is con­vex, and since (a,b) is Pareto-op­ti­mal, it must lie on the bound­ary. Hence there ex­ists a line L through (a,b) such that S lies en­tirely to the left of this line. Let -μ be the slope of L. Thus, there does not ex­ist any (c,d) in the ex­pected util­ities out­comes with fµ(c,d) > fµ(a,b).

Now, if there were to ex­ist an out­come qk for the game gk with ex­pected util­ities (ck,dk) such that fµ(ck,dk) > fµ(ak,bk), then the ex­pected util­ity for the out­comes oj with ok re­placed with pk, would be (c,d) = (a,b) + qk ((ck,dk) - (ak,bk)). This has fµ(c,d) > fµ(a,b), con­tra­dict­ing the pre­vi­ous re­sult. Thus (aj,bj) always max­imise fµ in gj, and hence this bar­gain­ing solu­tion pro­duces the same re­sults as μSMBS (with a given tie-break­ing pro­ce­dure, if needed).

So the best solu­tion, if you are un­cer­tain what the games are you could be play­ing, is to fix a com­mon rel­a­tive mea­sure of value, and then max­imise that, ig­nor­ing con­sid­er­a­tions of fair­ness or any other. To a crude ap­prox­i­ma­tion, cap­i­tal­ism is like this: ev­ery game is sup­posed to max­imise money as much as it can.

Mul­ti­ple games

For the mo­ment, we’ve been con­sid­er­ing a sin­gle game, with un­cer­tainty as to which game is go­ing to be played. The same re­sult goes through, how­ever, if you are ex­pect­ing to play mul­ti­ple games in a row. One caveats is needed: the games must be in­de­pen­dent of each other.

The re­sult holds, for in­stance, in two games with stakes €10, as long as our util­ities are lin­ear in these (small) amounts of money. It does not hold if the first game’s stake is a left shoe and the sec­ond’s is a right shoe, for there the util­ities of the out­comes are cor­re­lated: if I win the left shoe, I’m much more likely to value the right shoe in the sub­se­quent game.

Invariance

Max­imis­ing summed util­ity is in­var­i­ant un­der trans­la­tions (which just add a sin­gle con­stant to each util­ity). It is not, of course, in­var­i­ant un­der scal­ings, and it would be fool­ish in­deed to first de­cide on μ and then al­low play­ers to rescale their util­ities. In gen­eral the μ is not a real num­ber, but a lin­ear iso­mor­phism be­tween the two util­ities, in­var­i­antly defined by some pro­cess.

Kalai-Smorod­in­sky and Nash’s revenge

So, it seems es­tab­lished. μSMBS is the way to go. KSBS and NBS are loser solu­tions, and should be dis­carded. As you’d imag­ine, it’s not quite so sim­ple...

The prob­lem is, which µ? Fix­ing that µ is go­ing to de­ter­mine your ex­pected util­ity for any GG, so it’s an im­por­tant value. And each player is go­ing to have a differ­ent pri­or­ity it, try­ing to min­imise the con­tri­bu­tion of the other agent’s util­ity. So there will have to be some… bar­gain­ing. And that bar­gain­ing will be a one-shot bar­gain­ing deal, not a re­peated one, so there is no su­pe­rior way of go­ing about it. Use KSBS or NBS or any­thing like that if you want; or set µ to re­flect your joint valu­ing of a com­mon cur­rency ($, € or ne­gen­tropy); but you can’t get around the fact that you’re go­ing to have to fix that µ some­how. And if you use μ′SMBS to do so, you’ve just shifted the bat­tle to the value of μ′...

Edit: the mys­tery of µ (mathy, tech­ni­cal, and not needed to un­der­stand the rest of the post)

There has been some spec­u­la­tion on the list as to the tech­ni­cal mean­ing of U1+µU2 and µ. To put this on an ac­cept­able rigor­ous foot­ing, let u1 and u2 be any two rep­re­sen­ta­tives of U1 and U2 (in that u1 and u2 are what we would nor­mally term as “util­ity func­tions”, and U1 and U2 are the set of util­ity func­tions that are re­lated to these by af­fine trans­for­ma­tions). Then µ is a func­tion from the pos­si­ble pairs (u1, u2) to the non-nega­tive re­als, with the prop­erty that it is equiv­ar­i­ant un­der lin­ear trans­for­ma­tions of u1 and in­verse-equiv­ar­i­ant un­der lin­ear trans­for­ma­tions of u2 (in hu­man speak: when u1 gets scaled big­ger, so does µ, and when u2 gets scaled big­ger, µ gets scaled smaller), and in­var­i­ant un­der trans­la­tions. Then we can define U1+µU2 as the set of util­ity func­tions for which u1+µu2 is a rep­re­sen­ta­tive (the prop­er­ties of µ make this well defined, in­de­pen­dently of our choices of u1 and u2). When­ever µ≠0, there is a well defined µ-1, with the prop­erty that µ-1U1+U2 = U1+µU2. Then the case μ=∞ is defined to be μ-1=0.