{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T04:29:40Z","timestamp":1783484980566,"version":"3.55.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"content-version":"vor","delay-in-days":369,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ONR MURI","award":["N000142412742"],"award-info":[{"award-number":["N000142412742"]}]},{"DOI":"10.13039\/501100006374","name":"DOD U.S. Department of Defense","doi-asserted-by":"publisher","award":["NDSEG"],"award-info":[{"award-number":["NDSEG"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ARO MURI","award":["W911NF-19-1-0217"],"award-info":[{"award-number":["W911NF-19-1-0217"]}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-19-1-0183,FA9550-23-1-0068"],"award-info":[{"award-number":["FA9550-19-1-0183,FA9550-23-1-0068"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["ECCS-1847393,CNS-195599"],"award-info":[{"award-number":["ECCS-1847393,CNS-195599"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,3,6]]},"abstract":"<jats:p>Dynamic max-min fair allocation (DMMF) is a simple and popular mechanism for the repeated allocation of a shared resource among competing agents: in each round, each agent can choose to request or not for the resource, which is then allocated to the requesting agent with the least number of allocations received till then. Recent work has shown that under DMMF, a simple threshold-based request policy enjoys surprisingly strong robustness properties, wherein each agent can realize a significant fraction of her optimal utility irrespective of how other agents' behave. While this goes some way in mitigating the possibility of a 'tragedy of the commons' outcome, the robust policies require that an agent defend against arbitrary (possibly adversarial) behavior by other agents. This however may be far from optimal compared to real world settings, where other agents are selfish optimizers rather than adversaries. Therefore, robust guarantees give no insight on how agents behave in an equilibrium, and whether outcomes are improved under one.<\/jats:p>\n          <jats:p>\n            Our work aims to bridge this gap by studying the existence and properties of equilibria under DMMF. To this end, we first show that despite the strong robustness guarantees of the threshold based strategies,\n            <jats:italic toggle=\"yes\">no Nash equilibrium exists<\/jats:italic>\n            when agents participate in DMMF, each using some fixed threshold-based policy. On the positive side, however, we show that for the symmetric case, a simple data-driven request policy guarantees that no agent benefits from deviating to a different fixed threshold policy. In our proposed policy agents aim to match the historical allocation rate with a vanishing drift towards the rate optimizing overall welfare for all users. Furthermore, the resulting equilibrium outcome can be significantly better compared to what follows from the robustness guarantees.\n          <\/jats:p>\n          <jats:p>Our results are built on a complete characterization of the steady-state distribution under DMMF, as well as new techniques for analyzing strategic agent outcomes under dynamic allocation mechanisms; we hope these may prove of independent interest in related problems.<\/jats:p>","DOI":"10.1145\/3711695","type":"journal-article","created":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T16:05:24Z","timestamp":1741622724000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-7229-3338","authenticated-orcid":false,"given":"Chido","family":"Onyeze","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8954-4578","authenticated-orcid":false,"given":"Siddhartha","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4920-478X","authenticated-orcid":false,"given":"Giannis","family":"Fikioris","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2978-1475","authenticated-orcid":false,"given":"\u00c9va","family":"Tardos","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1820"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597723"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3606376.3593558"},{"key":"e_1_2_1_4_1","volume-title":"Near-Optimal Mechanisms for Resource Allocation Without Monetary Transfers. arXiv preprint arXiv:2408.10066","author":"Blanchard Moise","year":"2024","unstructured":"Moise Blanchard and Patrick Jaillet. 2024. Near-Optimal Mechanisms for Resource Allocation Without Monetary Transfers. arXiv preprint arXiv:2408.10066 (2024)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/378420.378438"},{"key":"e_1_2_1_6_1","volume-title":"A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing systems","author":"Bonald Thomas","year":"2006","unstructured":"Thomas Bonald, Laurent Massouli\u00e9, Alexandre Proutiere, and Jorma Virtamo. 2006. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing systems, Vol. 53 (2006), 65--84."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745869"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1544"},{"key":"e_1_2_1_9_1","volume-title":"International conference on Autonomous Agents and Multi-Agent Systems, AAMAS '14","author":"Cavallo Ruggiero","year":"2014","unstructured":"Ruggiero Cavallo. 2014. Incentive compatible two-tiered resource allocation without money. In International conference on Autonomous Agents and Multi-Agent Systems, AAMAS '14, Paris, France, May 5--9, 2014, Ana L. C. Bazzan, Michael N. Huhns, Alessio Lomuscio, and Paul Scerri (Eds.). IFAAMAS\/ACM, Paris, France, 1313--1320. http:\/\/dl.acm.org\/citation.cfm?id=2617457"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13235-023-00503-0"},{"key":"e_1_2_1_11_1","volume-title":"Kenan Zhang, John Lygeros, and Florian D\u00f6rfler.","author":"Elokda Ezzat","year":"2022","unstructured":"Ezzat Elokda, Carlo Cenedese, Kenan Zhang, John Lygeros, and Florian D\u00f6rfler. 2022. CARMA: Fair and efficient bottleneck congestion management with karma. arXiv preprint arXiv:2208.07113 (2022)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-71033-9_7"},{"key":"e_1_2_1_13_1","volume-title":"Online resource sharing via dynamic max-min fairness: efficiency, robustness and non-stationarity. arXiv preprint arXiv:2310.08881","author":"Fikioris Giannis","year":"2023","unstructured":"Giannis Fikioris, Siddhartha Banerjee, and \u00c9va Tardos. 2023. Online resource sharing via dynamic max-min fairness: efficiency, robustness and non-stationarity. arXiv preprint arXiv:2310.08881 (2023)."},{"key":"e_1_2_1_14_1","volume-title":"Dynamic Proportional Sharing: A Game-Theoretic Approach. In Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018","author":"Freeman Rupert","year":"2018","unstructured":"Rupert Freeman, Seyed Majid Zahedi, Vincent Conitzer, and Benjamin C. Lee. 2018. Dynamic Proportional Sharing: A Game-Theoretic Approach. In Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018, Irvine, CA, USA, June 18--22, 2018. ACM, Irvine, CA, USA, 33--35."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3587250"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011","author":"Ghodsi Ali","year":"2011","unstructured":"Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. 2011. Dominant Resource Fairness: Fair Allocation of Multiple Resource Types. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011, Boston, MA, USA, March 30 - April 1, 2011, David G. Andersen and Sylvia Ratnasamy (Eds.). USENIX Association, Boston, MA, USA."},{"key":"e_1_2_1_17_1","first-page":"170","article-title":"A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points","volume":"3","author":"Glicksberg Irving L","year":"1952","unstructured":"Irving L Glicksberg. 1952. A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proc. Amer. Math. Soc., Vol. 3, 1 (1952), 170--174.","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085140"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467560"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626334"},{"key":"e_1_2_1_21_1","volume-title":"GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Grandl Robert","year":"2016","unstructured":"Robert Grandl, Srikanth Kandula, Sriram Rao, Aditya Akella, and Janardhan Kulkarni. 2016. GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2--4, 2016. USENIX Association, Savannah, GA, USA, 81--97. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/grandl_graphene"},{"key":"e_1_2_1_22_1","volume-title":"9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010","volume":"3","author":"Guo Mingyu","year":"2010","unstructured":"Mingyu Guo and Vincent Conitzer. 2010. Strategy-proof allocation of multiple items between two agents without payments or priors. In 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10--14, 2010, Volume 1--3. IFAAMAS, Toronto, Canada, 881--888."},{"key":"e_1_2_1_23_1","volume-title":"Rational queueing","author":"Hassin Refael","unstructured":"Refael Hassin. 2016. Rational queueing. CRC press."},{"key":"e_1_2_1_24_1","volume-title":"To queue or not to queue: Equilibrium behavior in queueing systems","author":"Hassin Refael","unstructured":"Refael Hassin and Moshe Haviv. 2003. To queue or not to queue: Equilibrium behavior in queueing systems. Vol. 59. Springer Science & Business Media."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2007.00737.x"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2233213"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600523"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229075"},{"key":"e_1_2_1_29_1","volume-title":"Moment conditions for a sequence with negative drift to be uniformly bounded in Lr. Stochastic Processes and their Applications","author":"Pemantle Robin","year":"1999","unstructured":"Robin Pemantle and Jeffrey S Rosenthal. 1999. Moment conditions for a sequence with negative drift to be uniformly bounded in Lr. Stochastic Processes and their Applications, Vol. 82, 1 (1999), 143--155."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1086\/720332"},{"key":"e_1_2_1_31_1","volume-title":"Foundations and Trends\u00ae in Networking","volume":"2","author":"Shakkottai Srinivas","year":"2008","unstructured":"Srinivas Shakkottai, Rayadurgam Srikant, et al. 2008. Network optimization and control. Foundations and Trends\u00ae in Networking, Vol. 2, 3 (2008), 271--379."},{"key":"e_1_2_1_32_1","volume-title":"Performance Isolation and Fairness for Multi-Tenant Cloud Storage. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","author":"Shue David","year":"2012","unstructured":"David Shue, Michael J. Freedman, and Anees Shaikh. 2012. Performance Isolation and Fairness for Multi-Tenant Cloud Storage. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8--10, 2012, Chandu Thekkath and Amin Vahdat (Eds.). USENIX Association, Hollywood, CA, USA, 349--362. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/shue"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547353.3526951"},{"key":"e_1_2_1_34_1","volume-title":"Karma: Resource Allocation for Dynamic Demands. In 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023","author":"Vuppalapati Midhul","year":"2023","unstructured":"Midhul Vuppalapati, Giannis Fikioris, Rachit Agarwal, Asaf Cidon, Anurag Khandelwal, and \u00c9va Tardos. 2023. Karma: Resource Allocation for Dynamic Demands. In 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023, Boston, MA, USA, July 10--12, 2023. USENIX Association, Boston, MA, USA, 645--662."},{"key":"e_1_2_1_35_1","first-page":"25644","article-title":"Optimal Efficiency-Envy Trade-Off via Optimal Transport","volume":"35","author":"Yin Steven","year":"2022","unstructured":"Steven Yin and Christian Kroer. 2022. Optimal Efficiency-Envy Trade-Off via Optimal Transport. Advances in Neural Information Processing Systems (NeurIPS), Vol. 35 (2022), 25644--25654.","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711695","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711695","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:24:24Z","timestamp":1755915864000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,6]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,6]]}},"alternative-id":["10.1145\/3711695"],"URL":"https:\/\/doi.org\/10.1145\/3711695","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,6]]},"assertion":[{"value":"2025-03-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}