Return of d bugg - The sequel

6 dataloger, 1 semla


Eating “semlor” is fun. The feeling in your mouth when you tried eating one all at once, the look in everyone’s eyes when parts of the cream make their way down your spex-hoodie. Indescribable. What could be more fun? Yes: Eating semlor together.

Fairness in Sweden

But we are in Sweden, where fairness is considered the most important value of all. Usually there are two ways in which swedes achieve fairness: Democratic voting and Queueing. But even if it seems so, these two techniques, as great as they are, can’t serve as a universal solution for all equality-issues: If all six of us would queue for eating one semla, the result would be basically that the first of us would get all of it, and the rest doesn’t get anything. And voting is a worse solution: We are an even number of people, so any vote might result in a tie and endless discussions. And what would we even vote on? Elect someone who then is responsible for doing a fair division? And then trust that person? Sounds horrible.

The Solution

a German massacring a semla and a Swede licking his fingers

I am always happy to make my contribution to the Swedish fairness-culture of the future. And in this case, I present the following technique that should instantly be added to the Swedish fairness toolbox. It is not only the most deterministic, guaranteed terminating algorithm that is very easy to understand due to its recursive nature, but also the only one that gets presented in an unnecessarily long english article in the most popular computer science magazine of META.

8 dataloger 1 semla

The students sit around a table with the semla in the middle. The Student that shouts “Viking” first, starts. He or she takes a knife and cuts out a piece which he/she would be satisfied with (and which is a fair portion according to his/her subjective judgement). Then it goes around the table: Everyone can either agree that this piece is at most 1/8 according to his or her subjective judgement as well, or make the piece a bit smaller by cutting away a part and returning that to the rest of the semla. It’s that easy: When everybody has had his or her say or cut, the last person that cut gets to keep the piece! The other students start the same procedure again. A piece of cake, ehhh, I meant semla, right!?

Proof by example datalog failing badly at eating a semla

This semla-cutting-technique is totally fair, which we will proof by example:

Let’s say Emil, Emil, Emil, Valle, Emil and Emil try to divide the semla, and let Valle be the last person that wanted to make the piece smaller. Valle is happy: he got the piece he considered to be fair. All pre-Valle-Emils are happy as well, since the pieces that they thought are fair are supersets of Valles’ piece. So he got a smaller piece than what they would have been happy with. But what about the post-Valle-Emils? They must be happy as well, as they wouldn’t be happy with taking a piece that is only a tiny bit smaller than Valle’s.

Concluding remarks

In this paper we have shown that for any set of n density-functions f_n over [0,1] there is a fair algorithm to find n-1 division points 0 < d_k < 1, so that… Oh wait, this is not my thesis? Oh, ok, well. So how did this turn out? Theoretically the worst-case amount of cuts happening is 8 cuts until we get the first piece (which then the last person takes), and if everyone always cuts, the last cut will be by the second person, and the first person doesn’t have to cut in the end, soo…. It would be 8+7+6+5+4+3+2 = 35 cuts. But what happened in reality? Well, we had more than one semla. In fact, there were so many that we even started fighting for the smallest piece at the end. But as stated in the beginning, this algorithm should be seen as a contribution to the Swedish fairness toolbox. Our chapter turns 40 this year, maybe there will be a birthday-cake that must be divided fairly?