An Intro To Game Theory

[ComradeRed]

I was asked to give an intro to game theory, and after procrastinating, I think I may've gotten 'round to it :P

So a game has a set of rules, or parameters, which players, or participants in the game, follow. Game theory tends to study the nature of changing these rules and the change in the behavior of the players because of this change (there are other things which it studies, but I am focusing on this one).

A simple game is played by two players, zero-sum (i.e. there is a winner and a loser, nothing in between), and finite in length (has a certain number of rounds until the game ends).

The length may be dependent on what happens in a game (e.g. chess ends when one player cannot move his or her King piece).

Now, a player has a strategy which may or may not change in the course of the game. A strategy is a set of moves that the player is considering to execute (carry out).

If we have two players, we can determine the probability of a player's actions if we set up a table. Every row is a strategy for player A, and every column is a strategy for player B. The entries in this table are the probability that player A will be in a better position (that the move will give some sort of advantage to player A).

So player B wants to execute a strategy that s/he thinks will be close to 0, whereas player A wants to execute a strategy that s/he thinks will be close to 1. Game theory is trying to take into account thinking about the strategy your oppenent will take (so Player A will also try to get the entry closest to 1 knowing B will do the strategy that is closest to 0), but this is getting advanced into the stuff.

We determine the value of the entries through some elaborate functions, based on the parameters of the game (points, pieces, etc.). I'll go into more detail tomorrow.

[bisclavret]

If we have two players, we can determine the probability of a player's actions if we set up a table. Every row is a strategy for player A, and every column is a strategy for player B. The entries in this table are the probability that player A will be in a better position

Do we need a working knowledge on probability theory as a minimum requirement in game theory? Since game theory has more of an applied math flavor, are the games dependent on the scenarios to which they are applied to or are they pretty much paradigmatic and independent of the situations?..I think my second question was pretty stupid so I shall try to redeem myself with a third one..Is there a limit to the treatment of game theory on real-life situations as 'games' wherein there seems to be an implicit notion of 'winning' as the ultimate objective? Sorry for the excitement, I guess I have to rein myself in and steer away from the philosophical questions but a few lines of the philosophy of game theory might not be too demanding and instead interest-arousing to a wider audience. :blush:

[ComradeRed]

Well, it's quite simply the probability of winning; there's nothing more to it than that (you really don't need any statistics, distributions, or tests here ;)).

Basically, you need to know that the higher the probability to win, this means you are more likely to win if the number is closer to one.


Since game theory has more of an applied math flavor, are the games dependent on the scenarios to which they are applied to or are they pretty much paradigmatic and independent of the situations? Well, it depends on the game in question. So I guess it would be "both".

There are "paradigms" in games such that they have similiar "rules"...sorta like in biology how families (et al.) have similiar genetic structure. But each game is different and unique (and special :blush: ) in some way.

But you can "make" a game context dependent (of course, to play this game would be rather dull in reality). You'd begin by writing the rules in English, then try to put it as mathematically as possible, then create a "Winning matrix" as I described.


..I think my second question was pretty stupid so I shall try to redeem myself with a third one..Is there a limit to the treatment of game theory on real-life situations as 'games' wherein there seems to be an implicit notion of 'winning' as the ultimate objective? I dunno, there are games that go on for an "infinite" number of turns. So I suppose that if you can bring in breed/die into the rules, you can get somewhere.

Then you can integrate changing strategies dependent on events in the game, and so forth.

You can make it realistic, you can make it cartoonish, you can make it apply to a situation, you can make it irrelevant. It's all up to you.

[Sanjee]

Isn't "The game theory" the theory of John Forbes Nash?

[ComradeRed]

He was a major pioneer of the field, yes (I think...); he also worked on other stuff (though I believe the technical term is "differential geometry" :P).

[bisclavret]

Nash is among the greats in the field but game theory actually started, if I am not mistaken(though some would think it started with Emile Borel but following their line of thinking Id say it started with the Babylonians) , with John von Neumann and Oskar Morgenstern's monster of a book entitled "Theory of Games and Economic Behavior", a book that I would not even bother looking at the preface or introduction unless I wanted to sulk into fits of depression and self-inadequacy for long periods of time, caused no doubt by petit bourgeois tendencies that I still have. :angry:, hence, ending up requesting comradered for a Feynman-like intro to game theory.

[ComradeRed]

One thing I should note (thanks bisclavret for reminding me), Neumann et al. pointed out that Economics has always mooched off of the mathematical structure of physics since the birth of Marginalism.

He pointed out in his "Technical preface" to The Theory of Games that Game Theory is an attempt to catch up with Quantum Mechanics (since, at the time, Quantum Field Theory was the "Bees knees" in physics).

So this is another way of looking at the role of Game Theory in Economics ;) I thought you might be interested in that (it actually fascinates me to no end that Economists are failed physicists and now lemmings :lol:).

I should also note that the "rationality" defined in Game Theory is the same skewed definition used by economists; and I should also mention, being the old fuddy-duddy that I am (:P), I misplaced my Game Theory book...so I can't comment much more right now unless you have very specific questions (I should find it later tonight...hopefully).

[coda]

I don't know if anybody else saw the program PrimeTime on Game theory a few months back. They basically said that every social interaction is a game theory, thus Life is game theory.

