# fair_pairwise_exchange_among_groups__e6a3802d.pdf

Fair Pairwise Exchange among Groups

Zhaohong Sun1 , Taiki Todo2 and Toby Walsh1

1UNSW Sydney 2Kyushu University {zhaohong.sun, t.walsh}@unsw.edu.au, todo@inf.kyushu-u.ac.jp

We study the pairwise organ exchange problem among groups motivated by real-world applications and consider two types of group formulations. Each group represents either a certain type of patientdonor pairs who are compatible with the same set of organs, or a set of patient-donor pairs who reside in the same region. We address a natural research question, which asks how to match a maximum number of pairwise compatible patient-donor pairs in a fair and individually rational way. We ﬁrst propose a natural fairness concept that is applicable to both types of group formulations and design a polynomial-time algorithm that checks whether a matching exists that satisﬁes optimality, individual rationality, and fairness. We also present several running time upper bounds for computing such matchings for different graph structures.

1 Introduction Due to a shortage of organs harvested from deceased donors, living donations have become a signiﬁcant approach to saving the lives of patients who suffer from serious organ dysfunction. One issue with living donations is that the organs from willing donors may be medically incompatible with the intended patients. This problem can be partially overcome by organ exchange, which allows patients to swap their donors with others to obtain compatible organs [Roth et al., 2004]. Since transplant operations are usually conducted simultaneously, a ﬁxed upper bound is always imposed on the length of the exchange cycles. Pairwise organ exchange, which is the most common form in real-life, involves two pairs of patient and donor [Roth et al., 2005]. The design of organ exchange market has attracted considerable attention from both the economics and computer science ﬁelds [Abraham et al., 2007; Bertsimas et al., 2013; Dickerson et al., 2014; Hajaj et al., 2015; Dickerson and Sandholm, 2017; Dickerson et al., 2019; Ergin et al., 2020; Freedman et al., 2020]. In this paper, we study the organ exchange problem from a different perspective. We concentrate on a pairwise organ exchange market where all the patient-donor pairs are partitioned into disjoint groups. Dividing patient-donor pairs into groups is motivated by applications. Next we describe two

types of group formulations that have surfaced in recent literature. In the ﬁrst type, a group of agents represents a certain type of patient-donor pairs where patients are compatible with the same set of organs in the market. For instance, Dickerson et al. [2017] introduced a new model for kidney exchange that classiﬁes all participating patient-donor pairs into a ﬁxed number of types, based on a common set of attributes, e.g., blood type, tissue type, age, insurance, willingness to travel, etc. Ergin et al. [2017] studied the dual-donor organ exchange problem w.r.t. lung and liver exchanges. They consider a simpliﬁed model for theoretical analysis and grouped patientdonor pairs by blood types without taking tissue type or size compatibility into account. In the second type, each group represents a set of patientdonor pairs located in a certain area, formed geographically. For instance, each group can represent a set of patient-donor pairs in a certain hospital [Ashlagi et al., 2015]. Each group can also represent a state or territory in the national kidney exchange market, e.g. the Australian Organ and Tissue Authority [Mattei et al., 2017]. Or each group can represent a particular country in the European organ exchange program [Bir o et al., 2019]. Although dividing patient-donors into groups was previously proposed in the literature, scant attention was paid to the fair allocation of patient-donor pairs among groups. One exception [Bir o et al., 2019] considered core allocations, i.e., outcomes that cannot be improved upon by a coalition of agents. However, the core may be empty, and it is co-NPhard to check its existence. In contrast, we focus on the following research question: how can we design efﬁcient algorithms that match a maximum number of pairwise compatible patient-donor pairs in a fair and individual rational way? The contributions of this paper are summarized as follows. First, we propose a straightforward fairness concept for organ exchange among groups based on the notion of selection ratio, which provides the ﬂexibility to capture different ideas such as egalitarianism and proportionality. Second, we introduce a general polynomial-time algorithm that ﬁnds a matching that satisﬁes maximality, individual rationality, and fairness whenever it exists. Third, we provide several running time upper bounds of computing such matchings for different graph structures w.r.t. two forms of group formulations.

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

