This is a two-part sequence of posts, in the ancient LessWrong tradition of decision-theory-posting. This first part will introduce various concepts of bargaining solutions and dividing gains from trade, which the reader may or may not already be familiar with.

The upcoming part will be about how all introduced concepts from this post are secretly just different facets of the same underlying notion, as originally discovered by John Harsanyi back in 1963 and rediscovered by me from a completely different direction. The fact that the various different solution concepts in cooperative game theory are all merely special cases of a General Bargaining Solution for arbitrary games, is, as far as I can tell, not common knowledge on Less Wrong.

Bargaining Games

Let's say there's a couple with a set of available restaurant options. Neither of them wants to go without the other, and if they fail to come to an agreement, the fallback is eating a cold canned soup dinner at home, the worst of all the options. However, they have different restaurant preferences. What's the fair way to split the gains from trade?

Well, it depends on their restaurant preferences, and preferences are typically encoded with utility functions. Since both sides agree that the disagreement outcome is the worst, they might as well index that as 0 utility, and their favorite respective restaurants as 1 utility, and denominate all the other options in terms of what probability mix between a cold canned dinner and their favorite restaurant would make them indifferent. If there's something that scores 0.9 utility for both, it's probably a pretty good pick!

Although, there's something off about setting up the problem like this. There's no term for intensity of preferences! Someone who cared very little about food would have their preferences rank just as strongly as someone who had strong restaurant opinions!

In a sense, there's three responses to this objection.

The first response is that we might be zooming in too hard on the restaurant bargaining game in particular. In a broader context, a person having weak restaurant preferences may just be another way of saying that they are quick to trade off their choice of restaurant to someone else in return for other things they might desire. And so, in the broader bargaining game of a relationship where more is at stake than this one-time choice of restaurant, things may be fair. But in the restaurant bargaining game in particular, things can look unfair for the losing party, when in fact they traded off "ability to determine restaurant" in exchange for more concessions elsewhere. The generalization of this is that bargaining equilibria of an overall game might be quite different from just summing up the bargaining equilibria of the subgames.

The second response is that people care a nonzero amount about other people, and so someone with weak food preferences might be equally well modeled as someone with a strong preference that their partner get what they want. That can be folded into the utility function, however. Just make the ratings of the deferential person mostly copy the ratings of their partner.

And the third response is one of the most interesting. For a perfectly selfish person who always tries for their favorite foods and doesn't care at all about your pouting at disfavored restaurants, there really isn't much of a difference between having strong preferences for food and weak preferences for food, they'll still drive as hard of a bargain against you as they can, if there isn't some mitigating factor.

Much like the post about how the TRUE prisoner's dilemma is not the standardly framed version, but more like "a human civilization fighting with a paperclip maximizer for resources which can either save millions of lives, or make a few paperclips", the TRUE bargaining problem isn't couples deciding where to eat, but something more like "deciding how to split a pile of resources with nonsentient aliens that are willing to fight you over the resource pile". 

Accordingly, using the term "fair" for any of these mathematical concepts has the problem of automatically importing human concepts of fairness, which needs to be resisted in order to look clearly at what the math is doing. It'll be handy to have a separate word for "a mathematically distinguished point in a game where both parties have an interest in preventing destructive conflicts, that's neutral enough that aliens would probably come up with it" to enforce that mental separation. Let's use "chaa" as a nonsense word to denote that concept (the Lawful Neutral Alien analogue of fairness), since it makes it a lot easier to point at situations where the chaa outcome splits apart from the fair outcome.

The relevant questions to ask to work out what the chaa outcome is are things like "what are our best alternatives to a negotiated agreement and how does it compare to the choices on offer for us" instead of "how strong are our preferences compared to each other", (which is more relevant to fairness)

Anyways, returning to our restaurant game, to actually answer the question of what to do, let's see how we set up the problem.

We plotted the utilities of the various options, and got a scattering of points on the plane, where one of the coordinates is the utility assigned to the outcome by Alice, and the other is the same for Bob.

One extremely important note is that it should be possible to randomize between various options. For instance, if there's only two options, one where player 1 wins completely, and one where player 2 wins completely, an obviously chaa outcome is the players flipping a coin to decide who wins.

In graphical terms, access to randomization lets us set up situations that can attain any utility pair in the convex hull of these points.

So, which points in this shape are chaa outcomes?

Well, "chaa" hasn't been defined yet, but if it's about how to split gains between agents in a neutral way without getting into destructive conflicts, there's three obvious properties that such a solution must have.

First, since chaaness is partially about not getting into destructive conflicts, any chaa point should be on the Pareto frontier. Namely, there shouldn't be an alternative that leaves both players strictly better off. After all, if you have a prospective definition of "chaa" that demands that both players leave spare utility on the table, they should be able to take that as their new disagreement point, do another round of bargaining, and attain an outcome which is Not That and better for both. And then, this process would give you a new notion of chaaness that's just strictly better for all agents to use. So, whatever point is selected, it must be from the upper-right boundary of the shape.

Second, the definition of a chaa point shouldn't be sensitive to the exact utilities used. You can add any constant to a utility function, or multiply it by any positive constant, and it'll be the same utility function. Reporting your preferences as the function  should get you the same result as if you reported your preferences as the function , or if you reported your preferences as the function . No matter how the players relabel their utility functions and scale and shift them, it shouldn't affect anything because their underlying preferences didn't change.

This is convenient because it means that we can always rescale the disagreement point to  utility, and the highest utility a player can get (without making it so the other player would rather go for the disagreement point) to  utility. So, you only really have to consider problems where your convex shape fits in a unit square like this.

