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.
دریافت