{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T00:21:04Z","timestamp":1759191664271,"version":"3.44.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032060778","type":"print"},{"value":"9783032060785","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T00:00:00Z","timestamp":1759190400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T00:00:00Z","timestamp":1759190400000},"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-06078-5_22","type":"book-chapter","created":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T18:50:37Z","timestamp":1759171837000},"page":"380-397","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bandit Max-Min Fair Allocation"],"prefix":"10.1007","author":[{"given":"Tsubasa","family":"Harada","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shinji","family":"Ito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanna","family":"Sumita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,30]]},"reference":[{"issue":"09","key":"22_CR1","first-page":"13557","volume":"34","author":"M Aleksandrov","year":"2020","unstructured":"Aleksandrov, M., Walsh, T.: Online fair division: a survey. Proc. AAAI Conf. Artif. Intell. 34(09), 13557\u201313562 (2020)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"issue":"1","key":"22_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theor. Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theor. Comput."},{"issue":"7","key":"22_CR3","doi-asserted-by":"publisher","first-page":"2970","DOI":"10.1137\/080723491","volume":"39","author":"A Asadpour","year":"2010","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput. 39(7), 2970\u20132989 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"22_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.2013.0598","volume":"39","author":"JY Audibert","year":"2014","unstructured":"Audibert, J.Y., Bubeck, S., Lugosi, G.: Regret in online combinatorial optimization. Math. Oper. Res. 39(1), 31\u201345 (2014)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539701398375","volume":"32","author":"P Auer","year":"2002","unstructured":"Auer, P., Cesa-Bianchi, N., Freund, Y., Schapire, R.E.: The nonstochastic multiarmed bandit problem. SIAM J. Comput. 32(1), 48\u201377 (2002)","journal-title":"SIAM J. Comput."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Kleinberg, R., Slivkins, A.: Bandits with knapsacks. J. ACM 65(3), 13:1\u201313:55 (2018)","DOI":"10.1145\/3164539"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Gkatzelis, V., Gorokh, A., Jin, B.: Online nash social welfare maximization with predictions. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1\u201319 (2022)","DOI":"10.1137\/1.9781611977073.1"},{"key":"22_CR8","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, pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Barman, S., Khan, A., Maiti, A.: Universal and tight online algorithms for generalized-mean welfare. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a036, pp. 4793\u20134800 (2022)","DOI":"10.1609\/aaai.v36i5.20406"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Benade, G., Kazachkov, A.M., Procaccia, A.D., Psomas, C.A.: How to make envy vanish over time. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 593\u2013610 (2018)","DOI":"10.1145\/3219166.3219179"},{"key":"22_CR11","unstructured":"Besson, L., Kaufmann, E.: What doubling tricks can and can\u2019t do for multi-armed bandits. arXiv preprint arXiv:1803.06971 (2018)"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Bez\u00e1kov\u00e1, I., Dani, V.: Allocating Indivisible Goods. ACM SIGecom Exchanges 5(3), 11\u201318 (2005)","DOI":"10.1145\/1120680.1120683"},{"issue":"2","key":"22_CR13","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1109\/JSAIT.2021.3073065","volume":"2","author":"I Bistritz","year":"2021","unstructured":"Bistritz, I., Baharav, T.Z., Leshem, A., Bambos, N.: One for all and all for one: distributed learning of fair allocations with multi-player bandits. IEEE J. Sel. Areas Inf. Theor. 2(2), 584\u2013598 (2021)","journal-title":"IEEE J. Sel. Areas Inf. Theor."},{"issue":"137","key":"22_CR14","first-page":"1","volume":"25","author":"E Boursier","year":"2024","unstructured":"Boursier, E., Perchet, V.: A survey on multi-player bandits. J. Mach. Learn. Res. 25(137), 1\u201345 (2024)","journal-title":"J. Mach. Learn. Res."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair allocation of indivisible goods. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, chap.\u00a012, pp. 284\u2013310. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781107446984.013"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Prediction and playing games. In: Prediction, Learning, and Games, chap.\u00a07, pp. 180\u2013232. Cambridge University Press (2006)","DOI":"10.1017\/CBO9780511546921.008"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"key":"22_CR18","unstructured":"Chen, W., Wang, Y., Yuan, Y.: Combinatorial multi-armed bandit: general framework and applications. In: Proceedings of the 30th International Conference on Machine Learning, pp. 151\u2013159 (2013)"},{"key":"22_CR19","unstructured":"Chen, Y., Cuellar, A., Luo, H., Modi, J., Nemlekar, H., Nikolaidis, S.: The fair contextual multi-armed bandit. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1810\u20131812 (2020)"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Claure, H., Chen, Y., Modi, J., Jung, M., Nikolaidis, S.: Multi-armed bandits with fairness constraints for distributing resources to human teammates. In: Proceedings of the 2020 ACM\/IEEE International Conference on Human-Robot Interaction, pp. 299\u2013308 (2020)","DOI":"10.1145\/3319502.3374806"},{"key":"22_CR21","unstructured":"Cohen, S., Agmon, N.: Near-optimal online resource allocation in the random-order model. In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 2219\u20132221 (2024)"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1), 7:1\u20137:41 (2019)","DOI":"10.1145\/3284177"},{"key":"22_CR23","unstructured":"Feige, U.: On allocations that maximize fairness. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 287\u2013293 (2008)"},{"key":"22_CR24","unstructured":"Golovin, D.: Max-min fair allocation of indivisible goods. Technical Report CMU-CS-05-144, Carnegie Mellon University (2005)"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the lov\u00e1sz local lemma. J. ACM 58(6), 28:1\u201328:28 (2011)","DOI":"10.1145\/2049697.2049702"},{"key":"22_CR26","unstructured":"Hajiaghayi, M., Khani, M., Panigrahi, D., Springer, M.: Online algorithms for the Santa Claus problem. In: Advances in Neural Information Processing Systems 35, vol.\u00a035, pp. 30732\u201330743 (2022)"},{"key":"22_CR27","unstructured":"Harada, T., Ito, S., Sumita, H.: Bandit max-min fair allocation. arXiv preprint arXiv:2505.05169 (2025)"},{"key":"22_CR28","first-page":"24005","volume":"34","author":"S Hossain","year":"2021","unstructured":"Hossain, S., Micha, E., Shah, N.: Fair algorithms for multi-agent multi-armed bandits. Adv. Neural. Inf. Process. Syst. 34, 24005\u201324017 (2021)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Lackner, M., Nardi, O., Novaro, A.: Repeated fair allocation of indivisible items. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence, pp. 9781\u20139789 (2024)","DOI":"10.1609\/aaai.v38i9.28837"},{"issue":"7","key":"22_CR30","first-page":"8159","volume":"37","author":"M Jones","year":"2023","unstructured":"Jones, M., Nguyen, H., Nguyen, T.: An efficient algorithm for fair multi-agent multi-armed bandit with low regret. Proc. AAAI Conf. Artif. Intell. 37(7), 8159\u20138167 (2023)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Sumita, H.: Online max-min fair allocation. In: Proceedings of International Symposium on Algorithmic Game Theory, pp. 526\u2013543 (2022)","DOI":"10.1007\/978-3-031-15714-1_30"},{"issue":"1","key":"22_CR32","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/0196-8858(85)90002-8","volume":"6","author":"T Lai","year":"1985","unstructured":"Lai, T., Robbins, H.: Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1), 4\u201322 (1985)","journal-title":"Adv. Appl. Math."},{"key":"22_CR33","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"issue":"3","key":"22_CR34","doi-asserted-by":"publisher","first-page":"1799","DOI":"10.1109\/TNSE.2019.2954310","volume":"7","author":"F Li","year":"2019","unstructured":"Li, F., Liu, J., Ji, B.: Combinatorial sleeping bandits with fairness constraints. IEEE Trans. Netw. Sci. Eng. 7(3), 1799\u20131813 (2019)","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"22_CR35","doi-asserted-by":"crossref","unstructured":"Micheel, K.J., Wilczynski, A.: Fairness in repeated house allocation. In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 2390\u20132392 (2024)","DOI":"10.3233\/FAIA240909"},{"issue":"174","key":"22_CR36","first-page":"1","volume":"22","author":"V Patil","year":"2021","unstructured":"Patil, V., Ghalme, G., Nair, V., Narahari, Y.: Achieving fairness in the stochastic multi-armed bandit problem. J. Mach. Learn. Res. 22(174), 1\u201331 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"22_CR37","unstructured":"Zhang, M., Deo-Campo\u00a0Vuong, R., Luo, H.: No-regret learning for fair multi-agent social welfare optimization. In: Advances in Neural Information Processing Systems, vol.\u00a037, pp. 57671\u201357700 (2024)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases. Research Track"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-06078-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T18:50:45Z","timestamp":1759171845000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-06078-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,30]]},"ISBN":["9783032060778","9783032060785"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-06078-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,30]]},"assertion":[{"value":"30 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Porto","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ecmlpkdd.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}