Parrondo's paradox

Parrondo's paradox is a paradox in game theory and is often described as: A losing strategy that wins. It is named after its creator Juan Parrondo, a Spanish physicist. Mathematically a more involved statement is given as:

Given two games, each with a higher probability of losing than winning, it is possible to construct a winning strategy by playing the games alternately.

The paradox is inspired by the mechanical properties of ratchets, the familiar saw-tooth tools used in automobile jacks and in self-winding watches. However, there is less to this paradox than meets the eye. It hinges on an incorrect probabilistic analysis - dependent random variables are treated as independent, and the paradox resolves itself as soon as the dependence is accounted for. For this reason, the initial burst of interest in the paradox rapidly faded.

Illustrative examples

The saw-tooth example

Consider an example in which there are two points A and B having the same altitude, as shown in Figure 1. In the first case, we have a flat profile connecting them. Here if we leave some round marbles in the middle that move back and forth in a random fashion, they will roll around randomly but towards both ends with an equal probability. Now consider the second case where we have a saw-tooth like region between them. Here also, the marbles will roll towards either ends with equal probability. Now if we tilt the whole profile towards the right, as shown in Figure 2, it is quite clear that both these cases will become biased towards B.

Now consider the game in which we alternate the two profiles while judiciously choosing the time between altering from one profile to the other in the following way.

When we leave a few marbles on the first profile at point E, they distribute themselves on the plane showing preferential movements towards point B. However, if we apply the second profile when some of the marbles have crossed the point C, but none have crossed point D, we will end up having most marbles back at point E (where we started from initially) but some also in the valley towards point A given sufficient time for the marbles to roll to the valley. Then again we apply the first profile and repeat the steps. If no marbles cross point C before the first marble crosses point D, we must apply the second profile shortly before the first marble crosses point D, to start over.

It easily follows that eventually we will have marbles at point A, but none at point B. Hence for a problem defined with having marbles at point A being a win and having marbles at point B a loss, we clearly win by playing two losing games.

The coin-tossing example

A second example of Parrondo's Paradox is drawn from the field of gambling. Consider playing two games, Game A and Game B with following rules. For convenience, define $C_{t}$ to be our capital at time t, immediately before we play a game.

Winning a game earns us $1 and losing requires us to surrender $1. It follows that $C_{t+1}=C_{t}+1$ if we win at step t and $C_{t+1}=C_{t}-1$ if we lose at step t.
In Game A, we toss a biased coin, Coin 1, with probability of winning $P_{1}=(1/2)-\epsilon$ . If $\epsilon >0$ , this is clearly a losing game in the long run.
In Game B, we first determine if our capital is a multiple of some integer $M$ . If it is, we tossed a biased coin, Coin 2, with probability of winning $P_{2}=(1/10)-\epsilon$ . If it is not, we toss another biased coin, Coin 3, with probability of winning $P_{3}=(3/4)-\epsilon ,$ . The role of $M$ is murky, and is not discussed in most articles about Parrondo's Paradox.

It is clear that by playing Game A, we will almost surely lose in the long run. Harmer and Abbott^[1] show via simulation that if $M=3$ and $\epsilon =0.005,$ Game B is an almost surely losing game as well. In fact, Game B is a Markov chain, and an analysis of its state transition matrix shows that the steady state probability of using coin 2 is 0.3836, and that of using coin 3 is 0.6164. As coin 2 is selected nearly 40% of the time, it has a disproportionate influence on the payoff from Game B, and results in it being a losing game.

However, when these two losing games are played in some alternating sequences - e.g two games of A followed by two games of B (AABBAABB....), the combination of the two games is, paradoxically, a winning game. Not all alternating sequences of A and B result in winning games. For example, one game of A followed by one game of B (ABABAB...) is a losing game, while one game of A followed by two games of B (ABBABB....) is a winning game. This coin-tossing example has become the canonical illustration of Parrondo's Paradox – two games, both losing when played indvidually, become a winning game when played in a particular alternating sequence. The paradox has been resolved using a number of sophisticated approaches, including Markov Chains,^[2] Flashing Ratchets,^[3] Simulated Annealing^[4] and Information Theory.^[5] However, there is less to this paradox than meets the eye. Observe that:

