Game Theory for Undergraduates

Starting in January I’m teaching an introduction to game theory to students who have taken a year of calculus, a quarter of multivariable calculus, but in general nothing else. The syllabus says this course:

Covers two-person zero-sum games, minimax theorem, and relation to linear programming. Includes nonzero-sum games, Nash equilibrium theorem, bargaining, the core, and the Shapley value. Addresses economic market games.

However, I can do what I want, and I’d like to include some evolutionary game theory. Right now I’m rounding up resources to help me teach this course.

Here are three books that are not really suitable as texts for a course of this sort, but useful nonetheless:

• Andrew M. Colman, Game Theory and its Applications in the Social and Biological Sciences, Routledge, London, 1995.

This describes 2-person and multi-person zero-sum and nonzero-sum games, concepts like ‘Nash equilibrium’, ‘core’ and ‘Shapley value’, their applications, and—especially refreshing—empirical evidence comparing the theory of ideal rational players to what actual organisms (including people) do in the real world.

• J. D. Williams, The Compleat Strategyst, McGraw–Hill, New York, 1966.

This old-fashioned book is chatty and personable. It features tons of zero-sum games described by 2×2, 3×3 and 4×4 matrices, analyzed in loving detail. It’s very limited in scope, but a good supply of examples.

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

This is a book about industrial organizations, antitrust law, monopolies and oligopolies. But it uses a hefty portion of game theory, especially in the chapters on ‘Static games and Cournot competition’, ‘Price competition’, and ‘Dynamic games and first and second movers’. So, I think I can squeeze some nice examples and ideas out of this book to use in my course.

Over on Google+

I also got a lot of help from a discussion on Google+. (If ever it seems a bit too quiet here, visit me over there!)

I want the students to play games in class, and Lee Worden had some great advice on how to do that effectively:

For actually playing in class, I like the black-card, red-card system:

• Charles A. Holt and Monica Capra, Classroom games: a prisoner’s dilemma.

Students can keep their cards at their seats and use them for a whole series of 2-person or n-person games.

I like the double entendre in the title of Holt and Capra’s paper! I also like their suggestion of letting students play for small amounts of money: this would grab their attention and also make it easier to explain what their objective should be.

I’m also considering letting them play for points that improve their grade. But this might be controversial! Maybe if it only has a small effect on their grade?

(Students often ask, when they do badly in a course, what they can do to improve their grade. Usually I just say “learn the material and get good at solving problems!” But now I could say “let’s play a game. If you win, I’ll add 5 points to your class score. If you lose….”)

Vincent Knight gave a nice long reply:

I teach game theory in our MSc program and can suggest two “games” that can be played in class:

• Your comic suggests it already, the 2/3rds of the average game. I use that in class and play it twice, once before rationalising it and once after. In the meantime I get TAs to put the results in to a google spreadsheet and show the distribution of guesses to the students. The immediate question is: “what would happen if we played again and again”. This brings up ideas of convergence to equilibria.

• The second game I play with students is an Iterated Prisoner’s dilemma. I separate the whole class (40 students) in to 4 teams and play a round robin tournament of 5 rounds. Specifying that the goal is to minimise total “years in prison” (and not the number of duels won). This often throws up a coalition or two at the end which is quite cool.

I don’t only use the above on our MSc students but also at outreach events and I’ve written a series of blog posts about it:

• School kids: http://goo.gl/5u6Ic

• PhD students: http://goo.gl/6rkOt

• Conference delegates: http://goo.gl/JGWM7

• MSc students: http://goo.gl/oHoz0

The slides I use for the outreach event are available here: http://goo.gl/vJVWV. They include some cool videos (that have certainly made the rounds). I use some of that in the class itself.

I’m also in the middle of a teaching certification process called pcutl and my first module portfolio is available here: http://goo.gl/NhJYg. There’s a lot more stuff then you might care about in there but towards the end is a lesson plan as well as a reflection about how the session went with the students. There are some pics of the session (with the students up and playing the game) here: http://goo.gl/wBZwC.

The notes that I use are in the above portfolio but here is my page on game theory which contains the notes I use on the MSc course (which only has the time to go in to normal form games) and also some videos and Sage Mathematical Software System code: http://goo.gl/RXr1k.

Here are 3 videos I put together that I get my students to watch:

• Normal form games and mixed equilibria: http://goo.gl/dBtDK

• Routing games (Pigou’s example): http://goo.gl/807G4

• Cooperative games (Shapley Value): http://goo.gl/Pzf1F

Finally (I really do apologise for the length of this comment), here are some books I recommend:

• Webb’s Game Theory (in my opinion written for mathematicians): http://goo.gl/2M83l

• Osborne’s Introduction to Game Theory (a very nice and easy to read text): http://goo.gl/FXbcd

• Rosenthal’s A Complete Idiot’s Guide to Game Theory (this is more of a bedside read, that could serve as an introduction to game theory for a non mathematician): http://goo.gl/PCs76

I’m actually going to be writing a new game theory course for final year undergraduates next year and will be sharing any resources I put together for that if it’s of interest to anybody :)

And here are some other suggestions I got:

• Peter Morris, Introduction to Game Theory, Springer, Berlin, 1994.

Over on Google+, Joerg Fliege said this “is an excellent book for undergraduate students to start with. I used it myself a couple of years ago for a course in game theory. It is a bit outdated, though, and does not cover repeat games to any depth.”

• K. G. Binmore, Playing for Real: a Text on Game Theory, Oxford U. Press, Oxford, 2007.

Benjamin McKay said: “It has almost no prerequisites, but gets into some serious stuff. I taught game theory once from my own lecture notes, but then I found Binmore’s book and I wish I had used it instead.” A summary says:

This new book is a replacement for Binmore’s previous game theory textbook, Fun and Games. It is a lighthearted introduction to game theory suitable for advanced undergraduate students or beginning graduate students. It aims to answer three questions: What is game theory? How is game theory applied? Why is game theory right? It is the only book that tackles all three questions seriously without getting heavily mathematical.

• Herbert Gintis, Game Theory Evolving: a Problem-Centered Introduction to Modeling Strategic Behavior, Princeton U. Press, Princeton, 2000.

A summary says this book

exposes students to the techniques and applications of game theory through a problems involving human (and even animal) behaviour. This book shows students how to apply game theory to model how people behave in ways that reflect the nature of human sociality and individuality.

Finally, this one is mostly too advanced for my course, but it’s 750 pages and it’s free.

• Noam Nisan, Tim Roughgarde, Eva Tardos and Vijay V. Vazirani, editors, Algorithmic Game Theory, Cambridge U. Press, Cambridge, 2007.

It’s about:

• algorithms for computing equilibria in games and markets,

auction algorithms,

mechanism design (also known
as ‘reverse game theory’, this is the art of designing a game that coaxes the players into becoming good at doing something you want),

the price of anarchy: how the efficiency of a system degrades due to selfish behavior of its agents.

Over on Google+, Adam Smith said:

One suggestion is to get some mechanism design into the course (auctions, VCG, …) and from there into matching. Reasons to do this:

1) Teaching the stable marriage theorem is very fun.

2) This year’s Nobel prize in economics went to two game theorists for their work on matchings and markets.

3) Interesting auctions are everywhere—on Ebay, Google’s ad auctioning system, spectrum distribution, …

