Click my CoPilot link go.mycopilot.com/UpAndAtom to get a 14-day FREE trial AND 20% off your first month of personalized fitness if you sign up before February 1st!
As computer scientists, our plan is actually to explain theoretical solutions so confusingly that eventually everyone else will give in and let us have the big piece. It's an optimal solution because I get more cake and you get me to shut up.
Meanwhile in real life, Billie wants all the cake, Alex HATES cake but doesn't want Billie to have any. Charlie is completely over all this nonsense, killing his appetite so he tells Alex about Billie's Onlyfans. Now she's begging him not to text her boss the link and crying before throwing the cake in a fit of rage at Charlie, but misses, hitting Doug who was just walking by minding his own business.
@@theaxer3751Actually Ethan then fired Doug for showing up late to the KPI meeting covered in cake, causing his wife Fran, to leave him for his brother George and taking their daughter Hailey with her.
@@evelieningels9408 The real math problem would be proving there's a nonzero chances of there existing three sufficiently rational and intelligent people to all agree to do math to split a cake. But the only thing i really know about people is that they can be reliably counted on to make the worst, most irrational out of left field out of control emotion driven decisions and not for a single second question the logic of their actions.
I think it's a win-win scenario at a party. You cut the cake to obviously favor you. So you either get confronted about it, you say sharing is mathematically difficult and you immediately spot the mathematician in the group - thus avoiding the unnecessary discussions with others, or you're not confronted and you get the bigger slice.
It took me a bit too. It was the closup of the photo at the end that did it. But, until then, I was thinking that was a nice gesture by Mackenzie, acknowledging that he and his wife were a team regardless of her academically recognized contribution to the paper.
Once I was fed up with my daughters complaining about the size of their slice of cake, and the topping. They thought it was all just so unfair. I had enough of that, so I threatened them to put the cake in a blender and pour each of them a glass. I thought it was a great solution since it fixes the disagreement over who would get the chocolate bit, the strawberry bit and so forth. They declined my offer and accepted the slices given instead.
3:00 "This is a huge drawback for anyone with more than one friend." It's bold of you to assume I have more than one friend. As someone who has no friends, the optimal sharing strategy is for me to eat the entire cake myself. 😊
Having watched this twice now I’ve decided to use the tried and tested methods mothers in families have used for years. Don’t let the kids see the other kids pieces of cake😂
My identical twin and I used to share coke for instance, so we used to try to fill two glasses equally to the millimeter level accuracy, until we both were satisfied with the equality.. One drop to this, another two drops to that, and repeat. It sometimes took 20 minutes but who cares! Whatever is spilt onto the table, one of us put thier bare feet on it so that the other could not lick it off the table. so for me, it is fairly understandable why an envy free algorithm is so complicated :)
This reminds me of an argument I had as an 8-year-old with my parents who cut a small cake in two exact halves, one for me and one for my 2 years younger and much physically smaller sister. I complained that equivalence in absolute size of a cake piece was the wrong metric for fairness, but rather "equivalent satisfaction" should be aimed at and thus, my hypothesis was, that the cake should be divided into the ratio of the sizes of our stomachs, which again could be estimated from our body weights. My parents were not impressed with my hubristic mini-essay of neuroscience and mathematics and just told me to zip it and be glad I have any cake, as many kids don't have cake at all, ever. 😅☠
People tend to remember the most traumatic events of their lives. You had a good childhood if that's the thing you remember as being the equivalent to the end of the world.
@@privacyvalued4134 I tend to remember a lot of my life and this is by no means a "traumatic" event, but it's a stupid story about an annoying know-it-all kid (me) just for the sake of entertainment. But you are correct with your conclusion anyway, I was blessed with having wonderful parents and great friends. The only traumas I have are of loss.
If the size of her piece wound up being more than she could eat and, thus, went to waste, I would agree with you. But, if it was just a matter of you wanting more because you were bigger, I don't really think that is applicable. The purpose of the dessert is not to fill your stomach (that's what the main food in the meal is for, so your argument may apply to splitting up a pizza, but not cake). Eating more dessert just means enjoying more of the flavor, in which case size should not inherently entitle you to getting to enjoy more of that flavor. So, in that case, I agree with your parents.
Hannah Fry did a great video on this years ago on Numberphile. Your video is great too and seems a lot more comprehensive. What motivated you to make this one? EDIT: Oh. The wedding photo! That says a lot, lol.
As a teacher/fanatic of discrete math, I love everything that's here. I will admit, this is the one topic in the fair division chapter I skip only because I know how long it can take and resolving the whole envy issue. Divider-Chooser, Lone-Divider, Lone-Chooser, Sealed Bids, Markers, all fine. This is much tougher, but if you're willing to brute force the steps and no one minds the time it takes, then do it and let everyone walk away as happy as possible. But the thing I love most about fair division as a whole is that it brings the whole concept of the value system to light. It spans so many financial, personal and/or political aspects, and you can't just say everyone should be happy with what they get just because of what you perceive to be all pieces being equal fractions of the whole thing. What you value is not the same as what your neighbor values. Excellent video. I'll remember this one for the future.
Nice video. Note: I recall someone defining "fairness" as the condition when all parties are equally dissatisfied. I think that definition might make for an easier solution.😁
@@AstroEli133 I am aware. I was responding with a joke about how frequently mathematicians ignore simple but inexact solutions because they are off by ≈3 atoms in an entire cake.
says you I mean, I know it is more difficult to operate over non continuos land, But it's doable. The real challenge is that land changes, often impredictably, over time
Software engineer here: What if each player is given an incentive perk for having chosen a lesser slice? Like a good samaritan state of "I'll be happy with this smaller division in the sake of moving the algorithm further" Envy-free doesn't always imply equal distribution - lots of people would be happy to take a lesser slice to make another person smile too or for the sake of saving time (efficiency in the algorithm) at a party...'empathetically envy free' could be an alternative final condition to avoid the entire system being hung up in selfishness over ease
I had this issue one thanksgiving. My aunt had a cake with a lot of different toppings and we wanted to find the fairest way to cut the cake. There was 11 of us. Basically we solved the problem by asking which topping each person wanted the most. Those who wanted a particular topping had their topping cut away and they divided that portion among themselves, and so one and so on. The rest of the cake that didn't have toppings were divided amongst everyone.
“Cut and choose… only works for two people, this is a huge drawback for anyone with more than one friend” Ah, so that’s why it took 70 years. What an unrealistic scenario.
mathematicians make problems where there are easy solutions - you just buy more cake than friends can possibly eat, everyone is sated and there's like 1/3 still left 😂😂
@@jackapps2126you don't understand... It does revolve. There were so many wars and battles for the leftover cake. So many victims. And the only goal in this situation is victory, so there is no word such as loss!
What happens if some parts change in value depending of the parts they're paired with? Like a situation in which Matt likes strawberries and blueberries equaly, but hates them together, then if he ends with pieces that contain both, suddenly his cake loses value. Or what would we do in a case in which consecutive pieces are more or less valuable than pieces from different parts of the cake? For example if instead of cake we think about time, someone might think that 10 consecutive minutes of something is worth more (or less) than two separate sessions of five minutes each?
You ignored the REAL elephant in the room, slices with negative value. If we have a pizza and 90% of it has pineapple on it, I only want the slice without pineapple. What if nobody wants the pineapple? do you cut the non-pineapple up into 3 absolutely tiny pieces that nobody will be happy with?
@@Amor_fati.Memento_Mori Its more with the very idea that you should divide it up under those conditions, the 9 slices with pineapple should go in the bin. Also what if one person is a young child, one person is on a diet and one person is a body builder - as in what if they do not actually need the same amount, or what if everyone is starving and there is only enough for half the people. Or better yet - what if the optimal strategy is for the cutter NOT to make "equal slices"? Not only may people collaborate in the cake cutting game to gain more cake, but people may take advantage of what other people prefer. It is actually optimal to cut in a way you know makes everyone else happy but results in them leaving the specific slice you want for yourself - rather than to cut them "equally" The fact that it is not a math game but a MIND GAME means if a person values the piece with strawberries at 1 and everything else at 0, then that person has to keep dividing up strawberries for each person they THINK likes strawberries(just to guarantee maximum strawberries), but then if someone likes strawberries they didn't expect the cutter ends up without a piece, and if someone doesn't like strawberries that the cutter thought liked them, they would have to rely on mr non-strawberries feeling charitable enough to actually give a piece. The fact that so many of these methods rely on someone feeling charitable enough to give a piece away is another problem, because I do not know many people willing to give up part of their cake.
I feel like if I ever got near to spending 50+ years on a formula to cake cutting. At that point I would just take the 50 years green aged cake, stick it in a blender and measure it out in micrograms to each individual person.
This is such a great explanation! Me and a friend were just thinking about this problem a few days ago and this explains every one of our questions amazingly. You also explain the algorithms impressively intuitive
@@suttoncoldfield9318 Maybe she has been on one of those competitive baking programmes. He probably managed to solve the problem from trying to equally divide all of the practice cakes amongst their neighbours. It's insane how varied the show stoppers' toppings can be on a single cake. :)
I would honestly propose to freeze-dry the cake, then pulverize it to a pure protein shake-like powder and then weigh portions with a molecular scale. It's a bit like explaining a joke where the cake dies during the process. In the end I'm usually the one eating both the bigger cuts and eating the scraps anyway.
Except the point of the video is that preference plays a huge role - the people involved do not necessarily want a piece indistinguishable from every other piece; some want more frosting, others want more edge piece, etc
There is ONLY one sensible way to cut a cake (or equally divide anything), the person cutting the cake gets the last piece and because they do not want a small slice they will very carefully make sure all of the slices are the same. 70 years for scientists to figure out a complex version of the common sense my Grandmother taught me... Just goes to show that education and intelligence are often two entirely different things!
@@broccolionswag Then someone would take the bigger slice and you would be left with one of the smaller slices and a lot of unhappy people wanting to know why you gave a large piece away to just one person.
I think I just found a method to reduce the number of cuts needed for envy-free division for any amount of people. To demonstrate my method, I will use 3 people for an example. First Alex cuts the cake into 3 pieces that he thinks are of equal value. Then in case Billie and Charlie want the same piece of cake, Alex cuts Billie, taking her out of the equation. The rest is cut and chose.
I'm trying to think of a point in the division of a more complicated thing like a plot of land in which (a) some persons are not happy with the location of the division, such as through the middle of a town, or (b) some possibility where the cuts made by a large number of persons, especially when swapping pieces, result in non-adjacent pieces... For cake, whether the pieces were originally adjacent doesn't matter, but for other things (like plots of land) they definitely do
What happens in the cut and choose scenario if, for example, the cake has one area with nuts on the top and one area with strawberries, and the cutter cuts it so that both pieces have both nuts and strawberries and the chooser doesn't like (Or worse, is allergic to) nuts? The chooser wouldn't be happy with either bit.
Having part of the cake with 0 personal value, but non-0 perceived value. Pretty much guarantees envy unless the other person greatly favors what you can't eat. At the extreme sharing a meringue with someone who can't eat eggs is ridiculous.
So, first, if someone is allergic to nuts, he/she shouldn't be eating any part of a cake that has nuts anywhere on it; so we can remove that hypothetical pretty easily. Second, the entire point of the cut and choose is that the cutter decides the equal value but doesn't get to choose. It doesn't matter how the chooser would have divided the cake, because that isn't his job. If he wants any part of the cake, he has to choose the part he would be most happy with. I suppose if his dislike of both pieces was so extreme, then it just falls into what I said initially about the person with allergies. This is just a cake the second person doesn't want, so the first person gets all of the cake. Because, if you think about it, the only way you might solve this is to switch jobs and let the second person cut and the first person decide. But, when the second person goes to cut, he will realize that, if he cuts it into pieces that don't hold equal value to him (meaning he cuts it so all the nuts are on one piece and none on the other), then the first person might choose the piece he actually wants. So, to be fair to himself, he would also have to cut it so that there are nuts on both pieces (so, no matter what the first guy chooses, the second guy won't wind up with a piece covered in nuts). That is why the cut and choose method works no matter what order people go in. That's all just relying on the logic, though. Realistically, people can just talk to each other about what they like or don't like to see if they can come to a better agreement before cutting.
I think this is a good example of how envy free isnt exactly the same thing as fair. In this scenario, its still true that both players will be envy free. The cutter is not envious because they believe the peices to be equal value, and the chooser gets to choose whichever peice they think has the larger value, even if the values of those peices are low. Of course, this may not be considered strictly fair by some people (perhaps the fairest solution is give all nuts to the cutter and the chooser gets slightly less cake or something) but it is still definitely envy free.
@@SgtSupaman Not every allergy is life-threatening. I've got a fairly mild allergy, so food that's only _touched_ peanuts won't kill me*, but that doesn't mean I'd feel safe eating a whole peanut-covered slice of cake. (* at least, it's no more likely to than, say, crossing the street.)
Ah, this is the problem with envy freeness. Just because a division is envy free doesn't mean that it's pareto efficient. Being pareto efficient means that there is no way to divide the cake in a differentway such that everyone ends up at least as happy as they were with the current division, and someone ends up happier than they would with the current division. Thankfully, there is a theorem called Weller's theorem guaranteeing the existence a division that is both pareto efficient and envy free, but as far as I know, there has been no progress in creating an algorithm to find this division.
Excellent video as always. In a very sad scenario, Alex purchases candy sprinkles shaped like little ant coats the cake in them. After everyone else decides they don't want a piece of ant covered cake, Alex drops the mic then gleefully eats the whole thing.
This is so well detailed and illustrated to a topic which i always wanted to explore and understand in detail. I watched many videos on this but this is so far the best as it also included the journey and problems in the ideas till the best one we came to know today! Purely AWESOME!
@@shoyuramenoff and the one after that, and the one after that, and the one after that.... until they finally cut the cake from the first one, after it has decomposed and become the compost the ingredients for the next one were grown in :)
My mother’s solution was to have one kid cut the cake, but they would get the last choice of a piece. I think the pieces were perfectly equally sized down to the micrometer.
Perhaps the cake should be modeled digitally first, so all the cuts are just theoretical until the final agreement is come to. Hosting parties just keeps getting more and more complicated.
@@SgtSupaman It is not yet proven that you can always reach an envy-free solution where each slice is continuous. So your idea would definitely *reduce* the crumbiness, but it wouldn't guarantee that we avoid having thousands of pieces.
Misread the title when I first saw it in my sub-box. Thought it said fastest. Spent the last hour or so thinking of different arrangement of cake cutters arranged in frames* for all kinds of different shapes of cakes. Thought it was a bit of a odd topic considering the history here. Fairness will be a more interesting topic though so double thanks!
I usually am fine with less than a fair amount, but preferable not much less. I wonder if there is some mathematically fun stuff that can be used in my case.
Great work! You did it again! Take a hard mathematical subject, and explain it so that it is clear, accessible and a joy to watch. Kudos from a fellow mathematician. (And really nice to see n^^5 in any theorem.)
I remember reading an article about the cake cutting problem in Scientific American about 15-20 years ago. The practical upshot of the residue was to pay the attorneys! Also, Jade at some point in time, "How can I get my wedding photo in a video?" While working on this one, "Eureka!" Also, with a name like "Simon McKenzie," how does he speak French so well?
There is a way to cut a cake into five pieces that waiters and waitresses know about. You cup the cake in six even pieces which is easy, and then you give one slice to each of the five people and then you give the sixth slice to the waiter. 😅 It's a perfect solution
In practice, cut and choose still has the problem that the chooser is likely to get a better than equal piece, but the cutter won't unless he adjusts his cut by whatever he assumes to be the choosers preferences. So there could still be envy for who becomes the chooser.
The cutter splits the cake into 2 pieces that they consider equal, so they'd be happy with either piece without any envy for the other piece. The chooser then chooses whichever piece they prefer and so the cutter is left with the other piece, which they'd already decided was exactly equal, so there is no envy.
@@BenUK1 yeah, but wouldn't you still rather be the chooser? (especially if it is a cake with toppings) Unless your preferences align perfectly, the chooser will get a piece that is better than if they cut the cake honestly. Like in the video when the cutter makes a small piece with strawberries and a big piece without. If the chooser hates strawberries they will gladly take the bigger piece, but if they were to cut the cake into equal pieces themselves they wouldn't have that luxury. (At least not unless they take the risk of cutting strategically instead of honestly)
The cutter doesn’t care about the chooser’s preference. They just cut two pieces that they would be equally happy with. It doesn’t matter if the chooser is more happy with one or the other, by definition, the cutter is equally happy with theirs. The goal isn’t “everybody thinks they have the same value piece”, it is “everybody thinks they got at least their fair share”. There’s no issue with somebody thinking they got the better deal, and, in general, deciding you are less happy because somebody else is more happy is just a horrific way to live.
I think I see what you mean. You are essentially quantifying happiness and then saying that the chooser gets a larger share of the total happiness at the end than the cutter, but the problem itself is only interested in sharing the cake (or whatever the resource being shared is) and the absolute measure of 'happy' or 'not happy'. Both players do end up happy (nobody is actively unhappy), and both players believe they at least both got a fair share of the cake, even if they also believe the other player to have slightly more resultant happiness than them. Trying to get them to all believe they have a fair share of the cake AND a fair share of the total happiness at the end of the sharing would require being able to scientific measure (or mathematically model) happiness in some way, and would be a problem of an order of complexity up from the problem of 'simply' fairly sharing the cake. Another way to explain this away would be that each person has a different opinion or perspective about the value of the pieces (if they didn't it would just be like sharing a pile of money where the total sum of money could just be divided by the number of people sharing it to arrive at an equal amount each). So the chooser may well believe they had a better piece and that the cutter had a worse piece, but the cutter believes that they have a fair piece either way and therefore does not believe they have a worse piece than the chooser. The cutter doesn't care about the chooser's opinion of the choosers piece, they cutter only cares about the cutters opinion of the two pieces. Each person's own opinion of their own piece has to be positive at the end of the share. I guess the fact that the chooser is restricted to choosing one of the two pieces that the cutter cut, whilst the cutter has freedom to make whatever cut they want and create any of the essentially infinite possible pieces, is also something to bear in mind.
@@NitFlickwick it’s true that the cutter will always get their fair share, but if they had instead been the chooser, they’d also get at least their fair share, but they’d also have a chance of getting more cake. That said, if the cutter knows exactly how the chooser measures value, they could take advantage of it by making one piece include just the parts that they like more than the chooser, such that they would like that piece more, but the chooser would just barely prefer the other piece. This is not about how the cutter doesn’t want the chooser to be happier than them, it’s about how the cutter could’ve gotten a better piece while still keeping the other satisfied, but they usually don’t know how. Let’s say we’re cutting a half-vanilla half-chocolate cake, when A loves vanilla and B loves chocolate. If A cuts honestly, they’d cut just over half of the vanilla into one piece, and just under half of the vanilla in the same piece with the whole chocolate. But if B had cut, A could get the entire vanilla part (twice what they’d got), and almost half of the chocolate. Do you see the issue?
This is an excellent demonstration of a big concept in software engineering that is often overlooked by computer scientists. In the real world, you just divvy it into 3 semi-equal pieces and move on with the party. Absolute correctness is often desirable, but not at the cost of expedience, ease of implementation, ease of maintenance, or performance. A pretty good, very fast approximation is very often better (in a practical setting) than a 100% correct, slow and complex solution.
Only if you're in a situation where all participants have equal money at the start and people are okay with having more money in exchange for a worse piece of cake.
I think the algorithm would be that the dictator cuts the most for them selves, the second most for their cronies, and the proletariats can fight over the rest equally
10:04 funny, I always thought after WWII the 4 allies, UdSSR, France, Britain und USA devided Germany in 4 parts plus Berlin, and devided that one again into 4 parts that way they all got what they wanted
11:23 Designing airplanes is the engineering analogue of this. Meeting 90% of your design requirements doesn't mean anything because the remaining 10% will typically end up forcing you to redesign almost everything on the plane, and you have to keep iterating like this until you have _perfectly_ satisfied your design requirements. Blame the minimal safety factors needed to get something to fly for this headache!
Click my CoPilot link go.mycopilot.com/UpAndAtom to get a 14-day FREE trial AND 20% off your first month of personalized fitness if you sign up before February 1st!
When you said to imagine a cake, it made following the entire video without having a real cake. Great video, Jade! Cheers!
Feedback: you might want to try a catchier name for the video 😉
Suggestion for a catchier a title: “It took 50 years figure out how to cut a cake”
no
i love your content please share my video in your community
As computer scientists, our plan is actually to explain theoretical solutions so confusingly that eventually everyone else will give in and let us have the big piece. It's an optimal solution because I get more cake and you get me to shut up.
Haha but I wonder if people will listen and not decide on their own
This explains all the arrogant, know-it-all, power-hoarding arseholes in my Comp. Sci degree. And a number of colleagues.
It works
Joke's on you - I'm into that stuff.
You can design the problem better. So you have a circular and symmetric cake. Solved.
Meanwhile in real life, Billie wants all the cake, Alex HATES cake but doesn't want Billie to have any. Charlie is completely over all this nonsense, killing his appetite so he tells Alex about Billie's Onlyfans. Now she's begging him not to text her boss the link and crying before throwing the cake in a fit of rage at Charlie, but misses, hitting Doug who was just walking by minding his own business.
Free cake for Doug! He must be really happy :)
@@theaxer3751Actually Ethan then fired Doug for showing up late to the KPI meeting covered in cake, causing his wife Fran, to leave him for his brother George and taking their daughter Hailey with her.
Well for a decent number of people, that's pretty much the solution
You know, Alice and Bob would never get into this sort of trouble.
@@evelieningels9408 The real math problem would be proving there's a nonzero chances of there existing three sufficiently rational and intelligent people to all agree to do math to split a cake.
But the only thing i really know about people is that they can be reliably counted on to make the worst, most irrational out of left field out of control emotion driven decisions and not for a single second question the logic of their actions.
"Sharing is mathematically difficult"
New favourite excuse when my sister asks to share my food. 😂
😅
Just ask globalists how they are going to share the cake once everything is under their control.
I think it's a win-win scenario at a party. You cut the cake to obviously favor you. So you either get confronted about it, you say sharing is mathematically difficult and you immediately spot the mathematician in the group - thus avoiding the unnecessary discussions with others, or you're not confronted and you get the bigger slice.
unfortunately n = 2 is the simplest case!
Just buy everyone their own cake, no sharing, job done.
Note to self: do not invite mathematicians to a cake party.
Or software developers.
Just wait until you see how they cut sandwiches.
Particularly if there's more than 5 of them.
Alternatively: don't invite non-mathematicians to a cake party.
@@AdrianColleybecause while they are running the algorithm and/or trying to discuss a better one, you get to steal all the cake
"Wedding photo for Mackenzie? Could she not find another pho-OH WAIT A MINUTE"
This! I had this exact same reaction! ❤
I had to double take just to figure out if they were the same person or if my brain was playing tricks
Cake-cutting is an inside job 💒
It took me a bit too. It was the closup of the photo at the end that did it.
But, until then, I was thinking that was a nice gesture by Mackenzie, acknowledging that he and his wife were a team regardless of her academically recognized contribution to the paper.
This video is just one way to flex her husband. She deserves it though.
Once I was fed up with my daughters complaining about the size of their slice of cake, and the topping. They thought it was all just so unfair. I had enough of that, so I threatened them to put the cake in a blender and pour each of them a glass. I thought it was a great solution since it fixes the disagreement over who would get the chocolate bit, the strawberry bit and so forth. They declined my offer and accepted the slices given instead.
mmm,cake juce
This is the "proof by intimidation" solution to cake-cutting.
Cake juice sounds terrifying
that’d be so mean tbh
@Hix108 "proof by blender"
3:00 "This is a huge drawback for anyone with more than one friend." It's bold of you to assume I have more than one friend. As someone who has no friends, the optimal sharing strategy is for me to eat the entire cake myself. 😊
Exactly 😂
having no friends has some benefits after all.
That explains why computer scientists weren't in a hurry to solve it
The best part of working alone is the quality of the team members, isn't it? 😁
Bah! Then the problem is, which part do I eat first?
A man who truely has cake truely has friends.
Having watched this twice now I’ve decided to use the tried and tested methods mothers in families have used for years. Don’t let the kids see the other kids pieces of cake😂
Game theory it is
Or just "shut up and be grateful - there are starving kids in Africa and blah blah blah..."
@@ivesvaz2894 Wait, this might actually be on to something.
the cake was so much for matpat that it caused him to quit entirely @@ivesvaz2894
* kids'
Alex, Billie and Charlie may be happy but Simon definitely got the best deal. :) Good video.
That's not an envy-free cutting, I'm envious 🥲🫠
funny
simon says h
It's clear she's not great at providing non-enviousness inducing informative videos :)
My identical twin and I used to share coke for instance, so we used to try to fill two glasses equally to the millimeter level accuracy, until we both were satisfied with the equality.. One drop to this, another two drops to that, and repeat. It sometimes took 20 minutes but who cares! Whatever is spilt onto the table, one of us put thier bare feet on it so that the other could not lick it off the table. so for me, it is fairly understandable why an envy free algorithm is so complicated :)
This reminds me of an argument I had as an 8-year-old with my parents who cut a small cake in two exact halves, one for me and one for my 2 years younger and much physically smaller sister. I complained that equivalence in absolute size of a cake piece was the wrong metric for fairness, but rather "equivalent satisfaction" should be aimed at and thus, my hypothesis was, that the cake should be divided into the ratio of the sizes of our stomachs, which again could be estimated from our body weights. My parents were not impressed with my hubristic mini-essay of neuroscience and mathematics and just told me to zip it and be glad I have any cake, as many kids don't have cake at all, ever. 😅☠
People tend to remember the most traumatic events of their lives. You had a good childhood if that's the thing you remember as being the equivalent to the end of the world.
@@privacyvalued4134 I tend to remember a lot of my life and this is by no means a "traumatic" event, but it's a stupid story about an annoying know-it-all kid (me) just for the sake of entertainment. But you are correct with your conclusion anyway, I was blessed with having wonderful parents and great friends. The only traumas I have are of loss.
me when i lie
If the size of her piece wound up being more than she could eat and, thus, went to waste, I would agree with you. But, if it was just a matter of you wanting more because you were bigger, I don't really think that is applicable. The purpose of the dessert is not to fill your stomach (that's what the main food in the meal is for, so your argument may apply to splitting up a pizza, but not cake). Eating more dessert just means enjoying more of the flavor, in which case size should not inherently entitle you to getting to enjoy more of that flavor. So, in that case, I agree with your parents.
@@skylerwhitefan you should not lie
This is the first time ever I've seen a scientist made a video about their discover in mathematics. That's wholesome on so manh levels
Hannah Fry did a great video on this years ago on Numberphile. Your video is great too and seems a lot more comprehensive. What motivated you to make this one?
EDIT: Oh. The wedding photo! That says a lot, lol.
It would have been hilarious if you and Simon had cupcakes at your wedding!
As a teacher/fanatic of discrete math, I love everything that's here. I will admit, this is the one topic in the fair division chapter I skip only because I know how long it can take and resolving the whole envy issue. Divider-Chooser, Lone-Divider, Lone-Chooser, Sealed Bids, Markers, all fine. This is much tougher, but if you're willing to brute force the steps and no one minds the time it takes, then do it and let everyone walk away as happy as possible.
But the thing I love most about fair division as a whole is that it brings the whole concept of the value system to light. It spans so many financial, personal and/or political aspects, and you can't just say everyone should be happy with what they get just because of what you perceive to be all pieces being equal fractions of the whole thing. What you value is not the same as what your neighbor values.
Excellent video. I'll remember this one for the future.
this is so cool. I thought this video was gonna be about the better way to cut circular cakes but this is way better
Nice video. Note: I recall someone defining "fairness" as the condition when all parties are equally dissatisfied. I think that definition might make for an easier solution.😁
This is mathematics; obviously the harder one is more interesting.
@@crimsondragon2677 he knows. he said it so he could make the joke about the quote he said
@@AstroEli133 I am aware. I was responding with a joke about how frequently mathematicians ignore simple but inexact solutions because they are off by ≈3 atoms in an entire cake.
@@crimsondragon2677 oh ok, i didnt get ur joke bf
This is like the other comment on where someone threatened their kids with blending the cake so they would get the exact same
People in a birthday: Lets share the cake!
Me: Hold up
*Pulls out my phone to rewatch it*
ENVY-FREENESS, if only theres such a thing in this world 🥺🥺
yeah, people usually envy not the amount cake other person have, but the happiness itself. Someone is satisfied? envy.
It would be interesting to see it applied to land division, as it usually cannot be freely divided and the pieces must, usually, be continuous
says you
I mean, I know it is more difficult to operate over non continuos land, But it's doable. The real challenge is that land changes, often impredictably, over time
Easy, if no one possesses any land, then no one can be envious of the other. Just don't devide it in the first place.
Wish Israeli settlers could've heard this before dividing Palestine both unfairly AND non-contiguously 🙃
Software engineer here:
What if each player is given an incentive perk for having chosen a lesser slice? Like a good samaritan state of "I'll be happy with this smaller division in the sake of moving the algorithm further"
Envy-free doesn't always imply equal distribution - lots of people would be happy to take a lesser slice to make another person smile too or for the sake of saving time (efficiency in the algorithm) at a party...'empathetically envy free' could be an alternative final condition to avoid the entire system being hung up in selfishness over ease
"This is a huge drawback to anyone with more than one friend"
So it seems sharing a cake will always simple in my life
Damn, didn't realize it was her in the pic with the scientist. Putting her wedding pic at the end is the biggest flex I have seen by a youtuber
I had this issue one thanksgiving. My aunt had a cake with a lot of different toppings and we wanted to find the fairest way to cut the cake. There was 11 of us. Basically we solved the problem by asking which topping each person wanted the most. Those who wanted a particular topping had their topping cut away and they divided that portion among themselves, and so one and so on. The rest of the cake that didn't have toppings were divided amongst everyone.
This is why you set out the cut lines correctly BEFORE you make the cuts. I swear, if carpenters ruled the world, it would be a better place.
And... measure twice, cut once.
We would have a bunch of people saying "I cut it 3 times and it's still too short"😂
Never invite a carpenter/construction worker to a party. They'll ruin the cake when they bust out the blue chalk line tape.
Measure n^n^n^n^n^n times, cut once.
“Cut and choose… only works for two people, this is a huge drawback for anyone with more than one friend”
Ah, so that’s why it took 70 years. What an unrealistic scenario.
mathematicians make problems where there are easy solutions - you just buy more cake than friends can possibly eat, everyone is sated and there's like 1/3 still left 😂😂
Doesn't solve the problem -- who gets to take the uneaten 1/3rd of the cake home, hmmmm?
@@jmr5125 maybe it doesn’t matter because life doesn’t revolve around leftover cake?? Everyone’s like a child.
@@jackapps2126you don't understand... It does revolve. There were so many wars and battles for the leftover cake. So many victims. And the only goal in this situation is victory, so there is no word such as loss!
This is a practical solution for cake, using the make sure there is enough principle. But for dividing land or the like, it doesn't work that way.
What happens if some parts change in value depending of the parts they're paired with? Like a situation in which Matt likes strawberries and blueberries equaly, but hates them together, then if he ends with pieces that contain both, suddenly his cake loses value. Or what would we do in a case in which consecutive pieces are more or less valuable than pieces from different parts of the cake? For example if instead of cake we think about time, someone might think that 10 consecutive minutes of something is worth more (or less) than two separate sessions of five minutes each?
You ignored the REAL elephant in the room, slices with negative value. If we have a pizza and 90% of it has pineapple on it, I only want the slice without pineapple. What if nobody wants the pineapple? do you cut the non-pineapple up into 3 absolutely tiny pieces that nobody will be happy with?
This is when we do what’s called “pick it off”
@@doombybbr
Well, in that instance. It is not the division that people are happy with, it's the product. Right?
@@Amor_fati.Memento_Mori Its more with the very idea that you should divide it up under those conditions, the 9 slices with pineapple should go in the bin.
Also what if one person is a young child, one person is on a diet and one person is a body builder - as in what if they do not actually need the same amount, or what if everyone is starving and there is only enough for half the people.
Or better yet - what if the optimal strategy is for the cutter NOT to make "equal slices"? Not only may people collaborate in the cake cutting game to gain more cake, but people may take advantage of what other people prefer. It is actually optimal to cut in a way you know makes everyone else happy but results in them leaving the specific slice you want for yourself - rather than to cut them "equally"
The fact that it is not a math game but a MIND GAME means if a person values the piece with strawberries at 1 and everything else at 0, then that person has to keep dividing up strawberries for each person they THINK likes strawberries(just to guarantee maximum strawberries), but then if someone likes strawberries they didn't expect the cutter ends up without a piece, and if someone doesn't like strawberries that the cutter thought liked them, they would have to rely on mr non-strawberries feeling charitable enough to actually give a piece.
The fact that so many of these methods rely on someone feeling charitable enough to give a piece away is another problem, because I do not know many people willing to give up part of their cake.
Looks like a precondition for the algorithm...
I feel like if I ever got near to spending 50+ years on a formula to cake cutting. At that point I would just take the 50 years green aged cake, stick it in a blender and measure it out in micrograms to each individual person.
This is such a great explanation! Me and a friend were just thinking about this problem a few days ago and this explains every one of our questions amazingly. You also explain the algorithms impressively intuitive
Your husband solved this 50+ year old problem? Seems like a pretty smart guy!
That Simon guys's wife looks awfully familiar ;)
I'd swear I've seen her somewhere before.
@@suttoncoldfield9318 Maybe she has been on one of those competitive baking programmes. He probably managed to solve the problem from trying to equally divide all of the practice cakes amongst their neighbours. It's insane how varied the show stoppers' toppings can be on a single cake. :)
I would honestly propose to freeze-dry the cake, then pulverize it to a pure protein shake-like powder and then weigh portions with a molecular scale. It's a bit like explaining a joke where the cake dies during the process. In the end I'm usually the one eating both the bigger cuts and eating the scraps anyway.
Not to mention anyone who dared not agree with the arrangement.
Except the point of the video is that preference plays a huge role - the people involved do not necessarily want a piece indistinguishable from every other piece; some want more frosting, others want more edge piece, etc
@@orterves Probably that was what I was missing.
This video is just to show off that she's married to teh smart cake cutting man!
"If we dont know if we're making progress its very difficult to know in what direction we're heading" - nerd poetry🤤
Loved watching the math-intensive cake cutting on Nebula ❤
There is ONLY one sensible way to cut a cake (or equally divide anything), the person cutting the cake gets the last piece and because they do not want a small slice they will very carefully make sure all of the slices are the same. 70 years for scientists to figure out a complex version of the common sense my Grandmother taught me... Just goes to show that education and intelligence are often two entirely different things!
what if you cut all other people's slices smaller that the last one 😎
@@broccolionswag Then someone would take the bigger slice and you would be left with one of the smaller slices and a lot of unhappy people wanting to know why you gave a large piece away to just one person.
this channel really good and consistent. it deserve way more view
When Billie loudly proclaims that she got the best piece, Alex will be crying. -there is not solution
I think I just found a method to reduce the number of cuts needed for envy-free division for any amount of people.
To demonstrate my method, I will use 3 people for an example.
First Alex cuts the cake into 3 pieces that he thinks are of equal value. Then in case Billie and Charlie want the same piece of cake, Alex cuts Billie, taking her out of the equation. The rest is cut and chose.
I just ate and im hungry again now dang
"This is a huge problem with everyone with more than one friend"
Can't relate.
If any relative of mine talked about cutting cake like this they would never be invited to a family event ever again.
I'm trying to think of a point in the division of a more complicated thing like a plot of land in which (a) some persons are not happy with the location of the division, such as through the middle of a town, or (b) some possibility where the cuts made by a large number of persons, especially when swapping pieces, result in non-adjacent pieces... For cake, whether the pieces were originally adjacent doesn't matter, but for other things (like plots of land) they definitely do
3:04 "This is a huge problem for anyone with more then one friend"
I'm one step ahead in this regard :)
What happens in the cut and choose scenario if, for example, the cake has one area with nuts on the top and one area with strawberries, and the cutter cuts it so that both pieces have both nuts and strawberries and the chooser doesn't like (Or worse, is allergic to) nuts? The chooser wouldn't be happy with either bit.
Having part of the cake with 0 personal value, but non-0 perceived value. Pretty much guarantees envy unless the other person greatly favors what you can't eat. At the extreme sharing a meringue with someone who can't eat eggs is ridiculous.
So, first, if someone is allergic to nuts, he/she shouldn't be eating any part of a cake that has nuts anywhere on it; so we can remove that hypothetical pretty easily.
Second, the entire point of the cut and choose is that the cutter decides the equal value but doesn't get to choose. It doesn't matter how the chooser would have divided the cake, because that isn't his job. If he wants any part of the cake, he has to choose the part he would be most happy with.
I suppose if his dislike of both pieces was so extreme, then it just falls into what I said initially about the person with allergies. This is just a cake the second person doesn't want, so the first person gets all of the cake. Because, if you think about it, the only way you might solve this is to switch jobs and let the second person cut and the first person decide. But, when the second person goes to cut, he will realize that, if he cuts it into pieces that don't hold equal value to him (meaning he cuts it so all the nuts are on one piece and none on the other), then the first person might choose the piece he actually wants. So, to be fair to himself, he would also have to cut it so that there are nuts on both pieces (so, no matter what the first guy chooses, the second guy won't wind up with a piece covered in nuts). That is why the cut and choose method works no matter what order people go in.
That's all just relying on the logic, though. Realistically, people can just talk to each other about what they like or don't like to see if they can come to a better agreement before cutting.
I think this is a good example of how envy free isnt exactly the same thing as fair. In this scenario, its still true that both players will be envy free. The cutter is not envious because they believe the peices to be equal value, and the chooser gets to choose whichever peice they think has the larger value, even if the values of those peices are low. Of course, this may not be considered strictly fair by some people (perhaps the fairest solution is give all nuts to the cutter and the chooser gets slightly less cake or something) but it is still definitely envy free.
@@SgtSupaman Not every allergy is life-threatening. I've got a fairly mild allergy, so food that's only _touched_ peanuts won't kill me*, but that doesn't mean I'd feel safe eating a whole peanut-covered slice of cake.
(* at least, it's no more likely to than, say, crossing the street.)
Ah, this is the problem with envy freeness. Just because a division is envy free doesn't mean that it's pareto efficient. Being pareto efficient means that there is no way to divide the cake in a differentway such that everyone ends up at least as happy as they were with the current division, and someone ends up happier than they would with the current division. Thankfully, there is a theorem called Weller's theorem guaranteeing the existence a division that is both pareto efficient and envy free, but as far as I know, there has been no progress in creating an algorithm to find this division.
Wait, was that you at 10:03? Did your partner work on the cake cutting problem?
Excellent video as always. In a very sad scenario, Alex purchases candy sprinkles shaped like little ant coats the cake in them. After everyone else decides they don't want a piece of ant covered cake, Alex drops the mic then gleefully eats the whole thing.
except for the one guy who suggests a horizontal cut, leaving all the ant coated surface for Alex.
This is the best remake of a numberphile video I've ever seen
Rumor has it they're still cutting their wedding cake to this day.
I love how you kept the pull in the background at 5:20
Every gearhead watching this 🧏
Great topic... even better presentation.
Thank you, Jade.
This is so well detailed and illustrated to a topic which i always wanted to explore and understand in detail.
I watched many videos on this but this is so far the best as it also included the journey and problems in the ideas till the best one we came to know today!
Purely AWESOME!
clearly, the solution is televised cage matches with the winner getting all the cake.
I invited 6 friends over to my birthday party. This is gonna be a long party :D
Happy early birthday!
@@shoyuramenoff and the one after that, and the one after that, and the one after that.... until they finally cut the cake from the first one, after it has decomposed and become the compost the ingredients for the next one were grown in :)
If it's complicated, you can be sure that a certain Conway will come.
He is still sorely missed
Mathematicians over here worried about perfection, meanwhile I'm over here just happy I was invited to the party.
Whaaat, I am so happy, you made another video! Thank you so much.
My mother’s solution was to have one kid cut the cake, but they would get the last choice of a piece. I think the pieces were perfectly equally sized down to the micrometer.
The problem is 200 tiny little crumbles are worth significantly less than a slightly unfair but whole piece.
Perhaps the cake should be modeled digitally first, so all the cuts are just theoretical until the final agreement is come to. Hosting parties just keeps getting more and more complicated.
@@SgtSupaman It is not yet proven that you can always reach an envy-free solution where each slice is continuous.
So your idea would definitely *reduce* the crumbiness, but it wouldn't guarantee that we avoid having thousands of pieces.
@@tudornaconecinii3609 Another comment decided they're throw the cake in a blender, that way everyone is equally unhappy. :)
Misread the title when I first saw it in my sub-box. Thought it said fastest. Spent the last hour or so thinking of different arrangement of cake cutters arranged in frames* for all kinds of different shapes of cakes. Thought it was a bit of a odd topic considering the history here. Fairness will be a more interesting topic though so double thanks!
I usually am fine with less than a fair amount, but preferable not much less. I wonder if there is some mathematically fun stuff that can be used in my case.
"This is a huge drawback for anyone with more than one friend"
Whew! I'm safe
The fairest way to cut a cake is to not cut it at all and that way everyone gets the exact same amount: nothing.
Great work! You did it again! Take a hard mathematical subject, and explain it so that it is clear, accessible and a joy to watch. Kudos from a fellow mathematician. (And really nice to see n^^5 in any theorem.)
Yay Jade is back and we got cake video to celebrate it! :D
Easy solution: make a symmetrical cake (like a square) which is exactly the same all over (like equal toppings,etc.)
Great video. As always. 😊 But I can't stop pondering... How many cakes gave their lives for this video to be made? 😆
I legit gasped at 12:15. RIP residual cake. :c
As someon who doesn't have friends, I feel lucky not having this kind of problem.
the amount of innocent cake harmed in this video is disturbing :)
I think it was taken care of appropriately afterwards
to share mathematically correctly a cake, take all of you a spoon and start eating it at the same time untill it finishs.
Someone had to do a lot of baking for this episode 😅
-Okay guys how are we going to divide this cake?
Me:*breathes in
the cake is a LIE
This video should be a requirement for any poly relationship, parents, and groups.
This is the question a mother asks to make her child avoid eating cake 🍰🎂🍰🍰🍰🍰🎂🎂🎂🍰🍰🎂😂😂😂😂😂😂😂😂😂😂😂😂😂😂😂😂
Why the heck this many emojis?
@@tharii314 Just to match the number of pieces of cake required to be divided into 4 people.....
I remember reading an article about the cake cutting problem in Scientific American about 15-20 years ago. The practical upshot of the residue was to pay the attorneys! Also, Jade at some point in time, "How can I get my wedding photo in a video?" While working on this one, "Eureka!" Also, with a name like "Simon McKenzie," how does he speak French so well?
There is a way to cut a cake into five pieces that waiters and waitresses know about. You cup the cake in six even pieces which is easy, and then you give one slice to each of the five people and then you give the sixth slice to the waiter. 😅 It's a perfect solution
Do you know how to serve six potatoes to seven people?
...
Mash them! 😂
The way to cut it into 5 pieces is to first cut it into 6 pieces 🤔
Love your videos. For me they are the right balance of entertainment and knowledge. Thank you sincerely :-)
Well this video takes the cake so no need for equation 😂
She really should have used cheese so you could have said "Well this video really cuts the cheese..."
I dont know why i watchd the the entire thing, but i loved it. I hate math but that was awesome
In practice, cut and choose still has the problem that the chooser is likely to get a better than equal piece, but the cutter won't unless he adjusts his cut by whatever he assumes to be the choosers preferences.
So there could still be envy for who becomes the chooser.
The cutter splits the cake into 2 pieces that they consider equal, so they'd be happy with either piece without any envy for the other piece. The chooser then chooses whichever piece they prefer and so the cutter is left with the other piece, which they'd already decided was exactly equal, so there is no envy.
@@BenUK1 yeah, but wouldn't you still rather be the chooser? (especially if it is a cake with toppings)
Unless your preferences align perfectly, the chooser will get a piece that is better than if they cut the cake honestly.
Like in the video when the cutter makes a small piece with strawberries and a big piece without. If the chooser hates strawberries they will gladly take the bigger piece, but if they were to cut the cake into equal pieces themselves they wouldn't have that luxury. (At least not unless they take the risk of cutting strategically instead of honestly)
The cutter doesn’t care about the chooser’s preference. They just cut two pieces that they would be equally happy with. It doesn’t matter if the chooser is more happy with one or the other, by definition, the cutter is equally happy with theirs. The goal isn’t “everybody thinks they have the same value piece”, it is “everybody thinks they got at least their fair share”. There’s no issue with somebody thinking they got the better deal, and, in general, deciding you are less happy because somebody else is more happy is just a horrific way to live.
I think I see what you mean. You are essentially quantifying happiness and then saying that the chooser gets a larger share of the total happiness at the end than the cutter, but the problem itself is only interested in sharing the cake (or whatever the resource being shared is) and the absolute measure of 'happy' or 'not happy'. Both players do end up happy (nobody is actively unhappy), and both players believe they at least both got a fair share of the cake, even if they also believe the other player to have slightly more resultant happiness than them. Trying to get them to all believe they have a fair share of the cake AND a fair share of the total happiness at the end of the sharing would require being able to scientific measure (or mathematically model) happiness in some way, and would be a problem of an order of complexity up from the problem of 'simply' fairly sharing the cake.
Another way to explain this away would be that each person has a different opinion or perspective about the value of the pieces (if they didn't it would just be like sharing a pile of money where the total sum of money could just be divided by the number of people sharing it to arrive at an equal amount each). So the chooser may well believe they had a better piece and that the cutter had a worse piece, but the cutter believes that they have a fair piece either way and therefore does not believe they have a worse piece than the chooser. The cutter doesn't care about the chooser's opinion of the choosers piece, they cutter only cares about the cutters opinion of the two pieces. Each person's own opinion of their own piece has to be positive at the end of the share.
I guess the fact that the chooser is restricted to choosing one of the two pieces that the cutter cut, whilst the cutter has freedom to make whatever cut they want and create any of the essentially infinite possible pieces, is also something to bear in mind.
@@NitFlickwick it’s true that the cutter will always get their fair share, but if they had instead been the chooser, they’d also get at least their fair share, but they’d also have a chance of getting more cake.
That said, if the cutter knows exactly how the chooser measures value, they could take advantage of it by making one piece include just the parts that they like more than the chooser, such that they would like that piece more, but the chooser would just barely prefer the other piece. This is not about how the cutter doesn’t want the chooser to be happier than them, it’s about how the cutter could’ve gotten a better piece while still keeping the other satisfied, but they usually don’t know how.
Let’s say we’re cutting a half-vanilla half-chocolate cake, when A loves vanilla and B loves chocolate. If A cuts honestly, they’d cut just over half of the vanilla into one piece, and just under half of the vanilla in the same piece with the whole chocolate. But if B had cut, A could get the entire vanilla part (twice what they’d got), and almost half of the chocolate. Do you see the issue?
This is an excellent demonstration of a big concept in software engineering that is often overlooked by computer scientists. In the real world, you just divvy it into 3 semi-equal pieces and move on with the party. Absolute correctness is often desirable, but not at the cost of expedience, ease of implementation, ease of maintenance, or performance. A pretty good, very fast approximation is very often better (in a practical setting) than a 100% correct, slow and complex solution.
Now I'm hungry😂
A brilliant episode with a fun twist!
I wonder, does the problem get (significantly) easier if we allow participants to pay each other and hold auctions?
Only if you're in a situation where all participants have equal money at the start and people are okay with having more money in exchange for a worse piece of cake.
“This is a drawback for anyone with more than one friend.” Epic.
The best way to satisfy all is to not let one know what pieces others are getting
“Size is just one factor among many”
It took 70 years to divide a cake fairly, why should I share my cookies so easily ?
Beyond the main premise, this video is also very good at explaining how mathematicians convert intuitive logic to numerical alogrythms / formulas
an algorithm for communist cake cutting Haha
Define "communist" before uttering stupidities.
@@MarcusCactus you’re demanding definitions of words and putting people down? Bro…
I think the algorithm would be that the dictator cuts the most for them selves, the second most for their cronies, and the proletariats can fight over the rest equally
I have fallen behind Jade's advancing knowledge og game theory and I need to re-watch the prior videos now to fully appreciate these :0)
3:04 more than one friend? wouldn't know. must be nice.
alex and billie and Charlie were fighting over cake
....MEANWHILE....
Jade: oh im so full
Cake DOMINATION, is a phrase I did not expect to be relevant
“Fair” and “satisfying disparate preferences” are two different things.
10:04 funny, I always thought after WWII the 4 allies, UdSSR, France, Britain und USA devided Germany in 4 parts plus Berlin, and devided that one again into 4 parts that way they all got what they wanted
11:23 Designing airplanes is the engineering analogue of this. Meeting 90% of your design requirements doesn't mean anything because the remaining 10% will typically end up forcing you to redesign almost everything on the plane, and you have to keep iterating like this until you have _perfectly_ satisfied your design requirements. Blame the minimal safety factors needed to get something to fly for this headache!