Introductory description

This is an elective module available for students on the MORSE or MMORSE joint degree only. To apply for this module, log in to my.wbs.ac.uk using your normal IT login details and apply via the my.wbs module application system. Once you’ve secured a place on my.wbs you should apply via your home department’s usual process, which usually takes place via eVision. Note that you do not require the module leader’s permission to study a WBS module, so please do not contact them to request it.

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:

• Understand game theoretic models and methods used to analyse them.
• Be able to critically assess the relevance and limitations of the methods.
• Be able to determine which real world problems are game theoretic and which are not.

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.