We consider a pairwise organ exchange problem by compatibility graph G = (V, E) where each vertex v V represents a patient-donor pair. We assume that for each vertex, the patient is incompatible with his donor, or they will conduct the transplant immediately rather than participating in the exchange program [Roth et al., 2007]. Edge set E is speciﬁed as follows. There is an edge between two vertices, i, j V , if the donor of pair i is compatible with the patient of pair j and the donor of pair j is compatible with the patient of pair i. Vertex set V is partitioned into k disjoint sets where each set Vi V represents a group of patient-donor pairs. Let P = {V1, , Vk} denote the partition of vertices, i.e., Vi Vj = for any i = j and S Vi P Vi = V . Depending on whether all vertices within the same group have the same set of neighbors, we consider two types of compatible graph structures that correspond to two types of group formulations. If all the vertices within the same group have the same set of neighbors, then we refer to such graphs as compatible graphs with identical neighbors. A matching M in G is a set of edges without common vertices, and a maximum matching is a matching that contains the largest possible number of edges. Let M denote the set of all possible matchings in G and let M denote the set of all maximum matchings in G. Given a matching M in G, let |Mi| denote the number of matched vertices from group Vi. For each group Vi, let max(Vi) = max M M |Mi| denote the maximum bound of matched vertices from group Vi among M , and let min(Vi) = min M M |Mi| denote the minimum bound of matched vertices from group Vi among M . Let G[Vi] denote a subgraph of G only induced by vertices from group Vi. Consider any maximum matching M

in subgraph G[Vi]. Let g min(Vi) = 2 |M | denote the modiﬁed minimum bound of group Vi, which equals twice the size of maximum matching M in G[Vi]. Note that the modiﬁed minimum bound of group Vi is the largest number of matched pairs from group Vi if only exchanges between vertices within group Vi are allowed. The modiﬁed minimum bound is critical to deﬁne individual rationality.

3 Desirable Properties

For our problem, an algorithm takes as input a compatibility graph G, and outputs a matching M as the outcome. Next we introduce three desirable properties that an outcome should satisfy. The ﬁrst property is optimality, which requires that a matching must maximize the number of exchanges among compatible patient-donor pairs.

Deﬁnition 1 (Optimality). Given a compatible graph G, a matching M in G satisﬁes optimality if M is a maximum matching in G.

The second property, individual rationality, requires that in an individually rational matching M, the number of matched pairs |Mi| of each group Vi not be less than its modiﬁed minimum bound g min(Vi). This property guarantees that each group Vi will receive at least the same number of matched pairs as that when group Vi conducts exchanges by itself.

V1 V2 V3 V4

# of matched pairs

Figure 1: Given a matching M, for each group Vi, colored region represents |Mi| δi and shaded region represents δi |Mi|. Height of each bar equals size |Vi| of each group.

Deﬁnition 2 (Individual Rationality). Given a compatibility graph G = (V, E) and a partition P of vertices V , a matching M in G satisﬁes individual rationality, if for each group Vi P, we have |Mi| g min(Vi).

Note that for compatible graphs with identical neighbors, individual rationality is trivially satisﬁed, because each group forms an independent set and the modiﬁed minimum bound is zero for each group. Next we introduce an important notion called selection ratio which is key to the deﬁnition of our third property fairness. Let δi and δi denote the upper and lower bounds for group Vi with δi δi. Intuitively, these two bounds represent two target quotas s.t. we expect the number of matched pairs from group Vi to fall within the range of these two bounds. Given a matching M, upper and lower bounds δi and δi, selection ratio α(|Mi|, δi, δi) of group Vi is represented as a fraction, where the numerator is the difference between the number of matched pairs |Mi| from Vi in matching M and the lower bound δi, and the denominator is the difference between upper bound δi and lower bound δi. Formally,

Deﬁnition 3 (Selection Ratio). Given a matching M in G, two quotas δi and δi with δi δi, selection ratio of group Vi w.r.t. δi and δi is

α(|Mi|, δi, δi) = |Mi| δi

δi δi for δi > δi.

When δi = δi, we assume α(|Mi|, δi, δi) = if |Mi| < δi and α(|Mi|, δi, δi) = if |Mi| δi.

