Popularized by movies such as “A Beautiful Mind,” game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call `games’ in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We’ll include a variety of examples including classic games and a few applications.
The prisoner’s dilemma is a standard example of a game analyzed in game theory that shows why two completely “rational” individuals might not cooperate, even if it appears that it is in their best interests to do so. It was originally framed by Merrill Flood and Melvin Dresher working at RAND in 1950.
Requirements/Prerequisites
You must be comfortable with mathematical thinking and rigorous arguments. Relatively little specific math is required; you should be familiar with basic probability theory (for example, you should know what a conditional probability is), and some very light calculus would be helpful.
Suggested Readings
The following background readings provide more detailed coverage of the course material:
- Essentials of Game Theory, by Kevin Leyton-Brown and Yoav Shoham; Morgan and Claypool Publishers, 2008. This book has the same structure as the course, and covers most of the same material. It is free if you access the link from a school that subscribes to the Morgan & Claypool Synthesis Lectures, and otherwise costs $9 to download, if you use the code: mooc2016. You can also get it as a printed book from (e.g.) Amazon.com, or as an ebook for Kindle or Google devices.
- A Brief Introduction to the Basics of Game Theory, by Matthew O. Jackson. These notes offer a quick introduction to the basics of game theory; they are available as a free PDF download.
Expected utility from decision theory suggests:
ui (s) = ∑ {a ∈ A} ui (a)Pr(a|s)
Pr(a|s) = ∏ {j ∈ N} sj (aj)
Strictly Dominated strategies suggest:
A strategy ai ∈ Ai is strictly dominated by a’i ∈ Ai if
ui(ai, a-i) < ui(a’i, a-i) ∀ a-i ∈ A-i
Weakly Dominated strategies suggest:
A strategy ai ∈ Ai is weakly dominated by a’i ∈ Ai if
ui(ai, a-i) < ui(a’i, a-i) for some a-i ∈ A-i
Maxmin strategy suggests that in a zero-sum game hurting the other guy is tantamount to improving your own your own payoff. And so in the setting of zero-sum games, maxmin and minmax strategies make a lot of sense, and in fact, in a very famous theory due to Jean von Neumann it proved that, in a zero-sum game, by definition you consider only two player, such games, any Nash Equilibrium, the player sees a payoff that’s is equal to both his maxmin value and his minmax value.
The maxmin strategy for player i is arg maxsi min s-i ui(s1, s2), and
the maxmin value for player i is maxsi min s-i ui(s1, s2)
