\documentstyle[aps,prl,multicol,graphicx,epsf]{revtex} \title{Parity and Ruin in a Stochastic Game} \author{E.~Ben-Naim$\dag$ and P.~L.~Krapivsky$\ddag$} \address{$\dag$Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM 87545, USA} \address{$\ddag$Center for Polymer Studies and Department of Physics, Boston University, Boston, MA 02215, USA} \begin{document} \maketitle \begin{abstract} \noindent We study an elementary two-player card game where in each round players compare cards and the holder of the card with the smaller value wins. Using the rate equations approach, we treat the stochastic version of the game in which cards are drawn randomly. We obtain an exact solution for arbitrary initial conditions. In general, the game approaches a steady state where the card value densities of the two players are proportional to each other. The leading small value behavior of the initial densities determines the corresponding proportionality constant, while the next correction governs the asymptotic time dependence. The relaxation toward the steady state exhibits a rich behavior, e.g., it may be algebraically slow or exponentially fast. Moreover, in ruin situations where one player eventually wins all cards, the game may even end in a finite time. \medskip\noindent {PACS numbers: 02.50.Ey, 05.40.-a, 51.10.+y, 89.65.-s} \end{abstract} \begin{multicols}{2} \noindent Numerous phenomena in social and economic sciences involve multiple interacting agents. The interaction between these agents often leads to exchange of quantities such as capital, goods, political opinions, etc.~\cite{lig,soc,ikr,CMV,fkb}. Games are widely employed in modelling collective behavior especially in the context of economics\cite{vN}, with recent examples ranging from evolution of trading strategies in a stock market \cite{cz,cmz,c} to bidding in auctions \cite{dr}. Games can often be regarded as many body exchange processes resembling collision processes \cite{col}, and therefore their dynamics may be described by suitably adapted kinetic theories \cite{rl}. Here, we investigate a stochastic null strategy card game. By considering the ``thermodynamic limit'' where the initial number of cards is infinite, we show that rate equations provide a natural framework for analyzing game dynamics. This study was motivated by a recent auction bidding model where two agents compare bids. The agent offering the smaller bid wins, and the second agent replaces the losing bid with a randomly drawn bid \cite{dr}. This auction model demonstrates the utility of rate equations in describing game dynamics. The corresponding rate equations admit a family of steady state solutions and numeric integration shows that the dynamics selects one particular solution \cite{dr}. In this study, we consider a natural simplification of this model which is characterized by additional conservation laws. We show that the dynamics become analytically tractable, and we relate the selection criteria to extremal statistics of the initial conditions. Our toy auction model is nothing but a stochastic adaptation of the elementary card game ``war''. This two-player game is defined as follows. Each player starts with a certain number of cards. At each round players draw a card randomly from their deck and compare the card values. The holder of the card with the smallest value wins the round and gets both cards. This is repeated ad infinitum or until one of the players gains all cards. We primarily consider continuous distributions of card values where there is a winner in each round. Our main result is that one specific aspect of the initial card distribution, namely the small value extremal statistics governs the dynamics of the game. Let us denote by $A$ and $B$ the two players, and let the initial card value densities be $a_0(x)$ and $b_0(x)$, respectively. In the long time limit, a steady state is approached with the card value densities of both players being equal to a fraction of the total card value density. For instance, the limiting card value density of player $A$ is $a_\infty(x)=\alpha [a_0(x)+b_0(x)]$. While a family of steady state solutions characterized by the parameter $0\leq\alpha\leq 1$ is in principle possible, the leading small value behavior of the initial distributions selects a specific value $\alpha=\lim_{x\to 0}{a_0(x)\over a_0(x)+b_0(x)}$. Moreover, the next leading correction determines how the system approaches the steady state. The corresponding time dependent behavior may be algebraic or exponential. Interesting behaviors also occur when one player captures all cards. In this case, the game duration may be finite or infinite. Additionally, using numerical simulations we show that the theoretical predictions concerning the game duration extend to deterministic realizations of the game. Let the initial numbers of cards of player $A$ whose values lie in the range $(x, x+dx)$ be $N_A(x)dx$ (and similarly for $B$), and let the total number of cards be $N$. We shall take the thermodynamic limit $N_A(x),N_B(x),N\to\infty$ and focus on $a(x,t)$ and $b(x,t)$, the densities of cards with value $x$ at time $t$ for players $A$ and $B$, respectively. These densities evolve according to the rate equations \begin{equation} \label{rate} {\partial\over\partial t} a(x,t)=R(x,t), \qquad {\partial\over\partial t} b(x,t)=-R(x,t), \end{equation} with the gain (loss) term $R(x,t)$ given by \begin{eqnarray*} R={1\over A(t)B(t)} \left[b(x,t)\!\int_0^x\!\! dy\,a(y,t)-a(x,t)\!\int_0^x\!\! dy\, b(y,t)\right]. \end{eqnarray*} Here \begin{equation} \label{ab} A(t)=\int_0^\infty dx\, a(x,t), \qquad B(t)=\int_0^\infty dx\, b(x,t) \end{equation} are the fraction of cards possessed by players $A$ and $B$, respectively. Clearly, \begin{equation} \label{ab1} A(t)+B(t)=1. \end{equation} The rate equations (\ref{rate}) reflect the nature of the game as the rate by which player A gains (loses) cards of value $x$ is proportional to the fraction of his opponent's cards with value larger (smaller) than $x$. As mentioned above, there is always a winner as the cards are never identical when the value $x$ is continuous (the complementary discrete case is treated separately). The overall factor $[A(t)B(t)]^{-1}$ ensures that on average, every opposing pair of cards comes into play once per unit time. The minimal card value was tacitly set to zero as the process is invariant under the transformation $x\to x + {\rm const}$. Besides the obvious conservation law (\ref{ab1}), two other conservation laws underlie the process. First, the total number of cards of a given value is conserved, \begin{equation} \label{cons} a(x,t)+b(x,t)=u_0(x), \end{equation} where $u_0(x)=a_0(x)+b_0(x)$ is the initial total density ($a_0(x)\equiv a(x,t=0)$, and similarly for $B$). Second, the density of the minimal card value remains constant throughout the evolution: $a(0,t)=a_0(0)$. To determine the steady state behavior we introduce the cumulative distributions \hbox{${\cal A}(x,t)=\int_0^x dy\, a(y,t)$} and \hbox{${\cal B}(x,t)=\int_0^x dy\, b(y,t)$}. These cumulative distributions satisfy ${\cal A}'/{\cal A}={\cal B}'/{\cal B}$ in the long time limit. Therefore, ${\cal A}_\infty(x)\propto {\cal B}_\infty(x)$, and consequently, the limiting card value densities, \hbox{$a_\infty(x)={\cal A}'_\infty(x)$} and \hbox{$b_\infty(x)={\cal B}'_\infty(x)$}, are proportional to each other. The conservation law (\ref{cons}) implies that each limiting card density equals a fraction of the total card value density \begin{eqnarray} \label{final} a_\infty(x)=\alpha u_0(x),\qquad b_\infty(x)=(1-\alpha) u_0(x). \end{eqnarray} In principle, for a given total card value density $u_0(x)$, there is a family of steady state solutions characterized by the parameter $\alpha$ which lies in the range \hbox{$0\leq\alpha\leq 1$}. Moreover, initial conditions where the densities are proportional to each other, do {\em not} evolve regardless of $\alpha$. Still, for a given initial condition a specific $\alpha$ is selected. The selected $\alpha$ is easily found for a class of initial conditions with non-vanishing minimal card densities, $u_0(0)>0$. Consider the density of the smallest-value cards ($x=0$). Equation (\ref{final}) gives $a_\infty(0)=\alpha u_0(0)$, while the second conservation law implies $a_\infty(0)=a_0(0)$, and hence \hbox{$\alpha=a_0(0)/[a_0(0)+b_0(0)]$}. This simple argument demonstrates that the density of the smallest-value cards governs the outcome of the game. In the following, we solve for the full time dependent behavior and show that in general, the small-$x$ asymptotics of the two distributions dictates the magnitude of $\alpha$. To solve the time dependent behavior, we make two simplifying transformations. First, the overall rate by which the exchange occurs $[A(t)B(t)]^{-1}$ can be absorbed into a modified time variable $\tau$, defined via \begin{equation} \label{tau} \tau=\int_0^t ds\, \left[A(s)B(s)\right]^{-1}. \end{equation} The second transformation essentially reduces any total density $u_0(x)$ to a uniform density by introducing the variable $\xi$ \begin{equation} \label{xi} \xi=\int_0^x dy\,u_0(y). \end{equation} The transformed card value densities, $\bar a(\xi,\tau)$ and $\bar b(\xi,\tau)$, are found from the relations \hbox{$\bar{a}(\xi,\tau)\,d\xi=a(x,t)\,dx$} and \hbox{$\bar{b}(\xi,\tau)\,d\xi=b(x,t)\,dx$}. Clearly, the transformed densities satisfy \hbox{$\bar{a}(\xi,\tau)=a(x,t)/u_0(x)$} and \hbox{$\bar{b}(\xi,\tau)=b(x,t)/u_0(x)$}. In the following, we shall omit the bar. The conservation law (\ref{cons}) becomes \begin{equation} \label{norm} a(\xi,\tau)+b(\xi,\tau)=1, \end{equation} i.e., the transformed total density is uniform on the interval [0,1] (note that Eqs.~(\ref{ab1}) and (\ref{xi}) imply $0\leq \xi\leq 1$). The above transformations simplify the evolution equations, and given the linear dependence (\ref{norm}), it suffices to solve for $a$ \begin{eqnarray*} {\partial \over \partial \tau}a(\xi,\tau) =b(\xi,\tau)\!\int_0^\xi\!\! d\eta\,a(\eta,\tau)-a(\xi,\tau)\! \int_0^\xi\!\! d\eta\,b(\eta,\tau). \end{eqnarray*} Replacing $b(\xi,\tau)$ with $1-a(\xi,\tau)$ linearizes this equation \hbox{${\partial \over \partial \tau}a(\xi,\tau)=\int_0^\xi \!d\eta\,a(\eta,\tau)-\xi a(\xi,\tau)$}, and differentiating with respect to $\xi$ yields further simplification \begin{equation} \left({\partial \over \partial \tau}+\xi\right) {\partial \over \partial \xi}a(\xi,\tau)=0. \end{equation} Integrating over $\tau$ and then over $\xi$ we arrive at our primary result, the exact time dependent solution for arbitrary initial conditions: \begin{equation} \label{solution} a(\xi,\tau)=\alpha+\int_0^{\xi} d\eta\, a_0'(\eta)\,e^{-\eta\tau}. \end{equation} Hereinafter we utilize the notations \hbox{$a_0(\xi)\equiv a(\xi,\tau=0)$}, \hbox{$a_0'(\xi)\equiv {d \over d \xi}a_0(\xi)$}, and $\alpha=a_0(\xi=0)$. Let us again consider the steady state. In the long time limit $\tau\to\infty$, the integral in (\ref{solution}) vanishes and the densities become uniform $a(\xi,\tau)\to \alpha$ and $b(\xi,\tau)\to 1-\alpha$. Hence, in terms of the original variable $x$, both densities are proportional to $u_0(x)$ according to Eq.~(\ref{final}), with \hbox{$\alpha=a_0(\xi=0)=a_0(x=0)/u_0(x=0)$}. Even when $u_0(x)$ vanishes or diverges as $x\to 0$, the parameter $\alpha$ is well-defined and using l'Hopital rule, it is given by \begin{equation} \label{alpha} \alpha=\lim_{x\to 0} {a_0(x)\over a_0(x)+b_0(x)}. \end{equation} Thus, if the two distributions exhibit different leading behaviors, say \hbox{$\lim_{x\to 0} b_0(x)/a_0(x)=0$}, then player $A$ eventually ruins player $B$. Hence, from the $x\to 0$ asymptotics of the initial densities one can infer which of the family of solutions (\ref{final}) is eventually selected by the dynamics. We now study the approach to the steady state. First, we analyze the temporal behavior of the total fractions of cards possessed by each player. For example, the fraction of cards possessed by player $A$ is \hbox{$A(\tau)=\int_0^1 d\xi\, a(\xi,\tau)$}. Combining this with Eq.~(\ref{solution}) we obtain \begin{equation} \label{Atau} A(\tau)=\alpha+\int_0^1 d\xi\, (1-\xi)\,a_0'(\xi)\, e^{-\xi\tau}. \end{equation} While the steady state behavior is determined by the leading small argument behavior of $a_0(\xi)$, the relaxation toward the final state is governed by the correction to the leading behavior. Let us consider the following small argument behavior \begin{equation} \label{dens} a_0(\xi)\simeq\alpha+\gamma \xi^{\delta}\qquad \xi\to 0, \end{equation} with $\delta>0$. Substituting this into Eq.~(\ref{Atau}) we arrive at a simple power-law behavior: \hbox{$A(\tau)-\alpha\simeq\gamma\Gamma(\delta+1)\tau^{-\delta}$} where $\Gamma(a)$ is the Gamma function. In terms of the actual time variable $t$, a richer variety of behaviors is exhibited. First, suppose that the system approaches an active steady state, i.e., $0<\alpha<1$. Then from Eq.~(\ref{tau}) we obtain \hbox{$t\to\alpha(1-\alpha)\tau$}, and therefore the above asymptotics of $A(\tau)$ becomes \begin{equation} A(t)-\alpha\simeq Ct^{-\delta}, \qquad t\to \infty \end{equation} with $C=\gamma\Gamma(\delta+1)[\alpha(1-\alpha)]^{\delta}$. Hence, when the system reaches the active steady state the approach is generally algebraic. Next, suppose that one player, say $A$, eventually ruins the opponent, i.e., $\alpha=1$. Then \hbox{$dt/d\tau\sim B(\tau)\sim \tau^{-\delta}$} and consequently, $t\sim \tau^{1-\delta}$. Therefore, for $\delta\leq 1$ representing weak initial advantage of the eventual winner, the game duration is infinite: \begin{equation} 1-A(t)\sim \cases{t^{-{\delta\over 1-\delta}}&$\delta<1;$\cr e^{-{\rm const}\times t}&$\delta=1$.\cr} \end{equation} In the complementary situation of strong initial advantage for the eventual winner, $\delta>1$, the game duration is finite: \begin{equation} \label{finite} A(t_f)=1. \end{equation} The terminal time can be determined from the integral \hbox{$t_f=\int_0^\infty d\tau A(\tau)\left[1-A(\tau)\right]$}. Using Eq.~(\ref{Atau}) and recalling that $\alpha=1$ yields this time as an explicit function of the initial conditions \begin{eqnarray} \label{tf} t_f=&-&\int_0^1 d\xi\,{1-\xi\over \xi}\,a_0'(\xi)\\ &-&\int_0^1 \int_0^1 d\xi_1\,d\xi_2\, {(1-\xi_1)(1-\xi_2)\over \xi_1+\xi_2}\, a_0'(\xi_1)\,a_0'(\xi_2).\nonumber \end{eqnarray} For example, the initial density $a_0(\xi)=1-\xi^2$ yields $t_f={2\over 15}+{16\over 15}\,\ln 2\approx 0.87269$. Additionally, the time dependent approach toward the final state is algebraic, \begin{equation} 1-A(t)\sim (t_f-t)^{\delta\over\delta-1}, \end{equation} sufficiently close to the terminal time $t\to t_f$. As expected, the density decreases linearly with time when the disparity between the two players becomes very large in the limit $\delta\to\infty$. Thus if the system approaches a trivial steady state with one player winning all cards, the temporal behavior can be algebraically slow or exponentially fast. Moreover, every positive power can be realized. Remarkably, if the initial disparity between the two players is sufficiently large, the game ends in a finite time. Interestingly, such disparity is expressed solely in terms of the density of the cards with the smallest value while the initial densities of the rest of the cards are irrelevant to the game outcome. Next, we analyze the time dependent evolution of the entire card value density. Evaluating the leading behavior of the density (\ref{solution}) in the long time limit, we find that the density exhibits a boundary layer structure \begin{equation} a(\xi,\tau)-\alpha\simeq \cases{\gamma\xi^\delta&$\xi\ll \tau^{-1}$;\cr \gamma\Gamma(\delta+1)\tau^{-\delta}&$\xi\gg \tau^{-1}$.\cr} \end{equation} Thus, the initial densities of cards whose values exceed the (decreasing) threshold value $\xi_0\sim \tau^{-1}$ are already forgotten, the density $a(\xi,\tau)$ is uniform and the remnant relaxation is indistinguishable from the relaxation of the total fraction of cards $A(\tau)$. In contrast, cards whose values are smaller than the threshold value $\xi_0\sim \tau^{-1}$ have yet to exchange hands and hence, are still dominated by the initial distribution. We now briefly discuss the case where the number of card values is finite, say equals to $k$. Here, rounds may end in a draw and in such a case both players simply keep their cards. Mathematically, the card value densities are discrete distributions \begin{eqnarray} \label{disc} a(x,t)&=&\sum_{n=1}^k a_n(t)\delta(x-x_n),\\ b(x,t)&=&\sum_{n=1}^k b_n(t)\delta(x-x_n),\nonumber \end{eqnarray} with $x_1=0$ and $x_n1$ one therefore predicts a duration \begin{equation} \label{diffuse} T_f\sim N^2, \end{equation} where $T_f$ is the number of rounds. The duration in the marginal $\delta=1$ case can be estimated using the average time it takes for player $B$ to get down to one card $B(t)=N^{-1}$. Utilizing the exponential decay of $B(t)$, we find that there is an additional logarithmic dependence, $T_f\sim N^2\ln N$, in this case. Results of Monte Carlo simulations are consistent with these predictions. In the simulations, each player starts with $N$ cards whose values are drawn from a uniform distribution in the range $0