Theory of Search Games and Rendezvous

Team DDU......Page 1
Contents......Page 6
Preface......Page 12
Frequently Used Notations......Page 14
Acknowledgment......Page 16
BOOK I SEARCH GAMES......Page 19
1 Introduction to Search Games......Page 20
Part One Search Games in Compact Spaces......Page 24
2 General Framework......Page 26
8 Search on the Infinite Line......Page 29
8.1 Introduction......Page 140
8.2 The Linear Search Problem as a Search Game......Page 141
8.2.1 The minimax search trajectory......Page 143
8.2.2 Minimax trajectory on a half-line......Page 145
8.3 Optimal Strategies......Page 146
8.4 Search with a Turning Cost......Page 149
8.5 Search for a Moving Hider......Page 151
8.6 Search with Uncertain Detection......Page 154
8.6.1 Search with a delay......Page 155
8.7 A Dynamic Programming Algorithm for the LSP......Page 156
3.1 Introduction......Page 30
3.2 Search in a Network......Page 34
3.3 Search on a Tree......Page 38
3.4.1 Searching weakly cyclic networks......Page 42
3.4.2 Searching weakly Eulerian networks......Page 44
3.5 Simple Networks Requiring Complicated Strategies......Page 48
3.6 Using Dynamic Programming for Finding Optimal Response Search Trajectories......Page 53
3.7 Search in a Multidimensional Region......Page 56
3.7.1 Inhomogeneous search spaces......Page 59
4.1 Introduction......Page 62
4.2 Search on k Arcs......Page 65
4.3 Search on a Circle......Page 69
4.4 Quickly Searched Networks......Page 70
4.4.1 The figure eight network......Page 72
4.5.1 General framework......Page 75
4.5.2 Strategy of the searcher......Page 76
4.5.3 Strategy of the hider......Page 84
4.6.1 A "non-localized" search strategy......Page 90
4.6.4 The case of several searchers......Page 91
4.6.7 Non-homogeneous search spaces......Page 92
4.6.8 A general cost function......Page 93
5.1 Search in a Maze......Page 96
5.2.1 Continuous high-low search......Page 101
5.2.2 Economic applications......Page 106
5.2.3 Discrete high–low search......Page 108
5.3 Infiltration Games......Page 109
5.4 Searching in Discrete Locations......Page 112
Part Two Search Games in Unbounded Domains......Page 116
6.1 One-Dimensional Search Games......Page 118
6.2 Multidimensional Search Games......Page 121
7.1 Introduction......Page 124
7.2 Minimax Theorems......Page 126
7.2.1 Minimax theorems for the continuous case......Page 133
7.3 Uniqueness of the Minimax Strategy......Page 134
9.2 Star Search......Page 162
9.3 Search on the Boundary of a Region......Page 171
9.4 Search for a Point in the Plane......Page 174
9.5 "Swimming in a Fog" Problems......Page 176
9.6 Searching for a Submarine with a Known Initial Location......Page 178
BOOK II RENDEZVOUS THEORY......Page 180
10 Introduction to Rendezvous Search......Page 182
10.1 Relation to Coordination Games......Page 184
10.2 Real-Life Rendezvous......Page 185
10.3 Rendezvous Strategies......Page 187
10.4 Outline of Book II......Page 188
11.1 Symmetric Rendezvous on the Line......Page 190
11.2 Multi-Rendezvous on the Circle......Page 192
11.3 FOCAL Strategies on the Line......Page 193
11.4 Rendezvous in Two Cells......Page 194
Part Three Rendezvous Search on Compact Spaces......Page 196
12 Rendezvous Values of a Compact Symmetric Region......Page 198
12.2 Spatial Symmetry......Page 199
12.3 An Example: The Circle......Page 201
12.4 The Asymmetric Rendezvous Value Ra......Page 202
12.5 The Symmetric Rendezvous Value Rs......Page 204
12.6 Properties of Optimal Strategies and Rendezvous Values......Page 205
13.1 Networks and H-Networks......Page 208
13.2 Rendezvous on H-Networks......Page 210
13.3 The Interval H-Network......Page 214
13.3.1 Nondecreasing initial distributions......Page 215
13.4.1 Symmetric rendezvous on the labeled circle......Page 218
13.4.2 Asymmetric rendezvous on the labeled circle......Page 221
14 Asymmetric Rendezvous on an Unlabeled Circle......Page 224
14.1 One-Sided Search on the Circle......Page 225
14.2 Asymmetric Rendezvous on a Directed Circle......Page 228
14.3 Asymmetric Rendezvous on an Undirected Circle: Formalization......Page 230
14.4 Alternating Search on Two Circles......Page 232
14.5 Optimal Rendezvous on the Undirected Circle......Page 234
14.5.1 Monotone densities......Page 235
14.5.2 Slowly varying densities......Page 237
14.5.3 Arbitrary distributions......Page 238
15 Rendezvous on a Graph......Page 240
15.1 Asymmetric Rendezvous......Page 242
15.3 Symmetric Rendezvous on a Complete Graph......Page 244
15.3.1 Revealed actions......Page 247
15.4.1 Symmetric Markovian strategies......Page 248
Part Four Rendezvous Search on Unbounded Domains......Page 252
16 Asymmetric Rendezvous on the Line (ARPL)......Page 254
16.1 Asymmetric Rendezvous Value Ra (F)......Page 255
16.2 Finiteness of Ra (F)......Page 257
16.3 The Double Linear Search Problem (DLSP)......Page 258
16.4 Meeting-Probability Maximization......Page 259
16.5 Atomic Distribution......Page 260
16.6 Discrete Distributions......Page 263
16.7 Arbitrary Distributions......Page 264
16.8 Convex Distributions......Page 265
17 Other Rendezvous Problems on the Line......Page 268
17.1 Unequal Speeds......Page 269
17.2 Player Symmetry......Page 271
17.3.1 Expected time minimization for 3a+5b>=15D......Page 273
17.3.2 Probability maximization......Page 276
17.4.1 Asymmetric strategies......Page 281
17.5 Multiplayer Rendezvous......Page 284
17.5.1 Expected time minimization......Page 285
17.5.2 Maximum time minimization......Page 287
17.6 Asymmetric Information......Page 290
18.1 Asymmetric Rendezvous on a Planar Lattice......Page 294
18.2.1 Asymmetric rendezvous......Page 301
18.2.2 Symmetric rendezvous......Page 303
18.3.1 Common notion of direction......Page 305
18.3.2 Asymmetric information......Page 306
Appendices......Page 307
A A Minimax Theorem for Zero-Sum Games......Page 308
B Theory of Alternating Search......Page 312
B.1 Arbitrary Regions......Page 314
C Rendezvous-Evasion Problems......Page 316
Bibliography......Page 320
Index......Page 334