University of Twente Student Theses


Computing threat points in two-player ETP-ESP games

Harmelink, R.L.A. (2019) Computing threat points in two-player ETP-ESP games.

[img] PDF
Abstract:This thesis focuses on the development of algorithms for computing the threat point in Frequency-Dependent-games, with the Endogenous Transition Probabilities (ETP) Endogenous Stage Payoffs (ESP) game as the most complex type of game. We limit ourselves to two-state, two-player ergodic stochastic games with or without a FD payoff. Also incorporated into an algorithm are so-called Endogenous Transition Probabilities, i.e., transition probabilities that depend on the history of the play. Several algorithms have been developed, one of them (SciPy algorithm) only works on non-FD Type I games while the other (Relative Value Iteration algorithm) is limited to use on non-FD Type II games. The Jointly-Convergent Pure-Strategy algorithm works on the broad spectrum of stochastic games described in this thesis, i.e., (non)-FD Type I, Type II and Type III games. We test the algorithms in terms of speed and accuracy and reflect on them including a disquisition of the risks surrounding some of the algorithms. We find that the SciPy algorithm is superior to the Jointly-Convergent Pure-Strategy algorithm in terms of accuracy and speed when computing the threat point in non-FD Type I games. The Relative Value Iteration algorithm works better in terms of accuracy when compared to the Jointly-Convergent Pure-Strategy algorithm but lags in terms of speed. The Jointly-Convergent Pure-Strategy algorithm fits all types of games while finding reasonably accurate solutions in a reasonable time.
Item Type:Essay (Master)
Faculty:BMS: Behavioural, Management and Social Sciences
Subject:31 mathematics, 54 computer science, 83 economics
Programme:Industrial Engineering and Management MSc (60029)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page