We begin this session with a classic three-way negotiation problem. Which dates back to a 1973 article, by SC Littlechild and G Owen. Here's the set up. Three airlines are planning to build a shared runway. Airline A uses single engine planes, and only needs a runway of length one. Airline B requires a runway twice as long for its regional jets. Airline C employs commercial jets, like Boeing 747s, and needs a runway of lane 3. The shared runway will need to be three units long to accommodate all the airlines. How should the airlines split the building costs? Let's assume, if there were no partners available, each airline would be willing to pay the full cost of a runway long enough for its planes. We're also going to assume that the cost of building a runway increases linearly with it's length. In reality, large planes require runways that aren't just longer but wider and capable of bearing a lot more weight. To keep the math simple, we'll call the cost of building one unit stretch of runway $100. Though actually runways cost much more in the order of a million to a billion dollars. Now, how should the three parties divide up the cost? Littlechild and Owen propose the following solution. Each airline should split the cost equally for the portion of the runway it uses. Thus, airlines A, B, and C divide the cost of the first leg three ways. B and C split the cost of the second leg, and C pays the full cost of the third leg. That means airline A pays 33 and a third. Airline B pays 33 and a third plus 50, which is 83 and a third. And airline C pays 33 and a third, plus 50, plus 100, which is 183 and a third. I think this is a completely reasonable solution. There's another solution that makes sense which we'll discuss in a later session. For now, I want to explore how the principles behind this solution apply when the problem isn't so straightforward. One feature of the runway problem that makes the solution straightforward is that the runway is a straight line. The needs of the airlines perfectly overlap each other. What happens when needs aren't so perfectly aligned? Consider a situation where three friends are looking to share a taxi. Alice's home is almost an the way to Bob's, but Carroll's place is a bit out of the way. Each leg costs $6. The total cost of the trip is $18. If we simply applied the runway solution, we'd have Alice pays $2. That's a three way split of the first leg. Bob pays $2 plus $3, which is five, as Bob and Carroll split the second leg in half. And Carroll pays two plus three plus six, which is 11, as Carroll pays the full cost of the last leg. This strikes me as a great deal for Alice, and not such a great deal for Carroll. Carroll's being asked to pay his equal share of the first two legs, even though they aren't directly on his way home, and in fact, make his trip longer. So, what is fair? Let's go back to simpler case where we only have Alice and Bob to worry about. How should Alice and Bob split the cab fair? According to our basic framework, we need to determine what the pie is. We know how much their fair is together. That's $12. And how much Alice would spend on a taxi alone. That's six. But we still need to know, how much would it cost Bob to take a taxi directly home? Let's say it'd be $11. In that case, if they took separate taxis, the total cost would be 17. But, by sharing a taxi, the total cost is only 12, thus the pie is $5. Note, I'm ignoring that Bob will be slightly delayed in taking this route. That delay cost would make the pie slightly smaller. But we're not gonna factor it in here for Bob, or later when it comes up for Carroll. Since the pie is $5, if they split the savings, then Alice will pay $6 minus $2.50. Which is $3.50. And Bob will pay $11 minus $2.50. Which is $8.50. There's another way of seeing this fare split. Alice and Bob evenly split the cost to getting to Alice's place, which is $3 each. They could stop there, leaving Bob to pay the next $6 on his own. However, the detour to Alice's place created an extra dollar of cost. As a total taxi fare to Bob's is $12, rather than the 11 his direct trip home would have cost. Alice should split the cost of the detour with Bob. Thus Alice pays $3 to get home, plus $0.50 for the detour, for a total of $3.50, bringing Bob's share down to $8.50. And this is the exact same solution we got, splitting the pie. So, now what do we do? We bring Carroll back into the picture. The first step should be clear. We want to understand the pie. We need to know how much it would cost if each person made the trip on his own. In separate taxis, Alice would spend $6, Bob would spend $11, and let's say Carroll would spend $15. The total cost would be six plus 11 plus 15 or 32. By sharing the ride, their total cost is reduced to 6 plus 6 plus 6 or 18, so there's a $14 savings. Okay. Now we know the pie is $14. How should we split that up between Alice, Bob, and Carroll? Again, I'm ignoring the extra time Bob and Carroll spend in the taxi and the associated delay cost. A simple approach is just to split the pie evenly among the three of them. Each would save 14 over 3, or $4.67. I think that's simple, but simply wrong. In this case, Alice would save 4.67, so he would only pay $1.33. Which is less than $2. But I think Alice should be paying something more than $2. $2, what Alice owes, if the three of them split the first leg of the trip evenly. Alice, note, owes more than that because his house isn't entirely on the way to the other two. Thus, Alice should be partially responsible for the detour. But how much so? One clever solution comes from Lloyd Shapley, who won the 2012 Nobel Memorial Prize in Economics. Imagine the three riders approach the taxi in a random order. That means it's equally likely that Alice gets in first, followed by Bob and Carroll, as it is that Bob gets in first, followed by Carroll then Alice. In Shapley's solution, each person who joins the group is given all of the pie that comes from his joining the party. Let's illustrate this idea by going back to the case with just Alice and Bob. There are two possible orders. Alice then Bob, or Bob then Alice. Under the A B ordering, Alice pays the full $6 fare to get to his place, and Bob pays the incremental fare to his house, $6. Under the BA ordering, Bob pays the full $11 fare to get to home, and Alice only has to pay $1. Since the total cost is $12. If you like, you can think of this case as when Bob was prepared to pay $11 and is happy to let Alice reap all the gains. And while this seems unfair to Bob, remember, that under the AB ordering Bob gets all the savings. Since both orders are equally likely, we can say that Alice pays a half of six plus one which is $3.50 and Bob pays a half of six plus 11 which is $8.50. These are the very same numbers we saw when dividing the pie, and that's no accident. All we're doing is giving the whole pie to each of the two parties with a 50% chance by taking the average, we end up in the same place. Now, we're finally ready to apply this logic to the three person case. If the order they get in the cab is ABC, then Alice, Bob, and Carroll each pay $6. But what if they get in the order, ACB? Alice still pays $6. As for Carroll, the chart is missing how much it would cost to go from Alice's place directly to Carroll's. Say that cost is 11. So then Carroll pays 11, the cost of getting from Alice to Carroll's. How much does Bob pay? The total cab fare is 18, and Alice and Carroll are already paying 17. So Bob gets off easy, paying just $1. There's a key insight here. Even though the order they get in is ACB, the taxi driver isn't gonna drop them off in that order. Let me say that again. Even though the order they get in is ACB, the taxi driver isn't gonna drop them off in that order. It costs $5 more to drop off Bob after Carroll. ABC is the cheapest route to deliver all three of them home. Bob joining Alice and Carroll's cab simply means a stop midway. Let's do one more example. Say the order is CBA. Since Carroll gets into the cab first, he pays $15, what he would have paid on his own. Next, Bob joins in. The cheapest way to get Bob and Carroll home is to first stop at Bob's and then proceed to Carroll's house. That costs 11 plus six, or 17. Since Carroll has already contributed $15, that leaves only $2 for Bob to pay. Next Alice joins the group. Now the best root to go is ABC, which is a total cost of $18. Since Carroll and Bob have contributed 17, that leave just $1 for Alice to cover. You might think this case is unfair to Carroll. And it is. But there other orders in which Carroll does very well. Such as, when he gets in last. The solution Shapley came up with, called the Shapley Value in his honor, makes things fair by averaging across all possible orders. We need to calculate how much each person pays in each of the six possible orders. There's ABC, ACB, BAC, BCA, CAB, and CBA. Remember, the cab ride always goes to Alice's first, Bob's next and Carrol's last, even when that isn't the order they get into the cab. Thus, under BAC, Bob goes first and pays 11. Then Alice joins and pays 1. And Carol comes in last and pays the remaining $6. I put this all together in a table. In the table, I start with a payment by the person getting in first, who pays his full fare. Next, the person getting in second chips in the rest of what's needed to get the two of them home as cheaply as possible. And the person getting in last covers the rest of the $18 fare that gets all three of them home. If we average across all six orderings, then Alice pays 17 over six, or $2.83. Bob pays 32 over 6 or $5.33, and Carroll pays 59 over 6 or $9.83. When you add up all three payments, they come to $18. Just the same as the total cab fare. If we think of things in terms of the pie, and that's the way I like to do it, Alice saves three and a sixth, Bob saves five and two thirds, and Carroll saves five and a sixth. The sum of the savings is 84 over six, which is $14, the same as the pie. Note that Bob saves more than Alice or Carroll. That's because adding Bob to the cab is what creates the most pie. Alice and Bob can create a pie of size five together. They spend six and six, which is 12, which is $5 better than what they would spend on two cabs. Alice and Carroll can create a pie of size four together. They would spent six and 11 or 17 which is four then what they would spend on two cabs. Bob and Carroll can create a pie of size nine together. They would spend 11 and six or 17, which is nine better than what they would spend on two cabs. Thus, when it comes to pairs Bob can create $5 and $9 of pie, which is more than either of the other two. Both Alice and Carroll would pick Bob if it were just going to be two people sharing a cab. Bob is also the most valuable person when it comes to joining a pair. Adding Bob to the Alice and Carroll cab only costs an extra dollar. Which is $10 less than what Bob would have to pay on his own. Thus, adding Bob to Alice and Carroll creates $10 of pie. This makes sense, as Bob is barely out of the way in terms of Alice and Carroll's cab ride. In contrast, adding Carroll to Alice and Bob's taxi costs an extra six and saves 15, so adds $9 to the pie. And adding Alice to Bob and Carroll's taxi saves only $5. Thus, the reason why Bob gets more of the pie is because he brings more to the mix than either Alice or Carroll. When there are only two people in the negotiation, you need both to reach an agreement, and that's why I argue they should be treated equally and divide the pie 50-50. Once there are three or more people involved however, then no agreement doesn't mean each person must go his or her own way. They might reach a two person deal. And because those two person deals have different levels of attraction and even three way split of the pie is no longer fair. To find something fair, we can look to the Shapley Value. The Shapley V alue has much to recommended it. As I mentioned earlier, it gives each person who joins the group all of the pie created when that person joins. And we make things fair by having people join in a random order. But there's another remarkable feature of the Shapley Value. It is the only solution that obeys the following four properties. One, there's no money left on the table. In other words, if the total pie is $14 and that $14 is split up among the participants, nothing is thrown away or wasted. Two. Who gets what does not depend on people's names. If Carroll moves into Alice's home and Alice moves into Carroll's home, then the two of them also switch what they pay. A person's name is irrelevant in determining how much one should pay. All that matters is the pie one creates. Three. If someone can never save anybody else money, then that player doesn't get to share in any of the savings. In other words, say Daryl lives in the opposite direction from Alice, Bob, and Carol. There's no money to be saved by including Daryl in the taxi ride. In that case, Daryl pays her own fare. Four. If there are two cost-sharing problems and we combine them, the solution to the combined problem is equal to the sum of the solutions to the separate problems. This last property is a bit hard to understand. But it means that if we add $1 to every group that A is in, including just A, then A will end up with an extra dollar in the final result. It is really the only controversial requirement. When we return to talk about the other solution to the runway problem, we'll see how this property doesn't hold. For now, here's what we've done. We started out with a straightforward runway problem. While the answer seemed quite natural, it wasn't obvious what to do when the needs didn't line up so perfectly. That brought us back to think about the pie. With just two people we can divide the pie 50-50. But with three or more people, it doesn't make sense to divide the pie evenly, as what they contribute to the pie isn't always equal. The Shapley Value isn't the only solution, but it's a pretty good one. It is both simple to use and fair.
