Popular and Dominant Matchings with Uncertain and Multimodal Preferences

Gergely Csáji

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).

Complexity landscape for popular and dominant matchings across different preference models.

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

Abstract

We study the Popular Matching (PM) problem in multiple models, where the preferences of the agents in the instance may change or may be unknown or uncertain. In particular, we study an Uncertainty model, where each agent has a possible set of preference lists, a Multilayer model, where there are layers of preference profiles, and a Robust popularity model, where any agent may move some other agents up or down some places in his preference list. Our goal is always to find a matching that is popular in any possible preference profile. We study both one-sided (only one class of the agents have preferences) and two-sided bipartite markets. In the one-sided model, we show that all our problems can be solved in polynomial time by utilizing the structure of popular matchings. We also obtain nice structural results. With two-sided preferences, we show that all three above models lead to NP-hard questions for popular matchings. By using the connection between dominant matchings and stable matchings, we show that in the robust and uncertainty models, a certainly dominant matching in all possible preference profiles can be found in polynomial time, whereas in the multilayer model, the problem remains NP-hard for dominant matchings too. We also answer an open question about d-robust stable matchings.
BibTeX
@inproceedings{csaji2024popular,
  author = {Gergely Csáji},
  title = {{Popular and Dominant Matchings with Uncertain and Multimodal Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=F30AhNsPDF},
}
Figure