Frontiers of Parameterized Algorithmics of Matching under Preferences

The set of stable matchings has a very interesting structure in both the Stable Marriage (SM) and Stable Roommates (SR) settings. For SM, I describe the role of posets and distributive lattices and how they are used to design polynomial-time algorithms or prove hardness results. For SR, I show how the closed subsets of posets are generalized to the complete closed subsets of mirror posets and how distributive lattices are generalized to median graphs. I end the talk by noting that structural results on stable matchings can be exported to other fields that study distributive lattices and median graphs.

We consider bipartite stable many-one matching in combination with so called diversity constraints: entities on the “many”-side have certain (possibly intersecting) types and entities on the “one”-side have lower and upper bounds constraining how many entities of each type must be and are allowed to be matched to them respectively. This can for example be used to model college admission with affirmative action towards certain groups of students. In joint work with Jiehua Chen and Robert Ganian [1] we showed that this problem is complete for the second level of the polynomial hierarchy and carried out an extensive analysis of its paraNP-hardness versus XP-time solvability with respect to all combinations of a set of natural parameters. In this talk, I gave an overview of these results.

In this talk, we consider the problem of finding a matching between two disjoint groups $D,H$ of agents. Each agent has a preference over a subset of the agents in the other group, and the preferences may contain ties. Strong stability is one of the well-studied properties of a matching in this setting. In this talk, we consider the following variant of strong stability. We are given a subset $S$ of $H$. If an agent in $S$ is not matched to any partner in the current matching, then this agent cannot become a member of a blocking pair. We prove that the problem of checking the existence of a strongly stable matching in this setting is generally hard, and give some polynomial-time solvable cases. Interestingly, one positive result gives a unified approach to the strongly stable matching problem in the ordinary setting and the envy-free matching problem.

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). However, if we ‘only’ ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.

Matching problems involving ordinal preferences and cardinal utilities arise in many practical applications. In this talk I will outline four applications that I have been involved in over the last 25 years, namely course allocation, project allocation, resident doctor allocation and kidney exchange. In each case I will describe the application and define the underlying matching model that arises from it. I will then give an overview of the known algorithmic results and suggest some directions for future research, especially from the perspective of parameterised complexity.

In my talk, I will give a brief overview of the motivation and main definition of parameterized algorithms. I introduce some of the standard techniques that are used to show parameterized problems to be fixed-parameter tractable. In particular, I show how matroid-based techniques are relevant for matching problems.

We describe complex matching scheme for assigning teams of human topic experts to projects, in such a way that several hard and soft criteria for the assignment are satisfied. Moreover, there are preferences of experts over projects, and over other experts, who they would like to be in a team with and who they prefer not having as team mates. Structural insights into the nature of the data lets us decompose highly intractable problem into simpler phases, each of which can be solved separately and the solutions to which can be amalgamated to a full assignment. The theoretical findings for the algorithm design are then turned into an efficient implementation and evaluated on real data set of experts and projects, leading to significant savings in computation time over previously used manual approaches.

In the second part, we will explore the rich world of structural parameters. Then, we will discuss tractable parameterizations of Integer Programming and examples of IP-based parameterized algorithms.

Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In this work we seek to identify structural properties of instances of stable matching problems which will allow us to design efficient algorithms using elementary techniques. We focus on the setting in which all agents involved in some matching problem can be partitioned into $k$ different types, where the type of an agent determines his or her preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation would arise in practice if agents form preferences solely based on some small collection of agents’ attributes. We also consider a generalisation in which each agent may consider some small collection of other agents to be exceptional, and rank these in a way that is not consistent with their types; this could happen in practice if agents have prior contact with a small number of candidates. We show that (for the case without exceptions), several well-studied NP-hard stable matching problems including Max SMTI (that of finding the maximum cardinality stable matching in an instance of stable marriage with ties and incomplete lists) belong to the parameterised complexity class FPT when parameterised by the number of different types of agents needed to describe the instance. For Max SMTI this tractability result can be extended to the setting in which each agent promotes at most one “exceptional” candidate to the top of his/her list (when preferences within types are not refined), but the problem remains NP-hard if preference lists can contain two or more exceptions and the exceptional candidates can be placed anywhere in the preference lists, even if the number of types is bounded by a constant.

We consider the stable marriage problem when agents’ preferences are restricted by (1) bounded preference lists, (2) number of attributes, and (3) the “range” of the preference lists. We show that models 1 and 2 realize arbitrary rotation posets for bound parameters. Consequently, many problems that are hard in general, e.g., counting stable matchings, are hard in these restricted models. On the other hand, $k$-range instance have rotation posets with pathwidth $O(k^2)$. Consequently, the following problems admit FPT algorithms parameterized by the instance’s range:

1. 1.

   counting stable matchings,

2. 2.

   sampling stable matchings uniformly, and

3. 3.

   finding balanced, median, and sex-equal stable matchings.

This talk presents recent advances in parameterized algorithmics for matching markets. We discuss parameterized complexity results for hard problems that emerge from the classical stable matching framework when incorporating constraints such as fairness or diversity, as well as from extensions that address aspects of control, dynamic or multidimensional settings.

Many optimization problems regarding stable matchings are NP-hard to approximate and their decision variants remain parameterized intractable. Recently, Chen, Roy, and Simola [1] initiated the study of parameterized approximation on three NP-hard stable matching variants:

1. 1.

   Min-BP-SMI: Given a stable marriage instance and a number $k$, find a size-at-least-$k$ matching that minimizes the number $b$ of blocking pairs;

2. 2.

   Min-BP-SRI: Given a stable roommates instance, find a matching that minimizes the number $b$ of blocking pairs;

3. 3.

   Max Size-SMTI: Given a stable marriage instance with preferences containing ties, find a maximum-size stable matching.

In this working group, we aim to advance the research on parameterized approximation of further stable matching problems such as Min Egalitarian SRI which aims for finding a stable matching with minimum egalitarian cost and Incremental SR which aims for finding a stable matching that is closest to a given one.

We mainly focus on Min Egalitarian SRI parameterized by the maximum preference list length $d$. For instance, we obtain that the problem remains NP-hard to approximate even if $d=3$. This excludes parameterized approximation algorithms with respect to $d$.

In the classic hospital-residents problem with capacities a set of doctors should be assigned to a set of hospitals such that no hospital $h$ should still have space for a doctor $d$ that would prefer to be assigned to $h$ than whichever hospital (if any) that $d$ is assigned to or be able to make space for $d$ by removing a doctor assigned to $h$ which is less preferred by $h$ than $d$. To model more detailed constraints on which “diverse” kinds of doctors a hospital needs to be assigned, e.g. a hospital needs between 5 and 8 heart surgeons or should hire at least a tenth of its doctors locally, the problem was more recently generalized to include upper and lower quotas over so called types which are possibly overlapping attributes of doctors. In many situations, it is reasonable to assume that these quotas are given as absolute values but sometimes, e.g. when affirmative action is supposed to be imposed, it is more natural to formulate these quotas proportionally to the number of doctors that each hospital is actually assigned. The former generalization has already been studied in detail from a complexity theoretic and parameterized complexity theoretic angle but with proportional quotas we have no understanding of the problem’s complexity.

In this working group we first established the general hardness of the problem, even in very restricted settings. Specifically, we can show hardness, even if there are only two completely disjoint types which are not hospital-specific and all hospitals only have only constant capacity and no upper quotas on the types. Future work will target the more specific questions such as the impact of the number of hospitals on the problems complexity and a more precise understanding of the subtle differences in the problems difficulty when considering proportional versus absolute quotas.

Dynamic matching markets are commonly modeled as a set of agents with preferences over each other where these preferences change over time, new agents may arrive or present agents may leave. Such markets have received tremendous attention in terms of their economics. The algorithms and complexity of computing stable matchings in dynamic matching markets have also been studied extensively in the temporal setting (where all of the changes are known in advance) or the online setting (where none of the changes are known). However, the algorithmic dynamic setting has, to our knowledge, not been studied: Here the changes arrive one by one and in each step we need to efficiently maintain a stable matching. This working group set out to close that gap.

In our discussions, we were looking for a data structure that has some polynomial-time initialization time for a Stable Marriage instance with a fixed set of $2n$ agents, and supports efficiently a query operation that reports a stable matching for the current set of preferences, and an update operation that receives a change made to the current instance such as a shift of an alternative in a preference list.

In terms of lower bounds we found that, even when we allow only a swaps of two adjacent agents in preference lists, $O(n^{2-ϵ})$ query time and $O(n^{1-ϵ})$ update time for some $ϵ>0$ would contradict the so-called online matrix-vector multiplication conjecture and seems therefore unlikely.

In terms of upper bounds, it seems challenging to improve on the trivial $O(n^2)$ query-time upper-bound. We could achieve $O(n)$ query time and almost linear update time for the case where all the agents of one side have the same preference list. But in the more general setting where all agents’ preference lists follow an order over all pairs of agents we could achieve $O(n)$ query time only with quadratic updates so far. Hence, next in particular we want to look into stronger lower bounds that show superlinear required update time for subquadratic query time.

Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In [1] we aimed to identify structural properties of instances of stable matching problems which will allow us to design efficient algorithms using elementary techniques. We focused on the setting in which all agents involved in some matching problem can be partitioned into $k$ different types, where the type of an agent determines their preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation would arise in practice if agents form preferences solely based on some small collection of agents’ attributes. We also considered a generalisation in which each agent may consider some small collection of other agents to be exceptional, and rank these in a way that is not consistent with their types; this could happen in practice if agents have prior contact with a small number of candidates. We showed that (for the case without exceptions), several well-studied NP-hard stable matching problems including Max SMTI (that of finding the maximum cardinality stable matching in an instance of stable marriage with ties and incomplete lists) belong to the parameterised complexity class FPT when parameterised by the number of different types of agents needed to describe the instance. For Max SMTI this tractability result can be extended to the setting in which each agent promotes at most one “exceptional” candidate to the top of their list (when preferences within types are not refined), but the problem remains NP-hard if preference lists can contain two or more exceptions and the exceptional candidates can be placed anywhere in the preference lists, even if the number of types is bounded by a constant.

In this working group we explored open problems involving exceptional candidates, such as the case when the exceptional candidate can be moved to the bottom of the preference list, and the case where the exceptional candidate can be moved to the top or bottom of their respective type. Other avenues, such as considering other relaxation on types, inspired by real life instances, were briefly considered but not explored given the limited time available.

Given a stable roommates instance, we define the range of the range of an agent $a$ to be the difference between $a$’s maximum and minimum rank in all other agents’ preference lists. The range of the instance is the maximum range of any agent in the instances. We consider parameterized algorithms for stable matching problems parameterized by the range of the instance.

We showed that the following problems are FPT with respect to range:

• $\mathrm{■}$

  Counting stable matchings

• $\mathrm{■}$

  Sampling stable matchings uniformly

• $\mathrm{■}$

  Finding Optimal stable matchings

• $\mathrm{■}$

  Nearly stable matchings.

We have not yet determined if the following problems admit FPT algorithms:

• $\mathrm{■}$

  Finding egalitarian stable matchings

• $\mathrm{■}$

  Finding a matching that minimizes the number of blocking pairs.