A mathematical detour today. Will state and prove some basic results in combinatorial optimization that have applications in matching and auction theory. The first is the max-flow-min-cut theorem. I’ll use it to prove Hall’s marriage theorem as well as derive the Border-Matthews characterization of implementable interim allocation rules. It has other applications. Itai Sher, for example, uses it in the analysis of a special case of the Glazer-Rubinstein model of persuasion. Mobius et al use it in their study of capital flows in social networks (the Peruvian village paper). Olszewski and myself have a forthcoming paper where we use it to talk about team formation.
Then, its on to polymatroids which can be used to show the assignment problem retains its integrality property in the presence of additional constraints. These additional constraints arise in, for example, school choice problems. See the paper by Budish, Che, Kojima and Milgrom for a list of examples.
1. The Maximum Flow Problem
Let be a network with vertex set and edge set . Assume, for convenience, that edges are `bi-directional’. In there are two special vertices. One called , the source and the other , the sink. Each edge has a capacity that is the maximum flow that can traverse (in either direction). Assume is integral for all . To avoid trivialities assume at least one path in from to .
The maximum flow problem is to find the maximum amount of flow that can be sent from , through the network, to . That there is only source-sink pair is not a restriction. An instance with multiple sources and sinks can be converted into one with a single pair through the introduction of a dummy super source and super sink.
A cut in is a set of edges whose removal disconnects from . Equivalently, a cut is a set of edges that intersects every path from to in . A cut can also be defined in terms of a partition of into two sets and such that and . A cut would be the set of edges with one endpoint in and the other in . The capacity of a cut is the sum of the capacities of the edges in the the cut.
The maximum flow is clearly bounded above by the capacity of any cut. Indeed, the max flow must be bounded above by the minimum capacity cut. Remarkably, this upper bound is tight, i.e., the max flow is the min cut. Note that the min cut must be integer valued but it is not obvious that the maximum flow should be integer valued.
We can formulate the problem of finding a maximum flow as a linear program. To do this, let denote the amount of flow on edge from to . Then, the maximum flow problem can be expressed as follows:
The first constraint says that the flow, , out of must use edges of the form . The second constraint imposes flow conservation in each vertex, i.e., flow in must equal flow out. The third constraint ensures that the total flow entering must use edges of the form .
The constraint matrix is a network matrix and so TUM. You can see this by noting that each variable appears in at most two constraints with opposite sign. Once as an `incoming’ edge and once as an `outgoing’ edge. The variable also appears exactly twice with opposite sign.
TUM of the constraint matrix means that the flow on each edge and as well as the amount of flow is integer valued.
Theorem 1 The maximum flow is equal to the capacity of the minimum cut.
Proof: Let be the value of the maximum flow. By LP duality:
To see where it came from, observe that we have one dual variable for each and one variable for each . Recall the bidirectional assumption. So, is different from . Thus one should have two constraints for each pair :
I have simply folded these into a single constraint . Notice that at optimality at most one of and can be positive which is why this folding is legitimate.
Notice also, that we can WLOG fix and . This allows us to right the dual as:
By TUM of the constraint matrix, we know that an optimal solution to this program that is integral exists. An integer solution to this program corresponds to a cut. Let and . Observe
which is the capacity of the cut associated with the partition. It is easy to see that every cut corresponds to a feasible integer solution to the program.
I can’t resist offering a probabilistic proof due to Bertsimas, Teo and myself. Let be an optimal solution to the dual program. Suppose, for a contradiction that it is fractional. Consider the following randomization scheme:
- Position node in according to the value of .
- Generate a single random variable uniformly distributed in . Round all nodes with to and all nodes with to .
- Set .
The randomization scheme clearly returns a feasible cut. More importantly the randomization scheme defines a probability distribution over the set of cuts. Now lets compute the expected capacity of the cut generated by the randomization scheme:
Thus, the expected capacity of our random cut is the same as the optimal objective function value. Because the randomization scheme is a distribution over cuts, it follows that there must be a cut with capacity equal to .
1.1. Hall Marriage Theorem
Recall, that in the DGS auction from the previous session, an important step relied on the Hall Marriage theorem. Here, I will use maxflow-mincut to prove it.
Let be a bipartite graph with vertices and edge set . Suppose . Note edges run between and only. A perfect matching is a subset of edges such that each vertex is incident to exactly one edge in . A matching is a subset of edges such that each vertex is incident to at most one edge in .
For any , let be the set of neighbors of . That is .
Theorem 2 A bipartite graph, contains a perfect matching iff. for all .
Proof: This is clearly necessary. So, suppose for all and for a contradiction assume that the graph does not contain a perfect matching.
Introduce a dummy source vertex with an edge directed to each vertex in . To each edge with , assign a capacity of 1 unit. Introduce a dummy sink with an edge directed from each vertex of to . To each edge of the form assign a capacity of 1 unit. To each edge in assign a capacity of .
Consider now a maximum flow from to . By Theorem 1 we can assume the flow is integral, i.e., the flow on each edge is an integer amount. Second, it is easy to see that no edge will contain more than 1 unit of flow. Third, the set of edges, in that carry a non-zero amount of flow must be a matching. Why? No more than one unit of flow can leave any and no more than one unit of flow can enter an . Fourth, each matching corresponds to a feasible flow. Thus, the value of the maximum flow gives us the size of a maximum cardinality matching. Because we assumed no perfect matching, the value of the maximum flow must be less than . i.e., .
Now a maximum flow must equal the value of a minimum cut. Clearly, no minimum cut can contain edges in because they have infinite capacity. So, the minimum cut must consist of edges of the form and . Let and be the set of vertices incident to the edges in a minimum cut. The capacity of this cut will be . Because they form a cut, removing them from the graph would delete all paths from to . Do that.
Consider any . There cannot be a such that . If not, there would be a path . That means every neighbor of a vertex resides in . Hence, by assumption:
The Hall marriage theorem is easily generalized to something called Gale’s demand theorem. Suppose each vertex in is a demand vertex, demanding units of a homogenous good. Each vertex is a supply vertex, supplying units of that same good. Supply can be shipped to demand nodes only along the edges in . Is there a feasible way to match supply with demand? Yes, iff. for all we have
1.2. Border’s Theorem
For simplicity assume two agents, be the type space of agent 1, the type space of agent 2 and a single good. Suppose, also for simplicity, that types are independent draws. Denote by the probability of agent having type . Let the probability that the good is allocated to agent when agent 1 reports and agent 2 reports . Feasibility requires that
is an allocation rule. Denote by the interim allocation probability to agent 1when she reports . Note that
A similar expression applies for . Call an interim allocation probability implementable if there exists an allocation rule that corresponds to it. Here is the question posed originally posed by Steve Matthews (who conjectured the answer): characterize the implementable ‘s. The high level idea first. Roll up all the inequalities relating to and feasibility into matrix form:
Denote by the set of that satisfy the system above. The purely mathematical question is this: for which ‘s does there exist at least one such that ? In other words, we want to identify the set :
The set is called the reduced form. Geometrically, is just the projection of onto the -space. By the Farkas lemma, the set can be characterized in the following way. Let . is a cone. Then,
It would seem that is described by a continuum of inequalities. However, because is a cone, it suffices to consider only the generators of the cone and there are finitely many of them. The challenge now reduces to identifying the generators of . When the matrices and have suitable structure this is possible and is the case here. For convenience assume and . Here are all the inequalities:
Now some appropriate scaling:
Now a change of variables to make things nice and neat: .
This system corresponds to the flow balance conditions for a flow problem on a bipartite graph. For each profile of types introduce a supply vertex with supply . For each introduce a demand vertex with demand . From each supply vertex of the form , introduce two edges. One directed from to demand vertex ; the flow on this edge is . The other edge directed into demand vertex ; the flow on this edge is .
The first four inequalities say that the flow out of a supply vertex cannot exceed its available supply. The second four ensure that the flow into a demand vertex matches the demand.
Using this flow interpretation we can use Gale’s generalization of the Hall marriage theorem to determine when a feasible flow exists. Existence of a feasible flow means that is implementable. Let and . Then, for all such and ,
is necessary and sufficient for to be implementable. The left hand side of this inequality is the expected quantity of the good allocated to agents when their types come from and . The right hand side is the probability that at least one agent has a type in . In fact we can rewrite this inequality to read
Here, and are the complements of and .
As you will see later one can generalize this analysis to cases where the allocation rule, must satisfy additional constraints. For details see Che, Kim and Mierendorff as well as Federgruen and Groenvelt.
Let be a ground set. A real valued function defined on subsets of is
- non-decreasing if , and
- is submodular if
- is supermodular if is submodular.
Let be a submodular function on . The polytope:
is the polymatroid associated with . Notice that iff . Polymatroids arise in a number of economic settings. One that we have just discussed are the Border inequalities. Suppose a single object to allocate among bidders whose types are independent draws from the same distribution (with density ). Restrict attention to allocation rules that do not depend on the identity of the agent. Let be the interim allocation probability if an agent reports type . Then, is implementable iff.
Call the right hand side of the above and consider the change of variables :
Now is a monotone polymatroid. So, the feasible region described by the Border inequalities is a polymatroid. The theorem below tells us that every extremal interim allocation probability can be implemented as a priority rule. That is, types are assigned priorities and in any profile the good is allocated to the agent with the highest priority. This connection to priority rules is useful for analyzing optimal auctions in dynamic settings (see my survey paper on dynamic mechanism design) as well as competition between auctions (see Pai’s jmp).
Theorem 3 Let be a non-decreasing, integer valued, submodular function on with . Then, the polymatroid has all integral extreme points.
Proof: Choose a weight vector and order the elements of by decreasing weight:
let and for all . Consider the vector obtained by the following greedy procedure:
- for .
I show that Note is integral and non-negative because is non-decreasing. To verify that observe:
The dual to our optimization problem is:
To show that is an optimal primal solution we identify a dual feasible solution with an objective function value of . Set for . Set and for .
Notice that for all and is feasible in the dual because:
for all and
The dual objective function value is:
Now suppose has a fractional extreme point. Choose to be the unique weight vector that is optimized at that point. However, as shown above, every weight vector has an integral point in that optimizes it, contradiction.
If we drop the requirement that be non-decreasing then can still be solved by using the greedy algorithm because
Here which is submodular and non-decreasing. Now I describe a non-constructive proof of Theorem 3 which uses an `uncrossing’ trick that is good to know. Let be an optimal solution to the polymatroid optimization problem. Let . Then, we can assume that is laminar. If true, this means that the optimal basis in the dual is TUM. But this is also an an optimal basis for the primal. Thus, there is an optimal primal solution that is integral. Ok, suppose is not laminar. Then there exist such that . Construct a new dual solution as follows: Increase by each. Decrease , by each. This new dual solution feasible. The change in objective function value is
which cannot exceed zero by submodularity. This is the uncrossing step. Repeated applications produces an optimal dual solution which is laminar.
The following remarkable result on polymatroid intersection is due to Edmonds.
Theorem 4 Let and be non-decreasing, integer valued, submodular functions on with . Then is integral.
Proof: Pick an arbitrary integral and consider . The dual to this linear program is
Let be an optimal dual solution. Let and . By uncrossing we can assume that each of these laminar. Recall from the first session that the constraint matrix associated with can be arranged so that it has exactly one non-zero entry in each row. Similarly with . Hence, the constraint matrix formed from the concatenation of and (which is also the optimal basis) is TUM.
From the proof we get another result for free. Let and be two laminar collections on the same ground set . Consider the following polyhedron:
As long as the ‘s are integral, this polyhedron is integral.
How is this useful? Return to the SS model. For any set of edges, (of the form with and ) define to be the number of vertices in that the edges in are incident to. Similarly, define to be the number of vertices in that edges in are incident to. Note and are submodular. Here is an equivalent formulation of the problems of finding an efficient assignment:
Why is this useful? Notice, by choosing and differently we can model more constraints than just the number of edges incident to a vertex is at most 1.