Cake Cutting: Envy and Truth

Cake Cutting: Envy and Truth

Xiaohui Bei, Ning Chen, Guangda Huzhang, Biaoshuai Tao, Jiajun Wu

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 3625-3631. https://doi.org/10.24963/ijcai.2017/507

We study envy-free cake cutting with strategic agents, where each agent may manipulate his private information in order to receive a better allocation. We focus on piecewise constant utility functions and consider two scenarios: the general setting without any restriction on the allocations and the restricted setting where each agent has to receive a connected piece. We show that no deterministic truthful envy-free mechanism exists in the connected piece scenario, and the same impossibility result for the general setting with some additional mild assumptions on the allocations. Finally, we study a large market model where the economy is replicated and demonstrate that truth-telling converges to a Nash equilibrium.
Keywords:
Multidisciplinary Topics and Applications: AI and Social Sciences
Knowledge Representation, Reasoning, and Logic: Game Theory
Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems
Agent-based and Multi-agent Systems: Social Choice Theory