Analysing and optimising kidney paired donation

该项目属于EPSRC业务研究研究领域。运筹学已经改变了许多市场运作的方式。其中一个例子是肾脏配对捐赠（KPD），这是一种促进终末期肾病患者肾脏移植的新机制。有一个自愿但不相容的供体（如朋友或家人）的患者作为一对加入KPD市场，并与其他这样的配对交换肾脏。KPD项目已在世界上许多国家建立，包括韩国、美国和英国。到目前为止，KPD已经为数千名患者带来了新的生命机会。此外，进行的成本分析表明，仅在美国，KPD项目每年就可以节省至少7.5亿美元。在其他有KPD规划的国家也可以预期类似的结果。此外，对KPD的研究可以使市场理论和运筹学的其他领域受益，因为肾脏市场可以被视为易货市场的例子，代理人（患者-供体对）进入市场，目的是交换物品（不兼容的肾脏）以换取另一件物品（兼容的肾脏）。最初，KPD计划只允许在贪婪的基础上临时分配的双向交换。然而，不久之后，这些项目开始与计算机科学、经济学和数学领域的研究人员合作。因此，大量关于KPD的学术文献已经出现，利用复杂的数学建模和优化技术来确定理想的器官分配程序。如今，节目中最主要的方法是每隔一段时间对市场进行快照。对于每个快照，使用整数线性规划技术或图理论算法来确定最优的器官分配，服从于所讨论的程序定义的最优性标准。如今，项目通常超越了双向交换，允许多对夫妇交换肾脏，这样每对捐赠的夫妇也能得到一个器官。此外，一些项目还允许所谓的利他捐赠者开始多米诺骨牌式捐赠。该项目的目的是寻求一种新的方法来解决KPD匹配问题，有望产生更好的结果。Akbarpour， Li和Gharan在一篇工作论文中引入了一个模型，明确说明了代理人随机加入和退出市场的事实，而不是将市场视为一系列快照或离线问题。此外，他们还做出了一个貌似合理的假设，即中央市场计划者对代理人何时离开有短期的了解。{据我们所知，没有其他论文以这种方式对KPD进行建模。动态市场本身比静态或离线市场的分析要复杂得多，因此需要使用概率论中的各种工具，以使动态算法的分析易于处理。虽然Akbarpour等人的论文提出了一个强有力的启发式案例，支持对KPD采用动态算法，但将此类市场视为真正的动态问题仍处于起步阶段，需要进一步的工作来确定当前的初步结果是否可以转化为实践中的可行算法。作为对这些问题的结结性回答的一部分，我们计划实现一个现实的市场模拟，允许我们直接比较各种离线和动态算法在模拟当前市场情况的历史数据集上运行时的性能。总之，我们相信KPD的动态方法有望开发出改进的器官分配程序，从而挽救更多的生命，并在医疗保健方面节省更多的成本。

This project falls within the EPSRC Operational Research research area. Operational Research has transformed the way many markets have been conducted. One such example is Kidney Paired Donation (KPD), a novel mechanism that facilitates kidney transplantations for patients suffering from end stage kidney disease. Patients with a willing but incompatible donor (e.g.a friend or family member) join a KPD market as a pair and exchange kidneys with other such pairs. KPD programmes have been established in many countries around the world, including South Korea, the US and the UK.So far, KPD has already given thousands of patients a new chance at life. In addition, cost analysis conducted suggests that KPD programmes in the US alone could save at least $750 million yearly. Similar results can be expected in other countries with KPD programmes. Furthermore, research on KPD can benefit other areas of market theory and operational research, as kidney markets can be viewed as examples of barter markets where agents (patient-donor pairs) enter a market with the aim of swapping items (the incompatible kidney) for another item (a compatible kidney).Initially, KPD programmes only allowed for two-way exchanges that were allocated ad-hoc on a greedy basis. Soon after, however, programmes started collaborating with researchers from computer science, economics and mathematics. As a result, a significant body of academic literature on KPD has emerged that utilises sophisticated mathematical modelling and optimisation techniques to determine desirable organ allocation procedures. The predominant approach among programmes today is to take snapshots of the market at regular time intervals. For each snapshot, integer linear programming techniques or graph-theoretical algorithms are used to determine optimal organ assignments, subject to optimality criteria defined by the programme in question. Nowadays, programmes commonly go beyond two-way exchanges, allowing multiple pairs to exchange kidneys in such a way that every pair that donates also receives an organ. In addition, some programmes also allow so-called altruistic donors to start off domino-chain donations.The aim of this project is to pursue a novel approach to the KPD matching problem that promises to yield significantly better results. Instead of approaching the market as a series of snapshot or offline problems, Akbarpour, Li and Gharan in a working paper introduce a model that explicitly accounts for the fact that agents join and leave the market stochastically. In addition, they make the plausible assumption that the central market planner has short-term knowledge of when agents are about to depart. footnote{To the best of our knowledge, no other paper models KPD in this way.} Dynamic markets are inherently more complex to analyse than their static or offline counterparts, necessitating the use of various tools from probability theory to make the analysis of dynamic algorithms tractable. While the paper by Akbarpour et al.~makes a strong heuristic case in favour of adopting dynamic algorithms for KPD, treatment of such markets as a bona-fide dynamic problem is still in its infancy and much further work is needed to establish whether the current preliminary results translate to viable algorithms in practice. As part of a conclusive answer to these questions, we plan to implement a realistic market simulation that allows us directly compare the performance of various offline and dynamic algorithms when run on historical datasets that mimic the current market situation. In conclusion, we believe that a dynamic approach to KPD promises to develop improved organ allocation procedures that will save more lives and effect greater cost savings in healthcare.