|
|
|
|
I'm teaching an undergraduate course on game theory and I thought I'd try writing my course notes on this blog. I invite students (and everyone else in the universe) to ask questions, correct my mistakes, add useful extra information and references, and so on.
However, I should warn the geniuses who usually read my website that these notes will not be filled with deep insights: it's just a introductory course and it's the first time I've taught it.
I should also warn the students in my class that these notes are not a substitute for taking notes in class! I'll tell you a lot of other stuff in class!
Let's get started.
Mathematicians use words differently from normal people. When you hear the word 'game' you probably think about examples like:
• board games like checkers, chess, go, Scrabble, Monopoly, Risk and so on.
• card games like solitaire, poker, bridge, blackjack, and so on.
• sports involving athletic skill like football, basketball, baseball, hockey, tennis, squash, golf, croquet, horseshoes and so on.
• video games and computer games — I'm too much of an old fogey to even bother trying to list some currently popular ones.
• game shows on TV — ditto, though Jeopardy is still on the air.
• role-playing games — ditto, though some people still play Dungeons and Dragons.
• 'war games' used by armies to prepare for wars.
Game theory is relevant to all these games, but more generally to any situation where one or more players interact, each one trying to achieve their own goal. The players can be people but they don't need to be: they can also be animals or even other organisms! So, game theory is also used to study
• biology
• economics
• politics
• sociology
• psychology
For example, here is a 'game' I often play with my students. Some students want to get a passing grade while coming to class as little as possible. I want to make them come to every class. But, I want to spend as little time on this task as possible.
What should I do? I don't want to take attendance every day, because that takes a lot of time in a big class. I give quizzes on random days and make it hard for students to pass unless they take most of these quizzes. I only need to give a few quizzes, but the students need to come to every class, since they don't know when a quiz will happen.
How do the students respond? Lots of them come to class every time. But some try to 'bend the rules' of the game, mainly trying to get my sympathy. They invent clever excuses for why they missed the quizzes: dying grandmothers, etc. They try to persuade me to 'drop the lowest quiz score'. They try to convince me that it's unreasonable to make quizzes count for so much of the grade. After all, it's easy to get a bad score on a quiz, when there's not much time to answer a question about something you just learned recently.
How do I respond? Only the last idea moves me. So, I set things up so missing a quiz gives you a much worse score than taking the quiz and getting it completely wrong. In fact, just to dramatize this, I give students a negative score if they miss a quiz.
How the students respond? Some of them argue that it's somehow evil to give people negative scores. But at this point I bare my fangs, smile, and nod, and the game ends.
It's important to emphasize that other students have different goals: some want to come to class every time and learn as much as possible! In this case my goals and the students' goals don't conflict very much. As we'll see, in mathematical game theory there are plenty of games where the players cooperate as well as compete... or even just cooperate.
Mathematical game theory tends to focus on games where the most important aspect of the game is choosing among different strategies. Games where the most important aspect is physical ability are harder to analyze using mathematics. So are games where it's possible to 'bend the rules' in a huge number of different ways.
Game theory works best when we can:
• list the set of choices each player can make,
• clearly describe what happens when each player makes a given choice.
• clearly describe the 'payoff' or 'winnings' for each player, which will of course depend on the choices all the players make.
We can classify games in many different ways. For example:
• The number of players. There are single-player games (like solitaire), two-player games (like chess or 'rock, paper, scissors'), and multi-player games (like poker or Monopoly).
• Simultaneous versus sequential games. There are games where all players make their decisions simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players' actions, making them effectively simultaneous. These are called simultaneous games. There are also games where some players make decisions after knowing something about what other players have decided. These are called sequential games.
The games people play for fun are very often sequential, but a surprisingly large part of the game theory we'll discuss in class focuses on simultaneous games. 'Rock, paper, scissors' is an example of a simultaneous game, but we'll see many more.
• Zero-sum versus nonzero-sum games. A zero-sum game is one where the total payoff to all the players is zero. Thus, any player benefits only at the expense of others.
An example of a zero-sum game is poker, because each player wins exactly the total amount their opponents lose (ignoring the possibility of the house's cut). Chess, or any other two-player game with one winner and one loser, can also be seen as a zero-sum game: just say the winner wins $1 and the loser loses $1.
In nonzero-sum games, the total payoff to all players is not necessarily zero. An example is 'chicken', the game where two people drive their cars at each other, and both cars crash if neither pulls off the road. When this happens, both players lose. There are also games where both players can win.
In two-person zero-sum games, the players have no reason to cooperate, because whatever one wins, the other loses. In two-person nonzero-sum games, cooperation can be important.
• Symmetric and non-symmetric games. In a symmetric game the same rules apply to each player. More precisely, each player has the same set of strategies to choose from, and the payoffs to each player are symmetrical when we interchange which player chooses which strategy.
In a non-symmetric game, this is not the case. For example, we can imagine a non-symmetric version of poker where my hand always contains at least two aces, while no other player's does. This game is 'unfair', so people don't play it for fun. But games in everyday life, like the teacher-student game I mentioned, are often non-symmetric, and not always fun.
• Cooperative and non-cooperative games. A game is cooperative if the players are able to form binding commitments. That is, some players can promise to each that they will choose certain strategies, and these promises must be kept. In noncooperative games there is no way to make sure promises are kept.
Our legal system has the concept of a 'contract', which is a way people can make binding commitments.
There's a lot more to say about these ways of classifying games. There are also other ways of classifying games that we haven't discussed here. But you can already begin to classify games you know. Give it a try! You'll run into some interesting puzzles.
For example, chess is a two-person zero-sum sequential non-cooperative game.
Is it symmetric? The strategies available to the first player, white, are different from those available to the second player, black. This is true of almost any sequential game where the players take turns moving. So, we can say it's not symmetric.
Or, we can imagine that the first move of chess is flipping a coin to see which player goes first! Then the game becomes symmetric, because each player has an equal chance of becoming white or black.
I may put some puzzles on this blog, which are different than the homework for the course. You can answer them on the blog! If you're a student in the course and you give a good answer, I'll give you some extra credit.
Puzzle. What's a 'game of perfect information' and what's a 'game of complete information'? What's the difference?
You can also read comments on Azimuth, and make your own comments or ask questions there!
|
|
|
|