[SOLVED] CS Algorithmic Game Theory and Applications

Algorithmic Game Theory and Applications
Lecture 7:
The LP Duality Theorem
Kousha Etessami AGTA: Lecture 7

Copyright By Assignmentchef assignmentchef

recall LPs in Primal Form
Maximize c1 x1 +c2 x2 ++cn xn
Subject to:
a1,1 x1 +a1,2 x2 ++a1,n xn b1 a2,1 x1 +a2,2 x2 ++a2,n xn b2 am,1 x1 +ai,2 x2 ++am,n xn bm
x1,,xn 0
An LP can concisely be represented in
matrix notation:
Define the (m n)-matrix A by: (A)i,j = ai,j. Define (column) vectors x = [x1, . . . , xn]T ,
b = [b1,,bm]T & c = [c1,,cn]T.
The LP is:
Maximize cT x Subject to: Ax b x1,,xn 0

AGTA: Lecture 7

Solving LPs against an Adversary
Suppose you want to optimize this Primal LP:
Maximize cT x Subject to: Ax b x1,,xn 0
Suppose an Adversary comes along with a m-vector y Rm, y 0, such that:
For any solution, x, you may have for the Primal:
cTx (yTA)x (becausex0&cT yTA) = yT (Ax)
yTb (becauseyT 0&Axb) So, the adversarys goal is to minimize yT b, subject
tocT yTA,i.e.,tooptimizethefollowingDualLP:
Minimize bT y Subject to: AT y c y1,,ym 0
AGTA: Lecture 7

The LP Duality Theorem
As we saw, a feasible value of the primal LP is at most the optimal value of the dual, i.e.:
Proposition (Weak Duality) If x Rn and y Rm are optimal feasible solutions to the primal and dual LPs, then:
cTx bTy Amazingly, equality holds!
Theorem(Strong Duality, von Neumann47) One of the following four situations holds:
1. Both the primal and dual LPs are feasible, and for any optimal solutions x of the primal and y of the dual:
cTx =bTy
2. The primal is infeasible and the dual is unbounded.
3. The primal is unbounded and the dual is infeasible.
4. Both LPs are infeasible.
AGTA: Lecture 7

Simplex and the Duality Theorem
It turns out, LP Duality follows from the proof of correctness of the Simplex algorithm (which we didnt provide).
In fact, suppose Simplex on the Primal LP halts and produces an optimal solution vector x.
Let y = c , where c is the coefficient
of the slack variable xn+j in the last objective
function f(x) associated with the final dictionary for the primal LP. This defines y Rm, and it turns out the following holds:
Facty 0,ATy c,andcTx =bTy.
So, using Simplex, we can actually compute an optimal solution for the dual while we compute an optimal solution for the primal (or find out neither exists).
AGTA: Lecture 7

Complementary Slackness
Useful Corollary of LP Duality: solutions x and y to the primal and dual LPs, respectively, are both optimal if and only if both of the following hold:
For each primal constraint, (Ax)i bi, i = 1,,m, either
(Ax)i = bi or yi = 0 (or both).
For each dual constraint, (AT y)j cj , j = 1,,n, either
(ATy)j = cj or xj = 0 (or both). Proof By weak duality
cT x ((y)T A)x = (y)T (Ax) (y)T b
By strong duality each inequality holds with equality
precisely when x and y are optimal.
So, when optimal, (((y)T A) cT )x = 0. Sinceboth((y)TA)cT)0andx 0,itmust be that for each j = 1,,n,
( A T y ) j = c j o r x j = 0
Likewise, when optimal, (y)T (b Ax) = 0, and thus, for each i = 1,,m, (Ax)i = bi or yi = 0.
AGTA: Lecture 7

general recipe for LP duals
If the primal is:
Maximize cT x
Subject to:
(Ax)i bi , i = 1,,d, (Ax)i = bi , i = d + 1, . . . , m, x1,,xr 0
Then the dual is:
Minimize bT y
Subject to:
(ATy)j cj,j=1,,r, (ATy)j =cj,j=r+1,,n, y1,,yd 0
Strong Duality holds also in this more general setting. Fact: The dual of the dual is the primal.
AGTA: Lecture 7

