Popular Matchings under Preference Variation and an Algorithm for Popular Common Bases with Integral Comparison Margins

Abstract

Preference information in matching markets may be incomplete, criterion-dependent, or noisy. We study popular and dominant matchings under four forms of preference variation: independent uncertainty, multilayer profiles, bounded swap perturbations, and aggregation across profiles. In one-sided markets, we show that all four models admit polynomial-time algorithms for finding a matching that is popular in every relevant realization, or popular with respect to the aggregate comparison in the aggregation model. The aggregate result follows from our main optimization contribution: a pseudo-polynomial extension of the primal--dual level algorithm for popular common bases from partial-order preferences to bounded integral skew-symmetric comparison margins. We further extend our polynomial-time algorithms for one-sided markets with ties. In two-sided markets, the existence problem for popular matchings is NP-hard in all four models, whereas dominant matchings remain tractable under uncertainty and bounded swap perturbations.