Two-Sided Matching Meets Fair Division

1 Introduction

Consider a group of agents seeking to divide some number of indivisible goods amongst themselves. Each agent has a utility function describing the value that they have for every possible bundle of goods, and each agent may have a different utility function. This is a canonical resource allocation problem that arises in estate division, partnership dissolution, and charitable donations, to name just a few. A central goal is to find an allocation of the goods that is fair.

One desirable notion of fairness is envy-freeness [Foley, 1967], which requires that no agent prefer another agent's allocation of goods to her own. This is a compelling definition but, due to the discrete nature of the problem, cannot always be satisfied. Instead, we must consider relaxed versions, with one popular relaxation being envy-freeness up to one good (EF1) [Lipton et al., 2004; Budish, 2011], which requires that any pairwise envy can be eliminated by removing a single good from the envied agent's allocation. An allocation satisfying EF1 always exists for a broad class of agent utility functions [Lipton et al., 2004].

While quite general, the resource allocation model fails to capture some allocation settings that we might be interested in. In particular, it does not allow for the possibility of two-sided preferences, in which agents have preferences over "goods," but also "goods" have preferences over agents.

For instance, when college courses are allocated to students, it is reasonable to assume that students have preferences over the courses they take, and that teachers in charge of courses also have preferences over the students they accept (perhaps measured by prerequisites or GPA). 1 As another example, consider the problem of matching social services to vulnerable individuals 2 , where individuals have preferences over the services they receive, and service providers have preferences over the individuals they serve (perhaps based on demographics, location, or synergy with existing clients).

Allowing for two-sided preferences is immediately reminiscent of the matching literature. In two sided matching, it is generally assumed that each agent has ordinal preferences over the other side, and a matching is sought that is in some sense stable to individual or group deviations. It is well-known that stability is closely related to envy-freeness in the sense that a one-to-one matching is stable if and only if it eliminates justified envy [Abdulkadiro˘glu and S¨onmez, 2003], a requirement specifying that any envy that i may feel for j's match is "justified" by j's match preferring j to i. In many-toone settings, the notions remain tightly connected, with a stable matching being one that eliminates justified envy and has no waste. Justified envy-freeness has also been studied as in its own right in the many-to-one setting [Wu and Roth, 2018; Yokoi, 2020].

Justified envy, and therefore stability, fundamentally rely on the idea that the less an agent is preferred by the other side, the lower her own entitlement should be. However, in some applications, it may be desirable to provide equal entitlements or moral claims to agents regardless of how valued they are by the agents on the other side. For example, instructors may prefer students with high GPA over students with low GPA, but it is not clear that universities should adopt such a policy in their course scheduling (and, in fact, usually do not). Therefore, while stability is a valuable notion in many settings, in this work we consider two-sided preferences while incorporating traditional notions from fair division.

Our contributions. We introduce and study a two-sided resource allocation setting in which we have two groups of agents, where each agent has preferences over agents on the other side. Each agent must be "matched" to a subset of agents on the other side, subject to a maximum degree constraint. Our goal is to find a many-to-many matching that provides fairness to both sets of agents simultaneously. The standard resource allocation setting is a special case of our model in which each good can be matched to at most one agent, each agent can be matched to any number of goods, and goods are indifferent to which agent they are assigned to.

1 Assigning students to courses has been studied before [Budish, 2011; Othman et al., 2010; Budish and Cantillon, 2012], but these papers typically only consider the preferences of the students.

2 http://csse.utoronto.ca/social-needs-marketplace

As a natural tradeoff between expressiveness and succinctness, we restrict our attention to additive preferences, in which the utility for being matched to a group of agents is equal to the sum of utilities for being matched to each agent in the group individually. While conceptually simple, additive preferences have led to a rich body of work in fair division. We focus primarily on the case in which all agents on the same side have the same degree constraint, and the total maximum degree on both sides is equal. In this case, it is reasonable to seek a complete matching, which saturates the degree constraints of all the agents on both sides.

We begin by considering double envy-freeness up to one match (DEF1), requiring that EF1 hold for both sets of agents simultaneously. We show that a complete matching satisfying (a slight strengthening of) DEF1 does not always exists, but in the special case where both sides have identical ordinal preferences, it exists and can be computed efficiently using a carefully designed round robin algorithm.

