Problem
This problem was borrowed from the CS Department's Automata class.
Suppose there are five students, ranked according to their grades, and 100 candy
bars for distribution among the students.
The best student is given a chance to choose the distribution among the students
(for example, (20,20,20,20,20) would have the bars distributed evenly). Then the
students vote. If greater than 50 percent of the students vote to veto the
distribution, the top student is eliminated and the next best student proposes
a distribution among the remaining four students.
We assume the students are completely rational (they would choose even one candy
bar over 0) and always act to maximize the number of candy bars they will
recieve. They are also spiteful and would like that the other students recieve
0 candy bars.
What will the first student propose? That failing, what will the second student
propose?
The first student will propose a distribution of (98,0,1,0,1).
The second student will propose a distribution of (99,0,1,0).
The third, given the chance, would propose (99, 0, 1).
The fourth would propose (100, 0) and could never lose-- with just his vote it
passes.
(Why? Email Vanessa or Christopher...)