Wednesday, February 1, 2012

Introduction to Game Theory

Today, (most of) you were introduced to game theory, which is a theory that tries to explain the behavior of rational agents when they interact with one another. We saw the basic definition of a simple, finite game, and several examples of 2-player games in strategic/normal form. We saw that rational agents might be modeled as playing their best-response to other players' actions, and we defined the corresponding equilibrium concept - Nash equilibrium. We also defined dominant and dominated strategies, and saw that in certain situations, we could obtain the Nash equilibrium by iterated removal of dominated strategies. A recurring theme that we observed in the examples is that (selfish) rationality can hurt (the society)! We'll attempt to quantify and formalize this in later lectures.

We then looked at mixed strategies, where agents' strategies are now probability distributions over their action sets. For finite games, while pure-strategy Nash equilibrium might not always exist, mixed Nash equilibrium always exists. (Note that Nash's existence theorem is more general than this.)

Finally, we looked at extensive form games, which could capture additional aspects like timing/sequence as well as probabilistic payoffs. We saw how we could convert any extensive form game into an equivalent normal form payoff-matrix and study the Nash equilibria. We barely touched on backward induction and subgame-perfection (as equilibrium refinement concepts).

In the end, game theory is still a theory - and we briefly discussed a few ways in which the rationality assumptions made in the ideal world might differ from reality. There is a whole sub-field of experimental economics that deals with validating these assumptions in different real-world settings.

This lecture was just meant to be a primer. Later in the course, we'll explore more advanced concepts, as well as different kinds of games such as games with continuous players (routing games) and games with continuous action sets (ad auctions).

The concepts I tried to introduce are important, so if you have any questions or doubts, please feel free to post them as comments to this post (or email me personally) and I will clarify them. I encourage you to do this soon - this is foundation material for upcoming homeworks (HW5, HW6 and perhaps HW7 as well)!

Lecture slides will be up on the course website (here) in a couple of days.

1 comment: