{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,16]],"date-time":"2025-11-16T02:25:09Z","timestamp":1763259909136,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031710322"},{"type":"electronic","value":"9783031710339"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-71033-9_29","type":"book-chapter","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:02:17Z","timestamp":1725321737000},"page":"520-537","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of\u00a0Round-Robin Allocation with\u00a0Potentially Noisy Queries"],"prefix":"10.1007","author":[{"given":"Zihan","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Scarlett","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":[[2024,8,31]]},"reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"103965","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":"29_CR2","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Fusco, F., Lazos, P., Leonardi, S., Reiffenh\u00e4user, R.: Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness. In: Proceedings of the 17th International Conference on Web and Internet Economics (WINE), pp. 149\u2013166 (2021)","DOI":"10.1007\/978-3-030-94676-0_9"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H.: Developments in multi-agent fair allocation. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 13563\u201313568 (2020)","DOI":"10.1609\/aaai.v34i09.7082"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.artint.2019.08.002","volume":"276","author":"H Aziz","year":"2019","unstructured":"Aziz, H., Bir\u00f3, P., de Haan, R., Rastegari, B.: Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity. Artif. Intell. 276, 57\u201378 (2019)","journal-title":"Artif. Intell."},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Aziz, H., Bouveret, S., Lang, J., Mackenzie, S.: Complexity of manipulating sequential allocation. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 328\u2013334 (2017)","DOI":"10.1609\/aaai.v31i1.10586"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.artint.2015.06.002","volume":"227","author":"H Aziz","year":"2015","unstructured":"Aziz, H., Gaspers, S., Mackenzie, S., Walsh, T.: Fair assignment of indivisible objects under ordinal preferences. Artif. Intell. 227, 71\u201392 (2015)","journal-title":"Artif. Intell."},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Bai, Y., G\u00f6lz, P.: Envy-free and Pareto-optimal allocations for agents with asymmetric random valuations. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 53\u201359 (2022)","DOI":"10.24963\/ijcai.2022\/8"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Hassidim, A.: The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 221\u2013230 (2008)","DOI":"10.1109\/FOCS.2008.58"},{"issue":"4","key":"29_CR9","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR10","unstructured":"Bouveret, S., Lang, J.: Manipulating picking sequences. In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), pp. 141\u2013146 (2014)"},{"issue":"2","key":"29_CR11","first-page":"130","volume":"61","author":"SJ Brams","year":"2014","unstructured":"Brams, S.J., Kilgour, D.M., Klamler, C.: Two-person fair division of indivisible items: an efficient, envy-free algorithm. Not. AMS 61(2), 130\u2013141 (2014)","journal-title":"Not. AMS"},{"key":"29_CR12","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, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Braverman, M., Mao, J., Weinberg, S.M.: Parallel algorithms for select and partition with noisy comparisons. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pp. 851\u2013862 (2016)","DOI":"10.1145\/2897518.2897642"},{"key":"29_CR14","doi-asserted-by":"crossref","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)","DOI":"10.1145\/3355902"},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"103578","DOI":"10.1016\/j.artint.2021.103578","volume":"301","author":"M Chakraborty","year":"2021","unstructured":"Chakraborty, M., Schmidt-Kraepelin, U., Suksompong, W.: Picking sequences and monotonicity in weighted fair division. Artif. Intell. 301, 103578 (2021)","journal-title":"Artif. Intell."},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Mallmann-Trenn, F., Mathieu, C.: Instance-optimality in the noisy value-and comparison-model. In: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2124\u20132143 (2020)","DOI":"10.1137\/1.9781611975994.131"},{"key":"29_CR17","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Davidson, S., Khanna, S., Milo, T., Roy, S.: Top-k and clustering with noisy comparisons. ACM Trans. Database Syst. 39(4), 35:1\u201335:39 (2014)","DOI":"10.1145\/2684066"},{"key":"29_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":"5","key":"29_CR20","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"key":"29_CR21","unstructured":"Gan, J., Wirth, A., Zhang, X.: An almost optimal algorithm for unbounded search with noisy information. In: Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 25:1\u201325:15 (2022)"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"Gu, Y., Xu, Y.: Optimal bounds for noisy sorting. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 1502\u20131515 (2023)","DOI":"10.1145\/3564246.3585131"},{"issue":"2","key":"29_CR23","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF00565647","volume":"1","author":"J Kahn","year":"1984","unstructured":"Kahn, J., Saks, M.: Balancing poset extensions. Order 1(2), 113\u2013126 (1984)","journal-title":"Order"},{"key":"29_CR24","unstructured":"Kaufmann, E., Capp\u00e9, O., Garivier, A.: On the complexity of best-arm identification in multi-armed bandit models. J. Mach. Learn. Res. 17(1), 1:1\u20131:42 (2016)"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"Kurokawa, D., Procaccia, A.D., Wang, J.: When can the maximin share guarantee be guaranteed? In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 523\u2013529 (2016)","DOI":"10.1609\/aaai.v30i1.10041"},{"key":"29_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401","volume-title":"Bandit Algorithms","author":"T Lattimore","year":"2020","unstructured":"Lattimore, T., Szepesv\u00e1ri, C.: Bandit Algorithms. Cambridge University Press, Cambridge (2020)"},{"key":"29_CR27","doi-asserted-by":"crossref","unstructured":"Li, Z., Manurangsi, P., Scarlett, J., Suksompong, W.: Complexity of round-robin allocation with potentially noisy queries. arXiv preprint arXiv:2404.19402 (2024)","DOI":"10.1007\/978-3-031-71033-9_29"},{"key":"29_CR28","unstructured":"Li, Z., Bei, X., Yan, Z.: Proportional allocation of indivisible resources under ordinal and uncertain preferences. In: Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1148\u20131157 (2022)"},{"issue":"3","key":"29_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 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"29_CR30","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1137\/20M1353381","volume":"35","author":"P Manurangsi","year":"2021","unstructured":"Manurangsi, P., Suksompong, W.: Closing gaps in asymptotic fair division. SIAM J. Discret. Math. 35(2), 668\u2013706 (2021)","journal-title":"SIAM J. Discret. Math."},{"key":"29_CR31","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1146\/annurev-economics-080218-025559","volume":"11","author":"H Moulin","year":"2019","unstructured":"Moulin, H.: Fair division in the internet age. Annu. Rev. Econ. 11, 407\u2013441 (2019)","journal-title":"Annu. Rev. Econ."},{"issue":"2","key":"29_CR32","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."},{"issue":"2","key":"29_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."},{"issue":"1","key":"29_CR34","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0097-3165(81)90053-4","volume":"31","author":"RP Stanley","year":"1981","unstructured":"Stanley, R.P.: Two combinatorial applications of the Aleksandrov-Fenchel inequalities. J. Combin. Theory Ser. A 31(1), 56\u201365 (1981)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"1","key":"29_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"},{"issue":"2","key":"29_CR36","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3505156.3505162","volume":"19","author":"W Suksompong","year":"2021","unstructured":"Suksompong, W.: Constraints in fair division. ACM SIGecom Exchanges 19(2), 46\u201361 (2021)","journal-title":"ACM SIGecom Exchanges"},{"key":"29_CR37","doi-asserted-by":"crossref","unstructured":"Walsh, T.: Fair division: the computer scientist\u2019s perspective. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4966\u20134972 (2020)","DOI":"10.24963\/ijcai.2020\/691"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71033-9_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T17:54:14Z","timestamp":1732730054000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71033-9_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031710322","9783031710339"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71033-9_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"31 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","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":"3 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cwi.nl\/en\/groups\/networks-and-optimization\/events\/sagt-2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}