research-article

Open access

Fair Resource Allocation in A Volatile Marketplace

Authors:

Mohammad Hossein Bateni,

Yiwei Chen,

Dragos Florin Ciocan,

Vahab MirrokniAuthors Info & Claims

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

Page 819

https://doi.org/10.1145/2940716.2940763

Published: 21 July 2016 Publication History

PDF eReader

Abstract

We consider the setting where a seller must allocate a collection of goods to budgeted buyers, as exemplified by online advertising systems where platforms decide which impressions to serve to various advertisers. Such resource allocation problems are challenging for two reasons: (a) the seller must strike a balance between optimizing her own revenues and guaranteeing fairness to her (repeat) buyers and (b) the problem is inherently dynamic due to the uncertain, time-varying supply of goods available with the seller.

We propose a stochastic approximation scheme akin to a dynamic market equilibrium. Our scheme relies on frequent re-solves of an Eisenberg-Gale convex program, and does not require the seller to have any knowledge about how goods arrival processes evolve over time. The scheme fully extracts buyer budgets (thus maximizing seller revenues), while at the same time provides a 0.47 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 non-stationary) Gaussian processes.

We then extend our results to a more general family of metrics called \alpha-fairness. Finally, we deal with a multi-objective problem where the seller is concerned with both the proportional fairness and efficiency of the allocation, and propose a hybrid algorithm which achieves a 0.27 bi-criteria guarantee against fairness and efficiency.

Cited By

View all

Chen XSimchi-Levi DWang Y(2023)Utility Fairness in Contextual Dynamic Pricing with Demand LearningSSRN Electronic Journal10.2139/ssrn.4658056Online publication date: 2023
https://doi.org/10.2139/ssrn.4658056
Xiao GZheng JDai H(2022)A Unified Model for Bi-objective Online Stochastic Bipartite Matching with Two-sided Limited PatienceIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796963(1079-1088)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796963
Calmon ACiocan FRomero G(2021)Revenue Management with Repeated Customer InteractionsManagement Science10.1287/mnsc.2020.367767:5(2944-2963)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1287/mnsc.2020.3677
Show More Cited By

Index Terms

Fair Resource Allocation in A Volatile Marketplace

Recommendations

Fair Allocation through Competitive Equilibrium from Generic Incomes
FAT* '19: Proceedings of the Conference on Fairness, Accountability, and Transparency

Two food banks catering to populations of different sizes with different needs must divide among themselves a donation of food items. What constitutes a "fair" allocation of the items among them?

Competitive equilibrium from equal incomes (CEEI) is a ...
Fair allocation of indivisible goods: Beyond additive valuations
Abstract
We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations ...
Fair Resource Allocation in Distributed Combinatorial Auctioning Systems
ICDCN '09: Proceedings of the 10th International Conference on Distributed Computing and Networking

Combinatorial Auctions are auctions where bidders can place bids on combinations of items, called packages or bundles, rather than just on individual items. In this paper we extend this concept to distributed system, by proposing a Distributed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

July 2016

874 pages

ISBN:9781450339360

DOI:10.1145/2940716

General Chair:
Vincent Conitzer
Duke University, USA
,
Program Chairs:
Dirk Bergemann
Yale University, USA
,
Yiling Chen
Harvard University, USA

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2016

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '16

Sponsor:

SIGecom

EC '16: ACM Conference on Economics and Computation

July 24 - 28, 2016

Maastricht, The Netherlands

Acceptance Rates

EC '16 Paper Acceptance Rate 80 of 242 submissions, 33%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
635
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)12

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen XSimchi-Levi DWang Y(2023)Utility Fairness in Contextual Dynamic Pricing with Demand LearningSSRN Electronic Journal10.2139/ssrn.4658056Online publication date: 2023
https://doi.org/10.2139/ssrn.4658056
Xiao GZheng JDai H(2022)A Unified Model for Bi-objective Online Stochastic Bipartite Matching with Two-sided Limited PatienceIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796963(1079-1088)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796963
Calmon ACiocan FRomero G(2021)Revenue Management with Repeated Customer InteractionsManagement Science10.1287/mnsc.2020.367767:5(2944-2963)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1287/mnsc.2020.3677
Aziz MWang APappu ABouchard HZhao YCarterette BLalmas MDemartini GZuccon GCulpepper JHuang ZTong H(2021)Leveraging Semantic Information to Facilitate the Discovery of Underserved PodcastsProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3481934(3707-3716)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3481934
Rahmattalabi AVayanos PFulginiti ARice EWilder BYadav ATambe MWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Exploring algorithmic fairness in robust graph covering problemsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455700(15776-15787)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455700
Prasad AArumaithurai MKoll DJiang YFu X(2019)OFM: An Online Fisher Market for Cloud ComputingIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737641(2575-2583)Online publication date: Apr-2019
https://doi.org/10.1109/INFOCOM.2019.8737641
Cohen MElmachtoub ALei X(undefined)Pricing with FairnessSSRN Electronic Journal10.2139/ssrn.3459289
https://doi.org/10.2139/ssrn.3459289
Calmon ACiocan DRomero G(undefined)Revenue Management with Repeated Customer InteractionsSSRN Electronic Journal10.2139/ssrn.3200338
https://doi.org/10.2139/ssrn.3200338

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fair Allocation through Competitive Equilibrium from Generic Incomes

Fair allocation of indivisible goods: Beyond additive valuations

Fair Resource Allocation in Distributed Combinatorial Auctioning Systems