# twosided_matching_meets_fair_division__73a8119c.pdf

Two-Sided Matching Meets Fair Division

Rupert Freeman1 , Evi Micha2 , Nisarg Shah2

1University of Virginia 2University of Toronto Freeman R@darden.virginia.edu, {emicha,nisarg}@cs.toronto.edu

We introduce a new model for two-sided matching which allows us to borrow popular fairness notions from the fair division literature such as envyfreeness up to one good and maximin share guarantee. In our model, each agent is matched to multiple agents on the other side over whom she has additive preferences. We demand fairness for each side separately, giving rise to notions such as double envy-freeness up to one match (DEF1) and double maximin share guarantee (DMMS). We show that (a slight strengthening of) DEF1 cannot always be achieved, but in the special case where both sides have identical preferences, the round-robin algorithm with a carefully designed agent ordering achieves it. In contrast, DMMS cannot be achieved even when both sides have identical preferences.

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 individuals2, 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

1Assigning 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. 2http://csse.utoronto.ca/social-needs-marketplace

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

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. 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 dr i such that each i N ℓand each j N r

can be matched to at most dℓ i and dr j agents on the opposite side, respectively. When dℓ i = dℓ i for any i, i N ℓ(resp. dr j = dr j 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 | dr j 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 P i N ℓ|M ℓ i | = P j N r |M r j | = min(P i N ℓdℓ i, P j N r dr j). 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 ur j : N ℓ R 0. When agents i N ℓand j N r are matched, they simultaneously receive utilities uℓ i(j) and ur j(i), respectively. We assume that utilities are additive. Thus, with

3https://www.nrmp.org/

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

slight abuse of notation, the utilities to agents i N ℓand j N r under matching M are uℓ i(M ℓ i ) = P j M ℓ i uℓ i(j) and ur j(M r j ) = P i M r j ur j(i), respectively. 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. ur j), i.e., j σℓ i j whenever uℓ i(j) > uℓ i(j ) (resp. i σr j i whenever ur j(i) > ur j(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], Pt p=0 M(i, σℓ i(p)) Pt p=0 M(i , σℓ i(p)) c, i, i N ℓ,

and is SD-EFc over N r if, for every t [nℓ], Pt p=0 M(σr j(p), j) Pt p=0 M(σr j(p), j ) c, j, j N r.

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

MMSℓ i = max M M mini N ℓuℓ i(M ℓ i ),

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

MMSr j = max M M minj N r ur j(M r j ).

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 ur j(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.

4Ties 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-DEF1 Matchings 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.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

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ℓ= nrdr 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),

5As 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: return M

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/n Z 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

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

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 matching M 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] . If x = d, then M r j = j + a + td 1 : t = [d] , while

M ℓ i = i a td 1 : t = [d]

= i a (d 1 t)d 1 : t = [d] .