The show set up two simplified game scenarios. The first one was fascinating, though. They had six groups of two people who never met eachother before and told them they had to find atleast one of the other groups of people in New York City, (pop. 8 million) That was the only rule. They had no time, destination, nor description of the people they were to look for and they could find them by any means possible. But still with the density of people in NYC, it's like trying to find a needle in a haystack. Each group independently of eachother picked 12 noon as the time they thought the other groups might show up somewhere and each group picked certain famous landmarks (among tons of landmarks) that they thought the other group might choose. Amazingly, They all found each other within 3 hours or so.

Pretty cool!!

I would have lost this game for sure because I would have picked and most likely stayed at Grand Central Station (crossroads) and 12-noon never would have occurred to me at all.

Story here:
http://abcnews.go.com/Primetime/story?id=1730849&page=1

[bisclavret]

The show set up two simplified game scenarios. The first one was fascinating, though. They had six groups of two people who never met eachother before and told them they had to find atleast one of the other groups of people in New York City, (pop. 8 million) That was the only rule. They had no time, destination, nor description of the people they were to look for and they could find them by any means possible. But still with the density of people in NYC, it's like trying to find a needle in a haystack. Each group independently of eachother picked 12 noon as the time they thought the other groups might show up somewhere and each group picked certain famous landmarks (among tons of landmarks) that they thought the other group might choose. Amazingly, They all found each other within 3 hours or so

Nice. You can actually plot the possible moves on a table of some sort and then give it some sort of 'points' through probabality of winning but I think your situation is more like complex adaptive systems where an 'emergent' property or behavior that arises out of the interactions of the players or parties involved just like a traffic jam behaviour.

[bisclavret]

I've been doing more light reading on game theory and here are the more classic games

Bankruptcy
Barbarians at the Gate
Battle of the Networks
Caveat Emptor
Conscription
Coordination
Escape and Evasion
Frogs Call for Mates
Hawk versus Dove
Mutually Assured Destruction
Majority Rule
Market Niche
Mutual Defense
Prisoner's Dilemma
Subsidized Small Business
Tragedy of the Commons
Ultimatum
Video System Coordination

So I bumped into one of the simplest which is the prisoner's dilemma
***************The Table*******
*******************Al**********
*************confess**don't******
***Bob*confess*10,10***0,20****
********don't**20,0****1,1******

Ignore the asterisks in the table above, had to use them to solve indentation problem

and here's the story:

two burglars, Bob and Al, are captured near the scene of a burglary and are given the "third degree" separately by the police. Each has to choose whether or not to confess and implicate the other. If neither man confesses, then both will serve one year on a charge of carrying a concealed weapon. If each confesses and implicates the other, both will go to prison for 10 years. However, if one burglar confesses and implicates the other, and the other burglar does not confess, the one who has collaborated with the police will go free, while the other burglar will go to prison for 20 years on the maximum charge.

The strategies in this case are: confess or don't confess. The payoffs (penalties, actually) are the sentences served. We can express all this compactly in a "payoff table" of a kind that has become pretty standard in game theory. The table above is the payoff table for the Prisoners' Dilemma game.

The table is read like this: Each prisoner chooses one of the two strategies. In effect, Al chooses a column and Bob chooses a row. The two numbers in each cell tell the outcomes for the two prisoners when the corresponding pair of strategies is chosen. The number to the left of the comma tells the payoff to the person who chooses the rows (Bob) while the number to the right of the comma tells the payoff to the person who chooses the columns (Al). Thus (reading down the first column) if they both confess, each gets 10 years, but if Al confesses and Bob does not, Bob gets 20 and Al goes free.

So: how to solve this game? What strategies are "rational" if both men want to minimize the time they spend in jail? Al might reason as follows: "Two things can happen: Bob can confess or Bob can keep quiet. Suppose Bob confesses. Then I get 20 years if I don't confess, 10 years if I do, so in that case it's best to confess. On the other hand, if Bob doesn't confess, and I don't either, I get a year; but in that case, if I confess I can go free. Either way, it's best if I confess. Therefore, I'll confess."

But Bob can and presumably will reason in the same way -- so that they both confess and go to prison for 10 years each. Yet, if they had acted "irrationally," and kept quiet, they each could have gotten off with one year each.

But this is child's play
Comrade Red, can you explain Nash equilibrium in a popular book reader's terms?

[ComradeRed]

Well, once upon a time in the make believe land called West Virginia, there was a man named Nash. His theory of equilibrium is very unique.

He says that if we have a number of players in a game, there is this sort of solution concept to the game. This solution concept (http://en.wikipedia.org/wiki/Solution_concept) uses the concept of "equilibrium" of economics, but in game theory it suggests the outcome of a game (it's used as predictions of play).

Well, if no player can benefit from the current selection of strategies, and the other players do not change their strategies, this is a sort of equilibrium, isn't it?

Think about it in monopoly; if everyone just buys whatever they land on, and (theoretically) everyone has an equal amount of property, it logically follows that probablistically in the long run money won't change hands (it's sort of the same concept as flipping a coin; over the long run, the tendency is that 50% of the times it will be heads and 50% of the times it will be tails).

This sort of equilibrium, where nothin' is happenin', is called a Nash Equilibrium :)

[bisclavret]

Since most of the games are sort of 'payoff matrices' and rely on payoffs, are the ayoffs arbitrarily chosen by the one who designs the games?

[ComradeRed]

Well, yes and no. Yes, in the sense that the weight of the mechanism is chosen arbitrarily.

No in the sense that if you score a point (say), that is a positive increment of some arbitrary counter; and if you lose a point, that is a negative increment of that same arbitrary counter. The weight of the increment/decrement is based on the designer of the game.

This, I think, gets more into mechanisms and game mechanics than game theory (though some might argue it's part of game theory ;)).

I hope that made sense.