CO 456 Syllabus, Fall 2008

The course homepage is located at the address below. Contact information, office hours, and the required text are listed there.

http://www.math.uwaterloo.ca/~dagpritc/co456/

Collaboration Policy

• Independent Problem.
  
• Do not discuss this problem with anyone except for course staff.
• Collaborative Problem.
  
• You can work on this problem with up to 2 of the other students in this class, but
  
• you must write up your solutions independently - no copying!
• you must list all of your collaborators.
• Note, you can work on these problems alone if you like.
  
• Fun Problem.
• This problem is not for credit; don't hand in a solution.
  

If you want to post or discuss any course material online, you need to get permission of the course staff first. (Notwithstanding, discussing collaborative work via IM or e-mail is allowed.)

Failure to adhere to the collaboration policy has the following minimum penalty: a grade of 0% for that assignment/project, a 5% deduction from your final grade, and a report to the Dean.

• If you give your solutions to a friend, who then copies them and hands in the copy, it will count as if you had violated the collaboration policy (and them, also).
• When in doubt, ask me ahead of time!
  

Evaluation

There will be roughly one item (homework, project, or midterm) due every week of the term.

• homework (20%)
• about 6 homework assignments
  
• hand in at the beginning of class
• late submissions lose 10% or more of their value
  
• once solutions are posted online, no further late submissions can be accepted
• projects (20%)
  
• 3 or 4 small projects
• can work alone or in a pair
  
• will include a Java programming component
• final project: you get to choose the topic, subject to some constraints. a small presentation will be involved. (more details TBA)
  
• 2 hour midterm exam (25%)
  
• 2.5 hour final exam (35%)

Content

After the introduction, the course breaks into 4 units of approximately equal size:

Strategic Games

• Payoffs, actions, outcomes, rational players.
• Dominated actions, best responses, iterated elimination.
• Pure Nash equilibria.
• Examples: the prisoner's dilemma, auctions, oligopoly [1800s].
• Modeling lots of homogeneous players with population games.

Strategic Games, Part 2: Mixed Strategies and Mixed Equilibria

• Mixed strategies, expected value preferences, mixed domination.
• Nash equilibria, Nash's theorem [1950]. Interpretation.
  
• Finding Nash equilibria:
• in 2x2 games.
• using linear programming for 2-player zero-sum games. [1926]
  
• using the Lemke-Howson algorithm for general 2-player games. [1964]
  
• (Fixed point theorems and proof of Nash's theorem in general.)

• Modeling a game with actions and responses.
• A refinement of Nash equlibria: Subgame perfect equlibria. [1975]
  
• Backwards induction.
  
• Plausibility of "perfectly rational" players: the centipede game and chain-store game.
• Adding simultaneous moves and chance moves.
• (What's beyond: games of incomplete information.)

• How to "add" two combinatorial games.
• Tweedledum-Tweedledee strategies.
• The directed graph of a combinatorial game, finding its winning positions.
  
• Nim [1902]. Grundy values. The Sprague-Grundy formula [1930s]. Winning all impartial combinatorial games.

Learning Objectives

• Use the basic terminology and common notation of game theory.
  
• Given a multi-party decision-making situation, determine if any of the strategic, extensive, or combinatorial game models applies to it.
• Find dominated actions and pure equilibria in games.
• Understand and utilize some "tricks of the trade": linear programming, backwards induction.
• Explain and prove fundamental results in game theory.
  
• Given an outcome of a game, argue whether or not it is plausible.
• Use computers where pen and paper are too slow, e.g., to solve a linear program, to compute an optimal strategy, or to simulate a game.

click to go back to the course website