# fractional_matchings_under_preferences_stability_and_optimality__0dbf7f87.pdf

Fractional Matchings under Preferences: Stability and Optimality

Jiehua Chen , Sanjukta Roy and Manuel Sorge TU Wien, Austria {jiehua.chen, sanjukta.roy, manuel.sorge}@tuwien.ac.at

We study generalizations of stable matching in which agents may be matched fractionally; this models time-sharing assignments. We focus on the so-called ordinal stability and cardinal stability, and investigate the computational complexity of ﬁnding an ordinally stable or cardinally stable fractional matching which either maximizes the social welfare (i.e., the overall utilities of the agents) or the number of fully matched agents (i.e., agents whose matching values sum up to one). We complete the complexity classiﬁcation of both optimization problems for both ordinal stability and cardinal stability, distinguishing between the marriage (bipartite) and roommates (non-bipartite) cases and the presence or absence of ties in the preferences. In particular, we prove a surprising result that ﬁnding a cardinally stable fractional matching with maximum social welfare is NP-hard even for the marriage case without ties. This answers an open question and exempliﬁes a rare variant of stable marriage that remains hard for preferences without ties. We also complete the picture of the relations of the stability notions and derive structural properties.

1 Introduction

A joy shared is a joy doubled! As we will see, this may hold particularly true in matching markets. Such a market is described by a set of agents who have preferences over whom they want to have as a partner. Traditionally, the goal is to ﬁnd a stable integral matching [Gale and Shapley, 1962], i.e., to match the agents one-to-one such that no two agents prefer to be with each other rather than with their matched partners. Unfortunately, a stable integral matching does not always exist. If however the agents are allowed to share partners, then we will see that a stable matching is guaranteed to exist and the social welfare may increase! That is, we allow fractional matchings which are functions that assign each pair of agents a value between 0 and 1 (as opposed to integral matching which assigns either 0 or 1 to each pair) such that for each agent, the sum of the matching

Contact Author

values of all pairs containing this agent is at most one. In this paper, we study structural properties of stable fractional matchings and computational aspects of maximizing their social welfare and the number of the fully matched agents. Stable fractional matchings have been studied since the 90s [Vande Vate, 1989; Roth et al., 1993; Abeledo and Rothblum, 1994; Teo and Sethuraman, 1998] and enjoy continued interest [Bir o et al., 2008; Kintali et al., 2013; Do gan and Yıldız, 2016; Kesten and Unver, 2015; Ishizuka and Kamiyama, 2018; Aziz and Klaus, 2019; Caragiannis et al., 2020]. They have applications in time-sharing assignments and random assignments: For example, in a job market the agents may be partitioned into two sets, freelancers and companies. A fractional matching models the amount of time a freelancer spends working for a company. The preferences can model intensity of interest in working with the agents of the other set, and then stability models an equilibrium in such a job market. Similar scenarios are time-sharing assignments between advisors and apprentices or between workers and projects. An instance of the non-bipartite case occurs when agents (e.g., nurses) work in multiple shifts, and each shift is carried out by two workers. A fractional matching determines the fraction of shifts that each worker carries out with another worker over the total number of shifts for an agent. The preferences can model the intensity of willingness to work with each other, and then stability models the situation where no two workers want to change shifts to work more with each other. Fractional matchings also ﬁnd application in random matching [Roth et al., 1993; Kesten and Unver, 2015; Aziz and Klaus, 2019]: In the bipartite case, by the Birkhoffvon Neumann theorem, a fractional matching can be interpreted as a probability distribution over integral matchings. Choosing an integral matching at random instead of deterministically enables many desirable properties such as fairness and increased expected welfare [Aziz and Klaus, 2019].

Stability for fractional matchings. While the deﬁnition of stability in the integral case is straightforward, there are several natural ways to deﬁne stability for fractional matchings. We consider the following three stability concepts which have been recently discussed [Aziz and Klaus, 2019; Caragiannis et al., 2020]. The setting is given by a graph G = (V, E), where V is the set of agents, and a preference function sat: V V Q 0, where sat(u, v) speciﬁes the satisfaction of u towards v. A fractional matching M : E [0, 1] is

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

1 3 1 3 2 2 1

2 Decreasing Decreasing Preferences Preferences a: d c b, d: c e a, b: a c, e: d f, c: b a d, f : e.

ab ac ad bc cd de ef other edges M1 0.5 0.5 0 0.5 0 1 0 0 M2 0.5 0 0.5 0.5 0.5 0 1 0

Figure 1: Left: Acceptability graph with 6 agents a, b, c, d, e, f. The values on an edge denote the satisfactions of the endpoints of the edge towards each other, e.g., a s satisfaction towards b is 1 and b s satisfaction towards a is 3. Right: The ordinal preferences derived from the satisfactions. Bottom: Fractional matchings M1 and M2.

cardinally, ordinally, or linearly stable if it does not admit a blocking pair {u, v} E of the corresponding type: A cardinally blocking pair for M models the situation that the agents in the pair both obtain more utility from being integrally matched to each other than from the assignment under M [Caragiannis et al., 2020]. Herein, the utility of an agent v V under M is Usat,M(v) := P {v,u} E(G) sat(v, u) M({v, u}). If sat is clear from the context, we omit it in Usat,M. Thus, pair {u, v} is cardinally blocking M if UM(u) < sat(u, v) and UM(v) < sat(v, u). An ordinally blocking pair concerns ordinal preferences: As the preferences of an agent v we consider only the relative order of the agents u acceptable to v that is induced by sat(v, u), but ignore the magnitude of sat(v, u). An ordinally blocking pair {u, v} for M models the case when u and v both are not satisﬁed with M, i.e., u is matched by a fraction of less than one to agents that she weakly prefers to v and analogously for v [Aharoni and Fleiner, 2003]. For convenience, deﬁne M(x, y) := P y V : sat(x,y ) sat(x,y) M(x, y ). Then, {u, v} is ordinally blocking M if M(u, v) < 1 and M(v, u) < 1. Ordinal stability has also been studied under the name ex-ante weak stability [Kesten and Unver, 2015]. Finally, {u, v} is a linearly blocking pair of M if M(u, v)+M(v, u) M(u, v) < 1. That is, linear stability arises from the linear-programming formulation of computing a stable (integral) matching by relaxing the integrality constraints [Roth et al., 1993; Abeledo and Rothblum, 1994]. We give examples in Figure 1: Matching M1 (green) is cardinally stable, ordinally stable, and linearly stable. Matching M2 (red) is cardinally stable and every agent is fully matched, i.e. each agent s matching values sum up to one. However, M2 is neither ordinally stable nor linearly stable, due to {d, e}. Due to the agents a, b, c, no integral matching is stable. Note that all three stability concepts are the same when restricting to integral matchings. Figure 2 illustrates the relations between all discussed stability concepts.

Our contribution. We ﬁrst show that a stable fractional matching for all three stability concepts always exists, even when ties are present in the preferences and in the roommates case (i.e. G is not necessarily bipartite); this extends previous observations by Caragiannis et al. [2020] and Aharoni and

stable integral

ordinally stable

linearly stable

cardinally stable

Figure 2: Relation between the stability concepts, where α β means that an α matching is also β . No directed path between two concepts means that neither implies the other.

Fleiner [2003] for more restricted cases. Motivated by this positive result, we study the complexity of two optimization problems. We aim to maximize (1) the social welfare of the resulting matching, i.e., the sum of the utilities of the agents obtained from the matching, or (2) the number of fully matched agents. The second objective is a natural generalization of checking for perfect matchings and it is motivated by aims of being inclusive and avoiding unspent resources, for example, the freelancers non-working time in the introductory scenario. For linear stability both optimization problems are polynomial, because they can be formulated as linear programs. For ordinal stability and cardinal stability, together with a previous result [Caragiannis et al., 2020], we obtain a complete complexity classiﬁcation, distinguishing the marriage (bipartite) and roommates (non-bipartite) cases and whether ties are present in the preferences. See the summary in Table 1. For ordinal stability both optimization problems are polynomial in the marriage case without ties. The proof relies on a decomposition of the optimal fractional matching into integral matchings that consequently yields that an optimal integral matching is also optimal for the fractional case. Unfortunately, most of the other cases become NP-hard. We found particularly interesting that maximizing the social welfare remains NP-hard for cardinal stability in the marriage case without ties because it stands in stark contrast to the integral stability and ordinal stability for which the problem is tractable. This result thus reveals that the difﬁculty of computing optimal stable fractional matchings depends not only on ties or the fractionality but also on the cardinalities. NPhardness in the case without ties has been asked as an open question by Caragiannis et al. [2020] and the inﬂuence of ties on the complexity in the integral setting has been extensively studied [Gusﬁeld and Irving, 1989; Manlove, 2013]. Apart from the above complexity results we also study the structure of the (families of) matchings under the three stability notions. We show that the family of ordinally stable matchings form a lattice in the marriage case and that they adhere to the so-called median property in the roommates case. Apart from being interesting insights into the structure of the solution space, these properties are useful because they can enable efﬁcient algorithms that solve additional optimization goals or ﬁnd matchings with additional desirable properties. Omitted results and proofs marked with ( ) are available in a full version [Chen et al., 2020].

Related work. Roth et al. [1993] studied linear stability (they called it fractional stability) in marriage markets without ties, and showed that the set of linearly stable matchings enjoys a lattice structure. Abeledo and Rothblum [1994] studied linear stability, but in roommates markets. They observed that the set of linearly stable matchings in roommates

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

