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


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.