This leads nicely into our third desiderata. If the convex shape is symmetric, then the two players are in an identical position. Thus, any neutral way of selecting gains for the two players must be indifferent between which player is first and which is second, and so the chaa point should end up being on the line of symmetry, or on the halfway point. If one of the players is selected to win completely, the chaa outcome should involve flipping a coin to decide who wins. For the prisoner's dilemma, the chaa outcome should be mutual cooperation. For the game of chicken, the chaa outcome should be flipping a coin to decide who goes straight and who swerves.

These three desiderata are as obvious as can be, but past this they get a whole lot more controversial.

The Kalai-Smorodinsky Bargaining Solution is "Rescale things so the disagreement outcome is at , and 1 utility for a player is the maximum utility they can get without sending the foe below 0 utility. Draw a diagonal line from  to , pick where the line crosses the Pareto frontier."

Pretty simple, right? It's the only way of picking a point that fits all three of our desiderata, and also fulfills the extra property of monotonicity, which is basically saying that, if you move the Pareto-frontier points for a player up, they should get more utility.

Yes, yes, I didn't quite do it correctly, that point of the blue shape in the bottom-right corner isn't scaled appropriately, but eh, it's close enough. It makes it pretty clear what we're doing with the line and how it is that moving the various points up (to go from the blue shape to the purple shape) increases the expected utility of the player whose utility is being plotted on the y coordinate. After all, if you've got better options, a chaa outcome shouldn't leave you with lower expected utility!

Well... that's a bit of a fiddly issue. Remember, utility functions are scale-and-shift invariant. So, when we move these Pareto-frontier points up, we're not REALLY getting extra utility, this operation is really more like making the utility function more squashed at the top.

Hopefully, monotonicity doesn't look completely obvious now, though it still has an awful lot of intuitive force.

The Nash Bargaining Solution, by contrast, is "pick the point on the frontier that maximizes the area of the rectangle made between that and the disagreement point". It's nonobvious that this process doesn't depend on how we scale or shift the various utility functions, but it's true anyways. Maximizing the area of a rectangle isn't as obvious of a thing to do as "draw a diagonal line". It is pretty mathematically neutral, though.

Also, both the Kalai-Smorodinsky and Nash bargaining solutions happen to agree on which point to pick in the restaurant game, namely, a 2/3 chance of italian food, and a 1/3 chance of sushi. Although these solutions don't usually coincide.

The Nash Bargaining Solution is the only one that fulfills the usual three desiderata, and the axiom of Independence of Irrelevant Alternatives. Ie, if the final bargaining solution involved you doing a 60-40 mix between option D and option E, then deleting any of the options that aren't D or E from the set of available options doesn't affect what happens. Untaken options are irrelevant.

To put it mildly, this is not really a desiderata at all, it's actually an extremely baffling property. Let's say Alice and Bob bargain and hit on the Nash bargaining solution.


Then this axiom is saying that it'd be possible to delete all of the options that disproportionately favor Alice, making a game that looks like this, and their bargaining process would still hit the same point.

Intuitively, if options disproportionately favor you, you can use them as "bargaining chips", going "alright, I'll take these unfair options off the table, but only if you remove your unfair options from the table". Independence of Irrelevant Alternatives is basically saying that you can lose all your "unfair bargaining chips" and it'd have no effect on the net outcome!! Phrased like that, it's not clear why anyone would be interested in the Nash bargaining solution.

There are other, more obscure, bargaining solutions which have appeared in the literature, which won't be covered, though they all at least fulfill our basic three criteria.

So, for bargaining games, we can make some progress towards figuring out what a chaa outcome is (Pareto-efficient, scale-and-shift invariant, symmetric), but we don't have enough information yet to single out one particular bargaining solution as The One True Chaa Point, and in fact, it looks like there actually isn't a point like that; the various options all look pretty plausible.

The other issue is that not all games are bargaining games. Bargaining games require everyone to agree on what to do, and there are well-defined disagreement utilities for if negotiations break down. Clearly, this doesn't describe all, or even most, games. Now, it's time to look at another special case of games, for another notion of chaaness.

Cooperation/Competition Values

For full credit, I was introduced to this notion by this wonderful post, which itself was exposition of this wonderful paper by Kalai and Kalai.

Instead of bargaining games, we'll now be looking at transferrable utility games. A transferrable utility game is one where there's a single resource (like dollars) where everyone's utility is linear in that resource, and everyone can pay everyone else in that resource and has enough of the resource to actually do so.

Put another way, bargaining games are like bartering. Both sides must agree on what trade to make, and if either one doesn't like it, the transaction doesn't happen. Transferrable utility games are like arbitrary games that take place after money has been invented. There may no longer be a clear disagreement point for what happens when the various parties disagree, but it's also possible for everyone to settle matters by being clever about how they pay each other, which opens up a lot of options.

In particular, when there's a common resource like dollars, you can make everyone express their preferences in terms of dollars. This breaks the usual attribute of utility functions where you can scale and shift them as you please without affecting anything. You can't multiply one player's utilities (as denominated in dollars) by a factor of 100 without doing the same to everyone else. A collective scaling like that, where everyone's numbers go up by 100, is like a currency conversion, shifting from denominating everyone's utilities in dollars to denoting everyone's utilities in cents. It doesn't meaningfully change anything. Interestingly enough, we still do have individual shift-invariance. Put another way, you might be indifferent between option A and option B plus 300 dollars. Then that's consistent with scoring option A at 400 and option B at 100, or you can score option A at 700 and option B at 400. You can add or subtract whatever you want from options A and B, as long as the difference between the two options is 300.

So, in a totally general two-player game, with no well-defined disagreement point, but with the ability to pay each other money, and with everyone's utilities denominated in terms of money, is there some suitably chaa point?

