Game Theory VL
Lehrveranstaltung UZH WWF (6 Credits), 2013
Lehrveranstaltung UZH WWF (6 Credits), 2013
prisoner's dilema:
How many strategies when T = 2?
5 nodes for each player with 2 possible actions:
2^5 = 32 strategies
what's the subgame perfect equilibrium in repeated games with finite T?
if the normal form game has only 1 NE:
--> The NE is played in every stage!
if the normal form game has multiple NE:
--> game has to end with one of the NE (glaubi!?)
& find delta: ..... next card ;)
Is it a NE?
Yes, if:
5 + 4 x delta > 6 + 1 x delta ==> if delta > 1/3
SPE in repeated games with infinite T:
How to find delta (GRIM strategy) ?
cooperation > deviation:
C-Profit x 1 / (1-delta) > C-profit + D-profit x delta / (1-delta)
What does the Folk Theorem say?
in repeated games, if agents are patient enough (delta is high enough) and T --> unendlich,
many average payoffs (above the NE payoffs) can be attained with SPE strategies.
A Static Bayesian Game consists of:
...?
- The set of players I
- For each player i:
a set of possible types T.i & a set of actions A.i
- payoffs which depend on the actions taken by all players and types
- Probability measure on types p: T --> (0, 1)
- All these elements are common knowledge
How to solve a game with incomplete information!?
--> What was John Harsanyi's great idea?
To transform a game of incomplete information into a game with imperfect information.
To do so he introduced a new player, nature, who moves at the beginning
Definition of a Bayesian Nash Equilibrium!?
In a static Bayesian Game the strategies s* form a (pure-) strategy bayesian NE if for each player i and for each of i's types t.i no player wants to change her strategy, even if the change involves only one action by one type.
Give some examples for games with incomplete information. !?
- auction: Bidders do not know how much the other bidders value the object
- an insurance company does not know for sure the characteristics of the client
- we do not know if a second hand car is good or not
- a country does not know the exact military strenght of the enemy
- entrant / incumbent game
- etc....
If mü is the belief of player 2: probability that he is at the left note, given that he is at his information set.
How do we find mü?
--> picture
a) with what probability is P2's info set reached?
b) with what probability is p2's left node reached? and the right one?
c) What belief mü should player 2 have?
d) given those beliefs, which one is p2's optimal strategy?
a) 2/3
b) left: 2/3, right: 0
c) mü = 1
d) always play L
Assume now that P1 plays a mixed strategy which attaches equal probability to each of her pure strategies. Given this stragey for p1,
a) With what prob is P2's info set reached?
b) prob for left & right node?
c) mü?
a) 5/6
b) left node: 2/3, right node: 1/6
c) mü = 4/5
....give those beliefs, wich one is p2's optimal strategy?
b) is that strategy, together with p1's strategy, a NE?
c) expected value of L? and of R?
a) ????
b) ????
c) L: 4 x (4/5) + 0 x (1/5) = 16/ 5
R: 3 x (4/5) + (5/5) = 17 / 5
--> R > L
What is the unique solution to all bargaining problems?
The solution, that satisfies Nash's four axioms!
If...
- "you do not leave anything on the table"
- the outcome doesn't depend on the utility function
- one doesn't gets more than the other one
- Assume that you think (x.y) should be the solution and that I tell you that a set of partitions cannot be chosen but (x,y) is still possible. --> you still want (x,y) to be the solution!
What are Nash's four axioms, that lead to the Nash bargaining solution?
1.) Invariance to equivalent utility representations (If we change the utilities according to positive affine transformation, the solution should not change!)
2.) pareto efficiency
3.) symmetry (if the bargaining problem is symmetric, then both players should be treated the same)
4.) Independance of irrelevant alternatives (options which are not selected should not change the solution of they are no longer available)
To what do this four nash axioms lead?
(Formel für Problemlösung im bargaining)
The solution assigns to the bargaining problem the pair of payoffs that solves the problem:
R / F ?
a) If we make on of the player more risk averse (make his utility more concave) the bargaining problem changes and the less risk averse bargainer gets a higher share.
b) Improving a bargainer's outside option will make him better off in the bargaining
a) true
b) true
Describe the Rubinstein's Bargaining Game
P1 & P2 play:
- a cake of size one has to be divided. In a starting round, P1 makes a proposal tha P2 can accept or turn down
- if he accepts the cake is split according to this
- if he declines the games moves one round forward and it is now P2 who proposes a share
---> This game can last forever, but time is valuable!!
payoff z, after n round is worth:
delta ^n x Z
(set of Nash equilibria is infinitely large in this game!)
What's rubinsteins bargaining solution?
we solve first for a finite number of periods --> find the SPNE
--> it can be shown that for infinite T, there is a unique SPNE in which:
1 gets 1/ (1+ delta) and 2 gets: delta / (1+delta)
Compare the Nash bargaining solution with the NE in general.
Does the NE fulfill the 4 axioms of the bargaining solution?
1.) Invariance to equ. utility representations: YES
(NE are invariant to affine (=equivalent) utility representations)
2.) pareto efficiency: NO
3.) Symmetry: NO
4.) Independance of irrelevant alternatives: ??
a) Describe a game with perfect information.
b) And give some examples.
(belongs to "extensive form games")
a) a player moves
his action is observed by the other player who then moves
and his action is observed by the other player and so on, until the game finishes.
b) - removing sticks
- chess
- game played with myself (alarm clock)
- incrumbent and challenger (price fight or not?)
How do we usually solve a game with perfect information?
⇒ Games of perfect information are typically solved backwards starting at the end, and are very important to understand credibility of threats and commitment.
normal form is a description of a game. Unlike extensive form, normal-form representations are not graphical per se, but rather represent the game by way of a matrix. While this approach can be of greater use in identifying strictly dominated strategies and Nash equilibria, some information is lost as compared to extensive-form representations
Describe an equilibrum in a normal form game.
You have played an equilibrium if your choice was a best reply to the other player’s choice and this is also true for the other player, namely her/his choice is a best reply to yours.
In an equilibrium you cannot gain anything by choosing another strategy under the assumption that the other player does not change hers/his.
a) describe a simultaneous move game
b) and give some examples
a) simultaneous games are typically represented by the normal form; a game where both players have to decide/move simultaneously
b) prisoner's dilemma
decision or game:
a) a pair of teenage girls choosing dresses for their prom
b) a group of grocery shoppers in the diary section with each shopper choosing flavor of yogurt to purchase
a) game - girls choice affects the others choice
b) decision - no interaction among players
decision or game:
a) a college student considering what type of postgraduate education to pursue
b) the new york times and the wall street journal choosing prices for their online subscriptions this year
a) decision - doesn't affect other people
b) game - (Betrand; price competition; strategic)
What kind of decision theory is game theory?
Game theory is interactive decision theory
(It studies the behavior of players whoce decisions affect each other)
What's the difference between a) complete and b) incomplete information?
a) In a game with complete information all players are common knowledge. Example: prisoner's dilemma
b) In a game of incomplete information at least one player is uncertain about another player0s payoffs. Example: an auction ("true men do not eat quiche")
What's the difference between a
a) zero-sum game &
b) non zero-sum game?
a) In a zero-sum game what one players win is what the other looses. --> The players interests are completely opposed. The sum of the payoffs is always O.
Example: Rock-Scissors-Paper
b) In non zero-sum games both players can gain (think of trade), both can loose (think of nuclear war), there are some element of conflict but also scope for cooperation (think of bargaining)
difference between:
a) one shot game
b) repeated game
a) a one shot game is played only once by the players
b) In a repeated game, the "same" game is played repeatedly by the "same" players
What kind of game is "removing sticks"?
a dynamic game of perfect information
An extensive form of a game consists of:
(6)
- Players
- Orders of moves
- Actions. What players can do when they have to move
- Information sets. What each player knows when he has to move.
- Payoffs received by each player for each combination of moves that could be chosen by the players
- The probability distribution over exogenous events. New player: Nature
If a player does not know the moves a previous player had made, he cannot distinguish the corresponding nodes.
--> we speak of....
imperfect information
(a player does not know in which node he is)
Whats an information set?
An information set is a collection of decision nodes which cannot be distinguished by the player with the move.
(Entscheidungsknoten, die nicht unterschieden werden können)
--> in a game of perfect information each information set contains one and only one decision node.
When do we speakt of imperfect recall?
If ignorance about previous moves is the result of a player forgetting something he did before.
When do we speakt of games of perfect information?
If all moves are observed and not forgotten
difference between:
a) move
b) strategy
a) a move is a single action to be taken by a player at a information set controlled by him
b) A strategy is a specification of moves at each information set of the game for a player. It is a complete plan of action, that tells what a player does at any information set in which he may be called to decide.
What is a complete plan of action?
A complete plan of action tells what a player does at any information set in which he may be called to decide
Ultimatum Game:
a proposer has 100CHF to split with the responder. He offers a division and the responder can either agree or both get nothing.
If players are rational and only care about the money, the responder will accept anything and 1 will offer the smallest possible amount.
--> Why is this not observed in experiments?
(offers below 10% are rare and offers below 20% are often rejected)
proposers:
are unable to do the correct backward reasoning,
are altruistic or care about fairness / may feel ashamed
or may fear rejection of low offers
responders:
emotion-driven response,
stakes are too low in the Lab (stakes= Einsätze)
or biological aspects
-
- 1 / 67
-
Cartes-fiches
When do we speakt of games of perfect information?
If all moves are observed and not forgotten
difference between:
a) move
b) strategy
a) a move is a single action to be taken by a player at a information set controlled by him
b) A strategy is a specification of moves at each information set of the game for a player. It is a complete plan of action, that tells what a player does at any information set in which he may be called to decide.
What is a complete plan of action?
A complete plan of action tells what a player does at any information set in which he may be called to decide
Ultimatum Game:
a proposer has 100CHF to split with the responder. He offers a division and the responder can either agree or both get nothing.
If players are rational and only care about the money, the responder will accept anything and 1 will offer the smallest possible amount.
--> Why is this not observed in experiments?
(offers below 10% are rare and offers below 20% are often rejected)
proposers:
are unable to do the correct backward reasoning,
are altruistic or care about fairness / may feel ashamed
or may fear rejection of low offers
responders:
emotion-driven response,
stakes are too low in the Lab (stakes= Einsätze)
or biological aspects
What's the difference between a game with
a) perfect information
b) complete information?
a) you know, what the other players did before
b) you know the payoffs
What means "describe the game formally" ?
(-->give examples)
describe:
- set of players (ex: I = {S, T })
- order of moves (ex: simultaneously)
- information set (ex: HS = ({⊘},{S,n},{S,n,S,n}) )
- actions (ex: AS= {S,N} )
- strategies (ex: SS ={(NNN),(SNN),(NSN),(NNS),(SSN),(SNS),(NSS),(SSS)} )
- complete equilibrium strategies (ex: S *: {S, S, N} )
Two types of stategies in simultaneous-move games:
1.) pure stategies: one specific strategy is played for sure.
2.) mixed stategies: the player randomizes and chooses different pure stategies with positive probability. For instance tossing a coin and go to Tonhalle if Tails comes out and go to the Opera House if Heads comes out.
The set of stategies in simultaneous-move games can either be..... (2)
1.) discrete (e.g. go to Tonhalle, or to the Opera House)
2.) continuous (e.g. supply of electricity, a price)
What do we need to apply IESDS?
common knowledge of rationality
--> we need to assume not only that all players are rational, but also that all players know that all players are rational, and that all players know that all players know that all players are rational, and so on
Nash Equilibrium Theorem !?
In the n-player normal-form G={I, S1,....,Sn ; u1,....un} if n is finite and Si is finite for every i, then there exists at least ONE nash equilibrium, possibly involving mixed strategies.
exceptions: monopoly for example
Describe the
a) Cournot Equilibrium
b) Bertrand Equilibrium
a) The NE of the Cournot game: In this equilibrium the profits of each firm are positive but lower than half the monopoly profits
b) The NE of the Bertrand game: profits are zero.
Does rationality lead to equilibrium play?
not necessariliy.
We know that rational players will play stategies that survive IESDS. In some cases this leads to a unique profile --> this is then the unique NE of the game
What's a second price auction?
ex. with picasso:
each participant writes how much he's willing to pay. the painting goes to the one who was written the highest number but he will pay the second highest bid.
Imagine 3 girls sitting in a circle, each wearing either a red hat or a white hat. Suppose that all the hats are red. When the teacher asks if any student can identify the color of her own hat, the answer is always negative, since nobody can see her own hat. But if the teacher happens to remark that there is at least one red hat in the room, a fact which is well-known to every child then the answers change. How?
The first student who is asked cannot tell, nor can the second. But the third will be able to answer with confidence that she is indeed wearing a red hat. (common knowledge)
--> If the hats of 2&3 were white, then the first girl would know, that her one is red. But she cannot tell, which reveals to 2 &3 that at least one of them is wearing a red hat.
the 3 one knows because she thinks: "If my hat had been white, then the second girl would have answered that she was wearing a red hat, since we both know that at least one of us is wearing a red hat. But the second girl could not answer, Therefore I must be wearing a red hat!"
Dynamic Games:
How do we get rid of some equilibria which involve non credible threats?
By solving the game with Backward Induction
what is a strictly dominant strategy?
s'i is strictly dominant if,
- for all combination of the other players' strategies and
- for each strategy s''i of player i,
his playoff from playing s'i is strictly higher than that from playing s''i
=> the payoff by playing s'i is strictly higher than any other payoff
rational payers always choose the strictly dominant strategy!
Give an example for a game with continuous strategy spaces
- Monopoly
- political campaign advertising
Does Rationality lead to equilibrium play?
not necessarily.
--> we know that rational players will play strategies that survive IESDS. In some cases this leads to a unique profile. (This is then the unique NE of the game)
Definition of Nash Equilibrium
A NE is a list of strategies, on for each player, such that no player can get a better payoff by switching to some other strategy that is available to her while all the othere players adhere to the strategies specified for them in the list.
What's a...
a) strict NE
b) not strict NE
a) a NE where the payoffs of both players are strictly larger than any other payoff in their row/column
b) a NE where at least one of the players could give another answer and would get the same payoff
What's a mixed strategy NE?
a mixed-strategy profile in a finite normal-form game is a mixed NE if and only if, for each player i...
- the expected payoff to every action to which the profile assigns positive probability is the same
- the expected payoff to every action to which the profile assigns zero probability cannot be larger than the payoff of any action to twich the profile assigns positive probability
- each player's expected payoff in an equilibrium is the expected payoff to any of the actions that is used with positive probability. Simplifies the calculation.
Is it possible to play weakly dominated strategies in a NE?
Yes
What's a subgame?
- begins at a decision node x that is a singleton
- includes all decision and terminal nodes following x in the tree.
- it cannot cut any information set
--> The whole game is a subgame!
What's a subgame perfect NE?
A NE is subgame perfect if the players' strategies constitute a Nash equilibrium in every subgame
--> no matter what has happenend before, players must play a NE in the remaining game.
--> at any point in the game players believe that all will behave rationally in the remaining game
--> in games of perfect information, the SPE are the solutions found using backward induction
What does it mean for the NE, if the ranking of the payoffs of 2 games is the same?
--> they have the same PNE
What do we need in 2 games to have the same MNE?
we need a positive affine transformation with
u1 (Game2) = alpha x u1(Game1) + Beta
for both players!!
a) how many pure strategies do the players have?
b) find all the subgames
a) P1: 4 info sets, 2 possible actions -->
2^4 = 16 strategies
player 2: 3 info sets, 2 possible actions -->
2^3 = 8strategies
b) 5 subgames
What is a strategy in an extensive form game?
it tells a player what to do at each info set that may be reached (= complete plan of action)
Consider the two game trees.
(a) There is something wrong with the game tree on the right hand side. What?
At P3's infoset, P3 cannot distinguish whether P2 played a or b. Therefore the possible actions at both nodes must be the same (f.e. T and B at both nodes)
What's the difference between a SPE and a NE?
In the SPE, each player's strategy is required to be optimal for every history after it is the player's turn to move, not only at the start of the game, as in a NE.
prisoner's dilemma:
How many possible histories after t = 2?
1 x 2 x 2 x 2 x 2 =16
prisoner's dilema:
How many strategies when T = 2?
5 nodes for each player with 2 possible actions:
2^5 = 32 strategies
what's the subgame perfect equilibrium in repeated games with finite T?
if the normal form game has only 1 NE:
--> The NE is played in every stage!
if the normal form game has multiple NE:
--> game has to end with one of the NE (glaubi!?)
& find delta: ..... next card ;)
Is it a NE?
Yes, if:
5 + 4 x delta > 6 + 1 x delta ==> if delta > 1/3
SPE in repeated games with infinite T:
How to find delta (GRIM strategy) ?
cooperation > deviation:
C-Profit x 1 / (1-delta) > C-profit + D-profit x delta / (1-delta)
What does the Folk Theorem say?
in repeated games, if agents are patient enough (delta is high enough) and T --> unendlich,
many average payoffs (above the NE payoffs) can be attained with SPE strategies.
A Static Bayesian Game consists of:
...?
- The set of players I
- For each player i:
a set of possible types T.i & a set of actions A.i
- payoffs which depend on the actions taken by all players and types
- Probability measure on types p: T --> (0, 1)
- All these elements are common knowledge
How to solve a game with incomplete information!?
--> What was John Harsanyi's great idea?
To transform a game of incomplete information into a game with imperfect information.
To do so he introduced a new player, nature, who moves at the beginning
Definition of a Bayesian Nash Equilibrium!?
In a static Bayesian Game the strategies s* form a (pure-) strategy bayesian NE if for each player i and for each of i's types t.i no player wants to change her strategy, even if the change involves only one action by one type.
Give some examples for games with incomplete information. !?
- auction: Bidders do not know how much the other bidders value the object
- an insurance company does not know for sure the characteristics of the client
- we do not know if a second hand car is good or not
- a country does not know the exact military strenght of the enemy
- entrant / incumbent game
- etc....
