Algorithms for Fair Allocations (AFFA)

公平分配算法 (AFFA)

• 批准号: 284041127
• 负责人: Professor Dr. Robert Bredereck
• 金额: --
• 依托单位: Institut für Softwaretechnik und Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/284041127?language=en
• 关键词: Algorithms; Fair; Allocations; AFFA

The main focus of AFFA is on the investigation of important computational problems in the context of fair allocations with respect to their algorithmic tractability.The second phase of the project again contains three main parts: the allocation of exclusive resources, the allocation of representatives, and the allocation of shared resources. We will address both theoretical and practical aspects when developing algorithms for corresponding allocation scenarios.On the theoretical side, our goal is to get more general and more realistic models for various allocation scenarios. Pursuing the aim, on the one hand, we will further study the incorporation of social networks (represented by graphs) in fair allocation scenarios, in this way generalizing so-far studied models. Our work will, consequently, include the adaptation and modification of existing fairness and efficiency concepts to new allocation scenarios augmented with social networks. On the other hand, we will also develop new models for temporal aspects of allocations. In particular, we plan to investigate the allocation of representatives and thereby study “incremental” scenarios where the solution is based on incremental, usually small, changes. For these investigation areas we plan to perform a fine-grained complexity analysis. Undoubtedly, we will face several computationally hard problems for which we are going to use multivariate algorithmics, approximation algorithms, reductions to solvers, and combinations of these techniques in order to circumvent the expected (worst-case) computational intractability.On the practical side, we plan to test our developed algorithms with respect to their practical usefulness by implementations and experimental investigations. Our effort will not only benefit the understanding of allocation mechanisms, but it will also result in new software tools useful for further experimental research in the area of fair allocation. All our developed software will be made publicly available. In addition, we plan to advance knowledge on the topic of allocation of representatives by conducting more specialized experiments taking into account temporal aspects. Using the results of these experiments, we aim at visualizing the corresponding dynamics. This will give us a fresh insight into the dynamics of several multiwinner election mechanisms in a time-dependent environment.

AFFA 的主要重点是研究公平分配背景下的重要计算问题及其算法可处理性。该项目的第二阶段同样包含三个主要部分：专属资源分配、代表分配和共享资源分配。在开发相应分配场景的算法时，我们将同时考虑理论和实践两个方面。在理论方面，我们的目标是针对各种分配场景获得更通用、更现实的模型。为了实现这一目标，一方面，我们将进一步研究社交网络（以图表示）在公平分配场景中的结合，从而推广迄今为止研究的模型。因此，我们的工作将包括对现有的公平和效率概念进行调整和修改，以适应社交网络增强的新分配方案。另一方面，我们还将针对分配的时间方面开发新模型。特别是，我们计划调查代表的分配，从而研究“增量”场景，其中解决方案基于增量（通常是小变化）。对于这些调查领域，我们计划执行细粒度的复杂性分析。毫无疑问，我们将面临几个计算困难的问题，我们将使用多元算法、近似算法、简化求解器以及这些技术的组合，以避免预期的（最坏情况）计算困难性。在实践方面，我们计划通过实现和实验研究来测试我们开发的算法的实际有用性。我们的努力不仅有利于对分配机制的理解，而且还将产生新的软件工具，可用于公平分配领域的进一步实验研究。我们开发的所有软件都将公开。此外，我们计划通过考虑时间方面的更专业的实验来推进关于代表分配主题的知识。利用这些实验的结果，我们的目标是可视化相应的动态。这将使我们对依赖时间的环境中几种多赢者选举机制的动态有一个新的了解。