Selection ratio measures to what extent the number of matched pairs |Mi| from group Vi surpasses lower bound δi on the scale of the lower bound to the upper bound, as shown in Figure 1. Note that it is ﬂexible to choose upper and lower bounds in the formula of a selection ratio, which allows us to capture different reasonable ideas, e.g., egalitarianism and proportionality. We discuss different choices of upper and lower bounds in Section 4. The third property, fairness among groups, requires that the minimum selection ratio among all the groups be maximized

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

among all matchings. This is a natural and uniﬁed fairness concept for different compatibility graph structures.

Deﬁnition 4 (Fairness among Groups). Given the set of all matchings M in G, a partition P of vertices V and two vectors of quotas δ = (δi)Vi P and δ = (δi)Vi P with δi δi for each group Vi P, a matching M in G is fair (among groups) w.r.t. δ and δ if it maximizes the minimal selection ratio among all groups:

M arg max M M min Vi P α(|M i|, δi, δi)

W.L.O.G, we assume that δi δi for each group Vi P for the rest of the paper.

4 Choice of Upper and Lower Bounds

In this section, we propose several choices of upper and lower bounds and assign different names to the corresponding selection ratios summarized in Table 1.

4.1 Egalitarianism

For each group Vi, if we set δi = |V | and δi = 0 , then the egalitarian-selection-ratio (Egalitarian) α( ) represents the ratio between the number of matched pairs |Mi| from group Vi and the total number of vertices |V |.

α(|Mi|, δi, δi) = |Mi| δi

δi δi = |Mi|

A fair matching w.r.t. Egalitarian tries to equalize the numbers of matched pairs among all groups. Note that another positive constant can be chosen as δi instead of |V |.

4.2 Proportional to Group Sizes (Group-Size)

For each group Vi, if we set δi = |Vi| and δi = 0, then the group-size-selection-ratio (Group-Size) α( ) represents the ratio between the number of matched pairs |Mi| from group Vi and its group size |Vi|.

α(|Mi|, δi, δi) = |Mi| δi

δi δi = |Mi|

A fair matching w.r.t. Group-Size tries to ensure that for each group, the number of matched pairs |Mi| from group Vi is proportional to its group size |Vi|.

4.3 Proportional to Maximum Bounds (Maximum)

For each group Vi, if we set δi = max(Vi) and δi = 0, then the maximum-bound-selection-ratio (Maximum) α( ) represents the ratio between the number of matched pairs |Mi| from group Vi and its maximum bound max(Vi).

α(|Mi|, δi, δi) = |Mi| δi

δi δi = |Mi| max(Vi)

A fair matching w.r.t. Maximum tries to ensure that for each group, the number of matched pairs |Mi| from group Vi is proportional to its maximum bound max(Vi).

Upper bound Lower bound Egalitarian |V | 0 Group-Size |Vi| 0 Maximum max(Vi) 0 Minimum min(Vi) + 1 0 Max-Min max(Vi) min(Vi) Max-M-Min max(Vi) g min(Vi)

Table 1: Different Choices of Upper and Lower Bounds

4.4 Proportional to Minimum Bounds (Minimum) For each group Vi, if we set δi = min(Vi)+1 and δi = 0, then the minimum-bound-selection-ratio (Minimum) α( ) represents the ratio between the number of matched pairs |Mi| from group Vi and its minimum bound min(Vi) plus 1.

α(|Mi|, δi, δi) = |Mi| δi

δi δi = |Mi| min(Vi) + 1

A fair matching w.r.t. Minimum tries to ensure that for each group, the number of matched pairs |Mi| from group Vi is proportional to its minimum bound min(Vi) plus 1. Note that we consider minimum bound min(Vi) plus 1 to avoid the case that min(Vi) = 0. Similarly, we can replace minimum bound min(Vi) by modiﬁed minimum bound g min(Vi).

4.5 Proportional to the Range of Maximum and Minimum Bounds (Max-Min) For each group Vi, if we set δi = max(Vi) and δi = min(Vi), then the maximum-minimum-selection-ratio (Max-Min) α( ) represents the ratio between the number of matched pairs |Mi| from group Vi minus its minimum bound and the difference between its maximum and minimum bounds.

