The maximum bipartite matching is a well-known problem in graph theory, operations research, and economics. Also known by the name assignment problem, it models a marketplace with buyers and items, where every buyer has a valuation for each item, and we want to match (assign) each buyer to an item, with no item being shared. For social utility, an assignment that maximizes the total valuation is ideal.
In graph theory, the Hungarian algorithm by Kuhn produces a matching in polynomial time maximizing the total weight of the edges. Independently, Bertsekas from operations research and Demange, Gale, and Sotomayor from the economics perspective both use an underlying auction to solve the same problem. The auction provides additional intuition for this problem not transparent when using only graph-theoretic techniques. Here we describe a simple auction algorithm, largely following the presentation from this blog post.
To formulate this problem, we consider a bipartite graph , where represents buyers and represents items, with each edge having an nonnegative weight representing the value Buyer places on Item .
A matching from
is a function
such that for all
The assignment problem is simply to find a matching function such that its valuation is maximized. (Since it is possible that some buyers may not be assigned an item, we write for notational convenience.)
Below is the pseudocode of the auction algorithm. Intuitively, the algorithm is simulating a multi-item auction, where we put a price tag initialized to zero on each item. The queue represents the list of unmatched buyers, which is initialized to . In each iteration, a buyer is greedily matched with his most valued item minus the price tag. However, each time an item is matched, it becomes slightly more expensive, becoming less valuable to other buyers in future rounds.
Queue Q <- B
for j in I:
p[j] <- 0
i <- Q.pop()
j <- Find j in I maximizing v[i][j] - p[j]
if v[i][j]-p[j] >= 0:
M(i) <- j
p[j] <- p[j] + epsilon
Output M, p
Complexity. Before analyzing the running time, we first make the observation that the algorithm must terminate in finite steps. The key insight is that a buyer will not overpay for an item. In particular, writing , we have
) terminates within
To see this, fix an item . Note that before each increment to , the inequality must hold. So the final price must satisfy . The number of iterations in the loop is at most the number of times a price is incremented, which is .
A trivial implementation that finds the item with maximum value takes linear time, leading to an implementation with a running time of . A faster algorithm can be achieved by maintaining priority queues of size , one for each buyer, as follows: Each time the price of Item is incremented, priority queues are updated, where is the number of buyers who are connected to Item in the bipartite graph. Then the total number of priority queue updates is
By the handshaking lemma, , where is the number of edges in the bipartite graph. Thus, a priority queue-based implementation takes time at most .
Now we analyze the valuation produced from the matching . The proof is short and self-contained but utilizes -complementary slackness, a concept related to primal-dual method in optimization.
be the matching produced by AUCTION(
be any matching from
Since we can choose to be arbitrarily small, the theorem implies that output matching is arbitrarily close to optimal. In particular, if all the values are binary, setting implies that the algorithm terminates with a maximal matching, and its time complexity is cubic on dense graphs, on par with the Hungarian algorithm.
We say that Buyer
if he is matched with an item that is
-close to optimal, i.e., for all
For notational convenience, we will write
, so a buyer being completely out-priced (being matched with an “empty” item) is also
The key insight is that during each iteration, the algorithm preserves the loop invariant that all buyers in are -happy. To see this, note that the invariant holds vacuously true initially. During each iteration, whenever a buyer is removed from the queue, he is always matched with an item whose price (after the update) is -close to being optimal. Then the previous holder of the item is added back to the queue. Since all buyers in are -happy when the algorithm terminates, we can observe that for any matching ,
Re-arranging, it is easy to see that
Thus, it suffices to show that . If Item is in the range of but not , then the algorithm must have never incremented its price, so . Thus,
which is nonnegative.