Princess and Monster game

In game theory, a princess and monster game is a pursuit-evasion game played by two players in a region. The game was devised by Rufus Isaacs and published in his book Differential Games (1965) as follows:

The monster searches for the princess, the time required being the payoff. They are both in a totally dark room (of any shape), but they are each cognizant of its boundary. Capture means that the distance between the princess and the monster is within the capture radius, which is assumed to be small in comparison with the dimension of the room. The monster, supposed highly intelligent, moves at a known speed. We permit the princess full freedom of locomotion.[1]

This game remained a well-known open problem until it was solved by Shmuel Gal in the late 1970s.[2][3] His optimal strategy for the princess is to move to a random location in the room and stay still for a time interval which is neither too short nor too long, before going to another (independent) random location and repeating the procedure.[3][4][5] The proposed optimal search strategy, for the monster, is based on subdividing the room into many narrow rectangles, picking a rectangle at random and searching it in some specific way, after some time picking another rectangle randomly and independently, and so on.

Princess and monster games can be played on a pre-selected graph. It can be demonstrated that for any finite graph an optimal mixed search strategy exists that results in a finite payoff. This game has been solved by Steve Alpern and independently by Mikhail Zelikin only for the very simple graph consisting of a single loop (a circle).[6][7] The value of the game on the unit interval (a graph with two nodes with a link in-between) has been estimated approximatively.

The game appears simple but is quite complicated. The obvious search strategy of starting at a random end and "sweeping" the whole interval as fast as possible guarantees a 0.75 expected capture time, and is not optimal. By utilising a more sophisticated mixed searcher and hider strategy, one can reduce the expected capture time by about 8.6%. This number would be quite close to the value of the game if someone was able to prove the optimality of the related strategy of the princess.[8][9]
See also

Search games
List of games in game theory

References

R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, John Wiley & Sons, New York (1965), PP 349–350.
S. Gal, SEARCH GAMES, Academic Press, New York (1980).
Gal Shmuel (1979). "Search games with mobile and immobile hider". SIAM J. Control Optim. 17 (1): 99–122. doi:10.1137/0317009. MR 0516859.
A. Garnaev (1992). "A Remark on the Princess and Monster Search Game" (PDF). Int. J. Game Theory. 20 (3): 269–276. doi:10.1007/BF01253781.[permanent dead link]
M. Chrobak (2004). "A princess swimming in the fog looking for a monster cow". ACM SIGACT News. 35 (2): 74–78. doi:10.1145/992287.992304.
S. Alpern (1973). "The search game with mobile hiders on the circle". Proceedings of the Conference on Differential Games and Control Theory.
M. I. Zelikin (1972). "On a differential game with incomplete information". Soviet Math. Dokl.
S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. SIAM J. control and optimization 2008.

L. Geupel. The 'Princess and Monster' Game on an Interval.

vte

Topics in game theory
Definitions

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

Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies

Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy Bid shading

Classes
of games

Symmetric game Perfect information Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game Mean field game n-player game Large Poisson game Nontransitive game Global game Strictly determined game Potential 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 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 Purification theorem Revelation principle 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 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