α(|Mi|, δi, δi) = |Mi| δi

δi δi = |Mi| min(Vi) max(Vi) min(Vi)

A fair matching w.r.t. Max-Min tries to ensure that for each group Vi, the number of matched pairs |Mi| from group Vi minus its minimum bound is proportional to the difference between its maximum and minimum bounds.

4.6 Proportional to the Range of Maximum and Modiﬁed Minimum Bounds (Max-M-Min)

For each group Vi, if we set δi = max(Vi) and δi = g min(Vi), then the maximum-modiﬁed-minimum-selection-ratio (Max M-Min) α( ) represents the ratio between the number of matched pairs |Mi| from group Vi minus its minimum bound and the difference between its maximum and modiﬁed minimum bounds.

α(|Mi|, δi, δi) = |Mi| δi

δi δi = |Mi| g min(Vi)

max(Vi) g min(Vi)

A fair matching w.r.t. Max-M-Min tries to ensure that for each group, the number of matched pairs |Mi| from group Vi minus its modiﬁed minimum bound is proportional to the difference between its maximum and modiﬁed minimum bounds.

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

5 Compatibility between Optimality, Individual Rationality and Fairness

In this section, we discuss whether a matching always exists that satisﬁes optimality, individual rationality and fairness w.r.t. the different choices of upper and lower bounds in Table 1. The results are different for compatibility graphs with identical and different neighbors, as summarized in Theorem 1 and Theorem 2.

Theorem 1. For compatibility graphs with identical neighbors, a matching always exists that satisﬁes optimality, individual rationality, and fairness w.r.t. any choice of upper and lower bounds in Table 1.

Proof. Given a compatibility graph G with identical neighbors, let M denote any fair matching w.r.t. any choice of upper and lower bounds in Table 1. If M is not a maximum matching in G, by Berge s theorem [Berge, 1957], then an augmenting path p must exist w.r.t. M such that we can update M to be a new matching M p in which the edges from p \ M are added while those from M p are removed. Note that the vertices that are matched in M remain matched in new matching M p. Eventually we can obtain a maximum matching M by iteratively ﬁnding all augmenting paths w.r.t. M , and for each group Vi, the number of matched pairs |Mi| in M is at least as large as the number of matched pairs |M i| in M . Then the minimum selection ratio in matching M remains the same as in M ; otherwise M cannot be a fair matching. By the deﬁnition of fairness, the maximum matching M is also a fair matching. Next we show that matching M also satisﬁes individual rationality. Recall that we assume all patient-donor pairs in each vertex are incompatible, which indicates that there is no edge between two vertices from the same group. Thus for each group Vi, its modiﬁed minimum bound g min(Vi) is always 0. Then for any maximum matching M and for each group Vi, min(Vi) |Mi| max(Vi) holds. Since g min(Vi) = 0 min(Vi), then any maximum matching in G is also individually rational. This completes the proof.

Theorem 2. For compatibility graphs with different neighbors, a matching always exists that satisﬁes optimality, individual rationality and fairness w.r.t. Max-M-Min. Fairness w.r.t. any other choice of upper and lower bounds in Table 1 is incompatible with optimality and individual rationality.

Proof. Next we show that given a compatibility graph G with different neighbors, fairness w.r.t. Max-M-Min is compatible with optimality and individual rationality. Let M denote any fair matching w.r.t. Max-M-Min in G. If M is not a maximum matching, then we can update M to be a maximum matching as discussed in the proof for Theorem 1. For the sake of contradiction, suppose M does not satisfy individual rationality. Then there must exist a group Vi such that |Mi| < g min(Vi) and therefore its selection ratio α( ) is negative (including where g min(Vi) = max(Vi)). Now consider another matching M obtained as follows. For each group Vi, let Oi denote a maximum matching in subgraph G[Vi] only induced by vertices from group Vi. Match-

