Problems in rendezvous search.

Lim, Wei Shi (1996) Problems in rendezvous search. PhD thesis, London School of Economics and Political Science.

Preview

PDF Download (4MB) | Preview

Abstract

Suppose n players are placed randomly on the real line at consecutive integers, and faced in random directions. Each player has maximum speed one and cannot see the others. The least expected time required for m(? n) of them to meet together at a single point, if all players have to use the same strategy, is the symmetric rendezvous value Rsm,n. If the players can use different strategies, the least expected meeting time is the asymmetric rendezvous value Ram,n. show that Ra3,2 is 47/48 and Rsn,n is asymptotic to n/2. If the minimax rendezvous time Mn is the minimum time required to ensure that all players can meet together at a single point regardless of their initial placement, we prove that M2 is 3, M3 is 4 and Mn is asymptotic to n/2. If players have to stick together upon meeting, we prove that three players require 5 time units to ensure a meeting. We also consider a problem proposed by S. Alpern (in his joint paper with A. Beck, Rendezvous Search on the Line with Bounded Resources, LSE Math Preprint Series, 92 (1995)) of how two players can optimally rendezvous while at the same time evading an enemy searcher. We model this rendezvous-evasion problem as a two-person, zero-sum game between the rendezvous team R (with agents R1, R2) and the searcher S and consider a version which is discrete in time and space. R1, R2 and S start at different locations among n identical locations and no two of them share a common labelling of the locations. Each player can move between any two locations in one time step (this includes the possibility of staying still) until at least two of them are at the same location together, at which time the game ends. If S is at this location, S (maximizer) wins and the payoff is 1; otherwise the team R (minimizer) wins and the payoff is 0. The value of the game vn is the probability that S wins under optimal play. We assume that R1 and R2 can jointly randomize their strategies and prove that V3 is 47/76 ? 0.61842 and v4 is at least 31/54 ? 0.57407. If all the players share a common notion of a directed cycle containing all the n locations (while still able to move between any two locations), the value of the game dn is ((1 - 2/n)n-1 + l)/2. In particular, d3 is less than v3 and d4 is less than v4. We also compare some of these results with those obtained when the rendezvous-evasion game is modelled as a multi-stage game with observed actions (W. S. Lim, Rendezvous-Evasion As a Multi-Stage Game With Observed Actions, LSE Math-CDAM Research Report Series, 96-05 (1996)). In all instances considered, we find that obligatory announcement of actions at the end of each step either does not affect the value of the game or helps the rendezvous team secure a lower value.

Item Type:	Thesis (PhD)
Uncontrolled Keywords:	Mathematics
Sets:	Collections > ProQuest Etheses Departments > Mathematics
URI:	http://etheses.lse.ac.uk/id/eprint/2457

Actions (login required)

Record administration - authorised staff only