cardinal stability ordinal stability Marriage Roommates Marriage Roommates no ties ties no ties ties no ties ties no ties ties always exists? yes [ ] yes [ ] yes [P 3.5] yes [P 3.5] yes [ ] yes [P 3.5] yes [ ] yes [P 3.5] max-#-fully-matched NP-c [T 5.9] NP-c [T 5.7] NP-c [T 5.9] NP-c [T 5.7] P [P 4.5] NP-c [T 5.1] P [P 4.5] NP-c [T 5.1] max-welfare NP-c [T 5.7] NP-c [ ] NP-c [T 5.7] NP-c [ ] P [T 4.3] NP-c [T 5.1] NP-c [T 5.2] NP-c [T 5.2]

Table 1: New and known results for deciding a cardinally stable (resp. ordinally stable) matching with max. # of fully matched agents (resp. max-welfare). Results marked with and are from Caragiannis et al. (2020) and Aharoni and Fleiner (2003), respectively. Results marked in red and green are new; green means polynomial-time algorithms and red NP-completeness.

markets does not have a lattice structure in general, but are closed under the so-called median operation. Following the authors, we obtain the same results for ordinal stability. Aziz and Klaus [2019] considered multiple fractional stability concepts in marriage markets, including linear stability and ordinal stability (which they called fractional stability and ex-ante stability [Kesten and Unver, 2015]), but not cardinal stability. They showed that ordinal stability implies linear stability. We strengthen their result by showing the same for the roommates case. Caragiannis et al. [2020] introduced the problem of ﬁnding maximum-welfare cardinally stable matchings in marriage markets. They showed that the problem is NP-hard and hard to approximate even if each agent has at most three different satisfaction values but may contain ties in her preferences. We improve on this by showing NP-hardness even when no ties are present and each agent ﬁnds at most ﬁve agents acceptable. A subset of the structural results, namely the ones about cardinal stability in the marriage setting and for perfect matchings (see Observation 3.1) has been observed independently in parallel in their recent journal version [Caragiannis et al., 2020, Appendix A]. Aharoni and Fleiner [2003] studied ordinal stability in the hypergraphic setting. They found that Scarf s lemma from game theory guarantees the existence of ordinally stable matchings. For an overview on stable integral matchings refer to Gusﬁeld and Irving [1989] and Manlove [2013].

2 Preliminaries Given an integer z, we use [z] to denote the set {1, 2, . . . , z}. We consider instances (G, sat) where G = (V, E) is a graph and sat: V V Q 0 is a function, and where V denotes a set of vertices (also called agents), E denotes a set of edges such that an edge between two vertices means that the corresponding agents ﬁnd each other acceptable, and sat speciﬁes the cardinal preferences of an agent towards another agent, i.e., for all u, v V , sat(u, v) speciﬁes the satisfaction of u towards v. We also refer to G as the acceptability graph underlying the cardinal preferences sat. We assume throughout that (1) G contains no isolated vertices, (2) u V : sat(u, u) = 0, and (3) u, v V : {u, v} E (sat(u, v) > 0 or sat(v, u) > 0). From the function sat for G we derive a preference list v over the neighborhood NG(v) = {u | {v, u} E} of each v V as follows: Let v denote a complete and transitive binary relation of NG(v) such that for each two acceptable agents x, y NG(v) it holds that x v y if and only if sat(v, x) sat(v, y); we say that v weakly prefers x

to y. We use x vy to denote that sat(v, x) > sat(v, y), i.e., v (strictly) prefers x to y. We use P = ( v)v V to denote the collection of the preference lists derived from sat. We say that x is a most preferred agent of v if for each acceptable agent y NG(v) we have x v y. We say that an instance (G, sat) has complete preferences if G is a complete graph; otherwise it has incomplete preferences, and that it contains (preferences with) ties if there exists v V and two neighbors x, y NG(v) with sat(v, x) = sat(v, y); otherwise it has strict preferences. A fractional matching M : E R 0 is an assignment of non-negative weights to each edge e E such that P {v,u} E M({u, v}) 1 for each agent v V . If it is not ambiguous we abbreviate fractional matchings to matchings . By symmetry, for each edge {u, v} we use M(u, v) (resp. M(v, u)) to refer to M({u, v}). An agent v is fully matched (resp. matched) under M if P u NG(v) M(v, u) = 1 (resp. P u NG(v) M(v, u) > 0). M is perfect if each agent is fully matched. M is integral (resp. half-integral) if M(e) {0, 1} (resp. M(e) {0, 0.5, 1}) for each edge e. By the Birkhoff-von Neumann theorem a fractional matching in a bipartite graph can be decomposed into a convex combination of integral matchings [Horn and Johnson, 1991, Theorem 3.2.6]:

Proposition 2.1. Let M be a fractional matching of a bipartite graph G with n vertices. There is an integer k O(n2), positive coefﬁcients x1, . . . , xk R>0, and integral matchings M1, . . . , Mk of G such that P j [k] xj = 1 and for each edge e E it holds that M(e) = P j [k] xj Mj(e).

The integral matchings (Mj)j [k] constitute a support of the matching M. There may be multiple supports of M. The acronyms CSM, OSM, and LSM stand for cardinally stable, ordinally stable, and linearly stable fractional matching, respectively (see Section 1 for the deﬁnitions). We focus on two classes of decision problems, one aiming for maximizing the number of fully matched agents, and the other for maximizing social welfare. Let G = (V, E) be a graph, sat: V V Q 0 a satisfaction function, and M a fractional matching in G. Denote #fully(M) := |{x V | P y NG(x) M(x, y) = 1}| and welfaresat(M) := P v V Usat,M(v). If sat is clear from the context then we drop it in welfaresat. The problems are deﬁned as follows, where Π {OSM, CSM}1 :

1We omit linear stability since both problems for linear stability can be formulated as linear programs and are hence solvable in polynomial time.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Algorithm 1: Compute an OSM for (G, sat).

1 Compute the preference lists P from sat

2 ˆ sat Break ties in sat arbitrarily

3 Compute π and M π for (G, ˆ sat) (cf. Def. 3.2)

4 return M π

FULL Π MATCHING (FULL-Π) Input: G = (V, E), sat: V V Q 0, and τ N. Question: Does (G,sat) admit a Π M with #fully(M) τ?

WELFARE Π MATCHING (WELFARE-Π) Input: G=(V, E), sat: V V Q 0, and γ R 0. Question: Does (G,sat) admit a Π M with welfare(M) γ? All problems are in NP since they reduce in polynomial time to a very restricted variant of integer linear programs ( ).

3 Structural Properties We now discuss relations among (see Figure 2) and existence of fractional matchings regarding the three stability concepts. Observation 3.1 ( ). (i) Every OSM is an LSM and a CSM.2 (ii) There exists a graph G with strict preferences sat s.t. (G, sat) admits an LSM which is neither an OSM nor a CSM and admits a CSM which is neither an LSM nor an OSM. The following concept [Tan, 1991] turns out to be very useful for showing the existence of ordinally stable matchings. A stable partition of (G = (V, E), sat) with sat being strict is a permutation π: V V on the vertices, which satisﬁes the following for each vi V : (1) if π(vi) = π 1(vi), then {vi, π(vi)}, {vi, π 1(vi)} E and sat(vi, π(vi)) > sat(vi, π 1(vi)); (2) for each vj NG(vi), if π(vi) = vi or sat(vi, vj) > sat(vi, π 1(vi)), then sat(vj, π 1(vj)) > sat(vj, vi). We call vi a singleton if π(vi) = vi. A stable partition π can be decomposed into cycles, singletons, and transpositions (i.e., disjoint edges). We deﬁne a fractional matching for a stable partition. Deﬁnition 3.2. Let π be a stable partition of (G = (V, E), sat). Deﬁne a matching M π for G corresponding to π as follows. (a) For each vi V with π(vi) = vi, if π(vi)=π 1(vi), then let M π(vi, π(vi)) := 1; otherwise let M π(vi, π(vi)) = M π(vi, π 1(vi)) := 0.5. (b) For each remaining edge e, let M π(e) := 0. Example 1. π = (a, b, c)(d, e)(f) is the only stable partition for the instance in Figure 1. Since π contains (a, b, c) as an odd cycle of length three this instance does not admit a stable integral matching. The matching M π deﬁned for π according to Deﬁnition 3.2 is exactly M1. Recall that it is ordinally stable, and hence cardinally and linearly stable. We will see that each matching as deﬁned by Deﬁnition 3.2 is ordinally stable. Note that the case without ties is observed by Aharoni and Fleiner; Bir o et al. [2003; 2008]. Proposition 3.5 ( ). Each graph on n vertices and with cardinal preferences (and possibly ties) admits an OSM, and

2The result for perfect matchings in the marriage case was observed independently in parallel by Caragiannis et al. [2020].

hence a CSM, that is half-integral and matches each matched agent fully. Algorithm 1 ﬁnds such a matching in O(n2) time.

4 Algorithmic Results

The structural properties from Section 3 give rise to efﬁcient algorithms for ﬁnding optimal stable matchings. For bipartite graphs, we utilize the fact that supports of OSMs consist of stable integral matchings [Aziz and Klaus, 2019, Theorem 3].

