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 g_{j}, each with probability p_{j}. My utility function is U_{1}, yours is U_{2}. Once we choose a bargaining equilibrium which results in outcomes o_{j} with utilities (a_{j},b_{j}) for each game, then our expected utility gain is (Σp_{j} a_{j}, Σp_{j} b_{j})=Σp_{j}(a_{j}, b_{j}) 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 (U
_{1}+µU_{2}) in each game, for a positive μ.

We'll extend the definition to μ=∞ by setting that to be the bargaining solution that involves maximising U_{2}. Now this definition isn't complete; there are situations where maximising (U_{1}+µU_{2}) 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 o_{j} be the outcomes for game g_{j}, using μSMB, with expected utilities (a_{j},b_{j}). The GG has expected utilities (a,b) =∑p_{j} (a_{j},b_{j}). 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 q_{j} 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µ(a_{j},b_{j}) ≥ fµ(c_{j},d_{j}). Since fµ is linear, fµ(a,b)=∑p_{j} fµ(a_{j},b_{j}) ≥ ∑p_{j} fµ(c_{j},d_{j}) = 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 g
_{j}.

Let o_{j} be the outcomes for a given Pareto-optimal bargaining solution, with expected utilities (a_{j},b_{j}), and GG having expected utilities (a,b) =∑p_{j} (a_{j},b_{j}). 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 q_{k} for the game g_{k} with expected utilities (c_{k},d_{k}) such that fµ(c_{k},d_{k}) > fµ(a_{k},b_{k}), then the expected utility for the outcomes o_{j} with o_{k} replaced with p_{k}, would be (c,d) = (a,b) + q_{k} ((c_{k},d_{k}) - (a_{k},b_{k})). This has fµ(c,d) > fµ(a,b), contradicting the previous result. Thus (a_{j},b_{j}) always maximise fµ in g_{j}, 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.

**Invariance**

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 U_{1}+µU_{2} and µ. To put this on an acceptable rigorous footing, let u_{1} and u_{2} be any two representatives of U_{1} and U_{2} (in that u_{1} and u_{2} are what we would normally term as "utility functions", and U_{1} and U_{2} 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 u_{1} and inverse-equivariant under linear transformations of u_{2} (in human speak: when u_{1} gets scaled bigger, so does µ, and when u_{2} gets scaled bigger, µ gets scaled smaller), and invariant under translations. Then we can define U_{1}+µU_{2} as the set of utility functions for which u_{1}+µu_{2} is a representative (the properties of µ make this well defined, independently of our choices of u_{1} and u_{2}). Whenever µ≠0, there is a well defined µ^{-1}, with the property that µ^{-1}U_{1}+U_{2} = U_{1}+µU_{2}. Then the case μ=∞ is defined to be μ^{-1}=0.