Popular and Dominant Matchings with Uncertain and Multimodal Preferences

1 Introduction

Matching markets form a key area in computer science, economics and mathematics literature because of their demonstrated usefulness in many practical and theoretical applications, as well as their rich and beautiful structure. The intensive study of the area started after the seminal paper of Gale and Shapley [1962]. They introduced the famous stable marriage problem and provided a simple algorithm that always finds a stable matching. Intuitively, stability means that no two agents mutually prefer each other to their assigned partners. Stability turned out to be an essential property of matchings in many real-world scenarios such as resident allocation to hospitals (HR), student allocation to A problem with stable matchings is that their size may not be as large as some applications require. For example, in school choice it is important that all students are assigned to some school. In fact, a stable matching may only be half the size of a maximum matching.To overcome this issue, a relaxation of stability, called popularity was introduced by Gardenfors [1975]. Roughly saying, a matching is popular if it does not lose a head-to-head comparison to any other matching. He showed that stable matchings are popular, implying that such matchings also always exist. Furthermore, their size may even be two times the size of stable matchings. While with stable matchings we wish to avoid local blocking structures, with popular matching the goal is only a global form of stability (or fairness).

In recent matching market literature, popular matchings became a central area, partly because of their beautiful connection to stable matchings (see e.g. [Kavitha, 2014]). For a survey about popular matchings, see [Cseh et al., 2017].

In some cases, the participating agents in a matching market may have unknown or partially known preferences to the central authority, or even the agents themselves might not be sure about their own preferences, i.e. they are uncertain. Alternatively, agents may rank their possible partners differently according to different criteria, which gives rise to multilayer preference profiles, one for each such criteria. These kinds of problem have only recently come into attention in the related literature. In such problems, we want to compute stable or popular matchings, that are certainly stable or popular based on the information that we know about the preferences of the agents. Such problems have been studied for stable matchings ([Aziz et al., 2016; Chen et al., 2018]) and Pareto-optimal matchings ([Aziz et al., 2019]). However, so far there has been no work on similar questions for popular matchings. In our paper, we consider the corresponding questions for popularity that have been studied for stability and Pareto-optimality in the literature and provide a comprehensive overview of their complexity.

1.1 RelatedWork

Popularity was introduced in [G¨ardenfors, 1975] for twosided matching markets. He showed that every stable matching is popular.

Abraham et al. [2007] introduced popularity for the onesided preference model, also referred to as the House Allocation (HA) model. They provided an algorithm for finding a maximum size popular matching in the model.

Since popular matchings are easy to find, interest shifted to finding maximum size popular matchings in two-sided markets too. Huang and Kavitha [2013] proved that even maximum size popular matchings can be found in polynomial time. Furthermore, in [Cseh and Kavitha, 2018] it was shown that a nonempty subset of maximum size popular matchings, called dominant matchings of an instance I are in correspondence with the stable matchings of another instance I ′ .

Models where the preferences of agents can vary or may be uncertain have been studied in many papers in the recent literature.

Uncertain preferences have been studied by many papers (e.g. [Aziz et al., 2016; Aziz et al., 2019]). In [Aziz et al., 2016] they studied both a Lottery model, where there was a probability distribution for each different agent over some possible preferences, and a Joint Probability model, where the probability distribution was only over certain preference profiles. In both frameworks, they studied when can we find a matching that is stable with probability one (that is, stable in all possible preferences). In [Aziz et al., 2019], they studied similar questions for one-sided preferences and Pareto optimality as a condition instead of stability. Our work is very similar to these, as we consider many of the same problems for one-sided and two-sided popularity as they considered for Pareto-optimality and stability.

Miyazaki and Okamoto [2017] studied the jointly stable matching problem, where the goal is to find stable matchings across multiple instances with the same agents and contracts, but different preferences, which is equivalent to finding a matching that is stable with probability 1, if each possible preference profile has some positive probability. They strengthened the result of [Aziz et al., 2016] and showed that it is NP-hard even for two preference profiles.

