Strategy-proof Cake Cutting Mechanisms for All-or-nothing Utility

• Autorzy: Ihara T. , Tsuruta S. , Todo T. , Sakurai Y. , Yokoo M.

Identyfikatory

DOI

10.3233/FI-2018-1641

• Języki publikacji: EN

Abstrakty

EN

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 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 and Pareto efficiency when each agent has all-or-nothing utility. We next propose two strategy-proof mechanisms that satisfy Pareto efficiency, which are based on the serial dictatorship mechanism, at the sacrifice of envy-freeness. 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 Pareto efficient allocation is NP-hard. As another approach that abandons Pareto efficiency, we develop an envy-free mechanism and show that one of our serial dictatorship based mechanisms satisfies proportionality in expectation, which is a weaker definition of proportionality. Finally, we evaluate the efficiency obtained by our proposed mechanisms by computational experiments.

Słowa kluczowe

EN

cake cutting; mechanism design; non-additive preference; strategy-proofness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 158, nr 1/3
• Strony: 41--61
• Opis fizyczny: Bibliogr. 20 poz., rys., tab., wykr.

Twórcy

autor

Ihara T.

• Graduate School of Information Science and Electrical Engineering, Kyushu University, Motooka 744, Nishi-ku, Fukuoka, 819-0375, Japan

autor

Tsuruta S.

• Graduate School of Information Science and Electrical Engineering, Kyushu University, Motooka 744, Nishi-ku, Fukuoka, 819-0375, Japan

autor

Todo T.

• Faculty of Information Science and Electrical Engineering, Kyushu University, Motooka 744, Nishi-ku, Fukuoka, 819-0375, Japan

autor

Sakurai Y.

• Faculty of Information Science and Electrical Engineering, Kyushu University, Motooka 744, Nishi-ku, Fukuoka, 819-0375, Japan

autor

Yokoo M.

• Faculty of Information Science and Electrical Engineering, Kyushu University, Motooka 744, Nishi-ku, Fukuoka, 819-0375, Japan

Bibliografia

• [1] Gamow G, Stern M. Puzzle-math. Macmillan; 1958. ISBN-10:0670583359, 13:978-0670583355.
• [2] Austin A. Sharing a cake. The Mathematical Gazette. 1982;66(437):212-215. doi:10.2307/3616548.
• [3] Chen Y, Lai JK, Parkes DC, Procaccia AD. Truth, justice, and cake cutting. Games and Economic Behavior. 2013;77(1):284-297. URL https://doi.org/10.1016/j.geb.2012.10.009.
• [4] Maya A, Nisan N. Incentive compatible two player cake cutting. In: Proceedings of the Eighth International Workshop on Internet and Network Economics (WINE 2012); 2012. p. 170-183. doi:10.1007/978-3-642-35311-6_13.
• [5] Mossel E, Tamuz O. Truthful fair division. In: Proceedings of the Third International Symposium on Algorithmic Game Theory (SAGT 2010); 2010. p. 288-299. doi:10.1007/978-3-642-16170-4_25.
• [6] Aziz H, Mackenzie S. A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents. Forty-eighth Annual Symposium on the Theory of Computing (STOC 2016); 2016. doi:10.1145/2897518.2897522.
• [7] Barbanel JB, Brams SJ. Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond. Mathematical Social Sciences. 2004;48(3):251-269. URL https://doi.org/10.1016/j.mathsocsci.2004.03.006.
• [8] Branzei S, Miltersen PB. Equilibrium analysis in cake cutting. In: Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems 2013 (AAMAS 2013); 2013. p. 327-334. ISBN:978-1-4503-1993-5.
• [9] Procaccia AD. Cake Cutting Algorithms. Handbook of Computational Social Choice. Cambridge University Press. 2016; p. 311-329.
• [10] Brams SJ, Jones MA, Klamler C. Better ways to cut a cake. Notices of the American Mathematical Society (AMS). 2006;53(11):1314-1321.
• [11] Tsuruta S, Oka M, Todo T, Sakurai Y, Yokoo M. Fairness and false-name manipulations in randomized cake cutting. In: Proceedings of the Fourteenth International Conference on Autonomous Agents and Multiagent Systems 2015 (AAMAS 2015); 2015. p. 909-917. ISBN: 978-1-4503-3413-6.
• [12] Caragiannis I, Lai JK, Procaccia AD. Towards more expressive cake cutting. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011). vol. 22; 2011. p.127-132.
• [13] Mirchandani RS. Superadditivity and subadditivity in fair division. Journal of Mathematics Research. 2013;5(3):78-91. URL http://dx.doi.org/10.5539/jmr.v5n3p78.
• [14] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (JACM). 1973;20(1):46-61. doi:10.1145/321738.321743.
• [15] Garey MR, Johnson DS. Two-processor scheduling with start-times and deadlines. SIAM Journal on Computing. 1977;6(3):416-426. URL https://doi.org/10.1137/0206029.
• [16] Carroll TE, Grosu D. Strategy proof mechanisms for scheduling divisible loads in bus-networked distributed systems. IEEE Transactions on Parallel and Distributed Systems. 2008;19(8):1124-1135. doi:10.1109/TPDS.2007.70818.
• [17] Mohsenian-Rad AH, Wong VW, Jatskevich J, Schober R, Leon-Garcia A. Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid. IEEE Transactions on Smart Grid. 2010;1(3):320-331. doi:10.1109/TSG.2010.2089069.
• [18] Abdulkadiroğlu A, Sönmez T. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica. 1998;66(3):689-701. URL http://hdl.handle.net/10161/1866.
• [19] Aziz H, Brandt F, Brill M. The computational complexity of random serial dictatorship. Economics Letters. 2013;121(3):341-345. URL https://doi.org/10.1016/j.econlet.2013.09.006.
• [20] Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M. The efficiency of fair division. Theory of Computing Systems. 2012;50(4):589-610. URL https://doi.org/10.1007/s00224-011-9359-y.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).