Game theory shows GROUPS follows most successful member

Brian of Scrapyard Armory tipped me to this short article on game theory, which is quite interesting, but the author summarizing the article for Ars Technica really botched one thing. Here is the first paragraph with my insertions/corrections in red.

Game theory shows cultural evolution
follows most successful member

Game theory has become a useful way to evaluate strategies for survival in cultural evolution scenarios. In a new study, scientists set up a model where human players engage with each other and compete for resources, and can change their strategies for doing so in various ways. They found that as more rounds of the game were played, the human players developed a tendency to imitate the best player, causing the players as a group to tend to play the game the same way. This implies that in cultural evolution, as one member of a species group enjoys more and more success, its methods become hard to ignore for the others, which will eventually follow its lead.

The error was confusing biological evolution with cultural evolution. So if Brian and I are playing a game, and Brian consistently wins, I am likely to start playing the game the same way Brian does. That's how groups change their social behavior, and it is a form of cultural evolution. For it to be biological evolution, *I* would have to change my biology to be more like Brian, or at least so that my offspring are more like Brian (and if that happens, I'm going to be VERY suspicious about what Brian has been up to with my wife! ;-) ). People do not change their biology when they adapt new behaviors, but groups can change their culture to adopt new ways of doing things. (See Lamarkian Evolution)

Other than that, I'm OK with the article, and I've even looked up the original publication. Maybe I'll have more to say after I give that a read.

Carrots and Sticks

Games are increasingly being used to investigate social behavior. Here is an excellent example of an experiment in the form of a game that shows how rewards are better at persuading people than punishment.

Carrots trump sticks
for fostering cooperation

When it comes to encouraging people to work together for the greater good, carrots work better than sticks. That's the message from a new study showing that rewarding people for good behaviour is better at promoting cooperation than punishing them for offenses.

See the full article at Not Exactly Rocket Science.  

Game Theory Week: The Homicidal Chaffeur

To most gamers, and probably even most mathematicians, the games in Game Theory don't actually have much to do with the games we like to play for fun. The Curmudgeon Gamer put it very aptly:

In case you aren't aware, "Game Theory" is a bait-and-switch ruse right up there with "Greenland". Somehow they managed to take the field of strategic game-playing and restrict it only to games no one would ever want to play. (Apparently there was some analysis of actual games in there at the beginning, but that was swiftly excised, lest anyone actually enjoy themselves.) [emphasis added]

A fair criticism too, because I looked long and hard in the literature without finding any real mention of the mathematical exploration of games. It turns out I wasn't looking in the right place, but one day a very crafty lady (my wife, naturally) made a good find, and got me a nice birthday present: old book by some guy named Rufus.

Rufus Isaacs gave mathematical formulation to real problems such as games of Pursuit and Evasion. In doing so, he opened up a new field of mathematics. His book Differential Games is a classic (available at Amazon.com for under $13!). It probably helps to have a good math background to follow along, because it makes use a lot of use of trigonometry, calculus, and differential equations, but it's written as a discussion and introduction to the problems rather than as a textbook. You can read the first chapter and most of the second on Google Books.

Isaacs did a lot of classified work at the RAND Corporation, are many of the problems he discusses are versions of pursuit and evasion that are actual real military considerations, such as intercepting a bomber before it can reach a target area. These are not simple problems, but it's not too hard to see this sort of problem is not too different from that of playing a game that represent a real military problem.
[Image Google Books]

One of the most basic problems in differential game is that of a vehicle trying to intercept a moving target, and Isaacs called this problem (with some humor intended) the "Homicidal Chaffeur". You can find a nice description and short discussion of The Homicidal Chauffeur at Reasonable Deviations.

Differential Games go a long way toward taking game theory in the direction of games we know and love to play. It's NOT a simple topic, but we already knew that games are far from simple. It's not surprising - and perhaps even gratifying - to learn the games we play are so fantastically complex. I've actually worked through a few simple examples of discrete differential games that occur in boardgames (well, Battletech anyway). Those examples will probably find their way to becoming blogs posts eventually, but I have some other ground to cover before I tackle differential games for myself.
[Image Google Books]

Game Theory Week: GAMES!

