Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation

Haris Aziz (), Rupert Freeman (), Nisarg Shah () and Rohit Vaish ()
Additional contact information
Haris Aziz: School of Computer Science and Engineering, University of New South Wales, Sydney, New South Wales 2035, Australia
Rupert Freeman: Darden School of Business, University of Virginia, Charlottesville, Virginia 22903
Nisarg Shah: Department of Computer Science, University of Toronto, Toronto, Ontario M5T 3A1, Canada
Rohit Vaish: Department of Computer Science and Engineering, Indian Institute of Technology Delhi, New Delhi 110 016, India

Operations Research, 2024, vol. 72, issue 4, 1674-1688

Abstract: We study the problem of allocating indivisible goods among agents with additive valuations. When randomization is allowed, it is possible to achieve compelling notions of fairness such as envy-freeness, which states that no agent should prefer any other agent’s allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as envy-freeness up to one good can be guaranteed. Our goal in this work is to achieve both simultaneously, by constructing a randomized allocation that is exactly fair ex ante (before the randomness is realized) and approximately fair ex post (after the randomness is realized). The key question we address is whether ex ante envy-freeness can be achieved in combination with ex post envy-freeness up to one good. We settle this positively by designing an efficient algorithm that achieves both properties simultaneously. The algorithm can be viewed as a desirable way to instantiate a lottery for the probabilistic serial rule. If we additionally require economic efficiency, we obtain three impossibility results that show that ex post or ex ante Pareto optimality is impossible to achieve in conjunction with combinations of fairness properties. Hence, we slightly relax our ex post fairness guarantees and present a different algorithm that can be viewed as a fair way to instantiate a lottery for the maximum Nash welfare allocation rule.

Keywords: Decision Analysis; fair resource allocation; indivisible goods; randomization and approximation (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.2432 (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:1674-1688

Access Statistics for this article

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