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 2016-17 Level 7 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.

  • 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

Have a critical awareness of current problems, important concepts and research issues in  the field of algorithmic game theory.

 

  Systematic knowledge and ability to quantify the inefficiency of equilibria.

 

  Systematic knowledge and ability to formulate mechanism design models or network games for the purpose of modeling particular applications.
  Detailed understanding and ability to use, describe and explain appropriate algorithmic paradigms and techniques in context of a particular game-theoretic or mechanism design problem.
  Critical ability to read, understand and communicate research literature in the field of algorithmic game theory.     
Critical ability to recognise potential research opportunities and research directions in the field of algorithmic game theory.

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, Sponsored Search Auctions, Price of Anarchy in Auctions) (







  • Teaching and Learning Strategies

    Lecture -

    Tutorial -


    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
    Unseen Written Exam  150  2nd Semester  75  Yes  Standard UoL penalty applies  Written Exam Notes (applying to all assessments) 2 (sets of) assessment tasks This work is not marked anonymously. Written examination  
    CONTINUOUS Duration Timing
    (Semester)
    % of
    final
    mark
    Resit/resubmission
    opportunity
    Penalty for late
    submission
    Notes
    Coursework  30 hours for all CAs  2nd semester  10  Yes  Standard UoL penalty applies  Assessment 1 
    Coursework  30 hours for all CAs  2nd semester  15  Yes  Standard UoL penalty applies  Assessment 2 

    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: