Fair Division in a Connected World (Xiaohui Bei)

Abstract

In this talk we discuss fair resource allocation with connectivity constraints. Work on this subject typically assumes that the resources are arranged in a one-dimensional line. In this talk, we introduce a generalized model in which the resources form an undirected graph, and each agent must receive a connected subgraph. We consider both divisible and indivisible resources in this setting, which correspond to edges and vertices of the underlying graph, respectively. Unlike in the canonical setting, common fairness criteria such as proportionality for divisible goods and envy-freeness up to one good (EF1) for indivisible goods may not always exist in the graphical setting. Next we establish graph-specific approximation guarantees of these fairness criteria, which are tight for any graph with two agents and for a rich family of graphs with any number of agents. Our work reveals several new applications of tools and concepts from graph theory to fair division problems.a

Time

2019-06-18  10:00 ~ 10:45   

Speaker

Xiaohui Bei,Nanyang Technological University

Room

Room 102, School of Information Management & Engineering, Shanghai University of Finance & Economics