Algorithmic Game Theory and Applications
Lecture 8: Computing solutions for General Strategic Games: Part 1: dominance and iterated strategy elimination
AGTA: Lecture 8
Copyright By PowCoder代写 加微信 powcoder
Let’s again consider general finite strategic games. Definition For xi, x′i ∈ Xi, we say xi dominates x′i,
denoted xi ≽ x′i, if for all x−i ∈ X−i, Ui(x−i; xi) ≥ Ui(x−i; x′i)
We say xi strictly dominates x′i, denoted xi ≻ x′i, if for all x−i ∈ X−i
Ui(x−i; xi) > Ui(x−i; x′i)
Proposition xi dominates x′i if and only if for all pure “counter profiles” π−i ∈ X−i
π−i = (π1,j1,…,empty,…,πn,jn), Ui(π−i; xi) ≥ Ui(π−i; x′i)
Likewise, xi strictly dominates x′i iff for all π−i Ui(π−i; xi) > Ui(π−i; x′i)
Proof Another easy “weighted average” argument. AGTA: Lecture 8
a partial-order on strategies: dominance
obviously good strategies: dominant strategies
Definition A mixed strategy xi ∈ Xi is dominant if for all x′i ∈ Xi, xi ≽ x′i. xi is strictly dominant if forallx′i ∈Xi suchthatx′i ̸=xi,xi ≻x′i.
Definition For a mixed strategy xi, define its support, support(xi), to be the set of pure strategies πi,j such that xi(j) > 0.
Proposition Every dominant strategy xi is in fact a “weighted average” of pure dominant strategies. I.e., each πi,j ∈ support(xi) is also dominant. Moreover, only a pure strategy can possibly be strictly dominant.
Proof Again, easy “weighted average” argument: mi
Ui(x−i; xi) = xi(j) ∗ Ui(x−i; πi,j) j=1
But note, if xi is dominant, then for any x−i Ui(x−i;xi) ≥ Ui(x−i;πi,j), for j = 1,…,mi.
But this can only be the case if, whenever xi(j) > 0, Ui(x−i; xi) = Ui(x−i; πi,j ).
If xi is strictly dominant, it must clearly be equal to the unique pure strategy in its support.
AGTA: Lecture 8
So, easy algorithm to find dominant strategies
• For each player i and each pure strategy sj ∈ Si,
– Check if, for all pure combinations
s ∈ S = S1 × . . . Sn, ui(s−i; sj) ≥ ui(s).
– If this is so for all s, output “sj is a dominant strategy for player i”.
• If no such pure strategy found, then there are no dominant strategies.
Same easy algorithm for a strictly dominant strategy. But there may be no dominant strategies. . ..
AGTA: Lecture 8
Definition We say a strategy xi ∈ Xi is strictly dominated if there exists another strategy x′i such that x′i ≻ xi. We say xi is weakly dominated if there exists x′i such that x′i ≽ xi and for some x−i ∈ X−i, Ui(x−i; x′i) > Ui(x−i; xi).
Clearly, strictly dominated strategies are “bad”: “rational” players would be stupid to play them.
Weakly dominated strategies aren’t necessarily as “bad”. It depends on what you think others will play. In particular, there can be where everybody is playing a weakly dominated strategy:
(0,0) (0,0)
(0, 0) (1, 1)
Question How can we compute whether a strategy
is (strictly) dominated?
Example Consider the following table, showing only
Player 1’s payoffs: Is the last row strictly dominated?
30 0 0 0 30 0 0 0 30 555
obviously bad strategies: strictly dominated strategies
AGTA: Lecture 8
To do this, we can use an LP with strict inequalities. For each pure “counter profile” π−i, we add a constraint Cπ−i(x′i(1), . . . , x′i(n)), given by:
Ui(π−i; x′i) > Ui(π−i; xi)
Note that this is a linear constraint: the right hand side is a constant we can compute, and the left hand side is linear in the variables x′i(1), . . . , x′i(n).
We also add the constraints x′i(1) + . . . + x′i(n) = 1, and x′i(j) ≥ 0, for j = 1,…,n.
xi is strictly dominated iff this “strict LP” is feasible. But how do we cope with strict inequalities?
• Introduce a new variable y ≥ 0, to be Maximized, and change constraints to:
Ui(π−i; x′i) ≥ Ui(πi; xi) + y
Then xi is strictly dominated if and only if system is feasible and the optimal value for y is > 0 (or unbounded, but in this case that can’t happen).
• Useful Note: Any optimal solution x′i to this revised LP is itself not strictly dominated.
finding strictly dominated strategies via LP
Goal: Determine if xi ∈ Xi is (strictly) dominated.
AGTA: Lecture 8
common knowledge and strategy elimination
• Recall the games “Guess Half the Average”, and “Give a (matched) dollar to the other player”.
• How do we reason about such games? Suppose I “know” that all players are “rational” (i.e., aim to optimize their own expected payoff). Then I might conclude: “Jane will never play a strictly dominated (SD) strategy. So I can eliminate her SD strategies from consideration.” But by eliminating her SDSs, some of my strategies may become SD’ed! Deepening the reasoning, suppose
“I know that she knows that I know that ……”. • Definition (somewhat informal): A fact P is
“common knowledge” among all n players if:
– For every player i,
“Player i knows P”: call this fact P⟨i⟩.
– And, inductively, for k ≥ 1, for all players i, and all sequences s = i1 …ik ∈ {1,…,n}k, “Player i knows P⟨s⟩”: call this fact P⟨i s⟩.
(To be more formal, we would have to delve deeper into “logics of knowledge”. Outside the scope of this class. See, e.g., the book [Fagin-Halpern-Moses-Vardi’95].)
AGTA: Lecture 8
iterated SDS elimination algorithm
RKN hypothesis: every player’s “rationality” is common knowledge among all players.
Under this hypothesis, we can safely conduct the following strategy elimination algorithm:
• While (some pure strategy πi,j is SD’ed) eliminate πi,j from the game,
obtaining a new residual game;
Sometimes, a player’s strategy may be uniquely determined by the end of elimination, but certainly not always: (standard example from [Bernheim’84])
(0,7) (5,2) (7,0)
(2,5) (3,3) (2,5) (0, −2)
(7,0) (5,2) (0,7) (0, 0)
(0,1) (0,1) (0,1)
Note: we iteratively eliminate only pure SDSs. There may in fact remain mixed SDSs.
Before playing any mixed strategy in the residual game we should make sure it is not SD’ed (by, e.g., making sure it is an optimal solution of the appropriate LP).
AGTA: Lecture 8
• There is a more general notion of rationalizability
([Bernheim’84,Pierce84]), which says:
– A rational player i should never play a strategy xi which is “never a best response” to any counter strategy x−i (see below).
– Assuming rationality is common knowledge, we should also iteratively eliminate all strategies that are “never a best response”.
• It turns out, for 2-player games, this elimination yields exactly the same residual game as iterated SDS elimination. So the same algorithm applies.
• For > 2 players, things get more complicated: this equivalence doesn’t hold unless we adopt a different notion of “never a best response” (with respect to any “belief ” of player i about other players’ strategies, . . . . . . we will not consider this further.)
AGTA: Lecture 8
• Note: We did not eliminate weakly dominated strategies.
• In fact, the residual game obtained from iterated WDS elimination depends on the order of elimination:
(5,1) (4,0) (6,0) (3,1) (6, 4) (4, 4)
• This problem does not arise for strictly dominated strategies:
Proposition Iterated elimination of strictly dominated strategies produces the same final residual game regardless of the order in which strategies are eliminated.
Proof If a pure strategy is strictly dominated, it will remain strictly dominated even after another strictly dominated pure strategy is removed.
weakly vs. strictly dominated strategies
AGTA: Lecture 8
Computing : a first clue
Recall “Useful corollary for NEs”, from Lecture 3: Ifx∗ isanNE,thenifx∗i(j)>0then
Ui(x∗−i; πi,j ) = Ui(x∗).
Using this, and adding a condition, we can fully
characterize :
Proposition In an n-player game, a profile x∗ is a if and only if there exist w1, . . . , wn ∈ R, such that the following hold:
1. For all players i, and every πi,j ∈ support(x∗i ), Ui(x∗−i; πi,j) = wi, and
2. For all players i, and every πi,j ̸∈ support(x∗i ), Ui(x∗−i; πi,j ) ≤ wi.
Note: Any such wi’s necessarily satisfy wi = Ui(x∗). Proof Easy from what we already know.
Food for thought: Can you use this to find a NE?
AGTA: Lecture 8
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com