Yes. Time to explain the CoCo value. CoCo stands for Cooperation/Competition, as there's two cases of games where the "right answer" is super-obvious. In pure-cooperation games where both players have the exact same utility function, you just pick the best option in the expectation the foe will do the same. In pure-competition games (ie, zero-sum games), you maximize your worst-case score, as your opponent has perfectly opposing interests to you and so will be minimizing your utility.

As it turns out, when both player's utility functions are commensurable (through this common currency), it's always possible to uniquely split any 2-player game at all into two other games. One is a pure-cooperation game, where both players have the same utility function, and perfectly aligned interests. The other is a pure-competition game, where both players have opposite utility functions, and perfectly opposed interests. The CoCo point is  "cooperate as much as possible on the cooperative game where our interests align, and fight it out in the zero-sum game where our interests oppose, and add up our results from the two games to figure out how much value we both get".

And so, that's the CoCo point. You pick the most cooperative point in the cooperation game for what to actually do (to maximize the total amount of monetary gain for everyone), and use the results of the competition game to decide how much the two players pay each other, where the zero-sum aspect of the competition game ensures that the budget balances.

Being a bit more formal about this, we'll use  for the function mapping outcomes to player A's utilities, and  for the function mapping outcomes to player B's utilities.

For the cooperation game, both players A and B have the utility functions . Clearly, this is a pure cooperation game.

For the competition game, player A has the utility function  and player B has the utility function . Clearly this a pure competition game, as the utilities for any outcome add up to 0.

And note that for player A, adding up their utilities for the cooperation game and competition game yields , ie, their original utility function (and the same for player B)

Here's a concrete example, lifted from the previous post on the topic. Bob and Alice can sell hotdogs at the beach or the airport. If they're at the same location, they end up competing over customers, halving both their profits. Alice is twice as efficient as Bob at selling hotdogs, and the beach has twice as many customers as the airport.

Bob/AliceBeachAirport
Beach50/100100/100
Airport50/20025/50

It splits into a cooperation game and a competition game.

Bob/AliceBeachAirport
Beach75/75100/100
Airport125/12537.5/37.5
Bob/AliceBeachAirport
Beach-25/250/0
Airport-75/75-12.5/12.5

The best move in the cooperation game is Bob going to the airport, and Alice going to the beach, so that's what's played in real-life. The utility from the cooperation game is added to the maximin utility from the competition game (where beach/beach is played), for 100 Bob utility and 150 Alice utility. And so, the solution is that Alice goes to the beach and pays Bob 50 bucks to go to the airport.

This has a whole lot of good properties, as detailed in the Adam Kalai and Ehud Kalai paper linked above. It's the unique solution that fulfills all of

1: Pareto-optimality, it never leaves monetary value on the table.

2: Shift invariance. If one player gets a gift of 100 dollars at the start of a game, they'll walk out of the game 100 dollars richer than they would if they hadn't received the gift. You can add any constant amount of money to anyone's payoffs and it does nothing.

3: Payoff dominance. If player A gets more money than player B in all cells, then player A will leave the game with more money than player B.

4: Invariance to redundant strategies. Adding a new action that could just as well be accomplished by a probabilistic mix between other actions does nothing.

5: Action monotonicity. Adding a new action is always good for you: you never regret having a larger action space (though other players may regret you having a larger action space).

6: Information monotonicity. This is for the imperfect-information generalization of the CoCo value, that's detailed in the Kalai paper. Giving a player more information about what everyone else is doing can't hurt them: you'll never regret knowing more.

And the CoCo value is the unique solution that fulfills all six of those properties above. There doesn't seem to be any comparably good notion of equilibrium available besides this, and so we can say that any sensible definition of "chaa" for arbitrary games (if one exists) should manage to recover the CoCo value as a special case when presented with games with transferrable utility.

An interesting note. For bargaining games with transferrable utility (like, a bargaining game where you can pay each other), the equilibrium notion you get is "denominating both player's utility functions in dollars, pick the option that maximizes the overall monetary surplus over the disagreement point, and pay each other so both players equally split the monetary surplus"

Like, if the surplus-maximizing option is one that player 1 values at +80 dollars over the disagreement point, and player 2 values at +40 over the disagreement point, for +120 dollars of surplus value, the CoCo solution is that particular option is picked, and player 1 gives player 2 20 dollars, so both sides walk away with +60 dollars worth of utility.

If Pedro the street vendor and Pierre the rich tourist are haggling over the price of a burrito, and Pedro would walk away at 2$, and Pierre would walk away at 14$, then the CoCo solution is that the burrito is sold for 8$, because that's halfway between where the two people would rather walk.

When arguing over which movie to pick for a group movie night, everyone just needs to report how much they'd value seeing the various movies, pick the movie that maximizes total monetary surplus, and pay each other to equalize that surplus (so you get money if you have to sit through a movie you enjoy less than everyone else in your group, and if you're watching a personal favorite movie that everyone else is "meh" about, like Kong vs Godzilla 5, you've gotta pay the others to watch it.)

Actually, first maximizing surplus value, and then equally splitting the monetary gain, seems quite fair. Yes, we just used the F word.

Shapley Value

Let's say a bunch of people contribute various amounts of effort to a project, for various amounts of gain, creating an overall pile of money. What's a chaa way to fairly divide their pile of money?

We can impose some desiderata.

1: All the money should be going to someone. If the chaa division involved burning money, you should come up with an alternate notion of "chaa" which everyone agrees is better and which is Not That.

2: A player which contributes absolutely nothing to the project and just sits around, regardless of circumstances, should get 0 dollars.

3: If two players in the game are equivalent in all ways and totally interchangeable, then they should receive equal payoffs.

4: If the total pile of money is  times as big, everyone should get  times as much.

5: If two projects are completed in a row and the chaa division occurs, adding together someone's chaa share from project A and project B (considered individually) should be their chaa share from "do both projects in a row". Or, payoffs shouldn't depend on precisely how you slice up the projects.

 

