{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:39:46Z","timestamp":1767339586849,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CRII Award","award":["IIS-1948157"],"award-info":[{"award-number":["IIS-1948157"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Online matching markets (OMMs) are commonly used in today\u2019s world to pair agents from two parties (whom we will call\n            <jats:italic>offline<\/jats:italic>\n            and\n            <jats:italic>online<\/jats:italic>\n            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\/\ud835\uddbe~ 63.2% for competitive ratio in online matching. One is\n            <jats:italic>boosting<\/jats:italic>\n            , which is to adaptively re-distribute all sampling probabilities among only the available neighbors for every arriving online agent. The other is\n            <jats:italic>attenuation<\/jats:italic>\n            , 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.\n          <\/jats:p>","DOI":"10.1145\/3569705","type":"journal-article","created":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T12:04:30Z","timestamp":1676030670000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Fairness Maximization among Offline Agents in Online-Matching Markets"],"prefix":"10.1145","volume":"10","author":[{"given":"Will","family":"Ma","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}]},{"given":"Pan","family":"Xu","sequence":"additional","affiliation":[{"name":"New Jersey Institute of Technology, Newark, NJ"}]},{"given":"Yifan","family":"Xu","sequence":"additional","affiliation":[{"name":"Southeast University, Nanjing, China"}]}],"member":"320","published-online":{"date-parts":[[2023,4,5]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Algorithms - ESA 2015 - Proceedings of the 23rd Annual European Symposium (ESA 2015)","author":"Adamczyk Marek","year":"2015","unstructured":"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)."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"2842","DOI":"10.1137\/1.9781611976465.169","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bansal Nikhil","year":"2021","unstructured":"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\u20132861."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-021-10039-8"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0865"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1800"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3379552"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00603-7"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00698-3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","DOI":"10.1145\/3313276.3316303","article-title":"Solving linear programs in the current matrix multiplication time","author":"Cohen Michael B.","year":"2019","unstructured":"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).","journal-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","DOI":"10.3386\/w24732","volume-title":"The Gender Earnings Gap in the Gig Economy: Evidence from over a Million Rideshare Drivers","author":"Cook Cody","year":"2018","unstructured":"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."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/2615731.2617407"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331896"},{"key":"e_1_3_2_15_2","first-page":"318","volume-title":"Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems","author":"Dickerson John P.","year":"2018","unstructured":"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\u2013326."},{"key":"e_1_3_2_16_2","first-page":"1877","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"33","author":"Dickerson John P.","year":"2019","unstructured":"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\u20131884."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3456756"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_3_2_19_2","article-title":"Multi-stage and multi-customer assortment optimization with inventory constraints","author":"Fata Elaheh","year":"2019","unstructured":"Elaheh Fata, Will Ma, and David Simchi-Levi. 2019. Multi-stage and multi-customer assortment optimization with inventory constraints. Available at SSRN 3443109 (2019).","journal-title":"Available at SSRN 3443109"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/FOCS.2009.72","volume-title":"Foundations of Computer Science, 2009. FOCS\u201909. 50th Annual IEEE Symposium on","author":"Feldman Jon","year":"2009","unstructured":"Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. 2009. Online stochastic matching: Beating 1-1\/e. In Foundations of Computer Science, 2009. FOCS\u201909. 50th Annual IEEE Symposium on. IEEE, 117\u2013126."},{"key":"e_1_3_2_21_2","article-title":"Linear programming based online policies for real-time assortment of reusable resources","author":"Feng Yiding","year":"2019","unstructured":"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).","journal-title":"Available at SSRN 3421227"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-020-00675-y"},{"key":"e_1_3_2_23_2","article-title":"Online learning with an unknown fairness metric","author":"Gillen Stephen","year":"2018","unstructured":"Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. 2018. Online learning with an unknown fairness metric. arXiv preprint arXiv:1802.06936 (2018).","journal-title":"arXiv preprint arXiv:1802.06936"},{"key":"e_1_3_2_24_2","first-page":"982","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","volume":"8","author":"Goel Gagan","year":"2008","unstructured":"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\u2013991."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_15"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/978-3-642-25510-6_15","volume-title":"Internet and Network Economics - 7th International Workshop (WINE\u201911)","author":"Haeupler Bernhard","year":"2011","unstructured":"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\u201911). 170\u2013181."},{"key":"e_1_3_2_27_2","article-title":"Yes, there\u2019s a wage gap for Uber and Lyft drivers based on age, gender and race","author":"Hinchliffe Emma","year":"2017","unstructured":"Emma Hinchliffe. 2017. Yes, there\u2019s 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.","journal-title":"https:\/\/mashable.com\/2017\/01\/18\/uber-lyft-wage-gap-rideshare\/."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451079"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_3_2_30_2","first-page":"286","article-title":"Negative association of random variables with applications","author":"Joag-Dev Kumar","year":"1983","unstructured":"Kumar Joag-Dev and Frank Proschan. 1983. Negative association of random variables with applications. The Annals of Statistics (1983), 286\u2013295.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_2_31_2","first-page":"325","volume-title":"NIPAdvances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems","author":"Joseph Matthew","year":"2016","unstructured":"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\u2013333."},{"key":"e_1_3_2_32_2","first-page":"352","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC\u201990)","author":"Karp Richard M.","year":"1990","unstructured":"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\u201990). 352\u2013358."},{"key":"e_1_3_2_33_2","first-page":"5310","volume-title":"Advances in Neural Information Processing Systems","author":"Lesmana Nixie S.","year":"2019","unstructured":"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\u20135320."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","DOI":"10.1145\/3328526.3329619","article-title":"Incorporating compatible pairs in kidney exchange: A dynamic weighted matching model","author":"Li Z.","year":"2019","unstructured":"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).","journal-title":"Proceedings of the 2019 ACM Conference on Economics and Computation"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329556"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0884"},{"key":"e_1_3_2_37_2","article-title":"Group-level fairness maximization in online bipartite matching","author":"Ma Will","year":"2021","unstructured":"Will Ma, Pan Xu, and Yifan Xu. 2021. Group-level fairness maximization in online bipartite matching. arXiv preprint arXiv:2011.13908 (2021).","journal-title":"arXiv preprint arXiv:2011.13908"},{"key":"e_1_3_2_38_2","article-title":"Fair dynamic rationing","author":"Manshadi Vahideh","year":"2021","unstructured":"Vahideh Manshadi, Rad Niazadeh, and Scott Rodilitz. 2021. Fair dynamic rationing. Available at SSRN 3775895 (2021).","journal-title":"Available at SSRN 3775895"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","DOI":"10.1145\/3391403.3399519","article-title":"Online policies for efficient volunteer crowdsourcing","author":"Manshadi Vahideh","year":"2020","unstructured":"Vahideh Manshadi and Scott Rodilitz. 2020. Online policies for efficient volunteer crowdsourcing. In Proceedings of the 21st ACM Conference on Economics and Computation (2020).","journal-title":"Proceedings of the 21st ACM Conference on Economics and Computation"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","DOI":"10.1145\/3391403.3399458","article-title":"Matching algorithms for blood donation","author":"McElfresh Duncan C.","year":"2020","unstructured":"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).","journal-title":"Proceedings of the 21st ACM Conference on Economics and Computation"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_2_43_2","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press."},{"key":"e_1_3_2_44_2","first-page":"2210","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"34","author":"Nanda Vedant","year":"2020","unstructured":"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\u20132217."},{"key":"e_1_3_2_45_2","first-page":"5379","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"34","author":"Patil Vishakha","year":"2020","unstructured":"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\u20135386."},{"key":"e_1_3_2_46_2","article-title":"Discriminating tastes: Customer ratings as vehicles for bias","author":"Rosenblat Alex","year":"2016","unstructured":"Alex Rosenblat, Karen Levy, Solon Barocas, and Tim Hwang. 2016. Discriminating tastes: Customer ratings as vehicles for bias. Available at SSRN 2858946 (2016).","journal-title":"Available at SSRN 2858946"},{"key":"e_1_3_2_47_2","first-page":"4292","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915)","author":"Rossi Ryan A.","year":"2015","unstructured":"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\u201915), Blai Bonet and Sven Koenig (Eds.). 4292\u20134293."},{"key":"e_1_3_2_48_2","article-title":"Closing the GAP: Group-aware parallelization for online selection of candidates with biased evaluations","author":"Salem Jad","year":"2019","unstructured":"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).","journal-title":"Available at SSRN 3444283"},{"key":"e_1_3_2_49_2","article-title":"Matchings with group fairness constraints: Online and offline algorithms","author":"Sankar Govind S.","year":"2021","unstructured":"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).","journal-title":"arXiv preprint arXiv:2105.09522"},{"key":"e_1_3_2_50_2","article-title":"Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve","author":"Sinclair Sean R.","year":"2021","unstructured":"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).","journal-title":"arXiv preprint arXiv:2105.05308"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330793"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2675133.2675278"},{"key":"e_1_3_2_53_2","article-title":"Group-fairness in influence maximization","author":"Tsang Alan","year":"2019","unstructured":"Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. 2019. Group-fairness in influence maximization. arXiv preprint arXiv:1903.00967 (2019).","journal-title":"arXiv preprint arXiv:1903.00967"},{"key":"e_1_3_2_54_2","first-page":"4199","volume-title":"Proceedings of the 29th International Joint Conference on Artificial Intelligence","author":"Xu Yifan","year":"2020","unstructured":"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\u20134205."},{"key":"e_1_3_2_55_2","first-page":"2245","volume-title":"Proceedings of the 33rd Conference on Artificial Intelligence (AAAI\u201919)","author":"Zhao Boming","year":"2019","unstructured":"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\u201919). 2245\u20132252."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569705","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:57Z","timestamp":1750182537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3569705"],"URL":"https:\/\/doi.org\/10.1145\/3569705","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,12,31]]},"assertion":[{"value":"2022-02-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}