Auction Algorithm for Bipartite Matching

Undergraduate algorithms courses typically discuss the maximum matching problem in bipartite graphs and present algorithms that are based on the alternating paths (Hungarian) method.  This is true in the standard CLR book as well as in the newer KT book (and implicitly in the new DPV book that just gives the reduction to max-flow.)  There is an alternative auction-like algorithm originally due to Demange, Gale, and Sotomayor that is not well known in the CS community despite being even simpler.  The algorithm naturally applies also to the weighted version, sometimes termed the assignment problem, and this is how we will present it.

Input: A weighted bipartite graph, with non-negative integer weights.  We will denote the vertices on one side of the graph by B (bidders) and on the other side by G (goods).  The weight between a bidder i and a good j is denoted by .  We interpret  as quantifying the amount that bidder i values good j.

Output: A matching M with maximum total weight .  A matching is a subset of such that no bidder and no good appear more than once in it.

The special case where is the usual maximum matching problem.

Algorithm:

Initialization:

1. For each good j, set and .
2. Initialize a queue Q to contain all bidders i.
3. Fix , where  is the number of goods.

While Q is not empty do:

1. .
2. Find j that maximizes .
3. If then
   1. Enque current into Q.
   2. .
   3. .

Output: the set of for all j.

Correctness: The proof of correctness is based on showing that the algorithm gets into an “equilibrium”, a situation where all bidders “are happy”.

Definition: We say that bidder i is -happy if one of the following is true:

1. For some good j, and for all goods j’ we have that .
2. For no good j does it hold that and  for all goods j we have that that .

The key loop invariant is that all bidders, except those that are in Q, are -happy.  This is true at the beginning since Q is initialized to all bidders.  For the bidder i dequeued in an iteration, the loop exactly chooses the j that makes him happy, if such j exists, and the -error is due to the final increase in .  The main point is that this iteration cannot hurt the invariant for any other i’: any increase in for j that is not owned by i’ does not hurt the inequality while an increase for the j that was owned by i’ immediately enqueues i’.

The running time analysis below implies that the algorithm terminates, at which point Q must be happy and thus all bidders must be -happy.

Lemma: if all bidders are -happy then for every matching M’ we have that .

Before proving this lemma, we notice that this implies the correctness of the algorithm since by our choice of , we have that , and as all weights are integers, this implies that our matching does in fact have maximum weight.

We now prove the lemma.  Fix a bidder i, let j denote the good that he got from the algorithm and let j’ be the good he gets in M’ (possibly j=null or j’=null).  Since i is happy we have that (with a notational convention that and , which takes care also of case 2 in the definition of happy)  Summing up over all i we get .  Now notice that since both the algorithm and M’ give matchings, each j appears at most once on the left hand side and at most once on the right hand side.  More over if some j does not appear on the left hand side then it was never picked by the algorithm and thus .  Thus when we subtract from both sides of the inequality, the LHS becomes the LHS of the inequality in the lemma and the RHS becomes at most the RHS of the inequality in the lemma.  QED.

Running Time Analysis:

Each time the main loop is repeated, some is increased by or some bidder is removed from Q forever.  No can ever increase once its value is above .  It follows that the total number of iterations of the main loop is at most where n is the total number of vertices (goods+bidders).  Each loop can be trivially implemented in O(n) time, giving total running time of , which for the unweighted case, C=1, matches the running time of the basic alternating paths algorithm on dense graphs.

For non-dense graphs, with only edges (where an edge is a non-zero ), we can improve the running time by using a better data structure.  Each vertex maintains a priority que of goods ordered according to the value of .  Whenever some is increased, all bidders that have an edge to this j need to update the value in the priority queue.  Thus an increase in requires priority queue operations, where is the degree of j. Since each is increased at most times, and since  we get a total of O(Cmn) priority queue operations.  Using a heap to implement the priority queue takes per operation.  However, for our usage, an implementation using an array of linked lists gives O(1) amortized time per operation: entry t of the array contains all j such that , updating the value of j requires moving it down one place in the array, and finding the maximum is done by marching down the array to find the next non empty entry (this is the only amortized part).  All in all, the running time for the unweighted case is O(mn).

Additional comments:

• As shown by DGS, a similar procedure terminates with close to VCG prices, which are also the point-wise minimum equilibrium prices.
• The algorithm was presented for the assignment problem where bidders never desire more than a single item.  It does work more generally as long as bidders are “gross substitutes”.
• The algorithm, like many auctions, can be viewed as a primal-dual algorithm for the associated linear program.
• Choosing a small fixed value of, say, gives a linear time 1.01-approximation for the maximum matching.
• Choosing the value gives a matching that misses at most edges, that can then be added using alternating path computations, for a total running time of .
• Many algorithmic variants were studied by Dimitry Bertsekas.
• A wider economic context appears in this book.

Advertisements