2 Player Game 0 -1 1 1 0 -1 -1 1 0 Row player Column player Row player tries to maximize the payoff, column player tries to minimize Strategy:
A probability
distribution
2 Player Game A(i,j) Row player Column player Strategy:
A probability
distribution You have to decide your strategy first. Is it fair??
Von Neumann Minimax Theorem Strategy set Which player decides first doesn’t matter! e.g. paper, scissor, rock.
Key Observation If the row player fixes his strategy,
then we can assume that y chooses a pure strategy Vertex solution
is of the form
(0,0,…,1,…0),
i.e. a pure strategy
Key Observation similarly
Primal Dual Programs duality
Other Applications Analysis of randomized algorithms (Yao’s principle)
Cost sharing
Price setting
Totally Unimodular Matrices Vertex solution: unique solution of n linearly independent tight inequalities m constraints, n variables Can be rewritten as: That is:
Totally Unimodular Matrices When does has an integral solution x? Assuming all entries of A and b are integral By Cramer’s rule where Ai is the matrix with each column is equal to the
corresponding column in A except the i-th column is equal to b. x would be integral if det(A) is equal to +1 or -1.
Totally Unimodular Matrices A matrix is totally unimodular if the determinant
of each square submatrix of is 0, -1, or +1. Theorem 1: If A is totally unimodular,
then every vertex solution of is integral. Proof (follows from previous slides): a vertex solution is defined by a set of n linearly independent tight inequalities.
Let A’ denote the (square) submatrix of A which corresponds to those inequalities.
Then A’x = b’, where b’ consists of the corresponding entries in b.
Since A is totally unimodular, det(A) = 1 or -1.
By Cramer’s rule, x is integral.
Example of Totally Unimodular Matrices A totally unimodular matrix must have every entry equals to +1,0,-1. Guassian elimination And so we see that x must be an integral solution.
Example of Totally Unimodular Matrices x is not necessarily an integral solution. is not a totally unimodular matrix,
as its determinant is equal to 2.
Totally Unimodular Matrices Primal Dual Theorem 2: If A is totally unimodular,
then both the primal and dual programs are integer programs. Transpose of A Proof: if A is totally unimodular, then so is it’s transpose.
Application 1: Bipartite Graphs Let A be the incidence matrix of a bipartite graph.
Each row i represents a vertex v(i),
and each column j represents an edge e(j).
A(ij) = 1 if and only if edge e(j) is incident to v(i). edges vertices
Application 1: Bipartite Graphs We’ll prove that the incidence matrix A of a bipartite graph is totally unimodular. Consider an arbitrary square submatrix A’ of A.
Our goal is to show that A’ has determinant -1,0, or +1. Case 1: A’ has a column with only 0. Then det(A’)=0. Case 2: A’ has a column with only one 1. By induction, A’’ has determinant -1,0, or +1.
And so does A’.
Case 3: Each column of A’ has exactly two 1. Application 1: Bipartite Graphs We can write Since the graph is bipartite, each column has one 1 in Aup and one 1 in Adown So, by multiplying +1 on the rows in Aup and -1 on the columns in Adown,
we get that the rows are linearly dependent, and thus det(A’)=0, and we’re done. +1 -1 +1 -1
Application 1: Bipartite Graphs Maximum bipartite matching Incidence matrix of a bipartite graph,
hence totally unimodular,
and so yet another proof that this LP is integral.
Application 1: Bipartite Graphs Maximum general matching The linear program for general matching does not
come from a totally unimodular matrix, and this is why Edmonds’ result is regarded as a major breakthrough.
Application 1: Bipartite Graphs Theorem 2: If A is totally unimodular,
then both the primal and dual programs are integer programs. Maximum matching <= maximum fractional matching <=
minimum fractional vertex cover <= minimum vertex cover Theorem 2 show that the first and the last inequalities are equalites.
The LP-duality theorem shows that the second inequality is an equality.
And so we have maximum matching = minimum vertex cover.
Comments