Multilayer preferences in bipartite matching markets have been studied in [Chen et al., 2018]. They defined α-global and α-pair stability. The former means that we aim to find a matching that is stable in at least α layers, and the latter means that each edge can block in at most α layers. The bipartite graph of the instances in each layer is the same; hence, if α is the number of layers, then α-global stability becomes equivalent to deciding whether there is a stable matching across multiple preference profiles. They proved that deciding whether an α-global or α-pair stable matching exists is NP-hard even with strict preferences. Bentert et al. [2023] studied some similar questions for multilayer preferences, where in each layer the preferences of the agents are approval based, i.e. their preference list is a single tie over some acceptable partners.

Chen et al. [2021] studied a notion of d-globally-robust stability. This means that the agents may change the position of an other agent in their preference list, by moving them up or down so that the number of such swaps in the preference profile are at most d. They have shown that finding a d-globally-robust stable matching can be done in polynomial time. They posed the open question of whether finding a drobust stable matching, where each agent is allowed to make d swaps in their preference lists independently, is solvable in polynomial time. We answer this question positively.

Steindl and Zehavi ([2021; 2022]) studied multilayer preferences in the one-sided model. They also considered similar problems, e.g. problems where we aim to find matchings that satisfy many properties like Pareto-optimality in multiple layers.

1.2 Our Results

We consider an Uncertainty, a Multilayer and a Robustpopularity model for popular and dominant matchings.

In the Uncertainty model, each agent has a set of possible preference lists, and the goal is to find a matching that is popular for any possible choices of the preferences, which we call certainly popular. We show that deciding if there is such a matching is NP-hard with two-sided preferences, even if the preference lists on one side of the instance are fixed. If the preferences are one-sided, we show that the problem becomes solvable, and we give an algorithm that finds a certainly popular matching as well as a nice characterization of all certainly popular matchings.

In the Multilayer model, there are a set of layers of preference profiles and we aim to find matchings that are popular in all the layers, which again we call certainly popular matchings. We show that in the two-sided preference model, this is also NP-hard. On the positive side, we give an algorithm that finds a certainly popular matching in one-sided instances.

In the Robust popularity model, we know a preference list for each agent, but these may differ from their original preferences by at most k swaps, where a swap is just the switching of the order of two adjacent agents in a preference list. We show that finding a k-robust popular matching in such a model is NP-hard with two-sided preferences, but is solvable with one-sided ones.

Regarding dominant matchings, we show that in the Uncertainty model and the Robust popularity model, we can find a certainly (resp. k-robust) dominant matching in polynomial time, by utilizing the connection between stable and dominant matchings. For the Multilayer model, we show that the problem becomes NP-hard, even in restricted settings.

The results for the two-sided market are discussed in Section 3, while the one-sided market is considered in Section 4. Our results are summarized in Table 1.

2 Preliminaries

In this section, we describe the basics of two-sided and onesided matching markets and our studied problems.

2.1 Two-sidedMarkets

In two-sided markets, we are given a bipartite graph G = (A,B;E), where the vertices represent the agents and the edges represent the possible contracts or acceptability relations. Furthermore, for each agent u ∈ A∪B, we are given a strict linear order (called a preference list) ≻u over V (u), where V (u) denotes the neighbors of u in G, i.e. the acceptable partners of u. We call the set of these preferences the preference profile of the instance and denote it by L, so L = {≻u| u ∈ A ∪ B}.

We say that M ⊆ E is a matching, if |M(u)| ≤ 1 for all u ∈ A ∪ B, where M(u) ⊆ V (u) denotes the partner(s) of u inM. If u does not have any partners inM, thenM(u) = ∅, which is considered strictly worse than any acceptable partner v ∈ V (u). Depending on the context, we may also refer by M(u) to the edge incident to u inM.

Stability. In two-sided matching markets, the most wellknown optimality concept is stability. Let M be a matching. We say that an edge (a, b) blocks M, if b ≻a M(a) and a ≻b M(b) both hold. We say that M is stable, if no edge blocks M. A well-known result is that a stable matching always exists and can be found in linear time ([Gale and Shapley, 1962]).

Popularity. A relaxation of stability is popularity. To define the popularity of a matching, take two arbitrary matchings M and N. Then, we let each agent u ∈ A ∪ B cast a vote voteLu (M,N) as follows. If M(u) ≻u N(u), then voteLu (M,N) = +1, which means that u prefers M to N, if M(u) = N(u), then voteLu (M,N) = 0 and if N(u) ≻u M(u), then voteLu (M,N) = -1, meaning that u prefers N to M. We sum up these votes to obtain ∆L(M,N) = ∑u∈A∪B voteLu (M, N).

