Homework 2, Problems due October 18, Blog post due October 24
Read as much of Chapter 3 in
these notes as you can (and/or are interested in). You might also want to look
at Sections 3.1-3.3 in this book.
- Peres book, page 111, Problem 3.1
- Peres book, page 114, Problem 3.10
- Consider a 2-player (general-sum) game, where the first player has n pure strategies
and the column player has m pure strategies. The payoffs to the players are
given by two matrices A and B.
Give a finite algorithm for finding a Nash equlibrium in this game. Your algorithm
may run in exponential time. Hint: Consider the condition for a player to put
positive probability on each of a particular subset of his strategies (and no
probability on the remaining strategies).
- Blogging assignment (due October 24): Find and discuss on our blog an article
that is related in some way to the content of this course. You can find relevant online articles
in pretty much any popular media (e.g. New York Times), any popular science media
(e.g. Scientific American, New Scientist), computer science popular media (e.g. Wired),
or popular blogs related to economics and game theory, (e.g.
Freakanomics,
Market Design,
Oddhead Blog,
Mind your decisions,
Nuclear Chicken Collusion,
and The leisure of the theory class).
Be sure to put a link in your post to the article/blog post you are discussing,
summarize the key points and offer your own perspective (why you thought it was interesting,
what questions it raises, points where you agree or disagree, etc.)
- Extra Credit: Peres book, page 115,
Problem 3.15
- Extra Credit: Show that if there is a polynomial time
algorithm for finding a Nash equilibrium in a 3 player zero-sum game
(the sum of the payoffs to the 3 players is always 0), then there is a polynomial
time algorithm for finding a Nash equilibrium in a 2 player general sum game.
- Extra credit: Provide feedback on Chapter 3 in these notes.
By feedback, what I mean is (a) find typos, (b) find places where the exposition is unclear, (c) propose improved explanations, (d) point out what parts you could not understand and specifically where you got stuck. The better the feedback, the more extra credit.