A Survey on Bandit Learning in Matching Markets

1 Introduction

The two-sided matching market, a classic model, has diverse applications in areas such as school admissions and labor markets. It has been extensively explored in literature, as seen in [Gale and Shapley, 1962; Roth, 1984; Roth and Sotomayor, 1992; Roth, 2002]. In this market, two sets of participants exist, each having preferences for those on the opposite side. Stability is a key property defining the matching's equilibrium. The problem of finding stable matchings in a given market has been studied for ages, with [Gale and Shapley, 1962] and [Roth and Sotomayor, 1992] making significant contributions. These studies usually assume that preferences are fixed and known. However, this assumption is often unrealistic in real-world applications, such as online labor markets where employers are uncertain about their preferences for workers and can learn through multiple rounds of iterative matching.

Multi-armed bandit (MAB) is an essential mechanism for decision - making when faced with uncertainty across multiple rounds. This framework typically involves a single player and K arms, where each arm has its own unique reward distribution that remains unknown to the player. The player's objective is to minimize their cumulative regret, defined as the expectation of the difference in cumulative rewards between the arm with the highest reward and the player's selected arm over T rounds. Given that the player can only observe the reward of the arm they choose to pull, they need to strike a balance between exploration, which means gathering information about the various arms, and exploitation, which involves choosing the arm that appears to be the best based on the available information.

∗Corresponding author.

The problem of bandit learning in matching markets is first introduced by [Das and Kamenica, 2005] and has been studied by a rich line of work [Liu et al., 2020; Liu et al., 2021; Basu et al., 2021; Sankararaman et al., 2021; Kong et al., 2022; Kong and Li, 2023; Zhang et al., 2022; Wang et al., 2022; Kong and Li, 2024; Kong et al., 2024]. Players and arms correspond to the participants on two sides of markets. Each player has an unknown preference, while arms are certain about their preferences over players. For example, employers are unsure of their preferences because they lack knowledge about workers' capabilities, which can only be understood through interactions. This problem aims to minimize the stable regret, defined as the reward difference between the stable matched arm and the player's selected arm over T rounds. When the stable matching is not unique, there are mainly two types of regret: one is the player-optimal stable regret concerning the player's most preferred stable matching; the other one is the player-pessimal stable regret with respect to the player's least preferred stable matching.

In addition to the fundamental one-to-one matching markets focused on minimizing stable regret, a series of research efforts explore other variations. One strand of work expands the market framework to the many-to-one scenario [Wang et al., 2022; Kong and Li, 2024]. Here, each arm has the capacity to accept multiple players. Another line of inquiry delves into non-stationary markets [Muthirayan et al., 2022; Ghosh et al., 2022]. In such markets, the preferences of each player do not remain constant but change over time. This dynamic nature adds a layer of complexity to the matching process, as algorithms must adapt to these evolving preferences. Some studies concentrate on the setting of two-sided unknown preferences [Pagare and Ghosh, 2023; Zhang and Fang, 2024b]. In this case, not only are the players' preferences a factor for the learner, but the preferences on the arm side are also unknown and appear random to the learner. Finally, there are works that shift the focus away from merely minimizing regret [Hosseini et al., 2024; Athanasopoulos et al., 2025]. Instead, they aim to minimize the sample complexity required to identify a stable matching. This approach emphasizes the efficiency of the matching process in terms of the amount of data needed, rather than just the quality of the matching in terms of regret.

This survey situates and structures the extensive body of literature on bandit learning for matching markets. In Section 2 we introduce the basic framework of bandit learning in matching markets. In Section 3 the problem lower bound is introduced. Section 4 introduces the existing algorithm for centralized environment and decentralized environment respectively. In Section 5, we introduce the works beyond the basic one-to-one matching markets. Section 6 summarizes the potential future directions.

2 Preliminaries

This section introduces the model of bandit learning in the one-to-one matching markets with one-sided unknown preferences, which is a basic model studied by most works.

Suppose there are N players and K arms. Denote N = {p1, p2, · · · , pN} as the set of players and denote K = {a1, a2, · · · , aK} as the set of arms. Most works assume N ≤ K to ensure no player will be unmatched. Each arm has a fixed preference rank πk,i over players. πk,i > πk,i′ means arm ak prefers player pi to pi′ . The preference of player pi over arm ak is modeled by the utility µi,k > 0. µi,k > µi,k′ implies that player pi prefers arm ak rather than ak′ . The preferences of players are random and unknown, and can be learned through interactive matching iterations.

For each player pi and arm ak ̸= ak′ , let ∆i,k,k′ = |µi,k -µi,k′ | be the reward gap between arm ak and ak′ for player pi. Define ∆ = mini,k,k′ ∆i,k,k′ > 0 as the minimum reward gap across all players and arms, which measures the hardness of the learning problem.

At each round t = 1, 2, . . . , each player pi proposes to an arm Ai(t). For each arm ak, denote A-1 k (t) = {pi : Ai(t) = ak} as the set of players who selects arm ak at round t. When more than one player selects aj, it accepts its most-preferred one in A-1 k (t), i.e. ak will match with pi ∈ argmaxpi∈A-1 k (t) πk,i. If a player pi is successfully matched with arm Ai(t), it will receive a random reward Xi(t) characterizing its matching experience, which we assume is a 1-subgaussian random variable with expectation µi,Ai(t). Otherwise, pi is rejected by its proposed arm and only gets reward Xi(t) = 0.

Stability is a key property of a matching in two-sided markets to prevent the system from collapse [Gale and Shapley, 1962; Roth and Sotomayor, 1992]. A matching ¯ A(t) = {(i, ¯ Ai(t)) : i ∈ [N]} is stable if no market participant wants to break up its current matching relationship and find a new partner. Formally speaking, there is no player-arm pair (pi, ak) such that µi,k > µi, ¯ Ai(t) and πk,i > πk, ¯ A-1 k (t) . It is worth noting that there may be multiple stable matchings in the market. Denoted M = {m : m is stable} as the set of all stable matchings. It is shown that there exists a stable matching m∗ ∈ M such that all players are matched with their most preferred stable arm [Gale and Shapley, 1962], i.e., µi,m∗i ≥ µi,mi for any m ∈ M, i ∈ [N], which is called the player-optimal stable matching. Meanwhile there also exists a stable matching m∗ ∈ M such that all players are matched with their least preferred stable arm, i.e., µi,m∗i ≤ µi,mi for any m ∈ M, i ∈ [N], which is called the player-pessimal stable matching.

Here we introduce a classic offline algorithm called the Gale-Shapley (GS) algorithm that efficiently finds a stable matching when preferences on both sides are known. This algorithm is also implemented by many online matching works thus we introduce it in this section. It proceeds in rounds: in each round, each unmatched participant proposes to the most preferred participant on their list who has not yet rejected them. The participants receiving proposals tentatively accept the best proposal they have received so far and reject the rest. This process continues until all participants are matched. The key feature of the GS algorithm is that it always terminates and produces a player-optimal stable matching, providing an efficient and reliable way to achieve stable pairings in various matching scenarios.

Given a specified horizon T, the learning objective is to minimize the stable regret for each player pi. Since there may exist multiple stable matchings, there are two different definitions of regret with respect to player-optimal stable matching m∗ and player-pessimal stable matching m∗ respectively. The player-optimal stable regret is defined as the difference between the cumulative reward received by being matched with m∗i and the cumulative reward received by pi over T rounds:

Here, the expectation is taken over by the randomness of the reward generation and the randomness inherent in the player's strategy. Similarly, the player-pessimal stable regret is defined as the difference between the cumulative reward received by being matched with m∗i and the cumulative reward received by pi over T rounds.

3 Lower Bound

[Sankararaman et al., 2021] provide the regret lower bound of Ω(max{N logT/∆2 ,K logT/∆}). They study the special market named Optimally stable bandits (OSB) where all arms share the same preferences and each player's stable matched arm is exactly its optimal arm, i.e., m∗i = argmaxk µi,k. In this instance, the Ω(N logT/∆2 ) comes from the collisions when other players select the stable matched arm of player i, and Ω(K log T/∆) comes from the necessary explorations.

Theorem1. (Theorem 7 in [Sankararaman et al., 2021]) For any agent i ∈ [N], under any decentralized universally consistent algorithm π on a OSB instance ν satisfies

From the lower bound analysis, the regret is lower bounded by two terms: the necessary explorations for those suboptimal arms, and the unavoidable collisions caused by other players' explorations. This analysis also guides the algorithm design idea to attain the better regret upper bound.

4 Existing Results

In this section we review existing algorithms with their conditions and the corresponding regret upper bound.

4.1 CentralizedMarket

[Liu et al., 2020] first theoretically analyze the online matching market with the bandit problem. They consider the centralized scenario, in which a platform receives the preferences of both sides and assign matching for each player. They apply both the ETC algorithm and the UCB algorithm to estimate the ranking.

In the centralized ETC algorithm, players first explore all arms in a round-robin way in the first h rounds. After that platforms collect players' estimated preferences for each arm based on empirical mean reward, and then the platform computes the player-optimal stable matching by running GaleShapley algorithm and each player keeps selecting its stable matched arm in the remaining rounds. Centralized ETC requires the knowledge of reward gap ∆ and time horizon T to determine the explore horizon h, and it achieves the O (K log(T )/∆2 ) player-optimal regret.

In the centralized UCB algorithm, each player estimates the reward of arm by UCB index. At each round the centralized platform runs Gale-Shapley algorithm based on the preferences ranked by UCB index. Each player follows platform's assigned estimated player-optimal stable matching at each round and updates their UCB indices. This algorithm does not require the knowledge of ∆ and T, but it may fail to converge to player-optimal stable matching and only converge to a stable matching in some preference structures. They prove the O (NK log(T)/∆2 ) player-pessimal regret for the centralized UCB algorithm.

Note that though the centralized UCB does not need to know the parameters T, ∆ beforehand, it can only achieve the sub-linear player-pessimal regret, which is a weaker notion of regret compared with player-optimal regret. This is because since each player ranks its preferences over arm based on the UCB index, it does not imply that the player will be able to select the arm with higher UCB index since the player might be rejected by running GS algorithm. Thus there may exist some arms with high UCB values but never be matched, which leads to the failure of the centralized UCB to attain sub-linear player-optimal stable regret.

Note that in real-world case, the centralized setting is rarely satisfied since it requires a platform that assigns actions for all players and is hard to achieve when the market size is large. Thus only few works study the centralized setting and most of the works study the more general decentralized setting.

4.2 DecentralizedMarket

This section introduces the literature of studying the decentralized market, where each player make decisions based on its own observation without the coordination from the central platform.

Known Matching Result at Each Round

In this subsection, we introduce decentralized algorithms that assume players can observe the entire matching result at each round, i.e., ¯ Ai(t) for every i ∈ [N].

[Liu et al., 2021] and [Kong et al., 2022] propose the UCB and TS-type algorithm for the decentralized market, respectively. They both obtain O (exp(N 4 )N 5K2 log2 (T)/∆2 ) player-pessimal stable regret. The algorithm design idea is that each player tries to select the best possible successfully matched arm based on the last round's matching information, which means they will select the best possible arm where no collisions happen with high probability. And this selection approach will converge to a stable matching when each player has the correct estimation of the best possible arm, which is guaranteed by the UCB algorithm [Liu et al., 2021] and the TS algorithm [Kong et al., 2022], respectively.

Subsequently, [Kong and Li, 2023] carries out the in-depth research. They put forward the explore-then-Gale-Shapley (ETGS) algorithm. At first, each player explores all arms in a round-robin way. When all players have identified their full preference rankings over all arms, they terminate the exploration and run the GS algorithm to obtain the player-optimal stable matching. To make each player aware of other players exploration status, the exploration process is divided by phases with exponentially growing length. After each phase, each player communicate with each other by selecting certain arms and observing the matching result. The work effectively improves the player-optimal stable regret bound. Specifically, it has enhanced the bound to O (K log(T )/∆2 ).

Not Observing Matching Result

In this subsection, we introduce the decentralized algorithms that assume players can only observe their matching information.

Since not observing the matching result is more challenging, most of the works study the market satisfying certain uniqueness conditions as a beginning. The uniqueness condition means the preferences over arms and players satisfy some constraints to ensure that the stable matching is unique.

The work of [Sankararaman et al., 2021] proposes the UCB-D3 algorithm based on the assumption of serial dictatorship, where each arm has the same preference over players. Intuitively, each player selects the arm with the highest UCB index while not facing colliding. Since the market satisfies the serial dictatorship where all arms have the same preferences over players, each player will converge to its stable matching sequentially from the most preferred player to the least preferred one. An O(NK logT/∆2 ) regret is derived. They also provide the lower bound analysis.

The work of [Basu et al., 2021] assumes the market satisfies α-condition, which generalizes the serial dictatorship [Sankararaman et al., 2021] and is the weakest sufficient condition to guarantee the uniqueness. They propose the UCB-D4 algorithm modified based on UCB-D3 algorithm while maintaining an additional deleting arm set. Each player will also converge to stable matching by the order determined by α-condition. They also achieve the O (NK log(T)/∆2 ) regret bound.

[Maheshwari et al., 2022] study the market satisfying α-reducible and proposes a communication-free algorithm, where each player does not communicate with other players to synchronous their information. Note that other works focusing on the same decentralized setting all permit the communication process that exchange the information among players, and this work only allows each player make decisions without information from any other players. α-reducible is also a uniqueness condition weaker than serial dictatorship but stronger than α-condition. In their work, each player runs a single-player adversarial bandit algorithm, which means other players' actions are treated as an adversary and take actions based on that player's strategy. Each player tunes its stochastic policy based on collision and reward information observed at each step. The technique of instancedependent regret for adversarial bandit is applied for obtaining the O (NK log(T )/∆2 ) stable regret.

As for the general matching markets, the work of [Zhang et al., 2022] improved the player-optimal stable regret. They have proposed the ML-ETC algorithm. By the structure of arms' preferences, players are divided into different levels. The choices of players with lower levels do not influence those with higher levels. Then the algorithm finds the playeroptimal stable matching from the highest level to the lowest. In the same level, each player explores all arms in a roundrobin way until they identify their full rankings of all arms, then they run the GS algorithm to find the stable matching, similar with [Kong and Li, 2023]. The difference is that in this work players communicate their information by collisions rather than the total matching result, which avoids observing the matching result at each round. Through this algorithm, they have achieved the player-optimal stable regret bound of O (K log(T )/∆2 ).

To improve the regret upper bound to reach the lower bound [Sankararaman et al., 2021], [Wang and Li, 2024] first study the market satisfying serial dictatorship. Since players have an order from the most preferred to the least preferred, each player runs the elimination algorithm to find the stable matched arm sequentially. Here elimination algorithm is a classic bandit algorithm where the learner explores arms in a round-robin way and eliminates the sub-optimal arm when it is identified not the best. Player p1 first runs the elimination algorithm to find its best arm, while player p2 runs the elimination algorithm for other arms except p1 selects. Then similarly for player pi, she runs the elimination algorithms for arms of those not selected by player p1, . . . , pi-1. Then the regret for player pi is bounded by O((i - 1) logT/∆2 + K logT/∆). Here O(K logT/∆) is derived from the number of explorations for sub-optimal arms. O((i - 1) logT/∆2 ) is obtained from the number of times player p1, . . . , pi-1 explores the stable arm of pi and thus she can not select its stable matched arm. It should be noted that ∆ is the minimum gap among all K arms and is smaller than that in the lower bound analysis, which is the minimum reward gap between sub-optimal arms and the stable matched arm. Thus there is still a gap on the dependence of ∆.

Recently [Kong et al., 2024] provides the improved algorithm for the decentralized general matching markets. To remove the dependence of K on the leading term, they use the elimination algorithm to explore the sub-optimal arm, similar to [Wang and Li, 2024]. Unlike identifying all rankings among arms and running the full steps of GS algorithms [Kong and Li, 2023; Zhang et al., 2022]. This work proposes the adaptive online GS algorithm, which divides each step of GS algorithm into exploration. At first, all players run the elimination algorithm to identify their best arms. Note that each player eliminates arms until the number of non-eliminated arms equals to the number of players, i.e., N. This design is to ensure all players can explore arms in a round-robin way without collisions. When all players have identified their best arms, they run one step of the GS algorithm. Those rejected players turn to explore their second best arms. And those accepted players keep selecting their matched arms. The next step of GS is performed when those rejected players have identified their second best arms. The algorithm finds the player-optimal stable matching when full steps of GS have been performed. An O(N 2 logT/∆2 +K logT/∆) player-optimal regret is obtained. This work removes the dependence on K in the leading term for general markets.

Theorem 2. [Kong et al., 2024] Following the algorithm proposed in [Kong et al., 2024], the player-optimal stable regret for each player pi satisfies

