Competition between agents
(groups.msn.com/artofjimlee)
c -Trenn, King’s College London 2
Multi-party decision making
(xkcd.com/1890/)
c -Trenn, King’s College London 3
In the real world
(U.S. Army Military History Institute)
Strategic analysis.
c -Trenn, King’s College London 4
In the real world
( /citylimits.org)
School admissions
c -Trenn, King’s College London 5
In the real world
(froedtert.com)
Kidney exchange
Longest chain involved 28 donors and recipients.
c -Trenn, King’s College London 6
The grade game
( ’s Report Card, US National Archives)
c -Trenn, King’s College London 7
The grade game
Imagine in this module we assign grades as follows
You are randomly paired with a partner (you do not know who!)
You have to write X or Y on the piece of paper
You will get a grade based on the following rules:
If both you and your partner write X, then you both get a B
If you write X and your partner writes Y then you get D and your partner gets A If you write Y and your partner writes X then you get A and your partner gets D
If both you and your partner write Y then you both get C
PCD
” 3¥27
(The Grade Game, )
EE
k
c -Trenn, King’s College London
8
The grade game
What would you do?
What you get depends also on the choice of your partner. This is the blueprint of strategic interaction.
There is a poll on KEATS to find out …
c -Trenn, King’s College London 9
Choose the side
Which side of the road to drive on?
(haulagetoday.com)
c -Trenn, King’s College London 10
Choose the side
Which side of the road to drive on?
(businessinsider.com)
c -Trenn, King’s College London 11
Choose the side
Which side of the road to drive on?
Any fule kno that.
( / )
c -Trenn, King’s College London 12
Choose the side
Which side of the road to drive on?
Same side as everyone else
(berkshireeagle.com)
c -Trenn, King’s College London 13
Choose the side
How do you choose when you don’t know what “everyone else” is doing.
c -Trenn, King’s College London 14
Game theory
Game theory is a framework for analysing interactions between a set of agents. Abstract specification of interactions.
Describes each agent’s preferences in terms of their utility.
‚ Assumeagentswanttomaximiseutility.
Give us a range of solution strategies with which we can make some predictions
about how agents will/should interact.
c -Trenn, King’s College London 15
Payoff Matrices
We can characterise the “choose side” scenario in a payoff matrix j
left right left
i
right
we have two agents, each player picking a (pure) strategy
Agent i is the row player
gets the lower reward in a cell.
Agent j is the column player gets the upper reward in a cell.
1 1
0 0
0 0
1 1
c -Trenn, King’s College London 16
Payoff Matrices
We can characterise the grade game scenario in a payoff matrix
j
YX Y
i
X
Payoffs are the US grade points that correspond to the problem statement. From the game earlier: Grade A is 4, Grade B is 3 etc.
2 2
1 4
4 1
3 3
c -Trenn, King’s College London 17
Outcomes
An outcome is what we get when we combine the actions of all the players. An outcome corresponds to an element of the payoff matrix
j
left right up
i
down
We identify outcomes by the moves the players make:
pwhat i plays, what j playsq Thus pup, rightq identifies the outcome in which
i plays up and j plays right
c -Trenn, King’s College London 18
1 1
0 0
0 0
1 1
Payoff Matrices
Actually there are two matrices here, one (call it A) that specifies the payoff to i and another B that specifies the payoff to j.
jA
Sometimes we’ll write the payoff matrix as pA, Bq in recognition of this.
̈1 0 ̨
A “ ̋3 1‚is the payoff matrix for i from the following table
‘
“i l
left right : up 0
1
o :2
0
oooh
i0
down
Note that ai1,j1 is the payoff if i picks action i1 and j picks action j1
1
O
O
c -Trenn, King’s College London
19
3
1