Game Theory (Part 1)

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 this blog 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.

Examples of games

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.

Classifying games

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.

Warning

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.

Puzzle

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?

21 Responses to Game Theory (Part 1)

  1. Arrow says:

    What are important successes or killer applications of game theory? Other then gambling.

    • John Baez says:

      Game theory is heavily used in microeconomics, both in industry and among regulators. I’ve just begun reading this book:

      • Lynne Pepall, Dan Richards and George Norman, Industrial Organization: Contemporary Theory and Empirical Applications, Blackwell, Oxford, 2008.

      A quote:

      We have already noted that there is much to be said for pursuing a game-theoretic understanding of the strategic interaction of firms. What is important to note at this point is that it was game theory that allowed us a way to model and analyze firm behavior in imperfectly competitive markets. Moreover, as game theoretic analysis spread through industrial organizations its insights have, to some extent, led to a diminution of the Chicago School‘s impact. However it would be wrong to identify the advent of game theory models and the new Post-Chicago approach as a total rejection of the Chicago School’s work. For example, the Merger Guidelines adopted jointly by the Federal Trade Commission and the Justice Department have deep roots in the Cournot–Nash game-theoretic model that we describe more fully in Chapter 15. While these guidelines are far from permissive, they still allow for many more mergers than would ever have legally occurred in the “New Sherman Act” years of the 1950s and 1960s.

      So, we need to understand game theory to understand what these people are doing, regardless of whether they’re doing the right things.

      Game theory has also been important in evolutionary biology ever since the work of John Maynard Smith starting around 1973, as nicely summarized here:

      • William H. Sandholm, Evolutionary game theory, 12 November 2007.

      I talked about this before on this blog. Sandholm wrote:

      The birth of evolutionary game theory is marked by the publication of a series of papers by mathematical biologist John Maynard Smith. Maynard Smith adapted the methods of traditional game theory, which were created to model the behavior of rational economic agents, to the context of biological natural selection. He proposed his notion of an evolutionarily stable strategy (ESS) as a way of explaining the existence of ritualized animal conflict.

      Maynard Smith’s equilibrium concept was provided with an explicit dynamic foundation through a diff erential equation model introduced by Taylor and Jonker. Schuster and Sigmund, following Dawkins, dubbed this model the replicator dynamic, and recognized the close links between this game-theoretic dynamic and dynamics studied much earlier in population ecology and population genetics. By the 1980s, evolutionary game theory was a well-developed and firmly established modeling framework in biology.

      Towards the end of this period, economists realized the value of the evolutionary approach to game theory in social science contexts, both as a method of providing foundations for the equilibrium concepts of traditional game theory, and as a tool for selecting among equilibria in games that admit more than one. Especially in its early stages, work by economists in evolutionary game theory hewed closely to the interpretation set out by biologists, with the notion of ESS and the replicator dynamic understood as modeling natural selection in populations of agents genetically programmed to behave in specific ways. But it soon became clear that models of essentially the same form could be used to study the behavior of populations of active decision makers. Indeed, the two approaches sometimes lead to identical models: the replicator dynamic itself can be understood not only as a model of natural selection, but also as one of imitation of successful opponents.

      While the majority of work in evolutionary game theory has been undertaken by biologists and economists, closely related models have been applied to questions in a variety of fields, including transportation science, computer science, and sociology. Some paradigms from evolutionary game theory are close relatives of certain models from physics, and so have attracted the attention of workers in this field. All told, evolutionary game theory provides a common ground for workers from a wide range of disciplines.

      But needless to say, since this is an undergraduate math course, I’ll be talking a lot more about calculating optimal strategies and proving (easy) theorems than any of this stuff.

  2. Mike Stay says:

    Do you have someone writing up class notes?

    • John Baez says:

      The class won’t start until Tuesday! There are 60 students. I’d gladly pay someone with points towards their grade for writing up the best possible notes, scanning them in and emailing them to me. But this raises a good game theory problem. What’s the best way to run this?

      If I pick one person early on and pay them with points towards their grade, other people will be resentful and this one person may slack off. If I repeatedly get lots of people to submit their notes it will be a confusing mess. I don’t mind if people cooperate… I just want to get the best possible notes and not make any students miserably unhappy in the process.

      This problem reminds me of a problem in auction theory, but it’s a bit different.

      • Mike Stay says:

        Are there avenues for publication of lecture notes? Being a coauthor with you might motivate them.

        • John Baez says:

          These lecture notes won’t be good enough to publish without a vast amount of work. And I don’t think that work is justified yet. For one thing, I don’t know enough about game theory yet. Maybe someday.

          I am, however, also going to give a course this quarter based on the notes Derek Wise took: Lectures on Classical Mechanics. In the process I hope to polish them a bit more. And we’ll eventually publish them as a book.

          Anyway, the challenge is not rewarding someone enough to get them to scan in all their notes. The challenge is finding the right person among 60 people and rewarding them without pissing off 59 other people.

        • Blake Stacey says:

          On p. 10 of the classical mechanics PDF, there’s a sentence fragment:

          Consider reflection of light from a mirror,

          The diagram to which this refers spills over onto the next page.

          On p. 15, the unnumbered formula in between equations (2.2) and (2.3) has a formatting error:

          ``\delta''

          instead of

          \hbox{``} \delta \hbox{''}

        • Colin says:

          You are right make it into a game, in a game theory course no one will be annoyed with you or the winner(s). Let the students bid on what they want in return for taking the (quality) notes . The winner is the one(s), based on some set of hints (criteria) you give them, that minimize your effort. Hey some can even co-operate. You may get a bid like “I’d do it for free if you let me join your Math & Enviro group”. I’m just saying. Either way its a good time for you to have this puzzle.

    • Blake Stacey says:

      Do you have a TA for the class? Or a PhD student (i.e., minion) who could take notes to augment yours?

      Is there something else which students could do to earn the same number of extra points? If, say, a student had more skill or interest in coding than in note-writing, they could implement a simulation which illustrates a topic covered in the course. The more ways there are to get those extra points, the more fair it would seem.

      The challenge with “crowdsourcing” like this is that it’s much easier to get small, disorganized contributions than big, carefully-planned ones. Look at how Wikipedia articles grow: a couple sentences here, a footnote there—piecewise aggregation. If you already had a manuscript in hand (as with the classical mechanics course), you could distribute it in chunks to those who attend each lecture. The students could then read and work through them as the class went along, finding all the mixed-up minus signs. (Back during my less bitter and jaded days, Barton Zwiebach did this while teaching the class which became A First Course in String Theory, and so did Mehran Kardar with Statistical Physics of Particles. The notes for the latter course had gone through more rounds of polishing by the time I saw them.) That could be very helpful the next time you teach game theory, but I don’t know what to do this time!

  3. John Baez says:

    We’re having some mildly interesting discussions about these lecture notes over here on Google+.

  4. Heather says:

    Hmmm – I like the idea of +’ing the best notes, however, 60 students’ notes are not going to be feasible that way. A word doc with all 60 entries would, however, make for a wonderful qualitative data analysis…

  5. With the extra discussions underneath the class notes along with the link provided yet another group of discussions, I am confsued if I am also responsible for the discussions come along with the notes.

    They are certainly interesting and fun to read, but on a regular notes basis(that is, two before-class-notes per week) these notes will bring up so many discussions that takes too much time to go through.

    If it is intended to be a interactive platform, I guess I have no objection to these interactions; however, if I am ought to be responsible for the discussions, i.e. sometime during class you might say “during some discussion online we come to a conclusion such as…” or things like this, I found these interaction rather heavy.

    The notes are great and interesting, I am looking forward to finish this course; the added interactions especially the quotes part made me feel like I ought to be reading those books as well, are rather overwhelming.

    • PS: Some of the commentaries seem personal as well (the ones on google+). I am very confused if I should go through the comments since I might be responsible for them, or these are just some personal blogs for you to keep track of classes rather than very professional information site?

    • John Baez says:

      The course notes are my blog entries; you don’t need to read any of the other stuff.

      You don’t even need to read the course notes if you take really really good notes in class! But I’m afraid many students will feel a bit lost without a textbook. So, I’ve decided to make my course notes available on my blog.

  6. Reeve says:

    Maybe require those notes typed in LaTeX? Granted, that might be a little unfair – but it is extra credit! That will certainly lessen the number of people who submit notes, though!

    I’ll leave the puzzle for someone else – it’s easy after a quick internet search.

    Also, have you heard of the board game Munchkin? I don’t know much game theory, but that might be interesting from a game theory perspective. At its core, it’s a parody of role-playing games (the cards poke fun at D&D a lot) where you win by screwing the other guys over just enough to give you an advantage but not enough so that they reserve all their resources for retaliation.

    • Munchkin as a board game? I know the card game. Played casually it is quite funny. However becoming a wizard, which is random, usually suffices to survive the retaliation. So it is basically a game of luck without much strategy. At least, that was my impression.

      • Reeve says:

        Yeah. The card game, though it can be a board game, depending on which version you get. In the case it’s a board game (I think it’s the Deluxe edition?), the board is really superfluous.

        I don’t know if I’d say it’s just a game of luck without much strategy. Having to discard to get those temporary bonuses from being a wizard is kind of a high cost. All the classes/races have a set of advantages and disadvantages that is pretty balanced, I think, and an adept player could probably play all the classes/races nearly equally well, depending on the cards available to them (luck). Personally, I think if anything’s overpowered, it’s the Halflings. ;)

  7. DTec says:

    You could award the top two note takers maybe 4 and 6 times more than the rest, but award something to all substantial submissions. Also to allow more competition, don’t allow the same winners two weeks in a row.

    • John Baez says:

      Okay, I’ll do something like this! I suspect that only one or two people will take the trouble to produce good notes in a consistent way. In that case your “no same winner two weeks in a row” rule would be a bit problematic. But something like this should work.

  8. antfilfon says:

    A game is of complete information if the players know who the other players are and also their best strategies and the payoffs. A game is of perfect information if all the players have perfect knowledge of the sequence of moves performed in the game.

You can use HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,708 other followers