where ∆ is the minimum preference gap between arms that are more preferred than the next of the player-optimal stable arm among all players.

Note that there is still a gap between the problem lower bound Ω(N logT/∆2 + K logT/∆) [Sankararaman et al., 2021] and the state-of-the-art upper bound O(K logT/∆2 ) [Kong and Li, 2023; Zhang et al., 2022], O(N 2 logT/∆2 +K logT/∆) [Kong et al., 2024] in terms of both market size and definition of ∆. It remains an open question to close the gap for designing the optimal algorithm.

5 Other Variants

In this section, we introduce a line of works that study the setting beyond the basic one-to-one matching markets with one-sided unknown preference, which generalize the literature of bandit learning in matching markets.

5.1 Many-to-one MatchingMarket

In many real-world examples like school admissions, one side participants (schools) are able to match with multiple participants on the other side (students). This motivates the following extending setting of many-to-one matching markets.

[Wang et al., 2022] first study the problem of bandit learning in many-to-one matching markets, where each arm can accept multiple players rather than a single player. Specifically, each arm k ∈ [K] has a fixed capacity ck and it accept its most preferred top ck players at each round. This preference structure is called the responsiveness. This setting makes the system more complicated and players can be matched with an arm even though other players also propose to it. They study the decentralized matching market and propose the MOCA-UCB algorithm, which extends the CAUCB algorithm to the many-to-one setting [Liu et al., 2021]. Similarly they obtain the O (exp(N 4 )N 5K2 log2 (T)/∆2 ) player-pessimal stable regret.

[Zhang and Fang, 2024a] extend the work of [Zhang et al., 2022] to many-to-one setting with responsiveness preference. By the structure of arms' preferences, players are divided into different levels. The choices of players with lower levels do not influence those with higher levels. Then the algorithm finds the player-optimal stable matching from the highest level to the lowest. In the same level, each player explores all arms in a round-robin way until they identify their full rankings of all arms, then they run the GS algorithm to find the stable matching. Through this algorithm, they have achieved the player-optimal stable regret bound of O (K log(T )/∆2 ).

[Kong and Li, 2024] take an algorithm initially designed for the one-to-one setting and expand it to the more general many-to-one case. Through this expansion, they manage to reach a near-optimal bound for player-optimal stable regret. Nevertheless, single-player deviation can pose problems because of the requirements for collaboration. The primary objective in this research is to enhance the regret bound in many-to-one markets while maintaining incentive compatibility. To begin with, for the responsiveness setting, the adaptively explore-then-deferred-acceptance (AETDA) algorithm is put forward. This algorithm enables the derivation of an upper bound for player-optimal stable regret and also proves its incentive compatibility. It offers a polynomial player-optimal guarantee in matching markets without the need to have prior knowledge of ∆.

[Li et al., 2024] study the many-to-one matching market with complementary preferences and quota constraints. Here arms are divided into M types, and each type m includes Km arms. Each player has fixed but unknown preferences over each arm's type, and at each time each player has a quota constraint that each type's arm has to be matched over a certain numbers, and the total matched number is also bounded.

Real world examples include: firms seeking certain number of workers with skills that complement their existing workforce, sports teams forming teams with certain number of players that have complementary roles. A centralized Multiagent Multi-type Thompson Sampling (MMTS) algorithm is proposed and it achieves an O(√T ) Bayesian regret with high probability.

5.2 Non-stationaryMatching

Since participants' preference might shift, there are some studies focusing on non-stationary rewards, where the reward distribution is not fixed and may vary over time.

The work of [Muthirayan et al., 2022] specifically examines learning when players' preferences are time-varying and unknown. They assume that the number of preference changes is upper bounded by a constant L and this is known beforehand. The algorithm design idea is that the algorithm restart after each L-1/2T 1/2 rounds and the algorithm runs centralized UCB at each phase. It is demonstrated that with the proposed algorithm, each player gets a uniform sub-linear regret of O(L1/2T 1/2 )(1 +∆-2 ). The article also discusses the extensions of the algorithm to situations where the number of changes does not need to be known beforehand.