I am time challenged today, so I offer a list of suggested browsing on game theory.

From Game Theory.net:

• Strategy Board Games
• Online Strategy Games

A Chronology of Game Theory

Combinatorial Game Theory (LOTS of links!)

Steve LaValle's Home page, Rapidly-exploring Random Trees, and the RTT Gallery. Not exactly game theory, but the applications are just so cool. (Hint: Start with the gallery!)

More online? games from Dave Rusin.

Game Theory Week: Pop Culture

Oops. Now I find this post never got published. I'd like to say I'm not always such a space cadet, but it might not be true. Anyway, here it is, one week late:

Game Theory Week: Game Theory in Pop Culture

The Man with No Name says ...

You see in this world there's two kinds of people my friend; those with loaded guns, and those who dig. You dig.

[The build up is slow, so if you are in a hurry skip forward to 4:45]

GameTheory.net has a collection of game theory in film, or at least scenes in films that can be described in terms of game theory. The scene above with Uncle Clint is explained here. There are a number of good reviews here, including Princess Bride which is one of my all time favorites.

Game Theory Week: All Mixed Up

Today you get my home-cooked ramblings on game theory, and I'll be straying a bit from game theory as such to an application that interests me. If you really want to learn more about mixed strategies try the links.

Mixed strategies in game theory fascinate me. The basic premise of a mixed strategy is that sometimes there is no Nash equilibrium, no single choice of strategies between two players that is always the best either can do, without cooperation or coordination of the other player. In these cases there is still an equilibrium, but it exists as a random mix between two (maybe more) choices for each player.

