Algorithms for fair public and private resource allocation
Abstract/Contents
- Abstract
- This thesis explores algorithms for resource allocation, with an emphasis on fairness. "Fairness" is an extremely complex concept and our goal in this thesis is not to design an algorithm that is "truly fair" (if such a thing even exists). Rather, we consider a variety of specific objectives inspired by fairness, and analyze their properties in different resource allocation models. The thesis is split into "private" resource allocation and "public" resource allocation. Private resource allocation handles items such as food and cars, where each individual receives a separate bundle of resources, with the key assumption being that their happiness (or "utility") depends only on what they receive, and not on what others receive. This process typically occurs through decentralized markets. In contrast, in public resource allocation, a centralized government makes a single decision that affects all citizens: for example, how to allocate a city budget, or whether to build a communal pool. Markets and governments are two of the most fundamental institutions in our society, and so any improvement to these systems can have far-reaching benefits. For both of these settings, we take on the role of the system designer (or "social planner"). Our goal is to design an allocation method (or "mechanism") to distribute these resources in a "good" way, where "good" can have many interpretations, including but not limited to fairness concerns. We consider two primary approaches to defining "good": axiomatic and welfarist. An axiom states a desirable property the outcome. For example, a common fairness axiom for private resource allocation is "envy-freeness": no individual should prefer another individual's bundle to her own. In contrast, the welfarist approach is predicated on a designated "welfare function", which assigns a single number to each possible outcome, with larger numbers being "better". Our goal then becomes to choose an outcome which maximizes the welfare function. Different welfare functions represent different priorities: for example, maximizing the sum of utilities focuses on overall societal happiness, and maximizing the minimum utility focuses on equality of happiness across individuals. For all of these settings -- private or public, axiomatic or welfarist -- we provide allocation mechanisms that are provably "good" in some way. That said, each of our mechanisms has its own drawbacks, and whether or not these mechanisms are truly "fair" depends on a myriad of logistical, cultural, and philosophical factors. However, we hope that this thesis serves as an important step along the never-ending path to improve resource allocation in our society.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Plaut, Benjamin Jonas |
|---|---|
| Degree supervisor | Goel, Ashish |
| Degree supervisor | Reingold, Omer |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Reingold, Omer |
| Thesis advisor | Rubinstein, Aviad |
| Degree committee member | Rubinstein, Aviad |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Benjamin Plaut. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/pp623yb5881 |
Access conditions
- Copyright
- © 2021 by Benjamin Jonas Plaut
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...