書誌事項
- タイトル別名
-
- Cake Cutting for All-or-Nothing Utility
この論文をさがす
説明
<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>
収録刊行物
-
- 人工知能学会論文誌
-
人工知能学会論文誌 32 (5), AG16-E_1-9, 2017
一般社団法人 人工知能学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282680084847232
-
- NII論文ID
- 130006039485
-
- ISSN
- 13468030
- 13460714
-
- 本文言語コード
- ja
-
- 資料種別
- journal article
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可