Bandit Learning in Matching Markets: Utilitarian and Rawlsian Perspectives

• URL: http://arxiv.org/abs/2412.00301v1
• Date: Sat, 30 Nov 2024 01:04:58 GMT
• Title: Bandit Learning in Matching Markets: Utilitarian and Rawlsian Perspectives
• Authors: Hadi Hosseini, Duohan Zhang,
• Abstract summary: Two-sided matching markets have demonstrated significant impact in many real-world applications. Traditional models often assume that preferences are known, which is not always the case in modern markets.
• Score: 14.718999704371312
• License:
• Abstract: Two-sided matching markets have demonstrated significant impact in many real-world applications, including school choice, medical residency placement, electric vehicle charging, ride sharing, and recommender systems. However, traditional models often assume that preferences are known, which is not always the case in modern markets, where preferences are unknown and must be learned. For example, a company may not know its preference over all job applicants a priori in online markets. Recent research has modeled matching markets as multi-armed bandit (MAB) problem and primarily focused on optimizing matching for one side of the market, while often resulting in a pessimal solution for the other side. In this paper, we adopt a welfarist approach for both sides of the market, focusing on two metrics: (1) Utilitarian welfare and (2) Rawlsian welfare, while maintaining market stability. For these metrics, we propose algorithms based on epoch Explore-Then-Commit (ETC) and analyze their regret bounds. Finally, we conduct simulated experiments to evaluate both welfare and market stability.

Related papers

• Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty [5.250288418639076]
  We consider a learning problem for the stable marriage model under unknown preferences for the left side of the market. Our aim is to quickly identify the stable matching that is left-side optimal, rendering this a pure exploration problem with bandit feedback.
  arXiv  Detail & Related papers  (2025-01-06T13:59:57Z)
• Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
  Two-sided matching markets describe a class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. We exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions.
  arXiv  Detail & Related papers  (2024-10-06T06:47:53Z)
• An IPW-based Unbiased Ranking Metric in Two-sided Markets [3.845857580909374]
  This paper addresses the complex interaction of biases between users in two-sided markets. We propose a new estimator, named two-sided IPW, to address the position bases in two-sided markets.
  arXiv  Detail & Related papers  (2023-07-14T01:44:03Z)
• Fairness in Matching under Uncertainty [78.39459690570531]
  algorithmic two-sided marketplaces have drawn attention to the issue of fairness in such settings. We axiomatize a notion of individual fairness in the two-sided marketplace setting which respects the uncertainty in the merits. We design a linear programming framework to find fair utility-maximizing distributions over allocations.
  arXiv  Detail & Related papers  (2023-02-08T00:30:32Z)
• Parity in Markets -- Methods, Costs, and Consequences [109.5267969644294]
  We show how market designers can use taxes or subsidies in Fisher markets to ensure that market equilibrium outcomes fall within certain constraints. We adapt various types of fairness constraints proposed in existing literature to the market case and show who benefits and who loses from these constraints.
  arXiv  Detail & Related papers  (2022-10-05T22:27:44Z)
• Competition, Alignment, and Equilibria in Digital Marketplaces [97.03797129675951]
  We study a duopoly market where platform actions are bandit algorithms and the two platforms compete for user participation. Our main finding is that competition in this market does not perfectly align market outcomes with user utility.
  arXiv  Detail & Related papers  (2022-08-30T17:43:58Z)
• Deep Q-Learning Market Makers in a Multi-Agent Simulated Stock Market [58.720142291102135]
  This paper focuses precisely on the study of these markets makers strategies from an agent-based perspective. We propose the application of Reinforcement Learning (RL) for the creation of intelligent market markers in simulated stock markets.
  arXiv  Detail & Related papers  (2021-12-08T14:55:21Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  We develop a framework and algorithms for learning stable market outcomes under uncertainty. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.
  arXiv  Detail & Related papers  (2021-08-19T17:59:28Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)
• Robust Market Making via Adversarial Reinforcement Learning [5.482532589225552]
  We show that adversarial reinforcement learning can be used to produce market marking agents robust to adversarial and adaptively-chosen market conditions. We show that our ARL method consistently converges, and we prove for several special cases that the profiles that we converge to correspond to Nash equilibria in a simplified single-stage game.
  arXiv  Detail & Related papers  (2020-03-03T22:40:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.