Dynamic Coordination in Large Networks
Final Report Abstract
Der Thema des Projekts waren grundlegende Fragen über dynamische Aspekte in Netzwerksystemen, die durch eine Vielzahl an Teilnehmern mit begrenzter Information und eigensinnigem Interesse charakterisiert sind. Dieser Ansatz ist hilfreich in vielen Anwendungen, z.B. für verteilte Protokolle in Funknetzwerken zur Optimierung von Zugriffen auf das Frequenzspektrum. Hierbei treten neue Varianten von klassischen Optimierungsproblemen auf, z.B. verallgemeinerte Independent-Set Probleme für den konfliktfreien Zugriff auf einen Kanal, sowie Färbungs- oder Lastbalancierungsprobleme bei mehreren Kanälen, je nach Zielfunktion und Interferenzmodell. Ausgehend von diesen Anwendungen war die Zielsetzung des Projekts, verteilte Protokolle für spieltheoretische Modelle zu entwerfen und zu analysieren, insbesondere bzgl. der Konvergenzeigenschaften und der sozialen Güte der berechneten Lösungen. Ein gemeinsamer Aspekt der betrachteten Modelle war die Einbeziehung von Netzwerken, d.h. in den Modellen waren Interaktion und Anreize der Spieler charakterisiert durch eine Netzwerkstruktur. Zum Beispiel kann eine Vielzahl bekannter Interferenzmodelle in Funknetzwerken interpretiert werden als Klassen von gewichteten und gerichteten Konfliktgraphen. Daneben ergeben sich natürliche Netzwerkstrukturen auch in anderen Anwendungen, z.B. durch lokal beschränkte Interaktion in sozialen Netzwerken, oder bei Lastbalancierung in Rechnernetzen. Die Resultate des Projekts sind mathematisch beweisbare Schranken in diversen spieltheoretischen Modellen und durch eine Reihe von Veröffentlichungen in einschläagigen Organen der theoretischen Informatik, Mathematik und der Elektrotechnik dokumentiert. Einen großen Teil der Resultate bilden Garantien für den Durchsatz und die Konvergenzzeiten beim Einsatz von einfachen Verfahren des Online-Lernens in Funknetzwerken. Diese Verfahren liefern hohen Durchsatz, sogar beim Einsatz mit gegnerischen Jamming im Kanal, bei zeitlich veränderlichen Kommunikationsanfragen, bei unterschiedlicher Struktur der Anfragen, sowie unter der Verwendung von verschiedenen Interferenzmodellen zur Abbildung von Störungen. Daneben lassen sich einfache Verfahren des Online-Lernens auch zur Kontrolle von Signalstärken verwenden und haben hier konzeptionelle Vorteile gegenüber klassischen Fixpunktiterationen. Einen anderen Teil bilden Resultate zu Konvergenzzeiten in dynamischen Matching-Märkten mit lokal beschränkter Sichtbarkeit zwischen den Agenten. Lokale Sichtbarkeit kann dabei eine starke Einschränkung mit sehr negativen Folgen für das Konvergezverhalten sein. Hier können geeignete Formen von Gedächtnis über im Prozess aufgelöste Paare entscheidend zu schneller Konvergenz beitragen. Daneben wurden auch Resultate zu Protokollen für Lastbalancierung in Netzwerken erzielt. Diese Protokolle zeichnen sich dadurch aus, dass beim Entwurf einzelne Lasteinheiten wie eigensinnige Agenten behandelt werden. Dadurch können die Verfahren dezentral und mit beschränkter Information eingesetzt werden. Die vorgestellten Protokolle garantieren dabei schnelle Konvergenzzeiten zu approximativ balancierten Zuständen.
Publications
- . Local Matching Dynamics in Social Networks. In Proc. 38th Intl. Coll. Automata, Languages and Programming (ICALP), part II, pp. 113–124, 2011. Best Paper Award, Track C
Martin Hoefer
- Distributed Selfish Load Balancing in Networks. In Proc. 22nd Symp. Discrete Algorithms (SODA), pp. 1487–1497, 2011
Petra Berenbrink, Martin Hoefer, Thomas Sauerwald
- Convergence Time of Power-Control Dynamics. IEEE Journal on Selected Areas in Communications 30(11):2231– 2237, 2012
Johannes Dams, Martin Hoefer, Thomas Kesselheim
- Scheduling in Wireless Networks with Rayleigh-Fading Interference. In Proc. 24th Symp. Parallelism in Algorithms and Architectures (SPAA), pp. 327–335, 2012
Johannes Dams, Martin Hoefer, Thomas Kesselheim
- Friendship and Stable Matching. In Proc. 21st European Symposium on Algorithms (ESA), pp. 49–60, 2013
Elliot Anshelevich, Onkar Bhardwaj, Martin Hoefer
- Locally Stable Marriage with Strict Preferences.In Proc. 40th Intl. Coll. Automata, Languages and Programming (ICALP), part II, pp. 620– 631, 2013
Martin Hoefer, Lisa Wagner
- Jamming-Resistant Learning in Wireless Networks. In Proc. 41st Intl. Coll. Automata, Languages and Programming (ICALP), part II, pp. 447–458, 2014
Johannes Dams, Martin Hoefer, Thomas Kesselheim
(See online at https://doi.org/10.1007/978-3-662-43951-7_38) - Matching Dynamics with Constraints. In Proc. 10th Conf. Web and Internet Economics (WINE), pp. 161–174, 2014
Martin Hoefer, Lisa Wagner
(See online at https://dx.doi.org/10.1007/978-3-319-13129-0_12)
