Mechanism Design and Implementation for Lung Exchange

Suiqian Luo, Pingzhong TangIJCAI 2015 · OpenReview

Abstract

We explore the mechanism design problem for lung exchange and its implementation in practice. We prove that determining whether there exists a non-trivial solution of the lung exchange problem is NP-complete. We propose a mechanism that is individually rational, strategy-proof and maximizes exchange size. To implement this mechanism in practice, we propose an algorithm based on Integer Linear Program and another based on search. Both of our algorithms for this mechanism yield excellent performances in simulated data sets.

The Lung Exchange Problem

Organ exchange is a "barter" system where a patient with an incompatible donor swaps with another pair in the same predicament. While kidney exchange (one donor, one patient) is common, lung exchange is far more complex. A healthy human has five lung lobes; a patient with lung disease needs two donors to each contribute one lower lobe.

Figure 1: A conceptual diagram of a lung exchange involving three patient-donor triplets (X, Y, Z). Each patient requires two compatible donors simultaneously.

This creates a "triplet" requirement: one patient plus two donors. Because all three surgeries must happen simultaneously to prevent donors from withdrawing after their patient has received an organ, the logistical and mathematical complexity is significantly higher than in kidney exchange.

Complexity and Mechanism Design

The authors prove that even deciding if a non-trivial lung exchange exists is NP-complete by reducing it from the 3D-Matching problem. This is a significant finding because the same problem for kidneys is solvable in polynomial time. The shift from matching pairs to matching hyper-edges (triplets) is what moves the problem into the NP-hard domain.

Figure 3: Illustration of the triplet structure used in the complexity proof, reducing the 3D-Matching problem to the lung exchange problem.

To address this, the paper proposes the Maximum Lexicographical Mechanism. This mechanism first maximizes the total number of transplants. To break ties and ensure strategy-proofness—preventing patients from "gaming the system" by hiding compatible donors—it uses a fixed priority (lexicographical order) among patients. This ensures that a patient’s best move is always to report their true set of compatible donors.

Algorithmic Solutions

Since the problem is NP-hard, the authors propose two practical ways to solve it:

  1. Integer Linear Programming (ILP): A standard optimization approach using the CPLEX solver.
  2. Custom Search Algorithm: A depth-first search using "branch and bound." It uses the Kuhn-Munkres algorithm to calculate upper bounds on exchange sizes to prune the search tree efficiently.

Key Results and Insights

Because lung exchange has not yet been practiced at scale, the authors tested their methods on simulated datasets based on US blood type distributions and realistic patient profiles.

  • Efficiency: For smaller instances ($n=50$), the search algorithm is nearly instantaneous.
  • Search vs. ILP: In more than half of the test cases, the custom search algorithm was significantly faster than the ILP solver. However, the ILP approach was more "stable," finishing all test cases within the time limit, whereas the search algorithm failed on a small percentage of the largest, most complex cases ($n=200$).
  • Pruning Heuristics: The search algorithm's success relies on identifying patients who cannot be matched early and prioritizing branching on the most constrained patients.

Conclusion

This work provides a theoretical and practical framework for lung exchange. By establishing the complexity of the problem and proposing a strategy-proof mechanism with efficient algorithms, the authors lay the groundwork for life-saving clinical implementations. Future work will focus on adapting these mechanisms for dynamic environments where patients and donors arrive over time.

Summary updated

Abstract

We explore the mechanism design problem for lung exchange and its implementation in practice. We prove that determining whether there exists a non-trivial solution of the lung exchange problem is NP-complete. We propose a mechanism that is individually rational, strategy-proof and maximizes exchange size. To implement this mechanism in practice, we propose an algorithm based on Integer Linear Program and another based on search. Both of our algorithms for this mechanism yield excellent performances in simulated data sets.
BibTeX
@inproceedings{luo2015mechanism,
  author = {Suiqian Luo and Pingzhong Tang},
  title = {{Mechanism Design and Implementation for Lung Exchange}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=H1VpcQG_ZB},
}
Figure