As it turns out, this uniquely pins down how to divide the pile of resources! If  is the set of all players, and  is a particular player, and  (for ) is the total amount of resources that could be produced by all the players in  working together, then the payoff for player  is

Put another way, this is effectively going "if the players were added to the group in a random order, and everyone demanded all the marginal extra value they produced upon being added to the group, you'd get payoffs for everyone. Average the payoffs over all possible random orderings". That factorial term at the start is going "what are the odds that group S gets assembled (in any order), and then I get added to it?". And then the second term is "demanding my marginal contribution".

Here's a previous post about actually working out the Shapley values in several toy examples of games, to get some intuition for what they're doing.

Uniting the Shapley and CoCo Values

Before we get to the next post tying everything together, we'll see that the Shapley and CoCo values actually have a highly unexpected connection. If you try generalizing the CoCo value to n players, you get something that looks suspiciously Shapley-like.

Let's begin by reshuffling the Shapley values into a different form. The Shapley value for player i starts off as

Now, we can pair off the various coalitions with each other. The subset  will be paired off with the subset , the set of all the players that aren't in  and aren't . In particular, note that in both cases, the coefficient in front ends up being . It's then possible to swap the the values around between those two paired coalitions, producing a restatement of the Shapley value as

And then, instead of writing this as a sum over subsets that lack player , we can switch to the complement and write this as a sum over subsets which include player , although the factorial term has to be adjusted a bit to compensate for the fact that the complement of  has a cardinality of  instead of 

This restatement of the Shapley value will be useful later.

And now we'll try generalizing the CoCo value to n-player games with transferrable utility. Let's deal with a 3-player game, just to make things a bit simpler. The players are . As it turns out, this game will actually split into four games instead of two. There's the pure cooperation game, a zero-sum  vs everyone else game, a zero-sum  vs everyone else game, and a zero-sum  vs everyone else game.

For the first game, the utility functions for , and  are .

For the zero-sum  vs everyone else game, the utility function for  is , and the utility functions for  are  for both. You might be wondering "why 6?". And the answer is it's that way in order for the game to be zero-sum; the opposing players are weighted less to compensate for there being more of them. Also note that B and C have perfectly aligned incentives in this game, so they might as well perfectly coordinate.

For the zero-sum  vs everyone else game, the utility function for  is  for both, and for  it's .

And similar for .

For the player , adding up the payoff for all the games gives you

(and similar for all the other players)

And for each game in particular except for the pure cooperation game, it's zero-sum.

Now that we've seen that concrete example, let's generalize to  players. There are  subgames that the original game will split into, one game for each way to divide the players into two coalitions. Let  be the set of players in one of these coalitions.

For the game with  vs , the utility functions of everyone on coalition  will be

And the utility functions of everyone in the coalition , will be

It's not too hard to show that all these games are zero-sum (except for the one with the coalition of all players), with perfectly aligned incentives within a coalition.

Anyways, the value that player  gets is the sum of the values it gets from all of the component games where coalitions compete against each other. Or, the payoff for player  will be


Basically, do a weighted sum over "utility of my coalition minus utility of their coalition if the coalitions zero-sum fought" over all the coalitions that you're a part of, and that's your CoCo value in the n-player case.

But remember, the Shapley value can be re-expressed as

Which should look suspiciously similar, especially when you remember that  is the value that everyone on your coalition can produce by working together, and  is the value of the opposing coalition. Really, the CoCo values are just Shapley values but generalized to any sort of game where there's transferrable utility. The analogue of "add players in a random order, you get your marginal contribution" turns out to be "add players to a team in a random order, if you're added to team , your increase in value from that is the marginal increase in the value of the team if it got into a zero-sum competition against the entire rest of the world."

Ok, so the CoCo values are basically modified Shapley values, so these two are related to each other. Can we generalize even further?

Well, as it turns out, we'll be able to connect the CoCo value to the Nash bargaining solution to get solutions for games in general. I came at this problem from the direction of generalizing the CoCo value to games with nontransferable utility, since the CoCo values were so nicely behaved that any solution for games in general should replicate the CoCo values when utility happens to be transferrable, and it turned out my solution automatically spat out the Nash bargaining solution as a special case, which was a considerable surprise to me.

And then it turned out that Harsanyi came up with the same sort of solution from a completely different direction (but more elaborate and incorporating constraints that I missed) all the way back in 1963 by trying to generalize the Nash bargaining solution to games with no clear disagreement point. Next post, we'll cover this unifying concept.

New Comment
41 comments, sorted by Click to highlight new comments since:

This is fantastic and I am definitely looking forward to the next post.

Something I've often wondered about though is that the definition of fairness (though not necessarily of chaa!) seems strongly dependent on who, exactly, is taken into account as being a player of the game, which to me seems quite arbitrary. This concern isn't about the math or reasoning of the post, so much as my lack of clarity about how exactly it ought to be applied in real life.

Example: a factory owner is bargaining with his employees over pay. He points out that since he provides the capital needed for the factory to run in the first place, he has a significantly higher Shapley value than any individual worker, and deserves more wages. But an employee counters this by reminding him of all the people who built the factory, and the people who did the scientific research for how to design the machines, and the truckers who moved items to the construction site when the factory was being built - and even the employer's parents, whose wealth he inherited and used to fund building the factory in the first place. If you include all of those people as part of the "game" of the company, since their contributions were also partly responsible for its success and for any profits it makes, suddenly the Shapley value of the owner seems much smaller.

The same thing goes for other situations. Even games with a competitive element often have players (people affected by, and able to affect, the outcome) who are not obvious on the surface. Wars are games between not only national governments, but also corporations and wealthy elites who have a stake in the outcome - and large enough groups of concerned citizens, at least in democracies, can also affect what happens and force their values to be taken into account. So, in situations like that - situations where it's not clear exactly who the players even are - how can one find the fair outcome?

Actually, I just checked this, if you split the factory owner into multiple agents, the workers capture less and less of the value.

What model are you using to conclude the workers capture less value?

I'm reasonably sure Shapley values are preserved under agent decomposition.  That is, if you split agent A into multiple agents B+C who collectively make the same contribution as A, their combined share should be the same as A's original share.

Though I don't know whether/how you can extend this model to handle the fact that players can join and leave the "game"--workers can quit, other workers can be hired, the owner could decide not to build the factory but a different tycoon could build one instead, etc.  This means you aren't dealing with a fixed pool of "players".  (One theoretical option is to treat the entire world as one giant game, but then the problem becomes intractable.)

It becomes a lot more obvious when you consider two factors; 1, that every agent wants to maximize its utility, and 2, that no split will be agreed to if it makes one agent worse off for participating in the trade than their bull action. Consider our simplest factory case: a factory that requires 1 owner to supply capital and one worker to provide labor. Since both are required to obtain the output, you split the gains from trade by taking the income from the factory, paying out the costs to bring both agents to net 0 from agreeing to the trade (ie, maintenance on the capital, taxes, insurance against work injuries, food to replace calories expended in labor, etc). Then whatever is left, the profit, gets split between both.

Now expand this. If there is one supplier of Capital and 2 workers, but it still only needs 1 worker to function, how does the split go? If the workers have good decision theory, they realize their best option is to coordinate. The Capital provider and the Laborer each get 50-50 split, and since each laborer has a 50% chance to be chosen that comes out to 50-25-25. This comes from a few factors. First, the Capital owner won’t accept less than half. If he is better off refusing to deal with B entirely and just trade with A, obviously he will do that, so our split has to be at least 50 to him. However, the workers also won’t accept less than 25 in expectation, or else they are both better off with one of them going to the other and saying “I won’t compete with you in exchange for half your profit.” A 50% chance at a 70-30 split (since there is a half chance each is chosen) is worse than that in expectation, even if the nominal payout is higher. Thus if the owner won’t accept less than half and our workers won’t accept less than a quarter, the only possible split is 50-25-25. Since our position is symmetric, 2 Capital providers and one laborer get a 25-25-50 split. Assuming there are 2 of each, that comes down to 2 50-50 splits again, since any lesser split has a better alternative that one party can force. Thus in any trade that requires one member of party A to contribute and one of Party B, each member of party A gets 1/2*#A and each member of B gets 1/2*#B. If the factory requires 2 workers to function, you can treat those two workers as a single agent that distributes half of the profit between them.

This has a few desirable outcomes.

  1. For one, you are never better off for having more competition
  2. You are never worse off for having more people to trade with
  3. There is no coordination between agents that can reduce this to a simpler form that gets in expectation a higher payout for that group
  4. it is agnostic of which of a set of interchangeable options is chosen.
  5. There is no incentive to create dummy agents

And most importantly,

  1. it is very simple to calculate. However many workers there are split between them half of the profit, irrespective of how large the labor pool is. This gets them in expectation less money since they have less chance of getting picked, but doesn’t change the amount changing hands in each actual timeline.

First, I note that this comment thread was previously about Shapley values, and you don't seem to have done any Shapley calculations.  If this is meant to be the same rule, but explained from a different angle, then I don't see how to establish equivalence.  If this is meant to be a new system, then I don't see how it generalizes to more complex examples, such as where the factory output scales with the number of workers (rather than being all-or-nothing).  (I also don't see why you'd choose this particular comment to start promoting your alternative system.)

Second, you're analyzing a situation where a required input can be provided by any of multiple parties; that is, if there are 2 owners, you only need 1 owner to agree in order to make the factory run.  But the story problem above was about a situation where you need all of multiple parties; i.e. replace the 1 owner with 1 capitalist + 1 technologist and you need both of them to make the factory run.

If I came to you and said, here's a game with 3 people (1 worker + 1 capitalist + 1 technologist), you need all 3 people working together to produce anything, how do they split the profits?  I suspect you'd say an even 3-way split.  But that implies that the owner from the 2-person can divide himself into 2 dummy agents (1 capitalist + 1 technologist) and then demand 2/3 of the profit (up from 1/2) because he's now (nominally) doing 2 out of 3 jobs.

How do you prevent this exploit?

Third, I don't buy your claim in your advanced examples that "any lesser split has a better alternative that one party can force".  For instance, in the 1 owner + 2 workers example, if the owner offers worker A a 70-30 split, that's better for both the owner and worker A than your proposed split, and I don't see what worker B can do about it.

You seem to be arguing that worker A should reject this split on some sort of timeless logic (?) where A reasons that there was an equal chance the offer would have been made to B and so if A+B are the sort of people who accept this offer then they each get 15 in expectation across all counterfactuals.  Even if you buy the timeless logic, this only works if A and B use correlated strategies such that A is effectively choosing for both of them; otherwise, after A rejects this split, the owner proposes it to B and A gets nothing in all counterfactuals.  So that seems to me like a coordinated solution, not a solution that a single party can unilaterally force.

In fact, it looks to me like you've said something pretty close to "my system rewards monopolies, so A and B are incentivized to form a cartel and act like a single agent, and therefore I assume they do so."

I did a really simply and naive thing in an online calculator, and I'd like to state explicitly that I'll be quite intrigued if you show me I did it wrong as I feel I must have made a mistake looking back over this comment.

I used http://shapleyvalue.com/ with several (ANNOYING TO INPUT) sets of values (10 utility in each).

Here I did a trivial thing where you need all owners and 2 workers here, and included only those people. You can see that they trivially are going to telescope to each getting 1/n of the value out.

1 owner / 2 worker = ( 3.33333 / owner, 3.33333 / worker) 2 owner / 2 worker = ( 2.5 / owner, 2.5 / worker) 3 owner / 2 worker = ( 2 / owner, 2 / worker)

Apologies for the bad example, but I really don't want to enter all those cells again and am going to only do the better computations if I write some code for it later.

Sounds like you set up a model where the factory produces nothing unless it has 100% participation from all players, which means that all players are in equivalent positions (any one of them can veto the entire operation and leave the other players with nothing).  Under this model, "owners" and "workers" are actually equivalent--you've assumed that if 1 worker goes on strike, the entire factory shuts down.

Obviously, if all players are in equivalent positions, then by symmetry they'll have equal payouts.

In the original story-example, the factory owner can claim a higher Shapley value on the basis that if you removed just 1 worker, the factory would still produce quite a bit, but if you removed the owner, you wouldn't have a factory anymore.

A very simple model for this might be something like:  owner + any N workers produces N utility, while any subset not including the owner produces 0 utility.  Then, with 10 workers + 1 owner, if you add people in a random order, each worker produces an average of 0.5 marginal utils (= 0 if added before the owner, 1 if added after) while the owner produces an average of 5 marginal utils (= the average number of workers added before the owner).

If you double the number of workers to 20 (and thus double the max output to 20 as well), then each worker still adds an average of 0.5 marginal utils, but the owner now adds an average of 10 marginal utils.  So the worker wages stay the same, but the owner earns more from the larger operation.

Now suppose we go back to 10 workers, but now we have 2 owners, with the rule that the factory produces 0 unless both owners participate.  (Thus, these 2 owners collectively do the same job that the 1 owner previously did.)

A worker produces 1 marginal value if added after both owners, 0 otherwise.  Since there are 2 owners, on average 1/3 will be added before both, 1/3 between, and 1/3 after both.  So the worker average is 1/3 util.

The first owner added produces 0, the second produces as many as there are workers.  On average 2/3 of workers are added before the second owner, so the second owner produces 6.67 marginal utils.  Each owner is the second owner half the time, so each gets 3.33.

...um.  That is not the result I was expecting.

Can anyone either point out an error in my math, or explain to me philosophically why I ought to be ok with this result?  It seems concerning to me if the factory gets a different share depending on whether it's owned by 1 person or by 2 people.

Yup, I wrote the program and still get owner-value-portion-grabbing. If it's any help, I can now generate any simple pattern you want very quickly and easily.

Only the second owner to join adds any value, so they get the same slice as the sole owner in the first example, ie, half. Since each owner has a 50% chance of being the second owner, they each get 25%. With 3 owners it’s 1/3*.5=1/6. Etc. the math works out very neatly this way.

Only the second owner to join adds any value, so they get the same slice as the sole owner in the first example, ie, half. 

Show your work and/or explain what's wrong with my reasoning above?  I already took that into account, but got a different answer, because there's more permutations where the second owner is added late in the sequence than where the second owner is added early in the sequence.

(Note that if my reasoning from the previous comment is wrong, it has to be wrong about both the owners and the workers, since they need to sum to the correct total.)

You’re right, this was less clear than I intended it to be; my apologies. The proposal I offer here is that since the first owner to join offers nothing, they aren’t included in the calculation; you just run them as though the second owner was the only owner, and get the same result for the value of the second owner as you did for the sole owner the first time. This has the advantage of being very computationally simple and gets you the same results as the full calculation for this case. It’s a specific case of a broader way you can simplify shapely calculations, where when the payout can be calculated by (A1+A2+A3…AN)*(B1+B2+B3…BM)+…+(X1+X2+…XO), you’ll get the same values for combining “Like Terms” (Not exactly the same concept but I don’t remember what the real word was, been a while) and running the shapely calculation for A, B,…X and then dividing the total of A by which fraction of A each A1, A2, etc terms makes up. For more complicated payout amounts it’s a bit more annoying to do this way but you can still do it if you’re careful to set it up properly. This applies even when one of the terms, eg A2, is 0, which then gets us our specific case here. I don’t remember the exact setup for the proof my professor used, but I don’t think it’s neccesary? It feels like one of those things where it’s obvious once you run it through both ways for an example, but if it isn’t lmk and I’ll see about digging through my old notes.

If I understand you, you're saying that this simplified calculation should give the same answer as the full calculation, and that this should be obvious to me after I try it both ways.

But you're also saying that the simplified calculation is equivalent to the earlier problem with only 1 owner, which means I already worked it both ways (one way in the 1-owner problem and the other way in the 2-owner problem) and I got different answers.  So, no, the equivalence is not obvious after running it both ways.

My suspicion is that this half-remembered theorem you are trying to apply actually applies to a different situation and you are using it wrong.  But if you don't think that's the case, then yes, I'd like to see a more precise explanation.  (And ideally, an explanation of what you think I did wrong in my own calcs.)

That would happen too, yes. But that's the thing. How can one say whether this is good or bad - how fair or unfair this state of affairs is?

A transferrable utility game is one where there's a single resource (like dollars) where everyone's utility is linear in that resource

For humans, money does not seem to have linear returns of utility. For what real agents could it?

My expectation for the U of an aligned AGI would be something like, the sum of the desires of humans, which, if the constituent terms have diminishing returns on resources, will also be diminishing. I can see arguments that many probable unaligned AGI might get linear returns on resources... but if humanity is involved in the negotiation (and you really hope we are) then doesn't that still break shapley? I guess you could still potentially use shapley for analyzing the valence of ecosystems of unaligned AGI, which would be useful for comparing risk of unaligned singletons to unaligned multipolar outcomes and to authoritarian lockin, but it's not exciting, and... actually, everything collapses to aligned-somehwhataligned-unaligned multipolar under the Grabby Aliens model.

There does seem to be a value within the human utility function that does scale linearly with resources (a variable that population ethicists and early longtermists love), but it's not clear at all what its relationship with other variables is. Another way of phrasing this objection is, there is a lot of personal low-hanging fruit that a human has to grab before the scalable variable will be all they have left to optimize, and I don't think I've ever heard of a person who gathered "enough" of the low-hanging fruit of the good life, that they started acting in a purely longtermist or stewardly way. EG, Elon will still want his space adventure no matter how many of his friends explain why they think it's not cost-effective for reducing existential risk. Many people tell this story where, once a person is rich enough and "has their needs met", they're supposed to optimize the scalable term and consequently become selfless (the self is finite, even in the extremes, due to the light speed limit, so anything that keeps scaling has to be a kind of selflessness), many people would like that to be true. It's not obviously actually true, it doesn't accord with present human behavior, and I'm not sure how to investigate it.

Great post. Two comments:

That can be folded into the utility function, however. Just make the ratings of the deferential person mostly copy the ratings of their partner.

Can you say more specifically how this is done?

the axiom of Independence of Irrelevant Alternatives....is not really a desiderata at all, it's actually an extremely baffling property.

The reason it's a desideratum is because it makes bargaining more robust to variation in how the game is defined. I agree it's counterintuitive within the context of a given game though. So maybe the best approach is to take it out, but then specify that we should think of games as being defined via some unbiased meta-bargaining-process...

That can be folded into the utility function, however. Just make the ratings of the deferential person mostly copy the ratings of their partner.

 

Presumably the deferential parter could just use a utility function which is a weighted combination of their partner's and their own (selfish) one. For instance, the deferential partner could use a utility function like , where  is the utility function of the partner and  is the utility function of the deferential person accounting only for their weak personal preferences and not their altruism. 

Obviously the weights could depend on the level of altruism, the strength of the partner's preferences, whether they are reporting their true preferences or the preferences such that the outcome will be what they want, etc. But this type of deferential preference can still be described by a utility function.

Loved this post, thanks for writing it.

I believe I've found some typos, but given the mathematical nature of this post, I'm less sure about this than usual. Anyway, here goes:

The best move in the cooperation game is Bob going to the airport, and Alice going to the beach, so that's what's played in real-life. The utility from the cooperation game is added to the maximin utility from the competition game (where beach/beach is played), for 100 Bob utility and 150 Alice utility. And so, the solution is that Alice goes to the beach and pays Bob 50 bucks to go to the airport.

 

Like, if the surplus-maximizing option is one that player 1 values at +80 dollars over the disagreement point, and player 2 values at +40 over the disagreement point, for +120 dollars of surplus value, the CoCo solution is that particular option is picked, and player 1 gives player 2 20 dollars, so both sides walk away with +60 dollars worth of utility.

So if I understand the second example correctly, doesn't that imply that in the first example, Alice should only pay Bob 25 bucks so they both have 125 utility?

Anyways, the value that player i gets is the sum of the values it gets from all of the component games where coalitions compete against each other.

 -> the sum of the values they get from


Finally, there's lots of math about set differences. I believe in all these cases, using / as the symbol for a set difference may be wrong (?) or at least unconventional, and should be \ instead.

[These aren't necessarily in order:]

[The first two LaTeX formulas for Shapley values, following the sentence "then the payoff for player i is"]

S⊆N/{i}

the subset N/(S?{i}),

For the game with S vs N/S

in the coalition N/S

[In the two latex formulas after the sentence "producing a restatement of the Shapley value as", plus once after the sentence "But remember, the Shapley value can be re-expressed as"]

v(N/S)

and v(N/S) is the value of the opposing coalition

Curated! I really enjoyed this post (and its follow-up, though I didn't read that one in as much depth) and wholeheartedly endorse continuing the LessWrong tradition of decision-theory posting. The results of the post feel beautiful (I guess that's a common feeling when different notions are unified) and the explanations are lucid.

I won't claim that the post feels immediately practical in my life, though I suspect I will find myself thinking about bargaining strategies and fairness/chaa in future decision theories, and eventually mulling on the ideas here (and seeking out further bargaining knowledge) until it does have implications for my decisions.

More than that though, reading this post felt "healthy". It feels like the kind of seeking of rigor for "everyday" concepts and decisions that you ought to do. I almost feel like this is hunting for the true name of "fairness". 

To pull out one piece/attitude I liked:

Accordingly, using the term "fair" for any of these mathematical concepts has the problem of automatically importing human concepts of fairness, which needs to be resisted in order to look clearly at what the math is doing. It'll be handy to have a separate word for "a mathematically distinguished point in a game where both parties have an interest in preventing destructive conflicts, that's neutral enough that aliens would probably come up with it" to enforce that mental separation.
 

I'd love to see more posts like this, and would also love to see these notions connected to practical applications. Vanessa Kosoy replies in a comment that a reason some of the results might seem ugly is that we're already assuming "morality", i.e. already having a bargaining solution and we're not starting from square 1. So I'd be interested to see bargaining applied to the situations we already find ourselves in. 

I wonder how often the CoCo point is attained in real life transferable utility bargaining games.

Eg. Do most houses sell for half way between the seller’s walk away price and the buyer’s walk away price? Do most employees earn a wage that is half way between the employee’s walk away wage and the employer’s walk away wage (at least when the employee’s walk away wage is above the legal minimum wage)?

What is:

 

in the max min definition near the end?

aha it's a probabilistic blend over assignments of individual-player action tuples that the team S can take, ie the mixed actions of team S

To put it mildly, this is not really a desiderata at all, it's actually an extremely baffling property.

How can we decide an axiom used to pin down a bargaining solution is intuitive or baffling without first having a goal in mind? Which axioms are sound for the bargaining solution used to pick deals depends on the purpose that led us to want to apply bargaining theory to a problem. If you’re designing a file sharing protocol, you don’t care about bargaining chips. You just want the files to be distributed quickly. Or if you’re designing a standard for network equipment and you want to minimize spectrum congestion or wireless interference, knowing that you can’t trust the owners of the equipment not to be selfish at the expense of other users. You want the solution that works best and if some solution that isn’t the solution that works best becomes unavailable, that doesn’t change the solution you consider best. Independence of irrelevant alternatives is sound for some of the goals we want to apply bargaining theory to.

[-]DagonΩ-232

I really wish you'd included the outside-of-game considerations.  The example of what to eat for dinner is OVERWHELMINGLY about the future relationship between the diners, not about the result itself.  This is true of all real-world bargaining (where you're making commitments and compromises) - you're giving up some immediate value in order to make future interactions way better.

Agreed. The bargaining solution for the entire game can be very different from adding up the bargaining solutions for the subgames. If there's a subgame where Alice cares very much about victory in that subgame (interior decorating choices) and Bob doesn't care much, and another subgame where Bob cares very much about it (food choice) and Alice doesn't care much, then the bargaining solution of the entire relationship game will end up being something like "Alice and Bob get some relative weights on how important their preferences are, and in all the subgames, the weighted sum of their utilities is maximized. Thus, Alice will be given Alice-favoring outcomes in the subgames where she cares the most about winning, and Bob will be given Bob-favoring outcomes in the subgames where he cares the most about winning"

And in particular, since it's a sequential game, Alice can notice if Bob isn't being fair, and enforce the bargaining solution by going "if you're not aiming for something sorta like this, I'll break off the relationship". So, from Bob's point of view, aiming for any outcome that's too Bob-favoring has really low utility since Alice will inevitably catch on. (this is the time-extended version of "give up on achieving any outcome that drives the opponent below their BATNA") Basically, in terms of raw utility, it's still a bargaining game deep down, but once both sides take into account how the other will react, the payoff matrix for the restaurant game (taking the future interactions into account) will look like "it's a really bad idea to aim for an outcome the other party would regard as unfair"

Maybe a side note to not forget outside-of-game considerations? But I'm perfectly fine reading about 4/3 pi r^3 without "don't forget that actually things have densities that are never uniform and probably hard to measure and also gravity differs in different locations and in fact you almost certainly have an ellipsoid or something even more complicated instead", and definitely prefer a world that can present it simply without having to take into account everything in the real world you'd actually have to account for when using the formula in a broader context.

Ok, downvoted for that enough that I should just shut up.  But I learn slowly.  

These aren't outside considerations.  Future interactions (or, I guess, highly-suspicious superrational shared-causality) are the primary driver for any non-Nash outcome.  Use of these examples is more misleading than the canonical frictionless uniform spherical elephant, and even for that, every book or professor is VERY clear about the limitations of the simple equation.

I'm a huge fan of the research and exploration of this kind of game theory.  But without really understanding the VERY limiting assumptions behind it, it's going to be very misleading.

A better example might be literally paying for something while in a marketplace you're not going to visit again. You don't have much cash, you do have barter items. Barter what you've got, compensate for the difference. Cooperative is "yes a trade is good", competitive is "but where on the possibility list of acceptable barters will we land"?

I guess the difficulty is that the example really does want to say "all games can be decomposed like this if they're denominated, not just games that sound kind of like cash", but any game without significant reputational/relationship effects is gonna sound kind of like cash.

I now agree with you. Or possibly with a steelmanned you, who can say. ;)

This is why I was stressing that "chaa" and "fair" are very different concepts, and that this equilibrium notion is very much based on threats. They just need to be asymmetric threats that the opponent can't defuse in order to work (or ways of asymmetrically benefiting yourself that your opponent can't ruin, that'll work just as well).

(from the next post in this sequence https://www.lesswrong.com/posts/RZNmNwc9SxdKayeQh/unifying-bargaining-notions-2-2)

and

in physical reality, payoffs outside of negotiations can depend very much on the players' behavior inside the negotiations, and thus is not a constant.  Nash himself wrote about this limitation (Nash, 1953) just three years after originally proposing the Nash bargaining solution.  For instance, if someone makes an unacceptable threat against you during a business negotiation

(from Critch's first boundary post https://www.lesswrong.com/posts/8oMF8Lv5jiGaQSFvo/boundaries-part-1-a-key-missing-concept-from-utility-theory)

I'm not really concerned about saying "but reputation matters; the solution you land on here affects your reputation later" since that should be baked into the payoffs.

But I do think it's important to note the assumption that what happens during negotiation can affect the payoffs even of the current game which this analysis otherwise treats as constant.

The utility from the cooperation game is added to the maximin utility from the competition game (where beach/beach is played), for 100 Bob utility and 150 Alice utility.

I've reread this part and still don't understand why beach/beach is played in the competition game. How was that determined?

It is because beach/beach is the surplus-maximizing result. Any Pareto-optimal bargaining solution where money is involved will involve the surplus-maximizing result being played, and a side payment occuring.

This post is super useful, thankyou for writing it!

One thing I'm unclear on: does the transferrable utility assumption require that utility be linear with respect to money (or money-analogue)? It seems like we need that in order to split the game into a sum of two games in the CoCo derivation, but it makes the argument a lot weaker once we introduce uncertainty.

Yeah, "transferrable utility games" are those where there is a resource, and the utilities of all players are linear in that resource (in order to redenominate everyone's utilities as being denominated in that resource modulo a shift factor). I believe the post mentioned this.

Thanks for signal-boosting the coco solution!  I'm actually planning workshop near CMU this fall with Adam Kalai :)