Bluffing in poker is a good example of a mixed strategy. Bluff too often and other players will be more likely to call your bluff. Do not bluff enough, and other players will recognize when you are playing a strong hand (It's more complicated than that, because poker involves a lot of signaling too). Play poker with the right mix of bluffing and straight, and do these randomly without tipping other players to your choice, and you will be playing at a Nash equilibrium.

I have a proposition, an agenda for this blog that I am working towards, and I have most of the pieces in place to start discussing it seriously: I think mixed strategies can help describe how people actually play games, and how well they play them.

Typical game theory examples are usually very simple, there are generally 2 or 3 strategies and one of them might be the best (optimal). Games we like to play are not so simple. Consider that a player of boardgame (or card game, or a sport) might have multiple strategies, multiple moves for each piece on the board, and the total number of choice might be very large. Finding the best move might not be a trivial problem (a topic for another day).

Here is the obvious part: more skillful players will be better at picking out good move or strategies. A perfect player would always make the best available choice, but less skillful players will tend to make less-than-optimal choices, possibly because they have imperfect knowledge of how the game works. Information clearly plays an important role, so let's consider an unskilled player, someone new to a game that knows nothing at all and essentially chooses strategies at random. This might also be a computer program that literally plays randomly (Note: Some early versions of computer games such as chess played essentially random games like this.).

Now the less obvious: I'm departing from the concept of an optimal mixed strategy, to random play that is very far from optimal. In my own notes I've been referring to this as "random strategy", thought perhaps "blind strategy" is more apt, since the player uses no information about the game. This sort of random strategy might be a yardstick to gauge the ability non-random players; a baseline for comparison. Note that it is possible to play worse-than-random, but to do some requires information about the game and consistent bad choices, and most human players can probably do better than this even on their first try at a new game. [Image by Holger Meinhardt]

Information leads to opportunity for good choice, and good choices lead to good play. Player skill might be interpreted as the ability to take advantage of the available information and choose better strategies. So here is the conclusion of this ramble: Information is a statistically measurable quantity, so it should be possible to consider how much information is available to a player and how well they are able to make use of it (how much better than random). What I'm working towards here is (I think) a statistical measure called a likelihood ratio. A trivial example might be a game with two choices, one winning and the other losing, and the player must use some information to guess the winning choice. The random (blind) player will win 50% of the time, but the informed (yet imperfect) player should win more often than that, let’s say 75% of the time. The likelihood ratio would then be 0.75/0.50 = 1.5.

Game Theory Week: Getting Schooled

If you want some real education in game theory, then Open Yale Courses has just the thing for you: Game Theory with Professor Ben Polak.


This complete class in available online. Lectures are available in video and MP3 format, blackboard notes in PDF, and text transcripts too (see links in left hand sidebar). This is game theory for the math-phobic, though it does assume you have a passing familiarity with calculus for some of the problems. The lectures generally focus on talking about the theory, and not the math. I'm working my way through these at these and learning a lot. Polak is an excellent teacher and very enthusiastic about what he does.

I intentionally haven't posted direct links to this material here, because the material is too deep for casual browsing. I've been (slowly) working my way through these at the rate of a few per week. The lectures run about 90 minutes, and I find it's nice to have the blackboard notes and transcript handy to help understand the tricky bits. I'm really looking forward to some of the more advanced topics.

Game Theory Week: Barry Nalebuff

Barry Nalebuff (1 2) is a Professor ... excuse me ... the Milton Steinbach Professor at Yale School of Management. He is an expert in business strategy and game theory, author of a numbers of books, and is rumored to run a 9.86 second 100-meter dash (that last one is a rumor I am starting). He also has some video comments on BigThink. In this first one he talks a bit about the history of game theory:



Next up, Dr. Nalebuff tell us how game theory can be applied to relationships:



Barry Nalebuff on Game Theory and Poker --- (This one is for Brandon):



More video ideas from Barry Nalebuff can be found on BigThink.

Game Theory Week: That's Cheating!

Michael Shermer, champion skeptic and former competitive bicycle racer, has an article in the January issue of Scientific American:

The Doping Dilemma -
Game theory helps to explain the pervasive abuse of drugs in cycling, baseball and other sports

A recent comment by Jason about "cheat Scrabble" reminded me of this SciAm article that gives a nice explanation of why people cheat in terms of game theory, and sparked my idea for this series of posts (Thanks Jason!). Here are a few notes I grabbed from the key concepts:

• Game theory highlights why it is rational for professional cyclists to dope: the drugs are extremely effective as well as difficult or impossible to detect; the payoffs for success are high; and as more riders use them, a “clean” rider may become so noncompetitive that he or she risks being cut from the team.

Roughly speaking, when the payoff for winning far exceeds the penalty for cheating, "clean" athletes are pushed into cheating in order to keep up with those who cheat. While it is quite a different situation among the tabletop gamers, there are rumors of players banned from convention events, so it is not unheard of. It is far more common that people might have selective memories about what rules get applied and which dice rolls get modifiers, so gaining a small advantage at a critical moment. In games with quite complicated rule sets like I generally play, this sort of mistake might happen to anyone, and is not generally classified as cheating, but making too many mistakes makes gaming buddies suspicious, and so there is a social penalty for incorrect play.

• The game theory analysis of cycling can readily be extended to other sports. The results show quantitatively how governing bodies and antidoping agencies can most effectively target efforts to clean up their sports.

Game theory can show how the problem of cheating might be solved, by changing the payoffs so that honest play gains the athlete (or player) the greater benefit. Social groups are actually pretty good at enforcing "good behavior", but professional cycling (and maybe some other sports) have some problems to fix.

Game Theory Week: Intro

So far in these posts ramblings about the mathematics of games my approach has been to consider simpler versions of the game. There is a reason for this; I have been avoiding the difficult problem of player choice. In every post so far choice is either reduced to a near trivial (Scrabble --> Nim), removed entirely from consideration (Monopoly --> random walk), or not present in the first place (Candyland --> Markov chain). By simplifying choice out of these games, my task my task becomes much easier, but I'm also missing out on the best part of most games, which is the interaction between players seeking the winning strategy.

The time has come for that to change. To get at this problem I need a new tool, and that tool is Game Theory. The only problem is, I don't actually know that much about it ("Dammit Jim, I'm a Statistician, not an Economist!"). I do know some things; I have been reading and working to educate myself on this topic, but it is not my expertise and I feel a bit under-confident writing about it. Fortunately for me I don't have to be an expert. As a blogger I can point out some interesting uses of game theory and share the good sources that I am learning from.

Over the next week or so I will have a series of posts on game theory and related topics. My task will be to try to link game theory back to actual game people play. I will be leaning heavily on the work of others, but I hope to contribute some of my own thoughts as well.