Normal form games
( /Cartoon Network)
c -Trenn, King’s College London 2
Normal form games
An n-person, finite, normal form game is a tuple pN, A, uq, where ‚ N is a finite set of players.
‚ A“A1 ˆ…ˆAn whereAi isafinitesetofactionsavailabletoi. ‚ Each a “ pa1,…,anq P A is an action profile.
u “ pu1,…,unq where ui : A fiÑ < is a real-valued utility function for i. Naturally represented by an n-dimensional matrix
c -Trenn, King’s College London 3
Strategies
We analyze games in terms of strategies, that is what agents decide to do.
‚ Combinedwithwhattheotheragent(s)do(es)thisjointlydeterminesthepayoff.
An agent’s strategy set is its set of available choices. Can just be the set of actions — pure strategies.
We need more than just pure strategies in many cases.
‚ Willdiscussthislater
c -Trenn, King’s College London 4
Payoff matrix
Here is the payoff matrix from the “choose which side” (of the road) game:
j
left right left
i
right
We can classify games by the form of the payoff matrix.
1 1
0 0
0 0
1 1
c -Trenn, King’s College London 5
Common payoff games
“Choose which side” game
left right left
1 1
0 0
0 0
1 1
right Also called the coordination game
Anygamewithuipaq“ujpaqforallaPAi ˆAj isa common payoff game.
c -Trenn, King’s College London 6
Common payoff games
The misanthropes’ (un)coordination game:
left
right
0 0
1 1
1 1
0 0
left right
Here we try to avoid each other.
c -Trenn, King’s College London
7
Misanthrope
http://www.thebadchemicals.com
c -Trenn, King’s College London 8
Constant sum games
ion:
Anygamewithupaq`u paq“cforallaPA ˆA isaconstantsumgame. ij ifij
Matching pennies
heads tails
1
heads -1
1 -1
tails 1 -1 -1 1
c -Trenn, King’s College London 9
Zero-sum games
A particular category of constant sum games are zero-sum games. Where utilities sum to zero:
u1paq`ujpaq“0 forallaPAi ˆAj
c -Trenn, King’s College London
10
Zero-sum games
Where preferences of agents are diametrically opposed we have strictly competitive scenarios.
(Library of Congress)
Zero sum implies strictly competitive.
c -Trenn, King’s College London 11
Zero-sum games
Zero-sum encounters in real life are very rare . . . but people tend to act in many scenarios as if they were zero-sum.
Most encounters have some room in the set of outcomes for agents to find (somewhat) mutually beneficial outcomes.
c -Trenn, King’s College London 12
Zero-sum games
Rock, paper, scissors:
(Google/Droga5)
is another constant/zero sum game. Game in two senses.
c -Trenn, King’s College London 13
The rules
Rules for “rock, paper, scissors”.
(eyemotive.com)
c -Trenn, King’s College London 14
Rock, paper scissors, lizard, Spock
(DMacks/Nojhan/Wikipedia)
http://www.youtube.com/watch?v=x5Q6-wMx-K8
Scissors cuts paper, paper covers rock, rock crushes lizard, lizard poisons Spock, Spock
smashes scissors, scissors decapitates lizard, lizard eats paper, paper disproves Spock, Spock
vaporizes rock, and as it always has, rock crushes scissors.
c -Trenn, King’s College London 15
Rock, paper, scissors
j
rock
paper
scissors
0 0
1 -1
-1 1
-1 1
0 0
1 -1
1 -1
-1 1
0 0
i
rock paper scissors
c -Trenn, King’s College London
16