You cut I choose

    Keywords: Theory

You cut I choose is a general principle for fair division of just about anything between two parties. One side divides the stuff into two lots, and the other side selects which party gets which lot.

In Go, it is relevant to a wide variety of topics, e.g.

etc.


There's an interesting extension of You-Cut-I-Choose when more than 2 players are involved.

Suppose you have a cake that you want to divide 3 ways. Player A cuts a piece that he estimates to be 1/3 of the cake, that he would be willing to accept. Player B can either reject the piece, or cut another piece off. Player C then can either reject the piece, or cut another piece off. The last player to cut the piece gets that piece. The remaining 2 players play the 2-person You-Cut-I-Choose for the rest of the cake.

This method is fair, because each player is guaranteed what they estimate to be 1/3[1].

This method generalizes to a large number of players.


[1] I hope I don't understand it, because if I do, it doesn't work.

A is not a perfect estimator and say he cuts off a piece that is bigger or smaller then 1/3.

Say B and C are better estimators than A. How can they both get a piece that they estimate to be 1/3 ?

In the two player game I don't see this complication. A cuts the cake into two pieces he is willing to accept. They can be 1/3 and 2/3 of the cake, it does not matter. B chooses from those pieces. They may not get what they think to be half the cake, but both do get pieces they are willing to accept. -- mAsterdam

Bill: In this context, 1/3 means at least 1/3.

Bob McGuigan: It is important to note that the value of the pieces to each player is determined by that player's own measure. It is not assumed that all players are using the same measure for value of pieces of cake. Thus player A might cut a piece that has value 1/3 of the whole cake to her but its value to player B might be less than 1/3 of the whole cake or more than 1/3 of the whole cake. All players' measures must satisfy certain basic technical properties. A good reference for these things is the book Fair Division by Steven J. Brams and Alan D. Taylor.


The real generalisation of "You cut I choose" is as follows:

Player A cuts

Player B can take the piece cut by A or pass

Player C same...

...

If all players players pass A gets the piece he cut

Repeat until all have pieces

lavalyn: Close. You are assuming that there would be no alliances between players. Player A and B scheme to get an advantage, decides to cut 4/5 of the cake as chunk. B naturally accepts. C gets screwed.

Rather, player A cuts "the smallest" piece he is willing to accept, and all players that would accept the piece must play the game on the little piece, slowly cutting tiny little slices off until only one player is willing to accept. And that player gets it. This of course assumes that cake is infinitely divisible[2] and that the tiny slices that would result are Riemann summable :)

Henry: I don't think that an infinite process qualifies as a solution to this problem. The possibilities for collusion can be removed by randomising who out of B and C gets first dibs on A's cut. Obviously in this case A can't promise both B and C a larger share to get them to collude, since any collusion will increase A's share. B's and C's "expected" share is to get exactly half the remainder each, so it's not in either of their interests to collude with A before the toss. And after the toss it is too late for A to change his cut.

lavalyn: I didn't say it was an infinite process. I claimed that the little pieces of subcake will have to be summed up. The process at worst is O(n^3) time, since at least one person (the person doing the cutting) will drop out each cut. (I have corrected an omission above which addresses this.)

And as for randomizing - that doesn't work either. Player A cuts exactly half. Regardless of what either B or C does, A wins.

Henry: Oh, I see your method. I don't understand what you mean by Riemann summation, though. Obviously we are only talking about measurable subsets of the cake, or you could decompose it into four pieces adding to two copies of the original cake... (And in any case I dislike the notion that the last chooser is going to be left with a nasty, even if finite, collection of crumbs.)

If A cuts half and B and C get to choose randomly who picks first, then A is going to get no more than a quarter of the cake, a definite loss.


[2] The moving knife procedure can take care of that. One randomly chosen person moves the knife over the (lineair) cake until one of the participants says "stop", accepting the piece that is cut off there. (This is not just theory - big auctions, for instance [ext] VBA use computerized procedures similar to this part to establish the price of lots.) Repeat until there is one piece left. --mAsterdam


