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.