
-
Previous Article
Technology transfer: Barriers and opportunities
- JDG Home
- This Issue
-
Next Article
Delegation principle for multi-agency games under ex post equilibrium
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 |
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.
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.
|

Algorithm 1 General backward algorithm. |
1: for |
2: for |
3: Find |
4: end for |
5: end for |
Algorithm 1 General backward algorithm. |
1: for |
2: for |
3: Find |
4: end for |
5: end for |
Algorithm 2 Solving step 3 for fixed a, b. |
1: for |
2: Find the points defining |
3: end for |
4: for |
5: Find the points defining |
6: end for |
7: Find |
8: for |
9: compute v(a, b, a-i) |
10: end for |
11: for |
12: compute v(b, a, b-i) |
13: end for |
Algorithm 2 Solving step 3 for fixed a, b. |
1: for |
2: Find the points defining |
3: end for |
4: for |
5: Find the points defining |
6: end for |
7: Find |
8: for |
9: compute v(a, b, a-i) |
10: end for |
11: for |
12: compute v(b, a, b-i) |
13: end for |
Target of the game ( | value of the game |
10 | 0.70942388 |
50 | 0.54615051 |
100 | 0.530592071 |
200 | 0.52152913 |
500 | 0.51362019 |
1000 | 0.50963900 |
1 Obtained by Neller and Presser [16] |
Target of the game ( | value of the game |
10 | 0.70942388 |
50 | 0.54615051 |
100 | 0.530592071 |
200 | 0.52152913 |
500 | 0.51362019 |
1000 | 0.50963900 |
1 Obtained by Neller and Presser [16] |
[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
Other articles
by authors
[Back to Top]