新英格兰肾脏交换计划：为不相容的捐赠组合寻找匹配

2003年，大约6万美国人在等待肾脏；当年只有8665例死者捐赠移植，3436人在等待中死亡。活体捐赠可以填补部分缺口——健康人有两颗肾脏，可以靠一颗生活——但意愿捐赠者往往与所爱患者血型或组织不匹配，而法律禁止金钱交易：在移植医学受监管的任何地方，买卖器官都是非法的。

少数医院已经开始在两个不兼容配对之间交换肾脏——我的不匹配捐赠者捐给你的患者，你的捐给我们的——约翰·霍普金斯甚至成功进行了三向交换。但截至2004年12月，新英格兰14个移植中心总共只发生了5例这样的交换，因为没有人建立不配对数据库来进行匹配；未匹配的捐赠者只能回家。

将每个不兼容的配对视为匹配市场中的一个节点，然后搜索循环和链，使不匹配相互抵消，把稀缺转化为分配问题。

每个不兼容配对都是一个节点，而不是失败，因此不匹配可以相互抵消。

登记系统让算法能够同时找到所有配对中的循环和链。

由利他捐赠者发起的非同步链消除了同时手术的需要。

移植数量随池规模增长，而非肾脏供应增加，因此短缺成为分配问题。

当直接交换受阻时，建立一个清算所，匹配多方之间的互补性不匹配。

数千例原本不可能进行的移植得以实现；2012年诺贝尔经济学奖引用了这项工作。