Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms

Jugal Garg, Yixin Tao and L\'aszl\'o A. V\'egh

Papers from arXiv.org

Abstract: The Probabilistic Serial (PS) mechanism -- also known as the simultaneous eating algorithm -- is a canonical solution for the random assignment problem under ordinal preferences. It guarantees envy-freeness and ordinal efficiency in the resulting random assignment. However, under cardinal preferences, its efficiency may degrade significantly: it is known that PS may yield allocations that are $\Omega(\ln{n})$-worse than Pareto optimal, but whether this bound is tight remained an open question. Our first result resolves this question by proving that the PS mechanism guarantees $(\ln n+1)$-approximate Pareto efficiency under cardinal preferences. The key part of our analysis shows that PS achieves a logarithmic $(\ln n + 1)$-approximation to the maximum Nash welfare, in stark contrast to the $O(\sqrt{n})$ loss that can arise in utilitarian social welfare. Our results also extend to the more general submodular setting introduced by Fujishige, Sano, and Zhan (ACM TEAC 2018). In addition, we present a polynomial-time algorithm that computes an allocation which is envy-free and $e^{1/e}$-approximately Pareto-efficient, answering an open question posed by Tr\"obst and Vazirani (EC 2024). The PS mechanism also applies to the allocation of chores instead of goods. We prove that it guarantees an $n$-approximately Pareto-efficient allocation in this setting, and that this bound is asymptotically tight. This result provides the first known approximation guarantee for computing a fair and efficient allocation in the random assignment problem with chores under cardinal preferences.

Date: 2025-07, Revised 2026-02
New Economics Papers: this item is included in nep-des, nep-gth and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2507.03359 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2507.03359

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().