×

Truthful fair division without free disposal. (English) Zbl 1454.91103

Summary: We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful and envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional constraints are imposed on the mechanisms. Moreover, we provide bounds on the efficiency of mechanisms satisfying various properties, and give truthful mechanisms for multiple agents with restricted classes of valuations.

MSC:

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alijani R, Farhadi M, Ghodsi M, Seddighin M, Tajik AS (2017) Envy-free mechanisms with minimum number of cuts. In: Proceedings of the 31st AAAI conference on artificial intelligence, pp 312-318 · Zbl 1426.91148
[2] Amanatidis G, Birmpas G, Markakis E (2016) On truthful mechanisms for maximin share allocations. In: Proceedings of the 25th international joint conference on artificial intelligence, pp 31-37 · Zbl 1406.91153
[3] Amanatidis G, Birmpas G, Christodoulou G, Markakis E (2017) Truthful allocation mechanisms without payments: characterization and implications on fairness. In: Proceedings of the 18th ACM conference on economics and computation, pp 545-562
[4] Aziz H, Mackenzie S (2016a) A discrete and bounded envy-free cake cutting protocol for any number of agents. In: Proceedings of the 57th annual symposium on foundations of computer science, pp 416-427 · Zbl 1373.68251
[5] Aziz H, Mackenzie S (2016b) A discrete and bounded envy-free cake cutting protocol for four agents. In: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, pp 454-464 · Zbl 1373.68251
[6] Aziz H, Ye C (2014) Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In: Proceedings of the 10th international conference on web and internet economics, pp 1-14 · Zbl 1406.91212
[7] Aziz H, Bogomolnaia A, Moulin H (2019) Fair mixing: the case of dichotomous preferences. In: Proceedings of the 20th ACM conference on economics and computation, pp 753-781
[8] Bade S (2015) Multilateral matching under dichotomous preferences. Working paper
[9] Bei X, Chen N, Huzhang G, Tao B, Wu J (2017) Cake cutting: envy and truth. In: Proceedings of the 26th international joint conference on artificial intelligence, pp 3625-3631
[10] Bei X, Lu X, Manurangsi P, Suksompong W (2019) The price of fairness for indivisible goods. In: Proceedings of the 28th international joint conference on artificial intelligence, pp 81-87
[11] Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J Econ Theory, 100, 2, 295-328 (2001) · Zbl 1134.91357 · doi:10.1006/jeth.2000.2710
[12] Bogomolnaia, A.; Moulin, H., Random matching under dichotomous preferences, Econometrica, 72, 1, 257-279 (2004) · Zbl 1142.91691 · doi:10.1111/j.1468-0262.2004.00483.x
[13] Bogomolnaia, A.; Moulin, H.; Stong, R., Collective choice under dichotomous preferences, J Econ Theory, 122, 2, 165-184 (2005) · Zbl 1112.91048 · doi:10.1016/j.jet.2004.05.005
[14] Brams, SJ; Taylor, AD, An envy-free cake division protocol, Am Math Mon, 102, 1, 9-18 (1995) · Zbl 0824.90142 · doi:10.1080/00029890.1995.11990526
[15] Brams, SJ; Taylor, AD, Fair division: from cake-cutting to dispute resolution (1996), Cambridge: Cambridge University Press, Cambridge · Zbl 0991.91019
[16] Brânzei S, Miltersen PB (2015) A dictatorship theorem for cake cutting. In: Proceedings of the 24th international joint conference on artificial intelligence, pp 482-488
[17] Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M., The efficiency of fair division, Theory Comput Syst, 50, 4, 589-610 (2011) · Zbl 1262.91099 · doi:10.1007/s00224-011-9359-y
[18] Chen, Y.; Lai, JK; Parkes, DC; Procaccia, AD, Truth, justice, and cake cutting, Games Econ Behav, 77, 284-297 (2013) · Zbl 1274.91262 · doi:10.1016/j.geb.2012.10.009
[19] Dehghani S, Farhadi A, Hajiaghayi M, Yami H (2018) Envy-free chore division for an arbitrary number of agents. In: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, pp 2564-2583 · Zbl 1403.91207
[20] Dubins, LE; Spanier, EH, How to cut a cake fairly, Am Math Mon, 68, 1, 1-17 (1961) · Zbl 0108.31601 · doi:10.2307/2311357
[21] Duddy, C., Fair sharing under dichotomous preferences, Math Soc Sci, 73, 1-5 (2015) · Zbl 1310.91081 · doi:10.1016/j.mathsocsci.2014.10.005
[22] Farhadi A, Hajiaghayi M (2018) On the complexity of chore division. In: Proceedings of the 27th international joint conference on artificial intelligence, pp 226-232
[23] Goldberg PW, Hollender A, Suksompong W (2020) Contiguous cake cutting: Hardness results and approximation algorithms. In: Proceedings of the 34th AAAI conference on artificial intelligence (forthcoming) · Zbl 1490.68242
[24] Heydrich, S.; van Stee, R., Dividing connected chores fairly, Theor Comput Sci, 593, 51-61 (2015) · Zbl 1331.91107 · doi:10.1016/j.tcs.2015.05.041
[25] Kurokawa D, Lai JK, Procaccia AD (2013) How to cut a cake before the party ends. In: Proceedings of the 27th AAAI conference on artificial intelligence, pp 555-561
[26] Maya A, Nisan N (2012) Incentive compatible two player cake cutting. In: Proceedings of the 8th international workshop on internet and network economics, pp 170-183
[27] Menon V, Larson K (2017) Deterministic, strategy proof, and fair cake cutting. In: Proceedings of the 26th international joint conference on artificial intelligence, pp 352-358
[28] Mossel E, Tamuz O (2010) Truthful fair division. In: Proceedings of the 3rd international symposium on algorithmic game theory, pp 288-299 · Zbl 1310.91083
[29] Moulin, H., Fair division and collective welfare (2004), Cambridge: MIT Press, Cambridge
[30] Peterson E, Su FE (1998) Exact procedures for envy-free chore division. Working paper
[31] Peterson, E.; Su, FE, Four-person envy-free chore division, Math Mag, 75, 2, 117-122 (2002) · Zbl 1079.90633 · doi:10.1080/0025570X.2002.11953114
[32] Procaccia, AD; Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, AD, Cake cutting algorithms, Handbook of computational social choice, chapter 13, 311-329 (2016), Cambridge: Cambridge University Press, Cambridge · Zbl 1448.91139
[33] Robertson, J.; Webb, W., Cake-cutting algorithms: be fair if you can (1998), Boca Raton: Peters/CRC Press, Boca Raton · Zbl 0939.91001
[34] Steinhaus, H., The problem of fair division, Econometrica, 16, 1, 101-104 (1948)
[35] Stromquist, W., How to cut a cake fairly, Am Math Mon, 87, 8, 640-644 (1980) · Zbl 0441.90002 · doi:10.1080/00029890.1980.11995109
[36] Su, FE, Rental harmony: Sperner’s lemma in fair division, Am Math Mon, 106, 10, 930-942 (1999) · Zbl 1010.05077 · doi:10.2307/2589747
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.