Introduction to Computational Game Theory

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.

Instructor: Mohammad T. HajiAghayi, Office: 3249 A.V. Williams

TA's: Saeed Seddighin (saeedreza.seddighin@gmail.com) and Joon Kim (dongjoon999@gmail.com)

Classes: MW 2:00pm - 3:15pm, CSI, Room #3117

Requirement: 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.

Course agenda: [pdf]

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.

Office hours

• Instructor: Mon 12:30PM-1:30PM at A.V. Williams Bldg., Room #3249
• TA: Tue 9:00AM-11AM at A.V. Williams Bldg., Room #1120 (Saeed Seddighin), Thu 9:00AM-11AM at A.V. Williams Bldg., Room #4101/4103 (Joon Kim)

Homework:

1. Homework 1 (due date: September 20, 2017 )
2. Homework 2 (due date: October 11, 2017)
3. Homework 3 (due date: November 1, 2017)
4. Homework 4 (due date: November 29, 2017)

Projects:

1. Project 1 (due date: October 24, 2017)
2. Project 2 (due date: November 17, 2017)
3. Project 3 (due date: December 10, 2017)

Exams

• Mid Term (November 8)
• Final (December 16)

Class Topics

• Review of course agenda and introduction Slides
• Basic probability Slides
• Basic probability (continued) and an into to 2-player games Slides
• Linear programming Slides
• Normal-form games Slides
• Important normal-form games Slides
• Analyzing normal-form games Slides
• Finding Nash equilibria and epsilon Nash equilibria Slides
• Dominant strategies, price of anarchy, and Braess’s paradox Slides
• Rationalizability and correlated equilibrium Slides
• Maxmin and minmax strategies Slides
• Perfect-information extensive form games Slides
• A policy recommendation engine based on vector equilibria applied to reducing terrorism attacks Slides
• Sub-game perfect equilibrium Slides
• Game-tree search and pruning algorithms Slides
• Evolutionary game theory, cultural modeling, and third-party punishment Slides
• Imperfect-information games & Behavioral vs. mixed strategies Slides
• Repeated games Slides
• Combinatorial games and the games of NIM Slides
• Introduction to auctions Slides
• More auctions Slides
• Online auctions for dynamic environments Slides
• Online advertisement auctions Slides
• Coalition game theory & Shapley values Slides & Slides

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