We say that a matching M is popular (with respect to the preference profile L), if for any other matching N we have ∆L(M,N) ≥ 0. In other words, a matching M is popular if it does not lose a head-to-head comparison with any other matching. Otherwise, if ∆L(M, N) < 0, we say that N dominates M.

Dominant matchings. We say that a matching M is dominant, if (i) M is popular and (ii) for any other matching N with |N| > |M| it holds that ∆L(M, N) > 0, or equivalently ∆L(N, M) < 0. Dominant matchings form a nonempty subset of maximum size popular matchings, and can be found in polynomial time ([Cseh and Kavitha, 2018]). The motivation behind this definition is the following. A matching, where the same number of people are getting better and worse, but more people get matched may still be a more desirable solution and hence it would "dominate" the original matching in a weaker but still practical sense.

We will denote the problem of deciding whether an instance I of a two-sided matching market admits a popular matching by PM.

We study three different models. We start with describing the Multilayer model, where we assume that we are given multiple instances of PM, I1, I2, . . . , Ik, with the same underlying bipartite graph, but with different preference profiles L1,L2, . . . ,Lk. Our goal is to decide whether there is a matching that is popular in all preference profiles (so ∆Li (M, N) ≥ 0 ∀i ∈ [k] for all matchings N). We call such a matching a certainly popular matching. This model corresponds to the Multilayer preference model in [Chen et al., 2018], defined for stability instead of popularity with layers L1,L2, . . . ,Lk, hence we call it POPULAR-MULTILAYER. It also corresponds to finding a certainly stable matching in the joint probability model in [Aziz et al., 2016].

POPULAR-MULTILAYER

In: A number k, a bipartite graph G = (A,B;E), and preference profiles Li = {≻iu | u ∈ A ∪ B} for i ∈ [k].

Q: Is there a matchingM that is certainly popular?

The problem DOMINANT-MULTILAYER is defined analogously, but instead of a certainly popular matching, we are looking for a certainly dominant matching, that is, a matching that is dominant in all of the preference profiles.

We proceed by defining the Uncertaintly model. Instead of one bipartite graph with multiple preference profiles, now we assume that for each agent u, there is a set of possible preference lists Pu = {≻1u , . . . , ≻ku u }. This can be interpreted as each agent having preferences uncertain/unknown to us, such that we know some information about them, but not everything. In this model, our objective is to find a matching that is popular for any preference profile L ⊆ ×u∈A∪BPu, that is, for any choices ≻u∈ Pu for the individual preferences of each agent u. We call such a matching a certainly popular matching. This corresponds to the lottery model in [Aziz et al., 2016] for stability.

POPULAR-UNCERTAIN

In: A number k and a bipartite graph G = (A,B;E), with a set of preference lists Pu for each u ∈ A ∪ B with |Pu| ≤ k.

Q: Is there a matchingM that is certainly popular?

The problem DOMINANT-UNCERTAIN is defined analogously.

The next model is the Robust popularity model. Let k ≥ 1. Here, we have a fixed ≻u preference list for each u ∈ A ∪ B and we know that agent u's real preference list differs from ≻u by at most k-swaps, where a swap is the switching if the order of two adjacent entries in the preference lists. For example, a2 ≻ a3 ≻ a1 can be obtained from a1 ≻ a2 ≻ a3, with two consecutive swaps (a1, a2) and (a1, a3). We say that agent v is k-better (k-worse) than v′ for u, if the number of swaps required to make v worse (better) than v′ is k, respectively. We say that v is at least k-better (worse) than v′ , if the number of swaps required to make v worse (better) than v′ is at least k. For two preference lists ≻1u ,≻2u , we let ds (≻1u , ≻2u ) be the minimum number of swaps required to reach ≻2u from ≻1u . We say that a matching M is k-robust popular, if M is popular in any preference profile L = {≻Lu | u ∈ A ∪ B}, where ds (≻u, ≻Lu ) ≤ k for all u ∈ A ∪ B.

POPULAR-ROBUST

In: A number k and a bipartite graph G = (A,B;E) with preference lists ≻u, u ∈ A ∪ B.

Q: Is there a matchingM that is k-robust popular?

