Bidding Languages for Combinatorial Auctions

Abstract

This chapter examines a number of convenient bidding languages for combinatorial auctions and discusses their properties. It states that the basic aim of a bidding language is to draw a balance between the goals of expressiveness and simplicity. The chapter begins with some examples of valuations, both symmetric and asymmetric, and discusses the leading paradigm for bidding languages in combinatorial auctions. It further describes the computational complexity issues associated with bidding language including expression complexity, complexity of winner determination, and complexity of evaluation. The chapter concludes with the presentation of the technical proofs for the theorems related to both the OR and XOR bidding languages.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 152 citations exist upstream.