|
|
|
|
July 24 (Sunday), Afternoon session, Lehar 4
|
|
Fair division has received significant attention from the game theory and AI communities in the past decade, both from the axiomatic and computational point of view. Its goal is typically to divide resources among interested agents so that certain fairness criteria are met. While the majority of work on fair division assumes that any allocation of the resource to the agents is feasible, in many applications there are constraints on the allocation that can be made. For instance, when allocating offices in a university building to research groups, it is helpful for each group to receive a connected set of offices in order to facilitate communication within the group. Another example is the division of land among inhabitants: Since a thin or highly zigzagged piece of land is unlikely to have much value even if its area is large, the geometric shape of the allocated land must be taken into account. Additionally, if the land is used to grow crops, keeping different plots separated can help prevent cross-fertilization. A substantial line of work in the last few years focuses on identifying appropriate fairness notions and guarantees in the presence of such constraints.
In this tutorial, after providing an introduction to fair division for newcomers in the area, as well as an overview of common fairness notions (e.g., envy-freeness, proportionality, maximin share fairness), we will explain fairness guarantees for both divisible (so-called "cake cutting") and indivisible resources under different types of constraints. First, we will discuss the most frequently studied type of constraints—connectivity constraints—starting with the classical setting of connected cake cutting and moving on to more recent works on allocating a graphical cake (which represents a road network) or indivisible goods on a graph. We will then proceed to matroid constraints, an important class which captures cardinality and balancedness considerations; these are relevant, for example, when a museum distributes a set of exhibits among its branches, which may have capacity limits and category specifications. We will also survey other types of constraints that have been studied in the literature, including geometric (relevant when dividing a piece of land), separation (e.g., due to social distancing requirements), budget (when each agent has a limited spending), and conflict constraints (when items cannot be allocated simultaneously, perhaps due to temporal conflicts). Throughout the tutorial, we will highlight overarching themes for dealing with constraints—for example, the robustness of the maximin share fairness notion—and outline a number of open questions and directions for future work.
No prior knowledge of fair division or game theory is assumed. We believe that the tutorial will be useful for anyone who wants to find out about current directions in fair division, learn interesting frameworks and tools, or simply get an introduction to the area.
|
|
Ayumi Igarashi is an assistant professor in the Principles of Informatics Research Division at the National Institute of Informatics (NII), Japan. Previously, she was a JSPS postdoctoral fellow at the University of Tokyo, Japan, and completed her PhD in the Department of Computer Science at the University of Oxford, UK. Her research focuses on algorithmic game theory, computational social choice, and combinatorial optimization. She is an author of a number of fair division papers, several of which investigate various types of constraints that arise in practice. Recently, she was selected on the Innovators Under 35 Japan 2021 list by MIT Technology Review.
Warut Suksompong is an assistant professor in the School of Computing at the National University of Singapore. Previously, he was a postdoctoral researcher at the University of Oxford, UK, and completed his PhD in the Department of Computer Science at Stanford University, USA. He is interested in algorithmic game theory, mechanism design, social choice theory, and other problems at the interface between computer science, economics, mathematics, and operations research. His work on fair allocation of land with geometric constraints received a Distinguished Paper Award at IJCAI 2021, and his work on funding public projects was selected as the Best Student Paper at WINE 2021.
|
|
|
|
Survey: Constraints in Fair Division, ACM SIGecom Exchanges, 2021
|
|