Algorithmic Game theory and Applications Solutions for Homework 1 (2020)
(13, 9) (3, 5) (15, 5) (4, 11)
(5, 9) (14, 5) (10, 11) (8, 12)
Copyright By PowCoder代写 加微信 powcoder
(7, 13) (8, 11) (9, 5) (7, 4)
(11, 12) (13, 4) (6, 13) (12, 10)
(17, 12) (4, 10) (7, 14)
There is a unique for this game. The unique NE, x∗ = (x∗1,x∗2) is given by the following mixed strategies for the two players: mixed stategy x∗1 = (9/10, 0, 1/10, 0) for player 1; and mixed strategy x∗2 = (0, 0, 5/6, 0, 1/6) for player 2.
The expected payoffs to the two players in this NE are as follows: U1(x∗) = 26/3, and U2(x∗) = 61/5.
We now proceed to prove why this is the unique in this game.
We first use iterated illimination of strictly dominated strategies, as follows, to reduce the game down to a 2 × 2 residual game as follows:
First, strategy c1 (column 1) of player 2 can be eliminated by noting that it is strictly dominated by a weighted average (convex combi- nation) of strategies c2 and c3, with weights (1 − ε) · c2 and ε · c4, respectively, for a sufficiently small ε > 0 (for example, it suffices if 0 < ε < 1/10).
Next, strategy row 4 (r4) of player 1 can be eliminated in the risidual game, because it is strictly dominated by row r2 in the risidual game. Then strategy column c2 of player 2 can be eliminated in the risidual game, because it is strictly dominated by c5. Next, strategy c4 of player 2 can be eliminated, because it is strictly dominated by a weighted average of strategies c3 and c5, with weights ε·c3 and (1−ε)·c5, where
ε = 1/10 suffices. Finally, strategy r2 can be eliminated, because it is strictly dominated in the risidual game by r3.
Hence, we are left with the following final residual game, from which we can not eliminate any more pure strategies by a process of iterated elimination of strictly dominated strategies.
(7, 13) (17, 12) (9, 5) (7, 14)
Note that during this elimination process we can not possibly have eliminated any that existed in the original game, because (as explained in lectures) iterated elimination of strictly dom- inated strategies can not eliminate any pure strategy that is played with positive probability in any .
Note that in the final residual game, there are no pure NEs. This is easy to check by inspection. Furthermore, it is easy to check that there can not be any NE in which one of the players plays a pure strategy, because there is a unique pure-strategy best response to any pure strategy played by either player in this game.
Hence, the only possibility is that there exists a fully mixed stategy in this game where both players play both pure strategies with positive probability.
Thus, we can use the simple corollary to Nash’s theorem to compute the unique fully mixed NE in this risidual game, as follows:
Suppose player 1 plays strategy 1 with probability p and strategy 2 with probability p in some NE, where 0 < p < 1. Suppose player 2 plays strategy 1 with probability q and strategy 2 with probability (1 − q) in some NE, where 0 < q < 1.
We will show that, with these assumptions, p and q are both uniquely determined, and we will determine their values, which will give us the unique fully mixed NE in this risidual game.
Note that, by the corollary to Nash, it must be the case that if player 2 is playing against player 1’s mixed strategy (p, 1 − p), both of player 2’s pure strategies must be a best reponse to player 1. Likewise for player 1.
Thus we must have:
13p+5(1−p) = 12p+14(1−p) 7q+17(1−q) = 9q+7(1−q)
This is equivalent to saying:
p = 9(1−p) 2q = 10(1−q)
The unique solution to each of the above equations is given by p = 9/10 and q = 5/6.
This yields the fully mixed NE described above, after we plug back in the 0’s for the probability of those pure strategies that were eliminated during iterated elimination of strictly dominated strategies.
It is clear that there are no other NEs, because we only used elimina- tion of strictly dominated strategies to eliminate pure strategies, and because as we argued above the residual 2 × 2 game has a unique fully mixed NE.
2. Let the matrix A be the matrix shown in the problem. Then, using x to denote a vector of variables denoting player 1’s mixed strategy, and using an auxiliary variable v for the value of the game, and letting the vector vT denote a vector every coordinate of which is the variable v, we aim to solve the following LP for finding a minmaximizer strategy for player 1, and for finding the value v of the game:1
Maximize v Subject to: xT A ≥ vT
xT 1 = 1 x≥0
Plugging this LP into an LP solver (e.g., in matlab), we get the follow-
ing optimal solution vector (x∗, v∗): x∗ = (0.0, 0.0, 0.416185, 0.352601, 0.231214) and v∗ = 4.8034682089.
1Note that 1 (0) denotes the all-one (respectively, all-zero) vector. 3
Or, more precisely x∗ = (0, 0, 72/173, 61/173, 40/173), v∗ = 831/173. Thus the value of the game is v∗ = 831/173, and a minmaximizer
strategy for player 1 is given by x∗.
For player 2, we can solve the DUAL LP given by:
Miminize u Subject to: Ay ≤ u
y1 = 1 y≥0
The optimal solution (y∗, u∗) is y∗ =
and, as we would expect u∗ = 831/173, which gives us a maxminimizer for player 2, and (again) the value of game. (Of course the payoff to player 2 under this profile is: −831/173.)
(It is in fact not difficult to see that this is the unique Nash equilibrium of this 2-player zero-sum game, but you are not asked to establish this.)
(a) It is easy to see that for both players playing each of their strate- gies with probability 1/2 gives the only minimax profile (i.e., only NE) of the Matching Pennies game.
(b) For i = 1,2, and n ≥ 1, let Hni , Tni, denote the number of heads
and tails played by player i after n iterations of the game.
Let Dni = Hni − Tni denote the difference between the number of
heads and tails played by player i after n iterations of the game.
We will show that limn→∞ Dni = 0. This then easily implies that n
lim Hni = Hni = 1/2, which is what we want to show. n→∞ Hni +Tni n
First, we do something very simple: suppose we adopt the fol- lowing tie break rule: if at some round n, Dni = 0, then in the next round n+1, player j ̸= i must play something different than what it did in round n.
If we adopt this rule, then it is easy to prove that if we start out in round 1 with (D1,D12) = (A,B) for any A,B ∈ {1,−1}, then for all n ≥ 1, and all i ∈ {1, 2}, we must have |Dni | ≤ |A| + |B|. Indeed, starting for example from both players playing heads, the sequence of pairs (Dn1,Dn2), will always cycle as follows:
(1,1) → (2,0) → (1,−1) → (0,−2) → (−1,−1) → (−2,0) → (−1,1) → (0,2) → (1,1).
(0, 0, 39/173, 59/173, 75/173),
(This crucially uses the tie break rule. It wouldn’t be true without the tie break rule.)
Thus it is clear that, as n → ∞ Hni = 1/2, using this tie-break n
It is harder to prove this without the assumption about the tie break rule.
Here is a proof sketch only for a general tie-break rule:
Let’s first look at how the game must start. Suppose, e.g., that initially both players play heads.
Then the sequence of differences (Dn1,Dn2), starts off for n = 0, 1, 2, as:
(0,0) → (1,1) → (2,0)
Consider what happens if, after some iteration n, we have (Dn1,Dn2) = (A,0), with A > 0.
There are two possibilities, based on how player 1 breaks the tie in the next round (n + 1):
i. Player 1 plays tails. Then the sequence of differences there- after looks like:
(A − 1, −1) → (A − 2, −2) → . . . → (0, −A).
Once we reach (0,−A) we can symmetrically consider how player 2 can break ties.
ii. Player 1 can play heads. Then the sequence of differences becomes:
(A + 1, −1) → (A, −2) → . . . → (0, −(A + 2)).
If at round n we have differences (Dn1 , Dn2 ), let us define the SIZE of the “state” at round n, denoted sizen = max(|Dn1 |, |Dn2 |).
In both cases above, we see that it must take at least A + 2 iterations before the maximum size of the state is increased from A to A+2 for the first time. √
Using this, we claim that for all n, sizen ≤ c ∗ n, for some fixed constants c1 ≥ 0.
This is clearly true at the beginning, say up to the step when the differences are (2, 0). (We can pick, e.g., c = 2).
To see that it is always true, note that if the state at time n has differences (N,0) or (0,N), then it will take N+2 before we have sizen+N+2 = N + 2 for the first time.
Thus, to add N to the size, we must do at least (N +2)∗N/2 iterations.
Thus in general, as n gets large, it must be the case that the statistical probability of heads at round n for player 1 is:
1 Hn1 1 Dn1 1 c 1 c pn= n =2+2n∈[2−2√n,2+2√n]
Thus, we see that as n → ∞, we have p1n → 12 .
Symmetrically, we can make the same arguments when we start at a state (0,A), and to claim that p2n → 12.
(c) The approach of playing a best response against the statistical mixed strategy of the opponent in the repeated version of the game is called ficticious play. There is a large literature about ficticious play, going back to seminal work by [Annals of Mathematics, 1951], who showed that for every finite two-player zero-sum game, ficticious play converges to the set of statistical mixed strategies that correspond to minimax profiles (and thus to the set of NEs) of the zero-sum game. Her proof of this is quite amazing, and quite involved. (She is one of my mathematical heros, not just for this theorem, but for numerous amazing theorems she proved. Her life story is also amazingly inspiring; if you are interested in biographies of great mathe- maticians, I would highly recommend reading about her.)
For the special case of matching pennies, the situation is of course much simpler. (In particular, there is a unique NE, so “converging to the set of NEs”, means simply converging to that unique NE.) In general, for 2-player non-zero sum games, ficticious play need not converge at all to any NE. Shapley (1964) gave examples of 3 × 3 non-zero sum 2-player games (bimatrix games) for which ficticious play does not converge to any equilibrium (regardless of what pure strategies we start with, and regardless of the tie- breaking rule that we use during ficticious play).
The following 3 × 3 bimatrix game (which can be viewed as a strange kind of non-zero-sum variant of rock-paper-scissors) is one of Shapley’s examples:
(0,0) (2,1) (1, 2)
(1,2) (0,0) (2, 1)
(2,1) (1,2) (0, 0)
It has a unique Nash equilibrium, namely where both players play each pure strategy with probability 1/3 in the unique NE. And yet ficticious play does not converge to this unique NE.
Over the years, researchers in game theory have tried to classify for which kinds of games, beyond zero-sum games, convergence of ficticious play to the set of NEs does/doesn’t hold (and when it does hold, how “fast” or “slow” convergence happens). There are many such results.
4. One variant of the says the following:
Lemma 1 : A linear system of inequalities Ax ≤ b has a solution x if and only if there is no solution vector y satisfying y ≥ 0 , yT A = 0, and yT b < 0.
Proof. One direction is easy: suppose there is a vector y such that y ≥ 0, yT A = 0, and yT b < 0.
We show that this implies there is no solution to Ax ≤ b. Suppose there is such a solution. Then 0 = (yTA)x = yT(Ax) ≤ yTb < 0, which is a contradiction.
In the other (harder) direction, we wish to show that if there is no solution to Ax ≤ b, then there is a solution y ≥ 0 such that yTA = 0, and yT b < 0.
We will do this by using the fact that Fourier-Motzkin elimination works to solve linear systems of inequalities like Ax ≤ b.
The key observation is the following: one round of Fourier-Motzkin elimination (i.e., the elimination of a variable) can be “implemented” by pre-multiplying a given linear system of inequalities Ax ≤ b by a non-negative matrix. In other words, FM-elimination achieves the following:
Claim 1 For a linear system of inequalities Ax ≤ b, and a variable xi, there is a non-negative matrix Ci (corresponding to an FM-elimination step which eliminates variable xi), such that Ax ≤ b is feasible if and only if CiAx ≤ Cib is feasible, and furthermore such that the matrix (CiA) has only 0’s in its i’th column. (In other words the variable xi has been eliminated from the new system CiAx ≤ Cib of inequalities.)2
2Note that the number of rows in C may be much bigger then the number of columns, so the new system of inequalities CAx ≤ Cb may have many more constraints than Ax ≤ b.
We can use this claim to easily establish the harder direction of the Farkas lemma as follows: proceed using FM-elimination to sequentially eliminate the variables x1, . . . , xn.
This yields a new system of inequalities:
CnCn−1 ...C1Ax ≤ CnCn−1 ...C1b
If we let C := CnCn−1 ...C1 then we can write this system as CAx ≤
Now notice that by Claim 1, all Ci matrices, and thus also the matrix C are non-negative. Furthermore notice that, again by Claim 1, CA = 0 (in other words, CA is the all zero matrix), because it must be all 0 in every column (note that once a column becomes all 0 it stays all 0 thereafter).
Thus, CAx ≤ Cb can be rewritten as 0 ≤ Cb.
But we have assumed that the original system, Ax ≤ b, does not have a solution. Thus from the correctness of Fourier-Motzkin elimination we know that 0 ≤ Cb does not have a solution.
But this is the case iff there is a row j′ such that (Cb)j′ < 0.
Now, pick any such row j′, and construct a (non-negative) vector z which is 1 in position j′ and 0 everywhere else. Then we have (zT C)b = zT(Cb) < 0, and (zTC)A = zT(CA) = 0.
Thus,letyT :=zTC. Notethaty≥0,yTA=0,andyTb<0.
Thus, by assuming that Ax ≤ b has no solution, we have found a
solutiontoy≥0,yTA=0,andyTb<0. Wearedone.
All that remains is to establish Claim 1. But this is fairly easy to do: consider one round of FM-elimination where, say, variable x1 is being eliminated. Let us rephrase what happens in such a round of FM-elimination as follows:
Each inequality aj,1x1 + aj,2x2 + . . . + aj,nxn ≤ bj can be re-written (depending on the sign of aj,1) in one of three forms (types) of inequal- ities:
(a) if aj,1 > 0, then we can multiply the inequality by 1/aj,1 to rewrite it as an inequality of type (I):
x1 +(aj,2/aj,1)x2 +…+(aj,n/aj,1)xn ≤bj/aj,1
(b) if aj,1 < 0, then we can multiply by 1/−aj,1, to rewrite it as an inequality of type (II): −x1 +(aj,2/−aj,1)x2 +...+(aj,n/−aj,1)xn ≤bj/−aj,1 (c) finally, if aj,1 = 0, we have an inequality of type (III) and we can leave it untouched (i.e., multiply the inequality by 1). Note that all of these transformations can be carried out simultane- ously by pre-multiplying Ax ≤ b by a non-negative matrix D which has the appropriate multiplication constant for each inequality sitting on the diagonal of D and with 0 everywhere else in D. Now, we have a revised inequality system DAx ≤ Db, and FM- elimination corresponds to the following action: find every pair of inequalities β and α of type I and II, respectively, and add them together to get a new inequality without x1, and also retain all in- equalities of type III. But adding two such inequalities means pre-multiplying by a row vec- tor with 0 everywhere except a 1 in the two columns corresponding to the two inequalities. Doing this for every such pair, and leaving the type III inequalities unchanged corresponds to pre-multiplying by a non-negative matrix C′. Thus we get a new system C′DAx ≤ C′Db, such that x1 has been eliminated, i.e., such that (C′DA) has only 0’s in the first column. Let C1 := C′D. Note that C1 is non-negative. We have shown the claim holds for eliminating the variable x1. Of course x1 was arbitrary, and we could have just as easily FM-eliminated any other variable by pre-multiplying by a non-negative matrix. We are done. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com