Auction algorithm

The term "auction algorithm" applies to several variations of a combinatorial optimization algorithm which solves assignment problems, and network optimization problems with linear and convex/nonlinear cost. An auction algorithm has been used in a business setting to determine the best prices on a set of products offered to multiple buyers. It is an iterative procedure, so the name "auction algorithm" is related to a sales auction, where multiple bids are compared to determine the best offer, with the final sales going to the highest bidders.

The original form of the auction algorithm is an iterative method to find the optimal prices and an assignment that maximizes the net benefit in a bipartite graph, the maximum weight matching problem (MWM). This algorithm was first proposed by Dimitri Bertsekas in 1979. Detailed analysis and extensions to more general network optimization problems (ε-relaxation in 1986, and network auction in 1992) are provided in his network optimization books Linear Network Optimization 1991, and Network Optimization: Continuous and Discrete Models 1998. The auction algorithm has excellent computational complexity, as given in these books, and is reputed to be among the fastest for solving single commodity network optimization problems. In addition, the original version of this algorithm is known to possess a distributed nature particularly suitable for distributed systems, since its basic computational primitives (bidding and auctioning) are localized rather than relying on queries of global information. However, the original version that is intrinsically distributable has a pseudo-polynomial time complexity, which means that the running time depends on the input data pattern. Later versions have improved the time complexity to the state-of-the-art level by using techniques such as ε-scaling (also discussed in the original 1979 paper) but at the sacrifice of undermining its distributed characteristics. In order to retain the distributed nature and also attain a polynomial time complexity, recently some researchers from the multi-agent community have been trying to improve the earlier version of the auction algorithm by switching to a different economic model, namely, from the selfish bidders' perspective to a merchant’s point of view, where the merchant of a market adjusts the article prices in order to quickly clear the inventory.

...
Wikipedia