{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:52:13Z","timestamp":1764557533983},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Research Council","award":["639945"],"award-info":[{"award-number":["639945"]}]},{"name":"Stanford Graduate Fellowship"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc Choice Welf"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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<jats:italic>free disposal<\/jats:italic>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.<\/jats:p>","DOI":"10.1007\/s00355-020-01256-0","type":"journal-article","created":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T12:02:40Z","timestamp":1587816160000},"page":"523-545","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Truthful fair division without free disposal"],"prefix":"10.1007","volume":"55","author":[{"given":"Xiaohui","family":"Bei","sequence":"first","affiliation":[]},{"given":"Guangda","family":"Huzhang","sequence":"additional","affiliation":[]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,25]]},"reference":[{"key":"1256_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013318","DOI":"10.1609\/aaai.v31i1.10584"},{"key":"1256_CR2","unstructured":"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\u201337"},{"key":"1256_CR3","doi-asserted-by":"crossref","unstructured":"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\u2013562","DOI":"10.1145\/3033274.3085147"},{"key":"1256_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013427","DOI":"10.1109\/FOCS.2016.52"},{"key":"1256_CR5","doi-asserted-by":"crossref","unstructured":"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\u2013464","DOI":"10.1145\/2897518.2897522"},{"key":"1256_CR6","doi-asserted-by":"crossref","unstructured":"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\u201314","DOI":"10.1007\/978-3-319-13129-0_1"},{"key":"1256_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013781","DOI":"10.1145\/3328526.3329552"},{"key":"1256_CR8","unstructured":"Bade S (2015) Multilateral matching under dichotomous preferences. Working paper"},{"key":"1256_CR9","doi-asserted-by":"crossref","unstructured":"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\u20133631","DOI":"10.24963\/ijcai.2017\/507"},{"key":"1256_CR10","doi-asserted-by":"crossref","unstructured":"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\u201387","DOI":"10.24963\/ijcai.2019\/12"},{"issue":"2","key":"1256_CR11","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1006\/jeth.2000.2710","volume":"100","author":"A Bogomolnaia","year":"2001","unstructured":"Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ Theory 100(2):295\u2013328","journal-title":"J Econ Theory"},{"issue":"1","key":"1256_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1111\/j.1468-0262.2004.00483.x","volume":"72","author":"A Bogomolnaia","year":"2004","unstructured":"Bogomolnaia A, Moulin H (2004) Random matching under dichotomous preferences. Econometrica 72(1):257\u2013279","journal-title":"Econometrica"},{"issue":"2","key":"1256_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.jet.2004.05.005","volume":"122","author":"A Bogomolnaia","year":"2005","unstructured":"Bogomolnaia A, Moulin H, Stong R (2005) Collective choice under dichotomous preferences. J Econ Theory 122(2):165\u2013184","journal-title":"J Econ Theory"},{"issue":"1","key":"1256_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1995.11990526","volume":"102","author":"SJ Brams","year":"1995","unstructured":"Brams SJ, Taylor AD (1995) An envy-free cake division protocol. Am Math Mon 102(1):9\u201318","journal-title":"Am Math Mon"},{"key":"1256_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975","volume-title":"Fair division: from cake-cutting to dispute resolution","author":"SJ Brams","year":"1996","unstructured":"Brams SJ, Taylor AD (1996) Fair division: from cake-cutting to dispute resolution. Cambridge University Press, Cambridge"},{"key":"1256_CR16","unstructured":"Br\u00e2nzei S, Miltersen PB (2015) A dictatorship theorem for cake cutting. In: Proceedings of the 24th international joint conference on artificial intelligence, pp 482\u2013488"},{"issue":"4","key":"1256_CR17","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M (2011) The efficiency of fair division. Theory Comput Syst 50(4):589\u2013610","journal-title":"Theory Comput Syst"},{"key":"1256_CR18","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.geb.2012.10.009","volume":"77","author":"Y Chen","year":"2013","unstructured":"Chen Y, Lai JK, Parkes DC, Procaccia AD (2013) Truth, justice, and cake cutting. Games Econ Behav 77:284\u2013297","journal-title":"Games Econ Behav"},{"key":"1256_CR19","doi-asserted-by":"crossref","unstructured":"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\u20132583","DOI":"10.1137\/1.9781611975031.164"},{"issue":"1","key":"1256_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2311357","volume":"68","author":"LE Dubins","year":"1961","unstructured":"Dubins LE, Spanier EH (1961) How to cut a cake fairly. Am Math Mon 68(1):1\u201317","journal-title":"Am Math Mon"},{"key":"1256_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.mathsocsci.2014.10.005","volume":"73","author":"C Duddy","year":"2015","unstructured":"Duddy C (2015) Fair sharing under dichotomous preferences. Math Soc Sci 73:1\u20135","journal-title":"Math Soc Sci"},{"key":"1256_CR22","doi-asserted-by":"crossref","unstructured":"Farhadi A, Hajiaghayi M (2018) On the complexity of chore division. In: Proceedings of the 27th international joint conference on artificial intelligence, pp 226\u2013232","DOI":"10.24963\/ijcai.2018\/31"},{"key":"1256_CR23","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1609\/aaai.v34i02.5570"},{"key":"1256_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2015.05.041","volume":"593","author":"S Heydrich","year":"2015","unstructured":"Heydrich S, van Stee R (2015) Dividing connected chores fairly. Theor Comput Sci 593:51\u201361","journal-title":"Theor Comput Sci"},{"key":"1256_CR25","doi-asserted-by":"crossref","unstructured":"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\u2013561","DOI":"10.1609\/aaai.v27i1.8629"},{"key":"1256_CR26","doi-asserted-by":"crossref","unstructured":"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\u2013183","DOI":"10.1007\/978-3-642-35311-6_13"},{"key":"1256_CR27","unstructured":"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\u2013358"},{"key":"1256_CR28","doi-asserted-by":"crossref","unstructured":"Mossel E, Tamuz O (2010) Truthful fair division. In: Proceedings of the 3rd international symposium on algorithmic game theory, pp 288\u2013299","DOI":"10.1007\/978-3-642-16170-4_25"},{"key":"1256_CR29","volume-title":"Fair division and collective welfare","author":"H Moulin","year":"2004","unstructured":"Moulin H (2004) Fair division and collective welfare. MIT Press, Cambridge"},{"key":"1256_CR30","unstructured":"Peterson E, Su FE (1998) Exact procedures for envy-free chore division. Working paper"},{"issue":"2","key":"1256_CR31","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1080\/0025570X.2002.11953114","volume":"75","author":"E Peterson","year":"2002","unstructured":"Peterson E, Su FE (2002) Four-person envy-free chore division. Math Mag 75(2):117\u2013122","journal-title":"Math Mag"},{"key":"1256_CR32","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1017\/CBO9781107446984.014","volume-title":"Handbook of computational social choice, chapter 13","author":"AD Procaccia","year":"2016","unstructured":"Procaccia AD (2016) Cake cutting algorithms. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (eds) Handbook of computational social choice, chapter 13. Cambridge University Press, Cambridge, pp 311\u2013329"},{"key":"1256_CR33","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863855","volume-title":"Cake-cutting algorithms: be fair if you can","author":"J Robertson","year":"1998","unstructured":"Robertson J, Webb W (1998) Cake-cutting algorithms: be fair if you can. Peters\/CRC Press, Boca Raton"},{"issue":"1","key":"1256_CR34","first-page":"101","volume":"16","author":"H Steinhaus","year":"1948","unstructured":"Steinhaus H (1948) The problem of fair division. Econometrica 16(1):101\u2013104","journal-title":"Econometrica"},{"issue":"8","key":"1256_CR35","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1080\/00029890.1980.11995109","volume":"87","author":"W Stromquist","year":"1980","unstructured":"Stromquist W (1980) How to cut a cake fairly. Am Math Mon 87(8):640\u2013644","journal-title":"Am Math Mon"},{"issue":"10","key":"1256_CR36","doi-asserted-by":"publisher","first-page":"930","DOI":"10.2307\/2589747","volume":"106","author":"FE Su","year":"1999","unstructured":"Su FE (1999) Rental harmony: Sperner\u2019s lemma in fair division. Am Math Mon 106(10):930\u2013942","journal-title":"Am Math Mon"}],"container-title":["Social Choice and Welfare"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00355-020-01256-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00355-020-01256-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00355-020-01256-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T08:28:51Z","timestamp":1666427331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00355-020-01256-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,25]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["1256"],"URL":"https:\/\/doi.org\/10.1007\/s00355-020-01256-0","relation":{},"ISSN":["0176-1714","1432-217X"],"issn-type":[{"value":"0176-1714","type":"print"},{"value":"1432-217X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,25]]},"assertion":[{"value":"16 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}