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)
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.
01/29/15: Basic probability
02/03/15: Basic probability (continued) and an into to 2-player
games
02/05/15: Normal-form
games
02/10/15: Important normal-form games.
02/12/15: Analyzing normal-form games.
02/17/15: No class due to snow
02/19/15: Finding Nash equilibria and epsilon Nash equilibria.
02/24/15: Linear programming and discussing complexity of Nash
equilibria (from previous lecture)
02/26/15: Dominant strategies, price of anarchy, and Braess’s paradox.
03/03/15: Rationalizability and correlated equilibrium
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
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
03/26/15:
Guest Lecture by Anshul Sawant:
PREVE: a policy recommendation engine based on vector equilibria applied to
reducing terrorism attacks
03/31/15: Sub-game perfect equilibrium
04/02/15: Game-tree search and pruning algorithms
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
04/14/15: Combinatorial games and the games of NIM
04/16/15: Imperfect-information games & Behavioral vs. mixed
strategies
04/21/15: Repeated games
04/23/15: Introduction to auctions
04/28/15: More auctions
04/30/15: Reversi tournament in the class
05/05/15: Online auctions for dynamic environments
05/07/15: Online advertisement auctions
05/12/15: Coalition game theory & Shapley values
(last day of the class)
Further Topics (as reading
assignments):
-------: Evolutionarily stable strategies,
-------: Bayesian games & games of incomplete information
-------:
Network bargaining games
-------: Social networks
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: |
|
|
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) |