Auction Matching Algorithm

The auction matching algorithm due to Demange, Gale, and Sotomayor solves the problem of finding a maximum weighted matching in a weighted, bipartite graph. Albeit its simplicity, the algorithm is known to a much lesser extend than, e.g., the Hungarian method.

Algorithm description

        \begin{algorithm}
        \caption{Auction Matching}
        \begin{algorithmic}
        \Comment{\textbf{Input:} Bipartite weighted graph with $n_b$ bidders (left side) and $n_g$ goods (right side). 
        Matrix $w_{ij}$ representing the weights.
        \textbf{Output:} $M = \{ (\text{owner}_j, j) \mid 1 \leq j \leq n_g, \text{owner}_j \neq null  \}$}
        \STATE For each good $j$, set $p_j \leftarrow 0$ and $\textnormal{owner}_j \leftarrow null$
        \STATE Add all bidder into queue $Q$
        \STATE Set $\delta = \frac{1}{n_{\text{b}}} + 1$
        \WHILE{$Q$ is not empty}
            \STATE Take a bidder $i$ from $Q$
            \STATE Choose $j$ such that $w_{ij} - p_j$ is maximal (break ties arbitrarily)
            \IF{$w_{ij} - p_j > 0$}
                \STATE add $\text{owner}_j$ to $Q$
                \STATE $\text{owner}_j \leftarrow i$
                \STATE $p_j \leftarrow p_j + \delta$
            \ENDIF
        \ENDWHILE

        \end{algorithmic}
        \end{algorithm}
    

Visualization

In the following we go through a little example input given in the matrix in the bottom left (bidders on top, goods to the left). Click on the canvas (or press any key after having focus on the canvas) to step through the algorithm step by step. In each step, you will first see which bidder is going to bid on a good. The current price of each good is shown to the right of each good. The next click will show the assigned good for the bidder, and start the next round. In the matrix to the bottom right, the price is substracted from each weight such that it's clear which good a bidder is going to bid on.
At the moment, you can only change the input by manually editing the HTML file.

Martin Aumüller, 2013.