From: <rollo@artvark.com> (Rollo Silver)
Date: Sat, 27 Jul 1996 14:40:24 +0800
To: cypherpunks@toad.com
Subject: Pie cutting algorithm
Message-ID: <v03007803ae1f2dddab21@[206.183.203.4]>
MIME-Version: 1.0
Content-Type: text/enriched

Tim May said:
<< ObCrypto Sidebar: The "fair" method for dividing a pie between two people
is well-known: "You cut, I choose." This *game theory* result is central to
many cryptographic protocols (though it may not always be apparent at
first). And the protocol can be extended to 3 parties, and proabably to N.
Research is ongoing on this, including Cypherpunk Robin Hanson's work at
Caltech. >>

I (RS) believe Claude Shannon proposed the following N-person pie-cutting algorithm more than 25 years ago:

Persons 1...N are seated around a circular table. A Thing To Be Shared (Call it a "pie") sits in front of P1 (Alice, if you prefer).

P1 cuts a slice (a portion satisfactory to her) out of the pie -- the "current slice" -- and offers the whole pie with the current slice to the person P2 (Barbara, if you like) to her left for her consideration. It is possible that P1 is so greedy that she makes the whole pie the current slice.

P2 does one of 2 things:
A. P2 cuts a smaller slice (a portion satisfactory to her, which becomes the new current slice) out of the old current slice and offers the whole pie with the new current slice to P3.
B. P2 passes (being unwilling to settle for a smaller slice of the pie than the current slice), offering the person P3 to her left the whole pie with the current slice for her consideration;

P3 does one of 2 things:
A. P3 cuts a smaller slice (a portion satisfactory to her, which becomes the new current slice) out of the old current slice and offers the whole pie with the new current slice to P4.
B. P3 passes (being unwilling to settle for a smaller slice of the pie than the current slice), offering the person P4 to her left the whole pie with the current slice for her consideration;

...

Eventually, someone (Pm, or Morticia) has cut a current slice, and everybody else has passed. At that point Pm gets the piece she cut, leaves the table with it, and (if N > 2) the game proceeds ab initio with N-1 people and the remaining pie. If N = 2 (two people were playing), there's now one person left (Winnie), and she gets the remaining pie.

The whole procedure terminates, with everyone satisified, after a finite number of steps.

Tim May: as a Licensed Ontologist, do you know who made the wiseassed (but deep) remark "Ontology recapitulates Philology"? or for that matter, "Oncology recapitulates Proctology".
Rollo Silver / Amygdala | e-mail: rollo@artvark.com
216M N. Pueblo Rd, #107 | Website: http://www.artvark.com/artvark/
Taos, NM 87571 USA      | Voice: 505-751-9601; FAX: 505-751-7507