RI: Small: The Surprising Power of Sequential Fair Allocation Mechanisms

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

The research team will analyze algorithms for resource allocation in markets without money, that is, finding mechanisms for investing in domains where the use of money is not allowed for legal or ethical reasons. For example, universities do not sell course seats to the highest bidder, nor do academic peer review systems assign reviewers based on pricing mechanisms. In such cases, centralized allocation mechanisms are used to distribute resources. To be practical, these mechanisms need to be fast and adaptable. In addition, they must guarantee that resources are distributed effectively (items go to those who will benefit most from them) and fairly (individuals and groups do not receive a disproportionately small share of benefits or take on an unfair number of chores). The research team will investigate a simple and appealing paradigm: sequential allocation mechanisms. In a sequential allocation mechanism, users take actions in turns (for example, taking an unassigned item, or stealing an item from someone else), until some desired condition is met (for example, all items have been assigned). The research team will show that despite their simple structure, sequential allocation mechanisms can be practically used in many real-world problems, while offering fairness and efficiency guarantees. The research team will investigate the types of guarantees that sequential mechanisms offer, and the types of domains we can apply them to. The research team will collaborate with OpenReview, an academic peer reviewing platform, academic conference organizers, and with university administration, to test and implement its findings. Large-scale allocation of resources is a key problem in the design of multi-agent systems. Researchers have developed increasingly complex algorithmic frameworks to guarantee that the algorithms produce outcomes that are both fair and efficient. However, the complexity of these algorithms often precludes their practical implementation and makes them difficult to adapt to the needs of specific problem domains. To address this shortcoming, instead of complex algorithmic frameworks, the proposal advocates for sequential algorithmic techniques that are easy to both implement and understand. The proposal examines the theoretical foundations of sequential allocation mechanisms, as well as their applications. The research team will show that the sequential approach offers a significant computational speedup, and via careful analysis, guarantees both fairness and efficiency. For general agent preferences, it is well-known that achieving both fair and efficient allocations is computationally intractable; therefore, the researcher team will focus on specific agent preference classes, with a particular focus on submodular valuations. Submodular functions naturally arise in a variety of economic domains; however, their structural properties allow us to rely on fundamental combinatorial techniques, such as matroid optimization and graph theory. The proposal will investigate picking sequences, with a recent implementation in the OpenReview platform. The proposal will also study sequential item transfer mechanisms (termed Yankee Swap mechanisms), with strong fairness and efficiency guarantees in practical domains, such as course allocation. Finally, the proposal will study a broad sequential framework that handles more complex submodular valuation classes, including the fair allocation of chores (such as work shifts). The techniques developed through this proposal have broad applications in a variety of resource allocation domains, for example, conference paper reviewer assignment, work shift allocation, and course assignment systems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.