# American Institute of Mathematical Sciences

October  2018, 5(4): 331-341. 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, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020
##### References:

show all references

##### References:
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  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
 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
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.530592071 200 0.52152913 500 0.51362019 1000 0.50963900 1 Obtained by Neller and Presser [16]
 Target of the game ($N$) value of the game $v(N, N)$ 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]
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] 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: