In traditional economics, the Gale-Shapley (Deferred Acceptance) algorithm provides a elegant solution for matching two groups—such as students and colleges—into a "stable" state where no two parties would prefer each other over their current partners. However, Gale-Shapley assumes that everyone arrives with a perfectly ranked list of preferences.
In the real world, preferences are rarely known upfront. A freelancer on Upwork doesn't know which employers are best until they work for them; a lender in a P2P market doesn't know a borrower's reliability until the loan is issued. This has led to a new research direction that merges Multi-Armed Bandits (MAB) with Matching Theory, creating a framework where agents must learn their preferences through trial and error while competing for limited resources.
The Challenge of Competing Bandits
In a standard multi-armed bandit problem, an agent pulls "arms" to maximize their own reward. In a matching market, the arms are other agents who have their own preferences. As Horia Mania, Lydia T. Liu, and Michael I. Jordan established in Competing Bandits in Matching Markets, this creates a "collision" problem. If two agents attempt to match with the same high-quality arm, only one succeeds (based on the arm's preference), leaving the other with no reward.
This competition transforms the learning process. An agent cannot simply explore the best-looking options; they must also learn where they stand in the market's hierarchy to avoid wasted effort on "arms" that will ultimately reject them.
From One-Sided to Two-Sided Uncertainty
Much of the early work in this field assumed an informational asymmetry: one side of the market (the "agents") is learning, while the other side (the "arms") has fixed, known preferences. As noted by Shuai Li and Zilong Wang in A Survey on Bandit Learning in Matching Markets, this assumption is often unrealistic.
Recent research has pivoted toward two-sided uncertainty, where both sides must simultaneously learn their rankings through interaction. This creates a complex feedback loop:
- Mutual Discovery: Hadi Hosseini and Duohan Zhang argue in Putting Gale & Shapley to Work that coordinating stable outcomes becomes significantly harder when both sides are updating their internal models at the same time.
- Complex Constraints: Real markets often involve more than simple one-to-one pairings. Yuantong Li and Xiaowu Dai introduced Multi-agent Multi-type Thompson Sampling (MMTS) in Two-sided Competing Matching Recommendation Markets to handle "complementary" preferences—such as a firm needing a specific mix of different skill sets while learning the quality of individual applicants.
Achieving Stability Without Full Information
The ultimate goal of these algorithms is to reach a stable matching with minimal "regret" (the difference between the rewards earned and the rewards of the best possible stable matching).
A key insight in this direction is that we don't actually need to learn every agent's entire preference list to find the right match. Andreas Nikolaos Athanasopoulos and Christos Dimitrakakis proposed the Probably Correct Optimal Stable Matching (PCOS) framework in Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty, which uses adaptive sampling to identify the optimal stable matching efficiently.
Furthermore, Soumya Basu demonstrated in Competing Bandits in Matching Markets via Super Stability that by targeting super-stability, algorithms can converge much faster. Super-stability accounts for "indifference"—situations where an agent cannot distinguish between two options—which Fang Kong and John C. S. Lui identify as a critical real-world factor in Bandit Learning in Matching Markets with Indifference.
Decentralization and Coordination
In many digital platforms, a central controller cannot dictate matches; agents must act independently. Chinmay Maheshwari and Eric Mazumdar explored this in Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets. They showed that even without explicit communication or a central clearinghouse, agents can converge to a stable matching simply by observing their own successes and failures (collisions).
This decentralized approach is vital for scaling matching algorithms to massive markets like P2P lending, as explored by Soumajyoti Sarkar in Centralized Borrower and Lender Matching under Uncertainty for P2P Lending, where the platform must balance the learning needs of thousands of lenders against the immediate funding needs of borrowers.