doi: 10.3934/jdg.2018020

A non-iterative algorithm for generalized pig games

Centro de Matemática, Facultad de Ciencias, Universidad de la República, Iguá 4225, CP 11400, Montevideo, Uruguay

* Corresponding author: Ernesto Mordecki

Received  October 2017 Revised  September 2018 Published  October 2018

We provide a polynomial algorithm to find the value and an optimal strategy for a generalization of the Pig game. Modeled as a competitive Markov decision process, the corresponding Bellman equations can be decoupled leading to systems of two non-linear equations with two unknowns. In this way we avoid the classical iterative approaches. A simple complexity analysis reveals that the algorithm requires $O(\mathbf{s}\log\mathbf{s})$ steps, where $\mathbf{s}$ is the number of states of the game. The classical Pig and the Piglet (a simple variant of the Pig played with a coin) are examined in detail.

Citation: Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics & Games, doi: 10.3934/jdg.2018020
References:
[1]

D. Auger, P. Coucheney and Y. and Strozecki, Finding optimal strategies of almost acyclic simple stochastic games, Theory and applications of models of computation, Lecture Notes in Comput. Sci., 8402 (2014), 67–85.

[2]

M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, (2nd. rev. ed.) Springer, Berlin 2000. doi: 10.1007/978-3-662-04245-8.

[3]

A. Condon, The complexity of stochastic games, Information and Computation, 96 (1992), 203-224. doi: 10.1016/0890-5401(92)90048-K.

[4]

A. Condon, On algorithms for simple stochastic games, Advances in Computational Complexity Theory, J. Cai (Ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science AMS, 14 (1993), 51–71.

[5]

J. Filar and K. Vrieze, Competitive Markov Decision Processes, Springer, New York, 1997.

[6]

H. Gimbert and F. Horn, Simple stochastic games with few random vertices are easy to solve, Foundations of software science and computational structures, 5–19, Lecture Notes in Comput. Sci., 4962, Springer, Berlin. 2008 doi: 10.1007/978-3-540-78499-9_2.

[7]

J. Haigh and M. Roters, Optimal strategy in a dice game, Journal of Applied Probability, 37 (2000), 1110-1116. doi: 10.1239/jap/1014843089.

[8]

N. Halman, Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, 49 (2007), 37-50. doi: 10.1007/s00453-007-0175-3.

[9]

T. D. Hansen, P. B. Miltersen and U. Zwick, Strategy iteration is strongly polynomial for 2- player turn-based stochastic games with a constant discount factor, Innovations in Computer Science (ICS'11), (2011), 253–263.

[10]

A. J. Hoffman and R. M. Karp, On nonterminating stochastic games, Management Science, 12 (1966), 359-370. doi: 10.1287/mnsc.12.5.359.

[11]

R. Ibsen-Jensen and P. B. Miltersen, Solving simple stochastic games with few coin toss positions, Algorithms–ESA 20112, LNCS, 7501 (2012), 636–647. doi: 10.1007/978-3-642-33090-2_55.

[12]

G. Louchard, Recent studies on the dice race problem and its connections, Math. Appl. (Warsaw), 44 (2106), 63-86. doi: 10.14708/ma.v44i1.1124.

[13]

T. M. Liggett and S. A. Lippman, Stochastic games with perfect information and time average payoff, SIAM Review, 11 (1969), 604-607. doi: 10.1137/1011093.

[14]

J. MatoušekM. Sharir and E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996), 498-516. doi: 10.1007/BF01940877.

[15]

J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, New Jersey. 1944.

[16]

T. Neller and C. Presser, Optimal play of the dice game pig, The UMAP Journal, 25 (2004), 25-47.

[17]

M. Roters, Optimal stopping in a dice game, Journal of Applied Probability, 35 (1998), 229-235. doi: 10.1239/jap/1032192566.

[18]

L. S. Shapley, Stochastic games, Proceedings of the Natural Academy of Sciences, USA, 39 (1953), 1095-1100. doi: 10.1073/pnas.39.10.1953.

[19]

R. TripathiE. Valkanova and V. S. Anil Kumar, On strategy improvement algorithms for simple stochastic games, Journal of Discrete Algorithms, 9 (2011), 263-278. doi: 10.1016/j.jda.2011.03.007.

[20]

H. Tijms, Dice games and stochastic dynamic programming, Morfismos, 11 (2004), 1-14.

[21]

H. Tijms and J. van der Wal, A real-world stochastic two-person game, Probab. Engrg. Inform. Sci., 20 (2006), 599-608. doi: 10.1017/S0269964806060372.

[22]

O. J. VriezeS. H. TijsT. E. S. Raghavan and J. A. Filar, A finite algorithm for the switching control stochastic game, Operations-Research-Spektrum, 5 (1983), 15-24.

show all references

References:
[1]

D. Auger, P. Coucheney and Y. and Strozecki, Finding optimal strategies of almost acyclic simple stochastic games, Theory and applications of models of computation, Lecture Notes in Comput. Sci., 8402 (2014), 67–85.

[2]

M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, (2nd. rev. ed.) Springer, Berlin 2000. doi: 10.1007/978-3-662-04245-8.

[3]

A. Condon, The complexity of stochastic games, Information and Computation, 96 (1992), 203-224. doi: 10.1016/0890-5401(92)90048-K.

[4]

A. Condon, On algorithms for simple stochastic games, Advances in Computational Complexity Theory, J. Cai (Ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science AMS, 14 (1993), 51–71.

[5]

J. Filar and K. Vrieze, Competitive Markov Decision Processes, Springer, New York, 1997.

[6]

H. Gimbert and F. Horn, Simple stochastic games with few random vertices are easy to solve, Foundations of software science and computational structures, 5–19, Lecture Notes in Comput. Sci., 4962, Springer, Berlin. 2008 doi: 10.1007/978-3-540-78499-9_2.

[7]

J. Haigh and M. Roters, Optimal strategy in a dice game, Journal of Applied Probability, 37 (2000), 1110-1116. doi: 10.1239/jap/1014843089.

[8]

N. Halman, Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, 49 (2007), 37-50. doi: 10.1007/s00453-007-0175-3.

[9]

T. D. Hansen, P. B. Miltersen and U. Zwick, Strategy iteration is strongly polynomial for 2- player turn-based stochastic games with a constant discount factor, Innovations in Computer Science (ICS'11), (2011), 253–263.

[10]

A. J. Hoffman and R. M. Karp, On nonterminating stochastic games, Management Science, 12 (1966), 359-370. doi: 10.1287/mnsc.12.5.359.

[11]

R. Ibsen-Jensen and P. B. Miltersen, Solving simple stochastic games with few coin toss positions, Algorithms–ESA 20112, LNCS, 7501 (2012), 636–647. doi: 10.1007/978-3-642-33090-2_55.

[12]

G. Louchard, Recent studies on the dice race problem and its connections, Math. Appl. (Warsaw), 44 (2106), 63-86. doi: 10.14708/ma.v44i1.1124.

[13]

T. M. Liggett and S. A. Lippman, Stochastic games with perfect information and time average payoff, SIAM Review, 11 (1969), 604-607. doi: 10.1137/1011093.

[14]

J. MatoušekM. Sharir and E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996), 498-516. doi: 10.1007/BF01940877.

[15]

J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, New Jersey. 1944.

[16]

T. Neller and C. Presser, Optimal play of the dice game pig, The UMAP Journal, 25 (2004), 25-47.

[17]

M. Roters, Optimal stopping in a dice game, Journal of Applied Probability, 35 (1998), 229-235. doi: 10.1239/jap/1032192566.

[18]

L. S. Shapley, Stochastic games, Proceedings of the Natural Academy of Sciences, USA, 39 (1953), 1095-1100. doi: 10.1073/pnas.39.10.1953.

[19]

R. TripathiE. Valkanova and V. S. Anil Kumar, On strategy improvement algorithms for simple stochastic games, Journal of Discrete Algorithms, 9 (2011), 263-278. doi: 10.1016/j.jda.2011.03.007.

[20]

H. Tijms, Dice games and stochastic dynamic programming, Morfismos, 11 (2004), 1-14.

[21]

H. Tijms and J. van der Wal, A real-world stochastic two-person game, Probab. Engrg. Inform. Sci., 20 (2006), 599-608. doi: 10.1017/S0269964806060372.

[22]

O. J. VriezeS. H. TijsT. E. S. Raghavan and J. A. Filar, A finite algorithm for the switching control stochastic game, Operations-Research-Spektrum, 5 (1983), 15-24.

Figure 1.  Function $y = f_{b, a}(x)$ (solid line) intersects $x = f_{a, b}(y)$ (dashed line) at the solution $x = v(a, b)$, $y = v(b, a)$ in one instance of the Piglet game
Algorithm 1 General backward algorithm.
1: for $b$ from $1$ to $N$ do
2:   for $a$ from $1$ to $b$ do
3: Find $v(a, b, \tau)\colon 0\leq \tau <a$ and $v(b, a, \tau)\colon 0\leq \tau <b$
4:   end for
5: end for
Algorithm 1 General backward algorithm.
1: for $b$ from $1$ to $N$ do
2:   for $a$ from $1$ to $b$ do
3: Find $v(a, b, \tau)\colon 0\leq \tau <a$ and $v(b, a, \tau)\colon 0\leq \tau <b$
4:   end for
5: end for
Algorithm 2 Solving step 3 for fixed a, b.
1: for$i$ from $1$ to $a$ do
2:   Find the points defining $f_{a, b, i}$
3: end for
4: for $i$ from $1$ to $b$ do
5:   Find the points defining $f_{b, a, i}$
6: end for
7: Find $x$ and $y$ that solve system (7)
8: for $i$ from $1$ to $a-1$ do
9:   compute v(a, b, a-i)
10: end for
11: for $i$ from $1$ to $b-1$ do
12:   compute v(b, a, b-i)
13: end for
Algorithm 2 Solving step 3 for fixed a, b.
1: for$i$ from $1$ to $a$ do
2:   Find the points defining $f_{a, b, i}$
3: end for
4: for $i$ from $1$ to $b$ do
5:   Find the points defining $f_{b, a, i}$
6: end for
7: Find $x$ and $y$ that solve system (7)
8: for $i$ from $1$ to $a-1$ do
9:   compute v(a, b, a-i)
10: end for
11: for $i$ from $1$ to $b-1$ do
12:   compute v(b, a, b-i)
13: end for
Table 1.  Pig Game with different targets
Target of the game ($N$)value of the game $v(N, N)$
100.70942388
500.54615051
1000.530592071
2000.52152913
5000.51362019
10000.50963900
1 Obtained by Neller and Presser [16]
Target of the game ($N$)value of the game $v(N, N)$
100.70942388
500.54615051
1000.530592071
2000.52152913
5000.51362019
10000.50963900
1 Obtained by Neller and Presser [16]
Table 2.  Values of $v(a, b)$ for the piglet game with $N = 3$
[1]

Oliver Juarez-Romero, William Olvera-Lopez, Francisco Sanchez-Sanchez. A simple family of solutions for forest games. Journal of Dynamics & Games, 2017, 4 (2) : 87-96. doi: 10.3934/jdg.2017006

[2]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics & Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020

[3]

Jingzhen Liu, Ka-Fai Cedric Yiu. Optimal stochastic differential games with VaR constraints. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1889-1907. doi: 10.3934/dcdsb.2013.18.1889

[4]

Alain Bensoussan, Jens Frehse, Christine Grün. Stochastic differential games with a varying number of players. Communications on Pure & Applied Analysis, 2014, 13 (5) : 1719-1736. doi: 10.3934/cpaa.2014.13.1719

[5]

Lin Xu, Rongming Wang, Dingjun Yao. Optimal stochastic investment games under Markov regime switching market. Journal of Industrial & Management Optimization, 2014, 10 (3) : 795-815. doi: 10.3934/jimo.2014.10.795

[6]

Sylvain Sorin, Guillaume Vigeral. Reversibility and oscillations in zero-sum discounted stochastic games. Journal of Dynamics & Games, 2015, 2 (1) : 103-115. doi: 10.3934/jdg.2015.2.103

[7]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics & Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555

[8]

Beatris Adriana Escobedo-Trujillo, Alejandro Alaffita-Hernández, Raquiel López-Martínez. Constrained stochastic differential games with additive structure: Average and discount payoffs. Journal of Dynamics & Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008

[9]

Alain Bensoussan, Jens Frehse, Jens Vogelgesang. Systems of Bellman equations to stochastic differential games with non-compact coupling. Discrete & Continuous Dynamical Systems - A, 2010, 27 (4) : 1375-1389. doi: 10.3934/dcds.2010.27.1375

[10]

Beatris A. Escobedo-Trujillo. Discount-sensitive equilibria in zero-sum stochastic differential games. Journal of Dynamics & Games, 2016, 3 (1) : 25-50. doi: 10.3934/jdg.2016002

[11]

Qingmeng Wei, Zhiyong Yu. Time-inconsistent recursive zero-sum stochastic differential games. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1051-1079. doi: 10.3934/mcrf.2018045

[12]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117

[13]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

[14]

Hassan Najafi Alishah, Pedro Duarte. Hamiltonian evolutionary games. Journal of Dynamics & Games, 2015, 2 (1) : 33-49. doi: 10.3934/jdg.2015.2.33

[15]

Yonghui Zhou, Jian Yu, Long Wang. Topological essentiality in infinite games. Journal of Industrial & Management Optimization, 2012, 8 (1) : 179-187. doi: 10.3934/jimo.2012.8.179

[16]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control & Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010

[17]

Tyrone E. Duncan. Some linear-quadratic stochastic differential games for equations in Hilbert spaces with fractional Brownian motions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5435-5445. doi: 10.3934/dcds.2015.35.5435

[18]

Libin Mou, Jiongmin Yong. Two-person zero-sum linear quadratic stochastic differential games by a Hilbert space method. Journal of Industrial & Management Optimization, 2006, 2 (1) : 95-117. doi: 10.3934/jimo.2006.2.95

[19]

Alejandra Fonseca-Morales, Onésimo Hernández-Lerma. A note on differential games with Pareto-optimal NASH equilibria: Deterministic and stochastic models. Journal of Dynamics & Games, 2017, 4 (3) : 195-203. doi: 10.3934/jdg.2017012

[20]

Matthew Bourque, T. E. S. Raghavan. Policy improvement for perfect information additive reward and additive transition stochastic games with discounted and average payoffs. Journal of Dynamics & Games, 2014, 1 (3) : 347-361. doi: 10.3934/jdg.2014.1.347

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]