ing M = S Vi P Oi is the combination of each maximum matching Oi in each corresponding subgraph G[Vi]. Then for each group, |M i | = g min(Vi) holds, which satisﬁes individual rationality. However, this leads to a contradiction where matching M maximizes the minimal selection ratio among all the groups. Thus the assumption is wrong, and a maximum and fair matching w.r.t. Max-M-Min also satisﬁes individual rationality. We prove the second part of Theorem 2 by a counterexample in the Appendix due to space limitation.

6 Algorithm Design

In this section, we present a general algorithm that computes a matching that achieves optimality, individual rationality and fairness w.r.t. the different choices of upper and lower bounds in Table 1. The algorithm works for compatibility graphs with both identical and different neighbors and yields either a matching satisfying three properties whenever one exists or a NO-instance otherwise, as described in Algorithm 2.

6.1 Computing a Fair Matching Next we describe the ﬁrst step of Algorithm 2 that computes a fair matching w.r.t. some choice of upper and lower quotas in Table 1, as described in Algorithm 1. To develop a good intuition of how Algorithm 1 works, we postpone the following two technical details later: i) Some choices of upper and lower bounds require the maximum and minimum bounds of all groups. ii) Algorithm 1 iteratively invokes Algorithm Γ that solves the following problem of Matching with Quotas. Intuitively, Algorithm Γ checks whether a matching M exists s.t. for each group Vi, the number of matched pairs |Mi| is not smaller than some target quota λi. We design efﬁcient algorithms regarding these two issues in Section 7.

Matching with Quotas

Input: A compatibility graph G, a partition P of vertices V , a vector of targets λ = (λi)Vi P . Question: Whether a matching M in G exists s.t. for each Vi P, λi |Mi| holds.

The basic idea of Algorithm 1 is to apply a binary search to ﬁnd the maximal selection ratio α such that a matching exists where each group has a weakly larger selection ratio than α. Algorithm 1 takes as input a compatibility graph G, a vector of upper bounds δ = (δi)1 k and a vector of lower bounds δ = (δi)1 k. During the process of Algorithm 1, we track three variables, α, αℓ, and αu, representing the current, the lower, and the upper selection ratios respectively. In the initialization step, we set lower selection ratio αℓto 0 and set upper selection ratio αu to 1. For each group Vi, we initialize its target quota λi to 0. During each round of Algorithm 1, ﬁrst, compute current selection ratio α = (αℓ+ αu)/2. Then for each group Vi, calculate its target quota λi w.r.t. α, by rounding up value α (δi δi)+δi . Then we check whether a matching M exists s.t. for each group Vi, |Mi| λi holds through Algorithm Γ. If so, then update lower selection ratio αℓto be α to search for a larger selection ratio in the range

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

Algorithm 1 Computing a fair matching w.r.t. δ and δ

Input: G, δ = (δi)Vi P , δ = (δi)Vi P Output: a fair matching M w.r.t. δ and δ

1: Initialize a lower selection ratio αℓ= 0 and a upper selection ratio αu = 1 2: Initialize a target quota λi = 0 for each group Vi 3: while some target λi exists whose value is different from the last round do % including the initial round 4: Set current selection ratio α = (αℓ+ αu)/2 5: for each group Vi do 6: Compute target quota λi corresponding to α 7: λi α (δi δi) + δi 8: if a matching M in G exists s.t. for each Vi P, we have |Mi| λi then % Using Algorithm Γ 9: αℓ α % Search between α and αu 10: else 11: αu α % Search between αℓand α 12: return a matching M

[α, αu] in the next round; otherwise, update upper selection ratio αu to be α to search for a smaller selection ratio in the range [αℓ, α] in the next round. Repeat these procedures whenever some target λi exists whose value is different from the last round; otherwise Algorithm 2 terminates.

Theorem 3. Given a compatibility graph G and a choice of upper and lower bounds in Table 1, Algorithm 1 yields a fair matching in polynomial time.

6.2 Computing a Maximum, Individually Rational and Fair Matching Next we give a high-level description of Algorithm 2 that veriﬁes the existence of a matching that achieves optimality, individual rationality and fairness w.r.t. some choice of upper and lower bounds in Table 1. The input consists of a compatibility graph G and two vectors of quotas δ and δ. The ﬁrst step computes a fair matching M through Algorithm 1. We use α to denote the minimal selection ratio among all groups. The second step employs Algorithm Γ to check whether a fair and individually rational matching M exists s.t. for each group Vi, we have max( α (δi δi) + δi , g min(Vi)) |Mi|. In the ﬁnal step, if a fair and individually rational matching M exists, then we update M to be a maximum matching. Otherwise, no such matching exists.

Theorem 4. Given a compatibility graph and some choice of upper and lower bounds in Table 1, Algorithm 2 ﬁnds a matching that satisﬁes optimality, individual rationality and fairness whenever it exists in polynomial time.

7 Running Time Upper Bounds

This section is devoted to the two remaining technical details in Section 6: i) how to compute the maximum and minimum bounds for each group and ii) how to design Algorithm Γ. We present different polynomial-time algorithms for different compatibility graph structures and summarize all the results

Algorithm 2 Checking existence of a matching satisfying optimality, individual rationality, and fairness w.r.t. δ and δ

Input: G, δ = (δi)Vi P , δ = (δi)Vi P Output: a matching M that is maximum, individually rational and fair w.r.t. δ and δ

1: Compute a fair matching M in G w.r.t. δ and δ and let α denote the minimal selection ratio among all groups % using Algorithm 1 2: if a matching M exists s.t. for each group Vi, we have max( α (δi δi) + δi , g min(Vi)) |Mi| % using Algorithm Γ then 3: Update M to be a maximum matching. 4: return matching M 5: else 6: return NO-instance

on running time upper bounds in Table 2. Detailed proofs are presented in the Appendix. Note that given a compatible graph with identical neighbors G = (V, E) with a partition P of vertices V , we can create an equivalent and compact graph G = (V , E ) in which each node Vi V represents a group with capacity b(Vi) = |Vi|, i.e., the size of group Vi. We can construct such a compact representation graph G in polynomial time and assume the input for any compatibility graph with identical neighbors is its compact representation. The details of constructing compact graphs are presented in the Appendix.

7.1 Bipartite Graphs with Identical Neighbors First, we consider the simplest model, bipartite compatibility graphs with identical neighbors in which all groups form a bipartite graph and all vertices within each group have identical neighbors [Ergin et al., 2017].

Theorem 5. Given a bipartite compatibility graph with identical neighbors, the maximum bounds of all groups can be computed in time O(k2) where k is the number of groups.

Proof. (Sketch) Let NG(Vi) denote all neighboring vertices of some vertex from group Vi in G. For each group Vi, its maximum bound max(Vi) equals min(|Vi|, |NG(Vi)|) and we can calculate the total number of its neighboring vertices in O(k). Thus the total running time is O(k2).

Theorem 6. Given a bipartite compatibility graph with identical neighbors, the minimum bounds of all groups can be computed in time O(k3.5) where k is the number of groups.

Identical Identical Different Bipartite Non-bipartite Non-bipartite Maximum O(k2) O(k2) O(|V | |E|) Minimum O(k3.5) O(|V | |E|) O(|V | |E|) Algorithm Γ O(k3) O(k4 log k) O( p

Table 2: Running time upper bounds where k, |V |, and |E| represent numbers of groups, vertices, and edges in G

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

Proof. (Sketch) Let M denote a maximum matching in G and let M denote a maximum matching in subgraph G[V \ Vi] induced from all groups excluding group Vi. For each group Vi, its minimum bound min(Vi) is |M| |M |. Note that we can compute a maximum matching in bipartite compact graph G of G by the Hopcroft Karp algorithm in time O(k2.5) [Hopcroft and Karp, 1973]. Thus the total running time for computing all minimum bounds is O(k3.5).

Theorem 7. Given a bipartite compatibility graph G with identical neighbors and a vector of quotas λ = (λi)Vi P where each element λi corresponds to one group Vi, checking whether a matching M in G exists s.t. λi |Mi| holds for each group Vi can be done in time O(k3) where k is the number of groups.

Proof. (Sketch) We prove Theorem 7 by converting the problem of checking whether a matching M in G exists s.t. for each group Vi, λi |Mi| holds into an equivalent network ﬂow problem with edge capacities in polynomial time, which then can be solved in time O(k3) [Malhotra et al., 1978].

7.2 Non-bipartite Graphs with Identical Neighbors Next we consider non-bipartite compatibility graphs with identical neighbors in which all vertices within each group have identical neighbors [Dickerson et al., 2017].

Theorem 8. Given a non-bipartite compatibility graph with identical neighbors, the maximum bounds of all groups can be computed in time O(k2) where k is the number of groups.

Proof. (Sketch) The same proof for Theorem 5 works.

Theorem 9. Given a non-bipartite compatibility graph G = (V, E) with identical neighbors, the minimum bounds of all groups can be computed in time O(|V | |E|) where |V | and |E| denote the numbers of vertices and edges in G.

Proof. (Sketch) Consider any maximum matching M in G. If an alternating path p exists that starts from some unmatched vertex u V \ Vi and ends at some matched vertex v Vi w.r.t. M, then update M to be M p by taking their symmetric difference. Repeat this procedure until there is no such alternating path w.r.t. M, and the minimum bound of group Vi is |Mi|. For each group Vi, we can compute its minimum bound in time O(|Vi| |E|). The total running time of computing all minimum bounds is O(|V | |E|).

Theorem 10. Given a non-bipartite compatibility graph G with identical neighbors and a vector of quotas λ = (λi)Vi P where each element λi corresponds to one group Vi, checking whether a matching M in G exists s.t. λi |Mi| holds for each group Vi can be done in time O(k4 log k) where k is the number of groups.

Proof. (Sketch) We prove Theorem 10 by converting the problem of checking whether a matching M in G exists s.t. for each group Vi, λi |Mi| holds into an equivalent bmatching problem in polynomial time, which then can be solved in time O(k4 log k) [Anstee, 1987].

7.3 Compatible Graphs with Different Neighbors Next we consider compatibility graphs with different neighbors where vertices from the same group may have different neighbors [Mattei et al., 2017; Bir o et al., 2019].

Theorem 11. Given a compatibility graph G = (V, E) with different neighbors, the maximum bounds of all groups can be computed in time O(|V | |E|).

Proof. (Sketch) We use almost the same proof as that for Theorem 9. The main difference is that for computing the maximum bound, we continue to seek an alternating path p that starts from some unmatched vertex v Vi and ends at some matched vertex u V \Vi w.r.t. M. Thus they have the same running time O(|V | |E|).

Theorem 12. Given a compatibility graph G = (V, E) with different neighbors, the minimum bounds of all groups can be computed in time O(|V | |E|).

Proof. (Sketch) The same proof for Theorem 9 works.

Theorem 13. Given a compatibility graph G with different neighbors and a vector of quotas λ = (λi)Vi P where each element λi corresponds to one group Vi, checking whether a matching M in G exists s.t. λi |Mi| holds for each group Vi can be done in time O( p

Proof. (Sketch) Create a new graph G by extending G = (V, E) as follows. For each group Vi, add a new set of |Vi| λi vertices, denoted by V i . Each newly added vertex v i V i is incident to all vertices of Vi. All newly added vertices S Vi P V i are incident to each other. If the total number of vertices is odd, then add one more vertex v that is incident to all newly added vertices S Vi P V i . There exists a matching M in G s.t. λi |Mi| holds for each group Vi if and only if induced graph G has a perfect matching M . We can check whether G admits a perfect matching by computing a maximum matching in time O( p

|V | |E |) [Micali and Vazirani, 1980] where |V | and |E | are linear in the numbers of |V | and |E|.

8 Conclusion

We studied the pairwise organ exchange problem among groups motivated by real-world organ allocation markets. We proposed a new and straightforward fairness concept and introduced a general polynomial-time algorithm that computes a matching that satisﬁes three desirable properties including optimality, individual rationality, and fairness. An interesting future direction is how to design a fair and efﬁcient algorithm for exchange among groups by relaxing the assumption of pairwise exchanges.

Acknowledgements

The authors appreciate Haris Aziz and Serge Gaspers for their constructive comments. This work is partially supported by JSPS KAKENHI Grant Numbers JP20H00587. Toby Walsh is supported by the Australian Research Council via a Laureate Fellowship FL200100204.

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

References [Abraham et al., 2007] D. J. Abraham, A. Blum, and T. Sandholm. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM conference on Electronic commerce, pages 295 304, 2007. [Anstee, 1987] R. P. Anstee. A polynomial algorithm for bmatchings: an alternative approach. Information Processing Letters, 24(3):153 157, 1987. [Ashlagi et al., 2015] I. Ashlagi, F. Fischer, I. A. Kash, and A. D. Procaccia. Mix and match: A strategyproof mechanism for multi-hospital kidney exchange. Games and Economic Behavior, 91:284 296, 2015. [Berge, 1957] C. Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 43(9):842, 1957. [Bertsimas et al., 2013] D. Bertsimas, V. F. Farias, and N. Trichakis. Fairness, efﬁciency, and ﬂexibility in organ allocation for kidney transplantation. Operations Research, 61(1):73 87, 2013. [Bir o et al., 2019] P. Bir o, W. Kern, D. P alv olgyi, and D. Paulusma. Generalized matching games for international kidney exchange. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 413 421, 2019. [Dickerson and Sandholm, 2017] J. P. Dickerson and T. Sandholm. Multi-organ exchange. Journal of Artiﬁcial Intelligence Research, 60:639 679, 2017. [Dickerson et al., 2014] J. P. Dickerson, A. D. Procaccia, and T. Sandholm. Price of fairness in kidney exchange. Transplantation, 98:815, 2014. [Dickerson et al., 2017] J. P. Dickerson, A. M. Kazachkov, A. D. Procaccia, and T. Sandholm. Small representations of big kidney exchange graphs. In Proceedings of the 31st International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 487 493, 2017. [Dickerson et al., 2019] J. P. Dickerson, A. D. Procaccia, and T. Sandholm. Failure-aware kidney exchange. Management Science, 65(4):1768 1791, 2019. [Ergin et al., 2017] H. Ergin, T. S onmez, and M. U. Unver. Dual-donor organ exchange. Econometrica, 85(5):1645 1671, 2017. [Ergin et al., 2020] H. Ergin, T. S onmez, and M. U. Unver. Efﬁcient and incentive-compatible liver exchange. Econometrica, 88(3):965 1005, 2020. [Freedman et al., 2020] R. B. Freedman, S. Jana, W. Sinnott Armstrong, J. P. Dickerson, and V. Conitzer. Adapting a kidney exchange algorithm to align with human values. Artiﬁcial Intelligence, page 103261, 2020. [Hajaj et al., 2015] C. Hajaj, J. P. Dickerson, A. Hassidim, T. Sandholm, and D. Sarne. Strategy-proof and efﬁcient kidney exchange using a credit mechanism. In Twenty Ninth AAAI conference on artiﬁcial intelligence, pages 921 928, 2015.

[Hopcroft and Karp, 1973] J. E. Hopcroft and R. M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225 231, 1973. [Malhotra et al., 1978] V. M. Malhotra, M. P. Kumar, and S. N. Maheshwari. An O(|V |3) algorithm for ﬁnding maximum ﬂows in networks. Information Processing Letters, 7(6):277 278, 1978. [Mattei et al., 2017] N. Mattei, A. Safﬁdine, and T. Walsh. Mechanisms for online organ matching. In Carles Sierra, editor, Proceedings of the 29st International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 345 351, 2017. [Micali and Vazirani, 1980] S. Micali and V. V. Vazirani. An O( p

|V ||E|) algoithm for ﬁnding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 17 27. IEEE, 1980. [Roth et al., 2004] A. E. Roth, T. S onmez, and M. U. Unver. Kidney exchange. The Quarterly journal of economics, 119(2):457 488, 2004. [Roth et al., 2005] A. E. Roth, T. S onmez, and M. U. Unver. Pairwise kidney exchange. Journal of Economic theory, 125(2):151 188, 2005. [Roth et al., 2007] A. E. Roth, T. S onmez, and M. U. Unver. Efﬁcient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. American Economic Review, 97(3):828 851, 2007.

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