Truth, Justice and Cake Cutting

http://www.eecs.harvard.edu/econcs/pubs/Chen10.pdf

ارائه‌ی فردای جلسه‌ی الگوریتم. خوشمزه به نظر می‌رسه! ( این یکی از مسأله‌هاییه که هر دفعه می‌بینمش خوشحال میشم! :) )

Imagine a cake that must be divided between a group of gluttonous children. To complicate

matters, the cake is heterogeneous: two pieces of cake may differ in terms of their toppings, so

the children have different preferences over the pieces (one may weakly prefer a larger proportion

of chocolate curls, while another may single-mindedly desire the piece with the cherry).

In this lecture we discuss the surprisingly intricate problem of fairly dividing the cake — which

serves as a metaphor for heterogeneous divisible resources such as land or time.

From a computer scientist’s point of view, the cake cutting problem provides a sandbox in which

we can explore the role of computational thinking in the allocation of divisible goods. Indeed, the

elegant cake cutting model distills many of the issues we care about when studying divisible

goods more broadly; for example, how to reason about computational complexity in the face of

continuous inputs, and how to quantify the tradeoffs between individual fairness and global

welfare.