Back to search

West Virginia University

An Empirical Analysis of Algorithms for Simple Stochastic Games

Abstract

dc:description.abstract

This thesis presents the findings of a computational study on algorithms for Simple Stochastic Games (SSG). Simple Stochastic Games are a restriction of the Shapley stochastic model motivated by their applications in AI planning, logic synthesis, and theoretical computer science. This thesis seeks to empirically assess the performance of these algorithms to compensate for their lack of strong complexity results. Where applicable, we include both variations of algorithms where stable strategies are computed by a linear-programming and naive approach. These algorithms are evaluated on random inputs, in addition to specific difficult cases that were identified experimentally. We are interested in identifying difficult cases in particular because the worst case for the best performing algorithm, the Hoffman-Karp algorithm, is not known. The Hoffman-Karp algorithm for SSG is generally thought to take exponential iterations in the worst case, but this has not been proven. Despite both exhaustive and randomized searches of possible inputs, a case taking more than a linear number of iterations was not found. In this linear case, the otherwise fastest algorithms become inefficient and the naive algorithms surpass their linear-programming counterparts.

Degree

thesis:*
Name thesis:degree_name
MS
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Lane Department of Computer Science and Electrical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Klingler, Cody William
Contributors dc:contributor
  • K Subramani
  • Donald Adjeroh
  • Mohamed Hefeida
  • Xin Li
  • Piotr Wojciechowski

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Identifier
<p><a href="https://orcid.org/0009-0000-0563-0181">https://orcid.org/0009-0000-0563-0181</a></p>
https://researchrepository.wvu.edu/etd/11772

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Klingler, Cody William. An Empirical Analysis of Algorithms for Simple Stochastic Games. Thesis thesis, https://doi.org/10.33915/etd.11772