Algorithms for Fair Allocation of Indivisible Goods

不可分割商品的公平分配算法

• 批准号: 431465915
• 负责人: Professor Dr. Martin Hoefer
• 金额: --
• 依托单位: Arbeitsgruppe Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/431465915?language=en
• 关键词: Algorithms; Fair; Allocation; 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.

将不可分割的货物分配给几个用户是许多领域的一个基本问题，例如，当分配学生到大学，访问权限的资源，在计算机或交通网络，在纠纷解决（离婚，继承）等。设计良好的近似算法，这样的问题一直是一个突出的领域，积极的研究。特别是，公平保证有效的算法的输出是一个重要的研究挑战和最近的兴趣在公共domain.In这个项目中，我们研究的设计和分析的有效近似算法公平分配不可分割的货物的一个突出问题。我们的目标是获得新的算法和可证明的性能保证系统的公平性与表达用户的评价。我们将研究一些新的和有吸引力的公平标准（例如，无嫉妒的变体），其在结构和算法性质方面目前还没有被很好地理解。此外，我们在战略和博弈论环境中解决公平分配。我们的目标是设计新的机制，并显示可证明的性能保证的（近似）公平的平衡分配。