While Game B is a losing game under the probability distribution that results for $C_{t}$ modulo $M$ when it is played individually ( $C_{t}$ modulo $M$ is the remainder when $C_{t}$ is divided $M$ ), it can be a winning game under other distributions, as there is at least one state in which its expectation is positive.
As the distribution of outcomes of Game B depend on the player's capital, the two games cannot be independent. If they were, playing them in any sequence would lose as well.

The role of $M$ now comes into sharp focus. It serves solely to induce a dependence between Games A and B, so that a player is more likely to enter states in which Game B has a positive expectation, allowing it to overcome the losses from Game A. With this understanding, the paradox resolves itself: The individual games are losing only under a distribution that differs from that which is actually encountered when playing the compound game. In summary, Parrondo's paradox is not a paradox, but a shining example of how dependence can wreak havoc with probabilistic computations made under an incorrect assumption of independence. A more detailed exposition of this point, along with several related examples, can be found in Philips and Feldman.^[6]

Application of Parrondo's paradox

Parrondo's paradox is used extensively in game theory, and its application in engineering, population dynamics, financial risk, etc. are also being looked into.

It is of little use in most practical situations e.g. investing in stock markets, as the paradox specifically requires the payoff from at least one of the interacting games to depend on the player's capital. This is unrealistic, and would constitute a free lunch for an observant gambler if it did indeed exist.

References

^ G. P. Harmer and D. Abbott, "Losing strategies can win by Parrondo's paradox", Nature 402 (1999), 864
^ Harmer, G. P. and D. Abbott, , "Parrondo's Paradox", Statistical Science 14 (1999) 206-213
^ Harmer, G. P., D. Abbott, P. G. Taylor and J. M. R. Parrondo, in Proc. 2nd Int. Conf. Unsolved Problems of Noise and Fluctuations, D. Abbott, and L. B. Kiss, eds, American Institute of Physics, 2000
^ Harmer, G. P., D. Abbott, and P.G. Taylor, The Paradox of Parrondo's Games, Proc. Royal Society of London A 456 (2000), 1-13
^ Harmer, G. P., D. Abbott, P. G. Taylor, C. E. M. Pearce and J. M. R. Parrondo, Information Entropy and Parrondo's Discrete-Time Ratchet, in Proc. Stochastic and Chaotic Dynamics in the Lakes, Ambleside, U.K., P. V. E. McClintock, ed, American Institute of Physics, 2000
^ Philips, T. and Feldman, A. Parrondo's Paradox is not Paradoxical

External links

[1] G. P. Harmer and D. Abbott, "Losing strategies can win by Parrondo's paradox", Nature 402 (1999), 864

[2] Harmer, G. P. and D. Abbott, , "Parrondo's Paradox", Statistical Science 14 (1999) 206-213

[3] Harmer, G. P., D. Abbott, P. G. Taylor and J. M. R. Parrondo, in Proc. 2nd Int. Conf. Unsolved Problems of Noise and Fluctuations, D. Abbott, and L. B. Kiss, eds, American Institute of Physics, 2000

[4] Harmer, G. P., D. Abbott, and P.G. Taylor, The Paradox of Parrondo's Games, Proc. Royal Society of London A 456 (2000), 1-13

[5] Harmer, G. P., D. Abbott, P. G. Taylor, C. E. M. Pearce and J. M. R. Parrondo, Information Entropy and Parrondo's Discrete-Time Ratchet, in Proc. Stochastic and Chaotic Dynamics in the Lakes, Ambleside, U.K., P. V. E. McClintock, ed, American Institute of Physics, 2000

[6] Philips, T. and Feldman, A. Parrondo's Paradox is not Paradoxical

[1]

[2]

[3]

[4]

[5]

[6]

v t e Topics of game theory
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand
Strategies	Appeasement Backward induction Bid shading Collusion De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Bargaining problem Cheap talk Global game Intransitive game Mean-field game Mechanism design n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Stackelberg competition Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers Tic-tac-toe Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Arrow's impossibility theorem Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Miscellaneous	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory First-move advantage in chess Glossary of game theory List of game theorists List of games in game theory No-win situation Paradox of tolerance Solving chess Topological game Tragedy of the commons Tyranny of small decisions