American Institute of Mathematical Sciences

Advanced
October  2018, 5(4): 331-341. doi: 10.3934/jdg.2018020

A non-iterative algorithm for generalized pig games

Fabián Crocce and  Ernesto Mordecki ,

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.

Keywords: Dice games, simple stochastic games, polynomial algorithm.
Mathematics Subject Classification: Primary: 91A15, 91A60; Secondary: 90C47.
Citation: Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics & Games, 2018, 5 (4) : 331-341. 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.Google Scholar

[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. Google Scholar

[3]

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

[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. Google Scholar

[5]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[14]

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

[15]

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

[16]

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

[17]

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

[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. Google Scholar

[19]

R. Tripathi, E. 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. Google Scholar

[20]

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

[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. Google Scholar

[22]

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

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.Google Scholar

[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. Google Scholar

[3]

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

[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. Google Scholar

[5]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[14]

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

[15]

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

[16]

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

[17]

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

[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. Google Scholar

[19]

R. Tripathi, E. 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. Google Scholar

[20]

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

[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. Google Scholar

[22]

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

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
Figure Options

Download full-size image

Download as PowerPoint slide

Algorithm1 
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
Table Options

Download as excel

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
Algorithm2 
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 Options

Download as excel

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]
Table Options

Download as excel

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$
Table Options

Download as excel

[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]

Antoine Hochart. An accretive operator approach to ergodic zero-sum stochastic games. Journal of Dynamics & Games, 2019, 6 (1) : 27-51. doi: 10.3934/jdg.2019003
[13]

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

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
[15]

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

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
[17]

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
[18]

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
[19]

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
[20]

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

 Impact Factor: 

Tools

Metrics

  • PDF downloads (27)
  • HTML views (369)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences