Splitting a sandwich and not feeling deceived This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an hour to an hour, and then just grins at me, and whispers whole day: "You will never solve me..."

Please save me from this torturer.

Here it is:

Let's say there are two people and a sandwich. They want to share the sandwich, but they don't trust each other. However, they found the way how both of them will have a lunch without feeling deceived: One of them will cut the sandwich in two halves, and another will choose which half will be his. Fair, right?



The problem is:

Is there such mechanism for three people and a sandwich?



EDIT: This was roller-coaster for me. Now, it turns out that there are at least two books devoted exclusively on this problem and its variations:

Fair Division

Cake Cutting Algorithms





Yesterday, I was in a coffee shop in a small company. We ordered coffee and some chocolate cakes. As I was cutting my cake for my first bite, I felt sweat on my forehead. I thought, 'What if some of my buddies just interrupt me and say: Stop! You are not cutting the cake in a fair manner!' My hands started shaking in fear of that. But, no, nothing happened, fortunately.
For more than two, the moving knife is a nice solution.  Somebody takes a knife and moves it slowly across the sandwich.  Any player may say "cut".  At that moment, the sandwich is cut and the piece given to the one who said "cut".  As he has said that is an acceptable piece, he believes he has at least $\frac 1n$ of the sandwich.  The rest have asserted (by not saying "cut") that is it at most $\frac 1n$ of the sandwich, so the average available is now at least their share.  Recurse.
Hmm, if you cut it into an approximate 3rd and 2/3rds portions, then the cutter would get a slice that both other people think is about 1/3rd.  To attempt to subvert this, player A could cheat and make 2 equal halves.  In the real world, such a player would never get invited to party games again.  ;)  But let's just say that then one of the other players would have to divide each half into 1/6th and 1/3rd slices.  Repeat ad nauseum?

If you can 'uncut' the sandwich, then it's easier:  Just keep having a different player cut the sandwich until the other 2 agree.  This is similar to the moving-knife solution but where the cut is not done unless all 3 agree, in actual practice since 'uncutting' really means just not cutting yet.

Once you get the bigger piece being roughly 2/3rds, then you can apply the normal 2-person method.  To go to 4 people, vote in pairs?  You could also apply this idea with 1/4th &amp; 3/4ths slices.  This is generalizable to 5,...,dozens of people.