  We study a class of iterative combinatorial auctions which can be viewed as
subgradient descent methods for the problem of pricing bundles to balance
supply and demand. We provide concrete convergence rates for auctions in this
class, bounding the number of auction rounds needed to reach 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, which includes standard
best-response bidding as a special case. In the second model, bidders behave
arbitrarily (even adversarially), and meaningful convergence relies on properly
designed activity rules.
