Learning Stable Matchings under Social Influence: A Bandit Approach

In many matching markets, participants evaluate options individually, discuss them with peers, and revise their preferences before a final matching is made. The preferences governing stability therefore reflect both personal experience and social influence. However, existing learning models in matching markets abstract away this deliberation stage, treating preferences as fixed lists to be learned in isolation through direct interaction feedback. We study a pure-exploration setting where direct interactions reveal noisy intrinsic evaluations, but the preferences that determine stability emerge only after these evaluations propagate through a social network. Our goal is to identify the player-optimal socially stable matching with as few evaluations as possible. The central difficulty is a decoupling of evidence and decision: uncertainty in one player’s final ranking often originates from the intrinsic evaluations of others. Consequently, observing an unresolved ranking does not reveal which player–arm pairs should be sampled next. We characterize this challenge by establishing an instance-dependent lower bound through a network-weighted information-allocation problem over intrinsic source pairs, capturing necessary evidence to rule out alternatives that make the target matching unstable or no longer player-optimal. Guided by this variance structure, we design Source-Aware Elimination with Quadratic Allocation (SAE-Q), an algorithm that coordinates evaluations across source pairs to resolve network-propagated uncertainties. We prove that SAE-Q identifies the target matching with probability at least $1-\delta$, achieving instance-dependent sample complexity guarantees explicitly governed by network topology and social preference gaps. Our results show that social influence shapes not only which matching is stable, but also where evidence must be collected to identify it.