Algorithmic Fair Division in Dynamic, Socially Constrained Environments

Samenvatting

How to divide a set of items in a commonly acceptable way? In disputes involving resource allocation, for instance in a divorce, this is a crucial objective. The problem becomes very challenging when these items are indivisible, meaning they cannot be cut or shared, like a painting. Fair division refers to the problem of allocating a set of items to a set of agents in a way that satisfies a desired fairness criterion. As an extreme example, in an ideal allocation each agent sees their share to be the best among all shares. Many variants of fair division have been formalized and studied in economics, mathematics, and computer science.
My main goal is to develop a framework for fair division of indivisible items when the sets of agents and items dynamically change over time and the fairness requirements are constrained by the underlying social structure. My focus is primarily on obtaining efficient algorithms for computing fair allocations that also have strong, provable performance guarantees.
Despite the long history of fair division, dynamic, socially constrained settings are poorly understood. For such an example we may turn to cloud computing, where computing resources are allocated to agents/companies that arrive in a non-deterministic fashion. Here it is more important for an agent/company to have strong fairness guarantees with respect to their competitors rather than with respect to everyone using the service.
My project builds on two novel key ideas. First, in order to get meaningful fairness guarantees, the fairness criteria themselves should be defined taking time into consideration. To introduce such temporal fairness criteria, I will generalize the recently introduced notion of maximin shares. Secondly, to fully explore social constraints, I will use weighted social graphs. This allows to model the varying degrees of envy that an agent may have towards others.

Kenmerken

Projectnummer

VI.Veni.192.153

Hoofdaanvrager

Dr. G. Amanatidis

Verbonden aan

NWO-institutenorganisatie, CWI - Centrum Wiskunde & Informatica

Looptijd

01/09/2019 tot 31/08/2022