The communication complexity of private value single item auctions

In this paper we present a new auction, the bisection auction, that can be used for the sale of a single indivisible object. We discuss the issue concerning the information revelation requirement of this auction and the associated amount of data that needs to be transmitted. We show that in the truthtelling equilibrium the bisection auction is economical in its demand for information on the valuations of the players. It requires the players to transmit less information bits to the auctioneer than the Vickrey and English auctions. In particular, we prove that for integer valuations uniformly distributed on the interval [0,L) the bisection auction of n players requires in expectation transmission of at most 2n + log L information bits by the players. Compared with the corresponding number in the Vickrey auction which is n log L, and in the English auction which is on average at least (1/3) nL, the bisection auction turns out to be the best performer.