Models and Algorithms for Multi-Level Congestion and Security Problems

• Applicant: Professor Dr. Tobias Harks, since 1/2019
• Subject Area: Theoretical Computer Science
• Term: since 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 417282269

Strategic acts of sabotage and terrorism pose an increasing threat to important infrastructures and their users. This proposal aims at the design of models and algorithms for multi-level congestion and security games that allow for planning infrastructures that are robust against such attacks. In these models, we take the role of a planner, who in the first level designs the infrastructure, which is represented by a network (e.g., a public transit system or emergency exit ways in a stadium). Then, in the second level, users operate on this infrastructure according to their own selfish interests. Finally, an attacker, observing the distribution of users in the network, strategically attacks the infrastructure so as to cause as much harm as possible (e.g., affecting as many people as possible).Solving the resulting multi-level optimization problems is computationally very challenging, in particular due to non-convexities caused by the multi-level structure. We therefore propose a new concept of level-wise approximation that allows to relax optimality requirements at each level individually. Using this paradigm, we hope to devise algorithms that efficiently compute near-optimal solutions.An additional challenge arises when taking into account the interplay of congestion effects caused by the users’ selfish action and their anticipation of the attacker’s action. An important part of our project therefore is to investigate bilevel congestion games, i.e., congestion games in which users take their choices taking into account both congestion caused by other users and the actions of a lower level attacker who will strike at the most-frequented parts of the infrastructure.Combining the insights gained on approximating multi-level network problems and congestion games, we then aim to solve multi-level network security games with congestion effects using a mix of approximation algorithms, heuristics, and exact methods, which we finally investigate in a study based on realistic data sets.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Dr. Jannik Matuschke, until 1/2019