New algorithm solves popular matchings under preference variation

A new paper by Gergely Csáji tackles the challenge of popular matchings when preferences are incomplete, criterion-dependent, or noisy. The research models four distinct types of preference variation: independent uncertainty (random preferences), multilayer profiles (multiple preference layers), bounded swap perturbations (small changes in rankings), and aggregation (combining multiple profiles). For one-sided markets (e.g., assigning workers to tasks), Csáji provides polynomial-time algorithms that find matchings popular in every possible realization or with respect to the aggregate comparison in the aggregation model.

The main algorithmic contribution is a pseudo-polynomial extension of the primal–dual level algorithm for popular common bases, moving from partial-order preferences to bounded integral skew-symmetric comparison margins. This technique also handles ties in one-sided markets. For two-sided markets (e.g., students to schools), the problem of finding popular matchings becomes NP-hard in all four models, though dominant matchings (a stronger concept) remain tractable under independent uncertainty and bounded swap perturbations. The work advances both theoretical understanding and practical algorithms for matching markets, with implications for robust assignment systems that must withstand uncertain or changing preferences.