Deterministic and Probabilistic Complexity of Mean Payoff Games

Modderman, Robert (2022) Deterministic and Probabilistic Complexity of Mean Payoff Games. Master's Thesis / Essay, Mathematics.

Preview	Text mMATH_2022_ModdermanR.pdf Download (504kB) | Preview
	Text Toestemming.pdf Restricted to Registered users only Download (120kB)

Abstract

In this thesis, we consider three computational problems on mean payoff games on weighted digraphs: (1) finding winning positions, (2) computing characteristic values, and (3) determining optimal strategies. We give a detailed analysis of the relations between (1), (2), and (3). These three problems are discussed from multiple perspectives following several strategies to develop faster methods, one of which selects candidate positional strategies and provides additional edges by means of reachability between cycles. We provide limiting examples for all methods. Additionally, for a fixed number of vertices, we prove that Zwick and Paterson’s algorithm to determine the winning positions runs in O(log M) time with error probability going to zero as M goes to infinity, where M is the maximum of the absolute values of the weights.

Item Type:	Thesis (Master's Thesis / Essay)
Supervisor name:	Lorscheid, O. and Grossi, D.
Degree programme:	Mathematics
Thesis type:	Master's Thesis / Essay
Language:	English
Date Deposited:	19 Jul 2022 07:27
Last Modified:	19 Jul 2022 07:27
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/27965

Actions (login required)

View Item