Transcript
1. Trees and Tables
Game theory: study of strategic interaction. Outcome for each agent depends on the actions of all agents.
Strategy: The number of strategies for a player = the product of the number of actions at his or her decision points
Strict dominance between two strategies implies weak dominance between the same two strategies
The extensive form and backward induction
The strategic form and dominance analysis
The Winning strategy theory
Nim:
Procedure: After partial history be Alice will choose action h (not g). After partial history b Bob will choose action d (not e or f ). At the outset Alice will choose action c (not a or b).
Conclusion: Backward induction selects 1, ?1, so Alice should win.
Learning to play nim: One pile: first player wins. Two piles: first player wins if and only if piles unequal. Three piles: first player wins if any two piles equal.
2. Uncertainty and Information
Imperfect information:
Unobserved actions (The entertainment game)
Simultaneous actions (Penalty Kicks)
Exogenous uncertainty (Coin flip)
In extensive form: use information sets to allow for unobserved actions and simultaneous actions. Use moves of nature to allow for exogenous uncertainty.
In strategic form: Limit contingent plans to one action per information set. Average payoffs across moves of nature.
John von Neumann and Oskar Morgenstern: Expected utility theory and the Minimax theorem
The expected utility model
Bayesian updating of beliefs
The case of the endangered Omelette
4041521608100
3. Equilibrium and coordination
Coordination - Convention games: Multiple equilibria involving different strategies. Equilibrium outcomes are equivalent.
Coordination – Common interest games: Multiple equilibria involving different strategies. Equilibrium outcomes are Pareto ranked.
Coordination – Bargaining games: Multiple equilibria involving different strategies. Equilibrium outcomes are not equivalent and Pareto unranked.
Cournot Duopoly Model: Model, profit functions, observations, first order conditions for optimality, Equilibrium variables, Best response functions
4. Randomisation and Outguessing
Mixed strategy Nash equilibrium
Outguessing games: cyclical best responses (i.e. all best response cycles of length four or more)
Minimalist poker
Existence of equilibrium
Examples: The attraction repulsion game, the miners’ strike, penalty kicks
Equilibrium Existence Theorem (Nash): Allowing for mixed strategies, any finite game possess at least one Nash equilibrium
Minimax theorem (von Neumann and Morgenstern): Allowing for mixed strategies, any finite, two-player, constant sum game possess at least one Nash equilibrium. Moreover, all equilibria of such a game are equivalent.
5. Prisoners Dilemma
The prisoners dilemma:
410575518113000
The prisoners can cooperate (hold out) or defect (confess)
The decision of both prisoners will determine both their outcomes – thus, this is the study of strategic interaction – game theory
The payoffs are % chances of avoiding execution (higher = better)
We can determine that the Nash equilibrium is mutual confession
The mutual cooperation outcome <50,50> pareto dominates the mutual defection outcome <10,10>
34500584381500Abstract formulation: T > R > P > S
Essential features of the prisoners dilemma:
Agents can either cooperate or defect
Cooperation costs the cooperate (so T > R and P > S) and benefits the opponents (so R > S and T > P)
The benefit from the opponents cooperation OUTWEIGHS the cost of one’s own cooperation
Do we have a more practical application of the prisoners' dilemma?
Take the parental discipline dilemma:
4463535605910Two parents are trying to discipline their child, while at the same time, trying to win the child's love. The child does something stupid, and the parents both agree to punish him/her. Both parents may have agreed to punish the child together, but when on their own, they have the option to cooperate and follow through with the punishment, or defect and relent on the punishment.
The specific strategic form would look like this:
The payoffs represent the following states: R = The child Respects the child, NR = The child does not respect the parent, L= The child loves the parent, H = The child hates the parents, L > R > NR > H
As seen in the table, the Nash equilibrium will be reached when both parents relent, and their child will respect neither one of them. Had they both cooperated (punished)
6. Promises and Threats
Schelling: Enforceable promises cannot be taken for granted, though the possibility of trust between two partners does not necessarily need to be ruled out. The distinctive character of a threat is that one asserts that he will do, in a contingency, what he would manifestly prefer not to do if the contingency occurred, the contingency being governed by the second party’s behaviour.
The promise game: B has made a promise. A can either distrust or trust B’s sincerity. If A trusts, B can either keep or break his promise. (Via backward induction: B will break his promise, so A will distrust him)
Strategy < d ,b > with payoffs < 1,1 > are dominated by < 2,2 >
No strictly/weakly dominated strategies for A. For B: break weakly dominate keep
The threat game: B has made a threat. A can either accede to the threat or scoff at the threat. If A scoffs, B can either punish or capitulate. (Via backward induction: B will capitulate if A scoffs, so A scoffs)
Strategy < a,p > with payoffs < 0,5 > are dominated by < s,c > with payoff < 1,2 >
The Bridge game:
A disputed island is located between the republic of Freedonia (F) and Kingdom of Sylvania (S).
The island is linked to Freedonia by a wooden bridge, and occupied by the Freedonia republican guard (F).
The island is threatened by the Royal Navy (S). F can either burn or keep the bridge, then S can either attack or not attack.
If S attacks, then F can either fight or if the bridge is intact, retreat.
The Unanimity game: Players interests are perfectly aligned in this game. After the partial history p, Bob and Alice play a bargaining game.
4920529259784249845117364700
492052915355840023253701535430001267434060500
39713148281
Subgame perfection:
A subgame = any portion of a game that has a single initial node. Contains all of its successor nodes, and can be extracted from the larger game without breaking an information set.
How to find a subgame perfect equilibria? If the game has perfect information, use generalised backward induction. If the game has imperfect information: Find the Nash equilibria, and test for induced equilibrium in each subgame.
Iterative dominance:
Identify all dominated strategies for each player
Then delete all dominated strategies simultaneously
Repeat in successive rounds until no more strategies dominated
Dominance may be either iterative strict or weak dominance. No guarantee that even weakly strategies will exists, so analysis may be silent.
7. Repeated Interactions
Repeated games:
A stage game is played once per period. The number of periods can be finite or infinite. Behaviour in earlier periods is observed y all players. Payoffs are averaged across periods, with or without discounting of future payoffs.
Example 1 (repeated 2 x 2 bargaining): two periods, no discounting, stage game as follows
Example 2 (repeated 3 x 3 bargaining): two periods, yielding player i in period k the stage game payoff ?i(k). Future payoffs discounted by factor ? (with 0 ? ? ? 1), so player I receives (discounted) average payoff: ?i(1) + ??i(2)/ 1 + ?
Example 3 (Repeated prisoners dilemma): Future payoffs discounted by factor ?. The two-period repeated prisoners’ dilemma possesses a unique subgame perfect Nash equilibrium in which each player defects in both periods after any history. Any finitely-repeated game whose stage game has a single Nash equilibrium possesses a unique subgame perfect Nash equilibrium in which the stage game equilibrium is played in each period after any history.
Example 4 (infinitely repeated prisoners’ dilemma): infinitely many periods [1??][?i(1)+??i(2)+?2?i(3)+··· ] = [1??] ? k=0 ?k?i(k + 1)
Achieving cooperation:
Ingredients for cooperation in the prisoners’ dilemma
Repeated interaction
Observable history
Infinite horizon
Sufficient patience
Credible (Nash reversion) threats of punishment: If both players have always cooperated in the past (the “friendly regime”), then cooperate this period. If not (the “hostile regime”), then defects this period
Applications
GE vs Westinghouse in large electric turbine generators
The Christmas Truce of 1914
Definitions
Extensive form: shows all possible sequences of action choices and associates terminal histories with payoffs
Strategy: complete contingent plan of action
Strategy profile: list of strategies, one for each player
Strategic form: associates strategy profiles with payoffs
Strictly dominates: yields a strictly greater payoff for any strategy choice
Weakly dominates: weakly greater payoff for any strategy, strictly greater payoff for some strategies
Finite: A game is finite if it has a finite number of histories
Win-lose: Only possible payoff profiles are <1,-1>,<-1,1>
Winning strategy: In a win lose game, a payoff of 1
Winning strategy theorem: In any finite, two player, win-lose game, exactly one player has a winning strategy. Moreover a win for this player is selected by backward induction on the game tree.
Information set: is a collection of partial histories that are indistinguishable to the player who must choose an action
Perfect information: if each information set contains a partial history
Imperfect information: if at least one information set contains multiple partial histories
Winning strategy theorem: In any finite, two player, win-lose game of perfect information, exactly one player has a winning strategy. Moreover a win for this player is selected by backward induction on the game tree.
Best response: if it yields a weakly greater payoff than any other strategy
Nash equilibrium: if each player’s strategy is a best response to his or her opponents strategies
Pareto dominates: weakly preferred by all players and strictly preferred by some players
Pareto efficient: if it is not pareto dominated by any other outcome
Definitions
Pure strategy: complete, contingent plan of action
Mixed strategy: for a player is a probability distribution over his or her pure strategies
Subgame: Is any portion of a game that has a single initial node, contains all of its successor nodes, and can be extracted from the larger game without breaking an information set
Subgame perfect: A pure strategy Nash equilibrium is subgame perfect if it induces an equilibrium in each subgame
Cumulative summary (Topics 1-4)
Tools:
Extensive form (with information sets and moves of nature)
Strategic form (with payoff averaging)
415401615128400Expected utility model (with Bayesian updating)
Modes of analysis:
Backward induction
Dominance analysis
Pure strategy Nash equilibrium
Mixed strategy Nash equilibrium
Formal results:
Winning strategy theorem
Equilibrium existence theorem
Minimax theorem
Classes of games:
Coordination games: Convention games, common interest games, bargaining games
Outguessing games
Cumulative summary (Topics 5-7)
Tools:
Extensive form (with information sets and moves of nature)
Strategic form (with payoff averaging)
Expected utility model (with Bayesian updating)
Repeated game structure
Modes of analysis:
Backward induction
Dominance analysis
Pure strategy Nash equilibrium
Mixed strategy Nash equilibrium
Iterative dominance analysis
Subgame perfect Nash Equilibrium
Formal results:
Winning strategy theorem
Equilibrium existence theorem
Minimax theorem
Classes of games:
Coordination games: Convention games, common interest games, bargaining games
Outguessing games
Prisoners dilemma
Promise games
Threat games
