License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07471.4
URN: urn:nbn:de:0030-drops-15274
URL: http://dagstuhl.sunsite.rwth-aachen.de/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:
07471.HalmanNir.ExtAbstract.1527.pdf (0.1 MB)

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:DagSemProc.07471.4,
  author =	{Halman, Nir},
  title =	{{Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1527},
  URN =		{urn:nbn:de:0030-drops-15274},
  doi =		{10.4230/DagSemProc.07471.4},
  annote =	{Keywords: Subexponential algorithm, LP-type framework}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI