The University of Southampton
Courses

COMP6207 Advanced Intelligent Agents

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

Module Aims

To provide an overview of advanced intelligent agents

Learning Outcomes

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

  • The main game-theoretic concepts such as Nash equilibrium, dominant strategies, mixed strategies, and Bayesian games
  • Sponsored search auctions and their properties
  • Simple machine learning approaches for finding Nash equilibria
  • The principles of mechanism design and its use to shape incentives and designing markets
  • The main mechanisms including the second-price and Vickrey-Clarke-Groves auctions
  • Potential games and their application to congestion and routing problems
  • The main voting protocols
  • The issues of manipulation in voting
  • Cooperative games and coalition formation
  • The computational complexity of finding game theoretic solutions
Subject Specific Practical Skills

Having successfully completed this module you will be able to:

  • Find dominant strategy and min-max solutions, and compute pure strategy and mixed Nash equilibria in certain game classes
  • Apply learning techniques for finding stable outcomes
  • Derive parameters for producing optimal/efficient mechanisms in specific application domains
  • Apply cooperative solution concepts, such as the Core and the Shapley value, to analyse and design effective cooperative systems
Subject Specific Intellectual and Research Skills

Having successfully completed this module you will be able to:

  • As an element of an interactive system with multiple self-interested participants: to reason about the opponents' behaviour and make strategic decisions
  • As a system administrator: to analyse participant behaviours and predict likely outcomes
  • As a system designer: to create incentives for participants that result in systems with desirable properties, and encourage cooperation

Syllabus

Basic game-theoretic concepts: non-cooperative games - Strategic interactions as (normal form) games - Solution concepts: dominance and iterated dominance; minimax strategies; Nash equilibrium; - Computing and evaluating the quality of solutions - Games with pure strategy equilibria; potential functions and equilibrium dynamics - Other game forms and solutions concepts: extensive-form games; subgame perfect equilibrium; - Correlated equilibrium; strong equilibrium, Bayes-Nash equilibrium Basic game-theoretic concepts: cooperative games - Coalition formation - Characteristic function and other representations - Solution concepts (the Core, Nucleolus, Shapley value, Banzaff index) and their computation (Computational) social choice - Voting rules; desirable properties of voting rules - Arrow's impossibility theorem; Muller-Satterthwaite impossibility theorem - Manipulation; Gibbard-Satterthwaite impossibility theorem - Convergence to stable outcomes in strategic voting (Algorithmic) mechanism design - Standard auction formats: English; Dutch; first-price; second-price - Revenue maximisation and revenue equivalence theorem - General mechanisms: formalism; revelation principle; desirable properties - Vickrey-Clarke-Groves mechanism - Advanced mechanisms: combinatorial auctions; simultaneous auctions; sequential auctions; - Double auctions Learning in games - Fictitious play - Regret minimisation Applications - E-Commerce (ad auctions) - Network and routing games, (generalised) congestion games - Smart grid

Learning and Teaching

Teaching and learning methods

Teaching methods include: - Directed Reading: There is a combination of lecture notes, selected research papers and book chapters for directed reading, which is a necessary preparation for the lectures. - Lectures: Three hours per week during the teaching weeks, supported by handouts and class discussion. - Tutorials: One hour per week during the teaching weeks, focusing on the application of the practical aspects of computational game-theoretic techniques and problem solving. - Assessment: There are 4 home take Assignments. Learning activities include: - Work in groups: Reading and discussion groups with a plenary feedback during the tutorials. Participation, while not compulsory, is encouraged. - 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 example problems provided in the recommended literature and home take assignments.

TypeHours
Follow-up work18
Revision10
Wider reading or practice45
Tutorial12
Completion of assessment task11
Lecture36
Preparation for scheduled sessions18
Total study time150

Resources & Reading list

Y. Shoham, K. Leyton-Brown (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. 

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. 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

MethodPercentage contribution
Coursework 25%
Exam  (2 hours) 75%

Referral

MethodPercentage contribution
Exam  (2 hours) 100%

Repeat Information

Repeat type: Internal & External

Linked modules

Pre-requisites

To study this module, you will need to have studied the following module(s):

CodeModule
COMP6203Intelligent Agents
Share this module Facebook Google+ Twitter Weibo

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.

×