CO 456: Introduction to Game Theory, Fall 2008 CO 456: Introduction to Game Theory, Fall 2008This course offers a broad introduction to game theory and its applications. In it, we will study models of competition, cooperation and multi-party decision-making. Examples will be drawn from economics, society, and traditional games. The main topics will be the “strategic game” model (Nash equilibria, mixed strategies), the “extensive game” model (subgame perfect equilibria), and the “impartial game” model (Sprague-Grundy theory, Nim).
You will be asked to complete 6 assignments, 3 projects, a midterm and a final. You will get to choose the topic of your final project.
| Nov 18 | Nov 20 | Nov 25 | Nov 27 |
|---|---|---|---|
| Moniz | Samuel/Sun | Valieva | Ahmadian/Demirtas |
| Muzzerall/Kalai | Murdoch | Simpson | Jaroszewski |
| Byrne/Lopyrev | Ho/Wai | Engelking | Yuen/Kwong |
| Paterson | Arajs/Hussain | Coulombe | |
| Kou/Ryoo | Steiner/Wollaston | Denisenkov/Santos |
Click here for the syllabus (grading scheme, collaboration policy, detailed course content).
Office hours and contact information:
Pre-requisites: (MATH 239/249 and either CO 350 or CO 352/CM 340) or CO 355. Some knowledge of probability, linear programming, proof-writing and Java will be helpful.
Lectures: Tues & Thurs from 11:30 to 1:00 in MC 2034.
Assignment 1, due September 18.
Assignment 2, due September 25.
Assignment 3, due October 2.
Project 1, due October 16. Here is the code. Tournament results (1 page pdf) and full output / source code (4 MB zipped). For comparison, here are the Fall 07 results.
Assignment 4, due October 21.
Practice midterm (from fall 07); its solutions are available on ACE.
Assignment 5, due date extended to November 4.
The final project proposal is due November 6.
Project 2, due November 11. Here is the code. Final results and source code of submissions.
Assignment 6, due November 25.
Final project presentations will be November 18-27.
Final project writeup will be due December 1 (any time during the day, in my office or under the door).
Practice final exam (Fall 07; skip Q6a and Q7). Solutions are available on ACE. [Q4bc solutions corrected 5/12]
Final exam will be Tuesday December 9, 2008 from 12:30-3:00 PM in PAC 9.
November 13: (Extra material, not on exam) Fixed-point theorems and the proof of Nash's theorem.
November 11: How to win at Nim. Xor rule for g(G+H). How to win in any impartial combinatorial game. Sample analysis of take-and-break games (Ferguson section 4.3-4.4).
For impartial combinatorial games, the following page of notes from last year may be useful.
November 6: Proof of P-ignorance. Refining P vs N: the (Sprague-)Grundy function (Ferguson section 3.2). Winning strategy for Nim (Ferguson section 2). Proof of Sprague-Grundy theorem.
November 4: P-positions and N-positions. Sums of games and some properties. (Reference: von Stengel Sections 1.1-1.5, Ferguson Section 4.1). Proof of copycat principle, cancelling P-games (von Stengel section 1.6), N + N = ?.
October 30: Repeated games, infinitely repeated games. (Osborne 14-15) The one-deviation property for infinitely repeated strategic games. Hands-on introduction to impartial combinatorial games.
October 28: Examples: repeated Prisoner's Dilemma. (Osborne 14.10.1) The one-deviation property (Osborne 438.1 & 439.2).
October 23: An example of an extensive game: Edgeworth duopoly (Osborne 6.2). Adding simultaneous & chance moves (Osborne 7.1, 7.6).
October 21: Discussion for midterm review. Here are some links if you are interested in cake-cutting games: wikipedia and Brams-Taylor 1995.
October 16: Converting extensive games to strategic form, subgame perfect equilibria, backwards induction. (Osborne 5.3-5.5) Examples.
October 14: Extensive Games: model and examples. (Osborne 5.1-5.2)
October 9: The Lemke-Howson algorithm. Proof of Nash's theorem for all 2-player games. Notes. The example is from a survey by von Stengel.
October 7: Maxminimization. Proof of Nash's theorem for 2-player zero-sum games. Notes (corrected version posted Oct 16; fixed LP on page 6).
I said something about "linearity of expectation" in this lecture (Oct 7). It may be helpful to see the short formal proof of my claim.
Claim: in a 0-sum game, sum(u_i(alpha), i=1..n)=0 for all mixed action profiles alpha.
Proof: Let E[x] denote the expected value of the random variable x. By definition of utility in mixed profiles with von-Neumann Morganstern preferences, u_i(alpha) is E[u_i(a)] where the random variable a is defined by the mixed action profile alpha. So
sum(u_i(alpha), i=1..n)
=sum(E[u_i(a)], i=1..n)
=E[sum(u_i(a), i=1..n)] <-- by linearity of expectation
=E[0] <-- since the game is zero-sum
=0.
October 2: Support Characterization (Osborne 116.2). Examples. Project 1 demonstration.
Sept 30: Introduction to mixed strategies (Osborne 4.1-4.2). Mixed Nash Equilibria. Proof of Support Characterization (Osborne 116.2).
Sept 25: Examples of weak domination (Osbone 2.9.2, 2.9.4). Auctions (Osborne 3.5).
Sept 23: Short proofs for Bertrand and Hotelling's election model (Osborne 3.2-3.3). Weak domination.
Sept 18: NE of simple Cournot & Bertrand oligopoly (Osborne 3.1-3.2).
Sept 16: Proof that NEs survive iter del of st dom strat's. (Osborne 12.2). Osborne Ex 34.2(a). Population games: adopting technology and simple traffic game. Notes.
Sept 11: Def'n of strategic game. (Iterated) strict domination, best responses, Nash equilibria. Prisoner's Dilemma. (Osborne Chap. 2)
Sept 9: Syllabus, collaboration policy, aims & scope. Examples of games. Zermelo's theorem.
The following textbook is required and will be available at the South Campus Hall bookstore; it is also sold online (e.g., here and here). You can find errata here. It shall be available on 3-hour reserve loan from the Davis Centre library.
An Introduction to Game Theory. Martin J. Osborne, Oxford University Press 2004.