License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-15274
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1527/
Go to the corresponding Portal


Halman, Nir

Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems

pdf-format:
Document 1.pdf (105 KB)


Abstract

We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl for LP-type problems, we obtain the first strongly subexponential solution for SSGs (a strongly subexponential algorithm has only been known for binary SSGs). Using known reductions between various games, we achieve the first trongly subexponential solutions for Discounted and Mean Payoff Games. We also give alternative simple proofs for the best known upper bounds for Parity Games and binary SSGs. To the best of our knowledge, the LP-type framework has been used so far only in order to yield linear or close to linear time algorithms for various problems in computational geometry and location theory. Our approach demonstrates the applicability of the LP-type framework in other fields, and for achieving subexponential algorithms. This work has been published in Algorithmica, volume 49 (September 2007), pages 37-50

BibTeX - Entry

@InProceedings{halman:DSP:2008:1527,
  author =	{Nir Halman},
  title =	{Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems},
  booktitle =	{Equilibrium Computation},
  year =	{2008},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  number =	{07471},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1527},
  annote =	{Keywords: Subexponential algorithm, LP-type framework}
}

Keywords: Subexponential algorithm, LP-type framework
Seminar: 07471 - Equilibrium Computation
Issue Date: 2008
Date of publication: 04.06.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI