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 Computational Game Theory and Mechanism Design
Code COMP326
Coordinator Dr G Christodoulou
Computer Science
G.Christodoulou@liverpool.ac.uk
Year CATS Level Semester CATS Value
Session 2016-17 Level 6 FHEQ Second Semester 15

Aims
  • To provide an understanding of the inefficiency arising from uncontrolled, decentralized resource allocation.
  • To provide a foundation for modelling various mechanism design problems together with their algorithmic aspects.
  • 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.
  • To review the links and interconnections between algorithms and computational issues with selfish agents.

Learning Outcomes

Have a systematic understanding of current problems and important concepts in the field of computational game theory.

Ability to quantify the inefficiency of equilibria.

The ability to formulate mechanism design models or network games for the purpose of modeling particular applications.

The ability to use, describe and explain appropriate algorithmic paradigms and techniques in context of a particular game-theoretic or mechanism design problem.

Syllabus
1 
  • 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 Incen tive 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, Sponsored Search Auctions, Price of Anarchy in Auctions) (4 lectures)

Teaching and Learning Strategies

Lecture - Formal Lectures

Tutorial - Tutorials

Teaching Schedule
  Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
Study Hours 30
Formal Lectures
  10
Tutorials
      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
Unseen Written Exam  150  Semester 2  80  No reassessment opportunity  Standard UoL penalty applies  Written Exam There is no reassessment opportunity, No resit opportunity for final year students, only at the next ordinary sitting (subject to confirmation by the Board of Examiners). Notes (applying to all assessments) No resit opportunity for final year students, only at the next ordinary sitting (subject to confirmation by the Board of Examiners). 
CONTINUOUS Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
Coursework    Second Semester  10  No reassessment opportunity  Standard UoL penalty applies  Open Problems. There is no reassessment opportunity, No resit opportunity for final year students, only at the next ordinary sitting (subject to confirmation by the Board of Examiners). 
Coursework    Second Semester  10  No reassessment opportunity  Standard UoL penalty applies  Open Problems. There is no reassessment opportunity, No resit opportunity for final year students, only at the next ordinary sitting (subject to confirmation by the Board of Examiners). 

Recommended Texts
Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.
Explanation of Reading List:

Main textbook 

  • Algorithmic Game Theory - Nisan, Noam, Roughgarden, Tim, Tardos, Eva, Vazirani, Vijay V. 2007 (electronic book)

Recommended textbooks

  • Microeconomic theory - MAS-COLELL, Andreu, WHINSTON, Michael D., GREEN, Jerry R. 1995
  • Combinatorial auctions - Cramton, Peter C., Shoham, Yoav, Steinberg, Richard 2006
  • Mechanism Design- A Linear programming approach by Rakesh V. Vohra 2011
  • Bayesian Mechanism Design by Jason Hartline, 2013