Pith. sign in

REVIEW 2 major objections 4 minor 38 references

Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Win-Rate Matching gives dynamic max-min fairness an approximate equilibrium and near-optimal welfare.

desk verdict A solid mechanism-design paper: the subgroup state-space collapse theorem is the real contribution, while the 'data-driven' claim needs to be walked back because Algorithm 2 requires exact knowledge of p*. read the letter →

arxiv 2501.14916 v1 pith:CF7UC5KV submitted 2025-01-24 cs.GT

Chido Onyeze , Siddhartha Banerjee , Giannis Fikioris , Éva Tardos This is my paper · ORCID
classification cs.GT MSC 91A1091B3260J20
keywords dynamicmax-minfairnesspublicgoodsallocationNashequilibriumthresholdstrategiesWin-RateMatchingstate-spacecollapsewelfareguaranteecompetitive
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies repeated allocation of a single public resource under Dynamic Max-Min Fairness (DMMF), where in each round among requesting agents the one with fewest past wins receives the item. It establishes that the natural class of fixed threshold strategies has no pure Nash equilibrium, even for two symmetric agents with values on two points. It then proposes a data-driven policy, Win-Rate Matching, in which agents request with a probability that tracks the historical allocation rate plus a vanishing drift toward the welfare-optimal symmetric request probability $p^*$. The main theorem states that if all agents follow this policy, no agent can gain more than $o(t)$ over $t$ rounds by deviating to any fixed threshold strategy, so the profile is an approximate Nash equilibrium. The same policy improves the per-agent utility guarantee from the robust half of ideal utility to at least $1-1/e$ for arbitrary identical distributions, and to $1-O(\log n/n)$ for uniform distributions.

What carries the argument

The central object is the DMMF allocation process $X_i[t]=W_i[t]/\alpha_i - K[t]$, together with the subgroup stability condition: every subset $R$ of a stable group $S$ must satisfy $\left(1-\prod_{k\in R}(1-p_k)\right)/\sum_{k\in R}\alpha_k \ge \left(1-\prod_{k\in S}(1-p_k)\right)/\sum_{k\in S}\alpha_k$. This condition is exactly what links state-space collapse of normalized allocations to the request probabilities and fair shares: when it holds for the full set, every agent wins her fair share of requested rounds up to sub-linear error, and when it fails, agents split into ordered subgroups with distinct win rates. The Win-Rate Matching algorithm is the mechanism that uses this characterization: its request probability $M_{\eta,\zeta}[t]$ tracks the observed aggregate win rate through the inverse $\Phi^{-1}$ of the probability that at least one agent requests, while $\eta(t)$ injects a vanishing drift toward $p^*$ and $\zeta(t)$ keeps the process away from the absorbing rate $1$. The convergence lemmas for $M_{\eta,\zeta}[t]$ are what turn the static characterization into an equilibrium statement.

What would settle it

Simulate DMMF with $n$ agents drawing values from a chosen distribution, run all agents on Win-Rate Matching with the paper's $\eta(t)$ and $\zeta(t)$, and let a single agent deviate to a fixed threshold $p$ different from $p^*$. Theorem 4.5 predicts the deviator's utility exceeds her conforming utility by at most $o(T)$; a simulation showing a positive linear gain over a long horizon would refute it.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central finding is that strategic behavior in DMMF is governed by a complete characterization of long-run win rates, and that characterization makes possible a simple equilibrium-inducing policy. For any fixed threshold profile, the agents split into stable subgroups; within each subgroup normalized win rates are mean-reverting about a common line, so each agent's long-run utility is an explicit function of the request probabilities and fair shares. Using this, the paper shows that no pure Nash equilibrium exists among fixed thresholds. The remedy is Win-Rate Matching: each round agents set their request probability to $(1-\eta(t))\Phi^{-1}(\zeta(t) K[t-1]/(t-1)) + \eta(t) p^*$, where $\Phi(p)=1-(1-p)^n$. With $\eta(t)=1/\log(t)^{1/2-\epsilon}$ and $\zeta(t)=1-t^{-1/4}$, when everyone follows the policy the request rates converge almost surely to $p^*$; when one agent deviates to a fixed threshold $\hat{p}$, the rates converge almost surely to $\hat{p}$, which makes the deviation unprofitable up to $o(t)$. Consequently, the equilibrium outcome is welfare-superior to the robust threshold play, giving each agent at least $1-1/e$ of her ideal utility in the worst case and $1-O(\log n/n)$ for uniform values.