14 Responses to Game Theory for Undergraduates

  1. Rod Carvalho says:

    Here’s yet another book:

    • Nolan McCarty and Adam Meirowitz, Political Game Theory [pdf].

  2. In evolutionary game theory I’d first acquaint the students with the simplest equilibrium where it all came from: the perfect market one. After that the first comprehensive—yet very easy—work plotting out the connection to evolution, would be Nelson & Winter’s An Evolutionary Theory of Economic Change.

    From that downwards, still using economic parallels like oligopoly, it oughtn’t to be too hard to get downto the idea of “the core”. Then to Cournot and Stackelberg competition/games, and then finally a pure Nash equilibrium.

    This is the way I learnt about non-coöperative game theory. Top down from the libertarian, economical, ethical viewpoint, whereas nowadays most people learn it the harder way, from the bottom up, with very little motivation of why it even matters. I hope you can play this idea, and that two part Binmore monologue I pointed out, against the curriculum you were already planning.

    • John Baez says:

      My plans are very rough and flexible. Since it looks like I should teach a general introductory course rather than a course focused on evolutionary game theory, I do want people to see why game theory matters for politics and economics as well as biological evolution. To leave this out would be to undersell the importance of the subject! I’m not a libertarian, but you don’t need to have any particular political views to think game theory is important.

      I think for the way I teaching undergrads it’ll be better to start with simple special classes of games and work upwards, rather than starting from general ones and working down.

      I discovered a devilishly fun game that I’d like to get the students to play. It’s called Dollar Auction and it works like this. I’m auctioning off a dollar bill. Two or more players take turns making bids on a dollar bill, I accept the bid whenever I want, and give that player the dollar… but all the players have to give me their highest bid! The consequences are rather fiendish… though a player can always bid zero dollars if they don’t want to be coerced into joining the action.

  3. Have a look on my online material, including projects, small online games, and Excel sheets. This material will be removed in a few months, since I am in the final stages of a textbook project, but until then I still like to share it.
    http://www.eprisner.de/MAT109/MAT109.html

    • John Baez says:

      That stuff looks great! I hope you don’t take it down: unless I’m miscalculating, the prestige value of having it publicly available is likely to exceed the monetary value of selling all the rights to a publisher. Ever since I realized this, I make sure all my stuff is freely available online. Publishers will usually still publish things under these terms.

      Anyway, I’ll try to get my students to use it.

  4. John Roe says:

    I like the book Microeconomics: Behavior, Institutions and Evolution by Samuel Bowles. Contains a lot of game theory in an economic context.

  5. Sam Alexander says:

    When I took game theory as a senior at U of A, I was extremely disappointed at the lack of infinite games (so disappointed I eventually dropped the class). Of course, that was a class for seniors and it sounds like yours is more for freshmen and sophomores. Still, if there’s anyone like me in your class, know that what they want is infinite games.

    • John Baezj says:

      I’ll keep that in mind! I think most of the students want a course to fill out their electives for the math major. But they will wind up learning a lot and also having fun—there will be games in class. Not infinite ones, I’m afraid.

      The real problem (for people like you) is that, as far as I know, U.C. Riverside doesn’t offer a course on mathematical logic and set theory that goes beyond the basics. Our one logician hopped over to computer science when that department was created. Smart move. But we’re weak when it comes to the infinite.

      You might like my posts about bigness over on Google+. Eventually I’ll move them over here, and they’ll be easier to read in sequence.

      • Sam Alexander says:

        Thanks for the pointer. I’d heard you were writing about ordinals from a colleague, but since I’ve only been following the blog, I never saw that myself.

  6. murphmath says:

    Here’s a slightly evil in-class game: grade the course on a curve and have the students grade each other’s work. (It might be nicer to conduct this as a thought experiment about some bizarro game theory course.)

    • John Baez says:

      I’ve been imagining various slightly evil but educational in-class games. I also have another evil idea.

      Anyone who teaches large classes will know that some students doing badly in the course will ask, desperately, near the end of the course, if there’s “any way they can improve their grade”. Usually I say a polite version of “Yeah—learn the fucking stuff!”

      Of course they meant to ask if there’s any other way to improve their grade. But in this class I could offer them the chance to play some sort of game. If they win, I will increase their grade by one letter. If they lose, I’ll decrease it by that much.

      If I did this right, winning the game would actually demonstrate mastery of game theory, so this would be justified. Or, in a more evil variation, expertise in game theory would let the student realize that they shouldn’t play the game, because they were likely to lose!

    • The only problem is that grading on a curve is obviously a cooperative game, where the students’ optimal strategy is not what you as teachers would want them to do. I usually discuss both grading on a curve and the “cheating game” (in tests) as examples in my Game Theory classes.

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,794 other followers