Research Focus
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 - 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 |
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 |
|