Module overview
This module:
- Introduces the students to the key issues of interaction of multiple self-interested parties (a.k.a. agents) and gives a broad survey of topics at the interface of theoretical computer science and game theory dealing with such interactions.
- Provides the theoretical background and practical tools to solve problems arising in settings with self-interested participants, to predict possible behaviour and outcomes, and finally, to design multi-agent systems that would incentivise desirable behaviour.
- Introduces the students to the specifics of computational game-theoretic techniques in different application areas, ranging from multi-agent systems, electronic marketplaces and networked computer systems to computational biology and social networks.
- Extends and advances the knowledge obtained in other AI modules (in particular, COMP6203 Intelligent Agents).
Aims and Objectives
Learning Outcomes
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- As a system administrator: to analyse participants’ behaviours and predict likely outcomes
- As an agent in a setting with self-interested participants: to reason about the opponents’ behaviour and make strategic decisions
- As a system designer: to design a system such that participants’ strategic behaviour lead to a desirable outcome
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Social choice theory
- Some applications of game theory and mechanism design
- The principles of game theory and mechanism design (with and without money)
Subject Specific Practical Skills
Having successfully completed this module you will be able to:
- Identify and compute various game theoretic solution concepts
Syllabus
Basic game theoretic concepts
Social choice
Mechanism design without money
Mechanism design with money
Applications
Learning and Teaching
Teaching and learning methods
Teaching methods include:
Tutorials: One hour per week during the teaching weeks, used for in-class tests and problem solving sessions.
- Assessment: Coursework and final examination.
Work in groups: group coursework focused on literature review or mini-survey
- Individual study: Certain amount of (directed) reading is expected during your private study time. It is strongly recommended that you read around the subject areas covered in the lectures. Refer to the list of background texts and ask the lecturers if you require further resources.
- Exercise: Applying theoretical knowledge and practical tools obtained in the lectures to solve problems provided in the recommended literature and exercise sheets.
| Type | Hours |
|---|---|
| Completion of assessment task | 41 |
| Lecture | 36 |
| Revision | 10 |
| Tutorial | 12 |
| Wider reading or practice | 15 |
| Preparation for scheduled sessions | 18 |
| Follow-up work | 18 |
| Total study time | 150 |
Resources & Reading list
Textbooks
Y. Shoham, K. Leyton-Brown (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press.
David F. Manlove. Algorithmics of Matching under Preferences.
Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Algorithmic Game Theory.
Dan Gusfiled and Robert W. Irving. The Stable Matching Problem: Structure and Algorithms.
Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-sided Matching: a Study in Game-Theoretic Modelling and Analysis.
Assessment
Assessment strategy
Feedback and student support during module study:
- Assignments will be marked and feedback given during the tutorial sessions.
- Reading and discussion groups with a plenary feedback during the tutorials.
- Coursework will be marked and feedback given during the tutorial sessions or electronically
Relationship between the teaching, learning and assessment methods and the planned learning outcomes:
- The knowledge, understanding and intellectual skills listed will be taught in lectures. In completing the assignments and examination you will demonstrate your mastery of all the skills listed.
- The purpose of the tutorials is for you to master the skills and provide feedback on your understanding of topics not covered by, or are difficult to fully assess in, an assignment.
Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Examination | 75% |
| Coursework | 25% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
| Method | Percentage contribution |
|---|---|
| Examination | 100% |
Repeat
An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.
| Method | Percentage contribution |
|---|---|
| Examination | 100% |
Repeat Information
Repeat type: Internal & External