CMSC474: Introduction to Computational Game Theory, Fall 2013

 

Instructor: Mohammad T. HajiAghayi

TA: Hossein Esfandiari

 

Latest Announcements and Assignments (Last updated 12/10/13)

·      Final-exam date is December 21, 2013 (Sat) 10:30am-12:30pm at  CSI 1121 

·       Midterm is on Nov 21 in the class

·        Review session for Midterm is on Nov 19 in the class

·        Assignment release dates and due dates are announced below

·        See the course agenda

·        First lecture on Sep 3, 2013

 

     

Assignments and Midterm Schedule (Tentative)

·      Assignment 1:

o   Release date: Sep 12,

o   Due date: Sep 26 before the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·      Assignment 2:

o   Release date: Oct 10,

o   Due date: Oct 24 before the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·      Assignment 3:

o   Release date: Nov 5,

o   Due date: Nov 19 before the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·      Review session: Nov 19 in the class

·      Midterm date: Nov 21, 2013 in the class

·      Assignment 4:

o   Release date: Nov 28,

o   Due date: Dec 12 before the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·       Final date: December 21, 2013 (Sat) 10:30am-12:30pm at CSI 1121

 

Brief Course Description


Mechanism Design in particular Algorithmic Game Theory, which can be viewed as ``incentive-aware algorithm design'', has become an increasingly important part of computer science in recent years. In this course, we review the basics of game theory and algorithmic game theory and we consider several game theoretic scenarios in the class.

 

Course Agenda:

 

See the course agenda.

 

Reference Books:

 

Essentials of Game Theory: A Concise, Multidisciplinary Introduction, by Leyton-Brown, Morgan and Claypool Publishers, 2008.
Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani, Cambridge University Press, 2007.

Notes from the webpage of a similar course taught by Professor Nau.

Detailed Schedule:

 

Disclaimer: some slides are taken from slides of co-designer of this course at UMD Professor Dana

Nau

09/03/13: Review of course agenda and introduction.

Slides   

09/05/13: Normal-form games.

            Slides

09/10/13: Important normal-form games.

            Slides

09/12/13: Analyzing normal-form games.

            Slides

09/17/13: Road networks and Braess’s paradox.

            Slides

09/19/13: Finding Nash equilibria.

            Slides

09/24/13: Rationalizability and price of anarchy.

            Slides

09/26/13: Maxmin and minmax strategies.

            Slides

10/01/13: Dominant strategies and correlated equilibrium.

            Slides

10/03/13: Computing correlated equilibrium (continuing previous session) and epsilon-Nash equilibrium

            Slides

10/08/13: Evolutionarily stable strategies, and Quiz 1

            Slides

10/10/13: Perfect-information extensive form games, and answer to Quiz 1 (in class)

            Slides

10/15/13:  Guest Lecture by Anshul Sawant: Epsilon approximate equilibria with multiple payoffs and no priors

            Slides

10/17/13: Sub-game perfect equilibrium

            Slides

10/22/13: Imperfect-information games

            Slides

10/24/13: Behavioral vs. mixed strategies

            Slides

10/29/13: Repeated games

            Slides

10/31/13: Bayesian games & games of incomplete information

            Slides

11/05/13: Coalition game theory

            Slides

11/07/13: Shapley values

            Slides

11/12/13: Guest Lecture by Aravind Srinivasan: Social networks

            Slides

11/14/13: Introduction to auctions

            Slides

11/19/13: Midterm review session

           

11/21/13: Midterm

 

11/26/13: Guest Lecture by Hamid Mahini: Network bargaining games

            Slides

11/28/13: Thanksgiving: Happy holidayJ

 

12/03/13: More auctions

            Slides

12/05/13: Online advertisement auctions

            Slides

12/10/13: No class: University is closed due to snow

12/12/13: Game-tree search and pruning algorithms (last day of the class)

            Slides

 

 

Prerequisites

 

Minimum grade of C- in CMSC351; or permission of CMNS-Computer Science department. If you are unsure of whether you have sufficient background for this course or not, please contact the instructor in the first week of the class or before.

 

Tentative Grading & Evaluation

 

See the course agenda above.

 

            Other Resources (from here)

 

            Tips for good technical writing

           The elements of style by William Strunk Jr. and E. B. White (follow the "External links" at the bottom of this page for online copies of this book).

           Writing a technical paper, by Professor Michael Ernst.

                 Tips for writing technical papers, by Professor Jennifer Widom.

           Writing suggestions, by Professor Barton Miller.

           How to write a dissertation, by Professor Douglas Comer (most of the content on this page applies to all forms of technical writing).

 

            Tips for effective presentation

           Giving a technical talk, by Professor Michael Ernst.

           Tips for a good conference talk, by Professor Jennifer Widom.

           Oral presentation advice, by Professor Mark Hill.

 

General Information

Instructor:

Mohammad T. HajiAghayi

Time and Location:

Tue-Thu, 3:30 PM--4:45 PM, @ CSI Room 1121

Office hours:      

By appointment via e-mail OR Thu 12:00PM-1:00PM at A.V. Williams Bldg., Room 3249.

Office:

3249 A.V. Williams

Phone:

301-405-2741

Email:

The first 8 letters of instructor’s last name (AT) cs (DOT) umd (DOT)  edu

TA:

Hossein Esfandiari

TA’s Email

lastname.firstname@gmail.com