Lemma 4.1. Let G be a bipartite graph with satisfaction sat, M an OSM for (G, sat), and (Mj)j [k] a support for M. Then, each Mj, j [k], is (integrally) stable.

We show that the welfare and the number of fully matched agents of a fractional matching are a linear combination of the corresponding values of the matchings in the support.

Lemma 4.2 ( ). Let G be a bipartite graph with satisfactions sat, M be a matching for (G, sat), and (Mj)j [k] be a support of M with the coefﬁcients x1, . . . , xk R>0. Then, the following inequalities hold: welfare(M) = P j [k] xj welfare(Mj) and #fully(M) maxj [k] #fully(Mj).

From Lemma 4.2 it follows that there is an optimal ordinally stable matching that is also integral since we may swap out matchings in the support of a fractional matching for integral matchings with maximum welfare or with maximum number of fully matched agents in order to decrease the number of matchings in the support until only one matching remains in the support. Since ﬁnding an optimal stable integral matching for bipartite graphs with strict preferences is polynomial-time solvable [Irving et al., 1987], we immediately obtain the same for ordinal stability.

Theorem 4.3 ( ). For bipartite graphs with strict preferences, WELFARE-OSM and FULL-OSM are polynomialtime solvable.

The above tractability result heavily utilizes the fact that each fractional matching of a bipartite graph is a convex combination of integral matchings. This fact, however, does not hold for non-bipartite graphs. Nevertheless, we can extend the polynomial-time result to the non-bipartite case. The correctness is based on the following.

Lemma 4.4 ( ). Let G = (V, E) be a graph with cardinal and strict preferences sat, and let M be an OSM of (G, sat). The following statements hold for each agent y V : (1) M(x, y) = 1, where x is the most preferred agent of y. (2) The following are equivalent: (i) y is matched in M; (ii) y is not a singleton in a stable partition of (G, sat); (iii) y is fully matched in M.

Proof sketch. To show Statement (1), suppose to get a contradiction that M(x, y) < 1, where x is the most-preferred agent of y. This implies M(y, x) = M(y, x) < 1, a contradiction to M being ordinally stable regarding edge {x, y}. The equivalence of the statements in (2) is based on Statement (1). We can perform the ﬁrst phase of Irving s algorithm [Irving, 1985] (see Algorithm 2) to guarantee that after phase 1: (a) an agent is a singleton (in any stable partition) iff. her preference list is empty, and (b) every (fully) matched agent in M has non-empty preference list.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Algorithm 2: Irving s phase-1 algo. on input (G, sat)

1 Compute the preference lists P from sat

2 while y V (G) w. non-empty pref. s.t. last P(1st P(y)) =y do

3 D {{1st P(y), z} | 1st P(y) prefers y to z in P}

5 return {v V (G) | v has empty pref. list in P}

Note: In Algorithm 2, we use 1st P(x) and last P(x) to refer to the most-preferred and least-preferred agents in the list x P of x, respectively. We then derive the equivalence from the properties of Algorithm 2 and stable partitions.

Using Lemma 4.4 we can show that the OSM returned from Algorithm 1 achieves the maximum number of fully matched agents whenever no ties are present. Proposition 4.5 ( ). For n-vertex graphs with strict preferences, FULL-OSM is solvable in O(n2) time. We close this section by observing that the OSM that we obtain from Algorithm 1 is also a 2-approximate solution for both cardinal stability and ordinal stability, even with ties. Proposition 4.6 ( ). Algorithm 1 is a 2-approx. algorithm for the maximization variants of FULL-OSM and FULL-CSM.

Proof sketch. Let G = (V, E) denote a graph with cardinal preferences sat with ties. We only show the case of cardinal stability. Let M C be a CSM of (G, sat) with #fully(M C) being maximum. By Proposition 3.5, Algorithm 1 returns an OSM M π on input (G, sat) and the strict preference lists P that are used to compute the corresponding stable partition π (see lines (2) (3)). Recall that in M π every matched agent is fully matched. Let Aπ denote the set of (fully) matched agents in M π. To show that Algorithm 1 is a 2-approx. algorithm for cardinal stability, we observe that at least one agent of each pair of E must come from Aπ because otherwise this pair is ordinally blocking M π. Thus, #fully(M C) P x Aπ, y NG(x) M C(x, y) + P x V \Aπ, y NG(x) Aπ M C(x, y) 2|Aπ|.

5 Hardness Results

