Alexander Kress
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: akress@cs.toronto.edu
Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
We investigate the design of iterative, limited-precision mechanisms
for single-good auctions with dominant strategy equilibria. Our aim
is to design mechanisms that minimize the number of bits required
to determine approximately optimal allocations by sequentially asking
bidders to reveal their valuations with increasing precision, and
limiting participation to those bidders who might win. We prove several
necessary conditions that severely restrict the space of mechanisms
satisfying our criteria. We also study empirically the optimization
of the parameters of our sequential mechanisms, and how number of
bidders and cost of communication impact expected amount of
communication, expected loss in welfare, and other measures. Finally,
we show that incremental limited-precision
mechanisms offer advantages over fixed, single-shot mechanisms.
Working paper, 2004
Return to List of Papers