Load-bearing premise

The load-bearing premise is that every agent knows $p^*$, the request probability maximizing symmetric welfare, which is a function of the common value distribution and is not estimated or learned by the algorithm.

Editorial extensions

If this is right

  • Fixed threshold strategies, despite their robustness guarantees, cannot serve as a model of equilibrium play under DMMF; the paper proves this already for two symmetric agents with a two-point value distribution.
  • Following the Win-Rate Matching policy is an approximate Nash equilibrium: unilateral deviations to any fixed threshold gain at most $o(t)$.
  • The equilibrium outcome guarantees every agent at least $1-1/e$ of her ideal utility for arbitrary identical value distributions, improving on the robust $1/2$ guarantee.
  • For uniform value distributions the guarantee becomes $1-O(\log n/n)$, improving on the robust $1-O(1/\sqrt{n})$ bound.
  • The characterization of long-run win rates extends to asymmetric DMMF with exogenous fair shares, so the analytical core is not limited to symmetric agents.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The algorithm's dependence on $p^*$ means the policy is only partially distribution-agnostic; a natural extension is to replace $p^*$ with an estimator learned from realized values and to check whether the approximate-equilibrium and welfare guarantees survive with high probability.
  • The mechanism-with-advice reading suggests a principal could recommend the Win-Rate Matching threshold while agents keep the freedom to deviate; if the theorem is right, rational agents have little incentive to disobey the recommendation, so the policy can be viewed as a cheap way to implement the welfare-optimal symmetric outcome.
  • The subgroup state-space collapse decomposition is a general tool for loss-network-like allocation processes, and it may transfer to pseudo-market mechanisms or other dynamic priority rules with different service disciplines.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies repeated allocation of an indivisible resource under the Dynamic Max-Min Fair (DMMF) mechanism, where in each round the resource is given to the requesting agent with the fewest prior allocations. The authors first provide a characterization of the long-run behavior of DMMF under fixed threshold strategies: Theorem 3.3 gives necessary and sufficient conditions for global state-space collapse, and Theorem 5.8 gives a full decomposition into stable subgroups with distinct win rates. They then prove that the natural class of fixed threshold strategies admits no pure Nash equilibrium even for two symmetric agents with a two-point value distribution (Theorem 4.1). As a remedy, they propose the Win-Rate Matching strategy (Algorithm 2), in which each agent chooses a request probability that matches the historical aggregate request rate, with a vanishing drift toward p*, the request probability maximizing symmetric welfare. Lemma 4.3 shows that if all agents follow this strategy, the request rate converges to p*; Lemma 4.4 shows that if one agent deviates to a fixed threshold p̂, the remaining agents' request rate converges to p̂. Theorem 4.5 concludes that no agent can improve her utility by deviating to a fixed threshold strategy, up to o(t). Theorem 4.6 gives welfare guarantees of 1-1/e for arbitrary identical distributions and 1-O(log n/n) for uniform distributions, improving on the prior robust 1/2 and 1-O(1/sqrt n) guarantees.

