{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T13:27:00Z","timestamp":1778851620600,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T00:00:00Z","timestamp":1616976000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T00:00:00Z","timestamp":1616976000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["Start-up Grant"],"award-info":[{"award-number":["Start-up Grant"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1815434"],"award-info":[{"award-number":["CCF-1815434"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["639945"],"award-info":[{"award-number":["639945"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s00224-021-10039-8","type":"journal-article","created":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T15:02:55Z","timestamp":1617030175000},"page":"1069-1093","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["The Price of Fairness for Indivisible Goods"],"prefix":"10.1007","volume":"65","author":[{"given":"Xiaohui","family":"Bei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinhang","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,29]]},"reference":[{"key":"10039_CR1","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Markakis, E.: Comparing approximate relaxations of envy-freeness. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp 42\u201348 (2018)","DOI":"10.24963\/ijcai.2018\/6"},{"key":"10039_CR2","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2020.07.006","volume":"841","author":"G Amanatidis","year":"2020","unstructured":"Amanatidis, G., Ntokos, A., Markakis, E.: Multiple birds with one stone: Beating 1\/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. 841, 94\u2013109 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10039_CR3","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2781776","volume":"3","author":"Y Aumann","year":"2015","unstructured":"Aumann, Y., Dombb, Y.: The efficiency of fair division with connected pieces. ACM Trans. Econ. Comput. 3(4), 23:1\u201323:16 (2015)","journal-title":"ACM Trans. Econ. Comput."},{"key":"10039_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"10039_CR5","doi-asserted-by":"crossref","unstructured":"Barman, S., Bhaskar, U., Shah, N.: Settling the price of fairness for indivisible goods. In: Proceedings of the 16th Conference on Web and Internet Economics (WINE), pp. 356\u2013369 (2020)","DOI":"10.1007\/978-3-030-64946-3_25"},{"issue":"1","key":"10039_CR6","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/3381525","volume":"8","author":"S Barman","year":"2020","unstructured":"Barman, S., Krishnamurthy, S.K.: Approximation algorithms for maximin fair division. ACM Trans. Econ. Comput. 8(1), 5:1\u20135:28 (2020)","journal-title":"ACM Trans. Econ. Comput."},{"key":"10039_CR7","doi-asserted-by":"crossref","unstructured":"Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp 81\u201387 (2019)","DOI":"10.24963\/ijcai.2019\/12"},{"key":"10039_CR8","doi-asserted-by":"crossref","unstructured":"Benabbou, N., Chakraborty, M., Igarashi, A., Zick, Y.: Finding fair and efficient allocations when valuations don\u2019t add up. In: Proceedings of the 13th International Symposium on Algorithmic Game Theory, SAGT, pp 32\u201346 (2020)","DOI":"10.1007\/978-3-030-57980-7_3"},{"key":"10039_CR9","unstructured":"B\u00e9rczi, K., B\u00e9rczi-Kov\u00e1cs, E.R., Boros, E., Gedefa, F.T., Kamiyama, N., Kavitha, T., Kobayashi, Y., Makino, K.: Envy-free relaxations for goods, chores, and mixed items. arXiv:2006.04428 (2020)"},{"issue":"1","key":"10039_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/opre.1100.0865","volume":"59","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17\u201331 (2011)","journal-title":"Oper. Res."},{"issue":"3","key":"10039_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I Bez\u00e1kov\u00e1","year":"2005","unstructured":"Bez\u00e1kov\u00e1, I., Dani, V.: Allocating indivisible goods. ACM SIGecom. Exchanges. 5(3), 11\u201318 (2005)","journal-title":"ACM SIGecom. Exchanges."},{"key":"10039_CR12","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2015.10.046","volume":"613","author":"V Bil\u00f2","year":"2016","unstructured":"Bil\u00f2, V., Fanelli, A., Flammini, M., Monaco, G., Moscardelli, L.: The price of envy-freeness in machine scheduling. Theor. Comput. Sci. 613, 65\u201378 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"10039_CR13","doi-asserted-by":"crossref","unstructured":"Biswas, A., Barman, S.: Fair division under cardinality constraints. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp 91\u201397 (2018)","DOI":"10.24963\/ijcai.2018\/13"},{"issue":"1","key":"10039_CR14","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.: Random matching under dichotomous preferences. Econometrica 72(1), 257\u2013279 (2004)","journal-title":"Econometrica"},{"key":"10039_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, S.J., Taylor, D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)"},{"issue":"4","key":"10039_CR16","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory. Comput. Syst. 50(4), 589\u2013610 (2012)","journal-title":"Theory. Comput. Syst."},{"issue":"3","key":"10039_CR17","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/3355902","volume":"7","author":"I Caragiannis","year":"2019","unstructured":"Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. 7(3), 12:1\u201312:32 (2019)","journal-title":"ACM Trans. Econ. Comput."},{"key":"10039_CR18","doi-asserted-by":"crossref","unstructured":"Chaudhury, B.R., Garg, J., Mehlhorn, K.: EFX exists for three agents. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp 1\u201319 (2020)","DOI":"10.1145\/3391403.3399511"},{"key":"10039_CR19","doi-asserted-by":"crossref","unstructured":"Dickerson, J.P., Goldman, J., Karp, J., Procaccia, A.D., Sandholm, T.: The computational rise and fall of fairness. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pp 1405\u20131411 (2014)","DOI":"10.1609\/aaai.v28i1.8884"},{"issue":"1","key":"10039_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2311357","volume":"68","author":"LE Dubins","year":"1961","unstructured":"Dubins, L.E., Spanier, E.H.: How to cut a cake fairly. Am. Math. Mon. 68(1), 1\u201317 (1961)","journal-title":"Am. Math. Mon."},{"key":"10039_CR21","doi-asserted-by":"crossref","unstructured":"Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods Improvement and generalization. In: Proceedings of the 19th ACM Conference on Economics and Computation (EC), pp 539\u2013556 (2018)","DOI":"10.1145\/3219166.3219238"},{"key":"10039_CR22","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.: Dividing connected chores fairly. Theor. Comput. Sci. 593, 51\u201361 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"10039_CR23","first-page":"11:1","volume":"6","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A.D., Shah, N.: Leximin allocations in the real world. ACM Trans. Econ. Comput. 6(3\u20134), 11:1\u201311:24 (2018a)","journal-title":"ACM Trans. Econ. Comput."},{"issue":"2","key":"10039_CR24","first-page":"8:1","volume":"64","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A.D., Wang, J.: Fair enough: Guaranteeing approximate maximin shares. J. ACM 64(2), 8:1\u20138:27 (2018b)","journal-title":"J. ACM"},{"key":"10039_CR25","doi-asserted-by":"crossref","unstructured":"Kurz, S.: The price of fairness for a small number of indivisible items. In: Operations Research Proceedings, pp 335\u2013340 (2014)","DOI":"10.1007\/978-3-319-28697-6_47"},{"key":"10039_CR26","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.tcs.2020.07.008","volume":"841","author":"M Kyropoulou","year":"2020","unstructured":"Kyropoulou, M., Suksompong, W., Voudouris, A.A.: Almost envy-freeness in group resource allocation. Theor. Comput. Sci. 841, 110\u2013123 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"10039_CR27","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pp 125\u2013131 (2004)","DOI":"10.1145\/988772.988792"},{"key":"10039_CR28","doi-asserted-by":"crossref","unstructured":"Manurangsi, P., Suksompong, W.: Closing gaps in asymptotic fair division. arXiv:2004.05563 (2020a)","DOI":"10.1137\/20M1353381"},{"issue":"3","key":"10039_CR29","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1137\/19M1279125","volume":"34","author":"P Manurangsi","year":"2020","unstructured":"Manurangsi, P., Suksompong, W.: When do envy-free allocations exist? SIAM J. Discret. Math. 34(3), 1505\u20131521 (2020b)","journal-title":"SIAM J. Discret. Math."},{"key":"10039_CR30","unstructured":"Markakis, E.: Approximation algorithms and hardness results for fair division. In: Ulle, E. (ed.) Trends in Computational Social Choice, chapter 12. AI Access, pp 231\u2013247 (2017)"},{"key":"10039_CR31","doi-asserted-by":"crossref","unstructured":"Michorzewski, M., Peters, D., Skowron, P.: Price of fairness in budget division and probabilistic social choice. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp 2184\u20132191 (2020)","DOI":"10.1609\/aaai.v34i02.5594"},{"key":"10039_CR32","doi-asserted-by":"crossref","unstructured":"Oh, H., Procaccia, A.D., Suksompong, W.: Fairly allocating many goods with few queries. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp 2141\u20132148 (2019)","DOI":"10.1609\/aaai.v33i01.33012141"},{"issue":"2","key":"10039_CR33","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/19M124397X","volume":"34","author":"B Plaut","year":"2020","unstructured":"Plaut, B., Roughgarden, T.: Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2), 1039\u20131068 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"10039_CR34","doi-asserted-by":"publisher","first-page":"103167","DOI":"10.1016\/j.artint.2019.103167","volume":"277","author":"E Segal-Halevi","year":"2019","unstructured":"Segal-Halevi, E., Suksompong, W.: Democratic fair allocation of indivisible goods. Artif. Intell. 277, 103167 (2019)","journal-title":"Artif. Intell."},{"issue":"1","key":"10039_CR35","first-page":"101","volume":"16","author":"H Steinhaus","year":"1948","unstructured":"Steinhaus, H.: The problem of fair division. Econometrica 16(1), 101\u2013104 (1948)","journal-title":"Econometrica"},{"key":"10039_CR36","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.mathsocsci.2017.09.004","volume":"92","author":"W Suksompong","year":"2018","unstructured":"Suksompong, W.: Approximate maximin shares for groups of agents. Math. Soc. Sci. 92, 40\u201347 (2018)","journal-title":"Math. Soc. Sci."},{"key":"10039_CR37","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.dam.2019.01.036","volume":"260","author":"W Suksompong","year":"2019","unstructured":"Suksompong, W.: Fairly allocating contiguous blocks of indivisible items. Discret. Appl. Math. 260, 227\u2013236 (2019)","journal-title":"Discret. Appl. Math."},{"key":"10039_CR38","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/j.dam.2020.03.039","volume":"284","author":"W Suksompong","year":"2020","unstructured":"Suksompong, W.: On the number of almost envy-free allocations. Discret. Appl. Math. 284, 606\u2013610 (2020)","journal-title":"Discret. Appl. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10039-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10039-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10039-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T19:54:48Z","timestamp":1671738888000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10039-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,29]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10039"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10039-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,29]]},"assertion":[{"value":"27 February 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}