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 and 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.

[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šek, M. 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. 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.

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

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šek, M. 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. 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.

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

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 and 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 and 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 and 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 and Applied Analysis, 2014, 13 (5) : 1719-1736. doi: 10.3934/cpaa.2014.13.1719
[5]

Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics and Games, 2021  doi: 10.3934/jdg.2021021
[6]

Samuel Drapeau, Peng Luo, Alexander Schied, Dewen Xiong. An FBSDE approach to market impact games with stochastic parameters. Probability, Uncertainty and Quantitative Risk, 2021, 6 (3) : 237-260. doi: 10.3934/puqr.2021012
[7]

Jiequn Han, Ruimeng Hu, Jihao Long. Convergence of deep fictitious play for stochastic differential games. Frontiers of Mathematical Finance, , () : -. doi: 10.3934/fmf.2021011
[8]

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

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

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

Matt Barker. From mean field games to the best reply strategy in a stochastic framework. Journal of Dynamics and Games, 2019, 6 (4) : 291-314. doi: 10.3934/jdg.2019020
[12]

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

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 and Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008
[14]

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

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

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

Ryoji Sawa. Stochastic stability in the large population and small mutation limits for coordination games. Journal of Dynamics and Games, 2021  doi: 10.3934/jdg.2021015
[18]

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

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

Carlos Hervés-Beloso, Emma Moreno-García. Market games and walrasian equilibria. Journal of Dynamics and Games, 2020, 7 (1) : 65-77. doi: 10.3934/jdg.2020004

 Impact Factor: 

Tools

Metrics

  • PDF downloads (190)
  • HTML views (422)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy