More Web Proxy on the site http://driver.im/

research-article

Fairness Maximization among Offline Agents in Online-Matching Markets

Authors:

Yifan XuAuthors Info & Claims

ACM Transactions on Economics and Computation, Volume 10, Issue 4

Article No.: 16, Pages 1 - 27

https://doi.org/10.1145/3569705

Published: 05 April 2023 Publication History

Abstract

Online matching markets (OMMs) are commonly used in today’s world to pair agents from two parties (whom we will call offline and online agents) for mutual benefit. However, studies have shown that the algorithms making decisions in these OMMs often leave disparities in matching rates, especially for offline agents. In this article, we propose online matching algorithms that optimize for either individual or group-level fairness among offline agents in OMMs. We present two linear-programming (LP) based sampling algorithms, which achieve competitive ratios at least 0.725 for individual fairness maximization and 0.719 for group fairness maximization. We derive further bounds based on fairness parameters, demonstrating conditions under which the competitive ratio can increase to 100%. There are two key ideas helping us break the barrier of 1-1/𝖾~ 63.2% for competitive ratio in online matching. One is boosting, which is to adaptively re-distribute all sampling probabilities among only the available neighbors for every arriving online agent. The other is attenuation, which aims to balance the matching probabilities among offline agents with different mass allocated by the benchmark LP. We conduct extensive numerical experiments and results show that our boosted version of sampling algorithms are not only conceptually easy to implement but also highly effective in practical instances of OMMs where fairness is a concern.

References

[1]

Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. 2015. Improved approximation algorithms for stochastic matching. In Algorithms - ESA 2015 - Proceedings of the 23rd Annual European Symposium (ESA 2015).

[2]

Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce. 18–35.

Digital Library

[3]

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. 2021. Online discrepancy minimization for stochastic arrivals. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2842–2861.

[4]

Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. 2021. The price of fairness for indivisible goods. Theory of Computing Systems 65, 7 (2021), 1069–1093.

Digital Library

[5]

Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. 2011. The price of fairness. Operations Research 59, 1 (2011), 17–31.

Digital Library

[6]

Kostas Bimpikis, Ozan Candogan, and Daniela Saban. 2019. Spatial pricing in ride-sharing networks. Operations Research 67, 3 (2019), 744–769.

Digital Library

[7]

Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. 2020. An experimental study of algorithms for online bipartite matching. Journal of Experimental Algorithmics (JEA) 25 (2020), 1–37.

Digital Library

[8]

Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2020. Attenuate locally, win globally: An attenuation-based framework for online stochastic matching with timeouts. Algorithmica 82, 1 (2020), 64–87.

Digital Library

[9]

Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2020. Online stochastic matching: New algorithms and bounds. Algorithmica 82, 10 (2020), 2737–2783.

Digital Library

[10]

Michael B. Cohen, Y. Lee, and Zhao Song. 2019. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019).

Digital Library

[11]

Cody Cook, Rebecca Diamond, Jonathan Hall, John A. List, and Paul Oyer. 2018. The Gender Earnings Gap in the Gig Economy: Evidence from over a Million Rideshare Drivers. Technical Report. National Bureau of Economic Research.

[12]

John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. 2014. Price of fairness in kidney exchange. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’14) (Paris, France). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1013–1020.

Digital Library

[13]

John P. Dickerson, Karthik Abinav Sankararaman, Kanthi Kiran Sarpatwar, Aravind Srinivasan, Kun-Lung Wu, and Pan Xu. 2019. Online resource allocation with matching constraints. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1681–1689.

Digital Library

[14]

John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2018. Assigning tasks to workers based on historical data: Online task assignment with two-sided arrivals. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 318–326.

[15]

John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2019. Balancing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 1877–1884.

Digital Library

[16]

John P. Dickerson, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu. 2021. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Transactions on Economics and Computation (TEAC) 9, 3 (2021), 1–17.

Digital Library

[17]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 214–226.

Digital Library

[18]

Elaheh Fata, Will Ma, and David Simchi-Levi. 2019. Multi-stage and multi-customer assortment optimization with inventory constraints. Available at SSRN 3443109 (2019).

[19]

Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. 2009. Online stochastic matching: Beating 1-1/e. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on. IEEE, 117–126.

[20]

Yiding Feng, Rad Niazadeh, and Amin Saberi. 2019. Linear programming based online policies for real-time assortment of reusable resources. Available at SSRN 3421227 (2019).

[21]

David García-Soriano and Francesco Bonchi. 2020. Fair-by-design matching. Data Mining and Knowledge Discovery 34, 5 (2020), 1291–1335.

Digital Library

[22]

Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. 2018. Online learning with an unknown fairness metric. arXiv preprint arXiv:1802.06936 (2018).

[23]

Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 8. 982–991.

[24]

Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2011. Online stochastic weighted matching: Improved approximation algorithms. In Internet and Network Economics. Lecture Notes in Computer Science, Vol. 7090. Springer, Berlin, 170–181.

Digital Library

[25]

Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2011. Online stochastic weighted matching: Improved approximation algorithms. In Internet and Network Economics - 7th International Workshop (WINE’11). 170–181.

[26]

Emma Hinchliffe. 2017. Yes, there’s a wage gap for Uber and Lyft drivers based on age, gender and race. https://mashable.com/2017/01/18/uber-lyft-wage-gap-rideshare/.Accessed: 2019-12-27.

[27]

Zhiyi Huang and Xinkai Shu. 2021. Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 682–693.

Digital Library

[28]

Patrick Jaillet and Xin Lu. 2013. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research 39, 3 (2013), 624–646.

Digital Library

[29]

Kumar Joag-Dev and Frank Proschan. 1983. Negative association of random variables with applications. The Annals of Statistics (1983), 286–295.

[30]

Matthew Joseph, Michael J. Kearns, Jamie H. Morgenstern, and Aaron Roth. 2016. Fairness in learning: Classic and contextual bandits. In NIPAdvances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems. 325–333.

[31]

Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC’90). 352–358.

Digital Library

[32]

Nixie S. Lesmana, Xuan Zhang, and Xiaohui Bei. 2019. Balancing efficiency and fairness in on-demand ridesourcing. In Advances in Neural Information Processing Systems. 5310–5320.

[33]

Z. Li, Kelsey Lieberman, William Macke, Sofia Carrillo, C. Ho, J. Wellen, and Sanmay Das. 2019. Incorporating compatible pairs in kidney exchange: A dynamic weighted matching model. In Proceedings of the 2019 ACM Conference on Economics and Computation (2019).

Digital Library

[34]

Hongyao Ma, Fei Fang, and David C. Parkes. 2019. Spatio-temporal pricing for ridesharing platforms. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC’19). 583.

Digital Library

[35]

Will Ma. 2018. Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Mathematics of Operations Research 43, 3 (2018), 789–812.

Digital Library

[36]

Will Ma, Pan Xu, and Yifan Xu. 2021. Group-level fairness maximization in online bipartite matching. arXiv preprint arXiv:2011.13908 (2021).

[37]

Vahideh Manshadi, Rad Niazadeh, and Scott Rodilitz. 2021. Fair dynamic rationing. Available at SSRN 3775895 (2021).

[38]

Vahideh Manshadi and Scott Rodilitz. 2020. Online policies for efficient volunteer crowdsourcing. In Proceedings of the 21st ACM Conference on Economics and Computation (2020).

Digital Library

[39]

Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. 2012. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research 37, 4 (2012), 559–573.

Digital Library

[40]

Duncan C. McElfresh, Christian Kroer, Sergey Pupyrev, Eric Sodomka, Karthik Abinav Sankararaman, Zack Chauvin, Neil Dexter, and John P. Dickerson. 2020. Matching algorithms for blood donation. In Proceedings of the 21st ACM Conference on Economics and Computation (2020).

Digital Library

[41]

Aranyak Mehta. 2013. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science 8, 4 (2013), 265–368.

Digital Library

[42]

Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press.

Digital Library

[43]

Vedant Nanda, Pan Xu, Karthik Abhinav Sankararaman, John Dickerson, and Aravind Srinivasan. 2020. Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 2210–2217.

Digital Library

[44]

Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y. Narahari. 2020. Achieving fairness in the stochastic multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 5379–5386.

[45]

Alex Rosenblat, Karen Levy, Solon Barocas, and Tim Hwang. 2016. Discriminating tastes: Customer ratings as vehicles for bias. Available at SSRN 2858946 (2016).

[46]

Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI’15), Blai Bonet and Sven Koenig (Eds.). 4292–4293.

[47]

Jad Salem and Swati Gupta. 2019. Closing the GAP: Group-aware parallelization for online selection of candidates with biased evaluations. Available at SSRN 3444283 (2019).

[48]

Govind S. Sankar, Anand Louis, Meghana Nasre, and Prajakta Nimbhorkar. 2021. Matchings with group fairness constraints: Online and offline algorithms. arXiv preprint arXiv:2105.09522 (2021).

[49]

Sean R. Sinclair, Siddhartha Banerjee, and Christina Lee Yu. 2021. Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve. arXiv preprint arXiv:2105.05308 (2021).

[50]

Tom Sühr, Asia J. Biega, Meike Zehlike, Krishna P. Gummadi, and Abhijnan Chakraborty. 2019. Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 3082–3092.

Digital Library

[51]

Jacob Thebault-Spieker, Loren G. Terveen, and Brent Hecht. 2015. Avoiding the south side and the suburbs: The geography of mobile crowdsourcing markets. In Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing. ACM, 265–275.

Digital Library

[52]

Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. 2019. Group-fairness in influence maximization. arXiv preprint arXiv:1903.00967 (2019).

[53]

Yifan Xu and Pan Xu. 2020. Trade the system efficiency for the income equality of drivers in rideshare. In Proceedings of the 29th International Joint Conference on Artificial Intelligence. 4199–4205.

[54]

Boming Zhao, Pan Xu, Yexuan Shi, Yongxin Tong, Zimu Zhou, and Yuxiang Zeng. 2019. Preference-aware task assignment in on-demand taxi dispatching: An online stable matching approach. In Proceedings of the 33rd Conference on Artificial Intelligence (AAAI’19). 2245–2252.

Digital Library

Cited By

Ma W(2024)Randomized Rounding Approaches to Online Allocation, Sequencing, and MatchingTutorials in Operations Research: Smarter Decisions for a Better World10.1287/educ.2024.0281(90-116)Online publication date: 17-Oct-2024
https://doi.org/10.1287/educ.2024.0281
Dickerson JSankararaman KSrinivasan AXu PXu Y(2024)Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-sided ArrivalsACM Transactions on Economics and Computation10.1145/365202112:2(1-28)Online publication date: 10-Jun-2024
https://doi.org/10.1145/3652021

Index Terms

Fairness Maximization among Offline Agents in Online-Matching Markets

Recommendations

Online effects of offline ads
ADKDD '08: Proceedings of the 2nd International Workshop on Data Mining and Audience Intelligence for Advertising

We propose a methodology for assessing how ad campaigns in offline media such as print, audio and TV affect online interest in the advertiser's brand. Online interest can be measured by daily counts of the number of search queries that contain brand ...
From Online Behaviors to Offline Retailing
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

To combat the ease of online shopping in pajamas, offline mall owners focus increasingly on driving satisfaction and improving retention by identifying customers' preferences. However, most of these studies are based on customers' offline consuming ...
Price of Anarchy in Algorithmic Matching of Romantic Partners
Algorithmic matching is a pervasive mechanism in our social lives and is becoming a major medium through which people find romantic partners and potential spouses. However, romantic matching markets pose a principal-agent problem with the potential for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 10, Issue 4

December 2022

76 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3572856

Editors:
David Pennock
Rutgers University, USA
,
Ilya Segal
Stanford University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 April 2023

Online AM: 10 February 2023

Accepted: 24 October 2022

Received: 07 February 2022

Published in TEAC Volume 10, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF CRII Award

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
573
Total Downloads

Downloads (Last 12 months)313
Downloads (Last 6 weeks)37

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma W(2024)Randomized Rounding Approaches to Online Allocation, Sequencing, and MatchingTutorials in Operations Research: Smarter Decisions for a Better World10.1287/educ.2024.0281(90-116)Online publication date: 17-Oct-2024
https://doi.org/10.1287/educ.2024.0281
Dickerson JSankararaman KSrinivasan AXu PXu Y(2024)Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-sided ArrivalsACM Transactions on Economics and Computation10.1145/365202112:2(1-28)Online publication date: 10-Jun-2024
https://doi.org/10.1145/3652021

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents