Auction algorithm for the assignment problem

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 $B \times I$ , where $B$ represents buyers and $I$ represents items, with each edge $(i,j)$ having an nonnegative weight $v_{ij}$ representing the value Buyer $i$ places on Item $j$ .

A matching from $B$ to $I$ is a function $M:B \rightarrow I$ such that for all $i\neq j\in B$ , $M(i)\neq M(j)$ or $M(i)=M(j)=\emptyset$ .

The assignment problem is simply to find a matching function $M$ such that its valuation $\sum_{i\in B} v_{i,M(i)}$ is maximized. (Since it is possible that some buyers may not be assigned an item, we write $v_{i,\emptyset}=0$ 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 $Q$ represents the list of unmatched buyers, which is initialized to $B$ . 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

Consider the case when $|I|=1$ , where a group of buyers is being matched for a single item. Clearly whoever values the item the most will win the auction, but at what price? From the highlighted line in the above pseudocode, it is readily seen that a buyer drops out when the price is above his value. Thus, the final sale price is at most the second highest valuation among all buyers (plus $O(\epsilon)$ ) . Hence, the above algorithm can be seen as a generalization of a second-price auction for multiple items.

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 $C = \max_{i,j} v_{i,j}$ , we have

AUCTION( $\epsilon$ ) terminates within $(C/\epsilon + 1) |I|$ iterations.

To see this, fix an item $j$ . Note that before each increment to $p_j$ , the inequality $p_j \leq v_{ij} \leq C$ must hold. So the final price must satisfy $p_j \leq C + \epsilon$ . The number of iterations in the loop is at most the number of times a price is incremented, which is $(C/\epsilon + 1) |I|$ .

A trivial implementation that finds the item with maximum value takes linear time, leading to an implementation with a running time of $O(C|I|^2/\epsilon)$ . A faster algorithm can be achieved by maintaining $|B|$ priority queues of size $|I|$ , one for each buyer, as follows: Each time the price of Item $j$ is incremented, $d_j$ priority queues are updated, where $d_j$ is the number of buyers who are connected to Item $j$ in the bipartite graph. Then the total number of priority queue updates is

$\sum_{j \in I} d_j \mbox{(\# of increments to $p_j$)} \leq \sum_{j \in I} d_j (C / \epsilon + 1).$

By the handshaking lemma, $\sum_{j \in I} d_j = 2m$ , where $m$ is the number of edges in the bipartite graph. Thus, a priority queue-based implementation takes time at most $O(Cm\log|I|/\epsilon)$ .

Now we analyze the valuation produced from the matching $M$ . The proof is short and self-contained but utilizes $\epsilon$ -complementary slackness, a concept related to primal-dual method in optimization.

Let $M$ be the matching produced by AUCTION( $\epsilon$ ) and $M'$ be any matching from $B$ to $I$ . Then

$\sum_{i\in B} v_{iM(i)} \geq \sum_{i\in B} v_{iM'(i)} - \epsilon |B|.$

Since we can choose $\epsilon$ to be arbitrarily small, the theorem implies that output matching is arbitrarily close to optimal. In particular, if all the values $v_{ij}$ are binary, setting $\epsilon < 1/|B|$ 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 $i$ is $\epsilon$ -happy under $M$ if he is matched with an item that is $\epsilon$ -close to optimal, i.e., for all $j\in I$ , $v_{iM(i)} - p_{M(i)} \geq v_{ij} - p_j - \epsilon.$ For notational convenience, we will write $v_{i\emptyset}=p_{\emptyset}=0$ , so a buyer being completely out-priced (being matched with an “empty” item) is also $\epsilon$ -happy.

The key insight is that during each iteration, the algorithm preserves the loop invariant that all buyers in $B \setminus Q$ are $\epsilon$ -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 $\epsilon$ -close to being optimal. Then the previous holder of the item is added back to the queue. Since all buyers in $B$ are $\epsilon$ -happy when the algorithm terminates, we can observe that for any matching $M'$ ,

$\sum_{i\in B} \left(v_{iM(i)} - p_{M(i)}\right) \geq \sum_{i\in B} \left(v_{iM'(i)} - p_{M'(i)} - \epsilon\right).$

Re-arranging, it is easy to see that

$\sum_{i\in B} v_{iM(i)} \geq \sum_{i\in B} v_{iM'(i)} - \epsilon|B| + \sum_{i\in B}(p_{M(i)} - p_{M'(i)}).$

Thus, it suffices to show that $\sum_{i\in B}(p_{M(i)} - p_{M'(i)}) \geq 0$ . If Item $j$ is in the range of $M'$ but not $M$ , then the algorithm must have never incremented its price, so $p_j=0$ . Thus,

$\sum_{i\in B}(p_{M(i)} - p_{M'(i)}) = \sum_{j \in Range(M)\setminus Range(M')} p_j,$

which is nonnegative.

The theorem also implies that in any marketplace, there is a set of market-clearing prices, i.e., each buyer has at most one preferred item. If all the valuation are integers, then a variant of the above algorithm from the DGS paper produces a price vector that is pointwise minimal among all market-clearing prices.

Victor Chen

mathematics blog

Auction algorithm for the assignment problem

Leave a Reply Cancel reply