Fair Pairwise Exchange among Groups

1 Introduction

Due to a shortage of organs harvested from deceased donors, living donations have become a significant 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 fixed 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 fields [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 first 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 classifies all participating patient-donor pairs into a fixed 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 simplified 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 efficient 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 flexibility to capture different ideas such as egalitarianism and proportionality. Second, we introduce a general polynomial-time algorithm that finds a matching that satisfies 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.

2 Model

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 specified 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 ⋃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) = maxM∈M∗ |Mi| denote the maximum bound of matched vertices from group Vi among M∗ , and let min(Vi) = minM∈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 ˜ min(Vi) = 2 · |M ′ | denote the modified minimum bound of group Vi, which equals twice the size of maximum matching M ′ in G[Vi]. Note that the modified 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 modified minimum bound is critical to define 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 first property is optimality, which requires that a matching must maximize the number of exchanges among compatible patient-donor pairs.

Definition 1 (Optimality). Given a compatible graph G, a matching M in G satisfies 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 modified minimum bound ˜ 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.

Definition 2 (Individual Rationality). Given a compatibility graph G = (V, E) and a partition P of vertices V , a matching M in G satisfies individual rationality, if for each group Vi ∈ P , we have |Mi| ≥ ˜ min(Vi).

Note that for compatible graphs with identical neighbors, individual rationality is trivially satisfied, because each group forms an independent set and the modified minimum bound is zero for each group.

Next we introduce an important notion called selection ratio which is key to the definition 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,

Definition 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

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 flexible 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 among all matchings. This is a natural and unified fairness concept for different compatibility graph structures.

Definition 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:

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

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

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 toMaximumBounds (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).

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

4.4 Proportional toMinimumBounds (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.

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 modified minimum bound ˜ min(Vi).

4.5 Proportional to the Range of Maximum and MinimumBounds (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.

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 ModifiedMinimumBounds (Max-M-Min)

For each group Vi, if we set δi = max(Vi) and δi = ˜ min(Vi), then the maximum-modified-minimum-selection-ratio (MaxM-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 modified minimum bounds.

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 modified minimum bound is proportional to the difference between its maximum and modified minimum bounds.

5 Compatibility between Optimality, Individual Rationality and Fairness

In this section, we discuss whether a matching always exists that satisfies 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 satisfies 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 fromM ′ ∩p are removed. Note that the vertices that are matched inM ′ remain matched in new matching M ′ ⊕ p. Eventually we can obtain a maximum matching M by iteratively finding 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 definition of fairness, the maximummatching M is also a fair matching.

Next we show that matching M also satisfies 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 modified minimum bound ˜ min(Vi) is always 0. Then for any maximum matching M ′ and for each group Vi, min(Vi) ≤ |Mi| ≤ max(Vi) holds. Since ˜ 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 satisfies 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| < ˜ min(Vi) and therefore its selection ratio α(·) is negative (including where ˜ 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. Matching M ∗ = ⋃Vi∈P Oi is the combination of each maximum matching Oi in each corresponding subgraph G[Vi]. Then for each group, |M ∗ i | = ˜ min(Vi) holds, which satisfies 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 satisfies individual rationality.

We prove the second part of Theorem 2 by a counterexample in the Appendix due to space limitation.

6 AlgorithmDesign

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 first 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 efficient 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 find 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, first, 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 Algorithm 1 Computing a fair matching w.r.t. δ and δ

Input: G, δ = (δi)Vi∈P , δ = (δi )Vi∈P

Output: a fair matchingM 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 matchingM

[α, α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 aMaximum, Individually Rational and Fair Matching

Next we give a high-level description of Algorithm 2 that verifies 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 first 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 ⌉, ˜ min(Vi)) ≤ |Mi|. In the final 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 finds a matching that satisfies 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 matchingM that is maximum, individually rational and fair w.r.t. δ and δ

• 1: Compute a fair matchingM ′ in Gw.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 ⌉, ˜ min(Vi)) ≤ |Mi| % using Algorithm Γ then
• 3: Update M to be a maximummatching.
• 4: return matchingM
• 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 ).

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

Proof. (Sketch) LetM denote amaximummatching inGand 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 Theorem7 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 flow 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 anymaximummatchingM inG. 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(√|V | · |E|).

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 ⋃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 ⋃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(√|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 satisfies three desirable properties including optimality, individual rationality, and fairness. An interesting future direction is how to design a fair and efficient 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.