[Ghosh et al., 2022] focus on a different non-stationary setting where at each time the reward change for an arm does not exceed a small term δ. It introduces the framework of a decentralized two-sided matching market in nonstationary (dynamic) environments under the serial dictatorship setting. The authors propose and analyze a decentralized and asynchronous learning algorithm called Decentralized Non-stationary Competing Bandits (DNCB). In this algorithm, agents use successive elimination type learning algorithms to learn their preferences over the arms. The complexity of understanding the system comes from the asynchronous action selection of competing bandits and the situation where lower ranked agents can only learn from a set of arms not dominated by higher ranked agents, resulting in "forced exploration". By carefully defining complexity parameters, the paper characterizes this "forced exploration" and achieves sub-linear (logarithmic) regret for DNCB. Additionally, the theoretical findings are validated through experiments.

5.3 Two-sided Unknown Preference

When considering the market where preferences of participants on two sides are both unknown and random, it is more general than the basic one-sided unknown setting and needs more careful technique balancing the exploration on both sides.

[Pagare and Ghosh, 2023] propose a multi-phase explorethen-commit type algorithm namely Epoch-based CA-ETC (collision avoidance explore then commit) for this problem that does not require any communication across agents (players and arms) and hence fully decentralized. They show that the for the initial epoch length of T0 and subsequent epochlengths of 2ℓ/γ T0 (for the ℓ-th epoch with γ ∈ (0, 1) as an input parameter to the algorithm), CA-ETC yields a player optimal expected regret of O(T0( K logT T0∆2 )1/γ + T0(T/T0)γ )

for each player. Furthermore, we propose several other baselines for two-sided learning for matching markets.

[Zhang and Fang, 2024b] model the arm side, with a reasonable "Rational Condition", where their objective is to maximize their individual rewards. Then, on the player side, they introduce the Round-Robin ETC algorithm, incorporating various techniques to tackle challenges arising from unreliable feedback from arms and the absence of information and communication. Through rigorous analysis, we demonstrate that the optimal matching for the proposing side can be achieved with high probability Their algorithm achieves an O(logT) player-optimal stable regret.

5.4 Objectives BeyondMinimizing Regret

There is a line of works studying the objectives beyond minimizing regret. Specifically, they mainly study the sample complexity of finding a stable matching.

[Hosseini et al., 2024] showcase crucial techniques within the realm of learning preferences. These techniques are centered around leveraging the structure of stable solutions. Specifically, they made use of the known preferences of arms in the arm-proposing variant of the Deferred Acceptance (DA) algorithm. By doing so, and by eliminating arms at an early stage, they were able to provably decrease the sample complexity associated with finding stable matchings. Moreover, from an experimental perspective, this approach had minimal influence on optimality, which was gauged by the metric of regret.

[Athanasopoulos et al., 2025] focus on the centralized case where, at each time step, an online platform matches agents and gets a noisy evaluation of their preferences. They introduce the concept of a probably correct optimal stable matching, a special type of probably approximately correct (PAC) solutions requiring the output matching to be optimal with high probability. First, they analyze an algorithm that uniformly samples all available agent pairs, similar to the ETC strategy, demonstrating its ability to produce the optimal stable matching with high probability and providing a bound on its sample complexity. Next, they explore an action elimination-based algorithm, which improves sample efficiency and reduces dependence on instance - specific parameters. Additionally, they enhance sample complexity by modifying the stopping criterion, enabling the algorithm to terminate when enough information is gathered.

6 Future Direction

6.1 Optimal Analysis for MatchingMarkets

There still exists a gap between the existing best upper bound O(N 2 logT/∆2 + K logT/∆) when N 2 ≤ K [Kong et al., 2024], O(K logT/∆2 ) when N 2 > K [Kong and Li, 2023; Zhang et al., 2022], and the problem lower bound Ω(max{N log T/∆2 , K log T/∆}) [Sankararaman et al., 2021]. Thus a natural remaining open question is to design an optimal algorithm achieves the best regret bound.

A possible approach for designing the optimal algorithm is to refine the procedure of the adaptive Gale-Shapley algorithm proposed by [Kong et al., 2024]. The key bottleneck to attain the O(N logT/∆2 ) regret is because at each step of GS, the number of collisions is only bounded by O(N logT/∆2 ), and this multiplies the maximum number of steps N contributes to the final regret bound. To improve the final regret bound, it is likely to modify the algorithm to be more adaptive for reducing the bound of collision times at each step.

