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
.






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.
AUCTION(epsilon): Queue Q <- B for j in I: p[j] <- 0 BidirectionalMap M while !Q.isEmpty(): i <- Q.pop() j <- Find j in I maximizing v[i][j] - p[j] if v[i][j]-p[j] >= 0: if M.ContainsValue(j): Q.push(M.KeyOf(j)) 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


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.





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.








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.