- Title Pages
- Dedication
- Foreword
- Acknowledgements
- Introduction to Combinatorial Auctions
-
1 The Lovely but Lonely Vickrey Auction -
2 Iterative Combinatorial Auctions -
3 Ascending Proxy Auctions -
4 Simultaneous Ascending Auctions -
5 The Clock-Proxy Auction: A Practical Combinatorial Auction Design -
6 PAUSE: A Computationally Tractable Combinatorial Auction -
7 Pseudonymous Bidding in Combinatorial Auctions -
8 From the Assignment Model to Combinatorial Auctions -
9 Bidding Languages for Combinatorial Auctions -
10 Preference Elicitation in Combinatorial Auctions -
11 The Communication Requirements of Combinatorial Allocation Problems -
12 The Winner Determination Problem -
13 Tractable Cases of the Winner Determination Problem -
14 Optimal Winner Determination Algorithms -
15 Incentive Compatibility in Computationally Feasible Combinatorial Auctions -
16 Noncomputational Approaches to Mitigating Computational Problems in Combinatorial Auctions -
17 Observations and Near-Direct Implementations of the Ascending Proxy Auction -
18 A Test Suite for Combinatorial Auctions -
19 Empirical Hardness Models for Combinatorial Auctions -
20 Auctions for the Safe, Efficient, and Equitable Allocation of Airspace System Resources -
21 Combinatorial Auctions for Truckload Transportation -
22 Auctioning Bus Routes: The London Experience -
23 Industrial Procurement Auctions - Combinatorial Auction Glossary
- Contributors
- Author Index
- Subject Index
The Winner Determination Problem
The Winner Determination Problem
- Chapter:
- (p.297) 12 The Winner Determination Problem
- Source:
- Combinatorial Auctions
- Author(s):
Daniel Lehmann
Rudolf Müller
Tuomas Sandholm
- Publisher:
- The MIT Press
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.
Keywords: winner determination problem, mathematical programming models, integer linear programming, bidding languages, approximation algorithms, polynomial time algorithm
MIT Press Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
Please, subscribe or login to access full text content.
If you think you should have access to this title, please contact your librarian.
To troubleshoot, please check our FAQs, and if you can't find the answer there, please contact us.
- Title Pages
- Dedication
- Foreword
- Acknowledgements
- Introduction to Combinatorial Auctions
-
1 The Lovely but Lonely Vickrey Auction -
2 Iterative Combinatorial Auctions -
3 Ascending Proxy Auctions -
4 Simultaneous Ascending Auctions -
5 The Clock-Proxy Auction: A Practical Combinatorial Auction Design -
6 PAUSE: A Computationally Tractable Combinatorial Auction -
7 Pseudonymous Bidding in Combinatorial Auctions -
8 From the Assignment Model to Combinatorial Auctions -
9 Bidding Languages for Combinatorial Auctions -
10 Preference Elicitation in Combinatorial Auctions -
11 The Communication Requirements of Combinatorial Allocation Problems -
12 The Winner Determination Problem -
13 Tractable Cases of the Winner Determination Problem -
14 Optimal Winner Determination Algorithms -
15 Incentive Compatibility in Computationally Feasible Combinatorial Auctions -
16 Noncomputational Approaches to Mitigating Computational Problems in Combinatorial Auctions -
17 Observations and Near-Direct Implementations of the Ascending Proxy Auction -
18 A Test Suite for Combinatorial Auctions -
19 Empirical Hardness Models for Combinatorial Auctions -
20 Auctions for the Safe, Efficient, and Equitable Allocation of Airspace System Resources -
21 Combinatorial Auctions for Truckload Transportation -
22 Auctioning Bus Routes: The London Experience -
23 Industrial Procurement Auctions - Combinatorial Auction Glossary
- Contributors
- Author Index
- Subject Index
