博弈论,lecture1

  本文关键词：博弈论，由笔耕文化传播整理发布。

Static (or SimultaneousMove) Games of Complete Information
Introduction to Games Normal (or Strategic) Form Representation
博弈论讲义

Outline of Static Games of Complete Information
? Introduction to games ? Normal-form (or strategic-form)

representation ? Iterated elimination of strictly dominated strategies ? Nash equilibrium ? Review of concave functions, optimization ? Applications of Nash equilibrium ? Mixed strategy Nash equilibrium
博弈论讲义

Agenda
? What is game theory ? Examples

Prisoner’s dilemma ? The battle of the sexes ? Matching pennies
?

? Static (or simultaneous-move) games of

complete information ? Normal-form or strategic-form representation
博弈论讲义

What is game theory?
? We focus on games where: ? There are at least two rational players ? Each player has more than one choices ? The outcome depends on the strategies chosen by all players; there is strategic interaction ? Example: Six people go to a restaurant. ? Each person pays his/her own meal – a simple decision problem ? Before the meal, every person agrees to split the bill evenly among them – a game
博弈论讲义

What is game theory?
? Game theory is a formal way to analyze

strategic interaction among a group of rational players (or agents) who behave strategically
? Game theory has applications

Economics ? Politics ? etc.
?
博弈论讲义

Classic Example: Prisoners’ Dilemma
? Two suspects held in separate cells are charged with a major

crime. However, there is not enough evidence. ? Both suspects are told the following policy: ? If neither confesses then both will be convicted of a minor offense and sentenced to one month in jail. ? If both confess then both will be sentenced to jail for six months. ? If one confesses but the other does not, then the confessor will be released but the other will be sentenced to jail for nine months.
Prisoner 2 Mum Confess Mum Prisoner 1

-1 , -1 0 , -9

-9 ,

0

Confess
博弈论讲义

-6 , -6

Example: The battle of the sexes
? At the separate workplaces, Chris and Pat must choose to

attend either an opera or a prize fight in the evening. ? Both Chris and Pat know the following: ? Both would like to spend the evening together. ? But Chris prefers the opera. ? Pat prefers the prize fight.

Pat Opera Opera Chris Prize Fight

2 ,
0 ,

1
0

0 ,
1 ,

0
2

Prize Fight
博弈论讲义

Example: Matching pennies
? Each of the two players has a penny. ? Two players must simultaneously choose whether to

show the Head or the Tail. ? Both players know the following rules:
? ?

If two pennies match (both heads or both tails) then player 2 wins player 1’s penny. Otherwise, player 1 wins player 2’s penny.
Player 2 Head
Head Player 1 Tail
博弈论讲义

Tail

-1 ,

1

1 , -1 -1 , 1

1 , -1

Static (or simultaneous-move) games of complete information
A static (or simultaneous-move) game consists of:
? A set of pla

yers (at least

two players) ? For each player, a set of strategies/actions ? Payoffs received by each player for the combinations of the strategies, or for each player, preferences over the combinations of the strategies
博弈论讲义

? {Player 1, Player 2, ...

Player n} ? S1 S2 ... Sn
? ui(s1, s2, ...sn), for all

s1?S1, s2?S2, ... sn?Sn.

Static (or simultaneous-move) games of complete information
? Simultaneous-move

Each player chooses his/her strategy without knowledge of others’ choices. ? Complete information ? Each player’s strategies and payoff function are common knowledge among all the players. ? Assumptions on the players ? Rationality ? Players aim to maximize their payoffs ? Players are perfect calculators ? Each player knows that other players are rational
?
博弈论讲义

Static (or simultaneous-move) games of complete information
? The players cooperate?

No. Only noncooperative games ? The timing ? Each player i chooses his/her strategy si without knowledge of others’ choices. ? Then each player i receives his/her payoff ui(s1, s2, ..., sn). ? The game ends.
?

博弈论讲义

Definition: normal-form or strategicform representation
? The normal-form (or strategic-form)

representation of a game G specifies:
? A finite

set of players {1, 2, ..., n}, ? players’ strategy spaces S1 S2 ... Sn and ? their payoff functions u1 u2 ... un where ui : S1 × S2 × ...× Sn→R.

博弈论讲义

Normal-form representation: 2-player game
? Bi-matrix representation ? 2 players: Player 1 and Player 2 ? Each player has a finite number of strategies ? Example:

S1={s11, s12, s13} S2={s21, s22}
Player 2 s21 s11 u1(s11,s21), u2(s11,s21) u1(s12,s21), u2(s12,s21) u1(s13,s21), u2(s13,s21)
博弈论讲义

s22 u1(s11,s22), u2(s11,s22) u1(s12,s22), u2(s12,s22) u1(s13,s22), u2(s13,s22)

