Re: Nightingale and Cut-and-Choose Proofs

From: John A. Malley (102667.2235_at_compuserve.com)
Date: 07/30/04 

Date: Thu, 29 Jul 2004 19:27:13 -0700

flip wrote:
[...]
>

Since they are talking about secret-splitting, I bet they mean
cake-cutting algorithms. Cake-cutting algorithms are protocols for the
"fair" division of resources between two or more parties. There are some
theorems about what can achieved using certain kinds of cake-cutting
algorithms, that might be what is implied by "cut-and-choose proofs."

Google on "cake-cutting algorithms" and you'll get a bevy of papers and
presentations.

Here's a simple cut-and-choose algorithm. Two kids want to eat the last
slice of pizza. One child cuts the slice into two portions and the other
child chooses a piece after the cutting. It's in the best interest of
the first child to cut the slice into equal halves since the other child
gets to choose after the cut.

I have two kids. It works every time. :-) (Also works with soda, candy
and cake.)

Here's a great book on the subject - "Cake-Cutting Algorithms, Be Fair
If You Can," by Jack Robertson and William Webb, ISBN 156881076-8.

HTH,

John A. Malley
102667.2235@compuserve.com 

-- 
U.S. Presidents say the darndest things!
"I am not a crook." - Richard M. Nixon
"I did not have sexual relations with that woman." - Bill Clinton
"I have never ordered torture. I will never order torture." - George W. Bush