This paper deals with the implementation of an English auction on a distributed system. We assume that all messages are restricted
to bids and resignations (referred to as the limited communication assumption) and that all participants are trying to maximize
there gains (referred to as the prudence assumption). We also assume that bidders are risk-neutral, and that the underlying
communication network is complete, asynchronous and failure-free. Under these assumptions, we show that the time and communication
requirements of any auction process are 42(M2) and 42(M2 + n) respectively, where M2 denotes the second largest valuation
of a participant in the auction.
We then develop a number of distributed algorithmic implementations for English auction, analyze their time and communication
requirements, and propose an algorithm achieving optimal time and communication, i.e., meeting the above lower bounds. Finally
we discuss extensions to the case of dynamically joining participants.
Supported in part by a grant from the Israel Ministry of Science and Art.