Fair and Efficient Online Allocations

Gerdus Benadè (), Aleksandr M. Kazachkov (), Ariel D. Procaccia (), Alexandros Psomas () and David Zeng ()
Additional contact information
Gerdus Benadè: Questrom School of Business, Boston University, Boston, Massachusetts 02215
Aleksandr M. Kazachkov: Department of Industrial & Systems Engineering, University of Florida, Gainesville, Florida 32611
Ariel D. Procaccia: School of Engineering and Applied Sciences, Harvard University, Boston, Massachusetts 02134
Alexandros Psomas: Department of Computer Science, Purdue University, West Lafayette, Indiana 47907
David Zeng: Jane Street Capital, New York, New York 10281

Operations Research, 2024, vol. 72, issue 4, 1438-1452

Abstract: We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another’s allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. In a slightly weaker adversary regime where item values are drawn from (potentially correlated) distributions, it is possible to achieve the best of both worlds. We give an algorithm that is Pareto efficient ex post and either envy free up to one good or envy free with high probability. Neither guarantee can be improved, even in isolation. En route, we give a constructive proof for a structural result of independent interest. Specifically, there always exists a Pareto-efficient fractional allocation that is strongly envy free with respect to pairs of agents with substantially different utilities while allocating identical bundles to agents with identical utilities (up to multiplicative factors).

Keywords: Market Analytics and Revenue Management; online allocation; fair division; fairness-efficiency trade-off (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0332 (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:inm:oropre:v:72:y:2024:i:4:p:1438-1452

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().