Search Results

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.

This chapter discusses the optimal winner determination algorithm, which is used for solving the general problem where bids are not restricted. It further focuses on different fundamental design dimensions of search algorithms for winner determination, which include search formulation, search strategy, decomposition techniques, random restart techniques, and caching techniques. The chapter also discusses winner determination under fully expressive bidding languages such as XOR bidding language and OR bidding language, where substitutability is exhibited using XOR-constraints between different bids. It concludes that the various techniques it has discussed are applicable in generalized combinatorial markets, which include combinatorial reverse auctions and combinatorial exchanges.

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical programming models including integer linear programming, weighted stable set in graphs, knapsack, and matching that covers variants of the problem related to particular bidding languages is also discussed. The chapter further highlights inapproximability results, and reviews the approximation algorithm, which is a polynomial time algorithm. It concludes that the problem, which is represented as an integer program, is NP-complete and can be tackled by applying three fundamentally different approaches, which it discusses.

This book presents an integrated, comprehensive, and interdisciplinary study of combinatorial auctions (CA) in which bids are accepted for packages of items. Applications of CA in various industries including truckload transportation, bus routes, airport takeoff and landing slots, industrial procurement, and the allocation of radio spectrum for wireless communications services. The book starts with a discussion of variety of CA mechanisms including the Vickrey-Clarke-Groves mechanism, iterative combinatorial auctions, simultaneous ascending auctions, and clock-proxy auctions, and also addresses a number of challenges regarding bidding languages and questions of efficiency. Testing of solutions to the winner determination problem that have been proposed is discussed, and an assessment is made of the Combinatorial Auction Test Suite, a software package used for the prediction of the running times of algorithms for the winner determination problem. Further development of this emerging field of CA is expected with the integration of the disciplines of economics, operations research, and computer science.