Algorithms for Fair Allocations (AFFA)

• Applicant: Professor Dr. Robert Bredereck
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 284041127

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.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Professor Dr. Rolf Niedermeier, until 6/2022 (†)