Introductory description

N/A

Module web page

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Syllabus(by weeks):

1. The Game of Nim
2. Combinatorial Games I
3. Combinatorial Games II
4. Game of Hex and variations
5. Proof of Brouwer Fixed-Point Theorem using Hex
6. Search Theory: Introduction
7. Search Games I: Immobile Hider on a Tree
8. Search Games II: Immobile Hider on Weakly Eulerian Network
9. Search Games III: Mazes
10. Review
    Note: these topics have been chosen so that there is virtually no overlap with courses in game

Learning outcomes

By the end of the module, students should be able to:

• By completing this module, students will have a firm grasp of search theory and in particular the antagonistic version known as search games. They should be able to identify to problems that could be modelled by this theory, and to some extent have a start on how to attack such models. They should be able to extend our use of dynamic programming in search problems to other areas. Their ability to prove general theorems should be enhanced.

Indicative reading list

Steve Alpern (2017) "Hide-and-seek games on a network, using combinatorial search paths ", Operations Research, 65, 5,
1207-1214

Steve Alpern (2011) "A new approach to Gal's Theory of Search Games on Weakly Eulerian networks", Dynamic Games and
Applications, 1, 2, 209-219

S. Alpern, S. Gal. The Theory of Search Games and Rendezvous, International Series in Operations Research and
Management Science. Kluwer, New York (reprinted by Springer) (2003)

S. Alpern. Network search from a game theoretic perspective.
INFORMS Tutorials (2013)

Gal, S., & Anderson, E. (1990). Search in a Maze. Probability in the Engineering and Informational Sciences, 4(3), 311-318.
doi:10.1017/S0269964800001625

Additional reading

• J. H. Reijnierse and J. A. M. Potter (1993). Search games with immobile hider. Int. J. Game Theory 21 , 385-394.
• L. Pavlovic (1993). Search game on an odd number of arcs with immobile hider. Yugosl. J. Oper. Res. 3, no. 1, 11--19.
  S. Gal (2013). Search games: a review. In: Alpern, Steve, et al., eds. Search theory: a game theoretic perspective. Springer,
  New York.
• Dagan and S. Gal (2008), Network search games, with arbitrary searcher starting point, Networks 52, 156--161.
  V. Baston and K. Kikuta. Search games on a network with travelling and search costs. International Journal of Game Theory 44,
  no. 2 (2015): 347-365

Subject specific skills

Use game theory to analyse conflict situations. Suggest strategies appropriate to the problems

Transferable skills

Formulate business and other game problems in a structured form (trees, matrices) suited to game theoretic analysis. Apply these techniques to the solution of the problems. Interpret the results of the solution techniques in terms of the original problems faced by the players. Apply search algorithms to find objects and efficiency.