Determining the Deadness Levels of Packages in Online Multi-unit Combinatorial Auctions

Abstract

In online iterative combinatorial auctions, the deadness level (DL) of a package serves as a tight lower bound on a fresh bid that can be meaningfully placed on the package. Computational methods exist for determining the DL values of packages in the single-unit case. But when there are multiple identical units of items, these levels are hard to determine, and no closed form expression or computational method has been proposed as yet. This note examines the properties of package DLs in the multi-unit case; it provides theoretical results with supporting illustrative examples and presents for the first time an exact method for computing DL values. This could help to promote more widespread use in industry of such online auctions.