Research Article
Price Discovery in Subgradient Combinatorial Auctions
@INPROCEEDINGS{10.4108/eai.8-8-2015.2260355, author={Jacob Abernethy and S\^{e}bastien Lahaie and Matus Telgarsky}, title={Price Discovery in Subgradient Combinatorial Auctions}, proceedings={The Third Conference on Auctions, Market Mechanisms and Their Applications}, publisher={ACM}, proceedings_a={AMMA}, year={2015}, month={8}, keywords={combinatorial auction subgradient method convergence rate nonlinear pricing}, doi={10.4108/eai.8-8-2015.2260355} }- Jacob Abernethy
Sébastien Lahaie
Matus Telgarsky
Year: 2015
Price Discovery in Subgradient Combinatorial Auctions
AMMA
ICST
DOI: 10.4108/eai.8-8-2015.2260355
Abstract
We study a class of iterative combinatorial auctions which can be viewed as subgradient methods for the problem of pricing bundles to balance supply and demand. We provide concrete convergence rates for auctions in the class in the form of bounds on the number of auction rounds needed to discover clearing prices. Our analysis allows for a variety of pricing schemes, including item, bundle, and polynomial pricing, and the respective convergence rates confirm that more expressive pricing schemes come at the cost of slower convergence. We consider two models of bidder behavior. In the first model, bidders behave stochastically according to a random utility model. In the second model, bidders behave arbitrarily or even adversarially, and meaningful convergence relies on properly designed activity rules.