We obtain the problem DOMINANT-ROBUST similarly, where we are looking for a k-robust dominant matching instead, that is, a matching which is dominant even if each agent may do at most k swaps in his preference list.

2.2 One-sidedMarkets

One-sided markets, or (capacitated) House Allocation (HA) markets as often called in the literature, are similar to twosided markets. Here, also, we are given a bipartite graph G = (A,B;E). However, now only the agents a ∈ A have preference lists ≻a over their acceptable houses V (a) ⊆ B, so L = {≻a| a ∈ A}. We also allow the agents in B -who we call houses from now on- to have a positive integer capacity q[b].

In this model, we say that M ⊆ E is a matching, if it holds that |M(a)| ≤ 1 for any agents a ∈ A and |M(b)| ≤ q[b] for any house b ∈ B, where M(a) and M(b) denote the house(s) allocated to a and the agent(s) allocated to b in M, respectively. If |M(b)| = q[b], then we say that b is filled (or saturated).

Popularity for the HA model is defined analogously, with the only difference being that only the agents in A participate in the voting procedure, so ∆L(M,N) is defined as ∑a∈A voteLa (M, N). We say that a matching M is popular, if ∆L(M, N) ≥ 0 for any matching N.

In the HA model, popular matchings may fail to exists, but it is possible to find a maximum size popular matching in polynomial time, if one exists [Abraham et al., 2007].

The corresponding variants of POPULAR-MULTILAYER, POPULAR-UNCERTAIN and POPULAR-ROBUST for the onesided case are called HA-POPULAR-MULTILAYER, HAPOPULAR-UNCERTAIN and HA-POPULAR-ROBUST, respectively. Their definition is analogous to the two-sided case; hence the precise definitions of these problems are deferred to the Appendix.

3 Two-sidedMarkets

In this section, we investigate the questions discussed for twosided markets.

3.1 Verification

First of all, we show that deciding if a matching M is certainly popular or k-robust popular can be done in polynomial time, hence the problems are in NP.

Theorem 1. Verifying if a matching M is certainly popular (resp. dominant) or k-robust-popular (resp. dominant) can be done in polynomial time in all of POPULARMULTILAYER, DOMINANT-MULTILAYER, POPULARUNCERTAIN, DOMINANT-UNCERTAIN, POPULAR-ROBUST and DOMINANT-ROBUST.

Proof. The case of POPULAR-MULTILAYER and DOMINANT-MULTILAYER is trivial, because we only need to verify that M is popular (resp. dominant) in polynomially many preference profiles in the input size, and verifying whether a matching is popular or dominant can be done in polynomial time ([Huang and Kavitha, 2013; Cseh and Kavitha, 2018]).

We may assume without loss of generality that |A| = |B|. Otherwise, we can add isolated agents to the instance, whose vote will always be 0 when comparing any two matchings and the other agents' votes are unaffected.

Let I be an instance of POPULAR-UNCERTAIN or POPULAR-ROBUST with G = (A, B, E) and let L denote the set of possible preference profiles (in the case of POPULARROBUST, these are the profiles, where each preference list differs from the original by at most k swaps). Let M be a matching. First, we extend G to be a complete bipartite graph by adding all missing edges. Call this new graph H. Then, we create a weight function w : E(H) → Z as follows. For each e = (a, b) ∈ E(G), we let w(e) = vote∗a (M, e) + vote∗b (M, e). Furthermore, vote∗a (M, e) is defined to be -1, if there is a possible preference list, where a prefers his partner in e, 0 if M(a) = e and +1, if a always prefers his partner in M (so in the k-robust case, this corresponds to that partner being at least (k + 1)-better). For an edge e = (a, b) /∈ E(G), we let w(e) = vote∗a (M, ∅) + vote∗b (M, ∅) (here, vote∗a (M, ∅) = +1, except the case when M(a) = ∅, when it is 0).

We claim that M is popular in all possible preference profiles if and only the minimum weight perfect matching in H has weight at least 0. Indeed, for any perfect matching N ′ of H, if we let N = N ′ ∩ E(G), then w(N ′ ) is exactly minL∈L∆L(M,N) by the definition of the weights and the fact that since N ′ is perfect, we count the smallest possible vote (i.e. it is -1, whenever it can be -1 in a possible preference list) for every agent in A ∪ B exactly once. Also, for any maximal matching N ⊆ E(G), we can extend it to a perfect matching N ′ greedily (H is complete and |A| = |B|), using edges from E(H) \ E(G) such that w(N ′ ) is minL∈L∆L(M,N). Hence, M is popular if and only if there is no perfect matching N ′ ⊆ E(H) such that w(N ′ ) < 0. This can be verified in polynomial time with various methods, e.g. Egerv´ary's algorithm or Linear Programming.

For the case of DOMINANT-UNCERTAIN and DOMINANTROBUST, we can decide similarly if M is certainly popular or k-robust popular and if not, we can conclude that it is not certainly dominant or k-robust dominant, respectively. Therefore, we may assume that M is popular in any possible preference profile. To decide whether there is a larger matching N, such that ∆L(M,N) = 0 in a possible preference profile L, we subtract ε = 1 |M|+1 from each original edge's

(e ∈ E(G)) weight and check whether there is a perfect matching with weight at most -1. If there is a perfect matching N ′ of weight at most -1, then for N = N ′ ∩ E(G), we have that |N| ≥ |M|+1, asM is popular. Also, |N| ≤ 2|M|, because any popular matching is maximal. Therefore, the weight of N ′ cannot be at least 1 with respect to the original weights (so without subtracting the ε values), so it is exactly 0. Therefore, N is larger than M, but ∆L(M,N) = 0 in a possible preference profile L, as w(N ′ ) = 0, so M is not certainly dominant or k-robust dominant, respectively. In the other direction, if M is not dominant in all possible preference profiles, then there is a matching N with |N| ≥ |M|+1 and ∆L(M, N) = 0 in a possible preference profile L, so N can be extended to a perfect matching N ′ with weight at most -1.

3.2 Dominant Matchings

We proceed to our results about dominant matchings in twosided markets. Our first result is the hardness of DOMINANTMULTILAYER. The proof is deferred to the Appendix.

Theorem2. DOMINANT-MULTILAYER is NP-complete, even for a fixed constant k = 2.

Before the other results, we describe a useful reduction that connects dominant and stable matchings. Let I = (G,L), G = (A,B,E) be an instance of PM. We create an instance I ′ , by adding two parallel edges x(e), y(e) for each edge e ∈ E. Then, we create the preference profile in I ′ (over the edges now, as we have parallel edges in the new instance) from L, by the following rule. For each agent a ∈ A, we first rank all the edges of type x incident to it, in the same order as a's preference over his neighbors, then we rank all incident edges of type y, again in the order of a's preference list. So, if a had preference list b1 ≻ b2, then it becomes x((a, b1)) ≻ x((a, b2)) ≻ y((a, b1)) ≻ y((a, b2)). For the agents b ∈ B, we do it similarly, by interchanging the order of the x and y types. The following theorem connects the dominant matchings in I with the stable matchings in I ′ .

Theorem3 ([Kavitha, 2014], [Kamiyama, 2020]). Every stable matching M ′ in I ′ gives a dominant matching M = f(M ′ ) in I, where f(M ′ ) = {e | |M ′ ∩ {x(e), y(e)}| ≥ 1}. Furthermore, for every dominant matching M in I, there is a matchingM ′ in I ′ such that M = f(M ′ ).

The only problem with Theorem 3 is that for a dominant matching M, the stable matching M ′ with f(M ′ ) = M also depends on the preference profile in I. Hence, finding a certainly dominant matching does not reduce trivially to finding a certainly stable matching, as for a certainly dominant matching, its preimage in I ′ may be different for each preference profile, so there may not be a certainly stable matching in I ′ that gives M.

We use this connection to the stable matching problem to solve DOMINANT-UNCERTAIN and DOMINANT-ROBUST. First, we show that DOMINANT-ROBUST reduces in polynomial time to DOMINANT-UNCERTAIN.

Let I be an instance of DOMINANT-ROBUST. We create an instance I ′ of DOMINANT-UNCERTAIN with the same underlying bipartite graph. Then, we create the set of preference lists for each agent. Let Pu = {≻vu | v ∈ V (u)}, where ≻vu is the preference list obtained from ≻u by swapping v down k times in the preference list (a swap down of the worst entry in the preference list is just considered as doing nothing). For example, if ≻u= v1 ≻ v2 ≻ v3 ≻ v4 and k = 2, then ≻v1 u is v2 ≻ v3 ≻ v1 ≻ v4.

