Efficient winner determination techniques for internet multi-unit auctions

Achal Bassamboo, Manish Gupta, Sandeep Juneja

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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 r 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.

Original languageEnglish (US)
Title of host publicationTowards the E-Society
Subtitle of host publicationE-Commerce, E-Business, and E-Government - 1st IFIP Conference on E-Commerce, E-Business, E-Government, I3E 2001
PublisherSpringer New York LLC
Pages417-430
Number of pages14
ISBN (Print)0792375297, 9780792375296
DOIs
StatePublished - 2001
Event1st IFIP Conference on E-Commerce, E-Business, E-Government, I3E 2001 - Zurich, Switzerland
Duration: Oct 3 2001Oct 5 2001

Publication series

NameIFIP Advances in Information and Communication Technology
Volume74
ISSN (Print)1868-4238

Other

Other1st IFIP Conference on E-Commerce, E-Business, E-Government, I3E 2001
CountrySwitzerland
CityZurich
Period10/3/0110/5/01

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Efficient winner determination techniques for internet multi-unit auctions'. Together they form a unique fingerprint.

Cite this