A non-iterative algorithm for generalized pig games

Fabián Crocce; Ernesto Mordecki

doi:10.3934/jdg.2018020

Article Contents

2018, Volume 5, Issue 4: 331-341. Doi: 10.3934/jdg.2018020

This issue Previous Article Delegation principle for multi-agency games under ex post equilibrium Next Article Technology transfer: Barriers and opportunities

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
* Corresponding author: Ernesto Mordecki

Received: October 2017

Revised: September 2018

Published: November 2018

Abstract / Introduction Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 91A15, 91A60; Secondary: 90C47.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Table 1. Pig Game with different targets

Target of the game ($N$)	value of the game $v(N, N)$
10	0.70942388
50	0.54615051
100	0.53059207¹
200	0.52152913
500	0.51362019
1000	0.50963900
¹ Obtained by Neller and Presser [16]

| Show Table

DownLoad: CSV

Table 2. Values of $v(a, b)$ for the piglet game with $N = 3$

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.