{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:26Z","timestamp":1750221146784,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,4,3]],"date-time":"2018-04-03T00:00:00Z","timestamp":1522713600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1149252 CCF-1337215 SHF-1527610 AF-1408784 CCF-133721","IIS-1527434"],"award-info":[{"award-number":["CCF-1149252 CCF-1337215 SHF-1527610 AF-1408784 CCF-133721","IIS-1527434"]}],"id":[{"id":"10.13039\/100000001","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":[[2018,4,3]]},"abstract":"<jats:p>Sharing computational resources amortizes cost and improves utilization and efficiency. When agents pool their resources together, each becomes entitled to a portion of the shared pool. Static allocations in each round can guarantee entitlements and are strategy-proof, but efficiency suffers because allocations do not reflect variations in agents' demands for resources across rounds. Dynamic allocation mechanisms assign resources to agents across multiple rounds while guaranteeing agents their entitlements. Designing dynamic mechanisms is challenging, however, when agents are strategic and can benefit by misreporting their demands for resources.<\/jats:p>\n          <jats:p>\n            In this paper, we show that dynamic allocation mechanisms based on max-min fail to guarantee entitlements, strategy-proofness or both. We propose the\n            <jats:italic>fbp<\/jats:italic>\n            (\n            <jats:italic>FBPA<\/jats:italic>\n            ) mechanism and show that it satisfies strategy-proofness and guarantees at least half of the utility from static allocations while providing an asymptotic efficiency guarantee. Our simulations with real and synthetic data show that the performance of the\n            <jats:italic>fbp<\/jats:italic>\n            mechanism is comparable to that of state-of-the-art mechanisms, providing agents with at least 0.98x, and on average 15x, of their utility from static allocations. Finally, we propose the\n            <jats:italic>T<\/jats:italic>\n            -period mechanism and prove that it satisfies strategy-proofness and guarantees entitlements.\n          <\/jats:p>","DOI":"10.1145\/3179406","type":"journal-article","created":{"date-parts":[[2018,4,4]],"date-time":"2018-04-04T12:11:45Z","timestamp":1522843905000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic Proportional Sharing"],"prefix":"10.1145","volume":"2","author":[{"given":"Rupert","family":"Freeman","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seyed Majid","family":"Zahedi","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Conitzer","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin C.","family":"Lee","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1257\/mic.5.2.213"},{"key":"e_1_2_1_2_1","unstructured":"Martin Aleksandrov Haris Aziz Serge Gaspers and Toby Walsh. 2015. Online Fair Division: Analysing a Food Bank Problem Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI). 2540--2546.   Martin Aleksandrov Haris Aziz Serge Gaspers and Toby Walsh. 2015. Online Fair Division: Analysing a Food Bank Problem Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI). 2540--2546."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171650"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/2696363"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2007.443"},{"key":"e_1_2_1_6_1","first-page":"147","article-title":"Tres observaciones sobre el algebra lineal. Univ. Nac","volume":"5","author":"Birkhoff Garrett","year":"1946","journal-title":"Tucum\u00e1n Rev. Ser. A"},{"volume-title":"Apollo: Scalable and coordinated scheduling for cloud-scale computing Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation (OSDI)","year":"2014","author":"Boutin Eric","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/75247.75248"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085123"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2377677.2377679"},{"key":"e_1_2_1_11_1","volume-title":"Dominant Resource Fairness: Fair Allocation of Multiple Resource Types Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI)","volume":"11","author":"Ghodsi Ali","year":"2011"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465387"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Artur Gorokh Siddhartha Banerjee and Krishnamurthy Iyer. 2016. Near-Efficient Allocation Using Artificial Currency in Repeated Settings. (2016).  Artur Gorokh Siddhartha Banerjee and Krishnamurthy Iyer. 2016. Near-Efficient Allocation Using Artificial Currency in Repeated Settings. (2016).","DOI":"10.2139\/ssrn.2852895"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Artur Gorokh Siddhartha Banerjee and Krishnamurthy Iyer. 2017. From Monetary to Non-Monetary Mechanism Design Via Artificial Currencies. (2017).  Artur Gorokh Siddhartha Banerjee and Krishnamurthy Iyer. 2017. From Monetary to Non-Monetary Mechanism Design Via Artificial Currencies. (2017).","DOI":"10.1145\/3033274.3085140"},{"volume-title":"Demand Based Hierarchical QoS Using Storage Resource Pools USENIX Annual Technical Conference. 1--13","year":"2012","author":"Gulati Ajay","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_23"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1984.tb00068.x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750423.2750439"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/35043.35047"},{"key":"e_1_2_1_20_1","unstructured":"Lawrence Berkeley National Laboratory. 2017. National Energy Research Scientific Computing Center. https:\/\/www.nersc.gov. (2017).  Lawrence Berkeley National Laboratory. 2017. National Energy Research Scientific Computing Center. https:\/\/www.nersc.gov. (2017)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.234856"},{"key":"e_1_2_1_22_1","unstructured":"Charles Reiss John Wilkes and Joseph L. Hellerstein. 2011. Google cluster-usage traces: format  Charles Reiss John Wilkes and Joseph L. Hellerstein. 2011. Google cluster-usage traces: format"},{"volume-title":"Technical Report","year":"2014","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Thomas Sandholm and Kevin Lai. 2010. Dynamic proportional share scheduling in Hadoop. Job scheduling strategies for parallel processing. Springer 110--131.   Thomas Sandholm and Kevin Lai. 2010. Dynamic proportional share scheduling in Hadoop. Job scheduling strategies for parallel processing. Springer 110--131.","DOI":"10.1007\/978-3-642-16505-4_7"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI)","volume":"11","author":"Shieh Alan","year":"2011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597652.2597672"},{"key":"e_1_2_1_27_1","unstructured":"Duke University. 2017. The Duke Compute Cluster. http:\/\/rc.duke.edu\/the-duke-compute-cluster\/. (2017).  Duke University. 2017. The Duke Compute Cluster. http:\/\/rc.duke.edu\/the-duke-compute-cluster\/. (2017)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741964"},{"volume-title":"Lottery Scheduling: Flexible Proportional-Share Resource Management Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI). 1--11","author":"Carl","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Toby Walsh. 2011. Online cake cutting Proceedings of the Second International Conference on Algorithmic Decision Theory (ADT). Springer 292--305.   Toby Walsh. 2011. Online cake cutting Proceedings of the Second International Conference on Algorithmic Decision Theory (ADT). Springer 292--305.","DOI":"10.1007\/978-3-642-24873-3_22"},{"volume-title":"XChange: Scalable Dynamic Multi-Resource Allocation in Multicore Architectures Proceedings of the 21st IEEE International Symposium on High Performance Computer Architecture (HPCA).","year":"2015","author":"Wang Xiaodong","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541962"}],"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\/3179406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179406","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:17Z","timestamp":1750208897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179406"}},"subtitle":["A Game-Theoretic Approach"],"short-title":[],"issued":{"date-parts":[[2018,4,3]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,4,3]]}},"alternative-id":["10.1145\/3179406"],"URL":"https:\/\/doi.org\/10.1145\/3179406","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2018,4,3]]},"assertion":[{"value":"2018-04-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}