Switch to German Switch to English

Schwerpunkte


Drittmittelprojekte

Algorithms, Dynamics, and Information Flow in Networks

(DFG Forschungsgruppe 2975, gefördert 2020 - 2023)

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 Eigenschaten 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 Informationsflüssen in Netzwerken.


Sprecher: Martin Hoefer
PIs: Petra Berenbrink, Nils Bertschinger, Amin Coja-Oghlan, Tobias Friedrich, Martin Hoefer, Ulrich Meyer


Algorithmen für faire Zuteilung unteilbarer Güter

(gefördert von der DFG, 2020 - 2023)

Eine grundlegende Aufgabe ist die angemessene Zuteilung von Ressourcen an Nutzer. Im Internet müssen zum Beispiel Güter und Services an Marktteilnehmer verteilt, in großen Rechnersystmen Rechenzeit, Bandbreite oder Nutzungsrechte an die Nutzer vergeben werden. Ein aktuell zunehmendes Interesse, sowohl in der Öffentlichkeit als auch in der Forschung, besteht an Kriterien der Fairness in der Entscheidung von Algorithmen und ihren Auswirkungen auf die Nutzer. In diesem Projekt untersuchen wir Existenz, effiziente Algorithmen und Berechnungskomplexität von fairen Zuteilungen unteilbarer Güter.
Es gibt viele intuitive Ideen, was eine faire Behandlung von einer Gruppe von Nutzern darstellt. Daher wurden in der Vergangenheit eine Reihe von formalen Ansätzen untersucht, die Ideen von Fairness abbilden. Diese Arbeiten betreffen meist teilbare Güter. In der aktuellen Forschung sind Fairnesskriterien für unteilbare Güter von Interesse, zum Beispiel die sog. envy-freeness, max-min shares oder Nash social welfare.
In diesem Projekt untersuchen wir Approximationsalgorithmen und Nicht-Approximierbarkeit von Problemen der fairen Zuteilung. Ein übergeordnetes Ziel ist die Bereitstellung von algorithmischen Techniken, die zur Approximation von Fairnesskriterien genutzt werden können. Wir planen, Algorithmen für Zuweisungprobleme mit allgemeinen Klassen von Bewertungen (z.B. submodular, XOS, subadditiv, usw) zu entwickeln sowie obere und untere Schranken auf ihre Güte zu untersuchen. Die Verfahren sollen in Experimenten getestet werden, sowohl auf zufälligen Instanzen als auch mit Daten aus realen Anwendungen.


PIs: Martin Hoefer, Jugal Garg (Mercator Fellow)


Sequential Information Aggregation with Partial Observability

(gefördert von der 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