Fair Resource Allocation in a Volatile Marketplace

MohammadHossein Bateni (), Yiwei Chen (), Dragos Florin Ciocan () and Vahab Mirrokni ()
Additional contact information
MohammadHossein Bateni: Google Research, New York, New York 10011
Yiwei Chen: Department of Marketing and Supply Chain Management, Fox School of Business, Temple University, Philadelphia, Pennsylvania 19122
Dragos Florin Ciocan: Technology and Operations Management, INSEAD, 77300 Fontainebleau, France
Vahab Mirrokni: Google Research, New York, New York 10011

Operations Research, 2022, vol. 70, issue 1, 288-308

Abstract: We consider a setting where a platform dynamically allocates a collection of goods that arrive to the platform in an online fashion to budgeted buyers, as exemplified by online advertising systems where platforms decide which impressions to serve to various advertisers. Such dynamic resource allocation problems are challenging for two reasons. (a) The platform must strike a balance between optimizing the advertiser’s own revenues and guaranteeing fairness to the advertiser’s (repeat) buyers, and (b) the problem is inherently dynamic due to the uncertain, time-varying supply of goods available with the platform. We propose a stochastic approximation scheme akin to a dynamic market equilibrium. Our scheme relies on frequent resolves of an Eisenberg-Gale convex program and does not require the platform to have any knowledge about how the goods’ arrival processes evolve over time. The scheme fully extracts buyer budgets (thus maximizing platform revenues) and at the same time provides a 0.64 approximation of the proportionally fair allocation of goods achievable in the offline case, as long as the supply of goods comes from a wide family of (possibly nonstationary) Gaussian processes. We then deal with a multi-objective problem where the platform is concerned with both the proportional fairness and efficiency of the allocation and propose a hybrid algorithm that achieves a 0.3 bicriteria guarantee against fairness and efficiency. Finally, we build a sequence of datasets, one public dataset released by the DSP iPinYou and the second based on real Google AdX data, and use them to test the empirical performance of our schemes. We find that across these datasets there is a surprising relationship between fairness and efficiency that can be used to tune the schemes to nearly optimal performance in practice.

Keywords: Games; Information; and Networks; dynamic resource allocation; matching; Fisher equilibrium; online fairness performance; online multi-objective optimization; network revenue management; online advertising (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2049 (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:70:y:2022:i:1:p:288-308

Access Statistics for this article

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