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

by Stuart_Armstrong5 min read26th Oct 201026 comments


Personal Blog

Following: Let's split the Cake

tl;dr: Both the Nash Bargaining solution (NBS), and the Kalai-Smorodinsky Bargaining Solution (KSBS), though acceptable for one-off games that are fully known in advance, are strictly inferior for independent repeated games, or when there exists uncertainty as to which game will be played.

Let play a bargaining game, you and I. We can end up with you getting €1 and me getting €3, both of us getting €2, or you getting €3 and me getting €1. If we fail to agree, neither of us gets anything.

Oh, and did I forget to mention that another option was for you to get an aircraft carrier and me to get nothing?

Think of that shiny new aircraft carrier, loaded full with jets, pilots, weapons and sailors; think of all the things you could do with it, all the fun you could have. Places to bomb or city harbours to cruise majestically into, with the locals gaping in awe at the sleek powerful lines of your very own ship.

Then forget all about it, because Kalai-Smorodinsky says you can't have it. The Kalai-Smorodinsky bargaining solution to this game is 1/2 of a chance of getting that ship for you, and 1/2 of a chance of getting €3 for me (the Nash Bargaining Solution is better, but still not the best, as we'll see later). This might be fair; after all, unless you have some way of remunerating me for letting you have it, why should I take a dive for you?

But now imagine we are about to start the game, and we don't know the full rules yet. We know about the €'s involved, that's all fine, we know there will be an offer of an aircraft carrier; but we don't know who is going to get the offer. If we wanted to decide on our bargaining theory in advance, what would we do?

Obviously not use the KSBS; it gives 1/4 of an aircraft carrier to each player. One excellent solution is simple: whoever has the option of the aircraft carrier... gets it. This gives us both an expected gain of 1/2 aircraft carrier before the game begins, superior to the other approaches.

Let formalise this uncertainty over possible games. A great game (GG) is a situation where we are about to play one of games gj, each with probability pj. My utility function is U1, yours is U2. Once we choose a bargaining equilibrium which results in outcomes oj with utilities (aj,bj) for each game, then our expected utility gain is (Σpj aj, Σpj bj)=Σpj(aj, bj) Since the outcome utilities for each games are individually convex, the set S of possible outcome (expected) utilities for the GG are also convex.

Now, we both want a bargaining equilibrium that will be Pareto optimal for GG. What should we do? Well, first, define:

  • A μ-sum maximising bargaining solution (μSMBS) is one that involves maximising the expectation of (U1+µU2) in each game, for a positive μ.

We'll extend the definition to μ=∞ by setting that to be the bargaining solution that involves maximising U2. Now this definition isn't complete; there are situations where maximising (U1+µU2) doesn't give a single solution (such as those where µ=1, we have to split €10 between us, and we both have utilities where 1 utiliton=1€). These situations are rare, but we'll assume here that any μSMBS comes complete with a tie-breaker method for selecting unique solutions in these cases.

The first (major) result is:

  • For any positive µ, μSMBS is Pareto-optimal for any GG.

To prove this, let oj be the outcomes for game gj, using μSMB, with expected utilities (aj,bj). The GG has expected utilities (a,b) =∑pj (aj,bj). Let fµ be the function that maps (x,y) to x+µy. The μSMBS is equivalent with maximising the value of fµ for each game.

So now let qj be another possible outcome set, and expected utility (c,d), assume to be strictly superior, for both players, to (a,b). Now, because µ is positive, (c,d) > (a,b) implies c>a and µd>µb, so implies fµ(c,d) > fµ(a,b). However, by the definition of μSMBS, we must have fµ(aj,bj) ≥ fµ(cj,dj). Since fµ is linear, fµ(a,b)=∑pj fµ(aj,bj) ≥ ∑pj fµ(cj,dj) = fµ(c,d). This contradicts the assumption that (c,d) > (a,b), and hence proves that (a,b) is Pareto-optimal.

This strong result has a converse, namely:

  • For any bargaining solution that is Pareto-optimal for a given GG, there is a μSMBS that produces the same outcome, in each game gj.

Let oj be the outcomes for a given Pareto-optimal bargaining solution, with expected utilities (aj,bj), and GG having expected utilities (a,b) =∑pj (aj,bj). The set S of possible expected utilities for GG is convex, and since (a,b) is Pareto-optimal, it must lie on the boundary. Hence there exists a line L through (a,b) such that S lies entirely to the left of this line. Let -μ be the slope of L. Thus, there does not exist any (c,d) in the expected utilities outcomes with fµ(c,d) > fµ(a,b).

Now, if there were to exist an outcome qk for the game gk with expected utilities (ck,dk) such that fµ(ck,dk) > fµ(ak,bk), then the expected utility for the outcomes oj with ok replaced with pk, would be (c,d) = (a,b) + qk ((ck,dk) - (ak,bk)). This has fµ(c,d) > fµ(a,b), contradicting the previous result. Thus (aj,bj) always maximise fµ in gj, and hence this bargaining solution produces the same results as μSMBS (with a given tie-breaking procedure, if needed).

So the best solution, if you are uncertain what the games are you could be playing, is to fix a common relative measure of value, and then maximise that, ignoring considerations of fairness or any other. To a crude approximation, capitalism is like this: every game is supposed to maximise money as much as it can.

Multiple games

For the moment, we've been considering a single game, with uncertainty as to which game is going to be played. The same result goes through, however, if you are expecting to play multiple games in a row. One caveats is needed: the games must be independent of each other.

The result holds, for instance, in two games with stakes €10, as long as our utilities are linear in these (small) amounts of money. It does not hold if the first game's stake is a left shoe and the second's is a right shoe, for there the utilities of the outcomes are correlated: if I win the left shoe, I'm much more likely to value the right shoe in the subsequent game.


Maximising summed utility is invariant under translations (which just add a single constant to each utility). It is not, of course, invariant under scalings, and it would be foolish indeed to first decide on μ and then allow players to rescale their utilities. In general the μ is not a real number, but a linear isomorphism between the two utilities, invariantly defined by some process.

Kalai-Smorodinsky and Nash's revenge

So, it seems established. μSMBS is the way to go. KSBS and NBS are loser solutions, and should be discarded. As you'd imagine, it's not quite so simple...

The problem is, which µ? Fixing that µ is going to determine your expected utility for any GG, so it's an important value. And each player is going to have a different priority it, trying to minimise the contribution of the other agent's utility. So there will have to be some... bargaining. And that bargaining will be a one-shot bargaining deal, not a repeated one, so there is no superior way of going about it. Use KSBS or NBS or anything like that if you want; or set µ to reflect your joint valuing of a common currency ($, € or negentropy); but you can't get around the fact that you're going to have to fix that µ somehow. And if you use μ'SMBS to do so, you've just shifted the battle to the value of μ'...


Edit: the mystery of µ (mathy, technical, and not needed to understand the rest of the post)

There has been some speculation on the list as to the technical meaning of U1+µU2 and µ. To put this on an acceptable rigorous footing, let u1 and u2 be any two representatives of U1 and U2 (in that u1 and u2 are what we would normally term as "utility functions", and U1 and U2 are the set of utility functions that are related to these by affine transformations). Then µ is a function from the possible pairs (u1, u2) to the non-negative reals, with the property that it is equivariant under linear transformations of u1 and inverse-equivariant under linear transformations of u2 (in human speak: when u1 gets scaled bigger, so does µ, and when u2 gets scaled bigger, µ gets scaled smaller), and invariant under translations. Then we can define U1+µU2 as the set of utility functions for which u1+µu2 is a representative (the properties of µ make this well defined, independently of our choices of u1 and u2). Whenever µ≠0, there is a well defined µ-1, with the property that  µ-1U1+U2 = U1+µU2. Then the case μ=∞ is defined to be μ-1=0.

Personal Blog