Postgraduate Course: Algorithmic Game Theory and its Applications (INFR11020)

Course Outline
School	School of Informatics	College	College of Science and Engineering
Course type	Standard	Availability	Available to all students
Credit level (Normal year taken)	SCQF Level 11 (Postgraduate)	Credits	10
Home subject area	Informatics	Other subject area	None
Course website	http://course.inf.ed.ac.uk/agta	Taught in Gaelic?	No
Course description	Game theory is the formal study of interaction between "self-interested" (or "goal-oriented") "systems" (or "agents" or "decision makers" or "players"), & strategic scenarios that arise in such settings. It began life in Economics in the 1940's with the work of von Neumann & Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology & even to inspection regimes for arms control. Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification & model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics & computing have received extensive attention. These include electronic auctions, & more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet. Wherever game theory plays a quantitative role, algorithmic and computational questions related to "solving" games are also of central importance. This course aims to bring together as a coherent body of knowledge the game theoretic algorithms & models that underpin several flourishing subjects at the intersection of computer science, economics and e-commerce, & AI.

Entry Requirements (not applicable to Visiting Students)
Pre-requisites	It is RECOMMENDED that students have passed Algorithms and Data Structures (INFR09006)	Co-requisites
Prohibited Combinations		Other requirements	This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser. Some mathematical maturity, and concretely some basic background in: - Linear Algebra - Discrete Mathematics - Probability at the level of the year 1 and 2 required undergraduate courses in these topics. Background in algorithms at the level of Inf2B (INFR08009) and preferably at the level of Algorithms and Data Structures (INFR09006). Exposure to computational complexity theory (NP - completeness, etc.) at the level of Computational Complexity (INFR10008) is desirable but not required.
Additional Costs	None

Information for Visiting Students
Pre-requisites	None
Displayed in Visiting Students Prospectus?	Yes

Course Delivery Information

Delivery period: 2013/14 Semester 1, Available to all students (SV1)			Learn enabled: No	Quota: None
Web Timetable	Web Timetable
Course Start Date	16/09/2013
Breakdown of Learning and Teaching activities (Further Info)	Total Hours: 100 ( Lecture Hours 20, Seminar/Tutorial Hours 8, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 68 )
Additional Notes
Breakdown of Assessment Methods (Further Info)	Written Exam 70 %, Coursework 30 %, Practical Exam 0 %
Exam Information
Exam Diet	Paper Name	Hours & Minutes
Main Exam Diet S2 (April/May)		2:00

Delivery period: 2013/14 Semester 1, Part-year visiting students only (VV1)			Learn enabled: No	Quota: None
Web Timetable	Web Timetable
Course Start Date	16/09/2013
Breakdown of Learning and Teaching activities (Further Info)	Total Hours: 100 ( Lecture Hours 20, Seminar/Tutorial Hours 8, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 68 )
Additional Notes
Breakdown of Assessment Methods (Further Info)	Written Exam 70 %, Coursework 30 %, Practical Exam 0 %
Exam Information
Exam Diet	Paper Name	Hours & Minutes
Main Exam Diet S1 (December)		2:00

Summary of Intended Learning Outcomes
1 - Understanding of various models of games. 2 - How they are related, and how they arise in various applications in computer science and elsewhere. 3 - An understanding of linear programming and some of its broad applicability. 4 - An understanding of algorithms used to "solve" such games and their efficiency. 5 - Ability to model various scenarios as strategic games, and devise algorithms to solve them. 6 - An understanding of some of the aims of the current research frontier. 7 - Refinement of analytical skills. 8 - The following learning outcomes are all to be demonstrated via a combination of coursework and the exam.

Assessment Information
Written Examination 70 Assessed Assignments 30 Oral Presentations 0 Assessment Students will be given written practical assignments reinforcing the material taught in class. Some of the practical work may ask students to implement parts of algorithms for "solving" a game that arise in one of the application areas. If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year.

Special Arrangements
None

Additional Information
Academic description	Not entered
Syllabus	* Examples of diverse games. * Zero-sum two-person games: LP, simplex, LP-duality, mixed strategies and the minimax theorem. * General games in strategic form: o Equilibria and Nash's theorem. o 2-player equilibria: Lemke-Howson algorithm and its variants. * Games in Extensive form (mainly zero-sum, perfect information): o Game trees. Relation to Strategic games. o And/Or game graphs and reachability games. o bisimulation, simulation, parity games, and other omega-games on automata(finitely presented, infinite duration games). o mean value games, MDPs, and stochastic games. * Mechanism design and inverse game theory: designing games where selfish players will behave as desired. o Vickery auctions and other mechanisms. o Combinatorial auctions. o Incentive structures for the internet. Relevant QAA Computing Curriculum Sections: Artificial Intelligence, Data Structures and Algorithms, e-commerce, Simulation and Modelling, Theoretical Computing
Transferable skills	Not entered
Reading list	Multiagent Systems, Y.Shoham & K. Leyton-Brown, Cambridge University Press 2009 * Relevant references include: * "Linear Programming" by V. Chvatal, * "Game Theory" by Osborne and Rubinstein, "Game Theory: Anaysis of Conflict" by R. Myerson, several chapters from "Handbook of Game Theory, vol. I-III" * Chapters from "Automata, logic, and infinite games", (Eds.) Gradel, Thomas, and Wilke. * Survey papers, including "Algorithms, games, and the internet" by Papadimitriou, "Two-person equilibria" by von Stengel, and "Algorithmic Mechanism Design" by Nisan and Ronen
Study Abroad	Not entered
Study Pattern	Lectures 20 Tutorials 8 Timetabled Laboratories 0 Non-timetabled assessed assignments 32 Private Study/Other 40 Total 100
Keywords	Not entered

Contacts
Course organiser	Dr Iain Murray Tel: (0131 6)51 9078 Email: I.Murray@ed.ac.uk	Course secretary	Ms Katey Lee Tel: (0131 6)50 2701 Email: Katey.Lee@ed.ac.uk