Author ORCID Identifier

https://orcid.org/0009-0000-0563-0181

Semester

Spring

Date of Graduation

2023

Document Type

Thesis

Degree Type

MS

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

K Subramani

Committee Member

Donald Adjeroh

Committee Member

Mohamed Hefeida

Committee Member

Xin Li

Committee Member

Piotr Wojciechowski

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.

Download

Share

COinS