Optimal ordinally stable matchings. By Lemmas 4.1 and 4.2, FULL-OSM is equivalent to ﬁnding a stable integral matching with maximum cardinality, and WELFARE-OSM is equivalent to ﬁnding a stable integral matching with minimum egalitarian cost. Since both problems are known to be NP-hard [Manlove et al., 2002], we obtain the following. Theorem 5.1 ( ). When ties are allowed, FULL-OSM and WELFARE-OSM are NP-complete, even for bipartite graphs. Feder (1994) showed that ﬁnding a maximum-welfare stable integral matching in non-bipartite graphs is APX-hard, even for no ties. His idea can be adapted to the ordinal stability. Theorem 5.2 ( ). The maximization variant of WELFAREOSM is APX-hard and WELFARE-OSM is NP-complete, even if no ties are present.

5 eℓ: hℓ ei ℓ ej ℓ, fℓ: ei ℓ ej ℓ, gℓ: ei ℓ hℓ ej ℓ, ei ℓ: eℓ ui fℓ gℓ, ej ℓ: eℓ uj gℓ fℓ, hℓ: gℓ eℓ.

Figure 3: The edge-gadget for eℓ {vi, vj} E with i < j . Left: The acceptability graph and the card. preferences of the 6 edgeagents eℓ, fℓ, gℓ, hℓ, ei ℓ, and ej ℓ. When constructing a matching from an independent set V , we integrally match the pairs corresponding to the green edges if vi V . Right: The induced preference lists.

The instance constructed in Theorem 5.2 has incomplete cardinal preferences, each of value at least one. By assigning distinct cardinal preferences of value less than one to each unmentioned pair of agents we obtain complete preferences:

Corollary 5.3 ( ). For complete preferences without ties, the maximization variant of WELFARE-OSM remains APX-hard and WELFARE-OSM remains NP-complete.

Optimal cardinally stable matchings. We now prove that WELFARE-CSM and FULL-CSM are NP-complete even when the underlying acceptability graph G is bipartite and sat has no ties. For both problems we give a polynomial-time reduction from the NP-complete problem INDEPENDENT SET (IS) [Garey and Johnson, 1979], wherein we are given a graph G and an integer k and ask to ﬁnd an k-vertex subset X in G that is independent, that is, G[X] is edgeless. Both reductions use the same edge-gadgets, which we now describe. Let (G = (V, E), k) be an instance of IS, where V = {v1, . . . , vn} is the vertex set and E = {e1, . . . , em} the edge set. For each edge eℓ E we let {vi, vj} = eℓwhere i < j and we construct an edge-gadget which consists of a bipartite graph Gℓwith preference function sat as shown in Figure 3. The edge-gadget assumes that two vertex-agents ui and uj are already present, which will be ensured by the full construction later. The preference function sat of the agents ui and uj from the vertex gadgets towards the edge-agents ei ℓ and ej ℓare bounded by 5m and will be deﬁned later. The vertex set V (Gℓ) of the edge gadget is the union of the sets Uℓ= {eℓ, fℓ, gℓ} and Wℓ= {hℓ, ei ℓ, ej ℓ}; we call the vertices in Gℓ edge-agents to distinguish them from the vertices in G. Let GE = ℓ [m]Gℓ, i.e., the union of the graphs in all edge-gadgets. We now prove the essential property of the edge-gadgets: For each edge eℓ E with eℓ= {vi, vj} at least one of the edge-agents from{ei ℓ, ej ℓ} is unsatisﬁed with every CSM with sufﬁciently large social welfare. This asserts that not both vi and vj are in an independent set.

Lemma 5.4 ( ). Let M be a CSM for GE and ω denote the welfare of M induced by the edge-agents. Then, (i) ω 3m(2m2 + 9), and (ii) if there is an edge eℓ E with eℓ= {vi, vj} such that UM(ui) < sat(ui, ei ℓ) and UM(uj) < sat(uj, ej ℓ), then ω < 3m(2m2 + 9) n.

Using the above we can give the full reduction.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

2 ui : wi [E(vi)] yi, xi : yi wi, wi : xi ui,

yi : ui xi.

Figure 4: The vertex-gadget for vertex vi V used in the proof of Theorem 5.7. Left: The acceptability graph and the cardinal preferences of agents ui, xi, wi, yi associated with vi. Here, E(vi) = {ei ℓ| eℓ E and vi is incident to eℓ} and [E(vi)] denotes the order of the edge-agents E(vi) by increasing indices. The red edges indicate the matching that signiﬁes that vi is in the independent set. Right: The induced preference lists of the vertex-gadget.

Theorem 5.7 ( ). WELFARE-CSM is NP-complete, even for bipartite graphs with strict preferences.

Proof. Let (G, k) be an instance of IS, where G = (V, E), V = {v1, . . . , vn} and E = {e1, . . . , em}. We indeed reduce from IS in cubic graphs, i.e., each vertex in G has degree three, as the problem remains NP-hard for cubic graphs [Alimonti and Kann, 2000]. We construct an instance (G , sat, γ) of WELFARE-CSM where γ = (3n + 7)n + k + 3m(2m2 + 9) and G = (U W, E ) is a bipartite graph with partite sets U and W. For each vi V , create 4 vertex-agents ui, xi, wi, yi, and add ui, xi to U and wi, yi to W. For each eℓ E, add the edge-agents in Uℓ(resp. Wℓ) to U (resp. W), and add the acceptable edges of GE to E . The remaining edges in E and the sat function are described in Figure 4. In particular, for each vertex vi V and each incident edge eℓ E, i.e., vi eℓ, the cardinal preference of ui towards ei ℓis some value from {3n, 3n + 1, 3n + 2}; recall that each vertex in G has degree three. For each vertex vi V we call the subgraph of G together with the cardinal preferences, induced by {ui, wi, xi, yi} the vertex-gadget for vertex vi. Note that G is a bipartite graph because all the introduced edges are between U and W. This completes the construction of (G , sat, γ) which clearly takes polynomial time. In total, |U| = |W| = 6m + 4n. We construct the cardinal preferences for the vertex-agents to ensure the following. When combined with Lemma 5.4, there are essentially two possible ways of fractionally matching the vertex agents ui, xi, wi, yi corresponding to the same vertex vi V . The ﬁrst one will have a higher welfare than the second one, but it is not possible to use the ﬁrst one for two adjacent agents as this will induce a cardinally blocking pair. Next, we prove (G, k) is a yes-instance of INDEPENDENT SET iff. (G , sat, γ) is a yes-instance of WELFARE-CSM. The if direction amounts to a straightforward check of a somewhat peculiar matching and is available in the long version [Chen et al., 2020]. For the only if direction, let M be a cardinally stable matching for (G , sat) with welfare(M) γ. We show that the following vertex subset V with V = {vi V | M(ui, yi) 1/n} is an independent set in G and |V | k. We ﬁrst show |V | k. For each i [n], deﬁne muw i :=M(ui, wi), mue i :=P

e E(vi) M(ui, e), muy i :=M(ui, yi),

mxw i :=M(xi, wi), mxy i :=M(xi, yi). Then,

z {ui,wi,xi,yi} UM(z) n P

(3n+4)(muw i +mue i +muy i )

+ 3(mxw i +mxy i ) + n P

i=1 muy i (3n + 7)n + Pn i=1 muy i . (1)

The last inequality holds since since the total matching values of the edges incident to ui and xi sum up to at most 1, respectively. We show that Pn i=1 muy i |V |. Deﬁne k1 := |{ui | i [n] and muy i < 1/n}|. Then we have Pn i=1 muy i < k1/n + |V |. Since k1 n, it follows that |V | Pn i=1 muy i . To see that |V | k it thus sufﬁces to show Pn i=1 muy i k. Out of welfare(M) at most 3m(2m2+ 9) stems from the edge-agents (see Lemma 5.4(i)). Hence, at least (3n+4)n+3n+k must stem from the vertex-agents. By the upper bound on the welfare of the vertex-agents derived in eq. (1), thus indeed Pn i=1 muy i k, as required. It remains to show that V is an independent set. Towards a contradiction, suppose that there is an edge eℓ E with eℓ = {vi, vj} such that vi, vj V . By deﬁnition of V we have for both ν {i, j} that UM(uν) sat(uν, yν) muy ν +sat(uν, wν) (1 muy ν ) < 3n. That is, UM(uν) < sat(uν, eν ℓ). By Lemma 5.4(i), the total welfare received from M by vertices of the edge gadgets is at most 3m(2m2 + 9) n. By eq. (1), the total welfare received from the vertex-agents is at most (3n + 8)n and thus welfare(M) < γ, a contradiction.

The preferences constructed in Theorem 5.7 can be completed by assigning to each unacceptable pair of agents a sufﬁciently small but distinct value. Such small satisfaction values will not have any effect on a maximum-welfare CSM as the sum of those utilities will never exceed one. Proposition 5.8 ( ). WELFARE-CSM is NP-complete, even for bipartite graphs with complete and strict preferences. Next, we turn to FULL-CSM. The hardness construction uses the same edge gadgets as before, but with a different analysis. Theorem 5.9 ( ). FULL-CSM is NP-complete, even for bipartite graphs with strict preferences. The construction also implies that FULL-CSM is W[1]-hard wrt. parameter #fully(M) #fully(M π) where M is a perfect CSM and M π is as deﬁned in Deﬁnition 3.2.

6 Conclusion and Outlook Studying optimal stable fractional matchings using the framework of parameterized algorithmics [Niedermeier, 2006; Cygan et al., 2015] may provide more insights into the ﬁne-grained complexity of the problem. Promising parameters are the number of fully matched agents and the social welfare of the fractional matchings in the solution. Finally, regarding preference restrictions [Bredereck et al., 2020], it would be interesting to know whether assuming a special preference structure can help in ﬁnding tractable cases for optimal fractional stable matchings.

