Instructor:

Martin Gairing
Ashton Building
Room 3.03
m.gairing [at] liverpool.ac.uk

Meeting Times

• Monday 10:00 - 11:00: Hold223.

• Tuesday 10:00 - 11:00: NICH-NICSR.

• Friday 10:00 - 11:00: Hold223.

Tutorials:

• Tuesday 11:00 - 12:00: NICH-NICSR.

Course Outline and Lecture Notes

1. Introduction

• AGT book - Chapter 1
• slides

• AGT book - Chapter 20
• slides
• What I wrote on the board.

• AGT book - Chapter 18 and 19
• slides
• What I wrote on the board.

• AGT book - Chapter 19
• slides
• What I wrote on the board.

Exercise Sheets

Final continuous assessment task

This task will contribute 10% to your final mark. You will be working in groups on some open promblem related to the material from the lectures. The problem you study could either be one of the examples I presented in the lecture on 13 March 2011. You are also welcome to work on any other problem you like but you need to consult the topic with me.

Alternatively, you can give a presentation and write a 2-page summary on some research paper (no group work). Here, is a list of possible papers (you should have full access to these papers from any machine on campus):

• Congestion games with variable demands
• Efficiency of Restricted Tolls in Non-atomic Network Routing Games
• Stochastic Selfish Routing (assigned to Tianchen Zhu)
• Weakly-Acyclic (Internet) Routing Games (assigned to Bahareh Balazadeh)
• Basic network creation games (assigned to Menglei Shi)
• On Dynamics in Basic Network Creation Games (assigned to Hanxing Chen)
• Stackelberg Strategies for Network Design Games (assigned to Chengtian Jin)
• On Approximate Nash Equilibria in Network Design (assigned to Wenjie Zeng)
• Braess’s Paradox in Large Sparse Graphs
• Bottleneck Congestion Games with Logarithmic Price of Anarchy
• On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games
• The Price of Anarchy in Network Creation Games Is (Mostly) Constant (assigned to Junkai Zhi)
• Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

Presentations will take place on 1 May 2012, 10:00-12:30 in NICH-NICSR. You should handin by then (i) your 2-page summary, and (ii) a handout of your presentation slides.

Schedule:

Time	Speaker	Paper
10:00	Tianchen Zhu	Stochastic Selfish Routing
10:15	Bahareh Balazadeh	Weakly-Acyclic (Internet) Routing Games
10:30	Wenjie Zeng	On Approximate Nash Equilibria in Network Design
10:45	Junkai Zhi	The Price of Anarchy in Network Creation Games Is (Mostly) Constant
11:10	Hanxing Chen	On Dynamics in Basic Network Creation Games
11:25	Menglei Shi	Basic network creation games
11:40	Cheng Tian Jin	Stackelberg Strategies for Network Design Games
11:55	Eleftherios Anastasiadis & Michail Fasoulakis	Coordination Mechanisms for Congestion Games (ongoing research)

Other Resources

• 2012-02-06.pdf
• 2012-02-07.pdf
• 2012-02-13.pdf
• 2012-02-17.pdf
• 2012-02-20.pdf
• 2012-02-21.pdf
• 2012-02-24.pdf
• 2012-02-28.pdf
• 2012-03-02.pdf
• 2012-03-05.pdf
• 2012-03-06.pdf
• 2012-03-09.pdf
• 2012-03-13.pdf
• 2012-03-16.pdf
• 2012-03-19.pdf
• 2012-03-20.pdf
• 2012-04-17.pdf
• 2012-04-20.pdf
• 2012-04-23.pdf

Text Books

Algorithmic Game Theory, Cambridge University Press, 2007.
Nisan, Roughgarden, Tardos, Vazirani, eds.
Book available from here.

• username=agt1user
• password=camb2agt

Assessment

• Coursework: 25 %

  Details will follow.

• Final Exam: 75 %

  The exam will be 2 hours long. Details will follow.