Fractional Matchings under Preferences: Stability and Optimality

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 find 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 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.

∗Contact Author

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 find application in randommatching [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 definition of stability in the integral case is straightforward, there are several natural ways to define 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) specifies the satisfaction of u towards v. A fractional matching M : E → [0, 1] is 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) := ∑{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 satisfied 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, define M(x,⪰y) := ∑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 first 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 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 classification, 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 difficulty 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 influence of ties on the complexity in the integral setting has been extensively studied [Gusfield 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 efficient algorithms that solve additional optimization goals or find 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 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 finding 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 finds at most five 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 Gusfield 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 find each other acceptable, and sat specifies the cardinal preferences of an agent towards another agent, i.e., for all u, v ∈ V , sat(u, v) specifies 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 ∑{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 ∑u∈NG(v) M(v, u) = 1 (resp. ∑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 coefficients x1, . . . , xk ∈ R>0, and integral matchings M1, . . . ,Mk of G such that ∑j∈[k] xj = 1 and for each edge e ∈ E it holds that M(e) = ∑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 definitions).

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 | ∑y∈NG(x) M(x, y) = 1}| and welfaresat(M) := ∑v∈V Usat,M(v). If sat is clear from the context then we drop it in welfaresat. The problems are defined as follows, where Π ∈ {OSM, CSM}1 :

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

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 π andM π for (G, ˆ sat) (cf. Def. 3.2)
• 4 returnM π

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 LSMand 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 satisfies 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 define a fractional matching for a stable partition.

Definition 3.2. Let π be a stable partition of (G = (V,E), sat). Define 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 π defined for π according to Definition 3.2 is exactly M1. Recall that it is ordinally stable, and hence cardinally and linearly stable.

We will see that each matching as defined by Definition 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 hence a CSM, that is half-integral and matches each matched agent fully. Algorithm 1 finds such a matching in O(n2 ) time.

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

4 Algorithmic Results

The structural properties from Section 3 give rise to efficient algorithms for finding 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 Gbe a bipartite graph with satisfaction sat, M an OSM for (G, sat), and (Mj)j∈[k] a support for M. Then, eachMj, 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 coefficients x1, . . . , xk ∈ R>0. Then, the following inequalities hold: welfare(M) = ∑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 finding 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 inM.

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 first 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.

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. lastP(1stP(y))̸=y do 3 D← {{1stP(y), z} | 1stP(y) prefers y to z in P} 4 P ←P -D 5 return {v ∈ V (G) | v has empty pref. list in P}

Note: In Algorithm 2, we use 1stP(x) and lastP(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 ) ≤ ∑ x∈Aπ , y∈NG(x) M C (x, y) +

5 Hardness Results

Optimal ordinally stable matchings. By Lemmas 4.1 and 4.2, FULL-OSM is equivalent to finding a stable integral matching with maximum cardinality, and WELFARE-OSM is equivalent to finding 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 finding 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.

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 find 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 defined 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 unsatisfied with every CSM with sufficiently 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.

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 toW.
• 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 first one will have a higher welfare than the second one, but it is not possible to use the first 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 first show |V ′ | ≥ k. For each i∈[n], define muw i :=M(ui,wi), mue i :=∑ e∈E(vi)M(ui, e), muy i :=M(ui, yi),

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 ⌊∑ni=1 muy i ⌋ ≤ |V ′ |. Define k1 := |{ui | i ∈ [n] and muy i < 1/n}|. Then we have ∑ni=1 muy i < k1/n + |V ′ |. Since k1 ≤ n, it follows that |V ′ | ≥ ⌊∑ni=1 muy i ⌋. To see that |V ′ | ≥ k it thus suffices to show ∑ni=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 ∑ni=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 definition 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 sufficiently 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 defined in Definition 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 fine-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 finding 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. Significant work of SR done while with IMSc, Chennai, India.