COMP30191: Theory of Games and Game Models (2007-2008)
Games, apart from being of interest in themselves, provide a model for a variety of disciplines, even those that do not otherwise lend themselves to mathematical descriptions. Examples of these are the social sciences, economics and biology, and the issues modelled are typically decision processes conflicts and evolutionary systems. Recently games have also been used to model multi-agent systems and other computing scenarios.
This module provides a first introduction to the field. The notions of `game' and `strategy' are first put on a solid footing, and then the basics of classic game theory (an area of mathematics) are explored. Following that the notion of a game model is introduced and relevant examples are discussed. These include the Prisoner's Dilemma in a number of variations, computer simulations in situations where a theoretical analysis fails, and the modelling of evolution. For larger games, such as Chess, the methods introduced so far do not work in practice, but there are approaches in computing which allow finding good moves.
Students are expected to read the notes; to support them in this there are sessions to ask questions, and in which the lecturer will introduce the material to be read in the coming week.
A student completing this course unit should:
Have an overview over different classes of games and appreciate the different methods for finding good strategies.
Have an understanding of situations which can be modelled by games and be able to choose an appropriate model.
Know how computers are used to either solve games or to discover `good' strategies.
Appreciate how assumptions regarding a situation are reflected by the model and be aware of the consequences that has for the interpretations of the results.
Assessment of Learning outcomesThe assessment occurs in the form of a 2 hour examination (counting for 80% of the final mark) as well as assessed coursework (which counts for the remaining 20%).
The first four examples classes provide support for solving exercises, including the assessed ones. The last examples class is reserved for marking assessed coursework. This consists of a number of exercises published at the start of term. Students have to be able to explain their solution to these.
Contribution to Programme Learning OutcomesA1, A2, B1, D6.
Games and strategies
What is a game? Abstraction of the concept, describing games, extensive form. Playing a game: the notion of strategy, pay-off functions, matrix games.
Finite non-cooperative games, in particular 2-person games. Equilibrium points, the normal form of a game, usefulness of equilibria. Mixed strategies, the Minimax Theorem for matrix games. Finding equilibria; extended case study: is game theory useful?
The Prisoner's Dilemma, generalizations, real-world applications. Repeated games, computer tournaments - what does well in the real world? Indefinitely and infinitely repeated games.
Games and evolution
Ecological models; collective stability; territorial systems; noise, chance and automata; more biological games.
The algorithmic point of view; the minimax algorithm; alpha-beta pruning.
Writing game playing programs; representing positions and moves; evaluation functions; alpha-beta search.
There is no one book that covers the course material entirely. For this reason there will be a set of notes. At least browsing some of the literature listed here is highly recommended.
Core TextTitle: Game Theory
Author: A. Jones
Publisher: Horwood Publishing
Mathematical introduction to Games. Only the first two chapters are relevant for this course.
Supplementary TextTitle: Kasparov versus Deep Blue: computer chess comes of age
Author: M. Newborn
Supplementary TextTitle: Compleat Strategyst
Author: J.D. Williams
Entertaining, if slightly old-fashioned and limited, account of small matrix games.
Supplementary TextTitle: Metamagical Themas (Chapters 28 & 29)
Author: D.R. Hofstadter
Publisher: Basic Books
Interesting columns on prisonrs' dilemma type games.
Supplementary TextTitle: Evolution of Cooperation
Publisher: Basic Books, Inc.
A classic text on how the prisoners' dilemma game can be used to model the evolution of cooperation in a world of selfish individuals.
Supplementary TextTitle: Mathematics of Games of Strategy
Publisher: Dover Publications Inc. Publications Inc.
Supplementary TextTitle: Games of Life
Author: K. Sigmund
Nice account of using games to model the evolution of traits.
Supplementary TextTitle: Evolutionary Games and Population Dynamics
Author: J. Hofbauer and K. Sigmund
Publisher: Cambridge University Press
More games modelling biological processes.