{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T09:59:50Z","timestamp":1775815190943,"version":"3.50.1"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032085597","type":"print"},{"value":"9783032085603","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-08560-3_20","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:28:17Z","timestamp":1767320897000},"page":"348-365","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Logarithmic Comparison-Based Query Complexity for\u00a0Fair Division of\u00a0Indivisible Goods"],"prefix":"10.1007","author":[{"given":"Xiaolin","family":"Bu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zihao","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengxin","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaxin","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Biaoshuai","family":"Tao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Akrami, H., Garg, J.: Breaking the $$3\/4$$ barrier for approximate maximin share. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 74\u201391 (2024)","DOI":"10.1137\/1.9781611977912.4"},{"key":"20_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965","volume":"322","author":"G Amanatidis","year":"2023","unstructured":"Amanatidis, G., et al.: Fair division of indivisible goods: recent progress and open questions. Artif. Intell. 322, 103965 (2023)","journal-title":"Artif. Intell."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H., Caragiannis, I., Igarashi, A., Walsh, T.: Fair allocation of indivisible goods and chores. Auton. Agent. Multi-Agent Syst. 36(1), 3:1\u20133:21 (2022)","DOI":"10.1007\/s10458-021-09532-8"},{"key":"20_CR4","unstructured":"Aziz, H., Li, B., Xing, S., Zhou, Y.: Possible fairness for allocating indivisible resources. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 197\u2013205 (2023)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Aziz, H., Mackenzie, S.: A discrete and bounded envy-free cake cutting protocol for any number of agents. In: Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 416\u2013427 (2016)","DOI":"10.1109\/FOCS.2016.52"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Aziz, H., Mackenzie, S.: A discrete and bounded envy-free cake cutting protocol for four agents. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 454\u2013464 (2016)","DOI":"10.1145\/2897518.2897522"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Babichenko, Y.: Query complexity of approximate Nash equilibria. J. ACM 63(4) (2016)","DOI":"10.1145\/2908734"},{"key":"20_CR8","unstructured":"Benad\u00e8, G., Halpern, D., Psomas, A.: Dynamic fair division with partial information. In: Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 3703\u20133715 (2022)"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.geb.2021.11.006","volume":"131","author":"V Bil\u00f2","year":"2022","unstructured":"Bil\u00f2, V., et al.: Almost envy-free allocations with connected bundles. Games Econom. Behav. 131, 197\u2013221 (2022)","journal-title":"Games Econom. Behav."},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1995.11990526","volume":"102","author":"SJ Brams","year":"1995","unstructured":"Brams, S.J., Taylor, A.D.: An envy-free cake division protocol. Am. Math. Mon. 102(1), 9\u201318 (1995)","journal-title":"Am. Math. Mon."},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Br\u00e2nzei, S., Nisan, N.: Communication complexity of cake cutting. In: Proceedings of the ACM Conference on Economics and Computation (EC), p.\u00a0525 (2019)","DOI":"10.1145\/3328526.3329644"},{"key":"20_CR12","unstructured":"Br\u00e2nzei, S., Nisan, N.: The query complexity of cake cutting. In: Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 37905\u201337919 (2022)"},{"key":"20_CR13","unstructured":"Bu, X., Li, Z., Liu, S., Song, J., Tao, B.: On the complexity of maximizing social welfare within fair allocations of indivisible goods. arXiv preprint arXiv:2205.14296 (2022)"},{"key":"20_CR14","unstructured":"Bu, X., Li, Z., Liu, S., Song, J., Tao, B.: Logarithmic comparison-based query complexity for fair division of indivisible goods. arXiv preprint arXiv:2404.18133 (2024)"},{"issue":"6","key":"20_CR15","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061\u20131103 (2011)","journal-title":"J. Polit. Econ."},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"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), 1\u201332 (2019)","journal-title":"ACM Trans. Econ. Comput."},{"issue":"4","key":"20_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.disopt.2012.08.001","volume":"9","author":"K Cechl\u00e1rov\u00e1","year":"2012","unstructured":"Cechl\u00e1rov\u00e1, K., Pill\u00e1rov\u00e1, E.: On the computability of equitable divisions. Discret. Optim. 9(4), 249\u2013257 (2012)","journal-title":"Discret. Optim."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Conitzer, V., Freeman, R., Shah, N.: Fair public decision making. In: Proceedings of the ACM Conference on Economics and Computation (EC), pp. 629\u2013646 (2017)","DOI":"10.1145\/3033274.3085125"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Dubins, L.E., Spanier, E.H.: How to cut a cake fairly. Am. Math. Monthly 68(1P1), 1\u201317 (1961)","DOI":"10.1080\/00029890.1961.11989615"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Pruhs, K.: Cake cutting really is not a piece of cake. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 271\u2013278 (2006)","DOI":"10.1145\/1109557.1109588"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0166-218X(84)90005-2","volume":"7","author":"S Even","year":"1984","unstructured":"Even, S., Paz, A.: A note on cake cutting. Discret. Appl. Math. 7(3), 285\u2013296 (1984)","journal-title":"Discret. Appl. Math."},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Feige, U.: Low communication protocols for fair allocation of indivisible goods. arXiv preprint arXiv:2407.07641 (2024)","DOI":"10.1145\/3736252.3742553"},{"issue":"1","key":"20_CR23","first-page":"45","volume":"7","author":"DK Foley","year":"1967","unstructured":"Foley, D.K.: Resource allocation and the public sector. Yale Econ. Essays 7(1), 45\u201398 (1967)","journal-title":"Yale Econ. Essays"},{"issue":"3","key":"20_CR24","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1287\/moor.2020.1096","volume":"46","author":"M Ghodsi","year":"2021","unstructured":"Ghodsi, M., Hajiaghayi, M.T., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods: improvement. Math. Oper. Res. 46(3), 1038\u20131053 (2021)","journal-title":"Math. Oper. Res."},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Halpern, D., Shah, N.: Fair and efficient resource allocation with partial information. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 224\u2013230 (2021)","DOI":"10.24963\/ijcai.2021\/32"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Kurokawa, D., Lai, J., Procaccia, A.: How to cut a cake before the party ends. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 555\u2013561 (2013)","DOI":"10.1609\/aaai.v27i1.8629"},{"key":"20_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 ACM Conference on Electronic Commerce (EC), pp. 125\u2013131 (2004)","DOI":"10.1145\/988772.988792"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Nisan, N.: The demand query model for bipartite matching. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 592\u2013599 (2021)","DOI":"10.1137\/1.9781611976465.36"},{"issue":"2","key":"20_CR29","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1137\/20M1313349","volume":"35","author":"H Oh","year":"2021","unstructured":"Oh, H., Procaccia, A.D., Suksompong, W.: Fairly allocating many goods with few queries. SIAM J. Discret. Math. 35(2), 788\u2013813 (2021)","journal-title":"SIAM J. Discret. Math."},{"key":"20_CR30","doi-asserted-by":"crossref","unstructured":"Onak, K., Sun, X.: The query complexity of graph isomorphism: bypassing distribution testing lower bounds. In: Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 165\u2013171 (2018)","DOI":"10.1145\/3188745.3188952"},{"issue":"2","key":"20_CR31","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."},{"issue":"1","key":"20_CR32","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1137\/19M1244305","volume":"49","author":"B Plaut","year":"2020","unstructured":"Plaut, B., Roughgarden, T.: Communication complexity of discrete fair division. SIAM J. Comput. 49(1), 206\u2013243 (2020)","journal-title":"SIAM J. Comput."},{"key":"20_CR33","unstructured":"Procaccia, A.D.: Thou shalt covet thy neighbor\u2019s cake. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 239\u2013244 (2009)"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., Wang, J.: Fair enough: Guaranteeing approximate maximin shares. In: Proceedings of the ACM Conference on Economics and Computation (EC), pp. 675\u2013692 (2014)","DOI":"10.1145\/2600057.2602835"},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., Wang, J.: A lower bound for equitable cake cutting. In: Proceedings of the ACM Conference on Economics and Computation (EC), pp. 479\u2013495 (2017)","DOI":"10.1145\/3033274.3085107"},{"key":"20_CR36","doi-asserted-by":"crossref","unstructured":"Robertson, J., Webb, W.: Cake-Cutting algorithms: be fair if you can. Peters\/CRC Press (1998)","DOI":"10.1201\/9781439863855"},{"issue":"1","key":"20_CR37","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":"20_CR38","doi-asserted-by":"publisher","first-page":"315","DOI":"10.2307\/1907319","volume":"17","author":"H Steinhaus","year":"1949","unstructured":"Steinhaus, H.: Sur la division pragmatique. Econometrica 17, 315\u2013319 (1949)","journal-title":"Econometrica"},{"issue":"8","key":"20_CR39","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1080\/00029890.1980.11995109","volume":"87","author":"W Stromquist","year":"1980","unstructured":"Stromquist, W.: How to cut a cake fairly. Am. Math. Mon. 87(8), 640\u2013644 (1980)","journal-title":"Am. Math. Mon."},{"key":"20_CR40","doi-asserted-by":"crossref","unstructured":"Stromquist, W.: Envy-free cake divisions cannot be found by finite protocols. Electr. J. Comb. 15(1), #R11 (2008)","DOI":"10.37236\/735"},{"key":"20_CR41","doi-asserted-by":"crossref","unstructured":"Varian, H.R.: Equity, envy, and efficiency (1973)","DOI":"10.1016\/0042-207X(73)92318-X"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-08560-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T02:28:20Z","timestamp":1767320900000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-08560-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032085597","9783032085603"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-08560-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edinburgh","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wine2024.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}