International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong


Invited Speakers

Track H

Truthful Cake Sharing

Xinhang Lu

University of New South Wales

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.
Joint work with Xiaohui Bei and Warut Suksompong

Xinhang is currently a postdoc hosted by Toby Walsh at the University of New South Wales, Australia. Prior to this, she was a postdoc with Warut Suksompong at the National University of Singapore, a PhD student under the supervision of Xiaohui Bei at Nanyang Technological University, and an undergraduate at Southeast University. She is broadly interested in problems at the interface between computer science and economics. Recently, her work has focused on resource allocation and mechanism design.