Popular and Dominant Matchings with Uncertain and Multimodal Preferences

Gergely Csáji, Xiantao Cai, Jia Wu, Wenbin Hu

Introduction

Matching theory is a cornerstone of economics and computer science, with applications ranging from labor markets to organ donation. Traditional models assume fixed, complete preference rankings. However, real-world preferences are often characterized by uncertainty, multiple criteria (multilayered), or temporal shifts (robustness). This paper investigates the computational complexity of finding "popular" matchings—assignments where no alternative matching is preferred by a majority of agents—under these realistic constraints. The central goal is to identify "certainly popular" matchings that remain popular across all possible variations of agent preferences.

Methodology

The research employs a rigorous framework of combinatorial optimization and computational complexity analysis. The author utilizes several key techniques:

  • Graph Reductions: Transforming matching problems into weighted graph problems that can be solved using classic tools like the Hungarian method or Linear Programming. This allows the researchers to leverage well-established algorithmic frameworks to tackle new variations of the matching problem.
  • Stable-to-Dominant Mapping: Utilizing a known mathematical connection where "dominant" matchings (a special, larger type of popular matching) can be found by looking at "stable" matchings in a modified version of the graph. This mapping is crucial for proving the tractability of certain dominant matching problems.
  • Complexity Proofs: Using mathematical reductions to show that certain versions of the problem are NP-hard. By showing that these problems are at least as hard as known difficult problems, the author establishes that they likely cannot be solved efficiently for large-scale instances.

Key Insights

A primary finding is the significant divergence in complexity between one-sided and two-sided markets.

  • The One-Sided Advantage: In scenarios where only one set of agents has preferences (e.g., students choosing housing), finding popular matchings remains computationally efficient across all studied models of uncertainty. This suggests that centralized allocation systems can be made robust to preference uncertainty without sacrificing computational efficiency.
  • Two-Sided Intractability: Conversely, when both sides have preferences (e.g., the marriage problem), the introduction of uncertainty or multiple layers typically renders the problem NP-hard. This highlights a fundamental challenge in designing fair matching mechanisms for complex labor markets.
  • Dominant Matchings as a Tractable Alternative: Surprisingly, finding a matching that is "certainly dominant" is often easier than finding one that is "certainly popular." In two of the three uncertainty models, dominant matchings can be found in polynomial time even in two-sided markets, providing a potential workaround for practitioners.

Key Results

The paper provides a comprehensive complexity "cheat sheet" summarizing the feasibility of finding various types of matchings under different uncertainty models.

Complexity results for popular and dominant matchings under various models of uncertainty.

As shown in the table above, two-sided popular matchings are almost universally NP-hard, even with minimal constraints like two layers of preferences. In contrast, one-sided popular matchings are consistently solvable in polynomial time. The paper also resolves a long-standing open question by proving that finding a robustly stable matching (where agents can swap adjacent items in their preference lists) is solvable in polynomial time.

Conclusion and Future Directions

While the paper establishes a clear boundary between tractable and intractable matching problems, it highlights the need for approximation algorithms for NP-hard cases. Future research should explore scenarios where uncertainty is restricted to one side of a two-sided market or investigate specialized settings where the NP-hardness of dominant matchings might be circumvented.

Summary updated

BibTeX
@inproceedings{csaji2024popular,
  author = {Gergely Csáji and Xiantao Cai and Jia Wu and Wenbin Hu},
  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