Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 44 min ago
PreprintarXiv licencearXiv

Asymptotic Max-Min Fair Allocation with Random Utilities

  • Noam Glazner
  • Amir Leshem
Open at sourcePDFDOICite

Abstract

We investigate the asymptotic behavior of max-min fair allocations for indivisible goods under i.i.d. random utilities. For N agents and K goods with utilities mUi,j drawn independently from a common distribution F, we derive asymptotic characterizations of the max-min value in the balanced case K=N (and in K=LN extensions) via distributional quantiles. We then study the efficiency impact of max-min fairness by comparing the resulting total welfare with the optimal sum welfare. For distributions with sufficiently light tails, we prove that the relative efficiency loss converges to zero as the market grows, implying that max-min fairness incurs negligible welfare loss in large random instances for a broad class of distributions.

Related

  1. On a fair and risk-averse urban air mobility resource allocation problem under demand and capacity uncertainties
    Luying Sun, Haoyun Deng, Peng Wei +1
    Naval Research LogisticsPeer-reviewedCC BY-NC-NDFull text10 citedOptimisation & controlHAL
  2. On asymptotic expansions of the density of states for Poisson distributed random Schrödinger operators
    Jan Fischer, David Hasler, Jannis Koberstein
    arXivPreprintCC BY-NC-SA 4.0Full textMathematical physicsarXiv
  3. Asymptotic expansions for random walks conditioned to stay positive with arbitrary endpoints
    Alexander Tarasov
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Asymptotic Behaviour for Isotropic Pearson Random Walks
    Davide A. Bignamini, Emanuele G. Casini, Andrea Martinelli
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  5. Asymptotic long-range order for the XY-model on random geometric graphs
    Margherita Disertori, Max Mihailescu
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{glazner2026asymptotic,
  title = {{Asymptotic Max-Min Fair Allocation with Random Utilities}},
  author = {Noam Glazner and Amir Leshem},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19319},
  eprint = {2609.19319},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19319},
}
RIS
TY  - UNPB
TI  - Asymptotic Max-Min Fair Allocation with Random Utilities
AU  - Noam Glazner
AU  - Amir Leshem
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.19319
UR  - https://arxiv.org/abs/2609.19319
AB  - We investigate the asymptotic behavior of max-min fair allocations for indivisible goods under i.i.d. random utilities. For N agents and K goods with utilities mU_i,j drawn independently from a common distribution F, we derive asymptotic characterizations of the max-min value in the balanced case K=N (and in K=LN extensions) via distributional quantiles. We then study the efficiency impact of max-min fairness by comparing the resulting total welfare with the optimal sum welfare. For distributions with sufficiently light tails, we prove that the relative efficiency loss converges to zero as the market grows, implying that max-min fairness incurs negligible welfare loss in large random instances for a broad class of distributions.
ER  -