Design and analysis of efficient algorithms
Approximation and randomized algorithms
Algorithmic game theory and mechanism design
Algorithms for communication networks
Theory of distributed systems
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
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.
|PIs:||Petra Berenbrink, Nils Bertschinger, Amin Coja-Oghlan, Tobias Friedrich, Martin Hoefer, Ulrich Meyer|
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|
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)|
Sequential Information Aggregation with Partial Observability
(funded by German-Israeli Foundation (GIF), 2018 - 2020)
PIs: Martin Hoefer, Rann Smorodinsky.