Data Structures and Algorithms (CS 124) – Spring 2019

Module Topic: Matching mechanisms and fairness
Module Author: Cat Wade

Course Level: Upper-level undergraduate
AY: 2018-2019

Course Description: “This course covers the modern theory of algorithms, focusing on the themes of efficient algorithms and intractable problems. The course goal is to provide a solid background in algorithms for computer science students, in preparation either for a job in industry or for more advanced courses at the graduate level. I strongly encourage mathematicians, biologists, physicists, and people from other concentrations to take the course as well. Besides introducing the basic language and tools for algorithm analysis, we will also cover several specific problems and general design paradigms. Toward the end of the quarter, we will also examine heuristic techniques often used in practice, even though in many cases formal theoretical results are not known.

We will focus on the theoretical and mathematical aspects in class and on the homework assignments. But because one gains a deeper understanding of algorithms from actually implementing them, the course will include a substantial programming component. In particular, most problem sets include at least one problem that requires implementing an algorithmic solution to be tested against our test data. More details will be available when the first programming assignment is given.

As you can see from the preliminary list of topics (included below), we will be covering a great deal. I expect the course to be challenging, both in terms of the workload and the difficulty of the material. You should be prepared to do a lot of work outside of class. The payoff will be that you will learn a lot of both useful and interesting things. (Course description )”

Semesters Taught: Spring 2019

Tags

• fairness phil
• distributive justice phil
• original position phil
• flow algorithms CS

Module Overview

In this module, we consider fairness in resource allocation. Real-world resource allocation problems, such as the problem of allocating hospital beds to patients, can be modeled as flow maximization problems by representing both resources to be allocated and potential recipients of those resources as nodes in a flow network. After demonstrating how to model resource allocation problems using flow networks, the Embedded EthiCS fellow leads a discussion of what treating people fairly requires in different kinds of real-world resource allocation problems. We then discuss how to model these ethical requirements as formal constraints on flow maximization problems.

    Connection to Course Technical Material

In the leadup to the module, the course covers max flow problems and strategies for solving them algorithmically. The module builds on this technical material by (a) demonstrating how it can be used to solve real-world resource allocation problems and (b) showing how to formally model ethical constraints on these problems.

Goals

Module Goals

By the end of the module, students will be able to:

1. Understand the real-world applications of flow problems.
2. Identify ethical dilemmas associated with these real-world applications.
3. Develop a more sophisticated understanding of the concept of fairness.
4. Practice thinking and communicating about what fairness requires in the context of real-world resource allocation problems.

Key Philosophical Questions

• What do we mean when we say something is “fair”?
• What sorts of considerations should go into the decision-making process for the fair allocation of goods and services?
• What is the difference between procedural and outcome fairness?
• What types of procedural fairness are there?

Materials

Key Philosophical Concepts

• Fairness
• Procedural fairness and outcome fairness
• Rawls’ original position thought experiment
• Distributive justice

Assigned Readings

• Freeman (2019), “Original Position,” Stanford Encyclopedia of Philosophy, excerpts.
• Rawls (1971), A Theory of Justice, excerpts.
• Miller (2017), “Justice,” Stanford Encyclopedia of Philosophy, excerpts.

Implementation

Class Outline

1. Fairness in resource allocation.
2. The connection between fairness and flow maximization problems.
3. The concept of fairness.
4. Discussion of what fairness requires in three real-world resource allocation problems.
5. Modeling fairness requirements as constraints on min cost max flow problems.
6. Concluding discussion.

    Sample Class Activity

Students are given examples of three realistic resource allocation problems and asked to consider how they might be solved in a way that treats everyone concerned fairly.

Scenario (1): You are an employer trying to decide who to promote. You have 5 employees up for the position. How do you pick between them in order to make a fair decision?

Scenario (2): You are a conductor for a large orchestra with over one hundred members. Since you are new to the position, you don’t yet know any of the musicians well. You have ten tickets to an upcoming concert that you know everyone would like to go to. How do you decide fairly how to distribute the ten tickets?

Scenario (3): You and your partner have to decide who among your friends should officiate your wedding. You have different preferences. How could you resolve this fairly?

For each scenario, students are asked to discuss possible decision-making procedures they might use, as well whether those procedures would be fair or unfair. After each scenario, the Embedded EthiCS fellow leads a debrief with the full class.

Module Assignment

The assignment for this module consists of several short-answer questions on the assigned reading (see “Assigned Readings”):

1. What is the relationship between the original position and the veil of ignorance? (1 sentence)
2. Why does Rawls think the veil of ignorance is necessary? (Hint: think about the goal of the VOI.) (1-2 sentences)
3. Would someone behind the veil of ignorance know their race? (yes/no)
4. For the following scenarios, decide whether they would be examples of perfect procedural justice, imperfect procedural justice or pure procedural justice and explain your answer. (2-3 sentences per scenario)
   1. Students are placed into schools on the basis of a random lottery.
   2. Loan applicants are given loans on the basis of their credit score.
   3. Jail sentences are delivered using a very detailed and genuinely binding-in-all-cases system such that equal crimes serve equal time regardless of who perpetrates the crime.
   4. A couple uses a “you split, I’ll pick” policy for distributing naan bread between them when they get takeout.