Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges
The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
In barter-exchange markets, agents seek to swap their items with one another, in order to improve their own utilities. These swaps consist of cycles of agents, with each agent receiving the item of the next agent in the cycle. We focus mainly on the upcoming national kidney-exchange market, where patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. With over 70,000 patients already waiting for a cadaver kidney in the US, this market is seen as the only ethical way to significantly reduce the 4,000 deaths per year attributed to kidney diseas.The clearing problem involves finding a social welfare maximizing exchange when the maximum length of a cycle is fixed. Long cycles are forbidden, since, for incentive reasons, all transplants in a cycle must be performed simultaneously. Also, in barter-exchanges generally, more agents are affected if one drops out of a longer cycle. We prove that the clearing problem with this cycle-length constraint is NP-hard. Solving it exactly is one of the main challenges in establishing a national kidney exchange.We present the first algorithm capable of clearing these markets on a nationwide scale. The key is incremental problem formulation. We adapt two paradigms for the task: constraint generation and column generation. For each, we develop techniques that dramatically improve both runtime and memory usage. We conclude that column generation scales drastically better than constraint generation. Our algorithm also supports several generalizations, as demanded by real-world kidney exchanges.Our algorithm replaced CPLEX as the clearing algorithm of the Alliance for Paired Donation, one of the leading kidney exchanges. The match runs are conducted every two weeks and transplants based on our optimizations have already been conducted.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738 · cited 1×
“We also experimented with the A* node selection order [7, 2].”
MethodBranch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219 · cited 2×
“We can even find cycles with the most positive price, which are the ones most likely to improve the objective value of restricted LP [1].”
BackgroundGeneralized best-first search strategies and the optimality of A*
Dechter, R., & Pearl, J. (1985) · Journal of the ACM · doi:10.1145/3828.3830 · Cited by 1,071
Solving Airline Crew Scheduling Problems by Branch-and-Cut
Hoffman, K. L., & Padberg, M. (1993) · Management Science · doi:10.1287/mnsc.39.6.657 · Cited by 537
Kidney Paired Donation and Optimizing the Use of Live Donor Organs
Segev, D. L. (2005) · JAMA · doi:10.1001/jama.293.15.1883 · Cited by 442
Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences
Roth, A. E., Sönmez, T., & Ünver, M. U. (2007) · American Economic Review · doi:10.1257/aer.97.3.828 · Cited by 392
A Kidney Exchange Clearinghouse in New England
Roth, A. E., Sönmez, T., & Ünver, M. U. (2005) · American Economic Review · doi:10.1257/000282805774669989 · Cited by 279
Increasing the Opportunity of Live Kidney Donation by Matching for Two- and Three-Way Exchanges
Saidman, S. L., Roth, A. E., Sönmez, T., Ünver, M. U., & Delmonico, F. L. (2006) · Transplantation · doi:10.1097/01.tp.0000195775.77081.25 · Cited by 263
ÜNVER, M. U. (2009) · Review of Economic Studies · doi:10.1111/j.1467-937x.2009.00575.x · Cited by 213
A Comparison of Populations Served by Kidney Paired Donation and List Paired Donation
Gentry, S. E., Segev, D. L., & Montgomery, R. A. (2005) · American Journal of Transplantation · doi:10.1111/j.1600-6143.2005.00964.x · Cited by 100
Optimal Winner Determination Algorithms
Sandholm, T. (2005) · The MIT Press eBooks · doi:10.7551/mitpress/9780262033428.003.0015 · Cited by 86
Self-citation
Cited by
Computational thinking and thinking about computing
Wing, J. M. (2008) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2008.0118 · Cited by 1,784
“Computational thinking is transforming economics, spawning a new field of computational microeconomics, with applications such as advertisement placement, online auctions, reputation services and even finding optimal donors for n -way kidney exchange (Abraham et al .”
BackgroundAlgorithmics of Matching Under Preferences
Manlove, D. F. (2013) · Series on Theoretical Computer Science · doi:10.1142/8591 · Cited by 515
Herlihy, M. (2018) · Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing · doi:10.1145/3212734.3212736 · Cited by 506
Computational thinking and thinking about computing
Wing, J. (2008) · 2008 IEEE International Symposium on Parallel and Distributed Processing · doi:10.1109/ipdps.2008.4536091 · Cited by 415
Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions
Roth, A. (2007) · National Bureau of Economic Research · doi:10.3386/w13225 · Cited by 392
Metadata
- Authors
- Abraham, D. J., Blum, A., & Sandholm, T.
- Venue
- Proceedings of the 8th ACM conference on Electronic commerce
- Publisher
- ACM
- Published
- 2007-06-11
- Pages
- 295-304
- OpenAlex
- W2014511571
- Cited by
- 280
- References
- 12
- FWCI
- 60.75
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.