Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

[Link] A gentle video introduction to game theory

32 Post author: Konkvistador 13 December 2011 08:52AM

In this article I invite LessWrong users to learn the very basic math of something that is useful to both our community's goal of making better thinkers as well as many of the unrelated discussions that we often have here. I also present resources for further study to those interested. I made it based on the karma feedback given to this post in the monthly open thread.

Recently there has been a series of contributions made in main that serve more as introductory  and logistic material than novel contributions. Because of this and because I hope It will grab more attention from newer members, I posted this in main rather than discussion section.

 

What is "game theory"?

Wikipedia's take: Game of chess, what did you expect something original?

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success  is based upon  the choices of others. More formally, it is "the study of mathematical models  of conflict and cooperation between intelligent rational decision-makers." An alternative term suggested "as a more descriptive name for  the discipline" is interactive decision theory.

LessWrongWiki's more succinct alternative

Game theory attempts to mathematically capture behaviour in strategic situations, in which an individual's success in making choices depends on the choices of others.

From both definitions it should be clear how this relates to the art of refining human rationality. Besides the general admonition that rationalist should win, for us humans being the social animals that we are, there few things in our lives that do not depend at least partially on the choices of others. Game theory is extensively used in and connected to fields as disparate as economics, psychology, political science, logic, sports and evolutionary biology.

As many have argued before, it is an important part of the map of the real world:

Again and again, I’ve undergone the humbling experience of first lamenting how badly something sucks, then only much later having the crucial insight that its not sucking wouldn’t have been a Nash equilibrium.

--Scott Aaronson

You may not know it yet, but it is impossible to read this site for a extended period of time without running into concepts that are intimately tied to this field of study. Nash equilibrium, Pareto optimal, Prisoners Dilemma, non-zero sum, zero sum, the Decision theory talk that breaks out every now and then,... 

You can take the concepts one at a time, reading up on a few lines from a dictionary like definition and trying to assimilate them without doing any of the connected mathematics. I wouldn't want to discourage you from that, its better than guessing! But this approach has its limitations, one risks misunderstanding something or even more subtly just failing to appreciate nuance and running into practical difficulties when trying to apply this knowledge in the real world. At the very least guessing the teachers password is a problem. Those of you that looked up these phrases and concepts on-line probably realized that they fit into a wider framework, a framework I hope you can now begin to explore with simple math, even if only with just a few tentative steps.

 

So what are the videos I should watch?

This fall (2011) there has been an ongoing class offered by two Stanford professors, Sebastian Thrun and Peter Norvig called "Introduction to Artificial intelligence". It has been talked about extensively on LW in several threads here, here and here. Many LWers have showed interest, quite a few signed up and several of us are now preparing for its final exam. Among the material covered is a introduction to game theory. I've been on live lectures about the subject and even watched some recorded ones and in comparison this is one of the better short introductions I've seen so far. I especially like how each of the videos is a self-contained unit just a few minutes in length. Instead of having to commit to watching a 40 or 60 minutes lecture, you just need to commit 2-5 minutes at a time.

The relevant Units of the material that cover this are 13. Games and 14. Game Theory. These units are presented by Peter Norvig. They are not recordings of a professor presenting something to a class in front of a blackboard, but rather aim towards the feeling of having a private tutor sitting down with you and explaining a few things with the help of a pen and a few pieces of paper (reminiscent of the style seen on Khan Academy). Currently you can still go directly to the site and view these videos logged in as a visitor (recommended). But just to avoid a trivial inconvenience and in case the youtube videos outlast the current state of the website I'm going to link directly to the youtube videos and write down any relevant comments and missing information as well. Unit 13 especially, assumes some previous knowledge you probably don't have, it deals primarily with complexity of games and how computationally demanding it is to find solutions. It can be useful for getting to know some terminology, but is otherwise skippable.

 

Don't worry. If you look up or feel you know what an agent or player is and what utility is, the missing exotic stuff (ala POMDPs) that isn't explained as you go along doesn't matter much for our purposes.

13. Games (optional)

