Fair Division of Indivisible Items: Asymptotics and Graph-Theoretic Approaches

IJCAI 2019 Tutorial


Presenters


Abstract

Fair division has received significant attention in the game theory and artificial intelligence community 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. The applications of fair division range from settling divorce disputes and dividing inheritance to sharing apartment rent and splitting household tasks. Early work in the area mostly focused on how to allocate divisible resources such as land. However, the past two decades or so, and especially the last few years, have seen considerable interest in fairly allocating indivisible resources like jewelry and artworks. This setting is inherently different from the divisible setting in several ways and consequently calls for the use of new concepts, techniques, and tools.

In this tutorial, we will begin by providing an introduction to fair division for newcomers in the area. We will outline the main fairness notions for indivisible items and their properties. We will then present two emerging frameworks in the fair division of indivisible items. First, we will give a survey of asymptotic results: since several common fairness notions cannot always be satisfied in the presence of indivisibility, an important question is to determine the conditions under which allocations satisfying each notion are likely to exist in random instances. We will introduce tools from probability theory and matching theory that are required to address the question. Second, we will present an overview of recent work on fair division of indivisible items with constraints imposed by a network. In one setting, a network describes a physical or temporal relation between items, and agents are only interested in receiving a connected bundle of items. In another setting, networks describe a relation between agents rather than items, and require each agent to have no envy towards her neighbours. We will explain some existence and complexity results as well as techniques based on classical arguments from the divisible cake-cutting setting. Finally, we will discuss a number of open questions that stem from these lines of 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.


Presenters' Biographies

Ayumi Igarashi is a JSPS postdoctoral fellow, hosted by Prof. Satoru Iwata at University of Tokyo since April 2019. She completed her PhD at the Department of Computer Science, the University of Oxford under the supervision of Prof. Edith Elkind. Her broad area of research interests includes game theory, combinatorial optimisation, and social choice. She has been particularly looking at problems with connectivity constraints imposed by a network, especially the existence and complexity of fairness and stability notions in various contexts, such as coalition formation games and fair division of indivisible items.

Warut Suksompong is a research associate (postdoc) in computer science at the University of Oxford, hosted by Prof. Edith Elkind. He completed his PhD at Stanford University under the supervision of Prof. Tim Roughgarden, and his bachelor's and master's degrees at Massachusetts Institute of Technology. His research interests include algorithmic game theory, mechanism design, fair division, social choice theory, and other problems at the interface between computer science and economics. He has published papers in computer science, economics, mathematics, and operations research venues.


Tutorial Outline

  1. Introduction
  2. Fairness notions for indivisible goods
  3. Asymptotic results
  4. Graph-theoretic approaches
  5. Summary and open questions

Tutorial Slides

Part 1, Part 2