The DOI matches its Crossref record; 69 of the 69 references it cites were found in a registry or an index.
Combinatorial Auctions: A Survey
Abstract
Many auctions involve the sale of a variety of distinct assets. Examples are airport time slots, delivery routes, network routing, and furniture. Because of complementarities or substitution effects between the different assets, bidders have preferences not just for particular items but for sets of items. For this reason, economic efficiency is enhanced if bidders are allowed to bid on bundles or combinations of different assets. This paper surveys the state of knowledge about the design of combinatorial auctions and presents some new insights. Periodic updates of portions of this survey will be posted to this journal's Online Supplements web page at http://joc.pubs.informs.org/OnlineSupplements.html
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERS
Vickrey, W. (1961) · The Journal of Finance · doi:10.1111/j.1540-6261.1961.tb02789.x · Cited by 7,722
Myerson, R. B. (1981) · Mathematics of Operations Research · doi:10.1287/moor.6.1.58 · Cited by 5,920
Linear Programming and Extensions
Dantzig, G. (1963) · RAND Corporation eBooks · doi:10.7249/r366 · Cited by 5,755
Theory of Linear and Integer Programming
Letchford, A. N., & Schrijver, A. (2000) · The Journal of the Operational Research Society · doi:10.2307/253980 · Cited by 5,515
Integer and Combinatorial Optimization
Williams, H. P., Nemhauser, G. L., & Wolsey, L. A. (1990) · Journal of the Operational Research Society · doi:10.2307/2583737 · Cited by 5,485
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Groves, T. (1973) · Econometrica · doi:10.2307/1914085 · Cited by 3,284
Multipart pricing of public goods
Clarke, E. H. (1971) · Public Choice · doi:10.1007/bf01726210 · Cited by 3,246
Integer and Combinatorial Optimization
Nemhauser, G., & Wolsey, L. (1988) · Wiley eBooks · doi:10.1002/9781118627372 · Cited by 3,176
Linear Programming and Extensions
Dantzig, G. (1963) · Princeton University Press eBooks · doi:10.1515/9781400884179 · Cited by 2,713
Theory of Linear and Integer Programming
Smith, D. K. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.94 · Cited by 2,708
Branch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219
A Linear Programming Approach to the Cutting-Stock Problem
Gilmore, P. C., & Gomory, R. E. (1961) · Operations Research · doi:10.1287/opre.9.6.849 · Cited by 2,024
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Job Matching, Coalition Formation, and Gross Substitutes
Kelso, A. S., & Crawford, V. P. (1982) · Econometrica · doi:10.2307/1913392 · Cited by 1,307
A probabilistic heuristic for a computationally difficult set covering problem
Feo, T. A., & Resende, M. G. C. (1989) · Operations Research Letters · doi:10.1016/0167-6377(89)90002-3 · Cited by 1,065
Computationally Manageable Combinational Auctions
Rothkopf, M. H., Pekeč, A., & Harstad, R. M. (1998) · Management Science · doi:10.1287/mnsc.44.8.1131 · Cited by 1,024
What Really Matters in Auction Design
Klemperer, P. (2002) · Journal of Economic Perspectives · doi:10.1257/0895330027166 · Cited by 977
Demand Reduction and Inefficiency in Multi-Unit Auctions
Ausubel, L. M., Cramton, P., Pycia, M., Rostek, M., & Weretka, M. (2014) · The Review of Economic Studies · doi:10.1093/restud/rdu023 · Cited by 800
Privacy preserving auctions and mechanism design
Naor, M., Pinkas, B., & Sumner, R. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337028 · Cited by 753
An Efficient Ascending-Bid Auction for Multiple Objects
Ausubel, L. M. (2004) · American Economic Review · doi:10.1257/0002828043052330 · Cited by 727
On the facial structure of set packing polyhedra
Padberg, M. W. (1973) · Mathematical Programming · doi:10.1007/bf01580121 · Cited by 596
A Combinatorial Auction Mechanism for Airport Time Slot Allocation
Rassenti, S., & Bulfin, R. L. (1991) · Cambridge University Press eBooks · doi:10.1017/cbo9780511528354.035 · Cited by 583
A Combinatorial Auction Mechanism for Airport Time Slot Allocation
Rassenti, S. J., Smith, V. L., & Bulfin, R. L. (1982) · The Bell Journal of Economics · doi:10.2307/3003463 · Cited by 547
Solving Airline Crew Scheduling Problems by Branch-and-Cut
Hoffman, K. L., & Padberg, M. (1993) · Management Science · doi:10.1287/mnsc.39.6.657 · Cited by 537
Bidding and allocation in combinatorial auctions
Nisan, N. (2000) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/352871.352872 · Cited by 534
Efficient Design with Interdependent Valuations
Jéhiel, P., & Moldovanu, B. (2001) · Econometrica · doi:10.1111/1468-0262.00240 · Cited by 469
Handbook of Telecommunications Economics
Cave, M. E. (2003) · info · doi:10.1108/14636690310495265 · Cited by 449
Balas, E., & Padberg, M. W. (1976) · SIAM Review · doi:10.1137/1018115 · Cited by 449
Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches
Fujishima, Y., Leyton‐Brown, K., & Shoham, Y. (1999) · International Joint Conference on Artificial Intelligence · Cited by 440
Auction Protocols for Decentralized Scheduling
Wellman, M. P., Walsh, W. E., Wurman, P. R., & MacKie-Mason, J. K. (2001) · Games and Economic Behavior · doi:10.1006/game.2000.0822 · Cited by 429
The Biggest Auction Ever: The Sale of the British 3G Telecom Licences
Binmore, K., & Klemperer, P. (2002) · The Economic Journal · doi:10.1111/1468-0297.00020 · Cited by 409
Iterative Combinatorial Auctions: Theory and Practice
Parkes, D. C., & Ungar, L. (2000) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 360
Approximating maximum independent sets by excluding subgraphs
Boppana, R., & Halldórsson, M. M. (1992) · BIT · doi:10.1007/bf01994876 · Cited by 359
(1998) · Choice Reviews Online · doi:10.5860/choice.35-5705 · Cited by 343
An Algorithm for Optimal Winner Determination in Combinatorial Auctions
Sandholm, T. (1999) · Open Scholarship Institutional Repository (Washington University in St. Louis) · doi:10.7936/k74j0cb1 · Cited by 325
Computationally feasible VCG mechanisms
Nisan, N., & Ronen, A. (2000) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/352871.352898 · Cited by 322
Linear Network Optimization: Algorithms and Codes.
Wagner, D. K., & Bertsekas, D. P. (1993) · Mathematics of Computation · doi:10.2307/2153140 · Cited by 321
Bikhchandani, S., & Ostroy, J. M. (2002) · Journal of Economic Theory · doi:10.1006/jeth.2001.2957 · Cited by 306
Competitive Equilibrium in an Exchange Economy with Indivisibilities
Bikhchandani, S., & Mamer, J. W. (1997) · Journal of Economic Theory · doi:10.1006/jeth.1996.2269 · Cited by 295
The English Auction with Differentiated Commodities
Gül, F., & Stacchetti, E. S. (2000) · Journal of Economic Theory · doi:10.1006/jeth.1999.2580 · Cited by 293
The Economics of Multidimensional Screening
Rochet, J.-C., & Stole, L. A. (2010) · Advances in Economics and Econometrics · doi:10.1017/cbo9780511610240.006 · Cited by 289
Allocating Uncertain and Unresponsive Resources: An Experimental Approach
Banks, J. S., Ledyard, J. O., & Porter, D. P. (1989) · The RAND Journal of Economics · doi:10.2307/2555648 · Cited by 284
A New and Improved Design for Multiobject Iterative Auctions
Kwasnica, A. M., Ledyard, J. O., Porter, D., & DeMartini, C. (2005) · Management Science · doi:10.1287/mnsc.1040.0334 · Cited by 282
An Efficient Dynamic Auction for Heterogeneous Commodities
Ausubel, L. M. (2006) · American Economic Review · doi:10.1257/aer.96.3.602 · Cited by 272
Behavior in Multi-Unit Demand Auctions: Experiments with Uniform Price and Dynamic Vickrey Auctions
Kagel, J. H., & Levin, D. (2001) · Econometrica · doi:10.1111/1468-0262.00197 · Cited by 260
The First Use of a Combined-Value Auction for Transportation Services
Ledyard, J. O., Olson, M., Porter, D., Swanson, J. A., & Torma, D. P. (2002) · Interfaces · doi:10.1287/inte.32.5.4.30 · Cited by 249
Truth Revelation in Rapid, Approximately Efficient Combinatorial Auctions
Lehmann, D. J., O'Callaghan, L., & Shoham, Y. (n.d.) · Cited by 223
i Bundle: an efficient ascending price bundle auction
Parkes, D. C. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337032 · Cited by 215
On combinatorial auction and Lagrangean relaxation for distributed resource scheduling
Kutanoğlu, E., & Wu, S. D. (1999) · IIE Transactions · doi:10.1080/07408179908969883 · Cited by 194
A characterization of efficient, bayesian incentive compatible mechanisms
Williams, S. R. (1999) · Economic Theory · doi:10.1007/s001990050286 · Cited by 180
Mutually Destructive Bidding: The FCC Auction Design Problem
Bykowsky, M. M., Cull, R. J., & Ledyard, J. O. (2000) · Journal of Regulatory Economics · doi:10.1023/a:1008122015102 · Cited by 171
Linear Network Optimization: Algorithms and Codes
Boffey, T. B., & Bertsekas, D. P. (1994) · Journal of the Operational Research Society · doi:10.1057/jors.1994.70 · Cited by 156
Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics
Gonen, R., & Lehmann, D. J. (2000) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/352871.352873 · Cited by 148
Efficient Mechanism DesignPreprint
Krishna, V., & Perry, M. (1997) · RePEc: Research Papers in Economics · Cited by 133
Linear Programming and Vickrey Auctions
Bikhchandani, S., de Vries, S., Schummer, J., & Vohra, R. (2002) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4684-9277-4_6 · Cited by 130
Self-citationCovering, Packing and Knapsack Problems
Padberg, M. W. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70831-8 · Cited by 110
A k BA: a progressive, anonymous-price combinatorial auction
Wurman, P. R., & Wellman, M. P. (2000) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/352871.352874 · Cited by 106
Hobbs, B. F., Rothkopf, M. H., Hyde, L. C., & O’Neill, R. P. (2000) · Journal of Regulatory Economics · doi:10.1023/a:1008151712010 · Cited by 86
Preventing Strategic Manipulation in Iterative Auctions: Proxy Agents and Price-Adjustment
Parkes, D. C., & Ungar, L. (2000) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 85
On the facial structure of the set covering polytope
Sassano, A. (1989) · Mathematical Programming · doi:10.1007/bf01587087 · Cited by 84
A column generation algorithm for bandwidth packing
Parker, M., & Ryan, J. (1993) · Telecommunication Systems · doi:10.1007/bf02109857 · Cited by 75
Robustness of the Incentive Compatible Combinatorial Auction
Isaac, R. M., & James, D. (2000) · Experimental Economics · doi:10.1007/bf01669206 · Cited by 69
An Optimal Auction for Complements
Levin, J. (1997) · Games and Economic Behavior · doi:10.1006/game.1997.0534 · Cited by 64
An Auction Method for Course Registration
Graves, R. L., Schrage, L. E., & Sankaran, J. K. (1993) · INFORMS Journal on Applied Analytics · doi:10.1287/inte.23.5.81 · Cited by 49
On the Greedy Heuristic for Continuous Covering and Packing Problems
Fisher, M. L., & Wolsey, L. A. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603059 · Cited by 48
On the Complexity of Set Packing Polyhedra
Padberg, M. W. (1977) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70750-7 · Cited by 46
Rao, M. R. (2014) · Chapman & Hall/CRC eBooks · doi:10.1201/b16812-16 · Cited by 40
Bayesian incentive compatible mechanisms
Page, F. H. (1992) · Economic Theory · doi:10.1007/bf01212474 · Cited by 25
Cited by
Nisan, N., & Ronen, A. (2001) · Games and Economic Behavior · doi:10.1006/game.1999.0790 · Cited by 1,331
Consensus-Based Decentralized Auctions for Robust Task Allocation
Choi, H.-L., Brunet, L., & How, J. P. (2009) · IEEE Transactions on Robotics · doi:10.1109/tro.2009.2022423 · Cited by 1,128
Roth, A. E. (2002) · Econometrica · doi:10.1111/1468-0262.00335 · Cited by 1,004
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., & Nisan, N. (2006) · Games and Economic Behavior · doi:10.1016/j.geb.2005.02.006 · Cited by 471
On agent-mediated electronic commerce
He, M., Jennings, N. R., & Leung, H.-F. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1209014 · Cited by 389
Metadata
- Authors
- de Vries, S., & Vohra, R. V.
- Venue
- INFORMS Journal on Computing
- Published
- 2003-08
- Volume
- 15
- Issue
- 3
- Pages
- 284-309
- ISSN
- 0899-1499 (ISSN-L)
- 1091-9856
- 1526-5528
- OpenAlex
- W2110383956
- Cited by
- 985
- References
- 69
- FWCI
- 90.24
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.