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

post by Stuart_Armstrong · 2010-10-26T13:43:57.762Z · LW · GW · Legacy · 26 comments

Contents

  Multiple games
  Invariance
  Kalai-Smorodinsky and Nash's revenge
  Edit: the mystery of µ (mathy, technical, and not needed to understand the rest of the post)
None
26 comments

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₁, yours is U₂. 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₁+µU₂) in each game, for a positive μ.

We'll extend the definition to μ=∞ by setting that to be the bargaining solution that involves maximising U₂. Now this definition isn't complete; there are situations where maximising (U₁+µU₂) 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₁+µU₂ and µ. To put this on an acceptable rigorous footing, let u₁ and u₂ be any two representatives of U₁ and U₂ (in that u₁ and u₂ are what we would normally term as "utility functions", and U₁ and U₂ 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₁ and inverse-equivariant under linear transformations of u₂ (in human speak: when u₁ gets scaled bigger, so does µ, and when u₂ gets scaled bigger, µ gets scaled smaller), and invariant under translations. Then we can define U₁+µU₂ as the set of utility functions for which u₁+µu₂ is a representative (the properties of µ make this well defined, independently of our choices of u₁ and u₂). Whenever µ≠0, there is a well defined µ^-1, with the property that  µ^-1U₁+U₂ = U₁+µU₂. Then the case μ=∞ is defined to be μ^-1=0.

26 comments

Comments sorted by top scores.