Significance. The paper makes a substantial technical contribution to the analysis of a simple dynamic allocation mechanism. The subgroup state-space collapse characterization (Theorems 3.3 and 5.8) is a complete and nontrivial description of the long-run win rates under arbitrary threshold profiles, and the drift-based stochastic approximation arguments used to establish Lemmas 4.3 and 4.4 are likely to be of independent interest. The counterexample in Theorem 4.1 is concrete and worked out in Appendix C with explicit parameters. The welfare guarantees in Theorem 4.6 improve on the existing robustness results, and the proof structure is internally consistent once p* is taken as given. However, the paper overstates the scope of its equilibrium result in two respects that matter for its main claim: Algorithm 2 requires p* as an input, so the policy is not distribution-free despite being billed as data-driven; and Theorem 4.5 only rules out deviations to fixed threshold strategies, not to history-dependent dynamic strategies. These issues are load-bearing for the paper's advertised conclusions and should be addressed before the results can be accepted at face value.

major comments (2)
  1. [Section 4.2, Algorithm 2, Lemma 4.3] Algorithm 2 takes p* = argmax_p U_i(p,...,p) as input, and Lemma 4.3 proves convergence to p* only when the drift term uses the true welfare-maximizing rate. Since p* depends on the common value distribution D, the Win-Rate Matching strategy is not distribution-free. The paper describes the policy as 'data-driven' in the Abstract and Section 1.1, and motivates it as a step for distribution-agnostic mechanisms, but no estimation or learning procedure for p* is provided. A misspecified target p*+delta would make the symmetric request rate converge to p*+delta by the same argument as Lemma 4.3, while a fixed-threshold deviation to p* would give the deviator utility U_i(p*,...,p*) against followers whose rate converges to p*, yielding a constant gain. Thus exact knowledge of p* is necessary for Theorem 4.5, and the current manuscript does not supply it within the claimed data-driven model. The authors should either provide a convergent estimator for p* from observable histories, or explicitly restate the results as requiring distributional knowledge and remove or qualify the 'data-driven' claims.
  2. [Theorem 4.5 and Section 1.1] The equilibrium statement is restricted to unilateral deviations to fixed threshold strategies: Theorem 4.5 only compares U_i(WRM,...,WRM) with U_i(WRM,...,Thr_p,...,WRM). The paper nonetheless refers to this as an approximate Nash equilibrium in the abstract and in Section 1.1. Since Proposition 2.1 shows that arbitrary strategies are dominated by history-dependent dynamic threshold strategies, and Theorem 4.5 does not rule out profitable dynamic deviations, the claim as advertised is stronger than what is proved. The authors should either extend the result to a broader class of deviations or consistently describe the theorem as an equilibrium against fixed-threshold deviations.
minor comments (4)
  1. [Lemma 4.4 proof, Appendix D] The last sentence of the proof says '|M_{eta,zeta}[t] - p^*| = (1+o(1))|Z[t]| -> 0', but Z[t] is defined with p̂; this should be |M_{eta,zeta}[t] - p̂|.
  2. [Figure 2 caption] The caption states that the experiment uses zeta(t)=1 and an eta(t) that decays linearly to 0.05, which differs from the schedules zeta(t)=1-t^{-1/4} and eta(t)=1/log(t)^{1/2-epsilon} used in Theorem 4.5. This is acknowledged, but the experimental section would be clearer if it explained whether the displayed behavior is expected to persist under the theorem's parameter schedules.
  3. [Theorem 5.8] The error bound is written as 'o(t) <= O(sqrt(t log t)) if C_i satisfies the stability criterion strictly'; this mixes o(t) and O(sqrt(t log t)) notation. The intended meaning is that the remainder is O(sqrt(t log t)) under the strict condition, and the presentation should be adjusted.
  4. [Section 1.3] There is a typo: 'wide variery of applications' should be 'wide variety of applications'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the equilibrium and welfare claims are supported by independent convergence and deviation analyses.

full rationale

