Provably Fair: Splitting Taxi Fares

Consider this. The night's getting late and the metro lines are quiet. Everyone's still having a good time, but you live far away and you need to get back as soon as you can. You glance at your friend, who you know is in the same shoes as you. Without breaking the vibe, you suggest taking a cab together. Your friend agrees. At the end of the long cab ride, you wonder how the fare should be split. After all, you live further away from the original destination. It doesn't feel fair to split it 50-50. Maybe you should pay more?

A Fair Fare

Alright, I think most of us in this situation won't overthink this. But maybe you might start thinking more about it when you realize that there IS a provably fair way of splitting the fare. Here's how:

1. Find out how much it would cost for you to take a cab by yourself and ask your friend to do the same. Let these values be A and B respectively.
2. Find out how much it would cost for you and your friend to take the cab together. Let this be T.
3. The price you pay should be 0.5(A) + 0.5(T-B) and the price your friend pays should be 0.5(B) + 0.5(T-A).

So, for example, if A is 20, B is 32, and C is 40, then you should pay 14 and your friend should play 26. Maybe you might have noticed that this is the same as splitting the total "benefit" of cabbing together (T-A-B) evenly among you and your friend (and is probably an easier way of deriving it). This is intuitively fair, but is it really fair?

The Shapley Value

Yes. Let me introduce you to the Shapley value, a game-theoretic value that is the only value in a cooperative game (i.e., a game where different players collaborate) that fulfills the following characteristics:

• efficiency (the sum of all Shapley values is the overall cost/benefit)
• symmetry (players that behave the same are treated the same)
• dummy (players that contribute nothing get nothing)
• linearity (if the cooperative game is linearly scaled or translated, the values will be altered in the same way)

What does all of that mean? It means that this value is fair in a game-theoretic sense. Here's how you can calculate it: think of the game as the various permutations of all the players. Each player brings a certain cost/benefit to the coalition of players thus far (including them). Taking the average of all the different costs/benefits a player provides in each permutation gives us the Shapley value.

In the case of the above example, A is what you pay when you're the first person in the coalition of just you. When you come second in the permutation, you add the cost T-B to the coalition consisting of you and your friend, since your friend already pays B since they're before you in the coalition. These two are the only two permutations (2! = 2), and when we take the average of these two, we get 0.5(A) + 0.5(T-B).

To summarize, the Shapley value of a player is the mean of the marginal contributions of that player in every possible permutation.

What about 3 players sharing a cab?

Here, the Shapley value isn't simply evenly distributing the benefit of cabbing together to the three players, because you need to consider two-player coalitions as well. The resulting math is a lot more complicated, and requires finding out the cab fees for each of the three two-player coalitions as well, so maybe this one can be given a pass unless your friends care about game theory as much as you do.

Maybe I should make a simple website to do the calculations for you. 🤔

Algorithmic Mechanism Design

The Shapley value is an idea found in game theory, and specifically it's a part of algorithmic mechanism design, which is a lovely intersection between Computer Science and Economics that involves designing mechanisms to fulfill social or economic goals. For example, when designing a mechanism, it's important for the result to be fair (as in the Shapley value), but it's also important for the result to be economically viable.

For example, maybe, in the three-player case, two players might be better off just cabbing together than if they were to join the three-player coalition, and in this case, the Shapley value is fair but also meaningless, as the two players are incentivized to deviate from the coalition. The payment vector such that all possible subsets of players are not incentivized to deviate is called the core, and the vector of Shapley values might not necessarily be in the core.

Within algorithmic mechanism design, there are other considerations as well, such as envy-freeness, utility maximization, ensuring that players are truthful about their preferences etc. Other problems that can be solved with algorithmic mechanism design involve problems such as allocating divisible goods, matching people together, and splitting rent. Interestingly, it brings a formal, mathematical approach to nebulous issues such as fairness and truthfulness, and that's the kind of stuff I'm a huge fan of.

So okay, now you know how to split taxi fares evenly. For the sake of your social life, please don't try this with more than one other person (who is ideally a good friend). This is my first post going into something more technical that isn't related to software directly, but it's also so interesting that I can't help but share it. Hope you all enjoy this tidbit of knowledge!

A shoutout to CS5461 Algorithmic Mechanism Design, a module I'm taking this semester that I think is pretty cool.

That's all for now. See ya!