Agent-based Systems
Paolo Turrini
www.dcs.warwick.ac.uk/~pturrini R p.turrini@warwick.ac.uk
More Solution Concepts thinking about thinking about
Paolo Turrini More solution concepts Agent-based Systems
Plan for Today
Pure and mixed Nash equilibria are examples for solution concepts: formal models to predict what might be the outcome of a game.
Today we are going to see some more such solution concepts:
equilibrium in dominant strategies: do what’s definitely good elimination of dominated strategies: don’t do what’s definitely bad correlated equilibrium: follow some external recommendation
For each of them, we are going to see some intuitive motivation, then a formal definition, and then an example for a relevant technical result.
Most of this (and more) is also covered in Chapter 3 of the Essentials.
K. Leyton-Brown and Y. Shoham.
Essentials of Game Theory: A Concise, Multidisciplinary Introduction
Claypool Publishers, 2008. Chapter 3.
Paolo Turrini More solution concepts Agent-based Systems
Example: Prisoner’s Dilemma Again
Let’s have look at it once more:
C
D
Notice DD is a Nash Equilibrium, but there is more…
Discussion: Is this true for all pure strategy Nash Equilibria in all games?
CD
−10 −10
0
−25
−25 0
−20 −20
Paolo Turrini More solution concepts Agent-based Systems
Dominant Strategies
Have we maybe missed the most obvious solution concept? . . .
You should play the action ai⋆ that gives you a better payoff than any other action ai′,
whatever the others do (such as playing s−i):
ui(a⋆i ,s−i) > ui(ai′,s−i) for all ai′ ∈ Ai and all s−i ∈ S−i
Action ai⋆ is called a strictly dominant strategy for player i.
Profile a⋆ ∈ A is called an equilibrium in strictly dominant strategies if, for every
player i ∈ N, action ai⋆ is a strictly dominant strategy.
Downside: This does not always exist (in fact, it usually does not!).
Remark: Equilibria don’t change if we define this for mixed strategies. If some best strategy exists, then some pure strategy is (also) best.
Paolo Turrini More solution concepts Agent-based Systems
Equilibria and Dominant Strategies
CDLRLR
CTT
DBB
Exercise: Is there an equilibrium in strictly dominant strategies?
−10 −10
0
−25
−25 0
−20 −20
0
1
0
0
1
0
1
1
0
0
1
0
1
0
100
1
Paolo Turrini More solution concepts Agent-based Systems
Dominant Strategies and Nash Equilibria
Exercise:
Show that an equilibrium in strictly dominant strategies is also a pure Nash equilibrium.
Paolo Turrini More solution concepts Agent-based Systems
Elimination of Dominated Strategies
Action ai is strictly dominated by a strategy s ⋆ if, for all s −i ∈ S −i : i
ui(s⋆,s−i) > ui(ai,s−i) i
Then, if we assume i is rational, action ai can be eliminated. This induces a solution concept:
all mixed-strategy profiles of the reduced game that survive iterated elimination of strictly dominated strategies (IESDS)
Simple example (where the dominanting strategies happen to be pure): LRR
TT BBB
4
4
6
1
1
6
2
2
6
1
2
2
R
2
2
Paolo Turrini More solution concepts
Agent-based Systems
Order Independence of IESDS
SupposeAi ∩Aj ={}. ThenwecanthinkofthereducedgameGt aftert eliminations simply as the subset of A1 ∪ · · · ∪ An that survived.
IESDS says: players will actually play G∞. Is this well defined? Yes!
Theorem (Gilboa et al., 1990)
Any order of eliminating strictly dominated strategies leads to the same reduced game.
Paolo Turrini More solution concepts Agent-based Systems
Proof
Proof: Write G G′ if game G can be reduced to G′ by eliminating one action. We are done if we can show that ∗ (trans. closure) is Church-Rosser. So need to show that is C-R.
• •◦ •◦◦
•◦◦ •◦
•
bj ′′ bj′′ ⋆
′bj ′′′ ′′′
ai ′
Enoughtoshow:ifGG andGG,thenG G forsomeG .
This is immediate: G G means uj(sj ,s−j) > uj(bj,s−j) for all s−j. Take s−j = (ai′,s−ij) with ai′ ̸= ai: uj(sj⋆,ai′,s−ij) > uj(bj,ai′,s−ij).
Remark: This only works due to finiteness of A (induction!).
I. Gilboa, E. Kalai, and E. Zemel.
On the Order of Eliminating Dominated Strategies.
Operations Research Letters, 9(2):85–89, 1990.
Paolo Turrini More solution concepts Agent-based Systems
Let’s Play: Numbers Game (Again!)
Let’s play again:
Every player submits a (rational) number between 0 and 100. We then com- pute the average (arithmetic mean) of all the numbers submitted and multiply that number with 2/3. Whoever got closest to this latter number wins the game.
Paolo Turrini More solution concepts Agent-based Systems
Analysis
IESDS results in a reduced game where everyone’s only action is 0. So, we happen to find the only pure Nash equilibrium this way.
IESDS works on the assumption of common knowledge of rationality. In the Numbers Game, we have seen:
Playing 0 usually is not a good strategy in practice, so assuming common knowledge of rationality must be unjustified.
When we played the second time, the winning number got closer to 0. So by discussing the game, both your own rationality and your confidence in the rationality of others seem to have increased.
Paolo Turrini More solution concepts Agent-based Systems
Even More Solution Concepts
There are several other solution concepts in the literature. Examples:
Iterated elimination of weakly dominated strategies: eliminate ai in case there
is a strategy s⋆ such that ui(s⋆,s−i) ui(ai,s−i) for all s−i ∈ S−i and this ii
inequality is strict in at least one case.
Iterated elimination of very weakly dominated strategies: eliminate ai in case
there is a strategy s⋆ such that ui(s⋆,s−i) ui(ai,s−i) for all s−i ∈ S−i. ii
ε-Nash equilibrium: no player can gain more than ε in utility by unilaterally deviating from her assigned strategy.
Exercise: How does the standard definition of NE relate to this?
K. Leyton-Brown and Y. Shoham.
Essentials of Game Theory: A Concise, Multidisciplinary Introduction. . Morgan & Claypool Publishers, 2008. Chapter 3.
Paolo Turrini More solution concepts Agent-based Systems
Summary
We have reviewed several solution concepts for normal-form games. equilibrium in dominant strategies: great if it exists
IESDS: iterated elimination of strictly dominated strategies
What next? Extensive games
Paolo Turrini More solution concepts Agent-based Systems