Introduction to Game Theory
Dr Matthew Science University of Auckland
Interdisciplinarity & Modelling Frameworks
Copyright By PowCoder代写 加微信 powcoder
The dynamical systems tools you have learned about so far are applicable to the study of a broad range of things.
– physics, biology, neuroscience, chemistry, computer games and simulations, etc.
“Game Theory” is another broadly applicable modelling framework that can be applied when trying to understand diverse phenomena.
In this lecture we’ll look at some of the basics of game theory, setting the scene for future lectures on how computational methods can play an essential role.
Prisoner’s Dilemma
Imagine two criminal partners have been arrested. They are each interrogated in a different room (so cannot communicate with each other). They have two choices:
cooperate (with their partner) and not tell the police anything
defect (i.e. betray their partner) and tell the police everything
This is called a payoff matrix.
(both prisoners keep their mouths shut and are convicted, but only do a small amount of prison time)
(the defector goes free for ratting out their partner who gets a maximum sentence)
(the defector goes free for ratting out their partner who gets a maximum sentence)
(both criminals betray each other and the police can then convict them both)
Prisoner’s Dilemma
“defecting completely dominates cooperation; that is, no matter what one’s partner does, one’s own payoff is higher if one defects.”
“On the other hand, the highest total payoff is obtained when both parties cooperate […] the payoff to each party in that case is in fact higher than if both parties behave “rationally” and defect.”
This is called a payoff matrix.
(both prisoners keep their mouths shut and are convicted, but only do a small amount of prison time)
(the defector goes free for ratting out their partner who gets a maximum sentence)
(the defector goes free for ratting out their partner who gets a maximum sentence)
(both criminals betray each other and the police can then convict them both)
Chess, D. M. (1988). Simulating the evolution of behavior: the iterated prisoners’ dilemma problem. Complex systems, 2(6), 663-670.
cooperate (leave pasture alone)
defect (add cow to pasture)
cooperate (leave pasture alone)
(the value of the shared resource remains)
(the value of the shared resource is depleted by ε; the defector feeds their cow)
defect (add cow to pasture)
(the value of the shared resource is depleted by ε; the defector feeds their cow)
(the shared resource is destroyed)
The Tragedy
of the Commons
This game has been used to explore the dynamics of
cooperation.
It has also been used to think about sustainability and the idea of The Tragedy of the Commons, where a shared resource is destroyed because each involved individual (person or country) is selfishly incentivized to use it, resulting in its overuse.
ε is the cost of the consumption of the shared resource
these scores are not exactly the same as the previous, but have much in common
We can use models like this to think about climate change/pollution/CO2 emissions, etc.
– Common resource: our air and water
– Countries are incentivized to consume that resource, but in so doing destroy it
Or, at a smaller scale, over-fishing
– Common resource: fish stocks
– Individuals and/or fishing
companies are incentivized to fish, but in so doing destroy that resource
Models as tools for thinking
Models like this help us to get beyond a difficult to address desire “to all just get along” and can help us to develop productive scientifically supported answers to related questions like…
– Why don’t we all just get along?
– What does it take to avoid the tragedy of the commons?
– In what situations are people (or countries or animals, etc.) more likely to cooperate?
Underlying Assumptions
As I’ve said before, it is important to think about what the assumptions are underlying a model you are working on. What are some assumptions implicit in the Prisoner’s Dilemma?
– Only a single game played between players
– Decision to cooperate/defect is discrete (not spread
over time), with time to observe and/or interact with
other player, or change decision
– Both players are equally affected by shared
These assumptions allow us to build a model that is understandable, and where things can be proven (more in a moment), but they also limit the situations where we can rely upon the model to be predictive.
, A.; , P.; Manfredi, P. (2021) The Tragedy of the Commons as a Prisoner’s Dilemma. Its Relevance for Sustainability Games. Sustainability, 13, 8125. https://doi.org/10.3390/su13158125
cooperate (leave pasture alone)
defect (add cow to pasture)
cooperate (leave pasture alone)
(the value of the shared resource remains)
(the value of the shared resource is depleted by ε and the defector gets to feed their cow)
defect (add cow to pasture)
(the value of the shared resource is depleted by ε and the defector gets to feed their cow)
(the shared resource is destroyed)
Underlying Assumptions and Extensions Many of these assumptions can turn into extensions of the
model… What happens when I relax assumption X?
For instance, when thinking about climate change and
sustainability we might want to
● remove the symmetry of the game (the idea that both ‘players’ affect (and are affected equally by) the consumption of the common resource
● the idea that there are only two players
● the idea that the choice to cooperate or defect is
○ binary (i.e. a yes/no question) rather than a continuum of degree
○ a discrete event, rather than a choice that is made again and again (or continually) as time passes
Often, when relaxing these assumptions, the increased complexity demands a change in how the system is analyzed, and often a transition from mathematical, to computational models.
We’ll come back to this idea in a bit.
, A.; , P.; Manfredi, P. (2021) The Tragedy of the Commons as a Prisoner’s Dilemma. Its Relevance for Sustainability Games. Sustainability, 13, 8125. https://doi.org/10.3390/su13158125
How can you analyze these games?
Identify strategies and compare them…
“What would I do?” – good to start with, but not formal and not intellectually robust if just an intuition.
Proving what the best strategy is. Better! But the best strategy often depends upon what strategy the other player is using.
Identifying – sets of strategies for which no player would gain from changing their strategy.
Q. What are the in this game, “The Stag Hunt”?
hunt rabbit
(by cooperating both hunters can kill the larger animal and share its meat)
(the stag hunter cannot succeed on her own, the rabbit hunter gets the whole rabbit)
hunt rabbit
(the stag hunter cannot succeed on her own, the rabbit hunter gets the whole rabbit)
(the two hunters share the rabbit)
A1. both hunt stag A2. both hunt rabbit
Spaniel W. (2011) Game Theory 101: The Complete Textbook
Q. What are the in this game, “Car Intersection Game”?
(both cars go through the intersection and have an accident)
(green car goes through, blue car has to wait their turn)
(blue car goes through, green car has to wait their turn)
(both cars are stuck for a moment, as each is being so polite that no one goes until they figure it out)
A1. green goes / blue waits A2. blue goes / green waits
Spaniel W. (2011) Game Theory 101: The Complete Textbook
Pure vs. Mixed Strategies
So far, we have considered a given game being played only once, but games are often played again and again (e.g. the traffic intersection ‘game’)
This opens up the possibility of mixed strategies, meaning strategies that involve sometimes choosing one action and sometimes choosing another.
e.g. go 25% of the time randomly; wait the other 75% of the time
(both cars go through the intersection and have an accident)
(green car goes through, blue car has to wait their turn)
(blue car goes through, green car has to wait their turn)
(both cars are stuck for a moment, as each is being so polite that no one goes until they figure it out)
Mixed Strategies
The score of a mixed strategy against another strategy is its average score in a large number (infinite) number of competitions with that other strategy.
A 50/50 strategy in the traffic intersection game, playing against an “Always Go” strategy would receive a score of -5 half of the time and 0 the other half of the time. It’s average score against this strategy would thus be -2.5.
The Always Go strategy would receive -5 half of the time and 1 half of the time, for an average score of -2.
(both cars go through the intersection and have an accident)
(green car goes through, blue car has to wait their turn)
(blue car goes through, green car has to wait their turn)
(both cars are stuck for a moment, as each is being so polite that no one goes until they figure it out)
Mixed Strategies
When we considered only pure strategies, we identified two . What happens when we allow mixed strategies?
(Player A)
(both cars go through the intersection and have an accident)
(green car goes through, blue car has to wait their turn)
(blue car goes through, green car has to wait their turn)
(both cars are stuck for a moment, as each is being so polite that no one goes until they figure it out)
(Player b)
Questions for you to think about…
So…Player-A Always Wait and Player B Always Go remains a .
Q1. What about the other pure strategy combinations. Does their status as either being or not being change when you include mixed strategies?
Q2. Are there Nash equilibria involving mixed (i.e. not pure) strategies?
What about computation?
The first glimpse of computational techniques being used here is in the generation of visualizations.
The plots we have been looking at show how a player’s score varies as we change 2 parameters (that player’s strategy, and her opponent’s strategy).
I use plots like this all of the time in my research and I think it is worth taking a moment to show you how to efficiently generate these kinds of plots in Python…
A general way to think about these plots is that we have two parameters, x and y and we want to visualize a function of these two parameters, z = f(x,y)
Let’s start with a simple function f(x,y) = x + y
A beginner’s approach to generating this plot might involve a few for loops
for each x value :
for each y value :
calculate and store f(x,y)
but numpy has a useful set of tools that help you write neater and more efficient code* for doing this kind of thing. Let’s take a look.
* for loops are slow in Python compared to numpy operations which often use more efficient compiled code to run.
linspace(a,b,N)
“linear space” — return N evenly spaced values between a and b, inclusive. For example:
meshgrid(*xi)
Return coordinate matrices from coordinate vectors.
apply_along_axis(func1d, axis, arr)
Create a “flattened” version of a matrix by applying the function func1d along one of its axes.
x-values: y-values:
output: func1d([x,y])
Again: these plots are often used to show how a function z = f(x,y) changes as two of its parameters change (x,y)
As a case in point, we can look at the Mandelbrot set.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com