By. Sushil Bikhchandani, Sven de Vries, James Schummer & Rakesh V. Vohra
Based on the relationship between dual variables and sealed-bid Vickrey auction payments (established by Bikhchandani and Ostroy), we consider simpler, specific formulations for various environments. For some of those formulations, we interpret primal-dual algorithms as ascending auctions implementing the Vickrey payments. We focus on three classic optimization problems: assignment, matroid, and shortest-path problems.
No comments:
Post a Comment