We also ask whether it is possible to find matchings that satisfy double maximin share guarantee (DMMS), a twosided version of the maximin share guarantee. Even when both sides have identical preferences, a complete DMMS matching may not exist, in contrast to the one-sided setting in which an MMS allocation is guaranteed to exist when agents have identical preferences. In general, we show that approximate DMMS and approximate DEF1 are incompatible, although in the special case where the degree constraint is equal to two we can achieve exact versions of both simultaneously.

Related work. Most related to our work is that of Patro et al. [2020], who draw on the resource allocation literature to guarantee fairness for both producers and consumers on a two-sided platform. However, in their model, producers are indifferent between the customers; thus, only one side has interesting preferences. Other work [S¨uhr et al., 2019] has focused on guaranteeing fairness in two-sided platforms over time, rather than in a one-shot setting. Of particular note is the work of Gollapudi et al. [2020], who consider two-sided EF1 in a dynamic setting, but obtain positive results primarily for symmetric binary valuations, a much more restrictive class of valuations than we consider. Tadenuma [2011] studies envy minimization in two-sided matching subject to other notions, including stability, but focuses on ordinal notions of envy and restricts attention to one-to-one matchings.

The theories of matching and fair division each have a rich history. Traditional work in matching theory has focused on one-to-one or many-to-one matchings, beginning with the seminal work of Gale and Shapley [1962] and finding applications in areas such as school choice [Abdulkadiro˘glu and S¨onmez, 2003; Abdulkadiro˘glu et al., 2005;

Hatfield et al., 2011], kidney exchange [Saidman et al., 2006], and the famous US resident-to-hospital match. 3 We note that EF1 as a condition becomes vacuous whenever a set of agents has a maximum degree constraint of one, so we focus instead on the more general case of many-tomany matchings. This case has also been well-explored in the matching literature [Roth, 1984; Sotomayor, 1999; Roth and Sotomayor, 1992; Echenique and Oviedo, 2006], although that literature focuses on stability notions, which have a very different flavor to our guarantees.

Our work draws extensively on notions from the fair division literature, particularly envy-freeness and its relaxations [Foley, 1967; Budish, 2011; Lipton et al., 2004] and the maximin share guarantee [Budish, 2011]. Prior work has studied the satisfiability of these properties in the resource allocation setting [Caragiannis et al., 2019; Procaccia and Wang, 2014; Kurokawa et al., 2016], including the house allocation setting in which each agent is "matched" to a single item [Aigner-Horev and Segal-Halevi, 2019; Beynier et al., 2019; Gan et al., 2019], but, to our knowledge, no work has considered satisfying them on both sides of a market simultaneously.

2 Preliminaries

For n ∈ N, define [n] = {0, . . . , n - 1}. There are two disjoint groups of agents, denoted N ℓ ("left") and N r ("right"), of sizes nℓ and nr , respectively. For simplicity of notation, we write N ℓ = [nℓ ] and N r = [nr ]; when referring to an agent by only its index, the group she belongs to will be clear from context. We use indices i ∈ [nℓ ] and j ∈ [nr ] to refer to agents on the left and right, respectively. We are given degree constraints dℓi and dri such that each i ∈ N ℓ and each j ∈ N r can be matched to at most dℓi and drj agents on the opposite side, respectively. When dℓi = dℓi′ for any i, i′ ∈ N ℓ (resp. drj = drj ′ for any j, j ′ ∈ N r ), we denote by dℓ (resp. dr ) the common degree constraint of all agents in N ℓ (resp. N r ).

A (many-to-many) matching M is represented as a binary nℓ × nr matrix, where M(i, j) = 1 if i ∈ N ℓ and j ∈ N r are matched, and M(i, j) = 0 otherwise. With slight abuse of notation, we denote M ℓ i = {j ∈ N r : M(i, j) = 1} and M r j = {i ∈ N ℓ : M(i, j) = 1} as the sets of agents on the opposite side that agents i ∈ N ℓ and j ∈ N r are matched to, respectively. We say that M is valid if it respects the degree constraints, i.e., if |M ℓ i | ≤ dℓi for each i ∈ N l and |M r j | ≤ drj for each j ∈ N r . Hereinafter, we omit the term valid, but will always refer to valid matchings. We say that M is complete if ∑i∈N ℓ |M ℓ i | = ∑j∈N r |M r j | = min(∑i∈N ℓ dℓi , ∑j∈N r drj ). That is, a complete matching is one in which either every agent on the left has their degree constraint met exactly, or every agent on the right does.

Each agent i ∈ N ℓ has a valuation function uℓi : N r → R≥0 and each agent j ∈ N r has a valuation function urj : N ℓ → R≥0. When agents i ∈ N ℓ and j ∈ N r are matched, they simultaneously receive utilities uℓi (j) and urj (i), respectively. We assume that utilities are additive. Thus, with slight abuse of notation, the utilities to agents i ∈ N ℓ and j ∈ N r under matching M are uℓi (M ℓ i ) = ∑j∈Mℓ i uℓi (j) and urj (M r j ) = ∑i∈Mr j urj (i), respectively.

3 https://www.nrmp.org/

Our main constructive results take only the agents' preference orders as input. For agent i ∈ N ℓ (resp. j ∈ N r ), we denote by σℓ i (resp. σr j ) a linear order over N r (resp. N ℓ ) which is consistent with the valuation function uℓi (resp. urj ), i.e., j ≻σℓ i j ′ whenever uℓi (j) > uℓi (j ′ ) (resp. i ≻σr j i′ whenever urj (i) > urj (i′ )). 4 With a slight abuse of notation, we denote with σℓ i (p) (resp. σr j (p)) the position of alternative p in σℓ i (resp. σr j ).

Inspired by envy-freeness up to one good (EF1) from classical fair division [Budish, 2011; Lipton et al., 2004], we define the following fairness guarantee in our setting.

Definition 1 (Double Envy-Freeness Up To c Matches (DEFc)). We say that matching M is envy-free up to c matches (EFc) over N ℓ if for each pair of agents i, i′ ∈ N ℓ , there exists Sℓ ⊆ M ℓ i′ with |Sℓ | ≤ c such that uℓi (M ℓ i ) ≥ uℓi (M ℓ i′ \ Sℓ ). Similarly, we say that it is EFc over N r if, for each pair of agents j, j ′ ∈ N r , there exists Sr ⊆ M r j ′ with |Sr | ≤ c such that uℓj (M r j ) ≥ uℓj (M r j ′ \ Sr ). We say that M is DEFc if it is EFc over both N ℓ and N r .

When an algorithm takes as input only the preference rankings, it must ensure that the matching it returns is DEFc for all possible valuation functions which could have induced the rankings. It is easy to observe that this is equivalent to satisfying the following stronger guarantee which uses the stochastic dominance (SD) relation.This is akin to the SD-EF1 strengthening of EF1 [Freeman et al., 2020; Aziz, 2020].

Definition 2 (SD Double Envy-Freeness Up To c Matches (SD-DEFc)). We say that matching M is SD-envy-free up to c matches (SD-EFc) over N ℓ if, for every t ∈ [nr ],

and is SD-EFc over N r if, for every t ∈ [nℓ ],

M is called SD-DEFc if it is SD-EFc over both N ℓ and N r .

Finally, we extend a different fairness notion from classical fair division called the maximin share guarantee (MMS).

Definition 3 (α-Double Maximin Share Guarantee (α-DMMS)). Let M denote the set of valid matchings. The maximin share value of agent i ∈ N ℓ is defined as

and the maximin share value of agent j ∈ N r is defined as

Given α ∈ [0, 1], matching M is called α-maximin share fair (α-MMS) over N ℓ if uℓi (M ℓ i ) ≥ α·MMSℓ i for every i ∈ N ℓ , and α-MMS over N r if urj (M r j ) ≥ α · MMSr j for every j ∈ N r . It is called α-DMMS if it is α-MMS for both N r and N r . When α = 1, we write DMMS instead of 1-DMMS.

4 Ties among agents with equal utility are broken arbitrarily.

The notions of (SD-)DEF1 and DMMS are incomparable to the traditional notions of stability and justified envyfreeness, as the following example shows.

Example 1. Suppose N ℓ = N r = {0, 1, 2, 3}, the common degree requirement is 2, and each side has identical ordinal preference 0 ≻ 1 ≻ 2 ≻ 3 over the other side. The only matching that is stable and eliminates justified envy is the one that matches each i ∈ {0, 1} on the left with every j ∈ {0, 1} on the right, and each i ∈ {2, 3} on the left with every j ∈ {2, 3} on the right. Indeed, if some i ∈ {0, 1} on the left is not matched to some j ∈ {0, 1} on the right, then j must be matched to some i′ ∈ {2, 3} on the left, which would make (i, j) a blocking pair, and i would (justifiably) envy i′ for her match with j. However, this matching violates DEF1 when, for example, agent 2 on the left has more value for agent 1 on the right than for agents 2 and 3 on the right combined (as this would leave her envious of agents 0 and 1 on the left, even after ignoring their match to agent 0 on the right). Note that this matching also violates DMMS, since each agent on the left could partition those on the right into bundles {0, 3}, {0, 3}, {1, 2}, {1, 2}, guaranteeing themselves a better bundle than the {2, 3} that agents 2 and 3 receive. On the other hand, any one-to-one matching satisfies (SD-)DEF1 and DMMS, but many one-to-one matchings are not stable or free of justified envy.

3 Double Envy-Freeness Up To One Match

In this section, we focus on double envy-freeness up to one match, more specifically, its strengthening SD-DEF1. We begin in Section 3.1 by presenting an impossibility result that holds even under quite restrictive conditions. Then, in Section 3.2, we present an algorithm that efficiently computes an SD-DEF1 matching whenever both groups of agents have identical ordinal preferences. In the full version of the paper, we present an additional positive result for the case that all agents have maximum degree constraint equal to two, and one side has identical preferences.

3.1 SD-DEF1Matchings May Not Exist

Our first main result says that a complete SD-DEF1 matching may not exist. Observe that without the completeness condition an empty matching is trivially SD-DEF1.

Theorem 1. A complete SD-DEF1 matching is not guaranteed to exist.

The proof of Theorem 1, along with all other omitted proofs, can be found in the full version of the paper. It uses a counterexample in which both sides have the same number of agents (that is, N ℓ = N r = n), all agents have the same degree constraint (dℓ = dr = d), and one group of agents have identical preferences (uℓi = uℓi′ for all i, i′ ∈ N ℓ ). Thus, Theorem 1 holds even in this restricted case, and continues to hold for more general settings.

A natural question, that we leave open, is whether the impossibility continues to hold when we relax SD-DEF1 to DEF1. We have found no counterexamples (even for SDDEF1) via simulation; the counterexample for SD-DEF1 is carefully crafted but relies on the strength of SD-DEF1.

3.2 Identical Ordinal Preferences on Both Sides

Theorem 1 says that a complete SD-DEF1 matching is not guaranteed to exist even under quite restrictive conditions. It is natural to ask whether there exist any settings in which a complete SD-DEF1 matching can be guaranteed. In the full version of the paper, we establish the existence of a complete SD-DEF1 matching by restricting the degree bound (with still only one side having identical preferences). In this section, we consider a different restriction: when agents on both sides have identical preferences, i.e., σℓ i = σℓ i′ for all i, i′ ∈ N ℓ and σr j = σr j ′ for all j, j ′ ∈ N r .

Theorem 2. When nℓdℓ = nr dr and both groups of agents have identical ordinal preferences, a complete SD-DEF1 matching always exists and can be computed efficiently.

The proof of Theorem 2 follows from a series of lemmas. In the main text we focus on the simple case for which N ℓ = N r = n and dℓ = dr = d. Theorem 2 follows from progressively reducing the general case to this simple case.

We denote by σℓ and σr the ordinal preferences of the agents in N ℓ and N r , respectively. Without loss of generality, assume that σℓ = σr = 0 ≻ . . . ≻ n-1. We want to find an SD-DEF1 matching under which each agent is matched to exactly d agents on the opposite side. A natural idea is to let agents on one side pick agents on the other side in a roundrobin fashion. That is, we construct an ordering R over agents on one side, and these agents take turns according to R in a cyclic fashion with each agent, in her turn, making one match to her most preferred agent (i.e. lowest indexed agent) on the opposite side who has less than d matches so far. A standard argument from classical fair division shows that regardless of the ordering R, the resulting matching will be SD-EF1 over over the side that does the picking. 5 However, as the example below shows, not all orderings R lead to a matching that also satisfies SD-EF1 over the other side.

Example 2. Consider the case where n = 5 and d = 2. Suppose the ordering R has agents on the left choose in the order 0, 1, 2, 3, 4. Then, agent 0 on the right will be matched to agents 0 and 1 on the left, while agent 1 on the right will be matched to agents 2 and 3 on the left. SD-EF1 is violated as agent 1 significantly envies agent 0 on the right side.

We now show that when R is carefully designed, SD-EF1 can also be satisfied over the other side, resulting in SDDEF1. Algorithm 1 takes as input parameters a ∈ [n] and x ∈ {d, n - d}, and for any choices of these parameters, constructs an ordering R over the agents on (say) the left side. Algorithm 2 then uses this ordering to run the round-robin procedure while respecting the degree constraints. Example 3 demonstrates these algorithms.

Example 3. Consider the same instance as Example 2, with n = 5 and d = 2. Suppose we choose a = 3 and x = d = 2. Then the round robin ordering returned by Algorithm 1 is R(0) = 3+0 = 3 (setting i = 0), R(1) = 3+3 = 1 (i = 3), R(2) = 3 + 1 = 4 (i = 1), R(3) = 3 + 4 = 2 (i = 4),

5 As observed by Biswas and Barman [2018], the standard round robin algorithm is not EF1 when agents have cardinality constraints, but EF1 is retained provided that agents have identical preferences.

Algorithm 1 Round-Robin-Ordering(n, a, x)

• 1: // x and n coprime, so x-1 (mod n) exists 2: for i ∈ [n] do 3: R(p) = a+px-1 (mod n) 4: end for 5: return R

Algorithm 2 Restricted-Round-Robin-Coprime(n, d)

• 1: Choose a ∈ {0, . . . , n - 1} and x ∈ {d, n - d}
• 2: R =Round-Robin-Ordering(n, a, x)
• 3: // Round-robin with ordering R over agents on the left
• 4: M(i, j) = 0, ∀i, j ∈ [n]
• 5: for j ∈ [n], t ∈ [d] do
• 6: M(R(j · d+ t (mod n)), j) = 1
• 7: end for
• 8: returnM

and R(4) = 3 + 2 = 0 (i = 2), with all addition performed mod n. That is, agents on the left choose in order 3, 1, 4, 2, 0. This results in the matching M ℓ 3 = {0, 2}, M ℓ 1 = {0, 3}, M ℓ 4 = {1, 3}, M ℓ 2 = {1, 4}, and M ℓ 0 = {2, 4} (equivalent to the formula provided directly in Line 6 of Algorithm 2). The fact that this is SD-EF1 over N ℓ is easy to check. Examining the matching, note that M r 0 = {1, 3} = M ℓ 4 , M r 1 = {2, 4} = M ℓ 0 , M r 2 = {0, 3} = M ℓ 4 , M r 3 = {1, 4} = M ℓ 2 , and M r 4 = {0, 2} = M ℓ 3 . That is, the matchings received by agents on the right are the same as those received by agents on the left, up to a cyclic shift. For this matching, SD-EF1 over N ℓ immediately implies SD-EF1 over N r .

The next result shows that for any choices of the parameters, the resulting matching is SD-DEF1. The idea of the proof is to show that the structure in Example 3 holds in general: for any allowed choice of (a, x), the set of bundles received by agents on the right is the same as the set of bundles received by agents on the left, thus inheriting SD-EF1 from the fact that the matching is constructed by agents on the left choosing in round robin sequence.

Lemma 1. When nℓ = nr = n and dℓ = dr = d are coprime and both groups of agents have identical ordinal preferences, Algorithm 2 efficiently computes a complete SDDEF1 matching.

Proof. To avoid the (mod n) notation in this proof, we will treat integers as belonging to the ring Z/nZ of integers modulo n. Thus, addition, multiplication, and multiplicative inverses will be modulo n. Note that x-1 exists because x ∈ {d, n - d} = {d, -d} is coprime with n.

