Algorithmic Game Theory and Applications
Lecture 2: Mixed Strategies, Expected Payoffs, and
U. of Edinburgh
Copyright By PowCoder代写 加微信 powcoder
Finite Strategic Form Games
Recall the “strategic game” definition, now “finite”:
Definition A finite strategic form game Γ, with n-players, consists of:
A set N = {1,…,n} of Players.
For each i ∈ N, a finite set Si = {1,…,mi} of(pure) strategies.
LetS=S1 ×S2 ×…×Sn bethesetofpossible combinations of (pure) strategies.
For each i ∈ N, a payoff (utility) function:
ui : S → R, describes the payoff ui(s1,…,sn) to player i under each combination of strategies.
(Each player wants to maximize its own payoff.)
AGTA: Lecture 2
Mixed (Randomized) Strategies
We define “mixed” strategies for general finite games.
Definition A mixed (i.e., randomized) strategy xi for Player i, withSi ={1,…,mi},isaprobabilitydistributionoverSi.In other words, it is a vector xi = (xi(1),…,xi(mi)), such that xi(j)≥0for1≤j ≤mi,and
xi (1) + xi (2) + . . . + xi (mi ) = 1
Intuition: Player i uses randomness to decide which strategy to play, based on the probabilities in xi .
Let Xi be the set of mixed strategies for Player i.
For an n-player game, let
X = X1 × . . . × Xn
denote the set of all possible combinations, or “profiles”, of mixed strategies.
AGTA: Lecture 2
Expected Payoffs
Let x = (x1,…,xn) ∈ X be a profile of mixed strategies.
For s = (s1, . . . , sn) ∈ S a combination of pure strategies, let
x(s) := xj(sj)
be the probability of combination s under mixed profile x. (We’re
assuming players make their random choices independently.) Definition: The expected payoff of Player i under a mixed strategy profile x = (x1,…,xn) ∈ X, is:
Ui(x) :=x(s)∗ui(s) s∈S
I.e., the “weighted average” Player i’s payoff under each pure combination s, weighted by the probability of that combination. Key Assumption: Every player’s goal is to maximize its own expected payoff. (This can somtimes be a dubious assumption.)
AGTA: Lecture 2
some notation
Wecallamixedstrategyxi ∈Xi pureifxi(j)=1forsomej ∈Si, and xi(j′) = 0 for j′ ̸= j. We denote such a pure strategy by πi,j. I.e., the “mixed” strategy πi,j does not randomize at all: it picks (with probability 1) exactly one strategy, j, from the set of pure strategies for player i.
Given a profile of mixed strategies x = (x1,…,xn) ∈ X, let x−i = (x1,x2,…,xi−1,empty,xi+1,…,xn)
I.e., x−i denotes everybody’s strategy except that of player i. Foramixedstrategyyi ∈Xi,let(x−i;yi)denotethenewprofile:
(x1,…,xi−1,yi,xi+1,…,xn)
In other words, (x−i ; yi ) is the new profile where everybody’s stategy remains the same as in x, except for player i, who switches from mixed strategy xi , to mixed strategy yi .
AGTA: Lecture 2
Definition: A (mixed) strategy zi ∈ Xi is a best response for Playeri tox−i ifforallyi ∈Xi,
Ui(x−i;zi) ≥ Ui(x−i;yi)
Clearly, if any player were given the opportunity to “cheat” and look at what other players have done, it would want to switch its strategy to a best response.
Of course, players in a strategic form game can’t do that: players pick their strategies simultaneously/independently.
But suppose, somehow, the players “arrive” at a profile where everybody’s strategy is a best response to everybody else’s. Then no one has any incentive to change the situation.
We will be in a “stable” situation: an “Equilibrium”.
That’s what a “ ” is.
AGTA: Lecture 2
Definition: For a strategic game Γ, a strategy profile
x = (x1,…,xn) ∈ X is a mixed if for every player, i , xi is a best response to x−i .
In other words, for every Player i = 1, . . . , n, and for every mixed strategyyi ∈Xi,
Ui(x−i;xi) ≥ Ui(x−i;yi)
In other words, no player can improve its own payoff by unilaterally deviating from the mixed strategy profile
x = (x1,…,xn).
x is called a pure if in addition every xi is a pure strategy πi,j , for some j ∈ Si .
AGTA: Lecture 2
Nash’s Theorem
This can, agruably, be called
“The Fundamental Theorem of Game Theory”
Theorem(Nash 1950) Every finite n-person strategic game has a mixed .
We will prove this theorem next time.
To prove it, we will “cheat” and use a fundamental result from topology: the Point Theorem.
AGTA: Lecture 2
The crumpled sheet experiment
Let’s all please conduct the following experiment:
Take two identical rectangular sheets of paper.
Make sure neither sheet has any holes in it, and that the sides are straight (not dimpled).
“Name” each point on both sheets by its “(x , y )-coordinates”.
Crumple one of the two sheets any way you like, but make sure you don’t rip it in the process.
Place the crumpled sheet completely on top of the other flat sheet.
AGTA: Lecture 2
Fact! There must be a point named (a, b) on the crumpled sheet that is directly above the same point (a, b) on the flat sheet. (Yes, really!)
As crazy as it sounds, this fact, in its more formal and general form, will be the key to why every game has a mixed .
AGTA: Lecture 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com