Duality and the Minimax Theorem
Recall the LP for solving Minimax for Player 1 in a zero-sum game given by matrix A:
Maximize v
Subject to:
v(xTA)j 0forj=1,,m2, x1++xm1 =1,
xi 0 for j = 1, . . . , m1.
What is the Dual to this LP? It can be shown to be:
Minimize u
Subject to constraints: u(Ay)i 0fori=1,,m1, y1++ym2 =1
yj 0forj=1,,m2.
This is exactly the LP for Player 2s optimal strategy!
Thus, the minimax theorem follows from Duality: the optimal value for the two LPs is the same.
AGTA: Lecture 7

In fact, LP Duality can also be derived from the Minimax Theorem. Consider (A a (m n)-matrix):
Maximize cT x Subject to: Ax b x1,,xn 0
Proof (sketch) that Minimax LP-duality: Consider the zero-sum payoff matrix:
0 A b B=AT 0 c
This is a symmetric zero-sum game: B = BT. By a simple exercise, such a game must have minimax value 0, and every minmaximizer for player 1 is also a maxminimizer for player 2. Consider a symmetric minimax profile:
((Y,X,z),(Y,X,z))
for this game. Here Y is a (row) vector of length
m,andX isa(row)vectoroflengthn,andzR. AGTA: Lecture 7
From Minimax to LP Duality

more in Minimax LP-duality Suppose z > 0, in the minimax strategy (Y , X, z).
Note that, by the Minimax Theorem, we have AXbz0 and czATY0
Letting y = (1/z)Y , and x = (1/z)X, we would have Ax b and AT y c, i.e., feasible solutions for the LP and its Dual.
Moreover, by Useful Corollary to Minimax, player 1 can switch to ANY pure strategy j in its support (i.e., where x1(j) > 0) and not change its profit. Let it switch to the last row (i.e., letting z = 1). Then we also have: bY cX = 0, and hence by cx = 0. Thus,
by = cx The only thing left to prove is:
Claim If both the LP and its Dual are feasible, the game B has some minimax profile where z > 0.
AGTA: Lecture 7

The claim can be proved (see [Dantzig51], [Raghavan,HGT,Ch.20]) using facts related to the geometry of LP and Minimax: specifically the Farkas lemmas.
Such can actually be proved very nicely using Fourier-Motzkin elimination. Here is a Farkas lemma:
Ax b has no solutions if and only if there exists y 0 such that yT A = 0 and yT b < 0.(HW1 asks you to prove this.) This proof is somewhat unsatisfactory because the Farkas lemmas are essentially equivalent to LP- duality. (A recent modification of this proof, by [Adler 2013], avoids the use of Farkas lemmas.) AGTA: Lecture 7 Significance of LP Duality The Duality Theorem is an extremely important fact in subjects like mathematical economics and combinatorial optimization.So much so that we can not possibly do it justice. Often, you can learn something about an LP by looking at its dual. In Economics, one often sets up an LP to optimize some economic goal. Often, the dual LP can be meaningfully interpreted as a problem of optimizing some real economic counter goal.The fact that the optimal solutions of the two goals are the same is very powerful. Duality has many consequences in algorithms.For example, duality implies that LPs can be solved in NP co-NP.(Of course, we know from [Khachian79] that the LP problem is in P.) AGTA: Lecture 7more on algorithmic significance approximation algorithms: hard combinatorial optimization problems can often be formulated as Integer Linear Progams (ILPs). One can often use the LP-relaxation of the ILP together with its Dual to find approximate solutions and to bound the proximity of the approximate solution to the optimal. (See, e.g., [Vazirani2001].) Many important results in combinatorics can be viewed as particular manifestations of LP Duality. Max-Flow Min-Cut Theorem; Halls Theorem;Dilworths Theorem; Konig-Egervary Theorem……Each result says the maximum value of one useful quantity associated with a combinatorial object is the same as the minimum value of another useful quantity associated with it.These follow from LP-Duality: dual LPs for these complementary quantities can be set up (with solutions that consist necessarily of integers, due to the LPs structure).AGTA: Lecture 7food for thought(in this case thought for food) Recall the Diet Problem. It has the form:Minimize cT x Subject to: Ax b x1,…,xn 0 Construct the dual to this LP. What do the dual variables mean in the contextof the diet problem?Try to come up with an interpretation.(Hint: try to assign consistent units of measure to the primal variables, constants, and coefficients. These will determine the units of measure of the dual variables, and will guide you toward an interpretation.) What is the dual LP trying to optimize? AGTA: Lecture 7 CS: assignmentchef QQ: 1823890830 Email: [email protected]