Module Details

The information contained in this module specification was correct at the time of publication but may be subject to change, either during the session because of unforeseen circumstances, or following review of the module at the end of the session. Queries about the module should be directed to the member of staff with responsibility for the module.
Title ALGORITHMIC GAME THEORY
Code COMP559
Coordinator Dr G Christodoulou
Computer Science
G.Christodoulou@liverpool.ac.uk
Year CATS Level Semester CATS Value
Session 2020-21 Level 7 FHEQ Second Semester 15

Aims

1. To provide an understanding of the inefficiency arising from uncontrolled, decentralized resource allocation.
2. To provide a foundation for modelling various mechanism design problems together with their algorithmic aspects.
3. To provide the tools and paradigms for the design and analysis of efficient algorithms/mechanisms that are robust in environments that involve interactions of selfish agents.
4. To review the links and interconnections between algorithms and computational issues with selfish agents.
5. To provide an in-depth, systematic and critical understanding of selected significant topics related to algorithmic game theory, together with the related research issues.


Learning Outcomes

(LO1) Have a critical awareness ofcurrent problems, important concepts and research issues in  the field ofalgorithmic game theory. 

(LO2) Systematic knowledge andability to quantify the inefficiency of equilibria.

(LO3) Systematic knowledge andability to formulate mechanism design models or network games for the purpose of modeling particularapplications.

(LO4) Detailed understanding andability to use, describe and explain appropriate algorithmic paradigms and techniques in context of aparticular game-theoretic or mechanism design problem.

(LO5) Critical ability to read,understand and communicate research literature in the field of algorithmic game theory.  

(LO6) Critical ability torecognise potential research opportunities and research directions in the field of algorithmic game theory.

(S1) Communication (oral, written and visual) - Presentation skills – oral

(S2) Communication (oral, written and visual) - Presentation skills - written

(S3) Communication (oral, written and visual) - Presentation skills - visual

(S4) Critical thinking and problem solving - Critical analysis

(S5) Information skills - Critical reading

(S6) Business and customer awareness

(S7) Computer science principles


Syllabus

 

Introduction to Network Games: Reminder of game theory fundamentals (with a focus on network games): solution concepts such as Nash equilibria, correlated equilibria. (2 lectures)
Load balancing games: existence and complexity of equilibria, price of anarchy. (3 lectures)
Routing games (atomic and non-atomic selfish routing): existence and complexity of equilibria, price of anarchy, price of stability. (5 lectures)
Introduction to Mechanism Design: Social Choice, Mechanisms with Money, Dominant Strategies, Characterisations of Incentive Compatible Mechanisms, Bayesian-Nash Implementation. (4 lectures)
Mechanism Design without Money. (3 lectures)
Combinatorial Auctions (CA): Single-Minded Bidders, Bidding   Languages, Iterative Auctions, Winner Determination, Applications. (4 lectures)
Profit Maximisation in Mechanism Design. (3 lectures)
Online Mechanisms (2 Lectures)
Current Topics in Algorithmic Game Theory (Network Creation Games, Spon sored Search Auctions, Price of Anarchy in Auctions)


Teaching and Learning Strategies

Teaching Method 1 - Lecture
Description:
Attendance Recorded: Yes

Teaching Method 2 - Tutorial
Description:
Attendance Recorded: Yes

Due to Covid-19, in 2020/21, one or more of the following delivery methods will be implemented based on the current local conditions.
(a) Hybrid delivery, with social distancing on Campus
Teaching Method 1 - Lecture
Description: On-line synchronous/asynchronous lectures
Teaching Method 2 - Tutorial
Description: Mix of on-campus/on-line synchronous/asynchronous sessions

(b) Fully online delivery and assessment
Teaching Method 1 - Lecture
Description: On-line synchronous/asynchronous lectures
Teaching Method 2 - Tutorial
Description: On-line synchronous/asynchronous sessions

(c) Standard on-campus delivery with minimal social distancing.
As our planning has already gone too far, even if the campus opens up, we will offer hybrid teaching
Teaching Method 1 - Lecture
D escription: On-line synchronous/asynchronous lectures
Teaching Method 2 - Tutorial
Description: Mix of on-campus/on-line synchronous/asynchronous sessions


Teaching Schedule

  Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
Study Hours 30

  10

      40
Timetable (if known)              
Private Study 110
TOTAL HOURS 150

Assessment

EXAM Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
(559) Written Exam There is a resit opportunity. Standard UoL penalty applies for late submission. This is an anonymous assessment. Assessment Schedule (When) :2nd Semester  150 minutes.    70       
CONTINUOUS Duration Timing
(Semester)
% of
final
mark
Resit/resubmission
opportunity
Penalty for late
submission
Notes
(559.1) Assessment 1 There is a resit opportunity. Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :2nd semester  30 hours for all CAs    15       
(559.2) Assessment 2 There is a resit opportunity. Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :2nd semester  30 hours for all CAs    15       

Recommended Texts

Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.