Notice that M r j coincides with M ℓ j+2a d 1+1.

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 = dr j = 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 ur j(i) = ur j (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.

6In 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.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

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, P i N ℓuℓ(M ℓ i ) = P 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ℓ= nrdr 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.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

References [Abdulkadiro glu and S onmez, 2003] A. Abdulkadiro glu and T. S onmez. School choice: A mechanism design approach. American Economic Review, 93(3):729 747, 2003. [Abdulkadiro glu et al., 2005] A. Abdulkadiro glu, P.A. Pathak, A.E. Roth, and T. S onmez. The boston public school match. American Economic Review, 95(2):368 371, 2005. [Aigner-Horev and Segal-Halevi, 2019] E. Aigner-Horev and E. Segal-Halevi. Envy-free matchings in bipartite graphs and their applications to fair division. ar Xiv preprint ar Xiv:1901.09527, 2019. [Aziz, 2020] H. Aziz. Simultaneously achieving ex-ante and ex-post fairness. In Proc. of 16th WINE, pages 341 355, 2020. [Beynier et al., 2019] A. Beynier, Y. Chevaleyre, L. Gourv es, A. Harutyunyan, J. Lesca, N. Maudet, and A. Wilczynski. Local envy-freeness in house allocation problems. Autonomous Agents and Multi-Agents Systems, 33(5):591 627, 2019. [Biswas and Barman, 2018] A. Biswas and S. Barman. Fair division under cardinality constraints. In Proc. of 27th IJCAI, pages 91 97, 2018. [Budish and Cantillon, 2012] E. Budish and E. Cantillon. The multi-unit assignment problem: Theory and evidence from course allocation at harvard. American Economic Review, 102(5):2237 71, 2012. [Budish, 2011] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Caragiannis et al., 2019] I. Caragiannis, D. Kurokawa, H. Moulin, A.D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1 32, 2019. [Echenique and Oviedo, 2006] F. Echenique and J. Oviedo. A theory of stability in many-to-many matching markets. Theoretical Economics, 1(2):233 273, 2006. [Foley, 1967] D. Foley. Resource allocation and the public sector. Yale Economics Essays, 7:45 98, 1967. [Freeman et al., 2020] R. Freeman, N. Shah, and R. Vaish. Best of both worlds: Ex-ante and ex-post fairness in resource allocation. In Proc. of 21st EC, pages 21 22, 2020. [Gale and Shapley, 1962] D. Gale and L.S. Shapley. College admissions and the stability of marriage. Americal Mathematical Monthly, 69(1):9 15, 1962. [Gan et al., 2019] J. Gan, W. Suksompong, and A.A. Voudouris. Envy-freeness in house allocation problems. Mathematical Social Sciences, 101:104 106, 2019. [Gollapudi et al., 2020] S. Gollapudi, K. Kollias, and B. Plaut. Almost envy-free repeated matching in two-sided markets. In Proc. of 16th WINE, pages 3 16, 2020.

[Hatfield et al., 2011] J.W. Hatfield, F. Kojima, Y. Narita, et al. Promoting school competition through school choice: A market design approach. Stanford: Stanford University Capital and Economic Opportunity Working Group Working Paper, 18:2011, 2011. [Kurokawa et al., 2016] D. Kurokawa, A.D. Procaccia, and J. Wang. When can the maximin share guarantee be guaranteed? In Proc. of 30th AAAI, pages 523 529, 2016. [Lipton et al., 2004] R.J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proc. of 6th EC, pages 125 131, 2004. [Othman et al., 2010] A. Othman, T. Sandholm, and E. Budish. Finding approximate competitive equilibria: Efficient and fair course allocation. In Proc. of 9th AAMAS, pages 873 880, 2010. [Patro et al., 2020] G.K. Patro, A. Biswas, N. Ganguly, K.P. Gummadi, and A. Chakraborty. Fairrec: Two-sided fairness for personalized recommendations in two-sided platforms. In Proc. of 29th WWW, pages 1194 1204, 2020. [Procaccia and Wang, 2014] A.D. Procaccia and J. Wang. Fair enough: Guaranteeing approximate maximin shares. In Proc. of 14th EC, pages 675 692, 2014. [Roth and Sotomayor, 1992] A.E. Roth and M. Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485 541, 1992. [Roth, 1984] A.E. Roth. Stability and polarization of interests in job matching. Econometrica: Journal of the Econometric Society, pages 47 57, 1984. [Saidman et al., 2006] S.L. Saidman, A.E. Roth, T. S onmez, M.U. Unver, and F.L. Delmonico. Increasing the opportunity of live kidney donation by matching for two and three way exchanges. Transplantation, 81:773 782, 2006. [Sotomayor, 1999] M. Sotomayor. Three remarks on the many-to-many stable matching problem. Mathematical social sciences, 38(1):55 70, 1999. [S uhr et al., 2019] T. S uhr, A.J. Biega, M. Zehlike, K.P. Gummadi, and A. Chakraborty. Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform. In Proc. of the 25th SIGKDD, pages 3082 3092, 2019. [Tadenuma, 2011] K. Tadenuma. Partnership, solidarity, and minimal envy in matching problems. In Social Ethics and Normative Economics, pages 155 167. Springer, 2011. [Wu and Roth, 2018] Q. Wu and A.E. Roth. The lattice of envy-free matchings. Games and Economic Behavior, 109:201 211, 2018. [Yokoi, 2020] Y. Yokoi. Envy-free matchings with lower quotas. Algorithmica, 82(2):188 211, 2020.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)