Algorithms for Fair Allocations (AFFA)

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

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.