Welcome to the MATH 100-COSC 49/149 Web Page

Math 100---COSC 49/149

Topics in Probability:
Game Theory

Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)

TA: Ewa Infeld (Ewa.J.Infeld.GR at dartmouth.edu)

Abstract | Classes | Staff | Textbooks | Grading | News and current assignment | Past assignments | Exams | Honor Code


News

X-hour this week, noon Thursday in Kemeny 008. Class also on Wednesday and Friday at 10, as usual, but not Saturday.

Abstract

Game Theory is one of the great accomplishments of modern mathematics, with myriad applications to economics, computer science, political science, decision theory, warfare, and more. This course will tackle the key results in each of the main branches of game theory, using a variety of mathematical techniques.

We will begin with the simplest and most famous game model: two-player, simultaneous, one-move games such as the "prisoners' dilemma," and the notion of Nash equilibrium. (Sadly, John Nash, a "beautiful mind," recently lost his life in a car crash on the NJ Turnpike.) From this we will branch out to multiple players, repeated games, auctions, voting, and mechanism design.

Prerequisites: Mathematical background of a senior mathematics major or a beginning graduate student in mathematics or theoretical computer science; including a course in probability (e.g., MATH 20 or Math 60). If in doubt, please see the instructor. Dist: QDS.

Here is a (tentative) rough weekly syllabus.

1. Matrix games; dominance, mixed strategies, expectation

2. Equilibria and cooperation

3. Multiple players and coalitions

4. Equitability and stable matching

5. Repeated games

6. Voting schemes and voting power

7. Bargaining

8. Bayesian games and auctions

9. Mechanism design

Classes

Room: Kemeny Hall 008
Lectures: "10" slot, in particular: Monday, Wednesday and Friday 10-11:05.
X-hour: Thursdays (same room) 12:00 pm--12:50pm. Will be used only when so announced in class.

Staff

Instructor:
Peter Winkler -- Kemeny Hall 231
Office Hours: Tu 1:30-2:30; W 1:30-2:30; Fr 1:30-2:30.
TA:
Ewa Infeld -- Kemeny Hall 211
Office Hours: M 3:00-4:00, W 6:00-7:00, Th 2:30-3:30.

Textbooks

Steven Tadelis, Game Theory: An Introduction, Princeton University Press, 2012.

Grading

Your grade will be based on homework, class participation, and either a project or a final exam (depending on class size).

Exams

There may be unannounced in-class quizzes, just to make sure everyone is keeping up.
The final exam, if there is one, will be in the regular slot for MWF10 courses.

Homework

Homework will be assigned at each class period, due at the beginning of the next class.

Assignments

Due Friday Sept 18: Read the first three chapters of the text, and:

Count games: Compute the number of different games between two players, each with two possible actions, and in which each player's payoffs for the four possible profiles are different.

Since only the order of the payoffs matters, you can assume (if you wish) that the payoffs are 0, 1, 2 and 3. But notice that switching rows (i.e., relabeling Player 1's actions) or columns (Player 2's actions) does not change the game, nor does interchanging the roles of the two players.

Due Monday Sept 21: Read Chapter 4 of the text, and:

Prove that equilibrium solutions are IESDS solutions: For two player games (more, if you want), with finitely many actions for each player, show that equilibrium profiles---that is, profiles in which neither player would wish to change strategy if the other stayed put---will never be elimimated by IESDS. Putting it another way, no player will have a dominated strategy that's part of an equilibrium profile.

Due Wednesday Sept 23: Do Exercise 3.7, p. 58.

Due Friday Sept 25: Reread Chapters 1 and 2, and do Exercise 2.5, p. 34.

Due Monday Sept 28: Disprove the remark on the bottom of p. 75 of your text, by supplying a 2-player game in which rationalizability results in strictly fewer solutions than IESDS. Mixed strategies are not considered here. If you feel up to it, try to make the game symmetric.

Due Wednesday Sept 30: Read Chapters 4 and 5, and do Exercise 5.9, p. 97.

Due Thursday Oct 1: Do Exercise 5.17, p. 100, and begin reading Chapter 6.

Due Monday Oct 5: Do Exercise 6.5 (Cops and Robbers), p. 124, and continue reading Chapter 6.

Due Wednesday Oct 7: Do Exercise 6.7 (Grad School Competition), p. 124, and finish reading Chapter 6.

Due Friday Oct 9: Alice has a choice between playing "Odds and Evens" for $1 or for $1000, and of course a choice between putting out one finger or two. Bob has the latter choice. Trouble is, Alice can't really afford to lose $1000; she estimates that her utility for doing so is -1500. Complete the analysis of this game, considering all strategies pure and mixed, using (a) IESDS, and (b) rationalizability.

Due Monday Oct 12: Do Exercise 6.11 (Bribes), p. 126, and finish reading Chapter 6.

Due Wednesday Oct 14: Use Kakutani's Fixed Point Theorem to prove that a symmetric two-player game, in which each player has the same finite choice of actions, has a (mixed) symmetric Nash equilibrium.

Due Friday Oct 16: Do Exercise 6.9, p. 125, completely by yourself.

Due Monday Oct 19: Do Exercise 7.5 (Veto Power), p. 148, and read Chapter 7.

Due Wednesday Oct 21: Do Exercise 8.5 (Technology Adoption), p. 170, and read Chapter 8 through 8.3.3.

Due Thursday Oct 22: Do Exercise 8.11 (RA Selection with a Twist), p. 172, and finish reading Chapter 8.

Due Friday Oct 23: Analyze the game of Turn-die to determine whether you should opt to play first or second. (You must decide before the die is rolled.)

Due Monday Oct 26: (a) Analyze the subtraction game where Alice and Bob begin with n and each in turn subtracts either 2, 3, or 4, with the object leaving a non-negative number (so that the first person to hit a negative number loses). By analyze, I mean identify the P and N positions and prove correctness. (b) Do the same for the game where no player is allowed to subtract the number that was last subtracted.

Due Wednesday Oct 28: Read Chapter 9 and do Exercise 9.3.

Due Friday Oct 30: Read Chapter 10 and do Exercise 10.3.

Due Monday Nov 2: Read Chapter 11 and do Exercise 11.7 (Legislative Bargaining Revisited).

Due Wednesday Nov 4: You get to make one bid on a rug that's worth $250 to you, but whose value to the owner is a random variable with triangular density between $150 and $250, value 0 at the ends, and peak at $200. How much should you bid?

Due Friday Nov 6: Read Chapter 12 and do Exercise 12.5 (Not All That Glitters). Start reading Chapter 13, too, if you like.

Due Monday Nov 9: Read 13.1 and do Exercise 13.3 (Reserve Prices).

Due Wednesday Nov 11: In a second-price sealed-bid auction where each of the N players has independent private value uniform in [0,1], with the object destined to be destroyed if it is not sold, what should the reserve price be to maximize expected revenue?

Due Friday Nov 13: Finish reading Chapter 13 and do Exercise 13.6 (3rd-Price Auction).

Due Monday Nov 16: Read Chapter 14 do Exercise 14.1 (Brothers).

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.