We claim that the ordering R constructed in Algorithm 1 is a valid ordering over the agents in N ℓ . Notice that because x ∈ {d,-d} is coprime with n, (p · x-1 )i∈[n] = [n]. Thus, each position in the ordering R is mapped to exactly one agent. Because agents on the left take d turns in a cyclic fashion, it is convenient to think of an extended ordering R which is the original R concatenated with itself d times: one can check that this still obeys R(p) = a + px-1 for all p ∈ [nd].

Next, we argue that the matching returned is a valid complete matching. Notice that during the round-robin, d agents on the left that are consecutive in the ordering pick a given agent on the right before moving on to the next lowest indexed agent on the right. Further, each agent on the left gets d turns. Hence, it is easy to see that every agent is matched to exactly d agents on the opposite side.

As mentioned earlier, the fact that the returned matchingM is SD-EF1 over N ℓ follows directly from the standard roundrobin argument in classical fair division: given any pair of agents i, i′ ∈ N ℓ , if we ignored the first turn taken by i′ , then in each round agent i would get a turn before agent i′ does, and hence, would not envy agent i′ in the SD sense. It remains to show that M is also SD-EF1 over N r . We show that for each agent j ∈ N r , there exists an agent i ∈ N ℓ such that M r j = M ℓ i . SD-EF1 over N r will then follow from SD-EF1 over N ℓ given that σℓ = σr .

Let us focus on agent j ∈ N r . Because agents on the right are picked from lowest-indexed to highest-indexed, agent j is picked by the d agents from N ℓ who appear consecutively in the (extended) ordering R at indices jd+ t for t ∈ [d]. Given that R(p) = a + px-1 for all p ∈ [nd], we immediately have M r j = {a+ (jd+ t)x-1 : t = [d]}.

Next, let us focus on agent i ∈ N ℓ . If she is matched to some agent j ∈ N r in a particular turn, then from the observation above, it must be that i = a + (jd + t)x-1 for some t ∈ [d]. Solving this for j, we get that j = ((i - a)x - t)d-1 . Varying t ∈ [d] in this equation gets us the d agents on the right that agent i is matched to: M ℓ i = {((i -a)x- t)d-1 : t = [d]}.

To show that for each j ∈ N r , there exists i ∈ N ℓ with M ℓ i =M r j , we take two cases.

If x = n - d = -d, then x-1 = (-d)-1 = -d-1 . In this case, it is easy to check that taking i = j suffices as M r j =M ℓ j = {a - j - td-1 : t = [d]}.

Algorithm 2 executes round-robin with the left side taking turns, and allows freely choosing a ∈ [n] and x ∈ {d, n - d} to decide their ordering. Note that if the right side takes turns instead, the algorithm still produces a complete SDDEF1 matching. However, this extension does not find any new matchings. When x = n - d, the matching produced is symmetric (M ℓ i = M r i for all i ∈ [n]), and thus the same regardless of which side takes turns. When x = d, the allocations on one side are cyclic shift of the allocations on the other side. Hence, any matching produced by the right side taking turns can also be produced by the left side taking turns with appropriately chosen (a, x).

What about allowing choices of x other than just d and n - d? At least for n = 7, d = 3, and a = 0, it is easy to check by hand that no other choices of x produce an SDDEF1 matching. On the other hand, could it be that some of the 2n choices of (a, x) are redundant and lead to the same matching as other choices? The following result shows that in every instance, all 2n choices lead to different matchings.

Proposition 1. For any inputs n and d to Algorithm 2, the 2n possible choices of (a, x) result in distinct matchings.

Given Proposition 1, one may be tempted to conjecture that these 2n choices generate all complete SD-DEF1 matchings. However, in the full version of the paper, we show that this is not the case, leaving open the question of characterizing the set of all complete SD-DEF1 matchings.

The proof of Theorem 2 continues by reducing the case where n and d are not coprime to the coprime case. Letting g = gcd(n, d), we divide both sides into g sub-groups of n′ = n/g agents each. Then, we run Algorithm 2 a total of g2 times to match agents from each sub-group on the left to d′ = d/g agents from each sub-group on the right. This matches each agent with exactly d agents from the opposite side. Note that we allow each of the g2 calls to Algorithm 2 to use arbitrary choices of a and x. Nonetheless, we show that the resulting complete matching must be SD-DEF1.

