Game Theory

Mohammad Hossein Manshaei

manshaei@gmail.com
1402
Contents
1. Formal Definitions/Notations
2. Strict versus Weak Dominance
3. Iterative Deletion of Dominated Strategy
4. Median Voter Theorem
5. Model Simplification for Engineering
Application: Examples

2
 Pick a Number Game
Without showing your neighbor what you’re doing, write down an
integer number between 1 and 100. I will calculate the average
number chosen in the class.The winner in this game is the person
whose number is closest to two-thirds (2/3) of the average in the
class.The winner will win 10 $ minus the difference in cents
between her choice and that two-thirds of the average.

Example: 3 students 1-10: 3

Numbers: 25, 5, 60 11-20: 4
Total: 90, Average: 30, 2/3*average: 20 21-30: 12
31-40: 13
41-50: 6
25 wins: 10 $ –.01 * 5 = 9.95 $ 51-60: 1
61-70: 0
71-80: 1
81-90: ?
91-100: 0 3
 Notations
Notation Pick a Number Game
Players i, j, … You all
Strategy si: a particular strategy of player i S4=12, s8=22

s-i: the strategy of everybody else

except player i

Strategy Set Si: the set of possible strategies of {1, 2, …, 100}

player i

Strategy s: a particular play of the game The collection of your pieces of

Profile “strategy profile” paper
(vector, or list)

Payoffs ui(s1,…, si,…, sN) = ui(s) $10 - .01*Δ if you win

ui(s) =
0 otherwise

4
 Assumptions
• We assume all the ingredients of the game to be
known
– Everybody knows the possible strategies everyone else
could choose
– Everybody knows everyone else’s payoffs

Complete Information Game

• This is not very realistic, but we start from this class
of games

5
 Classification of games
Non-cooperative Cooperative

Static Dynamic (repeated)

Strategic-form Extensive-form

Perfect information Imperfect information

Complete information Incomplete information

Perfect information: each player can observe the action of each other player.

Complete information: each player knows the identity of other players and,
for each of them, the payoff resulting of each strategy.
6
 Example
Player 2
L C R
T 5, -1 11, 3 0,0
Player 1
B 6, 4 0, 2 2,0

Players 1, 2

Strategy sets S1={T,B} S2={L,C,R}

Payoffs U1(T,C) = 11 U2(T,C) = 3

NOTE: This game is not symmetric

7
 Game Analysis
• How is the game going to be played?
• Does player 1 have a dominated strategy?
• Does player 2 have a dominated strategy?

• For a strategy to be dominated, we need

another strategy for the same player that does
always better (in terms of payoffs)

8
Contents
1. Formal Definitions/Notations
2. Strict versus Weak Dominance
3. Iterative Deletion of Dominated Strategy
4. Median Voter Theorem
5. Model Simplification for Engineering
Application: Examples

9
Definition: Strict dominance
We say player i’s strategy si’ is strictly dominated by
player i’s strategy si if:

ui(si, s-i) > ui(si’, s-i) for all s-i

No matter what other people do, by choosing si instead of

si’, player i will always obtain a higher payoff.

10
 “Hannibal” game
• An invader is thinking about invading a country, and there are 2 ways
through which he can lead his army.
• You are the defender of this country and you have to decide which of
these ways you choose to defend: you can only defend one of these
routes.
• One route is a hard pass: if the invader chooses this route he will lose
one battalion of his army (over the mountains).
• If the invader meets your army, whatever route he chooses, he will lose
a battalion

11
 “Hannibal” game
Attacker
e h
E 1, 1 1, 1
Defender H 0, 2 2, 0

Strategies
1. e, E = Easy Path ;
2. h,H = Hard Path

Payoffs:
1. Attacker: Number of battalions in your country
2. Defender: Number of attacker’s lost battalions

12
 “Hannibal” game
• You’re the defender: what would you do?
• Is it true that defending the easy route dominates defending
the hard one?

• You’re the attacker: what would you do?

• Now, what the defender should do, if he would put himself in

the attacker shoes?
13
 Definition: Weak dominance
We say player i’s strategy si’ is weakly dominated by player
i’s strategy si if:

ui(si, s-i) ≥ ui(si’, s-i) for all s-i

ui(si, s-i) > ui(si’, s-i) for some s-i

No matter what other people do, by choosing si instead of si’,

player i will always do at least as well, and in some cases
she does strictly better.

It turns out that, historically, Hannibal chose H!

14
Contents
1. Formal Definitions/Notations
2. Strict versus Weak Dominance
3. Iterative Deletion of Dominated Strategy
4. Median Voter Theorem
5. Model Simplification for Engineering
Application: Examples

15
 Pick a Number Game
