Stochastic multiplayer games : theory and algorithms
| Autor: | Ummels, Michael |
|---|---|
| Přispěvatelé: | Grädel, Erich |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
Computer Science::Computer Science and Game Theory
Teilspiel-perfektes Gleichgewicht subgame-perfect equilibrium infinite game TheoryofComputation_GENERAL complexity theory Nash-Gleichgewicht Komplexitätstheorie Nash equilibrium Informatik Unentscheidbarkeit stochastic game Stochastisches Spiel Unendliches Spiel ddc:004 |
| Zdroj: | Amsterdam : Pallas Publ. 174 S. : graph. Darst. (2010). = Zugl.: Aachen, Techn. Hochsch., Diss., 2010 |
| Popis: | Stochastic games provide a versatile model for reactive systems that are affected by random events. Intuitively, a play of such a game evolves by moving a token along the edges of a directed graph. Each vertex of the graph is either controlled by one of the players, or it is a stochastic vertex. Whenever the token arrives at a non-stochastic vertex, the player who controls this vertex must move the token to a successor vertex; when the token arrives at a stochastic vertex, a fixed probability distribution determines the next vertex. At the end of a play, every player receives a payoff. In our case, the possible payoffs of a single play for one player are just 0 and 1: each player either wins or loses a play. However, due to the presence of stochastic vertices, a player's expected payoff, i.e. her probability of winning, can be an arbitrary number between 0 and 1. This dissertation develops the algorithmic theory of stochastic multiplayer games. In particular, we analyse the computational complexity of finding Nash equilibria in these games. On the conceptual side, we argue that the computational complexity of equilibria should not only be measured by the complexity of finding an arbitrary equilibrium, but also by the complexity of finding equilibria with certain payoffs. Specifically, we single out the following decision problem, which we call NE, as a yardstick for the complexity of equilibria: Given a game as well as an upper and a lower threshold on the payoff, decide whether the game has an equilibrium whose payoff lies in-between the given thresholds. The main result of this thesis is that NE is undecidable, regardless whether one looks for an equilibrium in pure or randomised strategies. In practice, equilibria in simpler strategies are more desirable than equilibria in arbitrary pure or randomised strategies, whose behaviour may depend on the whole sequence of vertices seen so far. In particular, strategies that only depend on the current vertex, so-called stationary strategies (which might again be pure or randomised) are very appealing. We prove that, for many typical payoff functions, NE with respect to stationary strategies is both NP-hard and contained in PSPACE, whereas NE with respect to pure stationary strategies is NP-complete. Our analysis is completed by providing algorithms for several fragments of NE. For instance, we show that NE becomes decidable when one searches for an equilibrium where the expected payoff for each player is either 0 or 1, or when one searches for an equilibrium where all but one player receive expected payoff 1. Our algorithms are accompanied by hardness proofs, which provide (almost always matching) lower bounds on the complexities of the problems we consider. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|