Schwerpunkte
Entwurf und Analyse effizienter Algorithmen
Approximationsalgorithmen und Randomisierte Algorithmen
Algorithmische Spieltheorie und Mechanism Design
Algorithmen für Kommunikationsnetzwerke
Theorie verteilter Systeme
Laufende Drittmittelprojekte
Algorithms, Dynamics, and Information Flow in Networks(DFG Forschungsgruppe 2975, gefördert 2020 - 2026) |
|
Ausbreitungsprozesse in Netzwerken sind eine zentrale Herausforderung in vielen Bereichen der Gesellschaft - Viren verbreiten sich in der Bevölkerung, Neuigkeiten und Meinungen in sozialen Netzwerken, Schadprogramme im Internet, usw. In Finanzmärkten können Ansteckungs- und Ausbreitungsprozesse stattfinden und systemische Risiken offenbaren. Die Dynamik von Ausbreitungsprozessen kann aber auch konstruktiv beim Entwurf von verteilten Algorithmen für dezentrale Anwendungen genutzt werden.
Prozesse dieser Art können als ein Fluss von Information durch ein Netzwerk angesehen werden. Die algorithmischen Eigenschaften von solchen Informationsflüssen sind in vielen Bereichen noch nicht gut verstanden. Die Forschungsgruppe untersucht in sechs Teilprojekten verteilte Algorithmen und Population Protocols, systemische Risiken in Finanzmärkten, Lernen und Rekonstruktion von Ansteckungsprozessen, Meinungsdynamiken, Netzwerkdesign sowie Skalierungsfragen bei der Implementation und Simulation von Prozessen dieser Art. Die Ziele sind einerseits die Erforschung von Grundlagen über die Teilgebiete hinweg, als auch konkrete algorithmische Verfahren für die Simulation, Rekonstruktion, (Gegen-)Steuerung und Optimierung von Informationsfüssen in Netzwerken.
| Sprecher: | Martin Hoefer |
| PIs: | Petra Berenbrink, Nils Bertschinger, Amin Coja-Oghlan, Tobias Friedrich, Martin Hoefer, Ulrich Meyer |
Online Algorithmen für Bayes'sches Überzeugen(gefördert von der DFG, 2024 - 2027) |
|
Das grundlegende Problem im Informationsentwurf oder Bayes'schen Überzeugen besteht darin, dass ein informierter Agent (Sender) Informationen mit einem uninformierten Agenten (Empfänger) teilt, um den Empfänger zu überzeugen, eine Entscheidung im Sinne des Senders zu wählen. Bayes'sches Überzeugen ist ein sehr populäres Gebiet in der Ökonomie mit vielen Anwendungen. Die algorithmischen Aspekte sind dagegen bisher nicht gut verstanden. In diesem Projekt vertiefen wir das algorithmische Verständnis von Problemen im Kontext von Bayes'schem Überzeugen. Wir konzentrieren uns auf Online-Modelle, in denen Akquise und Teilen der Information graduell und gleichzeitig ablaufen. Das Ziel ist, optimale und fast-optimale Überzeugungsstrategien für den Sender zu analysieren und effizient zu berechnen. Die Online-Modelle sind eng mit Modellen aus dem Optimal Stopping verwandt, insbesondere mit kombinatorischen Sekretärproblemen und prophetischen Ungleichungen. Hierbei kann der Empfänger mehrere Aktionen unter kombinatorischen Einschränkungen wählen. Wir konzentrieren uns dabei insbesondere auf Packprobleme wie Rucksack oder Matching. Das Ziel ist, die Komplexität von Empfehlungsstrategien zu untersuchen, mit denen der Sender seine erwartete Utility maximiert, während er dem Empfänger einen Anreiz gibt, die empfohlene Aktion auszuwählen. Daneben untersuchen wir mit Hilfe von kompetitiver Analyse, wie man gute Empfehlungsstrategien berechnen kann, die einen beschränkten Verlust garantieren zu optimalen Strategien im Offline-Modell (mit Kenntnis der Zukunft). Insbesondere ist dabei von Interesse, ob es "Black-Box"-Reduktionen gibt, mit denen man gute Online-Algorithmen zur Berechnung von guten Online-Empfehlungsstrategien nutzen kann. Unsere Resultate werden algorithmische Werkzeuge für Empfehlungsprobleme neu entwickeln und erweitern.
| PIs: | Martin Hoefer, Rann Smorodinsky |
Abgeschlossene Projekte
Algorithmen für faire Zuteilung unteilbarer Güter(gefördert von der DFG, 2020 - 2024) PIs: Martin Hoefer, Jugal Garg (Mercator Fellow) |
|
Sequential Information Aggregation with Partial Observability(gefördert von der German-Israeli Foundation (GIF), 2018 - 2020) PIs: Martin Hoefer, Rann Smorodinsky |
|