The paper's main equilibrium result (Theorem 4.5) is not circular: p* is defined as the maximizer of the symmetric threshold utility U_i(p,...,p), and Algorithm 2 uses p* as an explicit drift target. Lemma 4.3 then proves, via a stochastic approximation argument, that if all agents follow Win-Rate Matching the request probability converges to p*, and Lemma 4.4 proves that if one agent deviates to a fixed threshold p, the remaining agents' request probability converges to p, making the deviator's utility approximately U_i(p,...,p). The no-deviation conclusion therefore relies on a nontrivial dynamical claim (Lemma 4.4), not merely on the definition of p*. The welfare improvement in Theorem 4.6 is also obtained by comparing the p* outcome to independent lower-bound benchmarks (p=1/n for arbitrary distributions and p=log n/n for uniform distributions), rather than by renaming an input as a prediction. The exact-knowledge requirement for p* is a genuine modeling assumption and a limitation for truly distribution-agnostic implementation, but it is not a circular derivation: no fitted parameter is relabeled as a prediction, and no theorem is justified by citing the authors' own prior work. The self-citation to [13] appears only as a robustness baseline and in the experimental comparison, not as load-bearing support for the equilibrium characterization.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central equilibrium construction depends on knowing the distribution through p*, on the symmetry restriction, and on restricting deviations to fixed thresholds. No new physical entities are introduced; the main hand-chosen elements are the drift and gap schedules.

free parameters (3)
  • eta(t) drift schedule exponent = eta(t)=1/log(t)^{1/2-epsilon}, epsilon in (0,1/4)
    Hand-chosen to balance convergence under all-follow (Lemma 4.3) with allowing a single deviator to overtake the rate (Lemma 4.4); not fitted to data.
  • zeta(t) gap schedule = zeta(t)=1-t^{-1/4}
    Hand-chosen to keep the argument of Phi^{-1} bounded away from 1 and avoid the sink at request probability 1.
  • counterexample epsilon in Theorem 4.1 = epsilon = q/(2+q) with q=1/4
    A specific two-point value distribution used to prove non-existence of pure Nash equilibrium; not used in the main equilibrium construction.
assumptions (5)
  • domain assumption Values V_i[t] are i.i.d. across agents and rounds, independent, supported in [0,1].
    Used throughout, e.g., Proposition 3.1 and the Markov chain model in Section 3.1.
  • domain assumption Symmetric setting: all agents have identical value distribution and equal fair shares.
    Section 4.2 and Theorem 4.5 restrict to this case.
  • domain assumption Each agent knows the common distribution D, or at least the value p* = argmax U_i(p,...,p).
    Algorithm 2 takes p* as input; the paper does not justify how p* is obtained in a distribution-agnostic implementation.
  • ad hoc to paper Agents are limited to deviations to fixed threshold strategies in the equilibrium claim.
    Theorem 4.5 only rules out deviations to SThr_p, not arbitrary dynamic strategies; the paper acknowledges this but the equilibrium notion is weaker than full Nash.
  • standard math Standard concentration and stochastic approximation results (Azuma-Hoeffding, Borel-Cantelli, Pemantle-Rosenthal).
    Used in Appendices B and D for drift and convergence proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria." pith.science (2026). https://pith.science/paper/CF7UC5KV

@misc{pith2026250114916,
  author       = {Pith},
  title        = {Pith review of: Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CF7UC5KV}},
  note         = {Machine review of arXiv:2501.14916}
}
read the original abstract

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. 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, no Nash equilibrium exists 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.

Figures

Figures reproduced from arXiv: 2501.14916 by the authors.

