CO 456: Introduction to Game Theory (Fall 2016)

Instructor: David Jao, djao@math, MC 5032
Office hours: Mon. & Tue. 2:00pm-3:00pm

Teaching assistants:

Justin Toth	wjtoth	MC 5023B	Office hours: Wed. & Fri. 1:30pm-2:30pm
Youngho Yoo	yh2yoo	MC 5468	Office hours: Thu. 4:30pm-5:30pm

Please join the discussion forum on Piazza (https://piazza.com/) for assistance with the course.

Course materials

• Course outline (https:../../wiki/images/3/3f/CO456-2016-outline.pdf)
• Practice midterm problems (https:../../wiki/images/4/4a/CO456-2015-midterm.pdf)
• Practice final examination (https:../../wiki/images/1/10/CO456-2016-final.pdf)

Schedule

The (tentative) schedule for the course is as follows:

• Assignment 1 (https:../../wiki/images/7/76/CO456-2016-a1.pdf) (due Friday, September 23). (Solutions (https:../../wiki/images/1/18/CO456-2016-s1.pdf))
• Assignment 2 (https:../../wiki/images/b/bc/CO456-2016-a2.pdf) (due Friday, October 7). (Solutions (https:../../wiki/images/3/30/CO456-2016-s2.pdf))
• Assignment 3 (https:../../wiki/images/9/94/CO456-2016-a3.pdf) (due Friday, October 21). (Solutions (https:../../wiki/images/b/b2/CO456-2016-s3.pdf))
• Midterm examination: Friday, October 28, 6:30pm-8:00pm in MC 4059
• Assignment 4 (https:../../wiki/images/c/c6/CO456-2016-a4.pdf) (due Friday, November 11). (Solutions (https:../../wiki/images/c/c2/CO456-2016-s4.pdf))
• Assignment 5 (https:../../wiki/images/c/c8/CO456-2016-a5.pdf) (due Friday, December 2). (Solutions (https:../../wiki/images/9/9f/CO456-2016-s5.pdf))
  • Correction (November 21): In problem 1, the game must be assumed to be superadditive. PDF file has been updated with this correction.

Lectures

1. Introduction (https:../../wiki/images/5/59/CO456-2016-slides01.pdf) (September 9)
2. The game of NIM (https:../../wiki/images/1/12/CO456-2016-slides02.pdf) (September 12)
3. Equivalence of games (https:../../wiki/images/0/03/CO456-2016-slides03.pdf) (September 14)
4. Classification of NIM games (https:../../wiki/images/0/0b/CO456-2016-slides04.pdf) (September 16)
5. Impartial combinatorial games (https:../../wiki/images/0/03/CO456-2016-slides05.pdf) (September 19)
6. Game trees (https:../../wiki/images/4/47/CO456-2016-slides06.pdf) (September 21)
7. Strategic form (https:../../wiki/images/6/6d/CO456-2016-slides07.pdf) (September 23)
8. Nash equilibrium (https:../../wiki/images/4/47/CO456-2016-slides08.pdf) (September 26)
9. Atomic selfish routing (https:../../wiki/images/9/99/CO456-2016-slides09.pdf) (September 28)
10. Non-atomic selfish routing (https:../../wiki/images/6/66/CO456-2016-slides10.pdf) (September 30)
11. Nash flows (https:../../wiki/images/9/99/CO456-2016-slides11.pdf) (October 3)
12. Mixed strategies (https:../../wiki/images/c/ce/CO456-2016-slides12.pdf) (October 5)
13. Brouwer fixed point theorem (https:../../wiki/images/6/6b/CO456-2016-slides13.pdf) (October 7)
14. Support characterization theorem (https:../../wiki/images/c/cb/CO456-2016-slides14.pdf) (October 14)
15. Nash's existence theorem (https:../../wiki/images/1/1a/CO456-2016-slides15.pdf) (October 17)
16. Zero-sum games (https:../../wiki/images/0/08/CO456-2016-slides16.pdf) (October 19)
17. Lemke-Howson algorithm (https:../../wiki/images/b/b0/CO456-2016-slides17.pdf) (October 21)
18. Lemke-Howson example (https:../../wiki/images/3/3a/CO456-2016-slides18.pdf) (October 24)
19. Course project information (https:../../wiki/images/d/d8/CO456-2016-slides20.pdf) (October 31)
20. Cooperative games (https:../../wiki/images/4/40/CO456-2016-slides21.pdf) (November 2)
21. Shapley value and Shapley core (https:../../wiki/images/9/92/CO456-2016-slides22.pdf) (November 4)
22. Shapley core properties (https:../../wiki/images/2/2d/CO456-2016-slides23.pdf) (November 7)
23. Convex games and Bondareva-Shapley (https:../../wiki/images/d/d2/CO456-2016-slides24.pdf) (November 9)
24. Matching games (https:../../wiki/images/a/ab/CO456-2016-slides25.pdf) (November 11)
25. Nucleolus (https:../../wiki/images/5/56/CO456-2016-slides26.pdf) (November 16)
26. Properties of the nucleolus (https:../../wiki/images/2/22/CO456-2016-slides27.pdf) (November 18)
27. Job matching (https:../../wiki/images/0/03/CO456-2016-slides28.pdf) (November 21)
28. Voting theory (https:../../wiki/images/0/0c/CO456-2016-slides29.pdf) (November 23)
29. Auction theory (https:../../wiki/images/d/da/CO456-2016-slides30.pdf) (November 25)
30. VCG auctions (https:../../wiki/images/8/82/CO456-2016-slides31.pdf) (November 28)
31. Optimal auction theory (https:../../wiki/images/6/6d/CO456-2016-slides32.pdf) (November 30)
32. Repeated games (https:../../wiki/images/9/9f/CO456-2016-slides33.pdf) (December 2)