ilanpi: There are two generalisations to the pie problem when there are more than two people. The simplest is when you ask that each person feels that he gets at least his fair share. This has many simple solutions. The harder question is that no one feels that someone else has gotten a larger share, which is called ``envy-free'' pie division. Envy free pie division has a straightforward solution for three people (one of the solvers is John Conway of Combinatorial Game Theory). However, this has never been generalised to more than three people. A solution was only found fairly recently, but uses a complicated protocol with an unbounded number of steps. A solution with a bounded number of steps for envy-free division with 4 people is unknown as of 2 years ago.

Warfreak2: There is a nice three-player solution in which each player draws two horizontal lines across the pie, splitting it into thirds. For the top third, one line must be highest, so the player who drew that, gets that portion. Similarly one must be lowest. Since the lines drawn by the player who does not yet have a piece, do not overlap with the other pieces, he gets that portion. The remaining bits needn't be discarded, you can just move the remaining boundary lines to 2/3 or 1/3 (respectively) the distance between themselves, and each player gets a piece that is larger (or equal to) a piece he asked for.

Based on this, I worked out a four-player solution: each person draws a horizontal and vertical line into the pie, dividing it into four corners. Like the argument above, each player gets the corner that does not intersect more than one of any other player's corners. The crossing point of the two lines can then be taken to the average (x-bar, y-bar) point, each player keeping the same corner. Again, every player gets a piece that is larger (or equal to) a piece he asked for.

I'm not sure what the difference between "each player thinks he got more than or equal to his fair share" and "envy-free" is, though. Intuitively I'd say that if I asked for what I'd be happy to have, and I got more than it, then I'd be happy; I can't prove that rigorously though! (in fact it would be naive to think I'd solved this unsolved problem, so I can conclude that there is a difference and this intuition is wrong).


An interesting solution is outlined in "Mutiny on the H.M.S. Bounty", called the Who-shall-have-this Method. Say there are 'N' people to divide between, they choose from amongst themselves two people - A and B. 'A' stands where 'B' cannot observe him, and divides the cake. B then points to someone and that someone comes to claim his share of the cake. B may at any time point to A or to himself, but since he never can see which segment of cake he's giving out, and since B and A are both chosen by the crowd, there is virtually no opportunity for intentional collusion.

This method still won't guarantee everyone a satisfactory cut of the cake, but it gives 'A' the correct motivation, since only by dividing the cake evenly can he hope to get a large piece for himself.


Because of a mention in Bruce Schnier's book, "Beyond Fear", I was working on this w/ a friend of mine. It seems the easiest way to disprove a method for fair 3 person cut-n-choose, is to have the first person cut the cake in half. Is it still possible to be fair to everyone? Our method for three people (A, B, and C) was to have A cut, then B cuts the cake into six pieces. Now they start chosing pieces in this order: C, A, B, B, A C.

How does that solution rank? I didn't google any other good pages about this. I'd like to see a solution for 4 ppl that doesn't involve micro-slices of cake.

marc cutpie.20.foodgun@spamgourmet.com


PlatinumDragon: Three players A, B, and C. A, B, and C each cut one line, cutting the cake into sixth.

[Diagram]
Cake Diagram  
  • if A's cut is exactly half, B's cut is exactly half, and C's cut is exactly half in the sense that you don't count the other player's cuts.
    • The two pieces between A's and B's cut lines are equal.
    • the two pieces between B's and C's cut lines are equal.
    • the two pieces between C's and A's cut lines are equal.

In this case, each player gets to choose a piece (1/6th) of the cake on two criteria (the two cut lines made by the two other players). Therefore, there is an agreement on that each person will get one slice, so there remains 3 slices. To ensure fair, each player will get the opposite slice, and therefore, each player gets about 1/3 or the cake (or pie or whatever you are trying to divide). When they choose, they will choose two set of the three sets, but because it will be on one of the line of one of the player's cut, the other player gets priority, and wins.

A has top priority in selecting 3.

B has top priority in selecting 1.

C has top priority in selecting 2.

1 = 1 or 4, 2 = 2 or 5, 3 = 3 or 6.

The basics is each player cuts one line, and the number of pieces is twice the number of players. Players gets priority if the bordering cut is not their own.



See also:


You cut I choose last edited by PlatinumDragon on April 8, 2009 - 23:05
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library