Acknowledgments JC and SR supported by the WWTF research grant VRG18012. MS supported by the Alexander von Humboldt Foundation. Signiﬁcant work of SR done while with IMSc, Chennai, India.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

References [Abeledo and Rothblum, 1994] Hern an G. Abeledo and Uriel G. Rothblum. Stable matchings and linear inequalities. Discrete Applied Mathematics, 54(1):1 27, 1994. [Aharoni and Fleiner, 2003] Ron Aharoni and Tam as Fleiner. On a lemma of Scarf. Journal of Combinatorial Theory, Series B, 87:72 80, 2003. [Alimonti and Kann, 2000] Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theoretical Computer Science, 237(1-2):123 134, 2000. [Aziz and Klaus, 2019] Haris Aziz and Bettina Klaus. Random matching under priorities: Stability and no envy concepts. Social Choice and Welfare, 53(2):213 259, 2019. [Bir o et al., 2008] P eter Bir o, Katarina Cechl arova, and Tam as Fleiner. The dynamics of stable matchings and halfmatchings for the stable marriage and roommates problems. International Journal of Game Theory, 36(3):333 352, 2008. [Bredereck et al., 2020] Robert Bredereck, Jiehua Chen, Ugo P. Finnendahl, and Rolf Niedermeier. Stable roommate with narcissistic, single-peaked, and single-crossing preferences. Autonomous Agents and Multi-Agent Systems, 34(2):1 29, 2020. [Caragiannis et al., 2020] Ioannis Caragiannis, Aris Filos Ratsikas, Panagiotis Kanellopoulos, and Rohit Vaish. Stable fractional matchings. Artiﬁcial Intelligence, 295:1 26, 2020. [Chen et al., 2020] Jiehua Chen, Sanjukta Roy, and Manuel Sorge. Fractional matchings under preferences: Stability and optimality. Technical report, ar Xiv:2011.12259, 2020. [Cygan et al., 2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. [Do gan and Yıldız, 2016] Battal Do gan and Kemal Yıldız. Efﬁciency and stability of probabilistic assignments in marriage problems. Games and Economic Behavior, 95:47 58, 2016. [Feder, 1994] Tom as Feder. Network ﬂow and 2satisﬁability. Algorithmica, 11(3):291 319, 1994. [Gale and Shapley, 1962] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 120(5):386 391, 1962. [Garey and Johnson, 1979] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [Gusﬁeld and Irving, 1989] Dan Gusﬁeld and Robert W. Irving. The Stable Marriage Problem Structure and Algorithms. Foundations of Computing Series. MIT Press, 1989. [Horn and Johnson, 1991] Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991.

[Irving et al., 1987] Robert W. Irving, Paul Leather, and Dan Gusﬁeld. An efﬁcient algorithm for the optimal stable marriage. Journal of the ACM, 34(3):532 543, 1987. [Irving, 1985] Robert W. Irving. An efﬁcient algorithm for the stable roommates problem. Journal of Algorithms, 6(4):577 595, 1985. [Ishizuka and Kamiyama, 2018] Takashi Ishizuka and Naoyuki Kamiyama. On the complexity of stable fractional hypergraph matching. In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors, Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 18), volume 123 of LIPIcs, pages 11:1 11:12, 2018. [Kesten and Unver, 2015] Onur Kesten and M. Utku Unver. A theory of school-choice lotteries. Theoretical Economics, 10(2):543 595, 2015. [Kintali et al., 2013] Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang-Hua Teng. Reducibility among fractional stability problems. SIAM Journal on Computing, 42(6):2063 2113, 2013. [Manlove et al., 2002] David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. Hard variants of stable marriage. Theoretical Computer Science, 276(1-2):261 279, 2002. [Manlove, 2013] David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. World Scientiﬁc, 2013. [Niedermeier, 2006] Rolf Niedermeier. Invitation to Fixed Parameter Algorithms. Oxford University Press, 2006. [Roth et al., 1993] Alvin E. Roth, Uriel G. Rothblum, and John H. Vande Vate. Stable matchings, optimal assignments, and linear programming. Mathematics of Operations Research, 18(4):803 828, 1993. [Tan, 1991] Jimmy J.M. Tan. A necessary and sufﬁcient condition for the existence of a complete stable matching. Journal of Algorithms, 12(1):154 178, 1991. [Teo and Sethuraman, 1998] Chung-Piaw Teo and Jay Sethuraman. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 23(4):874 891, 1998. [Vande Vate, 1989] John H. Vande Vate. Linear programming brings marital bliss. Operations Research Letters, 8(3):147 153, 1989.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)