Modelle und Algorithmen für Multi-Level-Congestion- und Security-Probleme

• Antragsteller: Professor Dr. Tobias Harks, seit 1/2019
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 417282269

Strategisch geplante Sabotage- und Terroranschläge bedrohen zunehmend wichtige Infrastruktursysteme und ihre Nutzer. Ziel dieses Antrages ist die Entwicklung von Modellen und Algorithmen für Multi-Level- Congestion- und Security-Games, mit denen sich robuste Netzwerkdienste und -infrastrukturen planen lassen. Die Modellierung geschieht aus Sicht des Planer, der im ersten Level die Infrastruktur plant (z. B. ein U-Bahn-Netz oder Fluchtwege in einem Stadion). Im zweiten Level agieren die Nutzer der Infrastuktur unter Berücksichtigung ihrer eigenen Interessen. Im letzten Level wählt nun ein Angreifer, in Kenntnis der Verteilung der Netzwerknutzer, Teile der Infrastruktur als Ziel aus. Dabei zielt er auch maximalen Schaden ab (z. B. das treffen einer möglichst großen Menge Menschen).Das Lösen der daraus resultierenden Multi-Level-Optimierungsprobleme stellt eine große Herausforderung dar, vor allem wegen der nicht-konvexen Struktur der Lösungsmenge, die sich durch die verschiedenen Level ergibt. Zur Lösung schlagen wir deshalb ein neuartiges Konzept der level-weisen Approximation vor. In diesem wird die Optimalitätsbedingung in jedem einzelnen Level durch einen individuellen Faktor approximiert. Mithilfe dieses Ansatzes hoffen wir Algorithmen entwickeln zu können, die effizient fast-optimale Lösungen berechnen können.Eine weitere Herausforderung entsteht durch die Berücksichtigung von Auslastungseffekten, die durch das eigennützige Verhalten der Nutzer verursacht werden, in Kombination mit der Bedrohung durch den Angreifer. Ein wichtiges Ziel unseres Projektes ist deshalb die Untersuchung sogenannter Bilevel Congestion Games, also von Spielen, in denen jeder Nutzer die von allen Nutzern verursachte Auslastung und die Aktionen des Angreifers im letzten Level berücksichtigt, wobei letzterer die am stärksten frequentierten Teile der Infrastuktur als Ziel wählt.Die Kombination der gewonnenen Einsichten zur Approximation von Multi-Level-Netzwerk-Problemen und Bilevel Congestion Games soll dann zur Lösung von Multi-Level Network Security Games mit Auslastungseffekten verwendet werden. Hierbei wollen wir auf ein Zusammenspiel von Approximationsalgorithmen, Heuristiken und exakten Methoden setzen, die wir dann in einer experimentellen Studie mit realistischen Daten überprüfen.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Dr. Jannik Matuschke, bis 1/2019