Algorithmic fair division in dynamic, socially constrained environments

Can a set of items be divided in a commonly acceptable way?

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 formalised and studied in economics, mathematics, and computer science.

The goal of this project 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.

The key focus will be on developing 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.

A similar example can be found in 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.

Funding

This project was funded by the Dutch Research Council (NWO) Innovational Research Incentives Scheme (Veni Science domain 2019).