Algorithms for Fair Allocations (AFFA)

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.