Switch to German Switch to English

Research Focus



Current Projects with External Funding

Algorithms, Dynamics, and Information Flow in Networks

(DFG Research Unit, funded 2020 - 2023)

Spreading processes in networks are a central challenge in many areas of modern society - viruses spread in a population, news and opinions in social networks, malware in the Internet, etc. In financial markets, similar effects can lead to instability and bankruptcy, and highlight the systemic risks in interconnected economies. Dynamics and spreading can also be used constructively, e.g., in the design of distributed algorithms for decentral applications.
Dynamic spreading processes can be interpreted as an information flow in a network. In many applications, the fundamental algorithmic properties of these information flows are not well-understood. The research unit consists of six projects that study different aspects of spreading and information flow -- distributed algorithms and population protocols, systemic risks in financial markets, learning and reconstruction, opinion dynamics, network design, and scalable algorithms for implementation and simulation of randomized processes. The goals are to establish foundational insights across the different areas, as well as to develop algorithms to simulate, reconstruct, control, and optimize information flows in networks.


Spokesman: Martin Hoefer
PIs: Petra Berenbrink, Nils Bertschinger, Amin Coja-Oghlan, Tobias Friedrich, Martin Hoefer, Ulrich Meyer


Algorithms for Fair Allocation of Indivisible Goods

(funded by DFG, 2020 - 2023)

One of the most fundamental tasks in society is the proper allocation of resources to users. For example, in online markets we need to allocate goods and services to the market participants, or in large-scale computing systems we need to allocate computing time, bandwidth or other facilities to users. A recent and upcoming surge of interest, both in the public domain as well as in academia, is to guarantee fairness in the decisions made by computational systems and in the way they affect the users. In this project, we study existence, efficient algorithms, and computational complexity for fair allocations of indivisible goods.
There are many intuitive notions of what it means to be fair to a group of people. Despite the lack of an unanimous notion, different measures that capture intuitive ideas of fairness for allocation problems have been proposed and studied, albeit mostly for divisible goods. More recently, fairness criteria for indivisible goods have attracted interest, such as notions of envy-freeness, max-min shares or the Nash social welfare. In this project, we conduct a rigorous study of approximation algorithms and inapproximability results for fair allocation problems. The overarching goal is to provide a common algorithmic toolbox for approximation of fairness criteria. We plan to design algorithms with provable approximation guarantees for allocation problems with expressive user valuations (such as submodular, XOS, subadditive and beyond), as well as lower bounds and inapproximability results. We will test our algorithms in experiments on randomly generated as well as real-world data.


PIs: Martin Hoefer, Jugal Garg (Mercator Fellow)


Completed Projects

Sequential Information Aggregation with Partial Observability

(funded by German-Israeli Foundation (GIF), 2018 - 2020)