{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:38:57Z","timestamp":1787323137585,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-16-1-3075"],"award-info":[{"award-number":["N00014-16-1-3075"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2428"],"award-info":[{"award-number":["N00014-17-1-2428"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["639945"],"award-info":[{"award-number":["639945"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005851","name":"John Simon Guggenheim Memorial Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005851","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1350598"],"award-info":[{"award-number":["IIS-1350598"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1714140"],"award-info":[{"award-number":["IIS-1714140"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1525932"],"award-info":[{"award-number":["CCF-1525932"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1733556"],"award-info":[{"award-number":["CCF-1733556"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1813188"],"award-info":[{"award-number":["CCF-1813188"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010863","name":"Stanford Graduate School of Education","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010863","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic utilities, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive utilities and that a polylogarithmic bound holds for three agents with monotonic utilities. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envy-freeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive utilities.<\/jats:p>","DOI":"10.1137\/20m1313349","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T11:34:12Z","timestamp":1618486452000},"page":"788-813","source":"Crossref","is-referenced-by-count":9,"title":["Fairly Allocating Many Goods with Few Queries"],"prefix":"10.1137","volume":"35","author":[{"given":"Hoon","family":"Oh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel D.","family":"Procaccia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"G. Amanatidis, G. Birmpas, and E. Markakis,\n                      Comparing approximate relaxations of envy-freeness\n                      , in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018, pp. 42-48.","DOI":"10.24963\/ijcai.2018\/6"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"G. Amanatidis, G. Christodoulou, J. Fearnley, E. Markakis, C.A. Psomas, and E. Vakaliou,\n                      An improved envy-free cake cutting protocol for four agents\n                      , in Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), 2018, pp. 87-99.","DOI":"10.1007\/978-3-319-99660-8_9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"H. Aziz and S. Mackenzie,\n                      A discrete and bounded envy-free cake cutting protocol for any number of agents\n                      , in Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), 2016, pp. 416-427.","DOI":"10.1109\/FOCS.2016.52"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"H. Aziz and S. Mackenzie,\n                      A discrete and bounded envy-free cake cutting protocol for four agents\n                      , in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016, pp. 454-464.","DOI":"10.1145\/2897518.2897522"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/3381525"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"S. Barman, S. K. Krisnamurthy, and R. Vaish,\n                      Finding fair and efficient allocations\n                      , in Proceedings of the 19th ACM Conference on Economics and Computation (EC), 2018, pp. 557-574.","DOI":"10.1145\/3219166.3219176"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"X. Bei, A. Igarashi, X. Lu, and W. Suksompong,\n                      The price of connectivity in fair division\n                      , in Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021, forthcoming.","DOI":"10.1609\/aaai.v35i6.16651"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"X. Bei, X. Lu, P. Manurangsi, and W. Suksompong,\n                      The price of fairness for indivisible goods\n                      , in Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019, pp. 81-87.","DOI":"10.24963\/ijcai.2019\/12"},{"key":"atypb10","unstructured":"V. Bil\u00f2, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters, C. Vinci, and W. S. Zwicker,\n                      Almost envy-free allocations with connected bundles\n                      , in Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), 2019, pp. 14:1-14:21."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"A. Biswas and S. Barman,\n                      Fair division under cardinality constraints\n                      , in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018, pp. 91-97.","DOI":"10.24963\/ijcai.2018\/13"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"S. Bouveret, K. Cechl\u00e1rov\u00e1, E. Elkind, A. Igarashi, and D. Peters,\n                      Fair division of a graph\n                      , in Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017, pp. 135-141.","DOI":"10.24963\/ijcai.2017\/20"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1995.11990526"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. J. Brams and A. D. Taylor,\n                      Fair Division: From Cake-Cutting to Dispute Resolution\n                      , Cambridge University Press, Cambridge, 1996.","DOI":"10.1017\/CBO9780511598975"},{"key":"atypb16","unstructured":"S. Br\u00e2nzei and N. Nisan,\n                      The Query Complexity of Cake Cutting\n                      , CoRR, abs\/1705.02946, 2017."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"I. Caragiannis, N. Gravin, and X. Huang,\n                      Envy-freeness up to any item with high Nash welfare: The virtue of donating items\n                      , in Proceedings of the 20th ACM Conference on Economics and Computation (EC), 2019, pp. 527-545.","DOI":"10.1145\/3328526.3329574"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. Chakraborty, A. Igarashi, W. Suksompong, and Y. Zick,\n                      Weighted envy-freeness in indivisible item allocation\n                      , in Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020, pp. 231-239.","DOI":"10.65109\/XYWL8760"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1116"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000819"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"E. Elkind, E. Segal-Halevi, and W. Suksompong,\n                      Mind the gap: Cake cutting with separation\n                      , in Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021, forthcoming.","DOI":"10.1609\/aaai.v35i6.16672"},{"key":"atypb24","first-page":"45","volume":"7","author":"Foley D.","year":"1967","journal-title":"Yale Econ. Essays"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"M. Ghodsi, M. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami,\n                      Fair allocation of indivisible goods: Improvement and generalization\n                      , in Proceedings of the 19th ACM Conference on Economics and Computation (EC), 2018, pp. 539-556.","DOI":"10.1145\/3219166.3219238"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/2728732.2728738"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"D. Kurokawa, J. K. Lai, and A. D. Procaccia,\n                      How to cut a cake before the party ends\n                      , in Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 2013, pp. 555-561.","DOI":"10.1609\/aaai.v27i1.8629"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.008"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi,\n                      On approximately fair allocations of indivisible goods\n                      , in Proceedings of the 6th ACM Conference on Economics and Computation (EC), 2004, pp. 125-131.","DOI":"10.1145\/988772.988792"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"H. Moulin,\n                      Fair Division and Collective Welfare\n                      , MIT Press, Cambridge, MA, 2003.","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/19M1244305"},{"key":"atypb34","unstructured":"A. D. Procaccia,\n                      Thou shalt covet thy neighbor's cake\n                      , in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), 2009, pp. 239-244."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/2483852.2483870"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"A. D. Procaccia and J. Wang,\n                      A lower bound for equitable cake cutting\n                      , in Proceedings of the 18th ACM Conference on Economics and Computation (EC), 2017, pp. 479-495.","DOI":"10.1145\/3033274.3085107"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"J. M. Robertson and W. A. Webb,\n                      Cake Cutting Algorithms: Be Fair If You Can\n                      , A. K. Peters, Natick, MA, 1998.","DOI":"10.1201\/9781439863855"},{"key":"atypb38","first-page":"101","volume":"16","author":"Steinhaus H.","year":"1948","journal-title":"Econometrica"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1980.11995109"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.036"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.03.039"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1313349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:43:59Z","timestamp":1787319839000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1313349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1313349"],"URL":"https:\/\/doi.org\/10.1137\/20m1313349","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}