Internet auction servers have a history of breaking down when a large number of
accesses are made by users simultaneously, i.e., under peak load. In this paper
we develop algorithms for efficiently processing bids in a single item, N unit
(N >= 1) open cry auction for a large class of winner determination rules.
Existing techniques consider all previously submitted bids along with the new
arrivals to update the current set of winners. We propose that at most N
`potential winner bids' amongst the previously submitted bids need to be used for
such updates, thus significantly reducing the computation time and memory
requirements. This is crucial when a large number of auctions are being conducted
simultaneously. For a commonly used greedy auction rule we show that the expected
number of potential winner bids may be much less than N under reasonable
probabilistic assumptions. Another advantage of our approach vis-a-vis existing
approaches is that it is amenable to distributed bid processing.
By: Achal Bassamboo, Manish Gupta, Sandeep Juneja
Published in: RI00027 in 2000
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .