Without all the game theory stuff my initial gut reaction would be: for each segment of the trip you were in, you should pay the cost of that segment divided by the number of the people in the car during the segment. So: - the first person to get out pays 1/3 of the first segment - the second pays 1/3 of the first trip + 1/2 of the second segment - the third pays 1/3 of the first, 1/2 of the second and the full third segment. So: 2, 5 and 23, respectively.
The "alternate perspective" follows exactly from symmetry and linearity axioms - they are essentially playing 3 consecutive games on 3 disjoint segments with 3, 2 and 1 equivalent players respectively.
Without efficiency you couldn’t conclude that it hasn’t add to the total. E.g. perhaps they should all pay $3 for the first journey. It’s obviously stupid but without the axiom of efficiency we can’t rule it out.
And you need the null player axiom! The second and third games technically have all three players, but a subset of the players are null because they do not contribute to the cost for that game.
My first thought is to think in terms of man-miles. Each person would pay a percent of their "alone" cost equal to (farthest distance) / sum(man*miles) In this case, 30 / (6+12+30) = 30/48 = 0.625. Each person pays this fraction of what they would have paid on their own. So Nash pays $3.75 miles, Shapley pays $7.5 miles, and Bazett pays $18.75 miles. Everybody gets the same discount rate. Besides being much easier to calculate, this approach also encourages Nash and Shapley to include you, because without your 30 mile trip, the discount rate they could achieve with just the 2 of them would be 0.66... and their total amounts would be $4 and $8. If you think of it like that, then each person has a negative cost function. This seems much more fair than arguing about how much a person is costing the others by adding miles. The method shown in the video provides the most benefit for the least needy. There's also a societal cost - the person who has to travel the farthest benefits the least. If it 's not a great saving, they are likely to hire their own cab, creating more traffic and burning more fuel overall. You say there's no other way to do it fairly, but how does the man-miles approach violate any axioms of fairness? The trick is figuring out the total distance before the first person leaves the cab. Oh, and also a little thing called the traveling salesman problem. We will leave that as an exercise for the reader. XD
Arguably, the “fairest” approach that also promotes cooperation is to take the average (mean) of the Shapley value and the method you describe. In this scenario, Nash would pay $2.875, Shapley $6.25, and Bazett $20.875. Handle the rounding as you wish. Of course, the example is somewhat over simplified in that the taxi meter probably started at ~$2, so that portion should be shared equally and only the $28 in time/mileage should be divided using another method. In this case, that makes little difference.
I believe linearity is what breaks down. Specifically, the guy who lives closest is motivated to split the journey in two - first to his house, getting a 1/N price there, and then leave the others to sort out their own trip from there on.
I came to the same solution. I didn't think of it as "man-miles" (a la 'the mythical man-month') but a value proposition. The three are sharing a value pool that sums to $48, for a cost of $30. Each should contribute to the cost proportionally to the value they extract from it. Boiled down, they each discount their fares by -- in this case -- 37.5%, and they each get a larger total discount according to the relative length of their rides.
(Written at 2:50) Look at the ride as three separate rides: The first $6 should be split among all three, then N. leaves and the next $6 should be split between S. and B., and the last remaining $18 are for Dr. B. himself to pay alone.
In a more realistic scenario, homes won't be located on a neat straight line. Going from A to B won't take you exactly half way from A to C. In some cases going from B to C might take longer than going straight from A to C.
@@Bolpat The problem with the example is that taxis travel in two dimensions. If the path from start to A is 3 miles north, and from A to B is 4 miles east, then B has to travel 7 miles when they could have gone straight home in 5 miles. It's unfair to make B pay for those extra 2 miles.
Because it’s improbable that the 3 destinations lie exactly upon the same lowest cost/time/distance route from the origin, there is an additional consideration each participant should invoke. What is their cost solo, or in any subset of participants vs their cost for the full set. It might be less costly to break problem into two or more separate coalitions taking different routes, and compute the Shapley value for each subset, and each participant can then choose their lowest individual cost. However, the lowest cost for a given participant doesn’t guarantee the lowest cost for all participants (nor the lowest combined cost). Participants can negotiate (or again calculate something like the Shapley value) using the best options for each participant to minimize total costs and individual costs. But since total cost is no longer fixed, you can’t be guaranteed to meet all 4 of the specified criteria.
I don't see how being on the same route makes a difference. The formula still works, I think, and everyone's payment is still lower than outside of the coalition. Now, in practice it's impossible to talk about this topic without talking about value the people are getting out of the coalition, which is very subjective and that throws the wrench into the fairness theorem (I think).
@@levbobrov1398imagine player 1 has to go $6 on the meter on the opposite direction from player 2, then the total bill will be $24 (6 to get to player 1 destination, 6 to backtrack, and 12 more to get to player 2 destination) and there's clearly no benefit for player 2 to ally with such a player 1, this is an extreme example, but route efficiency and deviations will impact the problem the maths in the video will work better on cases that the cost of adding a person doesn't make the trip that much more expensive (as in my extreme example) that not having them join would've been much better
@levbobrov1398 An example of the above is, if S & B live North of the starting point but N lives south then the formula still works to fairly split that route, but that's a stupid route and it'd be better to split 2 taxis
I would do it simply like this: the bill is $30 the total "distance cost" is 48 = (6 + 12 + 30) each person pays their proportion of the total "distance cost", so first person pays 6/48 * 30 = 3.75, second pays 12/48 * 30 = 7.5, third pays 30/48 * 30 = 18.75 Pays the whole bill and seems pretty fair to me. Everybody pays the same (lower) rate for their distance. (62.5% of the normal rate, to be exact)
This was my initial thought, too. The "fairness" in this solution is that everyone gets the same discount. It works alright in the case of the taxi since everyone is going to a fixed location, but it falls apart when you look at a more geneal idea of contributing to a shared resource. Say the first two people use the resource and plan share it responsibly (in the taxi, a $6 and $12 fare for driving home). A third person can show up and gain an inordinate amount by exploiting the resouce (a $1k fare for a road trip). With this distribution, the first two responsible parties end up paying almost full price while the third party gets almost a $18 discount. Decidedly unfair. The simplest way to phrase the "fairness rule" that indicates this is an unfair system is that "the addition of a new party should never increase the amount existing parties pay."
This was my first thought as well. However, this doesn't reflect that different travellers are sharing different proportions of their journey with different numbers of people, so arguably some are due a bigger discount than others.
@@subrabalanmurugesan7159 Maybe there is a linearity violation when you actually try to write out the formula? everything else seems like it should hold
I wonder how the total price changing would be affect this. An extreme example would be to imagine Nash's house is actually $6 in the wrong direction (so $12 to return to the starting point). I hope it's clear to see that Nash ought to pay the full $12, since it gets the other two literally nowhere. Of course, Nash would be better off getting a separate taxi so he probably would
I think "would be better off getting a separate taxi" is the best way to look at this, actually. You could make an axiom of something like "adding someone to the taxi can never increase the cost for anyone already in the taxi", because an additional person won't be invited into the group if it'd make it more expensive for the people already *in* the taxi agreement. (I think this is the Linearity axiom, really. The Null one too, maybe -- assume there's someone in the taxi already who wants to go nowhere and thus will only pay $0. Anything that makes that person pay anything would also violate the "new person made existing person pay more" axiom.)
My first thought was to split the bill for each "segment" between whoever is still on the taxi (like you did later on). Indeed I got the same result, no formula needed. The only downside is it does not generalize equally well.
The alternative perspective is intuitive and it would be neat to show that it is the same as the full explanation, which seems completely out of the blue at first. It's also very easy to actually use this method in practice (assuming everyone has change/venmo): at each stop, divide the fare shown on the meter, minus the contributions of anyone who has already been dropped off, equally among the passengers to determine the amount the person being dropped off should pay.
It's definitely possible to rearrange the shapley value in terms of "synergies" formally, actually there are a couple ways to write it beyond the marginal contribution way I defined it.
A quick way to see how this is related is the Linearity property. Namely you can divide the original trip into three subtrips, one that costs $6 with three players, one that costs $6 with two players, and one that costs $18 with one player. Clearly if you use the main method from the video at each step you get all three people paying $2, the remaining two person paying $3, and the last remaining person paying $18, and so by the linearity property the final solution for each person is the sum of those three subsolutions for that person.
@@Bodyknock I think Linearity is by far the most load-bearing one here, so it's a shame it was skipped over. I'm sure there's a complicated reason that Null is needed too, but in a sense Linearity intuitively covers that too: someone who wants to stay where they are for $0 can address that by splitting the trip into the "stay here" trip for $0 and the "go somewhere" trip for non-zero with everyone else.
Why not just have everyone divvy up the cost for the ride that they share? So the first six dollars gets split into three, the second split into two, and the remaning 18 all lies on the last guy. It gives you the same exact result. Edit: always watch until the end before commenting lol, it's in the video
To me, another fair way of splitting up the cost is to make each person save the same % of their travel cost. You do this by finding the ratios of the different distances. A short formula is to divide your distance by the total of all distances together. This gives 6/(6+12+30)=1/8=~$4 for the first one, 1/4 =~$7 for the second, and 5/8=~$19 for the third. (30/8 is not an integer, so some rounding has to be done.) I am not sure what axioms this goes against, but it seems fair to me. (It certainly follows the 1st and 3rd axiom. I did not understand the 2nd and 4th axioms well enough to know which one it doesn't follow, but I don't necessarily agree with them either.) What is wrong with this approach?
This was my approach too, but It's definitely not the best. Guys with $10 and $10 would pay $5 if they were to travel with each other, but if a guy with $25 cost wanted to fit in, the costs would change to 5.55, 5.55 and 13.89. Why would the first 2 guys include the third in this situation?
@@misikaro Thank you for the example. I wondered what could be wrong with my approach and now I know. It looks like the only way things go wrong is if multiple people are carpooling together and one more person with a longer distance wants to join.
My first thought was that each person should pay in proportion to the "utility" they receive from the ride. Nash receives a $6 value from the ride, Shapley receives a $12 value and Bazett receives a $30 value so there is $48 dollars worth of utility received overall if you double count the bits that overlap. Apportioning cost then gets us Nash = (6/48)*$30 = $3.75, Shapley = (12/48)*$30 = $7.50, and Bazzet = (30/48)*$30 = $18.75. I wonder which axiom this method violates.
The problem is that the dollar value does not necessarily line up with the utility. For instance, the meter only read $30 dollars for Bazett because the taxi had made stops for Nash and Shapley along the way. For all we know, the taxi drove east to drop off Nash and Shapley, then had to turn around and go back west and go out past the original starting point to reach Bazett's place. So now you would be expecting Bazett to not only pay the most money, but also spend the greatest amount of time stuck in a taxi when he's not even necessarily the guy with the most distant house.
It violates Linearity. The easiest way to see why it's a bad solution is to add an extreme value: a 4th person, J for Jerk, whose fare is $1000000. Using the approach in the video, you get N=6/4=1.5, S=6/4+6/3=3.5, B=6/4+6/3+18/2=12.5, and J=6/4+6/3+18/2+999970=999982.5. That's great! The existing passengers all saved some money by letting J join, and so did J over travelling alone. If instead you give everyone the same percentage savings on the journey -- it's about a 0.05% discount -- then you get N≈5.9997, S≈11.9994, B≈29.999, J≈999952. And now J has somehow saved more money than the entire price for N+S+B to get home! All those numbers are higher than the ones you calculated for N+S+B taking a cab without J, so there's no game theoretical reason for N+S+B to let J get in the cab at all, and thus it's not a good solution. So I think a reasonable way to think about (a consequence of) Linearity is that with a good solution, adding someone else to the taxi shouldn't ever make it worse for the people already in the taxi, because if it did then they wouldn't let the person in the taxi.
@@pfeilspitze Actually, the method suggested in this comment would lead to N=6*1000/1048=5.72, S=11.45, B=28.63, J=954.20, which sounds a bit more reasonable than your numbers. However, it's still true that all except J now pay more than they would have (according to the same method) if they hadn't let J into the taxi. My first idea would also have been to use this method, but your example serves as a clear counter-argument.
@@elevenelven5388 I think you ran the numbers for a thousand instead of a million? But I'm glad it still works as a counterexample with the smaller number -- I just picked a big one to emphasize the silliness.
I'd think the fairest way would be for each to receive the same discount relative to what they would have paid if going alone. That looks to be ~62.5%, i.e. $3.75, $7.50, and $18.75. So they all get about a 1/3 discount for working together and no one gets a greater advantage.
I had the same reasoning and same numbers than you. From a mathematical point of view, the proposed solution might be better (2 5 23). In real life, I prefer yours. Everyone is benefitting from it anyway, and the person leaving further have to pay more regularly, and sometimes also are the person who can't live near, because housing is more expensive there.
@@barte4215well no, every dollar they would have spent is instead $0.625, yellow saves more money only because hes traveling further they all get a 37.5% "discount"
I thought the same at first, but from a game theory perspective, the presented solution makes more sense. If we suppose the 3rd person lives $60 away (instead of 30$) this becomes apparent. With %-discount cost-division, the closer two people both pay less if they exclude the 3rd person. For example the closest person pays 6/78*$60= $4.61 with three, but only 6/18*$12= $4 with two in the taxi. This is double for the 2nd person. According to game theory persons 1 and 2 would now take a taxi without the the 3rd person who is now even worse off. Therefore, the 3rd person should pay more. That said, not looking at it mathematically, I like the %-discount method better.
Last part of the trip (18$) is fully imputable to person 3, hence he pays 18$ for that part. The second part of the trip (6$) is the responsability of persons 2 and 3, hence they split the bill and each pays 3$ for this part. Finally, the first part (6$) is evenly shared between the three persons, so they each pay 2$. In total, person 1 pays 2$, person 2 pays 5$ and person 3 pays 23$.
That's $18, $3, $6, $2, $2, $5, and $23, *as shown in the video* . The dollar sign goes to the left of the numbers. I don't understand the tendency to write it wrong in YT comments, when you'll have never seen it written that way in life.
@@JohnDlugosz Not all currencies are written like that, and using the dollar sign makes no intuitive sense (as linguistically you say "X dollars", not "dollars X"), even if that is the default. I don't understand the need to "correct" someone like that.
@@JohnDlugosz In French-speaking Canada, the dollar sign goes after the number, the internet tells me. In Europe it is also quite normal. And in Cape Verde they put it at the position of the decimal point, apparently. Mere convention. Never say never.
@@JohnDlugoszI dont understand the ignorance of americans im the youtube comment field. The world is bigger than the USA and even just a bit north of you is a country writing the dollar after the number.
The initial idea I had coincided with the first proposal. However, I later considered an alternative method: First, calculate the total cost if each person were to go alone, which adds up to 6 + 12 + 30. Then, divide each individual's solo cost by this total amount. For example, N's share is 6/48, S's is 12/48, and B's is 30/48. These proportions are then applied to the shared cost. Consequently, N would pay 30 * (6/48) = 3.75, resulting in a saving of 2.25. Similarly, S pays 30 * (12/48) = 7.5, saving 4.5, and B pays 18.75, saving 11.25. In terms of relative savings, each person saves 37.5% of their original cost. This approach ensures that everyone saves an equal percentage, which seems the most equitable to me.
The "alternative perspective" is the first thing that came to my mind when the question was posed at the beginning of the video and I think it's an approach many many times more natural, simple and easy to understand than that thing about the average marginal costs of every imaginable reality. I don't get why anyone would choose that approach over the more logical one.
I think you meant "over the more intuitive one". Both approaches are logical. I'm not entirely sure, but I think the game theory approach is more general. It might be a little silly for this example, but this example is an easy way to explain it so you can then use the same approach on more complicated problems. That's been my experience whenever "oh, why didn't you just do it the easy way?" has come up in a math class.
The intuitive approach would get a lot more complicated if, for example, the taxi ride for the third person (without detours) costs 20 dollars. He would have no incentive to share the ride at 23 dollars, so the fair share has to change, despite the shared ride still being the same 30 dollars.
1. Assumption: The taxi drivers route taken already is the optimum route for every single passenger. First stretch: 1/3 the cost -> 2 dollars each (3 people) Second stretch 1/2 the cost-> 3 dollars each (2 people) Third stretch 1/1 the cost -> 18 dollars (1 person) N 2 dollars - S 5 dollars - B 23 dollars
An economics related video ! As an economics enthusiast I'm really grateful Unless I'm mistaking, Jhon Nash didn't really invent Game Theory, but hugely contributed to it, the actual creator is Von Neumann, who has also contributed to linear programming and the Von Neuman architecture in computer science.
personally think von neumann is the most underated scholar of the last century in popular terms. if you think about it, CS has been around only in "theory" less than 100 years, let alone real practice. so, he was like others (Shannon, say, who is much more widely touted popularly) literally making this s**t up as he went along. and boy did they get in right, not just in practice, but the theory. it must have been exhilirating. so much of the stuff he came up with has been re-discovered as useful, because it dated so fast. reliability was such an issue early on in circuits (valves and stuff),but quickly less so. he realised that rather than just having lots of "copies" of the same circuit element and just taking the most popular result, you could reduce errors WITH circuit design (which is different from error correcting codes [Shannon-style]). the idea of Expanders is now formalised used in many applications. see, "PMSP - Expander graphs: Applications and combinatorial constructions I - Avi Wigderson" on the IAS channel here (specifically 34mins in).
*Has to pause at **4:00** because the simple obvious answer was being ignored.* Their distances traveled: 6, 12, 30. The total of what they got from the taxi: 6+12+30 = 48. Nash got 6/48, Sharpley got 12/48, Gazety got 30/48. Apparently this cab costs 1/ km. So it costs 30 total. Nash pays 30 × 6/48 = 3.75 Shapley pays 30 × 12/48 = 7.50 Bazette pays 30 × 30/75 = 18.75 100% fair. Each pays 0.625/ km for the cab.
I use this: each * ( total / sum(each) ) so: 30 / (30 + 12 + 6) = 0.625 then, 6 * 0.625 = 3.75 12 * 0.625 = 7.5 30 * 0.625 = 18.75 if you add them, it is - total of 30, and everyone payed less but proportional to what they would have payed if they were alone.
My first thought was also the exact thing you described in the "alternate perspective". On second thought I had this alternative: Everybody pays the full price, but the surplus money is divided equally between the people. In this example: $6+$12+$30=$48, which is $18 too much. The $18 gets divided by 3, so each person gets a discount of $6. Resulting in the prices of $0, $6 and $24. I don't see which of the proposed fairness axioms is broken (except if there is another one not mentioned: "C must be > 0 for everyone involved" - because it seems unfair if suddenly one friend decides to share the ride for exactly 0 miles only so that he can get some money).
By your last point ("unfair if one friend decides to share the ride for exactly 0 miles"), your suggestion would break the "Null player" axiom. I think it also breaks linearity but had a hard time proving that to myself while trying to articulate it here
I also think it breaks the null player axiom. If we would go without you and you without us we would pay 30 dollars and you'd pay 6 so in total we would all pay 36 and go with 2 separate taxis, but if you join our coalition we all 3 pay 30 dollars, so C(S U i) is not equal to C(S) so then by axiom 3) you cannot pay 0 dollars, because phi(i) must not equal 0
It's linearity that's broken -- split it into different trips. If you take it as the first part as one trip, then the second and third parts as another trip, you get $12 of surplus for the first part, so N=S=B=$2. Then for the rest you get $6 of surplus, for N=0, S=$3, B=$21. But that gave a total of N=2,S=5,B=23, different from the N=0,S=5,B=24 that you got by considering the three parts of the trip as a whole, and thus the approach violates linearity. Your post is very interesting, though, since if I add *clamp*ing to C≥0 (zero is fine, since that's the correct cost for the Null Player who doesn't want to go anywhere) then it's really hard to counter. Let's add a new rider, Alice, who wants to take an even shorter $2 trip. Now we have an excess of $20, which without clamping we'd share between everyone as A=-3,N=1,S=7,B=22. Well, obviously that's bad because it makes it more expensive for N&S&B, so they wouldn't accept it. But *with* clamping, we end up at A=0,N=0,S=6,B=24, which is not worse for anyone, so seems almost fine? (I'd been saying "not worse" to avoid needing to add exceptions for the Null Player, since adding a player who doesn't go anywhere and who thus doesn't change the costs for anyone is fine.) So I guess the axiom I'd use would be something like this: "Adding a player must decrease the cost for every pre-existing player whose cost has non-empty overlap with that of the added player". (Which in the "assume the taxi goes straight one way on one road only" case from the video is the same as "adding someone with non-zero cost strictly decreases all existing non-zero costs", since every non-zero player overlaps every other non-zero player.) That's probably implied by linearity -- non-overlapping costs could be split into separate trips, maybe? -- but I don't know if it's equivalent. I think it makes sense, though. It's basically "you can't join my taxi unless you make it cheaper for me than not having you in it", which seems like a very good way of making "sharing a cab should be win-win" into something specific.
@@pfeilspitze Strictly taken it does not break the linearity. In your example for the second part of the trip should be: N=-2, S=4 and B=22. The problem is more that a negative cost indeed contradicts the null player axiom.
I like the answer from a theoretical perspective. I don't think most people would split it that way in practice. Friends might just go for 10 each which avoids mucking around with small denominations or perhaps, 5, 5 and 20. I remember splitting a bill in proportion to our salaries (only an Actuarial department would do this) but certainly some weighting for disposable income might happen between people who would want to share a taxi.
It would certainly be unfair monetarily to the person with the shortest journey but if I was out with two people and we knew the longest trip would cost 30 I'd definitely prefer splitting it closer to 10, 10, 10 than 2, 5, 23. (7, 9, 14 maybe?) It costs the first person more but considering how much more the last person pays I'd happily chip in to help them out
Perhaps this is yet another example in which game theory doesn't work on how people actually behave... By the time you show this video to your friends, all of them have already got home!... so, I am not sure what's the lesson here: maybe, only befriend mathematicians? no, that sounds like terrible advice 🙃
@@academyofuselessideasthe idea is to study a small, inconsequential case to extend it to larger applications where it is important. For instance, maybe multiple independent groups working on a project together, where the project benefits each group unequally.
@@iCarus_A Pretty good point! Indeed, we simplify problems and look for analogous problems in the hopes of improving our understanding... The point is that I was trying to make is that sometimes we confuse the map for the territory, or we apply a theory incorrectly to real life scenarios. In many practical scenarios people do not behave as game theory predicts (which is what my comment was about). This is in part because one of the biggest hypothesis of plenty of game theory is the existence of an observable linear utility function that agents want to maximize (a so called homo-economicus). For example, here we assume that people want to optimize for the money they spend while not annoying their friends. But in practice, when. humans are faced with problems like this one, humans do not perform all those calculations. We rely on heuristics that are not too trivial to model. However, I agree that knowing the theory can guide decisions in more complex situations, once you explain the whole reasoning to all the participants. Thanks for sharing your insight and for including me in the conversation! This is interesting to think about!
I would love a variation to this problem where the actual journey is formed by destinations that increase each other’s total cost. So, for example, let us say the total cost for journey 3 is 30 but when player 2 gets in is goes up to 35 and with player 1 to 40. So, each additional journey increases the next journeys (making the first journey the same price but the next one more expensive)
Oh damn, I just intuition'd my way to the problem. The first thing I thought (I paused the video) was the 1st case, but then I thought ("hey, this isnt very good for the first one") so then I thought ("what if we take the average over the intersecting paths?") For intersecting paths, I mean the points where they share, say, B has to pay 18 when he is alone, since no one else should pay for that. For formalizing a bit, lets say: For x in [12,30], Average(B)=(30-12)=18 Then, for x in [6,12], Average(B+L) = (12-6)=6, and because L= B for their shared travel, we get B,L=3 For x in [0,6], Avg(N+L+B)=6 and N=L=B implies B=2 So,we get N=2 for all x L=2+3=5, for all x B = 2+3+18=23, for all x Which, is neat that there's an actual analytical way to do this, really shows that math is just rigurous intuition... Edit: Just watched the full video... Damn I felt special for a moment :(
My initial thought was exactly that final explanation you gave of the Chapley value. Another way to look at it is that each person pays exactly for their proportion of the total people-distance driven, meaning the sum of the distances each person rides. First person pays 6/(6+12+30), second person pays 12/(6+12+30) and the final person pays 30/(6+12+30). This is a much more elegant and simple way (imo) of calculating the proportion of the cost each person is responsible for, than creating a large table of permutations, summing rows, then finding the proportion of the sums.
I like giving everyone a consistent discount. The combined bill of 30 is 37.5% less than the individual bills of 48. 3.75, 7.50, and 18.75, doesn’t do the linearity axiom, but does give each individual a 37.5% discount, sums to 30, is closer to equity, and still incentives every player to be added to the coalition regardless of order.
@mkj1887 I believe it is a coincidence. It arises from the given values 6, 12, and 30. 1 - 30/(6+12+30) = 0.375. If you had different values, that discount number would be different.
First stop cost $6 and all 3 were in cab. So each pays $2 Second stop costs additional $6 but only B & S were in cab, so each pays $3 Third stop cost additional $18 but only B was in the cab, so he pays $18 Add that up and you get N= $2, S = $5 and B = $23. I don't get the idea of complicating this. Maybe Shapley values make sense in some other situation.
I show that this IS the Shapley value at the end. Part of the point is that as examples get more complicated than this toy example, we need a more procedural method that applies generally
What if the costs are ambiguous? Imagine B and C living the same distance away from A. So, we could either drive to B or C as second base and this will impact their marginal costs. Do we just permute across all paths also and take the average across these? This idea kind of also applies for all scenarios in which A, B, and C don't live in a straight line. Similarly, imagine B lives in a different direction from C, increasing the segment length BC compared to AC. Could such a scenario lead to a case where C would not want B to join? (Because C would pay more for ABC than for AC but still less than going all the way alone)
It seems like this would be the case where the Shapley algorithm is even more valuable, since you can’t do the intuitive “first leg split three ways, second two, etc.” algorithm. Instead, you can actually figure out the relative contribution of each participant in a way that also accounts for the differing total costs. It would be interesting to explore that possibility more.
@@PaulFisher Yes but I'm wondering if 1) this might create paradoxical scenarios in which one player has to pay more than going all by their own and 2) if permuting the path would already count as a violation of efficiency since we would consider ways which are longer and thus more expensive than the shortest route.
@@spressi For #2, when permuting the order of additions, you would still want to rank the best-possible route for any given group (i.e. the group of people is considered as a set, not as an ordered list; no matter the order in which people are added, the total value is the same). This is the same as what we already do for the all-three-in-a-line case: when considering Farthest vs. Farthest + Nearest, we still visit Nearest, then Farthest.
I came to the same amounts to be paid but in a different way of thinking: you just split the cost of each part of the journey that you are there for. For the first $6 part of the journey, all 3 are benefiting, so each person pays $6/3=$2. For the second $6 leg of the journey, there are only 2 people left so each person would pay $6/2=$3. Then for the last leg, there is only one person so they would pay the full remaining $18. In total, the first person paid $2, the second paid $2+$3=$5, and the third paid $2+$3+$18=$23 (and the total amount being paid is the total paid by each person: $2+$2+$2+$3+$3+$18=$30). This also removes the need to think of who got there first. I like my simple way of thinking, but very nice putting that all into specific mathematical definitions, as well as proving that it is the best way. edit: ok nevermind, I clicked play and immediately the next thing you said was precisely that lmao
Great explanation! It's nice to see game theory in an scenario that doesn't end up with society collapsing due to a series of "tragedy of the commons"!
We forgot to add a nice tip for the driver. After all, he's arguably being denied $18 of income, and he has to listen to three math nerds arguing in the back of his cab while he does it. 😂
Seems obvious to me, blue pays the full fare because he's a cool guy. Alternatively, they split the travel per meter between all current passengers, so up to blue's house, each meter is divided by 3, and blue gets out paying 2. Then there are two passengers to pink's house, so those meters get halved, and pink gets out paying 5. Then yellow pays the remainder of his journey alone for a total of 23. Good to know my intuitive thought based on how many people were in the taxi at any given time matches the maths version.
Before i actually hear the solutions my thought is ear person pays 1/x multiplied by the amount of each leg where x is the number of people in the car for that leg. So the first $6 leg would be $2 per rider. The 2nd $6 leg would be $3 per rider, and the 3rd person pays the remainder. Edit: this ended up being equal to the chapley value lmao
Friend: "So to split up this bill, we're going to use game theory" Me: "I'll pay the bill if you never mention game theory again and I can just go home to bed"
I was thinking more about dividing it in proportion of what every single person has to pay relatively to what they would have to pay in total if they rode separately and I also realised that there is a hidden assumption in this, and its that they all travel along the same road regardless of how many people there are but thats most porbably not the case the nearest person will always have the same route so anything they pay less is their gain anyways but the total cost may increase for other people compared to their individual optimal route, which should be included in this calculation for example if bazett would pay $25 if he traveled alone he only gains $2 in this scenario for traveling the longer route while the nash only pays 1/3 of the cost he'd have to pay anyways to get home put that way this doesn't seem as fair as it's made out to be, maybe each gaining the same percentage on the travel could be better
You can see more obviously why Same Percentage doesn't work if you use larger numbers. Suppose X & Y are going to the same place that has a $30 fare. "Obviously" (by symmetry), they'd each pay $15, which the Shapley and "same percentage" approaches both get. Now Z shows up and asks to get in the taxi. Z wants to go much further, so their alone fare is $840. What happens with both of the approaches? Shapley says X=$10, Y=$10, Z=$820. That's great -- X & Y are happy to pay less than they were when it was just the two of them, and Z is happy because it's costing less than it would alone. The "same percentage" approach, though, say X=$28, Y=$28, Z=$784. If Z were to propose that solution, X&Y would tell Z to go away, since they're not going to pay *more* to split the fare with an additional person. To abstract that a bit, you can think of it like an "induction" fairness, in a way. What's the base case here? You're the only person in the taxi, and you have to pay the full fare. And thus the same applies if you're the only one who cares about a portion of the trip -- your total cost can't be less than the incremental cost for the part of the trip that only you care about. That's why the solution where Z pays less than 810 is unfair, and thus why the Same Percentage approach is flawed.
@@pfeilspitze this only proves that the algorithm I made off the top of my head for an example isn't very good either and my main point still remains the potential alternative costs which don't exist in here
@@89alcatraz89 Sure, but it also shows that there's a need for *some* axiom in addition to the first three. So maybe you could suggest one of those. I might go for a "I'll take my ball and go home" axiom: if there's any subset who would pay less by getting a second taxi than by sharing the first taxi, it's not a good solution since those people won't agree to play the game (in the game theory sense) if that happens. What do you think of that one? (Assuming we're still in the "taxi goes in one direction in a straight line" mode of the original video problem, and thus we don't need to worry about the TSP issues.)
@@pfeilspitze I didnt pay that much attention to axioms but now that I've looked back on it the linearity is there just to look nice and the symmetry is much less restrictive than I though it was, it's basically unbreakable if the algorithm is a state function and even if its not would probably still be hard to break that being said your proposal does seem to capture the idea of alternative cost pretty well but it basically doesn't occur without alternative paths though I may be focusing too much on this particular example for having very obvious additional variables in it not just a single one that this was initially made for
My initial guess would have been: 1. Sum up each separate bill - 6+12+30=48 2. Multiply the total bill with the fraction for each person - 30×6/48 or 30×12/48 or 30×30/48 I can't make sense out of it but it seems fair to me and I don't see how it violates any of the axioms.
This looks pretty cool! My instinctive way would have been to add up all the values and pay in proportion, so in this case: 6 + 12 +30 = 48, then 30/48 = 0.625 Now the first one should pay 6 * 0.625 = 3.25, and the other two should pay 7.5 and 18.75 I'm not sure which of the axioms this breaks. This should respect at least the first three, so I guess linearity?
It breaks linearity yes. For example, if you have: -> 2, 4 and 6 for the first stage -> 3, 3 and 3 for the second stage With the proportion approach, they pay: -> 1, 2 and 3 for the first stage -> 1, 1 and 1 for the second stage -> 2, 3 and 4 in total But if you consider the stage with 5, 7, 9 (sum of both stages) and apply the proportion approach, you pay: 5/21*9 = 15/7, 7/21*9=3 and 9/21*9=27/7 which is different from 2,3 and 4
One thought I have is that if a fourth person has a $1000 fare, then everyone paying roughly 95% of their fare is a bad deal for the first three, compared to the system that felt good with the three original amounts. It's mutually beneficial compared to no sharing, but they have no incentive for going from three to four.
I feel like monotonicity could be an alternate axiom: the payment for one rider should never increase when you enlarge the pool. This is probably a consequence of the other axioms, but probably not equivalent. Monotonicity by itself allows that the $1000 person could offer each of the first three an extra penny against what they were paying before, and they would be contributing $29.97 to his fare, while he gives them each a penny.
My solution was the final explanation of breaking up the segments. It's really cool to see that this concept generalizes this way! I wish the video touched on how we can use the less intuitive Shapely value for a less intuitive setup.
I think everyone shoud divide equally the ammount for every sector between the people in the cab during that sector, first 6 is 2$ each, second sector is 3$ each for the 2 people in the cab and last sector 18$ is payed comepletely by the only person remaining so the totals are 2, 5, and 23
It's so funny to see Shapley values outside of work! I've been working on a quantum speedup for approximating Shapley values for a year and a half now!
The second way is n squared log n, if they are not already sorted. What kind of speedup are you able to get? I remember in a graduate CS class, a major part of the semester was studying Dijkstra's algorithm for finding the Nth element, to understand how it can possibly be O(n).
@@JohnDlugosz Are you wondering how you'd get a speedup searching a graph using a quantum computer? That would probably involve either amplitude amplification or maybe some Markov chains depending on the exact thing you're trying to do. For my work I'm leveraging an algorithm called "quantum speedup for Monte Carlo methods" to get an approximation of Shapley values with a square root fewer applications of the value function. If you're interested I have a (relatively) accessible seminar up on RUclips: ruclips.net/video/qytXmZGA9-U/видео.htmlsi=gmDtuxuLwBDmhunv
My initial thought was that they should each receive the same percentage savings on their journey. For the example given in the video, this means that you divide the total cost of the journey by the sum of the costs of them each taking their own taxi, i.e. $30/$48 = 5/8. Then you multiply this number by the cost of each of their journeys, so they each get a discount of 3/8 on what they would have spent if they didn’t share a taxi. This follows the first three axioms but breaks the last axiom. After watching this video, I realised that I still think that my method works better, because I disagree with the fourth axiom. In the video you sort of skip over what the fourth axiom means, but I think once explained it would be more controversial than the video suggests.
The argument of linearity does not include the social background and is just game theory where you pick passengers out of a possible pool of passengers that HAVE to take a taxi. This leaves out other factors such as the question whether public transport is an option for anyone/everyone and MOST IMPORTANTLY if the guy living the furthest away would even come to your next party if the brat living closest seems to benefit way more on a percent basis even though he already pays the lowest fee.
I think the way to accept the Linearity axiom is to add a 4th passenger, Jerk, whose alone taxi fare is $1000000. Using the approach in the video, you get N=6/4=1.5, S=6/4+6/3=3.5, B=6/4+6/3+18/2=12.5, and J=6/4+6/3+18/2+999970=999982.5. If instead you give everyone the same percentage savings on the journey -- it's about a 0.05% discount -- then you get N≈5.9997, S≈11.9994, B≈29.999, J≈999952. And now J has somehow saved more money than the entire price for N+S+B to get home! That's pretty weird. Don't think of it as "a bunch of friends who might be willing to subsidize the furthest one", rather something like "a group of strangers going home from the airport", where it's just cold game theory. Said otherwise, the axiom is "you can't get in the cab if it you joining makes it *more* expensive for everyone already in the cab".
A fair way to divide the cost, taking into account the reroutes the taxi had to take for the last 2 stops would be: 1. To calculate how much it would have cost for each person to take a separate taxi. Person 1 would have paid a. Person 2 would have paid b. Person 3 would have paid c. Adding all of them together gives us the total cost if each person took a separate taxi= a+b+c. 2. Calculate the percentage equivalence of what was actually paid. In this case, the total cost was $30: (30x100)/(a+b+c)=X 3. Multiply the individual values that each person would have paid had they taken separate taxis by X%: a*X% b*X% c*X% With this, each person is still paying less than what they would have paid alone, and the burdens of the reroutes are divided proporcionally.
You don't need these calculations. Just decrease the price with the same percentage. If the first guy pays 6, the second 12 and the third 30 on their own, the total payment would be 48 but they can share the ride so each will pay 30/48 of their cost that is 62.5% and they'll all have 37.5% discount on their ride. Fair enough.
I have an alternative: Counting the total distance traveled in a different way, A travels 6 B travels 12 and C travels 30, add that all up and you have a total amount of value generated from the taxi of 48. So you want to find what proportion of the value is used by each member so that's: A=6/48=1/8 B=12/48=2/8 C=30/48=5/8 So you divide the cost by 8 (3.75) so the amount paid should be as follows: A=$3.75 B=$7.50 C=$18.75 Axioms: Efficiency:✓ Symmetry:✓ Null Player:✓ Linearity:✓ Part of why I like this solution is because it's works better when it's not a perfectly straight path as well. So if it's not a straight line but still more efficient or somehow preferred to carpool like this then there is no go reason that B or C should pay an equal portion of the first leg of the journey. I believe my solution satisfies all of these but I'm not firm on it, I would LOVE others' inputs :3
This is great, but it actually does violate linearity (imagine multiple stages to this taxi “game”). When not considering linearity there are many good options like this one.
my three most favorite solutions to this problem: 1. everyone pays weighted by mileage over total covered miles for all persons: a = 6/48*30 = 3.75; b = 12/48*30 = 7.5; c = 30/48*30 = 18.75 2. the video's approach, shapley value a = 2; b =5; c = 23 3. lets say everyone throws the money they would have paid for their own segment into a bowl and leftovers get distributed equally: a = 6 - 1/3*18 = 0; b = 12 - 1/3*18 = 6; c = 30 - 1/3*18 = 24 (i like the third approach, it's super simple. but it's possible to receive money even after paying for the taxi (e.g. a travels 1 mile, b travels 10, c 100; a would come out with +2.67 $ ^^; b = -6.33; c = -96.33) guess he gets paid for his company ^^)
An interesting further thought is to consider the effect of a more direct route to the third house, so that if not making the detour, the cost would have been only 24. The existence of this more direct route means the third guy pays a bit less, and the other two pay a bit more to compensate for the inconvenience of having him make a detour...
The "alternative perspective" is pretty straight forward but doesn't generalize as has been pointed out. It would have been interesting to see an example where the taxi route is prolonged by the people who live closer by i.e. the person living furthest away would have to pay 30$ alone but the cost for the whole ride is 40$ because they don't all live "on a straight line". Then we would additionally have the problem of figuring out the cheapest route (meaning the total price) and whether subsets (meaning taking multiple taxis) would be cheaper overall or at least for all people within one subset (a subset could even contain just one person who would save money riding alone). And even then we wouldn't have considered the "currency" of time as riding alone is always the (one of the equally) fastest route(s). This video is definitely a great introduction to a field of study. Thanks.
For me it was just: First leg: $6 / 3 = $2 each Second leg: $6 / 2 = $3 both Third leg: $18 = for Bazett Thus, 2, 5 (2+3), 23 (2+5+18)…. Makes it easier to visualize haha.
I dkirectly takled the question as presented in the last "alternative perspective" section of the video. I'm glad to see that my intuition was aligned with the Shapley value.
Sharing the cost for each leg of the ride equally between the people actually in the taxi at that time was my first intuition. Seems a bit odd that someone would get a Nobel price for something so trivial that many people here in the comments just thought of immediately. I'm guessing the rigorous proof of it being the unique solution to all the fairness axioms was Shapley's real contribution to economics? Either way, I would have been much more interested in a practical answer to the proposed problem, rather than such an idealized solution to a rather contrived special case. In real life scenarios, taxi fares are slightly more complex, and the stops for all passengers would not be placed along the shortest route to the final destination. For instance, there is generally a basic fee (sometimes called a _dispatch_ or _flag drop_ fee) that you could argue should be spit equally between all passengers. There is sometimes an extra fee per passenger in the car, or per stop along the route. But more importantly, how would you accurately compensate for the fact that every passenger except the first would be forced to endure varying amounts of detour? It is easy enough to make reasonable approximations, if you know all the variables and given enough time to do the maths. Like estimating the cost for each person if they took a taxi home by themselves, and establishing a ratio that way. But real life is messy and full of unknowns, and it might be hard to do reasonable approximations on the spot. How should a typical group of friends _practically_ calculate an adequately fair split in a real world scenario?
What is wrong with just sharing it proportionally? So $30 is the total, but the prices if they would be alone added up would be $48. So they first person pays (6/48)×30, the second person pays (12/48)×30 and the third person pays (30/48)×30. This way everyone pays proportionally with the price it would have normally been, just with a discount of a factor of 30/48.
13:29 . How do you make that uniqueness claim ? Like Is there formal ptoof? Other methods like total precent off also satisfy the four fairness axioms. ( Total precent off method is multiply each person individual cost by discount% = #total cost together/ # total cost individually ) . With the numbers the pay is 3.75 , 7.5 ,18.75
If its a pragmatic, real world solution we want, then we absolutely have to factor in that you don't generally pay taxis up front. You also should consider the scarcity of taxis available at the time, which was my immediate response to "why would any of the individuals agree to the coalition in the first place". Anybody who has stayed late at a party or something knows the pain of trying to organise 10 trips when only 3 taxis are available. People suddenly don't care about proportionality and discounts.
I guess I see a certain logic to the way of dividing this that was rejected at the outset, but it only makes sense if they're actually friends. Nash may not really gain any benefit from sharing the ride with the two others, but he also doesn't really lose anything if they get to start their trip from Nash's house rather than from the starting location, which would be effectively what he's letting them do by riding with him. Shapley in turn really doesn't lose anything from letting Bazett start his trip from that house rather than from the starting point. The other thing to consider is that Bazett is in the absolute worst situation, having to pay $30 to return home. So it's not really shocking that the other two, with bills of only $6, might not want to make things even harder on Bazett than they are already going to be, given that he's the one stuck making such a long trip home in a taxi. I can definitely see how it might be unfair if they're strangers, but I don't think I would want to treat a friend like that and insist on them ensuring a benefit to me for letting them take advantage of what, for me, is already a sunk cost. Especially if it saves them something like $12 on a $30 trip. That is to say, even though you mathematically proved to me that this is the fairest outcome, I don't think saddling the third guy with a bill that close to what he would have paid on his own seems like a very friendly thing to do... a good way of handling bills among strangers, but I feel like it's not taking into account that friends generally don't mind doing things for each other that come at little or no expense to themselves. I guess the other thing the Math isn't necessarily taking into account is that Bazett probably travelled a long way from home to go to an event with those two friends, and while knowing he would have a long trip back. So there's sort of an inequality there in that one of them had to travel a lot farther to and from that would likely weigh on people's assessment. On the one hand, yes the $23 is Mathematically fair, but on the other hand, do they really want Bazett's bill to be so high that he starts reconsidering going to events that are futher from his house, or maybe even start trying to push for future meetups to be more equally located between the houses to lower his own bills in the future? There's something to be said for trying to keep his bill under $20, because that makes it feel like less psychologically, while also not going too far to the point that it seems like they're pitying him, which is what offering to split the bill three ways might make him feel like.
I don't think this is a good example to demonstrate the Shapley value, because it's an oversimplification. It assumes that all 3 houses are exactly along the same path. In this trivial case, the intuitive approach you mentioned at the end makes the Shapley-value feel overly complex. But, if you consider a case where not everyone lives on the same route but it's still worth it for the players: there the intuitive answer falls apart, but the Shapley value works fine.
I actually agree, seeing the comments of people guessing the intuitive approach makes me wish I started with that, then made the houses not colinear, and then showed Shapley value could deal with that more complicated case
Similar to other comments, my first thought was each person should share the discount proportionally. Since it would cost $48 if they each take a taxi separately, but only cost $30 working together, the savings is 37.5%. So we could simply reduce each person's cost by that amount and you would get $3.75, $7.50, and $18.75 respectively. However, this "solution" does not consider that sharing your space in the taxi is part of the problem. During the first part of the trip, all 3 people must cram in there with very little room. That first leg being so unpleasant, this explains why Nash gets the best deal overall and only pays $2 rather than $3.75. During the 2nd leg of the trip, at least it's a bit more comfortable for each person. And on the last leg, the final person has all of the "perks" like music selection, temperament control, stretch out across the full length of the back seat, etc. I'll concede. My initial "solution" was suboptimal.
I see 2 ways to argue fairness. One is comparing to the contribution. The other is calculating the average savings vs nonparticipation. If each person rode a separate taxi, the total group cost would be $48. Participating, the group cost is $30, which is a 37.5% savings. Splitting this evenly, the first person (the $6 trip) would pay $3.75. The second person (the $12 trip) would pay $7. And finally, the last person (the $30 trip) would pay $18.75. Each person gets an equal percentage discount off of their trip cost versus their alternative (nonparticipation). This does give a larger actual dollar discount to the longer participants, but those people are also paying an additional cost, namely, the extra time stopped while previous occupants get out and get any belongings. By approaching fairness from the philosophy that the savings vs the alternative, as a percentage, should be equal, we can reach a fair answer that equalizes benefits related to the savings garnered by the group.
This assumes that everyone's house is perfectly on route to each other's house. What if Shapley's house is far enough out of the way that going via his house increases the total by the time you get to your own by $5? I.e. if you went to your own house by yourself the total cost would've been $30, but if you got in the shared taxi, the total value would've been $35
In my experience hotel room sharing at a convention follows the Shapley model. 2 people share a room for 2 nights pre--convention. 3 share the room for the 3 nights of the convention and post convention 1 person stays alone for another couple of nights to do some sightseeing. Room cost is borne in full by person in room alone, shared between 2 when 2 occupy the room and split 3 ways when occupied by 3.
This is a great worked example of a complex idea. That there is a simpler "intuitive" answer to this particular case does not mean that the theorem is "over-engineered". However, it's distracting though that Dr Bazett never mentions this intuitive answer which must have been on many viewers' minds for most of the video. (Basically dividing up the journey into three segments, and allocating the cost of each segment across those in the taxi at the time.) Then this can be aligned to the theorem by saying (1) the division into 3 segments is just the application of the linearity principle (2) those in the taxi for a segment don't pay (null principle) (3) everyone in the taxi for a segment pays the same (symmetry) (4) the total must add up to #30 (efficiency). It would then be great to give (without detailed solution) a real-world example of a much more difficult problem which Shapley handles but for which there is no immediately intuitive solution.
This was really interesting to watch for me since the "alternate perspective" on the solution was my immediate instinctive reaction to how this should be solved.
When I saw the liniarity axiom, I immediately thought of to treating it as 3 separate "journeys". First "journey" is to Nash's house, which costs $6, and there are 3 people in the taxi, so nash should pay $6/3 = $2. In the second "journey", we are going from the Nash's house to Shapley's house, which would cost $6, and there are two persons in the taxi, so Shapley shoud pay $2 + $6/2 = $5. And the last "journey" is Bazett by himself, so he should pay $5 + $18 = $23. This method is kinda different, but yelds the same result, easier to calculate, and more intuitive in my opinion.
My intuition is to equalize the percentage discount. The total bill to take the trips separately would be $48. We only have to pay 62.5% of that, so each person pays that fraction of their orginal cost. $3.75, $7.50, $18.75
visually you could simply split vertically each part on the number of people present during that part. (1/3 for each x 6, then 1/2 x 6, then 1 x 18). give the answer quick with less general formula tough
Far easier way to get same answer: Segment 1 had 3 people: $6/3=$2 each Segment 2 had 2 people: $6/2=$3 each Segment 3 had 1 person: $18 Nash pays $2, Shapley pays 2+3=$5, and Bazett pays 2+3+18=$23. Same answer just way simpler method
I'm glad to say i understood it from the alternate perspective without starting the video and got itt. Didn't know that the Shapley value would be the same as mine
Another look at it, for each segment divide the contribution by how many plays, add that to each player's total payment, continue doing that for all segments, what you end up with is the same result. So in this case the first segment has 3 players with a contribution of (6 - 0 = 6), and so (6 / 3 = 2), total is now (2,2,2), then for the second segment there are 2 players with the same contribution so (6 / 2 = 3), total is now (2,5,5) and lastly the last segment only has one player with a contribution of 18 so the end total is (2,5,23) This method actually came to mind first when the question was initially asked. Edit: apparently this method was spoken about at the very end of the video xD
Easy: You divide the 6$ by 3, so each pays 2$. Then you divide the other 6$ by 2 so the 2nd and 3rd person pay 3$ and lastly the last person pays the remaining 18$. That means that: the 1st person pays 2$, the second pays 5$ and the third pays 23$. Oh I finished the video and that's the exact solution. Wow I'm a genius
I'm not familiar with the taxi system where you are, but here (Scotland) they have an upfront cost (like £2 just for getting into the taxi) then I think they add an amount based on how many people are in the taxi (say £1 per additional person). So if individual distances cost {4,4,12} then C(N)=6, but for N+S the meter has reached 7 when they pass N's place, and hits 11 at S's place, and finally C(N,S,B) would read {8,12,24} as it passed N,S, and B. So, splitting the bill has become considerably more complex! But as long as N pays less than S pays less than B, who pays less than a single trip, then it's probably all good.
Cool video and presentation! I feel like numerous real world spliting situations are ones I don't particularly think symmetry axiom is a fair assumption. For example, if you see taxes as a cost dividing endevor (which I don't but lots of people do) I don't think this axiom will lead us to a fair taxation scheme. And the point is that symmetry seems to assume something to look fair, something in the direction of "every player has the same starting conditions for paying costs"
I haven't watched the entire video yet so maybe you'll mention this too, but instead of averaging the permutations I just split the bill according to who was in the car in each section(and got the same result) In the first part, 3 people were taking the cab, and the journey cost 6 dollars so they each pay 2$. Since N's journey ends there, that's the total amount they're gonna pay. In the next section of the way, 2 people need to share the fee for a journey that costs 6$, so now they each need to add 3$ to the 2$ they already owe for the first section, leaving them both to pay 5$. Since S's journey ends here, they pay 5$. Finally, one person has to go for another journey that costs 18$ so they just pay the 18$. Making the final result: N pays 2$ S pays 2$+3$=5$ B pays 2$+3$+18$=23$ Edit: yap, you mentioned this exact approach in 14:35
My initial thought without mathing jt as if you were actually talking to friends about how to do it before it happened was the first person wants to save some money so maybe $2 savings so cost of $4. 2nd person is same way so want to take a couple bucks off. Would also be okay with $2 but maybe $3-4 off of 12. 3rd person is still happy they dont have to pay 30. So now they are paying between 26-24. That's without trying to even do basic math. I think i was oretty close
My first instinct was the same as the top comment: divide the payment per person for each part of the trip. What's interesting is that it comes to the same values and seemingly follows the same axioms, suggesting that the method may actually be the same. So, I want to try to test that. One way to test it is exploring how the permutations change depending on the number of people and their 'order' in which they leave the equation (get off the taxi). Exploring the case of 3 people (N=3): Permutations = 3! = 6 = 2N According to my original instinct: The first person (P1) should pay the cost of the first part (C1) divided by N P1 = C1/N The second person should pay what P1 pays, plus the remaining change (delta or d) to get to C2 divided by N-1 (because there is 1 less person paying) P2 = C1/N + dC2/(N-1) The third person should pay what P2 pays plus dC3 (which is technically divided by N-2 for if this formula is needed for any number of N) P3 = C1/N + dC2/(N-1) + dC3/(N-2) According to game theory: P1: In 2 permutations, they pay C1 2*C1 / 2N = C1/N P1 = C1/N Therefore, for P1, the two designs are equal for N=3 P2: They pay 1*C1 and 2*C2 C2 = C1 + change to get to C2 (deltaC2 or dC2) 1*C1 + 2*C2 = 3*C1 + 2*dC2 (3*C1 + 2*dC2) / 2N = (3/2*C1 + dC2) / N To make the two models for P2 equal (and inserting N=3 because it is required for these formulas to exist): P2 = (3/2*C1 + dC2) / 3 P2 = C1/3 + dC2/(3-1) = 1/3*C1 + 1/2*dC2 1/3*C1 + 1/2*dC2 = 1/2*C1 + 1/3*dC2 1/3*C1 - 1/2*C1 = 1/3*dC2 - 1/2*dC2 (1/3 - 1/2)*C1 = (1/3 - 1/2)*dC2 C1 = dC2 Therefore, assuming I did none of my maths wrong, the 'game theory' formula and the 'separate parts' formula only match when dC2 = C1, or when the distance between the original location and the first house is the same as the distance from the first house to the second house. Testing my maths using the game theory formula for P2 (C1=6 and dC2=6): P2 = (3/2*C1 + dC2) / N = (3/2x6 + 6) / 3 = (9+6)/3 = 5 Testing the same using the separate parts formula for P2: P2 = C1/N + dC2/(N-1) = 6/3 + 6/(3-1) = 2 + 3 = 5 Testing game theory for C1=6, dC2=8: P2 = (3/2x6 + 8) / 3 = (9+8)/3 = 17/3 ~= 7.667 Testing separate parts for the same: P2 = 6/3 + 8/(3-1) = 2 + 4 = 6 6 ≠ 17/3 Therefore, because the two methods differed in answer when C1≠dC2, it is reasonable to say that I did not do my maths wrong and the two methods only coincidentally equalled in the video's specific scenario because C1=dC2. Also, yes, I did try to equate the two formulas without making N=3, but it became a very complicated problem involving numerous powers of N, so I decided to simplify it by inserting the known value instead.
You've described P2's marginal contributions wrong and imposed the result. P2 does NOT pay C1 in the permutation. P2 pays dC2 in that permutation (and 2 C2s in other permutations, as you wrote it out). By writing it as C1, you've implicitly imposed the condition that C1=dC2.
Idk how I figured out the answer before he finished explaining it, but I did. If you look at it, the first person is slitting his bill with 3 people, 2 people are splitting it in the second and 1 in the last
I usually do the following: We see how much each person would pay if we were not sharing. Sum everyones value, and calculate the total discount of going together. In this case, 6+12+30 = 48, but we are paying 30 with the discount. This means aprox. 30% of discount. Apply 30% of discount to each value in the sum: 6x(0,7) ; 12x(0,7) ; 30x(0,7). Everyone gets the same percentage of discount, which seems fair.
A lot of people seem to be suggesting a problem based on where the houses are located, but like, if the houses were lined up in such a way that the route would be too complicated, it's unlikely they'd take the same taxi - since they'd know this already. So we can assume the houses are relatively "linearly" far from the origin, and the route will be more or less optimized.
With just hering the problem and didn't watch the solution yet I would suggest the following: They drive to the first house toghter so they spitt this cost of 6$ equaly in thirds means everybody pays 2$ for this fist distance. The the second house they are 2 people so they splitt this amount equaly again but just between the 2 in the car. So both pay additionally 3$. The rest the last person is driving alone so it pays the total cost of this. In absolute numbers that means: Nash 2$ Shapley 5$ Bazett 23$
I’m still at 5:00, but I thought it like this: - A benefits for a trip long 6 - B benefits for a trip long 12 - C benefits for a trip long 30 Now let’s add them up: A+B+C = 48 And we do the proportion: - For A we have: 6 : 48 = x : 30 - For B we have: 12 : 48 = x : 30 - For C we have: 30 : 48 = x : 30 A pays 3.75 B pays 7.50 C pays 18:75 This way everyone pays in a way that is proportional to the benefit they had from hopping on the taxi.
I think Linearity is really the key to understanding this. Since only B cares about the last segment of the trip, the only fair answer has to be that B will pay at least 18, since they have to cover that part on their own, since N & S have to reason to subsidize the part they don't care about. But they also have to pay *some* part of the cost for the earlier segments too, or as you say, N & S have no reason to let them in the cab at all. Then symmetry means that cost is split evenly when multiple people are using the same segment.
You should also add in flagfall, starting cost for the taxi. Let’s say it’s $3. Each person contributes equally for it . That way it’s slightly cheaper for the 3rd and 2nd person because they have to take stops which slowly decrease from their experience.
Without all the game theory stuff my initial gut reaction would be: for each segment of the trip you were in, you should pay the cost of that segment divided by the number of the people in the car during the segment.
So:
- the first person to get out pays 1/3 of the first segment
- the second pays 1/3 of the first trip + 1/2 of the second segment
- the third pays 1/3 of the first, 1/2 of the second and the full third segment.
So: 2, 5 and 23, respectively.
I have same approche :-)
I do love skipping all the theory stuff and getting the same answer
Same here
That was also my thought.
Same here
A 3b1b gold plushie is genuinely a Medal of Honor and no other argument can exist.
Yeah this is my first video I've seen and as soon as he dropped the plushy I was sold.
The "alternate perspective" follows exactly from symmetry and linearity axioms - they are essentially playing 3 consecutive games on 3 disjoint segments with 3, 2 and 1 equivalent players respectively.
Without efficiency you couldn’t conclude that it hasn’t add to the total. E.g. perhaps they should all pay $3 for the first journey. It’s obviously stupid but without the axiom of efficiency we can’t rule it out.
And you need the null player axiom! The second and third games technically have all three players, but a subset of the players are null because they do not contribute to the cost for that game.
exactly!
My first thought is to think in terms of man-miles. Each person would pay a percent of their "alone" cost equal to (farthest distance) / sum(man*miles) In this case, 30 / (6+12+30) = 30/48 = 0.625. Each person pays this fraction of what they would have paid on their own. So Nash pays $3.75 miles, Shapley pays $7.5 miles, and Bazett pays $18.75 miles. Everybody gets the same discount rate. Besides being much easier to calculate, this approach also encourages Nash and Shapley to include you, because without your 30 mile trip, the discount rate they could achieve with just the 2 of them would be 0.66... and their total amounts would be $4 and $8. If you think of it like that, then each person has a negative cost function. This seems much more fair than arguing about how much a person is costing the others by adding miles. The method shown in the video provides the most benefit for the least needy. There's also a societal cost - the person who has to travel the farthest benefits the least. If it 's not a great saving, they are likely to hire their own cab, creating more traffic and burning more fuel overall.
You say there's no other way to do it fairly, but how does the man-miles approach violate any axioms of fairness?
The trick is figuring out the total distance before the first person leaves the cab. Oh, and also a little thing called the traveling salesman problem. We will leave that as an exercise for the reader. XD
This was my idea aswell. Does anyone know what axiom is broken?
Arguably, the “fairest” approach that also promotes cooperation is to take the average (mean) of the Shapley value and the method you describe. In this scenario, Nash would pay $2.875, Shapley $6.25, and Bazett $20.875. Handle the rounding as you wish.
Of course, the example is somewhat over simplified in that the taxi meter probably started at ~$2, so that portion should be shared equally and only the $28 in time/mileage should be divided using another method. In this case, that makes little difference.
I believe linearity is what breaks down. Specifically, the guy who lives closest is motivated to split the journey in two - first to his house, getting a 1/N price there, and then leave the others to sort out their own trip from there on.
I came to the same solution. I didn't think of it as "man-miles" (a la 'the mythical man-month') but a value proposition. The three are sharing a value pool that sums to $48, for a cost of $30. Each should contribute to the cost proportionally to the value they extract from it. Boiled down, they each discount their fares by -- in this case -- 37.5%, and they each get a larger total discount according to the relative length of their rides.
I also believe that this is the better way to go and think about it
The method he shown in the video seems interesting but unbalanced
(Written at 2:50) Look at the ride as three separate rides: The first $6 should be split among all three, then N. leaves and the next $6 should be split between S. and B., and the last remaining $18 are for Dr. B. himself to pay alone.
Exactly my thoughts too
@@cheeseplated same
In a more realistic scenario, homes won't be located on a neat straight line. Going from A to B won't take you exactly half way from A to C. In some cases going from B to C might take longer than going straight from A to C.
@@MortyrSC2 Doesn't matter. The fact that two sub-rides have equal cost is coincidence (the video could for sure provide a better example).
@@Bolpat The problem with the example is that taxis travel in two dimensions. If the path from start to A is 3 miles north, and from A to B is 4 miles east, then B has to travel 7 miles when they could have gone straight home in 5 miles. It's unfair to make B pay for those extra 2 miles.
Because it’s improbable that the 3 destinations lie exactly upon the same lowest cost/time/distance route from the origin, there is an additional consideration each participant should invoke. What is their cost solo, or in any subset of participants vs their cost for the full set. It might be less costly to break problem into two or more separate coalitions taking different routes, and compute the Shapley value for each subset, and each participant can then choose their lowest individual cost.
However, the lowest cost for a given participant doesn’t guarantee the lowest cost for all participants (nor the lowest combined cost). Participants can negotiate (or again calculate something like the Shapley value) using the best options for each participant to minimize total costs and individual costs. But since total cost is no longer fixed, you can’t be guaranteed to meet all 4 of the specified criteria.
I don't see how being on the same route makes a difference. The formula still works, I think, and everyone's payment is still lower than outside of the coalition.
Now, in practice it's impossible to talk about this topic without talking about value the people are getting out of the coalition, which is very subjective and that throws the wrench into the fairness theorem (I think).
@@levbobrov1398imagine player 1 has to go $6 on the meter on the opposite direction from player 2, then the total bill will be $24 (6 to get to player 1 destination, 6 to backtrack, and 12 more to get to player 2 destination) and there's clearly no benefit for player 2 to ally with such a player 1, this is an extreme example, but route efficiency and deviations will impact the problem
the maths in the video will work better on cases that the cost of adding a person doesn't make the trip that much more expensive (as in my extreme example) that not having them join would've been much better
@levbobrov1398 An example of the above is, if S & B live North of the starting point but N lives south then the formula still works to fairly split that route, but that's a stupid route and it'd be better to split 2 taxis
I would do it simply like this:
the bill is $30
the total "distance cost" is 48 = (6 + 12 + 30)
each person pays their proportion of the total "distance cost", so first person pays 6/48 * 30 = 3.75, second pays 12/48 * 30 = 7.5, third pays 30/48 * 30 = 18.75
Pays the whole bill and seems pretty fair to me. Everybody pays the same (lower) rate for their distance. (62.5% of the normal rate, to be exact)
This was my initial thought, too. The "fairness" in this solution is that everyone gets the same discount.
It works alright in the case of the taxi since everyone is going to a fixed location, but it falls apart when you look at a more geneal idea of contributing to a shared resource.
Say the first two people use the resource and plan share it responsibly (in the taxi, a $6 and $12 fare for driving home). A third person can show up and gain an inordinate amount by exploiting the resouce (a $1k fare for a road trip). With this distribution, the first two responsible parties end up paying almost full price while the third party gets almost a $18 discount. Decidedly unfair.
The simplest way to phrase the "fairness rule" that indicates this is an unfair system is that "the addition of a new party should never increase the amount existing parties pay."
This was my first thought as well. However, this doesn't reflect that different travellers are sharing different proportions of their journey with different numbers of people, so arguably some are due a bigger discount than others.
@@OxidisedGearzwhich axiom does this method fail to satisfy though? As far as I can see, the first three still come through.
Thank you,@@OxidisedGearz . I was having this question, and it really helped.
@@subrabalanmurugesan7159 Maybe there is a linearity violation when you actually try to write out the formula? everything else seems like it should hold
I wonder how the total price changing would be affect this. An extreme example would be to imagine Nash's house is actually $6 in the wrong direction (so $12 to return to the starting point). I hope it's clear to see that Nash ought to pay the full $12, since it gets the other two literally nowhere. Of course, Nash would be better off getting a separate taxi so he probably would
I think "would be better off getting a separate taxi" is the best way to look at this, actually. You could make an axiom of something like "adding someone to the taxi can never increase the cost for anyone already in the taxi", because an additional person won't be invited into the group if it'd make it more expensive for the people already *in* the taxi agreement. (I think this is the Linearity axiom, really. The Null one too, maybe -- assume there's someone in the taxi already who wants to go nowhere and thus will only pay $0. Anything that makes that person pay anything would also violate the "new person made existing person pay more" axiom.)
My first thought was to split the bill for each "segment" between whoever is still on the taxi (like you did later on). Indeed I got the same result, no formula needed. The only downside is it does not generalize equally well.
The alternative perspective is intuitive and it would be neat to show that it is the same as the full explanation, which seems completely out of the blue at first.
It's also very easy to actually use this method in practice (assuming everyone has change/venmo): at each stop, divide the fare shown on the meter, minus the contributions of anyone who has already been dropped off, equally among the passengers to determine the amount the person being dropped off should pay.
It's definitely possible to rearrange the shapley value in terms of "synergies" formally, actually there are a couple ways to write it beyond the marginal contribution way I defined it.
A quick way to see how this is related is the Linearity property. Namely you can divide the original trip into three subtrips, one that costs $6 with three players, one that costs $6 with two players, and one that costs $18 with one player. Clearly if you use the main method from the video at each step you get all three people paying $2, the remaining two person paying $3, and the last remaining person paying $18, and so by the linearity property the final solution for each person is the sum of those three subsolutions for that person.
@@Bodyknock I think Linearity is by far the most load-bearing one here, so it's a shame it was skipped over. I'm sure there's a complicated reason that Null is needed too, but in a sense Linearity intuitively covers that too: someone who wants to stay where they are for $0 can address that by splitting the trip into the "stay here" trip for $0 and the "go somewhere" trip for non-zero with everyone else.
Why not just have everyone divvy up the cost for the ride that they share? So the first six dollars gets split into three, the second split into two, and the remaning 18 all lies on the last guy. It gives you the same exact result.
Edit: always watch until the end before commenting lol, it's in the video
To me, another fair way of splitting up the cost is to make each person save the same % of their travel cost. You do this by finding the ratios of the different distances. A short formula is to divide your distance by the total of all distances together. This gives 6/(6+12+30)=1/8=~$4 for the first one, 1/4 =~$7 for the second, and 5/8=~$19 for the third. (30/8 is not an integer, so some rounding has to be done.) I am not sure what axioms this goes against, but it seems fair to me. (It certainly follows the 1st and 3rd axiom. I did not understand the 2nd and 4th axioms well enough to know which one it doesn't follow, but I don't necessarily agree with them either.) What is wrong with this approach?
It follows second, but not necessarily the last one. I also this that would be more fair
This was my approach too, but It's definitely not the best. Guys with $10 and $10 would pay $5 if they were to travel with each other, but if a guy with $25 cost wanted to fit in, the costs would change to 5.55, 5.55 and 13.89. Why would the first 2 guys include the third in this situation?
@@misikaro Thank you for the example. I wondered what could be wrong with my approach and now I know. It looks like the only way things go wrong is if multiple people are carpooling together and one more person with a longer distance wants to join.
@@misikaro Because they are probably drunk friends wanting to get home as fast as possible, thinking about the price split the second day. xD
@@michalgabriel9647 xD
My first thought was that each person should pay in proportion to the "utility" they receive from the ride. Nash receives a $6 value from the ride, Shapley receives a $12 value and Bazett receives a $30 value so there is $48 dollars worth of utility received overall if you double count the bits that overlap. Apportioning cost then gets us Nash = (6/48)*$30 = $3.75, Shapley = (12/48)*$30 = $7.50, and Bazzet = (30/48)*$30 = $18.75. I wonder which axiom this method violates.
The problem is that the dollar value does not necessarily line up with the utility. For instance, the meter only read $30 dollars for Bazett because the taxi had made stops for Nash and Shapley along the way. For all we know, the taxi drove east to drop off Nash and Shapley, then had to turn around and go back west and go out past the original starting point to reach Bazett's place. So now you would be expecting Bazett to not only pay the most money, but also spend the greatest amount of time stuck in a taxi when he's not even necessarily the guy with the most distant house.
It violates Linearity. The easiest way to see why it's a bad solution is to add an extreme value: a 4th person, J for Jerk, whose fare is $1000000.
Using the approach in the video, you get N=6/4=1.5, S=6/4+6/3=3.5, B=6/4+6/3+18/2=12.5, and J=6/4+6/3+18/2+999970=999982.5. That's great! The existing passengers all saved some money by letting J join, and so did J over travelling alone.
If instead you give everyone the same percentage savings on the journey -- it's about a 0.05% discount -- then you get N≈5.9997, S≈11.9994, B≈29.999, J≈999952. And now J has somehow saved more money than the entire price for N+S+B to get home! All those numbers are higher than the ones you calculated for N+S+B taking a cab without J, so there's no game theoretical reason for N+S+B to let J get in the cab at all, and thus it's not a good solution.
So I think a reasonable way to think about (a consequence of) Linearity is that with a good solution, adding someone else to the taxi shouldn't ever make it worse for the people already in the taxi, because if it did then they wouldn't let the person in the taxi.
@@pfeilspitze Actually, the method suggested in this comment would lead to N=6*1000/1048=5.72, S=11.45, B=28.63, J=954.20, which sounds a bit more reasonable than your numbers. However, it's still true that all except J now pay more than they would have (according to the same method) if they hadn't let J into the taxi. My first idea would also have been to use this method, but your example serves as a clear counter-argument.
@@elevenelven5388 I think you ran the numbers for a thousand instead of a million? But I'm glad it still works as a counterexample with the smaller number -- I just picked a big one to emphasize the silliness.
@@pfeilspitze thank you for this brilliant explanation
I'd think the fairest way would be for each to receive the same discount relative to what they would have paid if going alone. That looks to be ~62.5%, i.e. $3.75, $7.50, and $18.75. So they all get about a 1/3 discount for working together and no one gets a greater advantage.
it violates linearity, the person with the longest path gets the most advantage.
I had the same reasoning and same numbers than you. From a mathematical point of view, the proposed solution might be better (2 5 23).
In real life, I prefer yours. Everyone is benefitting from it anyway, and the person leaving further have to pay more regularly, and sometimes also are the person who can't live near, because housing is more expensive there.
That's how i would split it with my friends
@@barte4215well no, every dollar they would have spent is instead $0.625, yellow saves more money only because hes traveling further
they all get a 37.5% "discount"
I thought the same at first, but from a game theory perspective, the presented solution makes more sense.
If we suppose the 3rd person lives $60 away (instead of 30$) this becomes apparent. With %-discount cost-division, the closer two people both pay less if they exclude the 3rd person. For example the closest person pays 6/78*$60= $4.61 with three, but only 6/18*$12= $4 with two in the taxi. This is double for the 2nd person. According to game theory persons 1 and 2 would now take a taxi without the the 3rd person who is now even worse off. Therefore, the 3rd person should pay more.
That said, not looking at it mathematically, I like the %-discount method better.
Last part of the trip (18$) is fully imputable to person 3, hence he pays 18$ for that part. The second part of the trip (6$) is the responsability of persons 2 and 3, hence they split the bill and each pays 3$ for this part. Finally, the first part (6$) is evenly shared between the three persons, so they each pay 2$. In total, person 1 pays 2$, person 2 pays 5$ and person 3 pays 23$.
That's $18, $3, $6, $2, $2, $5, and $23, *as shown in the video* . The dollar sign goes to the left of the numbers. I don't understand the tendency to write it wrong in YT comments, when you'll have never seen it written that way in life.
@@JohnDlugosz Not all currencies are written like that, and using the dollar sign makes no intuitive sense (as linguistically you say "X dollars", not "dollars X"), even if that is the default. I don't understand the need to "correct" someone like that.
@@JohnDlugoszyes but it's a much simpler way of answering the question. Forget all the marginal contributions and instead get a fair amount
@@JohnDlugosz In French-speaking Canada, the dollar sign goes after the number, the internet tells me. In Europe it is also quite normal. And in Cape Verde they put it at the position of the decimal point, apparently.
Mere convention. Never say never.
@@JohnDlugoszI dont understand the ignorance of americans im the youtube comment field. The world is bigger than the USA and even just a bit north of you is a country writing the dollar after the number.
The initial idea I had coincided with the first proposal. However, I later considered an alternative method: First, calculate the total cost if each person were to go alone, which adds up to 6 + 12 + 30. Then, divide each individual's solo cost by this total amount. For example, N's share is 6/48, S's is 12/48, and B's is 30/48.
These proportions are then applied to the shared cost. Consequently, N would pay 30 * (6/48) = 3.75, resulting in a saving of 2.25. Similarly, S pays 30 * (12/48) = 7.5, saving 4.5, and B pays 18.75, saving 11.25.
In terms of relative savings, each person saves 37.5% of their original cost. This approach ensures that everyone saves an equal percentage, which seems the most equitable to me.
The "alternative perspective" is the first thing that came to my mind when the question was posed at the beginning of the video and I think it's an approach many many times more natural, simple and easy to understand than that thing about the average marginal costs of every imaginable reality. I don't get why anyone would choose that approach over the more logical one.
I think you meant "over the more intuitive one". Both approaches are logical.
I'm not entirely sure, but I think the game theory approach is more general. It might be a little silly for this example, but this example is an easy way to explain it so you can then use the same approach on more complicated problems.
That's been my experience whenever "oh, why didn't you just do it the easy way?" has come up in a math class.
The intuitive approach would get a lot more complicated if, for example, the taxi ride for the third person (without detours) costs 20 dollars. He would have no incentive to share the ride at 23 dollars, so the fair share has to change, despite the shared ride still being the same 30 dollars.
@@Frank01985 obviously, in the case you suggest, the third person just wouldn't share the ride and go home by him/herself.
@@Cloud88SkywalkerB would do that because N and S definition of "fair" is wrong when B can go solo and pay less than sharing.
The more intuitive answer works for very simple tasks like this example. The shapley method works with all problems of this kind.
1. Assumption: The taxi drivers route taken already is the optimum route for every single passenger.
First stretch: 1/3 the cost -> 2 dollars each (3 people)
Second stretch 1/2 the cost-> 3 dollars each (2 people)
Third stretch 1/1 the cost -> 18 dollars (1 person)
N 2 dollars - S 5 dollars - B 23 dollars
An economics related video ! As an economics enthusiast I'm really grateful
Unless I'm mistaking, Jhon Nash didn't really invent Game Theory, but hugely contributed to it, the actual creator is Von Neumann, who has also contributed to linear programming and the Von Neuman architecture in computer science.
personally think von neumann is the most underated scholar of the last century in popular terms. if you think about it, CS has been around only in "theory" less than 100 years, let alone real practice. so, he was like others (Shannon, say, who is much more widely touted popularly) literally making this s**t up as he went along. and boy did they get in right, not just in practice, but the theory. it must have been exhilirating. so much of the stuff he came up with has been re-discovered as useful, because it dated so fast. reliability was such an issue early on in circuits (valves and stuff),but quickly less so. he realised that rather than just having lots of "copies" of the same circuit element and just taking the most popular result, you could reduce errors WITH circuit design (which is different from error correcting codes [Shannon-style]). the idea of Expanders is now formalised used in many applications. see, "PMSP - Expander graphs: Applications and combinatorial constructions I - Avi Wigderson" on the IAS channel here (specifically 34mins in).
*Has to pause at **4:00** because the simple obvious answer was being ignored.*
Their distances traveled: 6, 12, 30.
The total of what they got from the taxi: 6+12+30 = 48.
Nash got 6/48, Sharpley got 12/48, Gazety got 30/48.
Apparently this cab costs 1/ km. So it costs 30 total.
Nash pays 30 × 6/48 = 3.75
Shapley pays 30 × 12/48 = 7.50
Bazette pays 30 × 30/75 = 18.75
100% fair. Each pays 0.625/ km for the cab.
I use this:
each * ( total / sum(each) )
so:
30 / (30 + 12 + 6) = 0.625
then,
6 * 0.625 = 3.75
12 * 0.625 = 7.5
30 * 0.625 = 18.75
if you add them, it is - total of 30, and everyone payed less but proportional to what they would have payed if they were alone.
My first thought was also the exact thing you described in the "alternate perspective". On second thought I had this alternative: Everybody pays the full price, but the surplus money is divided equally between the people. In this example: $6+$12+$30=$48, which is $18 too much. The $18 gets divided by 3, so each person gets a discount of $6. Resulting in the prices of $0, $6 and $24. I don't see which of the proposed fairness axioms is broken (except if there is another one not mentioned: "C must be > 0 for everyone involved" - because it seems unfair if suddenly one friend decides to share the ride for exactly 0 miles only so that he can get some money).
By your last point ("unfair if one friend decides to share the ride for exactly 0 miles"), your suggestion would break the "Null player" axiom. I think it also breaks linearity but had a hard time proving that to myself while trying to articulate it here
I also think it breaks the null player axiom. If we would go without you and you without us we would pay 30 dollars and you'd pay 6 so in total we would all pay 36 and go with 2 separate taxis, but if you join our coalition we all 3 pay 30 dollars, so C(S U i) is not equal to C(S) so then by axiom 3) you cannot pay 0 dollars, because phi(i) must not equal 0
It's linearity that's broken -- split it into different trips. If you take it as the first part as one trip, then the second and third parts as another trip, you get $12 of surplus for the first part, so N=S=B=$2. Then for the rest you get $6 of surplus, for N=0, S=$3, B=$21. But that gave a total of N=2,S=5,B=23, different from the N=0,S=5,B=24 that you got by considering the three parts of the trip as a whole, and thus the approach violates linearity.
Your post is very interesting, though, since if I add *clamp*ing to C≥0 (zero is fine, since that's the correct cost for the Null Player who doesn't want to go anywhere) then it's really hard to counter.
Let's add a new rider, Alice, who wants to take an even shorter $2 trip. Now we have an excess of $20, which without clamping we'd share between everyone as A=-3,N=1,S=7,B=22. Well, obviously that's bad because it makes it more expensive for N&S&B, so they wouldn't accept it. But *with* clamping, we end up at A=0,N=0,S=6,B=24, which is not worse for anyone, so seems almost fine? (I'd been saying "not worse" to avoid needing to add exceptions for the Null Player, since adding a player who doesn't go anywhere and who thus doesn't change the costs for anyone is fine.)
So I guess the axiom I'd use would be something like this: "Adding a player must decrease the cost for every pre-existing player whose cost has non-empty overlap with that of the added player". (Which in the "assume the taxi goes straight one way on one road only" case from the video is the same as "adding someone with non-zero cost strictly decreases all existing non-zero costs", since every non-zero player overlaps every other non-zero player.) That's probably implied by linearity -- non-overlapping costs could be split into separate trips, maybe? -- but I don't know if it's equivalent.
I think it makes sense, though. It's basically "you can't join my taxi unless you make it cheaper for me than not having you in it", which seems like a very good way of making "sharing a cab should be win-win" into something specific.
@@pfeilspitze Strictly taken it does not break the linearity. In your example for the second part of the trip should be: N=-2, S=4 and B=22. The problem is more that a negative cost indeed contradicts the null player axiom.
I definitely though of the "alternative perspective" immediately and then wondered if and how the marginal cost averaging would work out the same.
I like the answer from a theoretical perspective.
I don't think most people would split it that way in practice. Friends might just go for 10 each which avoids mucking around with small denominations or perhaps, 5, 5 and 20.
I remember splitting a bill in proportion to our salaries (only an Actuarial department would do this) but certainly some weighting for disposable income might happen between people who would want to share a taxi.
Splitting by salaries is interesting, adds an additional twist on top of the generical cooperative game set up.
It would certainly be unfair monetarily to the person with the shortest journey but if I was out with two people and we knew the longest trip would cost 30 I'd definitely prefer splitting it closer to 10, 10, 10 than 2, 5, 23. (7, 9, 14 maybe?) It costs the first person more but considering how much more the last person pays I'd happily chip in to help them out
Perhaps this is yet another example in which game theory doesn't work on how people actually behave... By the time you show this video to your friends, all of them have already got home!... so, I am not sure what's the lesson here: maybe, only befriend mathematicians? no, that sounds like terrible advice 🙃
@@academyofuselessideasthe idea is to study a small, inconsequential case to extend it to larger applications where it is important. For instance, maybe multiple independent groups working on a project together, where the project benefits each group unequally.
@@iCarus_A Pretty good point! Indeed, we simplify problems and look for analogous problems in the hopes of improving our understanding... The point is that I was trying to make is that sometimes we confuse the map for the territory, or we apply a theory incorrectly to real life scenarios. In many practical scenarios people do not behave as game theory predicts (which is what my comment was about). This is in part because one of the biggest hypothesis of plenty of game theory is the existence of an observable linear utility function that agents want to maximize (a so called homo-economicus). For example, here we assume that people want to optimize for the money they spend while not annoying their friends. But in practice, when. humans are faced with problems like this one, humans do not perform all those calculations. We rely on heuristics that are not too trivial to model. However, I agree that knowing the theory can guide decisions in more complex situations, once you explain the whole reasoning to all the participants.
Thanks for sharing your insight and for including me in the conversation! This is interesting to think about!
You forgot the 5th very important axiom:
The maths must be doable in the back of a taxi after you've had a few drinks
I would love a variation to this problem where the actual journey is formed by destinations that increase each other’s total cost. So, for example, let us say the total cost for journey 3 is 30 but when player 2 gets in is goes up to 35 and with player 1 to 40. So, each additional journey increases the next journeys (making the first journey the same price but the next one more expensive)
Oh damn, I just intuition'd my way to the problem.
The first thing I thought (I paused the video) was the 1st case, but then I thought ("hey, this isnt very good for the first one") so then I thought ("what if we take the average over the intersecting paths?")
For intersecting paths, I mean the points where they share, say, B has to pay 18 when he is alone, since no one else should pay for that.
For formalizing a bit, lets say:
For x in [12,30], Average(B)=(30-12)=18
Then, for x in [6,12], Average(B+L) = (12-6)=6, and because L= B for their shared travel, we get B,L=3
For x in [0,6], Avg(N+L+B)=6 and N=L=B implies B=2
So,we get N=2 for all x
L=2+3=5, for all x
B = 2+3+18=23, for all x
Which, is neat that there's an actual analytical way to do this, really shows that math is just rigurous intuition...
Edit: Just watched the full video... Damn I felt special for a moment :(
Using Nash as an example taxi passenger is cold af lol
Wish you uploaded more often. Literally every video you post is a winner for me. Love your content.
Working on it lol!
But hey, that's just a theory, a game theory
Thanks for teaching me advanced calculus and linear algebra
My initial thought was exactly that final explanation you gave of the Chapley value. Another way to look at it is that each person pays exactly for their proportion of the total people-distance driven, meaning the sum of the distances each person rides. First person pays 6/(6+12+30), second person pays 12/(6+12+30) and the final person pays 30/(6+12+30).
This is a much more elegant and simple way (imo) of calculating the proportion of the cost each person is responsible for, than creating a large table of permutations, summing rows, then finding the proportion of the sums.
I like giving everyone a consistent discount. The combined bill of 30 is 37.5% less than the individual bills of 48.
3.75, 7.50, and 18.75, doesn’t do the linearity axiom, but does give each individual a 37.5% discount, sums to 30, is closer to equity, and still incentives every player to be added to the coalition regardless of order.
You live farthest from the city, don’t you?
@@brandonhumphrey5085 Nope. I live in the city.
@mkj1887 I believe it is a coincidence. It arises from the given values 6, 12, and 30. 1 - 30/(6+12+30) = 0.375. If you had different values, that discount number would be different.
First stop cost $6 and all 3 were in cab. So each pays $2
Second stop costs additional $6 but only B & S were in cab, so each pays $3
Third stop cost additional $18 but only B was in the cab, so he pays $18
Add that up and you get N= $2, S = $5 and B = $23.
I don't get the idea of complicating this. Maybe Shapley values make sense in some other situation.
I show that this IS the Shapley value at the end. Part of the point is that as examples get more complicated than this toy example, we need a more procedural method that applies generally
What if the costs are ambiguous? Imagine B and C living the same distance away from A. So, we could either drive to B or C as second base and this will impact their marginal costs. Do we just permute across all paths also and take the average across these? This idea kind of also applies for all scenarios in which A, B, and C don't live in a straight line.
Similarly, imagine B lives in a different direction from C, increasing the segment length BC compared to AC. Could such a scenario lead to a case where C would not want B to join? (Because C would pay more for ABC than for AC but still less than going all the way alone)
It seems like this would be the case where the Shapley algorithm is even more valuable, since you can’t do the intuitive “first leg split three ways, second two, etc.” algorithm. Instead, you can actually figure out the relative contribution of each participant in a way that also accounts for the differing total costs. It would be interesting to explore that possibility more.
@@PaulFisher Yes but I'm wondering if 1) this might create paradoxical scenarios in which one player has to pay more than going all by their own and 2) if permuting the path would already count as a violation of efficiency since we would consider ways which are longer and thus more expensive than the shortest route.
@@spressi For #2, when permuting the order of additions, you would still want to rank the best-possible route for any given group (i.e. the group of people is considered as a set, not as an ordered list; no matter the order in which people are added, the total value is the same). This is the same as what we already do for the all-three-in-a-line case: when considering Farthest vs. Farthest + Nearest, we still visit Nearest, then Farthest.
I came to the same amounts to be paid but in a different way of thinking: you just split the cost of each part of the journey that you are there for. For the first $6 part of the journey, all 3 are benefiting, so each person pays $6/3=$2. For the second $6 leg of the journey, there are only 2 people left so each person would pay $6/2=$3. Then for the last leg, there is only one person so they would pay the full remaining $18. In total, the first person paid $2, the second paid $2+$3=$5, and the third paid $2+$3+$18=$23 (and the total amount being paid is the total paid by each person: $2+$2+$2+$3+$3+$18=$30). This also removes the need to think of who got there first.
I like my simple way of thinking, but very nice putting that all into specific mathematical definitions, as well as proving that it is the best way.
edit: ok nevermind, I clicked play and immediately the next thing you said was precisely that lmao
Great explanation! It's nice to see game theory in an scenario that doesn't end up with society collapsing due to a series of "tragedy of the commons"!
There's a whole theory of market design that aims to design markets with societally beneficial equilibria.
Meanwhile in reality the commons were going quite well until the king privatized the land
@@godowskygodowsky1155Well, in market design you often want to avoid people forming coalitions, ie cartels. You want people to outbid each other.
We forgot to add a nice tip for the driver. After all, he's arguably being denied $18 of income, and he has to listen to three math nerds arguing in the back of his cab while he does it. 😂
Seems obvious to me, blue pays the full fare because he's a cool guy.
Alternatively, they split the travel per meter between all current passengers, so up to blue's house, each meter is divided by 3, and blue gets out paying 2.
Then there are two passengers to pink's house, so those meters get halved, and pink gets out paying 5. Then yellow pays the remainder of his journey alone for a total of 23.
Good to know my intuitive thought based on how many people were in the taxi at any given time matches the maths version.
Before i actually hear the solutions my thought is ear person pays 1/x multiplied by the amount of each leg where x is the number of people in the car for that leg. So the first $6 leg would be $2 per rider. The 2nd $6 leg would be $3 per rider, and the 3rd person pays the remainder.
Edit: this ended up being equal to the chapley value lmao
Friend: "So to split up this bill, we're going to use game theory"
Me: "I'll pay the bill if you never mention game theory again and I can just go home to bed"
I was thinking more about dividing it in proportion of what every single person has to pay relatively to what they would have to pay in total if they rode separately
and I also realised that there is a hidden assumption in this, and its that they all travel along the same road regardless of how many people there are but thats most porbably not the case
the nearest person will always have the same route so anything they pay less is their gain anyways but the total cost may increase for other people compared to their individual optimal route, which should be included in this calculation
for example if bazett would pay $25 if he traveled alone he only gains $2 in this scenario for traveling the longer route while the nash only pays 1/3 of the cost he'd have to pay anyways to get home
put that way this doesn't seem as fair as it's made out to be, maybe each gaining the same percentage on the travel could be better
You can see more obviously why Same Percentage doesn't work if you use larger numbers.
Suppose X & Y are going to the same place that has a $30 fare. "Obviously" (by symmetry), they'd each pay $15, which the Shapley and "same percentage" approaches both get.
Now Z shows up and asks to get in the taxi. Z wants to go much further, so their alone fare is $840. What happens with both of the approaches?
Shapley says X=$10, Y=$10, Z=$820. That's great -- X & Y are happy to pay less than they were when it was just the two of them, and Z is happy because it's costing less than it would alone.
The "same percentage" approach, though, say X=$28, Y=$28, Z=$784. If Z were to propose that solution, X&Y would tell Z to go away, since they're not going to pay *more* to split the fare with an additional person.
To abstract that a bit, you can think of it like an "induction" fairness, in a way. What's the base case here? You're the only person in the taxi, and you have to pay the full fare. And thus the same applies if you're the only one who cares about a portion of the trip -- your total cost can't be less than the incremental cost for the part of the trip that only you care about.
That's why the solution where Z pays less than 810 is unfair, and thus why the Same Percentage approach is flawed.
@@pfeilspitze this only proves that the algorithm I made off the top of my head for an example isn't very good either
and my main point still remains the potential alternative costs which don't exist in here
@@89alcatraz89 Sure, but it also shows that there's a need for *some* axiom in addition to the first three. So maybe you could suggest one of those.
I might go for a "I'll take my ball and go home" axiom: if there's any subset who would pay less by getting a second taxi than by sharing the first taxi, it's not a good solution since those people won't agree to play the game (in the game theory sense) if that happens. What do you think of that one? (Assuming we're still in the "taxi goes in one direction in a straight line" mode of the original video problem, and thus we don't need to worry about the TSP issues.)
@@pfeilspitze I didnt pay that much attention to axioms but now that I've looked back on it the linearity is there just to look nice and the symmetry is much less restrictive than I though it was, it's basically unbreakable if the algorithm is a state function and even if its not would probably still be hard to break
that being said your proposal does seem to capture the idea of alternative cost pretty well but it basically doesn't occur without alternative paths
though I may be focusing too much on this particular example for having very obvious additional variables in it not just a single one that this was initially made for
me drunk:
believe me, it will make sense tomorrow when you're sober and I explain it to you
My initial guess would have been:
1. Sum up each separate bill - 6+12+30=48
2. Multiply the total bill with the fraction for each person - 30×6/48 or 30×12/48 or 30×30/48
I can't make sense out of it but it seems fair to me and I don't see how it violates any of the axioms.
It violates linearity
You know this comment is a requirement now
But hay that's just a theory, A GAME THEORY
This looks pretty cool! My instinctive way would have been to add up all the values and pay in proportion, so in this case:
6 + 12 +30 = 48, then 30/48 = 0.625
Now the first one should pay 6 * 0.625 = 3.25, and the other two should pay 7.5 and 18.75
I'm not sure which of the axioms this breaks. This should respect at least the first three, so I guess linearity?
I had exactly the same idea
It breaks linearity yes.
For example, if you have:
-> 2, 4 and 6 for the first stage
-> 3, 3 and 3 for the second stage
With the proportion approach, they pay:
-> 1, 2 and 3 for the first stage
-> 1, 1 and 1 for the second stage
-> 2, 3 and 4 in total
But if you consider the stage with 5, 7, 9 (sum of both stages) and apply the proportion approach, you pay:
5/21*9 = 15/7, 7/21*9=3 and 9/21*9=27/7 which is different from 2,3 and 4
One thought I have is that if a fourth person has a $1000 fare, then everyone paying roughly 95% of their fare is a bad deal for the first three, compared to the system that felt good with the three original amounts. It's mutually beneficial compared to no sharing, but they have no incentive for going from three to four.
I feel like monotonicity could be an alternate axiom: the payment for one rider should never increase when you enlarge the pool. This is probably a consequence of the other axioms, but probably not equivalent. Monotonicity by itself allows that the $1000 person could offer each of the first three an extra penny against what they were paying before, and they would be contributing $29.97 to his fare, while he gives them each a penny.
@@mtaur4113 Ah, yea, the limit case actually makes sense.
My solution was the final explanation of breaking up the segments. It's really cool to see that this concept generalizes this way! I wish the video touched on how we can use the less intuitive Shapely value for a less intuitive setup.
I think everyone shoud divide equally the ammount for every sector between the people in the cab during that sector, first 6 is 2$ each, second sector is 3$ each for the 2 people in the cab and last sector 18$ is payed comepletely by the only person remaining so the totals are 2, 5, and 23
It's so funny to see Shapley values outside of work! I've been working on a quantum speedup for approximating Shapley values for a year and a half now!
Oh woah cool!
The second way is n squared log n, if they are not already sorted. What kind of speedup are you able to get?
I remember in a graduate CS class, a major part of the semester was studying Dijkstra's algorithm for finding the Nth element, to understand how it can possibly be O(n).
@@JohnDlugosz Are you wondering how you'd get a speedup searching a graph using a quantum computer? That would probably involve either amplitude amplification or maybe some Markov chains depending on the exact thing you're trying to do.
For my work I'm leveraging an algorithm called "quantum speedup for Monte Carlo methods" to get an approximation of Shapley values with a square root fewer applications of the value function.
If you're interested I have a (relatively) accessible seminar up on RUclips:
ruclips.net/video/qytXmZGA9-U/видео.htmlsi=gmDtuxuLwBDmhunv
My initial thought was that they should each receive the same percentage savings on their journey. For the example given in the video, this means that you divide the total cost of the journey by the sum of the costs of them each taking their own taxi, i.e. $30/$48 = 5/8. Then you multiply this number by the cost of each of their journeys, so they each get a discount of 3/8 on what they would have spent if they didn’t share a taxi. This follows the first three axioms but breaks the last axiom.
After watching this video, I realised that I still think that my method works better, because I disagree with the fourth axiom. In the video you sort of skip over what the fourth axiom means, but I think once explained it would be more controversial than the video suggests.
There's always one axiom that isn't as trivial or intuitive as the others, and it inevitably knocks out what are otherwise perfectly good solutions.
The argument of linearity does not include the social background and is just game theory where you pick passengers out of a possible pool of passengers that HAVE to take a taxi.
This leaves out other factors such as the question whether public transport is an option for anyone/everyone and MOST IMPORTANTLY if the guy living the furthest away would even come to your next party if the brat living closest seems to benefit way more on a percent basis even though he already pays the lowest fee.
I think the way to accept the Linearity axiom is to add a 4th passenger, Jerk, whose alone taxi fare is $1000000.
Using the approach in the video, you get N=6/4=1.5, S=6/4+6/3=3.5, B=6/4+6/3+18/2=12.5, and J=6/4+6/3+18/2+999970=999982.5.
If instead you give everyone the same percentage savings on the journey -- it's about a 0.05% discount -- then you get N≈5.9997, S≈11.9994, B≈29.999, J≈999952. And now J has somehow saved more money than the entire price for N+S+B to get home! That's pretty weird.
Don't think of it as "a bunch of friends who might be willing to subsidize the furthest one", rather something like "a group of strangers going home from the airport", where it's just cold game theory.
Said otherwise, the axiom is "you can't get in the cab if it you joining makes it *more* expensive for everyone already in the cab".
A fair way to divide the cost, taking into account the reroutes the taxi had to take for the last 2 stops would be:
1. To calculate how much it would have cost for each person to take a separate taxi.
Person 1 would have paid a.
Person 2 would have paid b.
Person 3 would have paid c.
Adding all of them together gives us the total cost if each person took a separate taxi= a+b+c.
2. Calculate the percentage equivalence of what was actually paid. In this case, the total cost was $30:
(30x100)/(a+b+c)=X
3. Multiply the individual values that each person would have paid had they taken separate taxis by X%:
a*X%
b*X%
c*X%
With this, each person is still paying less than what they would have paid alone, and the burdens of the reroutes are divided proporcionally.
You don't need these calculations. Just decrease the price with the same percentage. If the first guy pays 6, the second 12 and the third 30 on their own, the total payment would be 48 but they can share the ride so each will pay 30/48 of their cost that is 62.5% and they'll all have 37.5% discount on their ride. Fair enough.
I have see a ton of videos related to shapely values and didn't make much sense. This is the best example!!
Thanks for the video!!
I have an alternative:
Counting the total distance traveled in a different way, A travels 6 B travels 12 and C travels 30, add that all up and you have a total amount of value generated from the taxi of 48. So you want to find what proportion of the value is used by each member so that's:
A=6/48=1/8
B=12/48=2/8
C=30/48=5/8
So you divide the cost by 8 (3.75) so the amount paid should be as follows:
A=$3.75
B=$7.50
C=$18.75
Axioms:
Efficiency:✓
Symmetry:✓
Null Player:✓
Linearity:✓
Part of why I like this solution is because it's works better when it's not a perfectly straight path as well. So if it's not a straight line but still more efficient or somehow preferred to carpool like this then there is no go reason that B or C should pay an equal portion of the first leg of the journey.
I believe my solution satisfies all of these but I'm not firm on it, I would LOVE others' inputs :3
This is great, but it actually does violate linearity (imagine multiple stages to this taxi “game”). When not considering linearity there are many good options like this one.
@@DrTrefor I'm not sure I understand what you mean how would this break down with additional stages?
my three most favorite solutions to this problem:
1. everyone pays weighted by mileage over total covered miles for all persons: a = 6/48*30 = 3.75; b = 12/48*30 = 7.5; c = 30/48*30 = 18.75
2. the video's approach, shapley value a = 2; b =5; c = 23
3. lets say everyone throws the money they would have paid for their own segment into a bowl and leftovers get distributed equally: a = 6 - 1/3*18 = 0; b = 12 - 1/3*18 = 6; c = 30 - 1/3*18 = 24
(i like the third approach, it's super simple. but it's possible to receive money even after paying for the taxi (e.g. a travels 1 mile, b travels 10, c 100; a would come out with +2.67 $ ^^; b = -6.33; c = -96.33) guess he gets paid for his company ^^)
An interesting further thought is to consider the effect of a more direct route to the third house, so that if not making the detour, the cost would have been only 24. The existence of this more direct route means the third guy pays a bit less, and the other two pay a bit more to compensate for the inconvenience of having him make a detour...
Hmm. These three riders are going to annoy their driver if they don't recompute with tip included!
The "alternative perspective" is pretty straight forward but doesn't generalize as has been pointed out.
It would have been interesting to see an example where the taxi route is prolonged by the people who live closer by i.e. the person living furthest away would have to pay 30$ alone but the cost for the whole ride is 40$ because they don't all live "on a straight line".
Then we would additionally have the problem of figuring out the cheapest route (meaning the total price) and whether subsets (meaning taking multiple taxis) would be cheaper overall or at least for all people within one subset (a subset could even contain just one person who would save money riding alone). And even then we wouldn't have considered the "currency" of time as riding alone is always the (one of the equally) fastest route(s).
This video is definitely a great introduction to a field of study. Thanks.
For me it was just:
First leg: $6 / 3 = $2 each
Second leg: $6 / 2 = $3 both
Third leg: $18 = for Bazett
Thus, 2, 5 (2+3), 23 (2+5+18)….
Makes it easier to visualize haha.
Which is exactly the end of the video, don’t comment before watching all the way through 😅
haha ya I think this is the most intuitive answer, but nice to know it is also provably the only fair way (according to the axioms)
This is what I was thinking.
0:48 whoops, I reflexively thought Shapley's first name would be Gale :D
I dkirectly takled the question as presented in the last "alternative perspective" section of the video. I'm glad to see that my intuition was aligned with the Shapley value.
Sharing the cost for each leg of the ride equally between the people actually in the taxi at that time was my first intuition. Seems a bit odd that someone would get a Nobel price for something so trivial that many people here in the comments just thought of immediately. I'm guessing the rigorous proof of it being the unique solution to all the fairness axioms was Shapley's real contribution to economics?
Either way, I would have been much more interested in a practical answer to the proposed problem, rather than such an idealized solution to a rather contrived special case. In real life scenarios, taxi fares are slightly more complex, and the stops for all passengers would not be placed along the shortest route to the final destination. For instance, there is generally a basic fee (sometimes called a _dispatch_ or _flag drop_ fee) that you could argue should be spit equally between all passengers. There is sometimes an extra fee per passenger in the car, or per stop along the route. But more importantly, how would you accurately compensate for the fact that every passenger except the first would be forced to endure varying amounts of detour?
It is easy enough to make reasonable approximations, if you know all the variables and given enough time to do the maths. Like estimating the cost for each person if they took a taxi home by themselves, and establishing a ratio that way. But real life is messy and full of unknowns, and it might be hard to do reasonable approximations on the spot. How should a typical group of friends _practically_ calculate an adequately fair split in a real world scenario?
What is wrong with just sharing it proportionally? So $30 is the total, but the prices if they would be alone added up would be $48. So they first person pays (6/48)×30, the second person pays (12/48)×30 and the third person pays (30/48)×30. This way everyone pays proportionally with the price it would have normally been, just with a discount of a factor of 30/48.
Wow this went way beyond my capabilities. However I did arrive at precisely the same value, the "alternative" perspective is what came to mind.
13:29 . How do you make that uniqueness claim ? Like Is there formal ptoof?
Other methods like total precent off also satisfy the four fairness axioms. ( Total precent off method is multiply each person individual cost by discount% = #total cost together/ # total cost individually )
. With the numbers the pay is 3.75 , 7.5 ,18.75
If its a pragmatic, real world solution we want, then we absolutely have to factor in that you don't generally pay taxis up front. You also should consider the scarcity of taxis available at the time, which was my immediate response to "why would any of the individuals agree to the coalition in the first place".
Anybody who has stayed late at a party or something knows the pain of trying to organise 10 trips when only 3 taxis are available. People suddenly don't care about proportionality and discounts.
I guess I see a certain logic to the way of dividing this that was rejected at the outset, but it only makes sense if they're actually friends. Nash may not really gain any benefit from sharing the ride with the two others, but he also doesn't really lose anything if they get to start their trip from Nash's house rather than from the starting location, which would be effectively what he's letting them do by riding with him. Shapley in turn really doesn't lose anything from letting Bazett start his trip from that house rather than from the starting point. The other thing to consider is that Bazett is in the absolute worst situation, having to pay $30 to return home. So it's not really shocking that the other two, with bills of only $6, might not want to make things even harder on Bazett than they are already going to be, given that he's the one stuck making such a long trip home in a taxi. I can definitely see how it might be unfair if they're strangers, but I don't think I would want to treat a friend like that and insist on them ensuring a benefit to me for letting them take advantage of what, for me, is already a sunk cost. Especially if it saves them something like $12 on a $30 trip. That is to say, even though you mathematically proved to me that this is the fairest outcome, I don't think saddling the third guy with a bill that close to what he would have paid on his own seems like a very friendly thing to do... a good way of handling bills among strangers, but I feel like it's not taking into account that friends generally don't mind doing things for each other that come at little or no expense to themselves. I guess the other thing the Math isn't necessarily taking into account is that Bazett probably travelled a long way from home to go to an event with those two friends, and while knowing he would have a long trip back. So there's sort of an inequality there in that one of them had to travel a lot farther to and from that would likely weigh on people's assessment. On the one hand, yes the $23 is Mathematically fair, but on the other hand, do they really want Bazett's bill to be so high that he starts reconsidering going to events that are futher from his house, or maybe even start trying to push for future meetups to be more equally located between the houses to lower his own bills in the future? There's something to be said for trying to keep his bill under $20, because that makes it feel like less psychologically, while also not going too far to the point that it seems like they're pitying him, which is what offering to split the bill three ways might make him feel like.
Depends how drunk each person is and if you’re going to deep it that much, get your own taxi!!
I don't think this is a good example to demonstrate the Shapley value, because it's an oversimplification. It assumes that all 3 houses are exactly along the same path.
In this trivial case, the intuitive approach you mentioned at the end makes the Shapley-value feel overly complex.
But, if you consider a case where not everyone lives on the same route but it's still worth it for the players: there the intuitive answer falls apart, but the Shapley value works fine.
I actually agree, seeing the comments of people guessing the intuitive approach makes me wish I started with that, then made the houses not colinear, and then showed Shapley value could deal with that more complicated case
@@DrTrefor It's often hard to know in advance, what's easier to understand to other people. Oh well.
Similar to other comments, my first thought was each person should share the discount proportionally. Since it would cost $48 if they each take a taxi separately, but only cost $30 working together, the savings is 37.5%. So we could simply reduce each person's cost by that amount and you would get $3.75, $7.50, and $18.75 respectively. However, this "solution" does not consider that sharing your space in the taxi is part of the problem. During the first part of the trip, all 3 people must cram in there with very little room. That first leg being so unpleasant, this explains why Nash gets the best deal overall and only pays $2 rather than $3.75. During the 2nd leg of the trip, at least it's a bit more comfortable for each person. And on the last leg, the final person has all of the "perks" like music selection, temperament control, stretch out across the full length of the back seat, etc. I'll concede. My initial "solution" was suboptimal.
My initial idea was that everyone pays proportional to the distance they traveled.
I see 2 ways to argue fairness. One is comparing to the contribution. The other is calculating the average savings vs nonparticipation. If each person rode a separate taxi, the total group cost would be $48. Participating, the group cost is $30, which is a 37.5% savings. Splitting this evenly, the first person (the $6 trip) would pay $3.75. The second person (the $12 trip) would pay $7. And finally, the last person (the $30 trip) would pay $18.75. Each person gets an equal percentage discount off of their trip cost versus their alternative (nonparticipation). This does give a larger actual dollar discount to the longer participants, but those people are also paying an additional cost, namely, the extra time stopped while previous occupants get out and get any belongings. By approaching fairness from the philosophy that the savings vs the alternative, as a percentage, should be equal, we can reach a fair answer that equalizes benefits related to the savings garnered by the group.
This assumes that everyone's house is perfectly on route to each other's house. What if Shapley's house is far enough out of the way that going via his house increases the total by the time you get to your own by $5? I.e. if you went to your own house by yourself the total cost would've been $30, but if you got in the shared taxi, the total value would've been $35
In my experience hotel room sharing at a convention follows the Shapley model. 2 people share a room for 2 nights pre--convention. 3 share the room for the 3 nights of the convention and post convention 1 person stays alone for another couple of nights to do some sightseeing. Room cost is borne in full by person in room alone, shared between 2 when 2 occupy the room and split 3 ways when occupied by 3.
This is a great worked example of a complex idea. That there is a simpler "intuitive" answer to this particular case does not mean that the theorem is "over-engineered". However, it's distracting though that Dr Bazett never mentions this intuitive answer which must have been on many viewers' minds for most of the video. (Basically dividing up the journey into three segments, and allocating the cost of each segment across those in the taxi at the time.) Then this can be aligned to the theorem by saying (1) the division into 3 segments is just the application of the linearity principle (2) those in the taxi for a segment don't pay (null principle) (3) everyone in the taxi for a segment pays the same (symmetry) (4) the total must add up to #30 (efficiency). It would then be great to give (without detailed solution) a real-world example of a much more difficult problem which Shapley handles but for which there is no immediately intuitive solution.
This was really interesting to watch for me since the "alternate perspective" on the solution was my immediate instinctive reaction to how this should be solved.
The alternative perspective is very helpful, that's so much easier to visualize and calculate than the table
Nice video, I'd love a follow up where people live in quite and not so quite different directions
When I saw the liniarity axiom, I immediately thought of to treating it as 3 separate "journeys". First "journey" is to Nash's house, which costs $6, and there are 3 people in the taxi, so nash should pay $6/3 = $2. In the second "journey", we are going from the Nash's house to Shapley's house, which would cost $6, and there are two persons in the taxi, so Shapley shoud pay $2 + $6/2 = $5. And the last "journey" is Bazett by himself, so he should pay $5 + $18 = $23.
This method is kinda different, but yelds the same result, easier to calculate, and more intuitive in my opinion.
Nevermind, reading other comments and watching video till the end is not my strong side
My intuition is to equalize the percentage discount.
The total bill to take the trips separately would be $48. We only have to pay 62.5% of that, so each person pays that fraction of their orginal cost. $3.75, $7.50, $18.75
visually you could simply split vertically each part on the number of people present during that part. (1/3 for each x 6, then 1/2 x 6, then 1 x 18). give the answer quick with less general formula tough
Always a good day when you upload
You're the best!
Far easier way to get same answer:
Segment 1 had 3 people: $6/3=$2 each
Segment 2 had 2 people: $6/2=$3 each
Segment 3 had 1 person: $18
Nash pays $2, Shapley pays 2+3=$5, and Bazett pays 2+3+18=$23. Same answer just way simpler method
Looks like I should have just watched to the end first haha
I'm glad to say i understood it from the alternate perspective without starting the video and got itt. Didn't know that the Shapley value would be the same as mine
Another look at it, for each segment divide the contribution by how many plays, add that to each player's total payment, continue doing that for all segments, what you end up with is the same result. So in this case the first segment has 3 players with a contribution of (6 - 0 = 6), and so (6 / 3 = 2), total is now (2,2,2), then for the second segment there are 2 players with the same contribution so (6 / 2 = 3), total is now (2,5,5) and lastly the last segment only has one player with a contribution of 18 so the end total is (2,5,23)
This method actually came to mind first when the question was initially asked.
Edit: apparently this method was spoken about at the very end of the video xD
Easy: You divide the 6$ by 3, so each pays 2$. Then you divide the other 6$ by 2 so the 2nd and 3rd person pay 3$ and lastly the last person pays the remaining 18$. That means that: the 1st person pays 2$, the second pays 5$ and the third pays 23$.
Oh I finished the video and that's the exact solution. Wow I'm a genius
I'm not familiar with the taxi system where you are, but here (Scotland) they have an upfront cost (like £2 just for getting into the taxi) then I think they add an amount based on how many people are in the taxi (say £1 per additional person). So if individual distances cost {4,4,12} then C(N)=6, but for N+S the meter has reached 7 when they pass N's place, and hits 11 at S's place, and finally C(N,S,B) would read {8,12,24} as it passed N,S, and B.
So, splitting the bill has become considerably more complex! But as long as N pays less than S pays less than B, who pays less than a single trip, then it's probably all good.
We could actually build in any of these computations into the marginal price computations and get a new Shapley value.
Cool video and presentation!
I feel like numerous real world spliting situations are ones I don't particularly think symmetry axiom is a fair assumption. For example, if you see taxes as a cost dividing endevor (which I don't but lots of people do) I don't think this axiom will lead us to a fair taxation scheme. And the point is that symmetry seems to assume something to look fair, something in the direction of "every player has the same starting conditions for paying costs"
Realistically the guys furthest away is gonna take detours to be able to drop the others off. So you should distract some.
I haven't watched the entire video yet so maybe you'll mention this too, but instead of averaging the permutations I just split the bill according to who was in the car in each section(and got the same result)
In the first part, 3 people were taking the cab, and the journey cost 6 dollars so they each pay 2$.
Since N's journey ends there, that's the total amount they're gonna pay.
In the next section of the way, 2 people need to share the fee for a journey that costs 6$, so now they each need to add 3$ to the 2$ they already owe for the first section, leaving them both to pay 5$.
Since S's journey ends here, they pay 5$.
Finally, one person has to go for another journey that costs 18$ so they just pay the 18$.
Making the final result:
N pays 2$
S pays 2$+3$=5$
B pays 2$+3$+18$=23$
Edit: yap, you mentioned this exact approach in 14:35
My initial thought without mathing jt as if you were actually talking to friends about how to do it before it happened was the first person wants to save some money so maybe $2 savings so cost of $4. 2nd person is same way so want to take a couple bucks off. Would also be okay with $2 but maybe $3-4 off of 12. 3rd person is still happy they dont have to pay 30. So now they are paying between 26-24. That's without trying to even do basic math. I think i was oretty close
My first instinct was the same as the top comment: divide the payment per person for each part of the trip. What's interesting is that it comes to the same values and seemingly follows the same axioms, suggesting that the method may actually be the same. So, I want to try to test that.
One way to test it is exploring how the permutations change depending on the number of people and their 'order' in which they leave the equation (get off the taxi).
Exploring the case of 3 people (N=3): Permutations = 3! = 6 = 2N
According to my original instinct:
The first person (P1) should pay the cost of the first part (C1) divided by N
P1 = C1/N
The second person should pay what P1 pays, plus the remaining change (delta or d) to get to C2 divided by N-1 (because there is 1 less person paying)
P2 = C1/N + dC2/(N-1)
The third person should pay what P2 pays plus dC3 (which is technically divided by N-2 for if this formula is needed for any number of N)
P3 = C1/N + dC2/(N-1) + dC3/(N-2)
According to game theory:
P1: In 2 permutations, they pay C1
2*C1 / 2N = C1/N
P1 = C1/N
Therefore, for P1, the two designs are equal for N=3
P2: They pay 1*C1 and 2*C2
C2 = C1 + change to get to C2 (deltaC2 or dC2)
1*C1 + 2*C2 = 3*C1 + 2*dC2
(3*C1 + 2*dC2) / 2N = (3/2*C1 + dC2) / N
To make the two models for P2 equal (and inserting N=3 because it is required for these formulas to exist):
P2 = (3/2*C1 + dC2) / 3
P2 = C1/3 + dC2/(3-1)
= 1/3*C1 + 1/2*dC2
1/3*C1 + 1/2*dC2 = 1/2*C1 + 1/3*dC2
1/3*C1 - 1/2*C1 = 1/3*dC2 - 1/2*dC2
(1/3 - 1/2)*C1 = (1/3 - 1/2)*dC2
C1 = dC2
Therefore, assuming I did none of my maths wrong, the 'game theory' formula and the 'separate parts' formula only match when dC2 = C1, or when the distance between the original location and the first house is the same as the distance from the first house to the second house.
Testing my maths using the game theory formula for P2 (C1=6 and dC2=6):
P2 = (3/2*C1 + dC2) / N
= (3/2x6 + 6) / 3
= (9+6)/3
= 5
Testing the same using the separate parts formula for P2:
P2 = C1/N + dC2/(N-1)
= 6/3 + 6/(3-1)
= 2 + 3
= 5
Testing game theory for C1=6, dC2=8:
P2 = (3/2x6 + 8) / 3
= (9+8)/3
= 17/3
~= 7.667
Testing separate parts for the same:
P2 = 6/3 + 8/(3-1)
= 2 + 4
= 6
6 ≠ 17/3
Therefore, because the two methods differed in answer when C1≠dC2, it is reasonable to say that I did not do my maths wrong and the two methods only coincidentally equalled in the video's specific scenario because C1=dC2.
Also, yes, I did try to equate the two formulas without making N=3, but it became a very complicated problem involving numerous powers of N, so I decided to simplify it by inserting the known value instead.
You've described P2's marginal contributions wrong and imposed the result. P2 does NOT pay C1 in the permutation. P2 pays dC2 in that permutation (and 2 C2s in other permutations, as you wrote it out). By writing it as C1, you've implicitly imposed the condition that C1=dC2.
Idk how I figured out the answer before he finished explaining it, but I did. If you look at it, the first person is slitting his bill with 3 people, 2 people are splitting it in the second and 1 in the last
I usually do the following: We see how much each person would pay if we were not sharing. Sum everyones value, and calculate the total discount of going together. In this case, 6+12+30 = 48, but we are paying 30 with the discount. This means aprox. 30% of discount. Apply 30% of discount to each value in the sum: 6x(0,7) ; 12x(0,7) ; 30x(0,7). Everyone gets the same percentage of discount, which seems fair.
A lot of people seem to be suggesting a problem based on where the houses are located, but like, if the houses were lined up in such a way that the route would be too complicated, it's unlikely they'd take the same taxi - since they'd know this already. So we can assume the houses are relatively "linearly" far from the origin, and the route will be more or less optimized.
So much math, and I think we forgot to tip the driver...
With just hering the problem and didn't watch the solution yet I would suggest the following:
They drive to the first house toghter so they spitt this cost of 6$ equaly in thirds means everybody pays 2$ for this fist distance.
The the second house they are 2 people so they splitt this amount equaly again but just between the 2 in the car. So both pay additionally 3$.
The rest the last person is driving alone so it pays the total cost of this. In absolute numbers that means:
Nash 2$
Shapley 5$
Bazett 23$
I’m still at 5:00, but I thought it like this:
- A benefits for a trip long 6
- B benefits for a trip long 12
- C benefits for a trip long 30
Now let’s add them up: A+B+C = 48
And we do the proportion:
- For A we have: 6 : 48 = x : 30
- For B we have: 12 : 48 = x : 30
- For C we have: 30 : 48 = x : 30
A pays 3.75
B pays 7.50
C pays 18:75
This way everyone pays in a way that is proportional to the benefit they had from hopping on the taxi.
I think Linearity is really the key to understanding this. Since only B cares about the last segment of the trip, the only fair answer has to be that B will pay at least 18, since they have to cover that part on their own, since N & S have to reason to subsidize the part they don't care about. But they also have to pay *some* part of the cost for the earlier segments too, or as you say, N & S have no reason to let them in the cab at all. Then symmetry means that cost is split evenly when multiple people are using the same segment.
You should also add in flagfall, starting cost for the taxi. Let’s say it’s $3. Each person contributes equally for it . That way it’s slightly cheaper for the 3rd and 2nd person because they have to take stops which slowly decrease from their experience.
It is contained in the first segment.