2023/10/22 by Gergely Csáji, Csáji, Gergely
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · Social Sciences · #Auction Theory and Applications #Bipartite graph #Combinatorics #Computer science #Electoral Systems and Political Participation #Game Theory and Voting Systems #Graph #Matching (statistics) #Mathematical economics #Mathematical optimization #Mathematics #Preference #Set (abstract data type) #Statistics #Time complexity #cs.GT
paper · pdf · doi:10.48550/arxiv.2310.14288
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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.