Agent-based Systems
Paolo Turrini
www.dcs.warwick.ac.uk/~pturrini R p.turrini@warwick.ac.uk
Today
We are going to look at the very basics of game theory, in particular: Pure and mixed strategies
Nash equilibria
We are also going to play a game.
K. Leyton-Brown and Y. Shoham
Essentials of Game Theory: A Concise, Multidisciplinary Introduction
Morgan & Claypool Publishers, 2008. Chapters 1 & 2
Paolo Turrini Game Theory: Introduction Agent-based Systems
Why?
Game theory entered AI when it became clear that we can use it to study interaction between the software agents in a multiagent system.
Nowadays, the study of “economic paradigms” is all over AI.
The influential One Hundred Year Study on AI (2016) singles out the following eleven
“hot topics” in AI:
large-scale machine learning | deep learning | reinforcement learning | robotics | computer vision | natural language processing | collaborative systems | crowdsourcing and human computation | algorithmic game theory and computational social choice | internet of things | neuromorphic computing
P.Stone
Artificial Intelligence and Life in 2030.
One Hundred Year Study on Artificial Intelligence, 2016.
Paolo Turrini Game Theory: Introduction Agent-based Systems
The Prisoner’s Dilemma
Two hardened criminals, Rowena and Colin, got caught by police and are being interrogated in separate cells. The police only has evidence for some of their minor crimes. Each is facing this dilemma:
If we cooperate (C) and don’t talk, then we each get 10 years for the minor crimes.
CD
−10 −10
0
−25
−25 0
−20 −20
If I cooperate but my partner defects (D) and talks, then I get 25 years.
C
D
If my partner cooperates but I defect, then I go free (as crown witness).
If we both defect, then we share the blame and get 20 years each.
What would you do? Why?
Paolo Turrini Game Theory: Introduction Agent-based Systems
Strategic Games in Normal Form
A normal-form game is a tuple ⟨N, A, u⟩, where
N = {1,…,n} is a finite set of players (or agents);
A=A1×···×An isafinitesetofactionprofilesa=(a1,…,an),withAi being the set of actions available to player i; and
u = (u1,…,un) is a profile of utility functions ui : A → R.
Every player i chooses an action, say, ai , giving rise to the profile a. Actions are played
simultaneously. Player i then receives payoff ui (a).
Remark: We use boldface italics to denote vectors (i.e., profiles) and Cartesian products
(i.e., sets of profiles).
Paolo Turrini Game Theory: Introduction Agent-based Systems
Nash Equilibria in Pure Strategies
Later we will allow players to randomise over actions. But today we restrict attention to pure strategies: strategy = action.
Notation: (ai′, a−i ) is short for (a1, . . . , ai−1, ai′, ai+1, . . . , an).
John F. Nash Jr. (1928–2015)
We say that ai⋆ ∈ Ai is a best response for player i to the (partial) action profile a−i ,
if ui(ai⋆,a−i) ui(ai′,a−i) for all ai′ ∈ Ai.
We say that action profile a = (a1,…,an) is
a pure Nash equilibrium, if ai is a best response to a−i for every agent i ∈ N.
Thus, pure Nash equilibria are stable outcomes: no player has an incentive to unilaterally deviate from her assigned strategy.
Paolo Turrini Game Theory: Introduction Agent-based Systems
Exercise: How Many Pure Nash Equilibria?
LRLRLR
TTT
BBB
2
2
1
2
3
1
2
3
2
2
2
2
2
2
2
2
2
1
1
2
1
2
2
1
Paolo Turrini Game Theory: Introduction Agent-based Systems
Zero-Sum Games
A zero-sum game is a two-player normal-form game ⟨N, A, u⟩ with u1(a) + u2(a) = 0 for all action profiles a ∈ A. Example:
What are the pure NE of this game? Intuitively, how should you play?
Paolo Turrini Game Theory: Introduction Agent-based Systems
Mixed Strategies
So far, the space of strategies available to player i has simply been her set of actions Ai (pure strategy = action).
We now generalise and allow player i to play any action in Ai with a certain probability. For any finite set X, let
Π(X)={p:X →[0,1]|p(x)=1} x∈X
be the set of all probability distributions over X.
A mixed strategy si for player i is a probability distribution in Π(Ai ).
The set of all her mixed strategies is Si = Π(Ai ).
A mixed-strategy profile s = (s1,…,sn) is an element of S1 × ··· × Sn.
Paolo Turrini Game Theory: Introduction Agent-based Systems
Mixed Strategies and Expected Utility
The expected utility of player i for the mixed-strategy profile s is:
ui(s)= ui(a)·sj(aj)
a∈A j∈N
The support of strategy si is the set of actions {ai ∈ Ai | si (ai ) > 0}. A mixed strategy si is pure iff its support is a singleton.
A mixed strategy si is truly mixed if it is not pure.
A mixed strategy si is fully mixed if its support is the full set Ai .
Paolo Turrini Game Theory: Introduction Agent-based Systems
Example: Battle of the Sexes
Traditionally minded Rowena and Colin are planning a social activity. Worst of all would be not to agree on a joint activity; but if they do manage, Colin prefers auto racing and Rowena really prefers ballet.
AB
4
2
0
0
0
0
3
8
A
B
Suppose Rowena chooses to go to the ballet with 75% probability, while Colin chooses to go to the races with certainty (pure strategy):
s1 =(1,3) s2 =(1,0) 44
Thus: u1(s)=2·(1 ·1)+0·(1 ·0)+0·(3 ·1)+8·(3 ·0)= 1 44442
Paolo Turrini Game Theory: Introduction Agent-based Systems
Mixed Nash Equilibria
Consider a game ⟨N, A, u⟩ with associated (mixed) strategies si ∈ Si .
We say that strategy s⋆ ∈ Si is a best response for player i to the (partial)
strategy profile s−i if ui(s⋆,s−i) ui(s′,s−i) for all s′ ∈ Si. iii
We say that profile s = (s1, . . . , sn) is a mixed Nash equilibrium, if si is a best response to s−i for every player i ∈ N.
Thus: no player has an incentive to unilaterally change her strategy. Remark: Note how this definition mirrors that of pure Nash equilibria.
Theorem (Nash, 1951)
Every (finite) normal-form game has at least one (truly mixed or pure) Nash equilibrium.
i
Paolo Turrini Game Theory: Introduction Agent-based Systems
Let’s Play: Numbers Game
Let’s play the following game:
Every player submits a (rational) number between 0 and 100. We then com- pute the average of all the numbers submitted and multiply that average with 2/3. Whoever got closest to this latter number wins the game.
Paolo Turrini Game Theory: Introduction Agent-based Systems
Summary
Game Theory: Decision Theory with many agents
Equilibria, in particular Nash equilibria, in pure and mixed strategies.
Coming next: Extensive Games.
Paolo Turrini Game Theory: Introduction Agent-based Systems