Without showing your neighbor what you’re doing, write down an
integer number between 1 and 100. I will calculate the average
number chosen in the class.The winner in this game is the person
whose number is closest to two-thirds (2/3) of the average in the
class.The winner will win 10 $ minus the difference in cents
between her choice and that two-thirds of the average.

Example: 3 students 1-10: 3

11-20: 4
Numbers: 25, 5, 60 21-30: 12
Total: 90, Average: 30, 2/3*average: 20 31-40: 14
41-50: 6
25 wins: 10 $ –.01 * 5 = 9.95 $ 51-60: 1
61-70: 0
71-80: 1
81-90: 0
91-100: 0
16
 What did you do?
• What we know:
– Do not choose a strictly dominated strategy
– Also, do not choose a weakly dominated strategy
– You should put yourself in others’ shoes, try to
figure out what they are going to play, and respond
appropriately

17
 First Clue!
• A possible assumption:
– People chose numbers uniformly at random
➔The average is 50
➔2/3 * average = 33.3

• What’s wrong with this reasoning?

IUT students are not rand()!

18
 Dominated Strategy?
• Let’s try to find out whether there are dominated
strategies

• If everyone would chose 100, then the winning number

would be 67

➔ Numbers bigger than 67 are weakly dominated by 67

➔ Rationality tells not to choose numbers bigger than 67

19
 New Game!
• So now we’ve eliminated dominated strategies, it’s like a
new game played over the set [1, …, 67]
• Once you figured out that nobody is going to choose a
number above 67, the conclusion is

Also strategies above 45 are ruled out

• This means:
1. Rationality
2. Knowledge that others are rational as well

• Note:
They are weakly dominated, only once we delete 68-100
20
 Iterative Deletion
• Eventually, we can show that also strategies
above 30 are weakly dominated, once we
delete previously dominated strategies

• We can go on with this line of reasoning and

end up with the conclusion that:

• 1 was the winning strategy!

21
 Common Knowledge
• Common knowledge: you know that
others know that others know … and so on
that rationality is underlying all players’ choices

22
 Theory vs. Practice
• Q: Why was it that 1 wasn’t the winning
answer?

• A: We need a strong assumption, that is that

all players are rational and they know that
everybody else’s rational as well

23
 Common Knowledge
Rationality

Rationality and Knowledge of Other’s Rationality

Rationality, Knowledge of Other’s Rationality, and Knowledge of Knowledge of Rationality (know

that you know that I know …. )

Rationality, Knowledge of Other’s Rationality, Knowledge of Knowledge of Rationality, and

Knowledge of knowledge of knowledge of Rationality
.
.
.
.

24
 How did you play?
– 40 Players
–Average number was: 30.85
–Winning number is closest to the
2/3 X Average = 20.56
– Winner= 21: No one
–Then 20: only one person

25
 Summary
• We’ve explored a bit the idea of deleting
dominated strategies
– Look at a game
– Figure out which strategies are dominated
– Delete them
– Look at the game again
– Look at which strategies are dominated now
– … and so on …

26
 Summary
• Iterative deletion of dominated
strategies seems a powerful idea, but it’s
also dangerous if you take it literally
• In some games, iterative deletion converges to
a single choice, in others it may not (we’ll see
shortly an example)
• HINT: try to identify all dominated strategies
at once before you delete, this may save you
some rounds…

27
 Let us play
the same Game, again!

28
Contents
1. Formal Definitions/Notations
2. Strict versus Weak Dominance
3. Iterative Deletion of Dominated Strategy
4. Median Voter Theorem
5. Model Simplification for Engineering
Application: Examples

29
 Election Game Model
• 2 candidates
• Choosing their political positions on a
spectrum
• Assume the spectrum has 10 positions

1 2 3 4 5 6 7 8 9 10
LEFT WING RIGHT WING

30
 Election Game Model
• There are 10% of the voters at each of these
positions:
– Voters are uniformly distributed
• Voters will eventually vote for the closest
candidate (i.e., for the candidate whose
position is closest to their own)
• We break ties by splitting votes equally

Votes: 10% 10% 10% 10% 10% 10% 10% 10% 10% 10%

1 2 3 4 5 6 7 8 9 10
LEFT WING RIGHT WING
31
 Election Game Strategies
• We assume payoffs follow the idea that the
candidates aim to maximize their share of
vote (Win the Election)

• Are there any dominated strategies here?

32
 Election Game
Analysis of Dominated Strategy
• Is position 1 dominated? If so, what dominates it? Let’s test, e.g.
how is 1 vs. 2

s-i 1’s Payoff for si=1 1’s Payoff for si=2

