2026-09-22T23:11:55Z https://opus4.kobv.de/opus4-uni-passau/oai

oai:kobv.de-opus4-uni-passau:1968 2025-12-09 bibliography:false doc-type:PhDThesis open_access ddc ddc:510

Multi-Leader Congestion Games with an Adversary 0009-0000-8006-9216 Mona Henle 510 Spieltheorie Congestion Games Game Theory Adversary In this thesis, we introduced a congestion game with multiple leaders and a single follower (adversary) which is motivated by security applications with congestion effects. Our objective was to understand the result and the impact of selfish acting individuals in these games. In this regard, we analyzed the existence, the computation and the quality of (approximate) pure Nash equilibria. First, we observed that an exact pure Nash equilibrium always exists in the resulting strategic game among the leaders if the resource cost coefficients are identical and the underlying congestion game is a matroid congestion game. If one of these two conditions is not fulfilled, the existence of PNE is not ensured anymore in general. Consequently, we focused on approximate equilibria. For the case of symmetric singleton strategies, one of our main result established that K ≈ 1.1974, the unique solution of a cubic polynomial equation, is the smallest possible factor such that the existence of a K-approximate equilibrium is guaranteed for all instances of the game. To this end, we presented an efficient algorithm which computes a K-approximate PNE. Furthermore, we showed that the factor K is tight by providing an instance where no α-approximate PNE with α < K exists. However, for a specific symmetric singleton instance there might be a better α-approximate PNE, i.e., with α < K. A given instance could even admit an exact PNE. We provided therefore a polynomial time procedure that computes a best approximate PNE of a given instance. In particular, this procedure can verify the existence of an exact PNE in a given instance efficiently and, if it exists, can also determine the corresponding load vector. Finally, for symmetric singleton instances with two resources, we compared the total cost of a best (cheapest) and worst (most expensive) PNE to the total cost of an optimal outcome, termed by the price of stability and the price of anarchy, respectively. In particular, we verified that the PoS and the PoA are 4/3. Universität Passau Passau Innstrasse 29, 94032 Passau Tobias Harks Max Klimm Britta Peis 2025-07-21 2025-12-09 PhDThesis Text urn:nbn:de:bvb:739-opus4-19683 application/pdf eng Creative Commons - CC BY - Namensnennung 4.0 International thesis.doctoral Universität Passau Passau Fakultät für Informatik und Mathematik 1 https://opus4.kobv.de/opus4-uni-passau/oai/container/index/docId/1968 https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/1968