Determining Nash Equilibria for Stochastic Positional Games with Discounted Payoffs
A class of discounted stochastic games is formulated and studied by applying the concept of positional games to Markov decision processes with expected total discounted reward criteria. Existence results of pure and mixed stationary Nash equilibria for th
- PDF / 140,172 Bytes
- 5 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 238 Views
2
Institute of Mathematics and Computer Science, Academy of Sciences, Moldova, Academy str., 5, 2028 Chisinau, Moldova [email protected] Institute for Theoretical Computer Science, Mathematics and Operations Research, Universit¨ at der Bundeswehr M¨ unchen, 85577 Neubiberg-m¨ unchen, Germany [email protected]
Abstract. A class of discounted stochastic games is formulated and studied by applying the concept of positional games to Markov decision processes with expected total discounted reward criteria. Existence results of pure and mixed stationary Nash equilibria for the considered class of discounted stochastic positional games are presented and an approach for determining the optimal strategies of the players is proposed. Keywords: Stochastic positional game ary strategy · Nash equilibrium
1
· Discounted payoffs · Station-
Introduction
In this paper we formulate and study a class of stochastic games by applying the concept of positional games to discounted Markov decision processes with finite state and action spaces. We consider Markov decision processes that may be controlled by several actors (players) as follows. The set of states of the system in a Markov process is divided into several disjoint subsets that represent the position sets for the corresponding players. Each player controls the process only in his position set via the feasible actions in the corresponding states. The aim of each player is to determine which action should be taken in each state of his position set in order to maximize his own discounted sum of step rewards. The step rewards in the states with respect to each player are known for an arbitrary feasible action in the corresponding states of the position sets. We consider the infinite horizon stochastic games and assume that players use stationary strategies of a selection of the action in the states, i.e. each player in his arbitrary position uses the same action for an arbitrary discrete moment of time. For the considered class of games we are seeking for a Nash equilibrium. We show that for stochastic positional games with discounted payoffs stationary Nash equilibria exist. Moreover, we show that for the considered class of games there exist stationary Nash equilibria in pure strategies. Based on these results we propose an approach for determining the optimal strategies of the players. c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 339–343, 2017. DOI: 10.1007/978-3-319-67504-6 24
340
2
D. Lozovanu and S. Pickl
Formulation of a Discounted Stochastic Positional Game
An n-player stochastic positional game with discounted payoffs is determined by the following elements: – a finite set of states X; – a partition X = X1 ∪ X2 ∪ · · · ∪ Xn of X, where Xi represents the position set of player i ∈ {1, 2, . . . , n}, Xi ∩ Xj = ∅ for i = j; – a finite set of actions A(x) for an arbitrary state x ∈ X; – a step reward ri (x, a) with respect to each player i ∈ {1, 2, . . . , n} for an arbitrary state x ∈ X and an arbitrary action a ∈ A(x); A(x)
Data Loading...
