Sets in Excess Demand in Ascending Auctions with Unit-Demand Bidders

Tommy Andersson, Lund University


This paper analyzes the problem of selling a number of indivisible items to a set of unit-demand bidders. An ascending price mechanism that utilizes so-called sets in excess demand is specified, and a number of properties of the sets in excess demand are derived. The main theoretical results establish that the mechanism terminates in a finite number of iterations and that it has an number of advantages compared to the mechanism of Demange, Gale and Sotomayor (J. Polit. Economy 94: 863--872, 1986). A large simulation study also indicates that the proposed mechanism converges significantly faster than similar algorithms.