CMSC474: Introduction to Computational Game Theory, Spring 2015

 

Instructor: Mohammad T. HajiAghayi

TA: Sina Dehghani and Reza Khani

Latest Announcements and Assignments (Last updated 5/4/15)

·        Final exam date is Wed, May 20, 10:30 AM - 12:30 PM, CSI 2107

·        Midterm exam is on March 12 in the class 3:30pm-4:55pm

·         Review session for Midterm is on March 10 in the class

·         All assignment release dates and due dates are announced below

·         See the course agenda

·         First lecture is on Jan 27, 2017, 3:30 PM--4:45 PM @ CSI Room 2107

 

     

Assignments and Midterm Schedule (Tentative)

·       Programming Assignments:

o   Release date: Jan 27,

o   Due date of Programming Assignment 1: Feb 28, 11:59pm (see instructions for submission inside the assignment)

o   Due date of Programming Assignment 2: Apr 18, 11pm (see instructions for submission inside the assignment)

o   Due date of Programming Assignment 3: May 8, 11pm (see instructions for submission inside the assignment)

·       Homework 1:

o   Release date: Feb 3,

o   Due date: Feb 19, 3:30pm beginning of the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·       Homework 2:

o   Release date: Feb 19,

o   Due date: Mar 5, 3:30pm beginning of the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·       Review session for Midterm: March 10 in the class

·       Midterm: March 12 in the class 3:30pm-4:55pm

·       Homework 3:

o   Release date: Mar 31,

o   Due date: Apr 21, 3:30pm beginning of the class TBD before the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·       Homework 4:

o   Release date: Apr 28,

o   Due date: May 12, 3:30pm beginning of the class (see instructions for submission inside the assignment)     Solutions to be released the same day.

·        Final EXAM date & place:  Wed, May 20, 10:30 AM - 12:30 PM, CSI 2107

 

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 (including Grading & Evaluation):

 

See the course agenda.

 

Needed Background

 

Minimum grade of C+ in CMSC351 is strongly recommended. 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.

 

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.



Detailed Schedule:

 

01/27/15: Review of course agenda and introduction.

Slides   

01/29/15: Basic probability

            Slides

02/03/15: Basic probability (continued) and an into to 2-player games

            Slides

02/05/15: Normal-form games

            Slides

02/10/15: Important normal-form games.

            Slides 

02/12/15: Analyzing normal-form games.

            Slides

02/17/15: No class due to snow

02/19/15: Finding Nash equilibria and epsilon Nash equilibria.

            Slides

02/24/15: Linear programming and discussing complexity of Nash equilibria (from previous lecture)

            Slides

02/26/15: Dominant strategies, price of anarchy, and Braess’s paradox.

            Slides

03/03/15: Rationalizability and correlated equilibrium

            Slides

03/05/15: No class due to snow           

03/10/15: Maxmin and minmax strategies & Midterm review session in the class 3:30pm-5:15pm

            Slides 

03/12/15: Midterm in the class 3:30pm-4:55pm

 

03/17/15: Spring BreakJ

 

03/19/15: Spring BreakJ

 

03/24/15: Perfect-information extensive form games

            Slides

03/26/15: Guest Lecture by Anshul Sawant: PREVE: a policy recommendation engine based on vector equilibria applied to reducing terrorism attacks  

            Slides

03/31/15: Sub-game perfect equilibrium

            Slides

04/02/15: Game-tree search and pruning algorithms

            Slides

04/07/15: No class due to power outage

04/09/15: Guest Lecture by Prof. Dana Nau: Evolutionary game theory, cultural modeling, and third-party punishment

            Slides

04/14/15: Combinatorial games and the games of NIM

            Slides

04/16/15: Imperfect-information games & Behavioral vs. mixed strategies

            Slides

04/21/15: Repeated games

            Slides

04/23/15: Introduction to auctions

            Slides

04/28/15: More auctions

            Slides

04/30/15: Reversi tournament in the class

05/05/15: Online auctions for dynamic environments

            Slides

05/07/15: Online advertisement auctions

            Slides

            05/12/15: Coalition game theory & Shapley values

            Slides & Slides

(last day of the class)

 

Further Topics (as reading assignments):

 

-------: Evolutionarily stable strategies,

            Slides

-------: Bayesian games & games of incomplete information

            Slides

-------: Network bargaining games

            Slides

-------: Social networks

            Slides

 

            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 2107

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:

Sina Dehghani (firstname.lastname@gmail.com) and

Reza Khani (lastname87@gmail.com)