Vs. 1 u1(1,1) = 50 % < u1(2,1) = 90%
Vs. 2 u1(1,2) = 10 % < u1(2,2) = 50%
Vs. 3 u1(1,3) = 15 % < u1(2,3) = 20%
Vs. 4 u1(1,4) = 20 % < u1(2,4) = 25%
… … … ….

• Do you see a pattern coming up here?

➔We conclude that 2 strictly dominates 1
• We’re not saying that 2 wins over 1
33
 Election Game
Analysis of Dominated Strategy
• Using a similar argument, we have that:
➔9 strictly dominates 10

• Is there anything else dominated here?

• What about 2 being dominated by 3?

Vs. 1 U1(2,1) = 90 % > U1(3,1) = 85%

34
 Election Game
Analysis of Dominated Strategy
• Even though 2 is not a dominated strategy, if
we do the process of iterative deletion and
delete dominated strategies (1 and 9)…
• Would 3 dominate 2?
Vs. 2 u1(2,2) = 50 % < u1(3,2) = 80%
Vs. 3 u1(2,3) = 20 % < u1(3,3) = 50%
Vs. 4 u1(2,4) = 25 % < u1(3,4) = 30%
Vs. 5 U1(2,5) = 30 % < u1(3,5) = 35%
… … … ….

35
 Election Game
Analysis of Dominated Strategy
• Strategies 2 and 8 are not dominated
➔They are dominated once we realize that
strategies 1 and 10 won’t be chosen

• If we continued the exercise, where would we

get?

36
 Election Game Result
• It turns out that 5 and 6 are not dominated
• What’s the prediction that game theory suggests
here?

➔ Candidates will be squeezed towards the center,

they’re going to choose positions very close to each
other

In political science this is called the

Median Voter Theorem
37
Election Game: Similar Examples

• The same model has applications in economics as

well (and computer science): product
placement
• Example: Placing Gas Stations (abroad)
or banks (here!)
– Spread themselves evenly out over the town
– On every road
• As we all know, this doesn’t happen:
All gas stations tend to crowd into the same
corners, all the fast foods crowd as well, … you
name it

38
Contents
1. Formal Definitions/Notations
2. Strict versus Weak Dominance
3. Iterative Deletion of Dominated Strategy
4. Median Voter Theorem
5. Model Simplification for Engineering
Application: Examples

39
 Model Simplification
• We have been using a model of a real-world
situation, and tried to predict the outcome
using game theory

• What is missing? Is there anything wrong with

the model?

40
Simplification in Median Voter
• Voters are not evenly distributed
• Some people do not vote
• There may be more than 2 candidates
• There may be higher “dimensions” to the
problem

41
 Model Simplification
• So if we’re missing so many things, our model is
useless, and in general modeling (as an abstraction
effort) is useless!!

• No: first, analyze a problem with simplifying

assumptions, then relax them and see what happens

• E.g.: would a different voters distribution change the

result?

42
 Model Simplification:
Engineering Approach
• We basically make lots of abstractions in make
game theoretical models for our engineering
problems
• Not a bad idea to start with abstraction, but
you must be careful about what you design

43
 George Edward Pelham Box
(1919-2013)
• Remember that all models are wrong; the
practical question is how wrong do they have
to be to not be useful.
• Essentially, all models are wrong, but
some are useful.

44
The Joint Packet Forwarding Game
? ?
Source Blue Green Dest

Green
• Reward for packet reaching Blue Forward Drop
the destination: 1
• Cost of packet forwarding:
c (0 < c << 1)
Forward (1-c, 1-c) (-c, 0)
Drop (0, 0) (0, 0)

No strictly dominated strategies !

45
 Weak dominance
Weak dominance: strictly better strategy for at least one opponent strategy
Strategy si is weakly dominates strategy s’i if:

ui ( si , s− i ) ≥ ui ( si' , s− i ), ∀s− i ∈ S − i
with strict inequality for at least one s-i
? ?
Source Blue Green Dest

Green
Blue Forward Drop
Iterative weak dominance Forward (1-c, 1-c) (-c, 0)
BUT Drop (0, 0) (0, 0)
The result of the iterative weak dominance
is not unique in general !
46
 Weak Dominance in
Threshold Cryptography

S = f (0) is the secret, and each Si is calculated Each party should receive the other two secret
using a polynomial function shares to calculate the secret.

J. Halpern and V. Teague, ”Rational secret sharing and multiparty computation”

In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
47
 Weak Dominance in
Threshold Cryptography
• The parties are rational and that they cooperate if it is
in their interest to share a part of the secret (it
increases its payoff)
• Given the rationality assumption:
“Rational parties will not broadcast their shares”
• Not sending the share (Defect) is a weakly dominating
strategy in the game between the parties
• Results make sense if we consider that the parties have
common knowledge about the running time of the
protocol

48