Cake Cutting for All-or-Nothing Utility

DOI Web Site 12 References Open Access
  • Ihara Takamasa
    Graduate School of Information Science and Electrical Engineering, Kyushu University
  • Todo Taiki
    Faculty of Information Science and Electrical Engineering, Kyushu University
  • Sakurai Yuko
    Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology
  • Yokoo Makoto
    Faculty of Information Science and Electrical Engineering, Kyushu University

Bibliographic Information

Other Title
  • 二値効用下でのケーキ分割問題

Description

<p>The cake cutting problem is concerned with the fair allocation of a divisible good among agents whose preferences vary over it. Recently, designing strategy-proof (SP) cake cutting mechanisms has caught considerable attention from AI and MAS researchers. Previous works assumed that an agent’s utility function is additive so that theoretical analysis becomes tractable. However, in practice, agents have non-additive utility over a resource. In this paper, we consider the all-or-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for such real-world resources as the usage of meeting rooms, time slots for computational resources, bandwidth usage, and so on. We first show the incompatibility between envy-freeness (EF) and Pareto efficiency (PE) when each agent has all-or-nothing utility. We next propose a SP mechanism that satisfy PE, which is based on the serial dictatorship mechanism, at the sacrifice of EF. To address computational feasibility, we propose a heuristic-based allocation algorithm to find a near-optimal allocation in time polynomial in the number of agents, since the problem of finding a PE allocation is NP-hard. As another approach that abandons PE, we develop an EF and SP mechanism. Furthermore, we argue about false-name-proofness (FNP), which is the expansion of SP, and propose FNP and EF cake cutting mechanism. Finally, we evaluate our proposed mechanisms by computational experiments.</p>

Journal

References(12)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top