A Dynamic Unit-Demand Auction Mechanism Supporting Bid Revision

Computing & Wireless : Application Software

Available for licensing


  • C. Greg Plaxton , Computer Science
  • Chinmayi Krishnappa , Computer Science

Background/unmet need

Online auctions have become increasingly popular over the last decade in both domestic and overseas markets. The overwhelming majority of online auctions are single-item auctions: multiple bidders bid to win a single item. In contrast, the field of combinatorial auction design, which enjoys a rich history in the academic literature, is concerned with the sale of multiple items in a single auction. In such auctions, bidders are not limited to submitting single-item bids; for example, some combinatorial auctions permit bids on bundles of items.

Many different combinatorial auctions have been studied in the literature. However, auctions involving multiple items, and especially auctions involving multiple distinct items, are not widely encountered in practice. Significant deterrents to the widespread adoption of combinatorial auctions include increased bid complexity and the computational difficulty of determining a suitable allocation and pricing of the items.

Invention Description

A unit-demand auction is a restricted kind of combinatorial auction in which a bidder is allowed to make a separate offer on each of a number of items, with the guarantee that at most one of these offers will be accepted. We propose a novel set rules for running a unit-demand auction. Our auction is dynamic, meaning that it proceeds in rounds. In each round, new bid data (bid revision requests and new bids) is received, and an update rule is applied to adjust the tentative outcome (allocation and pricing). The tentative outcome is made public at the end of each round.

The update rule associated with the present invention is shown to satisfy a number of desirable mathematical properties. These properties make the proposed auction attractive for practical use.


  • The update rule strikes an appropriate balance between competing considerations related to efficiency, truthfulness, scalability, and privacy preservation
  • Efficiency: Optimizes the allocation of items to bidders, leading to increased seller revenue and buyer satisfaction
  • Truthfulness: Limits the ability of a bidder to gain an advantage through strategic, as opposed to straightforward, bidding
  • Scalability: Computationally fast, thereby allowing for real-time support of auctions with large numbers of bidders and items
  • Privacy Preservation: Provides strong guarantees concerning the secrecy of tentatively allocated bids


  • The auction is ascending price: the tentative price of an item cannot decrease from one round to the next.
  • The dynamic price feedback enables bidders to concentrate their value discovery efforts on the most relevant items.
  • The bidding interface supports arbitrary bid revision by tentatively allocated bidders.
  • The update rule generalizes the bidding semantics of popular single-item auction sites, thereby allowing for seamless integration with such sites.

Market potential/applications

Online auction sites and software companies