Abstract
We study the Popular Matching (PM) problem in multiple models where the preferences of agents may change, be unknown, or be uncertain. Specifically, we investigate an Uncertainty model (sets of possible preference lists), a Multilayer model (multiple layers of preference profiles), and a Robust popularity model (preferences subject to local shifts). Our objective is to identify matchings that remain popular across all possible preference profiles. We analyze both one-sided (House Allocation) and two-sided bipartite markets. In one-sided models, we demonstrate that these problems are solvable in polynomial time. In two-sided markets, while finding popular matchings is generally NP-hard, we show that finding "certainly dominant" matchings remains efficient in the robust and uncertainty models, though it remains NP-hard in the multilayer model. Finally, we resolve an open question regarding $d$-robust stable matchings.
Introduction
In classical matching theory, algorithms like Gale-Shapley assume fixed, complete preference lists. However, real-world preferences are often fluid or multifaceted. Agents may be undecided (Uncertainty), evaluate partners based on different criteria like prestige versus location (Multilayer), or have preferences that shift slightly over time (Robustness).
While stable matchings are a standard solution, they can be significantly smaller than maximum matchings. Popularity offers a more flexible fairness criterion: a matching is popular if no other matching would win a head-to-head majority vote. This research maps the computational boundaries of finding popular matchings when preferences are messy or uncertain.
Methodology
The study employs a mix of graph theory, linear programming (LP), and complexity analysis:
- Verification: To check if a matching is popular, the author constructs a weighted bipartite graph where the problem reduces to finding a minimum weight perfect matching, solvable via the Hungarian method.
- Reductions to Stability: A key technique involves transforming the search for "dominant" matchings—a high-quality subset of popular matchings—into a search for stable matchings in a modified graph.
- Complexity Analysis: Standard reduction techniques are used to prove NP-completeness for difficult two-sided market scenarios, while polynomial-time algorithms are developed for one-sided markets.
Key Results and Complexity Landscape
The research provides a comprehensive map of the computational complexity for these problems. A major finding is the "Dominant Loophole": while finding a certainly popular matching in two-sided markets is NP-hard, finding a certainly dominant matching is often computationally easy (P).
As shown in the table above, the Multilayer model is the most computationally challenging, remaining NP-hard even for dominant matchings. Conversely, One-sided markets (House Allocation) are remarkably resilient, with all three uncertainty models remaining solvable in polynomial time.
Key Insights
- Resilience of One-Sided Markets: In scenarios where only one side has preferences (e.g., students picking dorms), the structure of popular matchings allows for efficient computation despite uncertainty.
- Solving Open Questions: The paper proves that finding a $d$-robust stable matching (where agents can independently make $d$ swaps) is solvable in polynomial time, answering a question posed by Chen et al. [2021].
- Dominant Matchings as a Practical Alternative: Because certainly dominant matchings are easier to find than certainly popular ones in two-sided markets, they provide a more practical target for algorithm designers in uncertain environments.
Limitations and Future Work
While this work clarifies the complexity of many scenarios, some gaps remain. The NP-hardness of the Multilayer model holds even in restricted settings (e.g., only two layers), and finding solvable sub-cases is an open challenge. Additionally, the complexity of "one-sided uncertainty" within a two-sided market—where only one side's preferences are uncertain—remains unknown. Future research may also extend these models to other optimality notions like Pareto-optimality or rank-maximal matchings.
Summary updated