Lemma 2. When nℓ = nr = n, dℓ = dr = d, and both groups of agents have identical ordinal preferences, a complete SD-DEF1 matching always exists and can be computed efficiently.

Finally, we turn our attention to the general case in which we drop the constraints nℓ = nr and dℓi = drj = d. We do however require that nℓ · dℓ = nr · dr . The proof of Theorem 2, which appears in the full version of the paper, uses a trick of adding dummy agents to the side with fewer agents, computing an SD-DEF1 matching as per Lemma 2, and then removing the dummy agents. The key is to show that the removal of dummy agents reduces the degrees of the agents on the opposite side exactly as intended and SD-DEF1 is preserved.

We note that it is possible to extend our constructive result slightly beyond the case of nℓ · dℓ = nr · dr . Without loss of generality, assume that nℓ · dℓ < nr · dr . First, note that in this case, no matching is complete. We can still make the degree of each agent on the left equal to dℓ , but the best we can hope for is that the degrees of agents on the right differ by at most 1, i.e., they are either ⌊nℓ ·dℓ/nr ⌋ or ⌈nℓ ·dℓ/nr ⌉. 6 In this case, the trick outlined in Theorem 2 only works when the dummy agents are added to the left side, i.e., if nℓ ≤ nr . We conjecture that such an SD-DEF1 matching always exists even when nℓ > nr , but leave it as an open question.

4 Double Maximin Share Guarantee

In this section, we focus first on the existence of DMMS matchings, and second on the existence of matchings that are DMMS and SD-DEF1 concurrently.

We begin by considering the case where agents on both sides have identical preferences, i.e., uℓi (j) = uℓi′(j), for any pair of agents i, i′ ∈ N ℓ , and any j ∈ N r , and similarly urj (i) = urj ′(i), for any pair of agents j, j ′ ∈ N r and any i ∈ N ℓ . We show the following negative result, which stands in contrast to the one-sided fair division setting in which an MMS allocation is guaranteed to exist when agents have identical preferences.

6 In case that nℓ ·dℓ/nr is an integer, we can set this to be dr and achieve exactly equal degrees on the right side too.

Theorem 3. A 0.89-DMMS matching may not exist, even when agents on both sides have identical preferences.

Proof. We denote by uℓ and ur the cardinal preferences of the agents in N ℓ and N r respectively. As the utilities are the same across the agents in the same group, we can define MMSℓ = MMSℓ i for all i ∈ [nℓ ], and MMSr = MMSr j for all j ∈ [nr ].

Consider the instance with n = nℓ = nr = 7 and d = dℓ = dr = 3, uℓ (j) = n - j - 1 for all j ∈ [n], and ur (i) = n - i - 1 for all i ∈ [n]. Thus, for any complete matching, ∑i∈N ℓ uℓ (M ℓ i ) = ∑j∈N r ur (M ℓ j ) = 63. This means that MMSℓ = MMSr ≤ 9, because if all agents receive equal utility then they each get utility 9. Next, we construct a matching M such that uℓ (M ℓ i ) = 9 for all i ∈ [n].

Without loss of generality, assume that M ℓ 0 , M ℓ 1 , and M ℓ 2 all contain agent 0. Then, we know that agents 1 and 2 cannot be contained in these bundles, because then they would have value larger than 9, implying that some other agent receives utility less than 9. Without loss of generality, we assume that bundles M ℓ 3 , M ℓ 4 , and M ℓ 5 contain agent 1. Now, we observe that M ℓ 6 = {2, 3, 4}, as there is no other way to have uℓ (M ℓ 6 ) = 9. As 0 and 2 can not belong to the same bundle (such a bundle would be valued at least 10), we may assume without loss of generality that agent 2 is contained in M ℓ 3 , and M ℓ 4 . Then, the constraint that uℓ (M ℓ 3 ) = uℓ (M ℓ 4 ) = 9 dictates that M ℓ 3 = M ℓ 4 = {1, 2, 6}. With these bundles fixed, it is easy to check that the only M ℓ 5 that yields uℓ (M ℓ 5 ) = 9 is M ℓ 5 = {1, 3, 5}. Lastly, without loss of generality, we may assume that M ℓ 0 = M ℓ 1 = {0, 4, 5}, and M ℓ 2 = {0, 3, 6}. Hence, we conclude that the following matching is the only one (subject to permutations of N ℓ ) that satisfies MMS for agents on the left.