Clearly, for a fixed matchingM, it is k-robust dominant in DOMINANT-ROBUST if and only if it is dominant even if every agent swaps down his partner in M (if there is any) by k places. Also, for each agent u and each possible partner v of u, we have created a preference list ≻vu , where any agent that can be better than v with at most k swaps is better than v at the same time. Hence, min≻′u |d(≻u,≻′u )≤k{vote≻′u (M,N)} = minv∈V (u){vote≻vu (M,N)} holds for each u ∈ A ∪ B and matchings M, N, so a matching M is certainly dominant in I if and only if it is certainly dominant in I ′ .

Remark 1. We note that with the same idea, we get that we can reduce the problem of finding a k-robust stable matching, that is, a matching which remains stable even if each agent can apply k swaps in his preference list, to finding a certainly stable matching in polynomial time. As the latter problem can be solved in polynomial time (see [Aziz et al., 2016]), we get that this problem also admits a polynomial algorithm, answering an open question of [Chen et al., 2021].

We are ready for our next result.

Theorem 4. DOMINANT-UNCERTAIN and DOMINANTROBUST can be solved in polynomial time.

Proof. We have seen that it is enough to give an algorithm for DOMINANT-UNCERTAIN.

Let I be an instance of DOMINANT-UNCERTAIN. We create an instance I ′ of STABLE-UNCERTAIN, where for each edge e, we create two parallel edges x(e) and y(e) as in Theorem 3, and for each agent u, his possible preference lists are created from his original preference lists ≻iu , such that if u ∈ A, then we first rank the x type edges according to ≻iu and then the y type edges in the same order, and if u ∈ B, then we rank the y types first and the x types last.

By Theorem 3, we see that if there is a certainly stable matching in I ′ , then that gives us a certainly dominant matching M in I. Therefore, our goal is to show that if there is a certainly dominant matching M in I, then there is a certainly stable matching M ′ in I ′ . For this, let M be certainly dominant. We first create a strict preference list ≻′u for each u ∈ A ∪ B in I, such that for any v ∈ V (u), if v ≻iu M(u) for a possible preference list ≻iu of u, then v ≻′u M(u), and if M(u) ≻iu v for all possible preference lists, then M(u) ≻′u v. Otherwise, the preferences between agents that are both better or both worse than M(u) are created arbitrarily. As M is certainly dominant, it is also dominant with the preferences ≻′u , u ∈ A ∪ B, because mini∈k{vote≻iu (M, N)} = vote≻′u (M, N) for any matching N.

By Theorem 3, this matching M gives a stable matching M ′ in I ′ with respect to the extensions of the ≻′u preferences, which we also denote ≻′u by abuse of notation. We claim that it is certainly stable. Suppose that an edge x(a, b) blocks M ′ with the extension of some preference lists of a and b. Then, if a is not matched by an x type edge, then a prefers this edge in the extension of ≻′a too. Also, b must be unmatched or matched with an x-type edge (x(a, b) cannot dominate y type edges for b) and in the latter case, there must be a preference list ≻ib , such that a ≻ib M(b). However, then we have that x(a, b) ≻′b M ′ (b), which contradicts that M ′ is stable with these preferences. If a is matched with an x-type edge, then the fact that x(a, b) blocks implies that b ≻ia M(a) for some i and so x(a, b) ≻′a M ′ (a). Similarly as before, we get that x(a, b) ≻′b M ′ (b) also holds and therefore M ′ is not stable, a contradiction. The case for edges of type y is analogous.

Hence, we conclude that M ′ is certainly stable, and therefore the theorem follows from the fact that a certainly stable matching can be found in polynomial time ([Aziz et al., 2016]).

3.3 Popular Matchings

We conclude the section with our results for popular matchings. Due to space constraints, their proofs are deferred to the Appendix.

Theorem 5. POPULAR-MULTILAYER and POPULARUNCERTAIN are NP-complete, even if uncertainty occurs only on one side and k = 2 is a fixed constant.

Theorem 6. POPULAR-ROBUST is NP-complete, even for a fixed constant k = 1.

4 One-sidedMarkets

