Switch to German Switch to English

Research Focus

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 proposal, 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)

Sequential Information Aggregation with Partial Observability

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

A classical setting where decentralized markets may fail is when critical information exists but is distributed among the agents. Each agent can access the information held by other agents only implicitly by observing their actions. We study structural properties and computationally efficient mechanisms for information aggregation in settings where self-interested agents take actions sequentially and partially observe each other. Our aim is to design mechanisms using ideas from learning theory to limit or even avoid market failure.
One (out of several) settings we study is designing a recommendation system based on the wisdom-of-the-crowd (such as, e.g., TripAdvisor, Hotels.com, etc). In these systems, services that are less recommended are typically consumed by fewer people, thus less reviewed and recommended, which ensures that they maintain a low rank. This tension between exploration and exploitation needs to be addressed to ensure good performance of the system. We study how to design computationally efficient mechanisms to ensure enough exploration even when agents act individually and partially see actions taken by preceding agents. Orchestrated by the system, exploration must be implemented such that agents find it in their best interest to follow the recommendations. The mechanisms must incorporate or even decide about partial observability of agents and actions of predecessors - which, in turn, result from the recommendations they received as well as what they saw (some of) their own predecessors doing.

PIs: Martin Hoefer, Rann Smorodinsky