Figure 1
Figure 1. A sample path of allocations under DMMF with 4 agents in the symmetric setting (i.e., with 𝛼𝑖 = 1/4 for all 𝑖). The agents all use threshold strategies, with strategy vector (S Thr 0.1 , S Thr 0.2 , S Thr 0.25, S Thr 0.5 ). Note that while for all agents 𝑊𝑖 [𝑡] grows linearly, they split up into 3 stable subgroups, each with a different average win rate. Note also that DMMF gives agent 1 the highest priority and age… view at source ↗
Figure 2
Figure 2. Utility of an agent who follows Win-Rate Matching or the robust threshold of [ [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 32 canonical work pages

  1. [1]

    Santiago R Balseiro, Huseyin Gurkan, and Peng Sun. 2019. Multiagent mechanism design without money. Operations Research 67, 5 (2019), 1417–1436

    work page 2019

  2. [2]

    Siddhartha Banerjee, Giannis Fikioris, and Éva Tardos. 2023. Robust Pseudo-Markets for Reusable Public Resources. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12,

    work page 2023

  3. [3]

    Siddhartha Banerjee, Chamsi Hssaine, and Sean R Sinclair. 2023. Online Fair Allocation of Perishable Resources. ACM SIGMETRICS 51, 1 (2023), 55–56

    work page 2023

  4. [4]

    Moise Blanchard and Patrick Jaillet. 2024. Near-Optimal Mechanisms for Resource Allocation Without Monetary Transfers. arXiv preprint arXiv:2408.10066 (2024)

    arXiv 2024

  5. [5]

    Thomas Bonald and Laurent Massoulié. 2001. Impact of fairness on Internet performance. In Proceedings of the Joint International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS/Performance 2001, June 16-20, 2001, Cambridge, MA, USA , Mary K. Vernon (Ed.). ACM, Cambridge, MA, USA, 82–91

    work page 2001

  6. [6]

    Thomas Bonald, Laurent Massoulié, Alexandre Proutiere, and Jorma Virtamo. 2006. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing systems 53 (2006), 65–84

    work page 2006

  7. [7]

    Thomas Bonald and James W. Roberts. 2015. Multi-Resource Fairness: Objectives, Algorithms and Performance. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Portland, OR, USA, June 15-19, 2015 , Bill Lin, Jun (Jim) Xu, Sudipta Sengupta, and Devavrat Shah (Eds.). ACM, Portland, OR, USA, 31–4...

    work page arXiv 2015

  8. [8]

    Eric Budish, Gérard P Cachon, Judd B Kessler, and Abraham Othman. 2017. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research 65, 2 (2017), 314–336

    work page 2017

Show all 38 references
  1. [9]

    Ruggiero Cavallo. 2014. Incentive compatible two-tiered resource allocation without money. InInternational 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 (...

    2014

  2. [10]

    Ezzat Elokda, Saverio Bolognani, Andrea Censi, Florian Dörfler, and Emilio Frazzoli. 2023. A Self-Contained Karma Economy for the Dynamic Allocation of Common Resources. Dynamic Games and Applications 13 (25 4 2023), 1–33. https://doi.org/10.1007/s13235-023-00503-0

    2023 doi

  3. [11]

    Ezzat Elokda, Carlo Cenedese, Kenan Zhang, John Lygeros, and Florian Dörfler. 2022. CARMA: Fair and efficient bottleneck congestion management with karma. arXiv preprint arXiv:2208.07113 (2022)

    2022 arXiv

  4. [12]

    Giannis Fikioris, Rachit Agarwal, and Éva Tardos. 2024. Incentives in dominant resource fair allocation under dynamic demands. In International Symposium on Algorithmic Game Theory . Springer, 108–125

    2024

  5. [13]

    Giannis Fikioris, Siddhartha Banerjee, and Éva Tardos. 2023. Online resource sharing via dynamic max-min fairness: efficiency, robustness and non-stationarity. arXiv preprint arXiv:2310.08881 (2023)

    2023 arXiv

  6. [14]

    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, Ju...

    2018

  7. [15]

    Jason Gaitonde and Éva Tardos. 2023. The price of anarchy of strategic queuing systems. J. ACM 70, 3 (2023), 1–63

    2023

  8. [16]

    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, Bosto...

    2011

  9. [17]

    Irving L Glicksberg. 1952. A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proc. Amer. Math. Soc. 3, 1 (1952), 170–174

    1952

  10. [18]

    Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. 2017. From Monetary to Non-Monetary Mechanism Design via Artificial Currencies. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017 , Constantinos Daskal...

    2017

  11. [19]

    Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. 2021. The Remarkable Robustness of the Repeated Fisher Market. In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021 , Péter Biró, Shuchi Chawla, and Federico Echenique (E...

    2021

  12. [20]

    Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. 2014. Multi-resource packing for cluster schedulers. In ACM SIGCOMM 2014 Conference, SIGCOMM’14, Chicago, IL, USA, August 17-22, 2014 , Fabián E. Bustamante, Y. Charlie Hu, Arvind Krishnam...

    2014

  13. [21]

    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, Novemb...

    2016

  14. [22]

    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, T...

    2010

  15. [23]

    Refael Hassin. 2016. Rational queueing. CRC press

    2016

  16. [24]

    Refael Hassin and Moshe Haviv. 2003. To queue or not to queue: Equilibrium behavior in queueing systems . Vol. 59. Springer Science & Business Media

    2003

  17. [25]

    Matthew O Jackson and Hugo F Sonnenschein. 2007. Overcoming incentive constraints by linking decisions. Econo- metrica 75, 1 (2007), 241–257

    2007

  18. [26]

    Carlee Joe-Wong, Soumya Sen, Tian Lan, and Mung Chiang. 2013. Multiresource allocation: Fairness–efficiency tradeoffs in a unifying framework. IEEE/ACM Transactions on Networking 21, 6 (2013), 1785–1798

    2013

  19. [27]

    Frank P Kelly, Aman K Maulloo, and David Kim Hong Tan. 1998. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society 49 (1998), 237–252

    1998

  20. [28]

    Parkes, Ariel D

    David C. Parkes, Ariel D. Procaccia, and Nisarg Shah. 2012. Beyond dominant resource fairness: extensions, limitations, and indivisibilities. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012. ACM, Valencia, Spain, 808–825

    2012

  21. [29]

    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 82, 1 (1999), 143–155

    1999

  22. [30]

    Canice Prendergast. 2022. The allocation of food to food banks. Journal of Political Economy 130, 8 (2022), 1993–2017

    2022

  23. [31]

    Srinivas Shakkottai, Rayadurgam Srikant, et al. 2008. Network optimization and control. Foundations and Trends® in Networking 2, 3 (2008), 271–379

    2008

  24. [32]

    Freedman, and Anees Shaikh

    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 Vahd...

    2012

  25. [33]

    Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. 2022. Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve. ACM SIGMETRICS 50, 1 (2022), 95–96

    2022

  26. [34]

    Midhul Vuppalapati, Giannis Fikioris, Rachit Agarwal, Asaf Cidon, Anurag Khandelwal, and Éva Tardos. 2023. Karma: Resource Allocation for Dynamic Demands. In17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023, Boston, MA, USA, July 10-12, 2023 . USE...

    2023

  27. [35]

    Steven Yin and Christian Kroer. 2022. Optimal Efficiency-Envy Trade-Off via Optimal Transport. Advances in Neural Information Processing Systems (NeurIPS) 35 (2022), 25644–25654. Proc. ACM Meas. Anal. Comput. Syst., Vol. 9, No. 1, Article 2. Publication date: March 2025. Alloc...

    2022

  28. [37]

    However, by symmetry, U2( 1 2,𝑝 2) is decreasing in𝑝2

    Thus, the only possible request probability profile that could be a Nash equilibrium is( 1 2, 1). However, by symmetry, U2( 1 2,𝑝 2) is decreasing in𝑝2. Hence, requesting in every round is not a best response for agent 2 to agent 1 requesting with probability 1

  29. [38]

    □ D Proofs of Subsection 4.2 In this section, we shall first prove our claims about the convergence of the random process𝑀𝜂,𝜁[𝑡] for appropriate chosen𝜂 and𝜁

    Thus,( 1 2, 1) is not a Nash equilibrium. □ D Proofs of Subsection 4.2 In this section, we shall first prove our claims about the convergence of the random process𝑀𝜂,𝜁[𝑡] for appropriate chosen𝜂 and𝜁 . Afterwards, we prove the utility bounds when the agents follow Win-Rate Mat...

    2025

  30. [2023]

    ACM, London, United Kingdom, 241

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.