Matching Under Preferences (MATCH-UP) is a research field which investigates the complexities and algorithms of matching markets, where agents or entities are paired based on individual preferences to meet certain criteria such as stability or fairness. Although matching markets have broad real-world applications—including labor allocation, organ exchanges, and educational placements—the computational landscape of the problems therein often presents as NP-complete or beyond.

Parameterized Complexity Theory (PCT), established by Downey and Fellows in the 1980s, has emerged as a robust framework for dissecting the computational intricacies of NP-hard problems. However, the primary application of PCT has largely been confined to graph-theoretical challenges.

In this interdisciplinary Dagstuhl Seminar, we intend to catalyze a synergy between MATCH-UP and PCT experts. The aim is to collaboratively explore how cutting-edge parameterized techniques can be employed to develop exact algorithms that tackle the inherent computational difficulties in matching markets.

Participants will engage in intensive cross-disciplinary discussions, with a spotlight on deploying parameterized methods to bypass or mitigate computational challenges within the scope of MATCH-UP. The topics under consideration will include, but are not limited to:

• Classical problems with new and natural parameterizations. Despite the many NP-hard problems in the MATCH-UP area, only a few parameterizations are known for which they admit FPT-algorithms. Problems that are likely to be of interest include hard variants of the Hospitals / Residents problem (e.g., involving couples, lower quotas or ties) where we seek an arbitrary or maximum-size stable matching. Structural parameters could be considered here, relating to the structure of the underlying “acceptability graph”. Other parameters could be based on distance from certain structured preference domains (e.g., where all residents are uniformly ranked in a “master list” or have single-peaked preferences).
• Dynamic models, online matching, multi-modal settings. As opposed to static models, there is a relative dearth of research dealing with dynamic, online or multi-modal settings where preferences or the underlying graph may be subject to change, or each agent has multiple preferences each depending on a different issue. A notable exception in the dynamic setting is the Incremental Stable Matching problem where the task is to adapt a given stable matching to modified preferences.
• Stable hypergraph matching. Hypergraphs are a powerful generalization of graphs that enable us to model situations where relations are not necessarily binary. Problems that fall into the framework of stable hypergraph matchings include the Multi-dimensional Stable Roommates problem and the Hospitals/Residents with Couples.
• Control and manipulation. When there is no solution that meets the requirements imposed, a central planner may have the ability to adjust the problem instance in ways that can facilitate a more favorable outcome. The task of such a central planner or authority is to take certain control actions (as few as possible) in order to achieve their goals.
• Different solution concepts. Besides stability, other notions of fairness or optimality are also of interest. Such notions might be motivated by different applications, or they may arise as a compromise in situations when stability cannot be achieved. Among these optimality concepts, popularity is an important one, which is not only easily motivated by applications when an election lies at the heart of a decision-making process, but additionally has a very strong theoretical background.

Creative Commons BY 4.0

Jiehua Chen, Christine Cheng, David Manlove, and Ildikó Schlotter