14. Game Theory

  1. Introduction
  2. Dominant Strategy Question ? (Solution) [This is where you learn about the famous Prisoners dilemma!] 
  3. Pareto Optimal Question ? (Solution) [rot13 after solving: Gur dhvm vapbeerpgyl vqragvsvrf bayl gur obggbz evtug bhgpbzr nf Cnergb bcgvzny, ohg obgu gur hccre evtug naq obggbz yrsg ner nyfb Cnergb bcgvzny. Va gur hccre evtug ab bgure bhgpbzr vf zber cersreerq ol O. Yvxrjvfr sbe gur ybjre yrsg ab bgure bhgpbzr vf zber cersreerq ol N.]
  4. Equilibrium Question ? (Solution)
  5. Game Console Question 1 ? (Solution)
  6. Game Console Question 2 ? (Solution)
  7. 2 Finger Morra
  8. Tree Question ? (Solution)
  9. Mixed Strategy
  10. Solving the Game
  11. Mixed Strategy Issues
  12. 2x2 Game Question 1 ? (Solution) [Please enter probabilities and not percentages.]
  13. 2x2 Game Question 2 ? (Solution)
  14. Geometric Interpretation
  15. Poker
  16. Game Theory Strategies
  17. Fed vs Politicians Question ? (Solution
  18. Mechanism Design
  19. Auction Question ? (Solution)

At any point feel free to ask questions here in the comment section, I'm sure someone will gladly help you. Also the AI class reddit may be a good resource. Once you are done with the short series of lectures test your knowledge with these assignments.

Note: I present this material in the form of a link to the video, followed by a "?" question mark if there is an answerable question that has a solution video posted. The link to the solution are posted as "(Solution)". Any additional comments made as corrections to the videos or some information that may be otherwise missing in this format, will be added in square brackets "[...]". I encourage people who are solving this via the links rather than the site to not watch the solutions straight away but first work out what they think the answer should be, don't worry if you get it wrong, sometimes the questions are unlikely to be answered correctly with the knowledge you have at that point, their role is to make you better remember and engage the material, not gauge your performance. The exception to this are the videos that come after Unit 14.

 

"I don't get it."   or   "It's not working."  or  "I didn't bother to watch more than a few."

First off for those who didn't for whatever reason like the lectures given here or find them dull or over your head,  don't despair!  If you feel you don't understand something, ask questions, I can guarantee that either me or someone else will answer it. To those of you who feel they are understanding the material but just don't like the videos or the lecturer, don't worry there are several other ways to approach the field. To just point you on your way here is a wide variety of quality alternatives, some of which may have approaches you prefer:

I will keep this list updated and add any quality recommendations proposed by fellow LWers.

Unfortunately for those wanting just the introduction and most basic approach, many of these are more in depth and longer (this is also fortunate for those wanting a bit more). So if you just watch, comprehend and learn to use the information presented in the first lecture or two in one of these recommendations, you have done as much or more as someone who completed Unit 13 and 14. If you don't like video format in general and learn better from written material or live interaction... well this is mostly the wrong article for you. But I do present some additional non-video material in the next section you may find useful. 

 

I watched the lectures and I think I understood them, where do I go from here?

Cool! Well check out some of the alternative videos and classes listed above, most of them are quite extensive. Try to complete one! If you'd like and try to take one ask around the comment section, maybe enough people would be interested to start a study group. Also MIT open course-ware has  some material  you may be interested even if you don't feel like doing the full classes.

A good AI textbook might be something you would like to explore. LessWrong has a great article with  recommendations  for a variety of textbooks for several interesting subjects (all recommendations must be made by people who've read at least two other titles on the subject)... but none for game theory. :/

In the thread Bgesop  requested a recommendation:

I would like to request a book on Game Theory. I went to my school's library and grabbed every book I could find, and so I have Introduction to Game Theory by Peter Morris, Game Theory 2nd Edition by Guillermo Owen, Game Theory and Strategy by Philip Straffin, Game Theory and Politics by Steven Brams, Handbook of Game Theory with Economic Applications edited by Aumann and Hart, Game Theory and Economic Modeling by David Kreps, and Gaming the Vote by William Poundstone because I also like voting theory.

My brief glances make Game Theory and Strategy look like a fun, low level read that I'll probably start with to whet my appetite for the subject. Introduction to Game Theory looks like a good, well written intro textbook, but it was written in 1940 and was only updated once in 1994, and I would hope something new would have happened in that time. Game Theory 2nd Edition looks like a good, moderately modern (1982) and incredibly boring book. The others look worse.

I'll read at least portions of all of them and at least two or three completely unless somebody suggests anything. If no one does before I read them I'll post an update.

Unfortunately it was the plea went unanswered. I'd love to just recommend you the textbook I first learned the subject from, but most readers are probably English speakers, so that's a no go. I'm not familiar with that many of them. I did skim Game Theory 2nd edition by Guillermo Owen, and it seemed ok. Hopefully me pointing this out will prompt someone to come up with a good recommendation. When they do I'll update this post accordingly, and lukeprog's great list can get another good textbook.

 

 

Comments (9)

Comment author: James_Miller 13 December 2011 02:46:17PM *  6 points [-]

Please forgive the self-promotion but I've written a game theory book for a general audience

Game Theory at Work

which Yvain has cited.

It's been translated into Chinese, Japanese and Korean.

Comment author: Xece 14 December 2011 04:27:29AM 2 points [-]

The link to the Chess Question solution is the same as that of the Space Complexity Question Solution video.

Comment author: Konkvistador 14 December 2011 07:20:03AM *  1 point [-]

Thank you! Fixed.

Sorry to everyone for the errors so far, I was doing the links by hand, and it was multitasking at the time since it was such a boring thing to do.

Comment author: imajunryou 13 December 2011 07:17:12PM 2 points [-]

As I have been watching the videos, I noticed that chapter 13, video 6 on your list there links to video 7 of the AI class' website. Your video 7 link is to the youtube version of the same.

Thanks for writing this up, it is nice to have these sort of things broken down into bite-sized pieces that I can enjoy in between lulls in my day without a lot of backtracking to figure out where I left off.

Comment author: Konkvistador 13 December 2011 07:38:36PM *  1 point [-]

As I have been watching the videos, I noticed that chapter 13, video 6 on your list there links to video 7 of the AI class' website. Your video 7 link is to the youtube version of the same.

Fixed the link. Thanks for pointing out the error.

Thanks for writing this up, it is nice to have these sort of things broken down into bite-sized pieces that I can enjoy in between lulls in my day without a lot of backtracking to figure out where I left off.

Glad to hear this!

Comment author: Ben_Welchner 14 December 2011 02:37:13AM 1 point [-]

On a similar note, what should be 13.9's solution links to 13.8's solution.

I'm also finding this really interesting and approachable. Thanks very much.

Comment author: Konkvistador 14 December 2011 07:19:42AM 1 point [-]

Fixed, thank you.

Comment author: novalis 13 December 2011 04:59:21PM 2 points [-]

Broken link on Scott Aaronson.

Comment author: Konkvistador 13 December 2011 05:12:56PM 1 point [-]

Thank you, fixed.