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 - 2026)

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

Online Algorithms for Bayesian Persuasion

(funded by DFG, 2023 - 2026)

Information design, also known as Bayesian persuasion, is a field that studies how an informed agent (sender) can share information in order to motivate an uninformed agent (receiver) to take certain actions that are beneficial to the sender. Bayesian persuasion has received a lot of attention in economics due to its many applications, but the underlying algorithmic problems are not well-understood. In this project, our goal is to advance the state of the art of algorithmic theory in persuasion and recommendation problems. We focus on online settings where information sharing and gathering happen gradually and concurrently. Our goal is to analyze and compute optimal and near-optimal persuasion strategies for the sender. The online setting is closely related to optimal stopping theory, in particular, to combinatorial secretary and prophet inequality problems. Here a receiver can select several actions, under different combinatorial restrictions on the subset of selected actions. Most prominently, we will focus on packing structures such as knapsack or matching. The overarching goal is to study the computational complexity of persuasion schemes that optimize the expected utility of the sender, while incentivizing the receiver to follow any recommended action. We are also interested in competitive analysis, i.e., designing good schemes with a bounded loss in sender utility compared to optimal schemes in the offline setting (when knowing the future). More fundamentally, we want to see if there are "black-box"-reductions, using which we can transform good online algorithms into good online signaling schemes. In this way, we contribute to the algorithmic toolbox for (online and offline) persuasion and recommendation problems.

PIs: Martin Hoefer, Rann Smorodinsky

Cryptography & Game Theory for Decentralized Exchanges

(funded by ATHENE Center for Applied Cybersecurity, 2023 - 2026)

Our goal is to address some of the main shortcomings of the current state of the art in designing protocols for decentralized finance (DeFi) in blockchain environments. We work on the underlying blockchain infrastructure to make it more robust to power DeFi applications, and explore the design space of DeFi protocols by developing theoretical foundations for their design and analysis. We mainly focus on decentralized exchanges (DEXes) and their main innovation, the automated market maker (AMM). AMMs work fundamentally different from classical order-based exchanges and are realized via a public smart contract that runs fully autonomous. We investigate existing designs for DEXes and build a mathematical framework for their analysis. This allows to examine critical security aspects of DEXes relating to maximal extractable value (MEV) of miners of the blockchain. We study several countermeasures to MEV that exploit characteristics of the DEX environment. Moreover, we advance the understanding from single DEXes to the interplay of multiple DEXes and analyze the results of market behavior using game-theoretic methods. We want to understand the influence on economic aspects such as liquidity and transactions fees, as well as security aspects by understanding attacks of miners against DEXes running on the blockchain.

PIs: Sebastian Faust, Martin Hoefer

Completed Projects

Algorithms for Fair Allocation of Indivisible Goods

(funded by DFG, 2020 - 2024)

PIs: Martin Hoefer, Jugal Garg (Mercator Fellow)

Sequential Information Aggregation with Partial Observability

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

PIs: Martin Hoefer, Rann Smorodinsky