Truth, justice, and cake cutting

• 成果类型: Article
• 署名作者: Chen, Yiling; Lai, John K.; Parkes, David C.; Procaccia, Ariel D.
• 署名单位: Harvard University; Carnegie Mellon University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2012.10.009
• 发表日期: 2013
• 页码: 284-297
• 关键词: fair division; Envy-freeness; Cake cutting; maximum flows; strategy-proofness; mechanism design

摘要

Cake cutting is a common metaphor for the division of a heterogeneous divisible good. There are numerous papers that study the problem of fairly dividing a cake; a small number of them also take into account self-interested agents and consequent strategic issues, but these papers focus on fairness and consider a strikingly weak notion of truthfulness. In this paper we investigate the problem of cutting a cake in a way that is truthful, Pareto-efficient, and fair, where for the first time our notion of dominant strategy truthfulness is the ubiquitous one in social choice and computer science. We design both deterministic and randomized cake cutting mechanisms that are truthful and fair under different assumptions with respect to the valuation functions of the agents. (c) 2012 Elsevier Inc. All rights reserved.