Introduction to Algorithms and their Limitations (CS 120) – Fall 2022

Module Topic: Matching Algorithms for Ethical Organ Distribution
Module Author: Megan Entwistle

Course Level: Upper-level undergraduate
AY: 2022-2023

Course Description: “An introductory course in theoretical computer science, aimed at giving students the power of using mathematical abstraction and rigorous proof to understand computation. Thus equipped, students will be able to design and use algorithms that apply to a wide variety of computational problems, with confidence about their correctness and efficiency, as well as recognize when a problem may have no algorithmic solution. At the same time, they will gain an appreciation for the beautiful mathematical theory of computation that is independent of (indeed, predates) the technology on which it is implemented.” (Course website)

Semesters Taught: Fall 2022, Fall 2023

    Tags

Module Overview

The module introduces two distinct ethical approaches for allocating kidneys to patients on a maximum matching scheme. Students consider whether donor-patient matches should be guided by considerations of expected outcomes or by considerations of patient need, and whether there are prospects for an algorithmic solution that can incorporate both kinds of concern.

    Connection to Course Technical Material

This module took place at the end of a unit on graph theory, during which students were introduced to maximum matching algorithms: solving for the greatest number of matches (edges) between two sets of individuals (vertices). Maximum matching algorithms have various applications: e.g. matching rideshare passengers to drivers; matching medical residents to hospitals; matching living kidney donors to patients in need of a transplant. Prior to the module, the professors introduced the graph theory behind matching algorithms in the context of the US kidney exchange, and students practiced solving for greatest total matches in simplified cases (in which the only relevant constraints were (i) numbers of donors and patients, and (ii) blood-type compatibilities between individuals of either group). This set the stage for the module, which begins with a simple demonstration that under conditions of donor scarcity, there will typically be more than one way to maximize matches (based on compatibility considerations alone). In reality, further considerations such as urgency of need, or projected future life years of the patient following the transplant, need to be incorporated into a matching decision procedure. The two main candidate decision procedures we discuss are backed by competing ethical theories, and are abstractable into formal algorithms that students would encounter in more advanced CS courses.

Goals

    Module Goals

1. Get students to recognize that maximum matching algorithms for matching donors to patients, under current conditions of donor scarcity, leave open a further ethical question of which patients to prioritize.
2. Highlight some ethically relevant factors for decisions about medical resource allocation, in the context of the kidney exchange.
3. Introduce students to an outcomes-based approach (e.g. Utilitarianism), and have them practice applying the corresponding decision procedure (Maximization) to kidney exchange cases.
4. Introduce students to a needs-based approach (e.g. Rawls), and have them practice applying the corresponding decision procedure (Maximin) to kidney exchange cases.
5. Enable students to identify potential problems with either approach, and to articulate which decision procedure they think yields the better ethical verdicts.
6. Sketch an alternative solution (Prioritarianism) that accommodates the core intuitions of both approaches.

    Key Philosophical Questions

1. What ethical considerations should guide our decisions about scarce resource allocation?
2. Under a maximum matching scheme for kidney transplants, which patients ought to be prioritized?
3. What is the core ethical intuition behind the maximization decision procedure, and what are some reasons to think this procedure is unfair?
4. What is the core ethical intuition behind the maximin decision principle, and in what kinds of cases might it deliver the wrong verdict?
5. Is it ethically better, in the context of the kidney exchange, to maximize total life years gained for patients or to help the worst-off?
6. What would a decision procedure look like that is sensitive to both scale (like maximization) and starting points (like maximin)?

Materials

    Key Philosophical Concepts

• Scarce resource problem
• Welfare maximization
• Fairness
• Maximin
• QALY (quality-adjusted life years)
• Prioritarianism

Assigned Readings

None

Implementation

Class Agenda

1. Motivate the central question: given the scarcity of donors, which patients ought to be prioritized under a maximum matching scheme?
2. Identify some ethically relevant factors for decisions about allocating scarce resources.
3. Introduce an outcomes-based approach (Utilitarian ethical theory/principle of Maximization), apply it to the case, and discuss potential problems.
4. Introduce a needs-based approach (Rawlsian fairness/principle of Maximin), apply it to the case, and discuss potential problems.
5. Weigh the pros and cons of each approach.
6. Briefly consider a middle way (Prioritarianism).

    Sample Class Activity

Once students are familiar with both approaches, they are asked to form small groups and come up with a potential problem for the Maximin decision principle. The prompt is to vary the case under discussion involving two donors and four patients, by assigning different marginal utilities and QALY’s, such that it would generate a bad result for the Maximin principle.

    Module Assignment

Example of a reflection question on the problem set for the graph theory unit:

EthiCS Reflection (1 pt): Suppose there are two patients in need of an immediate kidney transplant, but only one donor is currently available. The donor’s kidney is compatible with both patients. Patient A is 30 years old, and is expected to live 6 additional years as a result of the transplant. Patient B is 60 years old, and is expected to live 10 additional years as a result of the transplant. All else being equal (e.g., both patients have an urgent need for the transplant; both patients have been on the kidney exchange waiting list for the same length of time), which patient should the kidney go to, and why? Your response should take the form of a short paragraph (3-4 sentence) reflection. In explaining your ethical reasoning about the case, be sure to draw on at least one concept discussed in class.

Lessons Learned

Students caught on quickly to the underlying intuitions, as well as the problems with, both ethical approaches to the matching problem. Despite the size of the class and lecture hall, students were able to engage productively in conversation with one another facilitated by the Embedded EthiCS TA. Based on a show of hands at the end of the module, more students favored the Maximin decision procedure over welfare maximization. Overall, student responses to the module were overwhelmingly positive.
Pedagogical lessons:

1. Concluding the module with a sketch of a view that captures best of the two main approaches is a good way to leave students feeling both that progress was made, and that more work is to be done. That said, some students were keen to hear more, so a future iteration of the module might leave more time at the end for in-depth discussion of Prioritarianism.
2. It is important to strike an appropriate balance between (i) impressing upon students that the ethical complexity of real-world cases might not be best addressed by simply applying an algorithm to the problem, and (ii) keeping students optimistic about the prospects of representing solutions to problems abstractly, once the right ethical considerations are in view.
3. It might be worth considering other ways (besides QALY) to capture comparisons of more/less well-off. Some students found the intuition that a patient who has lived fewer (quality-adjusted) life years than someone else is therefore in more ‘need’ of a kidney a bit difficult to get behind.