TY - UNPB

T1 - Computing threat points in irreducible ETP-ESP games

AU - Harmelink, Rogier Leon Alexander

AU - Joosten, Reinoud A.M.G.

PY - 2020/1/31

Y1 - 2020/1/31

N2 - In non-cooperative stochastic games, the threat point is the lowest possible Nash equilibrium when players force each other to receive the minimal reward possible. For repeated games the determination of the threat point seems trivial, but when looking at more complex stochastic games this does not hold. Frequency-dependent (FD) games are stochastic games for which the stage payoffs depend on a FD function, a so-called Endogenous Stage Payoff (ESP) game. Another type of FD games is when the transition probabilities between states are adjusted based on a FD function, these are called Endogenous Transition Probabilities (ETP) games. Incorporating these characteristics in stochastic games results in non-trivial determination of the threat point and therefore creates the need of an efficient threat point algorithm. In this paper we develop an algorithm which computes the threat point in irreducible ETP-ESP games with two players under the limiting average reward criterion. We start by describing an algorithm for a simple repeated game for which we later incorporate more complex elements in order to end up at an ETP-ESP game. Our algorithm can at best be described as an intelligent brute force method which computes a reasonably accurate threat point in a reasonable amount of computational time. The resulting threat point can be seen as a good approximation of the exact threat point while also giving an indication of the set of Nash equilibria.

AB - In non-cooperative stochastic games, the threat point is the lowest possible Nash equilibrium when players force each other to receive the minimal reward possible. For repeated games the determination of the threat point seems trivial, but when looking at more complex stochastic games this does not hold. Frequency-dependent (FD) games are stochastic games for which the stage payoffs depend on a FD function, a so-called Endogenous Stage Payoff (ESP) game. Another type of FD games is when the transition probabilities between states are adjusted based on a FD function, these are called Endogenous Transition Probabilities (ETP) games. Incorporating these characteristics in stochastic games results in non-trivial determination of the threat point and therefore creates the need of an efficient threat point algorithm. In this paper we develop an algorithm which computes the threat point in irreducible ETP-ESP games with two players under the limiting average reward criterion. We start by describing an algorithm for a simple repeated game for which we later incorporate more complex elements in order to end up at an ETP-ESP game. Our algorithm can at best be described as an intelligent brute force method which computes a reasonably accurate threat point in a reasonable amount of computational time. The resulting threat point can be seen as a good approximation of the exact threat point while also giving an indication of the set of Nash equilibria.

M3 - Working paper

BT - Computing threat points in irreducible ETP-ESP games

ER -