Seminar in Game Theory - Math 391-02
Prof. Anderson
Spring 2004
MWF 9:00 - 9:50 SW 359

 

 

Syllabus Schedule and Assignments

Syllabus

Text:  Game Theory, manuscript by Thomas Ferguson, UCLA.

Course Webpage: http://math.holycross.edu/~anderson/math125.html

Contact:  My office is Swords 340, phone 793-2459, email:  anderson@mathcs.holycross.edu

Office Hours:  Monday 11 - 12,  Tuesday 11- 12,  2 - 3,  Friday 9 - 10 or by appointment.

Problem Sets: Weekly problem sets.  Problems and due dates are posted on the course webpage.  Problems marked with a * are bonus problems.  Late problem sets are not accepted, except in the case of documented illness.  Working together on problem sets is OK, copying someone else's homework is not.

In-Class Presentation:  Everyone must contribute one in-class presentation (15 - 20 minutes) on a topic from the text.  These will be assigned (on a volunteer basis) on the fly; you will generally have two ot three class periods advance notice.

Exams:  One take-home midterm exam, distributed Friday, March 5; due Friday March 19; and one take-home final, distributed May 3, due May 15.

Final Projects:  A substantial team project, with both presentation and written components.  Teams will consist of three people.   Each team will give a fifty-minute presentation during the last two weeks (April 23 - May 3), and prepare a companion written report (15 - 20 pages).   Each team will contribute two problems for a take-home final based on the projects.

        Project Timetable:

Grading:

 

Component Total Points = 500 Percentage
Problem Sets (10) 20 x 10 = 200 40 %
In-Class Presentation 25 5 %
Midterm (take-home) 75 15 %
Final Project 150 30 %
Final Exam  50 10 %

Academic Honesty:  This course operates under the College and Departmental policies on academic honesty.

Schedule and Assignments
 
 
 

J


 

Day
 Date Topics
Text Sections
  Problem Sets  etc. 
W 1 1/21 Introduction to Impartial Combinatorial Games: Examples, Definition, 
P and N positions. 		 I-1 
 #1 - due Wednesday 1/28
1.5 # 1, 2, 3a, b*, 5, 6a, b* 
2.6 # 1, 2a, c, 3, 7a, b* 
 

 
F 2 1/23 Games as directed graphs, algorithm for finding P and N positions, characterization (axioms). Begin discussion of Nim.  I-1, I-2, I-3
M 3 1/26 Nim-Sum.  Bouton's Theorem,  applications. 
Project Lists Posted 		 I-2
W 4 1/28 Proof of Bouton's Theorem (presentation by Gabe Weaver), the Sprague-Gundy Function of a Graph, P-positions and S-G values. I-2, I-3
#2 - due Wednesday 2/4


3.5 # 1, 2, 3 (find the S-G function up to position 20 or so, and see if you can describe the pattern), 5 (you can save yourself some work by noticing that the values have to be symmetric - interchanging rows and columns doesn't change the answer. 

4.5 # 1, 4, 8, 9, 11a-d,e* 


 
F 5 1/30 S-G value 0 <-> P position 
(presentation by Heather Johnson) 
Sums of games, the S-G Theorem		 I-3, I-4
M 6 2/2 Choice of Projects Due
Application of the S-G Theorem  to Lasker's Nim, Kayles 		 I-4
W 7 2/4 Proof of the S-G Theorem
(presentation by Rosanna Arcuri) Introduction to Matrix Games 
Mixed strategies, expected values		 II-1 # 3 - due Wednesday 2/11
(from chapter II)
1.5 # 1, 3, 4
2.6 # 2, 3, 4a, 5, 6, 7, 8
 
 
F 8 2/6 2 x 2 zero-sum games, solving by equalizing 
payoffs. 		 II-2
M 9 2/9 First Project Consultations this week 
The general concept of value, domination, saddle points.		 II-2
W 10 2/11 Symmetric games (A antisymmetric); V = 0 for symmetric games.  Examples: rock-paper-scissors, Morra
# 4 - due Wednesday 3/3
(from chapter II)
3.7 # 1, 2 (hint: think about saddle points), 3, 4, 9, 13b, 15
4.7 # 2 (hint: B = cA + d for some numbers c,d), 4
5.9 # 2, 3, 10bc

F 11 2/13 Invariant games; using invariance to reduce 
the number of strategies.  Example: Colonel Blotto.
M 12 2/16 General results: the Equilibrium theorem, the Principle of Indifference.
W 13 2/18  Solution of games for which the matrix A is invertible. 
 
F 14 2/20 Solution of games for which the matrix A is invertible. 
M 15 2/23 Solving a game reduces to a linear programming problem: minimize x1 + ... + xn subject to Ax > 1 .
W 16 2/25 Solving a linear programming problem in a simple example.  Start discussion of extensive form games.  
F  17 2/27 Extensive form games, conversion to matrix form. 
M 18 3/1 Second Project Consultations this week 
Algorithm for solving general games (presentation by Joe Hibdon and Kirk Kozol)
W 19 3/3 Two-person general-sum games in matrix and extensive form. 
F 20 3/5 Safety levels and Pure Strategic equilibria. 
Take-home midterm distributed. 
M 3/8 no class - spring break
W 3/10 no class - spring break
F 3/12 no class - spring break
M 21 3/15 Strategic Equilibria.  Finding PSE's and 
general SE's by equalizing strategies. Comparison with safety levels.
W 22 3/17 Prisoner's Dilemma
F 23 3/19 Economic Models I 
Take-home midterm due
M 24 3/22 Evolutionarily Stable Strategies
W 25 3/24 Economic Models II (presentations by Kevin Hyland and Dennis Langer) # 5 - due Wednesday 3/31
(from chapter III) 
 2.5 # 1, 2ab, 4, 5a, 6, 7, 9 
3.5 # 1a, 2 
plus problem on handout about ESS 
F 26 3/26 Proof of Nash's Equilibrium Theorem 
(presentations by Noah Shier and Rich Ghiorse)
M 27 3/29 Cooperative Games - TU and NTU games. 
Payoff sets for NTU games as the convex hull 
of payoffs.  Payoff sets for TU games.
W 28 3/31  Application of Nash's technique to Labor-Management bargaining problem
F 29 4/2  Finding the Nash bargaining solution for NTU games, examples
 

M  30 4/5 Properties of the convex hull (presentation by Jen Strazdins) 
Threat points and side payments in TU games.
W 31 4/7 Proof of Nash's theorem on the bargaining solution 
(presentations by Michelle Greene and Matt Fanning)
F 4/9 no class - Good Friday
 
M 4/12 no class - Easter recess
W 32 4/14 TU games - finding threat point
F 33 4/16 TU Example: Game show contestants (Caitlin Agostinacchio) 
N - person games, games in coalitional (characteristic function) form
M 34 4/19 Carpool example of a game in characteristic function  form (presentation by Josh  Ruffin). Imputations and the core. 
W 35 4/21 Geometric representation of the core in three-person games (presentation by Emmit Ferriter).  Completion of the carpool example. 
F 36 4/23 Matt, Kirk,  Noah : Gambit
M 37 4/26 Caitlin, Joe, Gabe : Surreal Numbers
W 38 4/28 Rosana, Michelle, Heather: Voting Theory I
F 39 4/30 Rich, Jen: Voting Theory II
Handout
M 40 5/3 Emmit, Kevin, Dennis, Josh: Auctions
5/15 Take-home final due

Last modified: May 3, 2004