In a typical Search Game, one or more unit-speed searchers wishes to minimize the time required to find (or meet) a lost object or objects, (or other searcher or searchers) within a known search region. For example, the following symmetric rendezvous game, was posed by Alpern in 1976:

Two agents wish to meet at one of $n$ locations. They start in two distinct locations. In each subsequent period $t=1,2,\dotsc$, each agent may visit any one location. The meeting time $T$ is the first time $t$ they are in the same location. A pure strategy for an agent is simply a list of locations. What randomized strategy, if followed by both players, minimizes the expected value of $T$ ?

For $n=2$ the problem is easy. But the case of $n=3$ was solved only 30 years after it was first posed. The problem for $n>3$ is still completely open.

Write an essay about key results in Search Game theory, and the mathematics that has been used to obtain them. You might wish to discuss the rendezvous search game mentioned above. But you might also range more widely, writing about other games to be found in [1] and [2] or by searching for other literature. Some interesting search games of current research interest are described in [5] and [6].

[1] Alpern, S. Rendezvous search: A personal perspective. Oper. Res. 50(5): 772--795, 2002.

[2] Alpern, S. and Gal, S. The Theory of Search Games and Rendezvous. New York: Kluwer (reprinted by Springer, 2003).

[3] Han, Q., D. Du, J. C. Vera, L. F. Zululaga. Improved bounds for the symmetric rendezvous problem on the line. Oper. Res. 56(3) 772--782, 2006.

[4] Weber, R. R., 2012. Optimal symmetric rendezvous search on three locations, Math Oper Res., 37(1): 111-122, 2012.

[5] Alpern, S., Fokkink, R., Pelekis, C. A proof of the Kikuta-Ruckle conjecture on the cyclic caching of resources. J. of Optimization Theory and Applications 153: 650-661, 2012.

[6] Alpern, S., Fokkink, R., Lidbetter, T. and Clayton, N. S. A search game model of the scatter hoarder's problem. J. R. Soc. Interface May 7, 70: 869--879, 2012.

In the on line matching problem we have $n$ boys and $n$ girls. Boys arrive in some sequence and as each boy arrives we learn the subset of the girls he knows, and must match him against one of these, provided they are not all already matched. We wish to maximize the number of matches obtained. In the on line bin packing problem we are presented with a sequence of items, of sizes $r_1, r_2,\dotsc,r_n$, each $r_i < 1$. As each item arrives we learn its size and must place it in a bin (which may be partly full already). Bins are of size 1 and we wish to use as few bins as possible. A typical theorem is no online bin packing algorithm can be better the $4/3$-competitive (which means that in the worst case it will use at least $4/3$ the number of bins used by an optimal off line algorithm.)

Write about some key results for these problems and the mathematics that has been used to obtain them. You could write, for example, about heuristics (like Next Fit, Best Fit, Greedy, etc.), or Lyapounov functions, or uses of linear and/or semi-definite programming. Perhaps you can find a way to give a unified exposition for ideas that are common to both problems. You might like to discuss the modern application area addressed in [5] and [6].

[1] Coffman, E. G., Courcoubetis, C., Johnson, D. S., Garey, M. R., Shor, P. W., Weber, R. R. and Yannikakis, M. Perfect packing theorems and the average case behavior of optimal and online bin packing. SIAM Review, 44:95--108, 2002.

[2] Csirik, J. Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W. and Weber, R. R. On the sum-of-squares algorithm for bin packing.JACM, 53(1):1--85, 2006. (preprint at http://arxiv.org/abs/cs/0210013)

[3] R.M. Karp, U.V. Vazirani, and V.V. Vazirani. An optimal algorithm for online bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computin}, 1990.

[4] Mahdian, M. and Yan, Q. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs, in Proceedings of the 43rd annual ACM Symposium on Theory of Computing, 597--606, 2011.

[5] Mehta, A., Saberi, A., Vazirani, U. and Vazirani, V. AdWords and generalized on-line matching, JACM, 54(5):22, 2007.

[6] Devanur, N. R. and Hayes, T. P. The Adwords problem: online keyword matching with budgeted bidders under random permutations, in Proceedings of the 10th annual ACM Conference on Electronic Commerce, 71--78, 2009.

[7] [3] Johnson, D. S. 2012. A Brief History of NP-Completeness, 2012