In this section, we discuss our results for the HA model.

First, we describe a characterization of popular matchings in HA instances from [Manlove and Sng, 2006]. Let (G, q,L) be an instance with preference profile L. We can add a "last-resort" house ˆb to B with capacity |A| that is appended to the end of each applicant's preference list. Then, the set of popular matchings in this new instance are in oneto-one correspondence with the original ones: we just say that each unmatched agent a is now at an imaginary worst house, the "last-resort". Hence, from now on we may assume that each instance of HA-POPULAR-MULTILAYER and HAPOPULAR-UNCERTAIN contains such a house. Very importantly though, the new inputs are always such that this house must always be last for every agent in all possible preference lists or preference profiles in the input. This is without loss of generality, since this house did not exist originally.

Next, for each applicant a ∈ A, define the first house fL(a) to be the house that is the most preferred by a. For a house b, we call an agent a an admirer of b in L, if b = fL(a). Denote the set of admirers of b by ADL(b). Next, we define the pseudo-second house sL(a) to be either fL(a), whenever b = fL(a) has at most as many admirers as its capacity q[b], or otherwise as the house most preferred by a among the houses that have strictly less admirers than their capacity. Note that because of the last resort house, sL(a) exists.

Make a graph GL = (A,B,EL) by adding the edges (a, fL(a)) and (a, sL(a)) for each applicant a ∈ A. In the case where fL(a) = sL(a) we only add one of the parallel edges.

Theorem 7 ([Manlove and Sng, 2006]). A matching M is popular if and only if the following conditions hold:

• Every edge of M is from EL,
• M is A-perfect, so it matches every a ∈ A and
• every house b ∈ B that can be filled with admirers of b only is filled with admirers of b only.

4.1 Multilayer and UncertaintyModels

Let us consider an instance I of HA-POPULAR-MULTILAYER or HA-POPULAR-UNCERTAIN.

For a house b, let CA(b) denote the set of certain admirers of b, that is, the agents a ∈ A that consider b first in any possible preference profile/preference list. Let PA(b) denote the set of possible admirers of b, that is, the agents a ∈ A that consider b best in some possible preference profiles/preference lists. Finally, let Ha(b) be the set of houses that are better than b in some possible preference lists of a. All these sets can be easily computed in polynomial time in both the HA-POPULAR-MULTILAYER and the HAPOPULAR-UNCERTAIN problems.

Using Theorem 7 we get the following result.

Theorem 8. Let G = (A,B;E) be a bipartite graph, with q[b] capacities for each b ∈ B. Let L = {L1,L2, . . . ,Lk} be a set of preference profiles for A. Then, a matching M is popular in any L ∈ L if and only if

• M is an A-perfect matching in the graph ˆG = (A,B, ˆE), where ˆE = ∩ni=1ELi and
• for any L ∈ L, any house b for which |ADL(b)| ≥ q[b] is filled by agents from ADL(b).

For the uncertainty model, we prove a different characterization in the appendix that we are going to utilize.

Theorem 9. Let G = (A,B;E) be a bipartite graph with q[b] capacities for each b ∈ B. Let Pa1 , . . . , Pan be the sets of preference lists for ai ∈ A. Then, a matching M is popular in any L ∈ ×ni=1Pai if and only if

• M is an A-perfect matching in the graph ˆG = (A,B, ˆE), where ˆE = ∩ni=1ELi ,
• any house b that has at least q[b] possible admirers is filled with possible admirers,
• any house b that has at least q[b] certain admirers is filled with certain admirers,
• for each agent a and each possible pseudo-second house b of a, if (a, b) ∈ M, then each b′ ∈ Ha(b) is filled with certain admirers.

Using Theorems 8 and 9, we show that HA-POPULARMULTILAYER and HA-POPULAR-UNCERTAIN are polynomial-time solvable. It also follows that the verification problems are solvable too in both cases.

Theorem 10. HA-POPULAR-MULTILAYER and HAPOPULAR-UNCERTAIN are solvable in polynomial time.

Proof. Let I be an instance of either HA-POPULARMULTILAYER or HA-POPULAR-UNCERTAIN. Let L denote the set of possible preference profiles, which in the case of HA-POPULAR-UNCERTAIN is L = ×a∈APa, which can have exponentially many profiles in the input size, whereas in the case of HA-POPULAR-MULTILAYER only polynomially many (since each of them is part of the input).

