Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

COMP30191: Theory of Games and Game Models (2007-2008)

This is an archived syllabus from 2007-2008

Theory of Games and Game Models
Level: 3
Credit rating: 10
Pre-requisites: COMP10020 or equivalent (e.g. CS1021 COMP10021 or MATH10111 or MATH10131 or MATH10212 or MATH10232 or MATH10662 or MATH10672)
Co-requisites: No Co-requisites
Duration: 11 weeks in the first semester
Lectures: 11 sessions to introduce reading and for students to ask questions
Examples classes: 5 in weeks A (starting in week 3), in the last of which coursework is assessed
Labs: none
Lecturers: Andrea Schalk
Course lecturer: Andrea Schalk

Additional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 w1-5,7-12 Lecture 1.1 Mon 16:00 - 17:00 -
Sem 1 w1,3,5,8,10,12 Examples 2.19 Wed 09:00 - 11:00 -
Assessment Breakdown
Exam: 80%
Coursework: 20%
Lab: 0%

Introduction

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.

Aims

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.

Learning Outcomes

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 outcomes

The 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 Outcomes

A1, A2, B1, D6.

Syllabus

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.

Small 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?

Game models


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.

Medium games


The algorithmic point of view; the minimax algorithm; alpha-beta pruning.

Large games


Writing game playing programs; representing positions and moves; evaluation functions; alpha-beta search.

Reading List

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 Text
Title: Game Theory
Author: A. Jones
ISBN:
Publisher: Horwood Publishing
Edition:
Mathematical introduction to Games. Only the first two chapters are relevant for this course.


Supplementary Text
Title: Kasparov versus Deep Blue: computer chess comes of age
Author: M. Newborn
ISBN:
Publisher: Springer
Edition:


Supplementary Text
Title: Compleat Strategyst
Author: J.D. Williams
ISBN:
Publisher: McGraw-Hill
Edition:
Entertaining, if slightly old-fashioned and limited, account of small matrix games.


Supplementary Text
Title: Metamagical Themas (Chapters 28 & 29)
Author: D.R. Hofstadter
ISBN:
Publisher: Basic Books
Edition:
Interesting columns on prisonrs' dilemma type games.


Supplementary Text
Title: Evolution of Cooperation
Author: R.Axelrod
ISBN: 0140124950
Publisher: Basic Books, Inc.
Edition:
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 Text
Title: Mathematics of Games of Strategy
Author: M.Dresher
ISBN: 048664216X
Publisher: Dover Publications Inc. Publications Inc.
Edition:
Year: 1982


Supplementary Text
Title: Games of Life
Author: K. Sigmund
ISBN:
Publisher: Penguin
Edition:
Nice account of using games to model the evolution of traits.


Supplementary Text
Title: Evolutionary Games and Population Dynamics
Author: J. Hofbauer and K. Sigmund
ISBN:
Publisher: Cambridge University Press
Edition:
More games modelling biological processes.