Player 1 s12 s13

Classic example: Prisoners’ Dilemma: normal-form representation
? Set of players: ? Sets of strategies: ? Payoff functions:

{Prisoner 1, Prisoner 2} S1 = S2 = {Mum, Confess}

u1(M, M)=-1, u1(M, C)=-9, u1(C, M)=0, u1(C, C)=-6; u2(M, M)=-1, u2(M, C)=0, u2(C, M)=-9, u2(C, C)=-6
Players Strategies
Mum

Prisoner 2 Mum Confess

-1 , -1 0 , -9

-9 ,

0

Prisoner 1
Confess

-6 , -6

Payoffs
博弈论讲义

Example: The battle of the sexes
Pat Opera Opera Chris Prize Fight Prize Fight

2 ,

1

0 ,

0

0 ,

0

1 ,

2

? Normal (or strategic) form representation: ? Set of players: { Chris, Pat } (={Player 1, Player 2}) ? Sets of strategies: S1 = S2 = { Opera, Prize Fight} ? Payoff functions: u1(O, O)=2, u1(O, F)=0, u1(F, O)=0, u1(F, O)=1; u2(O, O)=1, u2(O, F)=0, u2(F, O)=0, u2(F, F)=2
博弈论讲义

Example: Matching pennies
Player 2 Head Head Player 1 Tail Tail

-1 ,

1

1 , -1 -1 , 1

1 , -1

? Normal (or strategic) form representation: ? Set of players: {Player 1, Player 2} ? Sets of strategies: S1 = S2 = { Head, Tail } ? Payoff functions: u1(H, H)=-

1, u1(H, T)=1, u1(T, H)=1, u1(H, T)=-1; u2(H, H)=1, u2(H, T)=-1, u2(T, H)=-1, u2(T, T)=1
博弈论讲义

Example: Tourists & Natives
? Only two bars (bar 1, bar 2) in a city ? Can charge price of $2, $4, or $5 ? 6000 tourists pick a bar randomly ? 4000 natives select the lowest price bar ? Example 1: Both charge $2 ? each gets 5,000 customers and $10,000 ? Example 2: Bar 1 charges $4, Bar 2 charges $5 ? Bar 1 gets 3000+4000=7,000 customers and $28,000 ? Bar 2 gets 3000 customers and $15,000
博弈论讲义

Example: Cournot model of duopoly
? A product is produced by only two firms: firm 1 and

firm 2. The quantities are denoted by q1 and q2, respectively. Each firm chooses the quantity without knowing the other firm has chosen. ? The market price is P(Q)=a-Q, where Q=q1+q2. ? The cost to firm i of producing quantity qi is Ci(qi)=cqi.
The normal-form representation:
?
? ?

Set of players: { Firm 1, Firm 2} Sets of strategies: S1=[0, +∞), S2=[0, +∞) Payoff functions: u1(q1, q2)=q1(a-(q1+q2)-c), u2(q1, q2)=q2(a-(q1+q2)-c)
博弈论讲义

One More Example
? Each of n players selects a number between 0 and

100 simultaneously. Let xi denote the number selected by player i. ? Let y denote the average of these numbers ? Player i’s payoff = xi – 3y/5
? The normal-form representation:

博弈论讲义

Solving Prisoners’ Dilemma
? Confess always does better whatever the other

player chooses ? Dominated strategy
?

There exists another strategy which always does better regardless of other players’ choices
Prisoner 2 Mum Confess

Players Strategies
Mum

-1 , -1 0 , -9

-9 ,

0

Prisoner 1
Confess

-6 , -6

Payoffs
博弈论讲义

Definition: strictly dominated strategy
In the normal-form game {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, let si', si" ? Si be feasible strategies for player i. Strategy si' is strictly dominated by strategy si" if si” is strictly ui(s1, s2, ... si-1, si', si+1, ..., sn) better than si’ < ui(s1, s2, ... si-1, si", si+1, ..., sn) for all s1? S1, s2? S2, ..., si-1?Si-1, si+1? Si+1, ..., sn? Sn.
regardless of other players’ choices Mum Prisoner 1 Confess Prisoner 2 Mum Confess

-1 , -1 0 , -9
博弈论讲义

-9 ,

0

-6 , -6

Summary
? Static (or simultaneous-move) games of complete

information ? Normal-form or strategic-form representation
? Next time ? Dominated strategies ? Iterated elimination of strictly dominated strategies ? Nash equilibrium
? Reading lists ? Sec 1.1.A and1.1.B of Gibbons and Sec 2.1-2.5, 2.9.1 and 2.9.2 of Osborne
博弈论讲义



  本文关键词：博弈论，，由笔耕文化传播整理发布。