Let us start with the case of HA-POPULAR-MULTILAYER. By Theorem 8, it is enough to decide whether ˆG = (A,B, ˆE), ˆE = ∩L∈LEL admits an A-perfect matching or not, satisfying that for any L ∈ L, any house b for which |ADL(b)| ≥ q[b] is filled by agents from ADL(b). We can compute ADL(b) for each (b,L) ∈ B × L in polynomial time, and we can also compute the graph ˆG in polynomial time. Now, for each edge (a, b) ∈ ˆE, we check whether there is a preference profile L, such that |ADL(b)| ≥ q[b], but a /∈ ADL(b), and if so, then we delete the edge (a, b). If there remains an A-perfect matching M in the graph, then it clearly satisfies the first condition and also the second, as otherwise if (a, b) ∈ M, but a is not an admirer of b in L and |ADL(b)| ≥ q[b], then the edge (a, b) has been deleted, contradiction. For the other direction, if there is no A-perfect matching remaining, then there can be no matching that is popular in every L ∈ L, because such a matching would be A-perfect and none of its edges would have been deleted.

Next, consider the case of HA-POPULAR-UNCERTAIN. We start by computing the sets CA(b), PA(b) for each house b ∈ B and the sets Ha(b) for each edge (a, b) ∈ E.

First, we show that we can decide whether e ∈ ˆE or not, so we can construct ˆG in polynomial time.

By Theorem 7, an edge e = (a, b) is included in ˆG if and only if b ∈ {sL(a), fL(a)} for each possible preference profile L ∈ L. If b is first in all of a's possible preference lists, then (a, b) ∈ ˆE clearly. If not, then (a, b) ∈ ˆE, if and only if for each preference list ≻ia , where b is not first, each house b′ ≻ia b for a must have at least q[b′ ] many admirers in any possible preference profile containing ≻ia . This means that |CA(b′ )| ≥ q[b′ ]. Using the sets CA(b), we can check for a given a ∈ A and b ∈ B, whether the conditions for (a, b) ∈ ˆE hold for each ≻ia∈ Pa preference list of a and, therefore, we can construct ˆG in polynomial time.

Then, by point two of Theorem 9, we know that the edges (a, b) such that |PA(b)| ≥ q[b], but a /∈ PA(b) cannot be included in any matching that is certainly popular, so we can safely delete them from ˆG. Similarly, we can delete the edges (a, b), such that |CA(b)| ≥ q[b], but a /∈ CA(b) by point three of Theorem 9.

Finally, for each agent a ∈ A, and each remaining (a, b) edge, if b is not a first house of a in some preference list, then we check whether for each b′ ∈ Ha(b), |CA(b′ )| ≥ q[b′ ], which can be done in polynomial time. If not, then b′ cannot be filled with certain admirers and hence a cannot be at b in a certainly popular matching by Theorem 9 point four, so we can delete (a, b) from the graph. Otherwise, for each such b′ , we already deleted each edge (a′ , b′ ) when a′ /∈ CA(b′ ), so whenever a matching in the remaining graph fills b′ , it must fill it with certain admirers.

Therefore, we conclude that there is a certainly popular matching if and only if the remaining graph has a matching that is (i) A-perfect and (ii) fills every b ∈ B such that |PA(b)| ≥ q[b] by Theorem 9. Such a matching, if exists, can be found efficiently with, for example, the Hungarianmethod.

Our results regarding the Robust popularity model are deferred to the appendix.

5 Conclusions and Open Questions

In this paper, we considered models where agents' preferences may vary or may be uncertain for popular matching problems both in one-sided and two-sided preferences. We gave a comprehensive overview of the complexity of our studied problems.

For future work, it may be interesting to consider similar questions for other well-known notions. We also left open the complexity of DOMINANT-MULTILAYER and POPULARROBUST if only one side has uncertain preferences.

Acknowledgements

Gergely Cs´aji acknowledges the financial support by the Hungarian Academy of Sciences, Momentum Grant No. LP20211/2021, by the Hungarian Scientific Research Fund, OTKA, Grant No. K143858 and by the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation fund, financed under the KDP-2023 funding scheme (grant number C2258525).