Cookies?
Library Header Image
LSE Theses Online London School of Economics web site

Hide-and-seek and other search games

Lidbetter, Thomas (2013) Hide-and-seek and other search games. PhD thesis, The London School of Ecoomics and Political Science (LSE).

[img]
Preview
PDF
Download (525Kb) | Preview

Abstract

In the game of hide-and-seek played between two players, a Hider picks a hiding place and a Searcher tries to find him in the least possible time. Since Isaacs had the idea of formulating this mathematically as a zero-sum game almost fifty years ago in his book, Differential Games, the theory of search games has been studied and developed extensively. In the classic model of search games on networks, first formalised by Gal in 1979, a Hider strategy is a point on the network and a Searcher strategy is a constant speed path starting from a designated point of the network. The Searcher wishes to minimise the time to find the Hider (the payoff), and the Hider wishes to maximise it. Gal solved this game for certain classes of networks: that is, he found optimal strategies and the payoff assuming best play on both sides. Here we study new formulations of search games, starting with a model proposed by Alpern where the speed of the Searcher depends on which direction he is traveling. We give a solution of this game on a class of networks called trees, generalising Gal's work. We also show how the game relates to another new model of search studied by Baston and Kikuta, where the Searcher must pay extra search costs to search the network's nodes (or vertices). We go on to study another new model of search called expanding search, which models coal mining. We solve this game on trees and also study the related problem where the Hider's strategy is known to the Searcher. We extend the expanding search game to consider what happens if there are several hidden objects and solve this game for certain classes of networks. Finally we study a game in which a squirrel hides nuts from a pilferer.

Item Type: Thesis (PhD)
Additional Information: © 2013 Thomas Lidbetter
Library of Congress subject classification: Q Science > QA Mathematics
Sets: Departments > Mathematics
Supervisor: Alpern, Steve
URI: http://etheses.lse.ac.uk/id/eprint/692

Actions (login required)

Record administration - authorised staff only Record administration - authorised staff only

Downloads

Downloads per month over past year

View more statistics