6.2 Incentive Compatibility Analysis

Incentive compatibility is a key yet under-explored aspect in matching markets with bandit learning. Agents in these markets often have private information and self-interested motives. To ensure bandit-based matching mechanisms are incentive-compatible, agents must be motivated to truthfully disclose their preferences and characteristics.

Most existing studies on bandit learning in matching markets prioritize matching efficiency over agents' strategic behavior [Kong and Li, 2024]. Future research could delve into how different bandit algorithms interact with incentive compatibility. This could involve analyzing agent incentives in various matching market types using game-theoretic models. Additionally, there's a need to design mechanisms that are both incentive compatible and computationally efficient, perhaps by exploring approximate incentive compatibility concepts. Empirical studies, whether in a lab or using real-world data, are also essential to validate theoretical results and refine these mechanisms for practical use.

6.3 Robustness Analysis Against Attack

In the context of bandit learning in matching markets, robustness against attack has emerged as a critical area that demands in-depth exploration in future research. With the increasing digitization and reliance on automated matching systems, these markets become vulnerable to various malicious attacks that can disrupt the normal operation of bandit-based algorithms and undermine the fairness and efficiency of the matching process.

One of the primary future research directions is to comprehensively identify and categorize the potential attack models. For example, in a matching market for online auctions, malicious bidders could launch shill-bidding attacks. They create fake identities to inflate the prices artificially, tricking the bandit-learning algorithm into making sub-optimal matching decisions. In a ride-sharing matching market, attackers might manipulate location data to disrupt the efficient pairing of drivers and passengers. By precisely defining these attack models, researchers can then develop targeted defense mechanisms.

6.4 Other Possible Settings

There are several other possible settings in bandit learning for matching markets that merit future research attention.

Dynamically ChangingMarket Structures. Most current studies assume relatively static market structures in the context of bandit learning for matching. However, in real-world scenarios, markets are often dynamic. For example, new participants may continuously enter the market, and existing ones may leave. In a job-matching market, new companies may be established, creating new job openings, while some existing firms might downsize or go out of business. Future research could explore how bandit learning algorithms can adapt to such dynamic market structures. This may involve developing algorithms that can quickly re-evaluate and adjust the matching strategy as the market composition changes. One approach could be to use time-series analysis techniques to predict the inflow and outflow of market participants and then incorporate these predictions into the bandit-learning framework.

Contextual Matching Markets. Contextual bandit for online matching market holds great significance as it enables more accurate and efficient matching in various real-world scenarios, from e-commerce platforms connecting buyers and sellers to ride-sharing services pairing passengers with drivers, where the preference of a participant is related to its contextual information. Specifically, each arm ak is associated with a fixed context Xk ∈ Rd , where d is the number of dimension. The preference of player pi over arm ak is determined by a reward function Ri(Xk), such as the linear model with Ri(Xk) = θ⊤ i Xk. The learner aims to learn the reward model of each player through multiple matchings. This model can well describe how the player's preference is determined by various attributes of each arm.

7 Conclusion

The study of bandit learning in two-sided matching markets has emerged as a rapidly evolving research area. This survey comprehensively reviews and systematically organizes the abundant literature on bandit learning in matching markets. These works have shown great promise in improving the efficiency of matching, whether it is in job-seeker-employer match-ups, ride-sharing driver-passenger pairings, or online dating platform matches. This survey covers the existing theoretical achievements and various related aspects.

There are still numerous avenues for future research. The optimal algorithm design is not sufficiently explored and remains open. Incentive compatibility has also been recognized as a crucial factor, ensuring that market participants are motivated to truthfully reveal their preferences is essential for the proper functioning of bandit-based matching mechanisms. Robustness analysis against attacks, is becoming increasingly important in the face of potential malicious disruptions in digital matching markets. Additionally, the study of bandit learning in dynamically changing market structures, and contextual matching market structure, also hold great potential for advancing the field. Overall, the future of bandit learning in matching markets is bright, with the potential to bring about more efficient and robust matching systems across a wide range of industries.

Acknowledgements

The corresponding author Shuai Li is supported by National Key Research and Development Program of China (2022ZD0114804) and National Natural Science Foundation of China (62376154). Fang Kong is supported by the Guangdong Basic and Applied Basic Research Foundation 2025A1515011412.