Algorithms for Fair Allocation of Indivisible Goods

点击翻译按钮获取中文摘要

The allocation of indivisible goods to several users is a fundamental problem in many domains, e.g., when assigning students to universities, access rights to resources in computer or traffic networks, in dispute resolution (divorce, inheritance), etc. Designing good approximation algorithms for such problems has been a prominent area of active research. In particular, fairness guarantees for the output of efficient algorithms are an important research challenge and a prominent issue of recent interest in the public domain.In this project, we study design and analysis of efficient approximation algorithms for fair allocation of indivisible goods. The goal is to obtain new algorithms and provable performance guarantees for fairness in systems with expressive user valuations. We will examine a number of new and attractive fairness criteria (e.g., variants of envy-freeness) which are currently not well-understood in terms of their structural and algorithmic properties. In addition, we address fair allocation in strategic and game-theoretic environments. The goal is to design new mechanisms and show provable performance guarantees for the (approximate) fairness of the allocations in equilibrium.