Algorithmic Game Theory and Applications
Lecture 9: Computing solutions for General Strategic Games: Part II:
AGTA: Lecture 9
Copyright By PowCoder代写 加微信 powcoder
from last time:
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 1 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 Follows easily from what we already know,
particularly 1st claim in the proof of Nash’s theorem. AGTA: Lecture 9
using our first clue
Suppose we somehow know support sets, support1 ⊆ S1, . . . , supportn ⊆ Sn, for some x∗ = (x∗1, . . . , x∗n).
Then, using Proposition 1, to find a NE we only need to solve the following system of constraints:
1. For all players i, and every πi,j ∈ supporti, Ui(x−i; πi,j) = wi,
2. For all players i, and every πi,j ̸∈ supporti, Ui(x−i; πi,j) ≤ wi.
3. for i=1,…,n, xi(1)+…+xi(mi)=1.
4. for i = 1,…,n, & for j ∈ supporti, xi(j) ≥ 0.
5. for i = 1,…,n, & for j ̸∈ supporti, xi(j) = 0.
This system has ni=1 mi + n variables, x1(1),…,x1(m1),…,xn(1),…,xn(mn),w1,…,wn.
Unfortunately, for n > 2 players, this is a non-linear system of constraints.
Let’s come back to the case n > 2 players later.
Consider the 2-player case: the system is an LP!! But,
Question: How do we find support1 & support2? Answer: Just guess!!
AGTA: Lecture 9
First algorithm to find NE’s in 2-player games
Input: A 2-player strategic game Γ, given by rational values u1(s,s′) & u2(s,s′), for all s ∈ S1 & s′ ∈ S2. (I.e., the input is (2 · m1 · m2) rational numbers.)
Algorithm:
• For all possible support1 ⊆ S1 & support2 ⊆ S2:
– Check if the corresponding LP has a feasible solution x∗, w1, . . . , wn. (using, e.g., Simplex). – If so, STOP: the feasible solution x∗ is a (and wi = Ui(x∗)).
Question: How many possible subsets support1 and
support2 are there to try? Answer: 2(m1+m2)
So, unfortunately, the algorithm requires worst-case exponential time.
But, at least we have our first algorithm.
AGTA: Lecture 9
remarks on algorithm 1
• The algorithm immediately yields:
Proposition Every finite 2-player game has a rational NE. (Furthermore, the rational numbers are not “too big”, i.e., are polynomial sized.)
• The algorithm can easily be adapted to find not just any NE, but a “good” one. For example:
Finding a NE that maximizes “(util.) social welfare”:
– For each support sets, simply solve the LP constraints while maximizing the objective
f (x, w) = w1 + w2 + . . . + wn
– Keep track of best NE encountered, & output
optimal NE after checking all support sets.
• The same algorithm works for any notion of “good” NE that can be expressed via a linear objective and (additional) linear contraints: (e.g.: maximize Jane’s payoff, minimize John’s, etc.)
• Note: This algorithm shows that finding a NE for 2-player games is in “NP”.
AGTA: Lecture 9
Towards another algorithm for 2-players
Let A be the (m1 × m2) payoff matrix for player 1, B be the (m2 × m1) matrix for player 2,
w1 be the m1-vector, all entries = w1,
w2 be the m2-vector, all entries = w2. Note:WecansafelyassumeA>0andB>0: by adding a large enough constant, d, to every entry we “shift” each matrix > 0. Nothing essential about the game changes: payoffs just increase by d.
We can get another, related, characterization of NE’s
by using “slack variables
” as follows:
Lemma x∗ = (x∗1, x∗2) is a NE if and only if:
1. There exists a m1-vector y ≥ 0, and w1 ∈ R, such
2. There exists a m2-vector z ≥ 0, and w2 ∈ R, such
A x ∗2 + y = w 1
& for all j =1,…,m1, x∗1(j)=0 or (y)j =0.
& for all j =1,…,m2, x∗2(j)=0 or (z)j =0.
Proof Again follows by the Useful Corollary to Nash: in a NE x∗ whenever, e.g., x∗1(j) > 0, U(x∗−1;π1,j) = U(x∗). Let(y)j =U(x∗)−U(x∗−1;π1,j).
AGTA: Lecture 9
B x ∗1 + z = w 2
rephrasing the problem
The Lemma gives us some “constraints” that characterize NE’s:
1. Ax2+y=w1 and Bx1+z=w2
2. x1,x2,y,z ≥ 0.
3. x1 and x2 must be probability distributions, i.e., m1 x1(j) = 1 and m2 x2(j) = 1.
4. Additionally, x1 and y, as well as x2 and z, need to be “complementary”:
for j = 1,…,m1, either x1(j) = 0 or (y)j = 0, for j = 1,…,m2, either x2(j) = 0 or (z)j = 0. Since everything is ≥ 0, we can write this as
yTx1 =0 and zTx2 =0
AGTA: Lecture 9
continuing the reformulation
Note that, because A > 0 and B > 0, we know that w1 >0 and w2 >0 in any solution.
Using this, we can “eliminate” w1 and w2 from the constraints as follows: Let x′2 = (1/w1)x2, y′ = (1/w1)y, x′1 = (1/w2)x1, and z′ = (1/w2)z.
Let 1 denote an all 1 vector (of appropriate dimension).
Suppose we find a solution to
Ax′2 +y′ =1 and Bx′1 +z′ =1
x′1,x′2,y′,z′ ≥ 0, (y′)Tx′1 = 0, and (z′)Tx′2 = 0.
If, in addition, x′1 ̸= 0 or x′2 ̸= 0, then, by
complementarity both x′1 ̸= 0 and x′2 ̸= 0.
In this case we can “recover” a solution x1,x2,y,z, and w1 and w2 to the original constraints, by multiplying x′1 and x′2 by “normalizing” constants w1 and w2, so that each of x1 = w1x′1 and x2 = w2x′2 define probability distributions. These normalizing constants define w1 and w2 in our solution.
AGTA: Lecture 9
2-player NE’s as a
Linear Complementarity Problem
Let 0 A x′1 M= B 0 u= x′
“Our Goal:” Find a solution u, v, to Mu + v = 1
such that u, v ≥ 0, and uT v = 0.
y′ v= z′
This is an intance of a Linear Complementarity Problem, a classic problem in mathematical programming (see, e.g., the book [Cottle-Pang-Stone’92]).
But, we already know one solution: u = 0, v = 1.
Our Actual Goal: is to find a solution where u ̸= 0.
Wait! Doesn’t “M u + v = 1” look familiar??
Sure! It’s just a “Feasible Dictionary” (from lect. 6 on Simplex), with “Basis” the variables in vector v.
Question: How do we move from this “complementary basis” to one where u ̸= 0?
Answer: Pivoting!! (in a very selective way) AGTA: Lecture 9
sketch of the Lemke-Howson Algorithm
• Start at the “extra” “complementary Basis” β = {(v)1,…,(v)m}, where m = m1+m2 (with BFS u=0,v=1). Abasisβiscomplementaryif for k ∈ {1,…,m}, either (u)k ̸∈ β or (v)k ̸∈ β (but not both, since |β| = m).
• For some i, move via pivoting to a “neighboring” “i-almost complementary” basis β′. A basis β′ is i-almost complementary if for k∈{1,…,m}\{i},(u)k ̸∈β′ or(v)k ̸∈β′.
• While (new basis isn’t actually complementary)
– There is a unique j, such that both (u)j and (v)j are not in the new basis: one of them was
just kicked out of the basis.
– If (u)j was just kicked out, move (v)j into the
basis by pivoting. If (v)j was just kicked, move (u)j in. (Selective pivot rules assure only one possible entering/leaving pair each iteration.)
– Newest basis is also i-almost complementary.
• STOP: we have reached a different complementary basis & BFS. A is obtained by “normalizing” u = [x′1 x′2]T .
AGTA: Lecture 9
We are, of course, skipping lots of details related to “degeneracy”, etc. (similar to complications that arose in Simplex pivoting).
Question Why should this work?
A key reason: With appropriately selective pivoting rules, each i-almost complementary Basis (“vertex”) has 2 neighboring “vertices” unless it is actually a complementary Basis, in which case it has 1. This assures that starting at the “extra” complementary BFS, we will end up at “the other end of the line”.
Let’s see it in pictures:
“extra” complementary BFS
AGTA: Lecture 9
• The Lemke-Howson (1964) algorithm has a “geometric” interpretation.
(See, [von Stengel, Chapter 3, in Nisan et. al. AGT book, 2007]. Our treatment is closer to [McKelvey-McLennan’96], see course web page.)
• The algorithm’s correctness gives another proof of Nash’s theorem for 2-player games only, just like Simplex’s gives another proof of Minimax (via LP-duality).
• How fast is the LH-algorithm? Unfortunately, examples exist requiring exponentially many pivots, for any permissible pivots (see [Savani-von Stengel’03]).
• Is there a polynomial time algorithm to find a NE in 2-player games? This is an open problem, which we will discuss shortly.
• However, finding “good” NE’s that, e.g., maximize “social welfare” is NP-hard. Even knowing whether there is > 1 NE is NP-hard. ([Gilboa-Zemel’89], [Conitzer-Sandholm’03]).
In practice we may want NE’s that optimize some “goodness”. The NP-hardness of doing so for many notions of “good”, for me diminishes the importance of efficiently finding “any lousy” NE.
AGTA: Lecture 9
games with > 2 players
• Nash himself (1951, page 294) gives a 3 player “poker” game where the only NE is irrational. So, it isn’t so sensible to speak of computing an “exact” NE when the number of players is > 2.
• But we can try to approximate NEs. But there are different notions of approximate NE:
Definition 1: A mixed strategy profile x is called a ǫ- , for some ǫ > 0, if ∀ i, and all mixed strategies yi: Ui(x) ≥ Ui(x−i; yi) − ǫ.
I.e.: No player can increase its own payoff by more than ǫ by unilaterally switching its strategy.
Definition 2: A mixed strategy profile x is ǫ- close to an actual NE, for some ǫ > 0, if there is an actual NE x∗, such that ∥x − x∗∥∞ ≤ ǫ.
I.e.: there is an NE x∗ in which every pure strategy of every player has a probability in x∗ that is at most ǫ different from its probability in x.
• Surprisingly, it turns out that these two different notions of approximation of an NE have VERY different computational complexity implications.
AGTA: Lecture 9
What is the complexity of computing an ǫ-NE?
• It turns out that:
(A) computing an NE for 2-player games, and (B) computing an ǫ-NE for > 2-player games
are reducible to each other.
Both are at least as hard as ANOTHER- LINE-ENDPOINT: “Find another end-point of a succinctly given (directed) line graph, with indegree and outdegree ≤ 1.”.
• [Papadimitriou 1992], defined a complexity class called PPAD to capture such problems, where ANOTHER-LINE-ENDPOINT is PPAD-complete.
He took inspiration from ideas in the Lemke- Howson algorithm and an algorithm by [Scarf’67] for computing almost fixed points.
• [Chen-Deng’06] and [Daskalakis-Goldberg- Papadimitriou,’06], showed that computing an NE in 2-player games, & computing a ǫ-NE in > 2- player games, respectively, are PPAD-complete.
• However, these results don’t resolve the complexity of approximating an actual NE in > 2 player games.
AGTA: Lecture 9
The complexity of computing an actual NE in games with > 2 players
• For games with > 2 players, approximating an actual NE, i.e., computing a profile that is ǫ- close to an actual NE, even for any ǫ < 1/2, is MUCH harder. It is not even known to be in NP. The best complexity upper bound we have is PSPACE (using deep but impractical algorithms for solving nonlinear systems of equations [...,Canny’88,Renegar’92]).
• [Etessami-Yannakakis’07] showed that if we can approximate an actual NE even in NP, that would resolve major open problems in the complexity of numerical analysis. (Seems unlikely at present.)
[Etessami-Yannakakis’07] showed computing or approximating an actual NE is FIXP- complete, where FIXP consists of all problems reducible to computing a fixed point for algebraic Brouwer functions defined by operators {+, ∗, −, /, max, min} and rational constants.
AGTA: Lecture 9
• Such fixed point computation problems have many other important applications, in particular, for computation of market equilibria.
• In turns out that PPAD is exactly the “piecewise linear” fragment of FIXP, consisting of problems reducible to Brouwer fixed point problems defined by algebraic functions using operators {+, −, max, min}.
• These results are beyond the scope of this course.
If you are interested, for more information see:
K. Etessami and M. Yannakakis, “On the Complexity of and other Fixed Points”, SIAM Journal on Computing, 39(2), pp. 2531-2597, 2010.
and the references therein.
AGTA: Lecture 9
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com