Cake Cutting Algorithms
Cake Cutting Algorithms
复制标题
DOI：
10.1017/cbo9781107446984.014
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ariel D. Procaccia
中科院分区：
文献类型：
--
作者：
Ariel D. Procaccia
想象一下，一块蛋糕必须分给一群贪吃的孩子。更复杂的是，蛋糕是异质的：两块蛋糕的配料可能不同，因此孩子们对这些蛋糕有不同的偏好（一个可能更喜欢更大比例的巧克力卷，而另一个可能一心一意地想要带有樱桃的蛋糕）。在本章中，我们讨论公平分配蛋糕这一令人惊讶的复杂问题——这是土地或时间等异构可分割资源的隐喻。切蛋糕问题有着悠久而传奇的历史，例如在 Brams 和 Taylor (1996) 以及 Robertson 和 Webb (1998) 的书中。对该问题的早期研究有两个主题：存在结果表明可以实现一定的公平保证；以及显示如何实现此类保证的算法结果。本章的重点是后一个主题，它具有更多的计算风味。从计算机科学家的角度来看，切蛋糕问题提供了一个沙箱，我们可以在其中探索计算思维在可分割商品分配中的作用。事实上，优雅的蛋糕切割模型（第 13.2 节）提炼了我们在更广泛地研究可分割商品时关心的许多问题；例如，如何在面对连续输入时推理计算复杂性，以及如何量化个人公平与全球福利之间的权衡。
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 prefer a larger proportion of chocolate curls, while another may single-mindedly desire the piece with the cherry). In this chapter 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. The cake cutting problem has a long and storied history described, e.g., in the books by Brams and Taylor (1996) and Robertson and Webb (1998). The early research on the problem has two main themes: existence results showing that certain fairness guarantees can be achieved; and algorithmic results showing how such guarantees can be achieved. The focus of this chapter is on the latter theme, which has a more computational flavor. 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 (Section 13.2) 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.