Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Trade-off Curve

Sean R. Sinclair (), Gauri Jain (), Siddhartha Banerjee () and Christina Lee Yu ()
Additional contact information
Sean R. Sinclair: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Gauri Jain: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Siddhartha Banerjee: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Christina Lee Yu: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Operations Research, 2023, vol. 71, issue 5, 1689-1705

Abstract: We consider the problem of dividing limited resources to individuals arriving over T rounds. Each round has a random number of individuals arrive, and individuals can be characterized by their type (i.e., preferences over the different resources). A standard notion of fairness in this setting is that an allocation simultaneously satisfy envy-freeness and efficiency. The former is an individual guarantee, requiring that each agent prefers the agent’s own allocation over the allocation of any other; in contrast, efficiency is a global property, requiring that the allocations clear the available resources. For divisible resources, when the number of individuals of each type are known up front, the desiderata are simultaneously achievable for a large class of utility functions. However, in an online setting when the number of individuals of each type are only revealed round by round, no policy can guarantee these desiderata simultaneously, and hence, the best one can do is to try and allocate so as to approximately satisfy the two properties. We show that, in the online setting, the two desired properties (envy-freeness and efficiency) are in direct contention in that any algorithm achieving additive counterfactual envy-freeness up to a factor of L T necessarily suffers an efficiency loss of at least 1 / L T . We complement this uncertainty principle with a simple algorithm, G uarded- H ope , which allocates resources based on an adaptive threshold policy and is able to achieve any fairness–efficiency point on this frontier. Our results provide guarantees for fair online resource allocation with high probability for multiple resource and multiple type settings. In simulation results, our algorithm provides allocations close to the optimal fair solution in hindsight, motivating its use in practical applications as the algorithm is able to adapt to any desired fairness efficiency trade-off.

Keywords: Revenue Management and Market Analytics; online resource allocation; Varian fairness; Nash social welfare; model-predictive control (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2397 (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:71:y:2023:i:5:p:1689-1705

Access Statistics for this article

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