@phdthesis{8080,
  abstract     = {{This thesis investigates approximate pure Nash equilibria in different game-theoretic models. In such an outcome, no player can improve her objective by more than a given factor through a deviation to another strategy. In the first part, we investigate two variants of Congestion Games in which the existence of pure Nash equilibria is guaranteed through a potential function argument. However, the computation of such equilibria might be hard. We construct and analyze approximation algorithms that enable the computation of states with low approximation factors in polynomial time. To show their guarantees we use sub games among players, bound the potential function values of arbitrary states and exploit a connection between Shapley and proportional cost shares. Furthermore, we apply and analyze sampling techniques for the computation of approximate Shapley values in different settings. In the second part, we concentrate on the existence of approximate pure Nash equilibria in games in which no pure Nash equilibria exist in general. In the model of Coevolving Opinion Formation Games, we bound the approximation guarantees for natural states nearly independent of the specific definition of the players' neighborhoods by applying a concept of virtual costs. For the special case of only one influential neighbor, we even show lower approximation factors for a natural strategy. Then, we investigate a two-sided Facility Location Game among facilities and clients on a line with an objective function consisting of distance and load. We show tight bounds on the approximation factor for settings with three facilities and infinitely many clients. For the general scenario with an arbitrary number of facilities, we bound the approximation factor for two promising candidates, namely facilities that are uniformly distributed and which are paired.}},
  author       = {{Feldotto, Matthias}},
  title        = {{{Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games}}},
  doi          = {{10.17619/UNIPB/1-588}},
  year         = {{2019}},
}

@misc{3851,
  author       = {{Koop, Samuel}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Congestion Games mit gewichteten Strategien}}},
  year         = {{2018}},
}

@misc{1186,
  author       = {{Kemper, Arne}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Pure Nash Equilibria in Robust Congestion Games via Potential Functions}}},
  year         = {{2018}},
}

@misc{1187,
  author       = {{Nachtigall, Marcel}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Scenario-driven Strategy Analysis in a n-player Composition Game Model}}},
  year         = {{2018}},
}

@misc{1188,
  author       = {{Kempf, Jérôme}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Learning deterministic bandit behaviour form compositions}}},
  year         = {{2018}},
}

@misc{1073,
  author       = {{Nachtigall, Simon}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Sortieren dynamischer Daten}}},
  year         = {{2017}},
}

@misc{1074,
  author       = {{Pukrop, Simon}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Robuste Optimierung in Congestion Games}}},
  year         = {{2017}},
}

@misc{1080,
  author       = {{Bürmann, Jan}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Complexity of Signalling in Routing Games under Uncertainty}}},
  year         = {{2017}},
}

@misc{1081,
  author       = {{Vijayalakshmi, Vipin Ravindran}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Bounding the Inefficiency of Equilibria in Congestion Games under Taxation}}},
  year         = {{2017}},
}

@phdthesis{200,
  author       = {{Drees, Maximilian}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Existence and Properties of Pure Nash Equilibria in Budget Games}}},
  year         = {{2016}},
}

@misc{210,
  author       = {{Leder, Lennart}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Congestion Games with Mixed Objectives}}},
  year         = {{2016}},
}

@misc{1082,
  author       = {{Handirk, Tobias}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Über die Rolle von Informationen in Verkehrsnetzwerken}}},
  year         = {{2016}},
}

@misc{251,
  author       = {{Pfannschmidt, Karlson}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Solving the aggregated bandits problem}}},
  year         = {{2015}},
}

@misc{316,
  author       = {{Pautz, Jannis}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Budget Games with priced strategies}}},
  year         = {{2015}},
}

@misc{277,
  author       = {{Kothe, Nils}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk}}},
  year         = {{2015}},
}

@misc{373,
  author       = {{Pahl, David}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Reputationssysteme für zusammengesetzte Dienstleistungen}}},
  year         = {{2014}},
}