Lots of people wanted game theory, so game theory it is. The logical first question: what is game theory?
Game theory is typical of math. What mathematicians like to do is reduce
things to fundamental abstract structures or systems, and understand them in
terms of the abstraction. So game theory studies an abstraction of games - and
because of the level of abstraction, it turns out be be applicable to a wide
variety of things besides what you might typically think of as games.
Game theory starts with the fundamental idea of a game. What is
a game?
A game consists of a system with at least two agents (that is,
entities that can perform actions), who each have their own
interests which they are trying to satisfy. They have a situation,
which consists of the set of things that they have, and the things that
they want. They have a set of rules, which describes what actions they
can take in the situation, and when they can take them.
Game theory looks at that, and tries to understand how the
agents will interact. You can study it from many different points
of view, and with many different objectives.
For example, you can look at it from a very "pure" perspective, and
try to find optimal strategies for a particular kind of game. For example,
if you analyze the game of Nim, you can find that there's a guaranteed
winning strategy for player two. (We'll look at Nim, and why it's always winnable by player two in a later post.)
You can also use game theory for things that seem very non-game like.
Basically, any situation in which you have multiple interacting agents with
distinct, possibly conflicting goals, you can analyze it using game
theory.
A classic example of this is the prisoner's dilemma. In the
prisoners dilemma, you have two criminals who've been arrested for a murder.
The two criminals (now prisoners) are the agents. The police know that they
did it; but they don't have enough evidence to convict them of murder, only of
a lesser charge. So the police want to get the prisoners to rat on each other.
You end up with the following situation:
- If neither prisoner rats on the other, they'll both get off with a very light sentence of 6 months in jail.
- If one prisoners rats on the other, that prisoner goes free,
and the other one gets a life sentence. - If both prisoners rat on each other, they each get 10 years in
jail.
If you look at this in the abstract, it's obvious what the prisoners
should do. If they both keep their mouths shut, then they'll both get off
easy. But if you look at it in terms of cost/benefit for one of them,
you get a very different answer: for a prisoner acting only in his own self-interest, the correct choice is to rat on his partner. Game theory
looks at it from that latter point of view: each agent is concerned
only with maximizing the benefit/minimizing the penalty for
themselves.
To see why that works, just look at it from of one of the prisoners. We'll call him Adam, and we'll call his partner Bert. Adam doesn't know what Bert is going to do. So he looks at the options.
If Bert keeps his mouth shut, Adam has two choices: he can keep quiet, or
he can rat on Bert. If he keeps quiet, he'll go to jail for six months. If he
rats, he'll walk. Clearly, in this case, ratting on Bert is the best choice
for Adam.
If Bert rats, Adam has the same two choices. If he keeps quiet,
he goes to jail for life. If he rats, then he goes to jail for ten years. Once again, clearly, the better choice for Adam is to rat.
So each prisoner maximizes his own benefits by testifying, even though
that means that they'll both wind up spending 10 years in jail, when they
could have gotten off with 1 year each by cooperating. By trying to always
maximize their own benefit, both suffer.
Game theory works out a kind of categorization of games, based on
how many agents, whether they can cooperate or communicate, whether
they move simultaneously or take turns, etc. It also categorizes
based on the kinds of benefit/penalty relationships that define the
possible outcomes of the game. For games of different forms, it
describes strategies, equilibriums, and tipping points in those games.
It turns out to be an incredibly useful framework. It's used in computer
science for things like protocol design; it's used in economics for models of
markets; it's used in negotiation studies; it's used in sociology. The basic
idea of multiple parties acting in their own interest is a fundamental
framework for understanding almost anything involving multiple people or
multiple interacting processes of any kind.
- Log in to post comments
Hi Mark,
Game Theory - an excellent choice.
USA Today has an article from Harvard study: Nice guys actually finish first on a prisoner's dilemma game.
The outcome is very much like the paper that secured 1/3 Nobel 1994 Economics Prize for John Nash.
Personally, I prefer pursiut-evasion games used in robotics, studied extensively by Tamer Basar, Chair EE and Computer Engineering, UIUC who cowrote "Dynamic Noncooperative Game Theory" with Geert Jan Olsder, Math Faculty of Information Technology and Systems, Delft University of Technology.
I find the mathematics of the last paragraph very similar to dynamics and ergodic theory even though the terminolgy is not identical, but somewhat related via thesaurus.
It's 6 months each, or 1 year total.
Good intro.
I highly recommend all of Thomas Schelling's work, in case you haven't seen it. In particular, The Strategy of Conflict is a brilliant use of game theory in the least mathematical but most intuitive way I've ever seen.
What I've always wondered about game theory is why it's called a theory? To me a theory implies that there's some kind of a framework with many basic results that generalize well, but that's obviously not true of games. All but the most trivial of games are too complex to even discover optimal strategies (when they exist), let alone other interesting properties. And in games where we can figure out these things, there are no general methods for doing so. It might make sense to talk about a theory of a game, but not a theory of games.
Douglas Hofstadter's book, Metamagical Themas, contains an extensive discussion of the Prisoner's Dilemma and the most successful strategies for it.
@Flaky: I think you're using a scientific/physical sense of "theory", whereas what we're dealing with here is a mathematical sense. The abstract ideas defined here, of agents interacting with choices and payoffs/penalties depending on the choices, is indeed a theory of games (though not of all games) in the same sense that, say, kinetic theory of gases is a theory of matter (but not of all matter).
Prisoner's dilemma is fascinating. There've been whole books written on it. One accessible one is
Poundstone, W (1993) Prisoner's dilemma.
somewhat more technical is
The evolution of cooperation by Axelrod
For repeated prisoner's dilemma, there is a simple strategy that is almost optimal: Tit for Tat. I've read some articles that say that some modifications of tit for tat are even better, but these are usual fairly minor variations. (e.g., tit for tat except once in a while be 'nice' regardless).
@Flaky also: When they say "game", they mean a very specific type of game. I'm not sure if you thought otherwise, but for example they're not referring to Starcraft or Halo 3! Rather, mathematical games (typically) have two players, players must alternate moves, and the last person to move wins. This is the definition of a combinatorial game, which is kinda a sub-branch of game theory, but many of the games end up looking like that. Nim, as Mark mentioned, is one such game.
I have studied a game called the Tree Game. If you can imagine a binary tree, i.e. you have straight lines (edges) and dots (nodes) connected by the edges. Each dot has at most two other edges branching off from it, and only one edge coming into it. You cannot move backward, or move to a non-connected node. You have two players, left and right, and each branch from a node goes to the left or the right. I always imagined the trees pointing up, even though most computer scientists think of trees as pointing down. Anyway, it seems like a trivially simple game: You start at the bottom of the tree, and alternate moves (choosing someone to start) until the last person has moved. Player Right can only move on right-branches, and vice versa. True, for a game of a single tree, this is trivial; but when you get into games of even 5 trees, this becomes difficult to solve, assuming moderate complexity of the trees.
The abstraction comes in when you try to assign values to the trees and use that to figure out what the best strategies probably are. I'm sure Mark will have more on this later, so I'll leave it to him (he's better at explaining these things).
Oh, a critical note to my comment: Combinatorial game theory is not the same as game theory. They're different, I just found out from wikipedia. I should have read that first. But it was one thing that was confusing to me all the time back during my research. :D Game theory deals with games of chance, imperfect games, and other, more realistic settings than does CGT.
My mathematician friend Ben Allen recently blogged about the Prisoner's Dilemma, here.
Quick question: Is game theory supposed to be normative (telling me how I should act in a game), descriptive (describing how people will tend to act in game situations), both, or something else.
The reason I ask is that a prominent game theorist told me it was neither: you couldn't use game theory to figure out how you should act and you couldn't use game theory to figure out how others will tend to act. I didn't understand then, and I'm not sure I do now. Here is the quote from the game theorist, so you can judge for yourself: "I think it is a mistake to think of game theory as a theory that gives practical advice about what to do in the kind of situations it models. Nor do I think the theory, by itself, yields predictions about how people will behave."
@bill: That corresponds to my limited understanding of game theory as well. In general, games are too complicated to yield optimal strategies for individual agents and it's certainly not psychology, so it certainly can't answer how humans would behave.
Instead game theory seems to play around with kind of what-if scenarios. What if these agents follow this strategy and what if these other agents do that? Even then it's usual to run simulations, since any comprehensive analysis may be intractable.
@#11
I'm certainly no expert, but it sounds more like he was saying that the psychology of the games play a huge part, which game theory can't really answer effectively (as far as I know).
Perhaps because there are always uncertain elements to it, such as both of the prisoners happening to be altruists, he may have been saying simply that it gives answers for what people SHOULD do for the best results, but not necessarily what people WILL do. Yeah, I think that's the ticket: People will sometimes be random or do something totally unexpected, and that can change the situation considerably.
At least in a strictly qualitative analysis, game theory tells us a bit about altruism. Imagine a population of predatory animals who live and hunt as a pack, and where social interactions are modelled by Prisoner's Dilemma-type situations; the move any player will most probably make is determined by inherited instinct.
Too many "selfish moves" will be detrimental to the pack's viability: packs consisting mainly of selfish members will die out quicker than packs consisting mainly of unselfish members. So even without mentioning "higher functions" such as empathy or conscience, there's a suggestion of a mechanism by which unselfish behaviour could evolve entirely without the need for a god to create a moral code.
I'm just not quite sure how you'd model it ..... I'm sure it would be an interesting experiment, though .....
In some cases, it is possible to make predictions with Game Theory, and have them work reasonably well.
A key factor is that the agents involved in most basic games are assumed to be rational, which means (roughly speaking) that they think things through and try to maximise their utility. You can get utility from helping others, so rational isn't the same as selfish, by the way.
People, as a whole, are not rational by Game Theory standards. And if you're playing a game where you risk a few pennies, you're going to trust luck, your instincts, or whatever - giving game theorists a nightmare. On the other hand, if you're risking thousands of dollars (or euros), and have the time to think things through... Game theory becomes a very good predictor. See papers by Ken Binmore for more detail.
Another example where Game Theory works well is auctions. Basic auction mechanisms are well understood, and the effects of different auction mechanisms on prices and buyer satisfaction also.
Of course, trying to apply Game Theory to everything is not going to work well - because people are not rational, don't have enough information or time to think things through, and more.
Questions about game theory raised in some of the previous posts/comments are answered to some extent in this Scientific American article on The Traveler's Dilemma.
Not sure why the link didn't make it above. Maybe this one will. http://tinyurl.com/2bhjo6
My first exposure to the concept of Game Theory was through a BBC documentary by Adam Curtis called "The Trap". It doesn't have a too positive view on the impact of game theory on the world, but it is a really eye-opening documentary. Here is a synopsis http://www.blairwatch.co.uk/node/1690 The documentary itself is available on The Pirate Bay and its ilk.
From the synopsis: """Hayek was largely ignored until scientists looking for ways to win the Cold War developed strategies based on "Game Theory", which was pioneered by the schizophrenic mathematician John Nash at the Rand corporation. Game Theory applied as military strategy kept a balance of power as the Soviet Union would not attack the USA out of fear and self-interest knowing that if they did, they too would be devastated. Game Theory, however, produced a dark vision of humanity where everyone was mistrustful of one another. John Nash demonstrated that it was possible to create stability through suspicion and self-interest in the whole of society rather than just Cold War strategy. Nash developed a game called "Fuck You Buddy" in which the only way to win was to betray your partners. By applying Game Theory to all forms of human interaction, he proved that a society based on mutual suspicion didn't necessarily lead to chaos, but he made the assumption that humans were naturally calculating and always seeking an advantage over their fellows and this led to an equilibrium. This system could only work if everyone behaved selfishly. As soon as people started co-operating together, instability ensued and this proved to be the case when the system was tested - participants co-operated with each other."""
Does anyone know whether this theorie has already been applied to traffic congestion problems?
kind regards,
Jeroen
Game Theory was not pioneered by John Nash but by John von Neumann. There is a good chronology of the history of Game Theory here.
RE #19:
There is this paper abstract available on-line, Su, et al, "A Game Theory Model of Urban Public Traffic Networks', 2007 on Elsevier Science via doi:10.1016/j.physa.2006.12.049.
I suspect other examples may be accessed through Wikipedia, Stanford Encylopedia, IEEE, Google or ArXiv.
A game variant of discrete events known as Max-Plus Algebra has modeled railways and pedestrian flows. Geert Jan Olsder, Delft, works in this area.
I like the fact that IIRC one known slightly better strategy is cooperation where individuals sacrifice themselves for the group. (Not necessarily hereditary related altruism, AFAIU.) Sacrificial patsies means it's a mafia - and so you get extra support for moral and de facto law vs more or less hidden and uneconomical cooperation in some market sectors of society.
Altruism is complicated and supported by heredity, so there are AFAIU many models like reciprocal altruism and kin selection. Dunno the theoretical status of which are actually seen in nature.
Mark Chu Charrol, do you could say "I believe the earth is 4.5 billion years old." for me? I just need you to say that so I'm sure that's what you believe. I tried searching your blog for this from you, but I can't find it anywhere.
Mark Chu Charrol, do think you could say "I believe the earth is 4.5 billion years old." for me? I just need you to say that so I'm sure that's what you believe. I tried searching your blog for this from you, but I can't find it anywhere.
skeptic4u:
Might I ask just why you'd ask this question here? It's about as off-topic for this post as possible.
Another recent bit about the prisoners dilemma from a psychology perspective. What might game theory have to say about the optimal strategy in this version, are people playing it right?
http://scienceblogs.com/notrocketscience/2008/03/winners_dont_punish_pu…
#24, #25:
We have a 2-player zero sum game. Player 1 is called "Scientist." Player 1 is called "Intelligent Design Advocate" or "Young Earther."
Now, all we need is the payoff matrix, a calculation of The Nash Equilibrium, and a pass to see "Expelled."
Properly done, this is publishable... but I'm not quite sure where.
Mark C. Chu-Carroll, where else can I ask you? Where will you answer my question if you haven't written a blog that is relevant to the age of earth (which would then make my question relevant)? Why didn't you just answer the question here? You must have OCD or something as to think it absolutely necessary that every comment fallowing a blog must relevant to the blog.
I'm not a creationist, and I believe the earth is 4.55 billion years old. I'm just a high school student gathering names of people that believe the earth is 4.55 billion years old.
PEACE.
skeptic4u:
Ever heard of email?
You'll pardon me if I wonder why someone would show up on a math blog in a discussion of game theory, and start asking irrelevant questions about the age of the earth. It's an exceedingly strange thing to do.
I'm wondering if people are right complain that they lose because the other players in, say, Whist, "don't know how to play".
Hope you will touch the issue of nondeterministic games.
Re #30, Dante:
Nim and Chess are "open games" where, at first approximation, ALL information is right there on the board, no secrets, obvious to both players and all spectators.
But, second approximation, in Chess there is bluff and deception, because of the limited time and computational capability of each player. Poker and bridge and whist are "closed games" where there is information in one's hand about cards that the other players can't see.
Hence reading the opponent and psychologically stressing the opponent are necessary skills, as is understanding probability.
Read the life of Cardano, "the gambling scholar", who started Probability Theory, while being a professional Astrologer, and the first person to have a modern business of royalties from series of books, which list forthcoming titles in their pages to pre-promote. Another magician/Scientist akin to Newton, and just as dangerous to cross.
I strongly recommend this book:
The Mathematics of Games And Gambling (2nd ed.), Edward Packel, 2006, Mathematical Association of America, 190 pages, ISBN 0-883-85646-8
The new edition of a favorite introduces and develops some of the important and beautiful elementary mathematics needed for rational analysis of various gambling and game activities.
Most of the standard casino games (roulette, craps, blackjack, keno), some social games (backgammon, poker, bridge) and various other activities (state lotteries, horse racing) are treated in ways that bring out their mathematical aspects.
The mathematics developed ranges from the predictable concepts of probability, expectation, and binomial coefficients to some less well-known ideas of elementary game theory.
The second edition includes new material on:
⢠Sports betting and the mathematics behind it
⢠Game theory applied to bluffing in poker and related to the "Texas Holdem phenomenon"
⢠The Nash equilibrium concept and its emergence in popular culture
⢠Internet links to games and Java applets for practice and classroom use. Game-related exercises are included and solutions to some appear at the end of the book.
If you get a chance, I'd like to request the Volunteer's Dilemma as an example at some point.
It looks to be a good place to start looking in designing artificial intelligent systems. In carbon based life really nothing is black or white. Yet in silicon life everything need be false or true. At least it has been this way, but being able to manipulate computer logic and outputs using these type scenarios, one could possibly reverse engineer a silicon based fuzzy consciousness of sorts. Really interesting ideas.
Luck and chance have been mentioned in passing in this blog chain. Is there a Game Theory model for the Luck Factor?
Thanks to Google, I know there's a best-selling book of that title by UK psychology Prof. Richard Wiseman, which claims people who think of themselves as lucky are more likely to win the lottery than those who don't, not because they're better at picking winning lottery numbers, but because they're more likely to buy tickets.
I also found a reasonably precise definition of the Luck Factor in baseball by Curt Schilling: "The luck factor results from the fact that even the best pitchers are not perfect in their throws, and even the best batters are not perfect in their swings. Thus, neither pitcher or batter has complete control over the outcome." I guess Wiseman would say the one who felt lucky that day would have the edge.
So: can the Luck Factor be defined rigorously enough for Game Theory?
The computer games are really annoying because all they do is just get little kids attention and give them bad education during school
They should stop having computer games, I just want to get the kids to finish school then they can play all they want.........