History
According to Sol Garfunkel, the cake-cutting problem had been one of the most important open problems in 20th century mathematics, when the most important variant of the problem was finally solved with the Brams-Taylor procedure by Steven Brams and Alan Taylor in 1995.
Divide and choose's origins are undocumented. The related activities of bargaining and barter are also ancient. Negotiations involving more than two people are also quite common, the Potsdam Conference is a notable recent example.
The theory of fair division dates back only to the end of the second world war. It was devised by a group of Polish mathematicians, Hugo Steinhaus, Bronisław Knaster and Stefan Banach, who used to meet in the Scottish Café in Lvov (then in Poland). A proportional (fair division) division for any number of players called 'last-diminisher' was devised in 1944. This was attributed to Banach and Knaster by Steinhaus when he made the problem public for the first time at a meeting of the Econometric Society in Washington D.C. on 17 September 1947. At that meeting he also proposed the problem of finding the smallest number of cuts necessary for such divisions.
Envy-free division was first solved for the 3 player case in 1960 independently by John Selfridge of Northern Illinois University and John Horton Conway at Cambridge University, the algorithm was first published in the 'Mathematical Games' column by Martin Gardner in Scientific American.
Envy-free division for 4 or more players was a difficult open problem of the twentieth century. The first cake-cutting procedure that produced an envy-free division of cake for any number of persons was first published by Steven Brams and Alan Taylor in 1995.
A major advance on equitable division was made in 2006 by Steven J. Brams, Michael A. Jones, and Christian Klamler.
Read more about this topic: Fair Division
Famous quotes containing the word history:
“There is a constant in the average American imagination and taste, for which the past must be preserved and celebrated in full-scale authentic copy; a philosophy of immortality as duplication. It dominates the relation with the self, with the past, not infrequently with the present, always with History and, even, with the European tradition.”
—Umberto Eco (b. 1932)
“No matter how vital experience might be while you lived it, no sooner was it ended and dead than it became as lifeless as the piles of dry dust in a school history book.”
—Ellen Glasgow (1874–1945)
“Every library should try to be complete on something, if it were only the history of pinheads.”
—Oliver Wendell Holmes, Sr. (1809–1894)