Noam Nisan
- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0010
- Subject:
- Society and Culture, Technology and Society
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 ...
More
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.Less
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.
Peter Cramton, Yoav Shoham, and Richard Steinberg (eds)
- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- book
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.001.0001
- Subject:
- Society and Culture, Technology and Society
The study of combinatorial auctions—auctions in which bidders can bid on combinations of items or “packages”—draws on the disciplines of economics, operations research, and computer science. This ...
More
The study of combinatorial auctions—auctions in which bidders can bid on combinations of items or “packages”—draws on the disciplines of economics, operations research, and computer science. This book integrates these three perspectives, offering a survey of developments in combinatorial auction theory and practice. Combinatorial auctions (CAs), by allowing bidders to express their preferences more fully, can lead to improved economic efficiency and greater auction revenues. However, challenges arise in both design and implementation. This book addresses each of these challenges. After describing and analyzing various CA mechanisms, it addresses bidding languages and questions of efficiency. Possible strategies for solving the computationally intractable problem of how to compute the objective-maximizing allocation (known as the winner determination problem) are considered, as are questions of how to test alternative algorithms. The book discusses five important applications of CAs: spectrum auctions, airport takeoff and landing slots, procurement of freight transportation services, the London bus routes market, and industrial procurement.Less
The study of combinatorial auctions—auctions in which bidders can bid on combinations of items or “packages”—draws on the disciplines of economics, operations research, and computer science. This book integrates these three perspectives, offering a survey of developments in combinatorial auction theory and practice. Combinatorial auctions (CAs), by allowing bidders to express their preferences more fully, can lead to improved economic efficiency and greater auction revenues. However, challenges arise in both design and implementation. This book addresses each of these challenges. After describing and analyzing various CA mechanisms, it addresses bidding languages and questions of efficiency. Possible strategies for solving the computationally intractable problem of how to compute the objective-maximizing allocation (known as the winner determination problem) are considered, as are questions of how to test alternative algorithms. The book discusses five important applications of CAs: spectrum auctions, airport takeoff and landing slots, procurement of freight transportation services, the London bus routes market, and industrial procurement.
Tuomas Sandholm
- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0015
- Subject:
- Society and Culture, Technology and Society
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 ...
More
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.Less
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.
Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm
- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0013
- Subject:
- Society and Culture, Technology and Society
This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical ...
More
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.Less
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.
Peter Cramton, Yoav Shoham, and Richard Steinberg
- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0001
- Subject:
- Society and Culture, Technology and Society
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 ...
More
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.Less
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.