• M ℓ 0 =M ℓ 1 = {0, 4, 5}
• M ℓ 2 = {0, 3, 6}
• M ℓ 3 =M ℓ 4 = {1, 2, 6}
• M ℓ 5 = {1, 3, 5}
• M ℓ 6 = {2, 3, 4}

Now, consider agents 0 ∈ N r and 4 ∈ N r . Both are matched to agents 0 ∈ N ℓ and 1 ∈ N ℓ , but agent 0 ∈ N r is matched to agent 2 ∈ N ℓ while agent 4 ∈ N r is matched to agent 6 ∈ N ℓ . Therefore, ur (M r 0 ) ̸= ur (M r 4 ) (and this difference persists regardless of permutations of N ℓ ). It is therefore not the case that every agent on the right receives utility 9; in particular, one agent receives utility 8 or less, producing the approximation ratio α = 8/9 < 0.89.

While a DMMS matching may not exist, even when preferences are identical, we can exploit the algorithms presented in Section 3 to obtain an approximation to DMMS.

Theorem 4. When nℓdℓ = nr dr and both groups of agents have identical utilities, every complete SD-DEF1 matching M is also 1 dℓ -MMS over N ℓ , and 1 dr -MMS over N r .

We next show an almost-matching upper bound that can be achieved by any SD-DEF1 matching, to complement Theorem 4. In fact, we show a more general result that trades off the approximation to DMMS with the approximation to double envy-freeness.

Theorem 5. There exists an instance with nℓ = nr = n and dℓ = dr = d in which no matching is simultaneously c+2 d - DMMS and SD-DEFc for any c ∈ [d].

Finally, we show that a strong impossibility persists even if we only require SD-EF1 on one side and MMS on the other.

Theorem 6. A matching that satisfies SD-EF1 over N ℓ and MMS over N r is not guaranteed to exist, even when agents on both sides have identical preferences.

5 Discussion

We have introduced a model that bridges two-sided matching and fair division by requiring fairness on both sides of a matching market. We have shown that SD-EF1 can be achieved for agents on both sides, when all agents on the left side and all agents on the right share a common ordinal preference ranking over agents on the other side. When this condition is not satisfied, there may exist no matching that satisfies SD-DEF1. We have also shown that there may not exist a doubly MMS matching even when agents have identical preferences. While we do not rule out a good approximation to DMMS, we show that it is essentially impossible to obtain a good approximation to DMMS if one also requires SD-DEF1.

It is interesting to note that the proofs of Theorems 4 and 5 do not rely on the constraints that an agent in N ℓ can have up to d matches, and can be matched with an agent in N r at most once. Therefore, these theorems also hold in a one-sided fair division problem where there are n agents and n/d items with d copies each, and all the agents have identical preferences.

Many interesting avenues for future research remain. For example, one can hope to derive weaker positive results in the case where one side has identical preferences. When the side with identical preferences does the picking, Algorithm 2 remains EF1 for that side. In the full version of the paper, we conduct empirical simulations and observe that Algorithm 2 remains EF1 for some of the agents on the other side as well (and does better than the classical round-robin algorithm in this aspect). It would also be interesting to compare the two-sided fair division setting with its one-sided counterpart (where only one side has preferences and we seek fairness only for this side). In our simulations, we observe that there is a sharp contrast for envy-freeness (one-sided EF is almost always achievable while two-sided DEF almost always isn't). For the maximin share guarantee, however, there is no contrast: both one-sided MMS and two-sided DMMS are almost always achievable. Theoretically analyzing the probability of satisfiability of these notions in random instances would be an interesting direction for the future. One can also consider two-sided versions of other fairness notions, including those that remain interesting when the degree constraint is 1, which could yield further interesting results in the one-to-one or many-to-one settings. Finally, it would also be interesting to derive positive results when each agent can have a different degree constraint.