Bandit Learning in Matching Markets with Interviews

• URL: http://arxiv.org/abs/2602.12224v1
• Date: Thu, 12 Feb 2026 18:03:37 GMT
• Title: Bandit Learning in Matching Markets with Interviews
• Authors: Amirmahdi Mirfakhar, Xuchuang Wang, Mengfan Xu, Hedyeh Beyhaghi, Mohammad Hajiesmaili,
• Abstract summary: Two-sided matching markets rely on preferences from both sides, yet it is often impractical to evaluate preferences.<n>We study bandit learning in matching markets with interviews, modeling interviews as textitlow-cost hints that reveal partial preference information to both sides.
• Score: 16.603456812107975
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two-sided matching markets rely on preferences from both sides, yet it is often impractical to evaluate preferences. Participants, therefore, conduct a limited number of interviews, which provide early, noisy impressions and shape final decisions. We study bandit learning in matching markets with interviews, modeling interviews as \textit{low-cost hints} that reveal partial preference information to both sides. Our framework departs from existing work by allowing firm-side uncertainty: firms, like agents, may be unsure of their own preferences and can make early hiring mistakes by hiring less preferred agents. To handle this, we extend the firm's action space to allow \emph{strategic deferral} (choosing not to hire in a round), enabling recovery from suboptimal hires and supporting decentralized learning without coordination. We design novel algorithms for (i) a centralized setting with an omniscient interview allocator and (ii) decentralized settings with two types of firm-side feedback. Across all settings, our algorithms achieve time-independent regret, a substantial improvement over the $O(\log T)$ regret bounds known for learning stable matchings without interviews. Also, under mild structured markets, decentralized performance matches the centralized counterpart up to polynomial factors in the number of agents and firms.

Related papers

• An External Fairness Evaluation of LinkedIn Talent Search [55.18656975953939]
  We conduct an independent, third-party audit for bias of LinkedIn's Talent Search ranking system.<n>We focus on potential ranking bias across two attributes: gender and race.<n>Our analysis reveals an under-representation of minority groups in early ranks.
  arXiv  Detail & Related papers  (2025-11-13T19:10:49Z)
• 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)
• Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets [2.9833943723592764]
  We study the problem of online learning in competitive settings in the context of two-sided matching markets. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match.
  arXiv  Detail & Related papers  (2022-06-06T04:08:04Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Decentralized Competing Bandits in Non-Stationary Matching Markets [46.13741000158631]
  We introduce the framework of decentralized two-sided matching market under non stationary (dynamic) environments. We propose and analyze a decentralized and asynchronous learning algorithm, namely Decentralized Non-stationary Competing Bandits (textttDNCB) We characterize this emphforced exploration and obtain sub-linear (logarithmic) regret of textttDNCB.
  arXiv  Detail & Related papers  (2022-05-31T21:05:30Z)
• The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations [27.388757379210034]
  We introduce the Dichotomous Affiliate Stable Matching (DASM) Problem, where agents' preferences indicate dichotomous acceptance or rejection of another agent in the marketplace. Our results are threefold: (1) we use a human study to show that real-world matching rankings follow our assumed valuation function; (2) we prove that there always exists a stable solution by providing an efficient, easily-implementable algorithm that finds such a solution; and (3) we experimentally validate the efficiency of our algorithm versus a linear-programming-based approach.
  arXiv  Detail & Related papers  (2022-02-22T18:56:21Z)
• Byzantine-Robust Decentralized Learning via ClippedGossip [61.03711813598128]
  We propose a ClippedGossip algorithm for Byzantine-robust consensus optimization. We demonstrate the encouraging empirical performance of ClippedGossip under a large number of attacks.
  arXiv  Detail & Related papers  (2022-02-03T12:04:36Z)
• 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)
• Bandit Learning in Decentralized Matching Markets [82.39061186055775]
  We study two-sided matching markets in which one side of the market (the players) does not have a priori knowledge about its preferences for the other side (the arms) and is required to learn its preferences from experience. This model extends the standard multi-armed bandit framework to a decentralized multiple player setting with competition. We show that the algorithm is incentive compatible whenever the arms' preferences are shared, but not necessarily so when preferences are fully general.
  arXiv  Detail & Related papers  (2020-12-14T08:58:07Z)
• 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)

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.