In a search game a hider and searcher compete. For example, in [1] a hider and searcher wish to maximize and minimize, respectively, the cost to the searcher of finding $k$ objects which a strategic hider has hidden amongst $n > k$ locations. Another interesting game is the so-called accumulation game in which a hider secretly distributes her wealth $w > 1$ amongst $n$ locations. The searcher visits a random $r$ of these locations and steals what is there. The hider wins if the wealth remaining sums to at least 1; otherwise the searcher wins. This game models a problem in which the hider needs sucient remaining wealth to carry out some objective. For example, if she might need enough nuts to survive the winter, [2]-[4]. Finally, in the caching game, studied in [5]-[7], the hider buries various portions of her wealth at various depths at $n$ locations, subject to the constraint that sum of the depths of the holes is no more than 1. Again, the searcher can steal her wealth but is constrained that sum of the depths of the holes he digs can be no more than $h$. Starting from the papers below, and references therein, write an essay about these games, their practical motivation, the interesting results that have been obtained, the mathematics that has been useful, and open problems.

[1] Lidbetter, T. Search games with multiple hidden objects. SIAM Journal on Control and Optimization 51(4) 3056{3074, 2013. http://eprints.lse.ac.uk/55103/
[2] Kikuta, K. and Ruckle, W. H. Continuous accumulation games on discrete locations, Naval Research Logistics, 49, 60{77, 2002. http://onlinelibrary.wiley.com/doi/10.1002/nav. 1048/pdf
[3] Alpern, S. and Fokkink, R. Accumulation games on graphs Networks 64, 40-47, 2014 http://www.cdam.lse.ac.uk/Reports/Files/cdam-2008-18.pdf
[4] 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. http://link.springer.com/article/10.1007/s10957-011-9977-1?null
[5] 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. http://rsif.
royalsocietypublishing.org/content/9/70/869
[6] Csoka, E, Lidbetter, T. The solution to an open problem for a caching game, 2015 http://arxiv.org/pdf/1507.08425v2.pdf
[7] Lidbetter, T. A caching game with innitely divisible hidden material, SIAM J. Control Optim., 53(5), 3040{3056, 2015. http://epubs.siam.org/doi/abs/10.1137/140997075

The online matching problem starts with $n$ boys and $n$ girls. Boys arrive in some sequence and as each arrives we learn the subset of the girls whom 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 recent years this type of problem has had important application in the allocation of adwords, [1]-[3]. In the online 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 that no online bin packing algorithm can be better the $4/3$--competitive (which means that in the all algorithms will in some cases use at least $4/3$ the number of bins as an optimal offline algorithm would use.) You might like to learn how such a theorem is proved.

Your essay can describe these problems, their practical motvations, some interesting results, the mathematics that has been useful and open problems. You could write, for example, about heuristics (like Next Fit, Best Fit, Greedy, etc.), or Lyapunov functions, or uses of linear programming. You could write just on the adwords matching problem [1]-[4], or just on bin packing, [5]-[7], or try to identify and treat similarly some common aspects of the two problems.

[1] Mehta, A., Saberi, A., Vazirani, U. and Vazirani, V. AdWords and generalized on-line matching, JACM, 54(5):22, 2007. http://web.stanford.edu/~saberi/adwords.pdf
[2] 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 Con ference on Electronic Commerce, 71{78, 2009. http://research.microsoft.com/apps/pubs/
default.aspx?id=80738
[3] Mehta, A. Online matching and ad allocation. In Foundations and Trends in Theoretical Computer Science Vol. 8, No. 4, 265{368, 2012. http://algomagic.com/41870-16.pdf
[4] 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 Computing, 1990. http://www.eecs.berkeley.edu/~vazirani/pubs/online.pdf
[5] Coman, 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. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.6911
[6] 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
[7] Epstein, L., Favrholdt, L. M., Kohrt, J. S. Comparing online algorithms for bin packing problems, Journal of Scheduling 15, 1, pp 13{21, 2012. http://link.springer.com/article/10.1007%2Fs10951-009-0129-52