Combinatorial Auctions: A Survey

References

• Akcoglu K., Aspnes J., DasGupta B., Kao M., Kontoghiorghes E. J., Rustem B., Siokos S. An opportunity-cost algorithm for combinatorial auctions. Applied Optimization: Computational Methods in Decision-Making, Economics and Finance (2002) (Kluwer, Dordrecht, The Netherlands) Crossref, Google Scholar
• Andersson A., Tenhunen M., Ygge F. Integer programming for combinatorial auction winner determination. Proceedings of the Fourth International Conference on Multi-Agent Systems (ICMAS00) (2000) Boston, MA:39–46Crossref, Google Scholar
• Ausubel L. M. An efficient ascending-bid auction for multiple objects. (1997) . Working Paper No. 97-06, Department of Economics, University of Maryland, College Park, MDGoogle Scholar
• Ausubel L. M. An efficient dynamic auction for heterogeneous commodities. (2000) . Working paper, Department of Economics, University of Maryland, College Park, MDGoogle Scholar
• Ausubel L. M., Cramton P. Demand reduction and inefficiency in multi-unit auctions. (1998) . Manuscript, Department of Economics, University of Maryland, College Park, MDGoogle Scholar
• Balas E., Carrera M. C. A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. (1996) 44:875–890Link, Google Scholar
• Balas E., Ceria S., Cornuéjols G. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming (1993) 58:295–324Crossref, Google Scholar
• Balas E., Padberg M. W. Set partitioning: a survey. SIAM Rev. (1976) 18:710–760Crossref, Google Scholar
• Ball M. O., Magazine M. The design and analysis of heuristics. Networks (1981) 11:215–219Crossref, Google Scholar
• Banks J. S., Ledyard J. O., Porter D. P. Allocating uncertain and unresponsive resources: an experimental approach. RAND J. of Econom. (1989) 20:1–25Crossref, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch and price: column generation for solving huge integer programs. Oper. Res. (1998) 46:316–329Link, Google Scholar
• Beasley J. E. A Lagrangian heuristic for set-covering problems. Naval Res. Logist. (1990) 37:151–164Crossref, Google Scholar
• Bertsekas D. P.Linear Network Optimization: Algorithms and Codes (1991) (MIT Press, Cambridge, MA) Google Scholar
• Bikhchandani S., Huang C.-f. The economics of treasury securities markets. J. of Econom. Perspectives (1993) 7:117–134Crossref, Google Scholar
• Bikhchandani S., de Vries S., Schummer J., Vohra R. V., Dietrich B., Vohra R. V. Linear programming and Vickrey auctions. Mathematics of the Internet: E-Auction and Markets. The IMA Volumes in Mathematics and Its Applications (2002) 127(Springer-Verlag, New York) 75–116Crossref, Google Scholar
• Bikhchandani S., Mamer J. W. Competitive equilibrium in an exchange economy with indivisibilities. J. of Econom. Theory (1997) 74:385–413Crossref, Google Scholar
• Bikhchandani S., Ostroy J. M. The package assignment model. (2001) . Manuscript, The Anderson School, UCLA, Los Angeles, CAGoogle Scholar
• Binmore K., Klemperer P. The biggest auction ever: the sale of the British 3G telecom licences. Econom. J. (2002) 112:C74–C96Google Scholar
• Boppana R. B., Halldórsson M. M. Approximating maximum independent sets by excluding subgraphs. BIT (1992) 32:180–196Crossref, Google Scholar
• Brewer P. J. Decentralized computation procurement and computational robustness in a smart market. Econom. Theory (1999) 13:41–92Crossref, Google Scholar
• Bykowsky M. M., Cull R. J., Ledyard J. O. Mutually destructive bidding: the FCC auction design problem. J. of Regulatory Econom. (2000) 17:205–228Crossref, Google Scholar
• Caplice C. G. An optimization based bidding process: A new framework for shipper-carrier relationships. (1996) . Thesis, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Clarke E. Multipart pricing of public goods. Public Choice (1971) 8:19–33Google Scholar
• Cornuéjols G., Sassano A. On the 0-1 facets of the set covering polytope. Math. Programming (1989) 43:45–56Crossref, Google Scholar
• Cramton P., Cave S. Majumdar, Vogelsang I. Spectrum auctions. In M. Handbook of Telecommunications Economics (2002) (Elsevier Science B.V., Amsterdam, The Netherlands) Google Scholar
• Crescenzi P., Kann V. A compendium of NP optimization problems. (1995) . Technical report SI/RR-95/02, Dipartimento di Scienze dell'Informazione, Università di Roma “La Sapienza,” Italy. http://www.nada.kth.se/theory/compendium/. Continuously updatedGoogle Scholar
• Cybernomics, Inc. An experimental comparison of the simultaneous multi-round auction and the CRA combinatorial auction. (2000) . http://combin.fcc.gov/98540193.pdfGoogle Scholar
• Dantzig G. B.Linear Programming and Extensions (1963) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Davenport A., Kalagnanam J., Dietrich B., Vohra R. V. Price negotiations for procurement of direct inputs. In. Mathematics of the Internet: E-Auction and Markets. The IMA Volumes in Mathematics and Its Applications (2002) 127(Springer-Verlag, New York) 27–44Crossref, Google Scholar
• DeMartini C., Kwasnica A., Ledyard J. O., Porter D. A new and improved design for multi-object iterative auctions. (1999) . Social Science Working Paper No. 1054, Division of the Humanities and Social Sciences, California Institute of Technology, Pasadena, CAGoogle Scholar
• de Vries S., Vohra R. V. Auctions and the German UMTS-auction. Mitteilungen der DMV (2001a) No. 1:31–38Crossref, Google Scholar
• de Vries S., Vohra R. V. A solver for winner determination for combinatorial auctions. (2001b) . Manuscript, Zentrum Mathematik, TU München, München, GermanyGoogle Scholar
• Dietrich B., Forrest J. J., Dietrich B., Vohra R. V. A column generation approach for combinatorial auctions. Mathematics of the Internet: E-Auction and Markets. The IMA Volumes in Mathematics and Its Applications (2002) 127(Springer-Verlag, New York) 15–26Crossref, Google Scholar
• Eső M. Parallel branch and cut for set partitioning. (1999) . Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NYGoogle Scholar
• Eső P., Maskin E. Multi-good efficient auctions with multi-dimensional information. (2000) . Working paper, Kellogg School of Management, Northwestern University, Evanston, ILGoogle Scholar
• Fudenberg D., Tirole J.Game Theory (1992) (MIT Press, Cambridge, MA) Google Scholar
• Fujishima Y., Leyton-Brown K., Shoham Y. Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. Proc. of IJCAI-99 (1999) Stockholm, Sweden:548–553Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem. Oper. Res. (1961) 9:849–859Link, Google Scholar
• Gonen R., Lehmann D. Optimal solutions for multi-unit combinatorial auctions: branch-and-bound heuristics. ACM Conf. on Electronic Commerce (EC-00) (2000) Minneapolis, MN:13–20Crossref, Google Scholar
• Graves R., Sankaran J., Schrage L. An auction method for course registration. Interfaces (1993) 23:81–92Link, Google Scholar
• Grimm V., Riedl F., Wolfstetter E. The third generation (UMTS) spectrum auction in Germany. (2001) . Manuscript, Institute of Economic Theory I, Humboldt University of Berlin, Berlin, GermanyGoogle Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) (Springer-Verlag, Berlin Heidelberg, Germany) Crossref, Google Scholar
• Groves T. Incentives in teams. Econometrica (1973) 41:617–631Crossref, Google Scholar
• Golumbic M. C., Hammer P. L. Stability in circular arc graphs. J. Algorithms (1988) 9:314–320Crossref, Google Scholar
• Gul F., Stacchetti E. English and double auctions with differentiated commodities. J. of Econom. Theory (2000) 92:66–95Crossref, Google Scholar
• Håstad J. Clique is hard to approximate within n1-ε. Acta Mathematica (1999) 182:105–142Crossref, Google Scholar
• Hershberger J., Suri S. Vickrey prices and shortest paths: What is an edge worth? 42nd Annual Sympos. on Foundations of Comput. Sci. (FOCS) (2001) (Las Vegas, NV)129–140Crossref, Google Scholar
• Hobbs B. F., Rothkopf M., Hyde L., O'Neill R. P. Evaluation of a truthful revelation auction in the context of energy markets with nonconcave benefits. J. of Regulatory Econom. (2000) 18:5–32Crossref, Google Scholar
• Hoffman K., Padberg M. W. Solving airline crew scheduling problems by branch and cut. Management Sci. (1993) 39:657–682Link, Google Scholar
• Isaac R. M., James D. Robustness of the incentive compatible combinatorial auction. (1998) . Manuscript, Department of Economics, University of Arizona, Tucson, AZGoogle Scholar
• Jackson C. Technology for spectrum markets. (1976) . Ph.D. thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Jehiel P., Moldovanu B. Efficient design with interdependent valuations. Econometrica (2001a) 69:1237–1259Crossref, Google Scholar
• Jehiel P., Moldovanu B. The European UMTS/IMT-2000 license auctions. (2001b) . Discussion paper, Faculty of Economics, University of Mannheim, Mannheim, GermanyGoogle Scholar
• Jehiel P., Moldovanu B. note on revenue maximization and efficiency in multi-object auctions. Econom. Bull. (2001c) 3:1–5Google Scholar
• Jehiel P., Moldovanu B., Stacchetti E. Multidimensional mechanism design for auctions with externalities. J. of Econom. Theory (1999) 85:258–294Crossref, Google Scholar
• Johnson R. B., Oren S. S., Svoboda A. J. Equity and efficiency of unit commitment in competitive electricity markets. Utilities Policy (1997) 6:9–20Crossref, Google Scholar
• Kagel J. H., Levin D. Behavior in multi-unit demand auctions: Experiments with uniform price and dynamic Vickrey auctions. Econometrica (2001) 69:413–454Crossref, Google Scholar
• Keil J. M. On the complexity of scheduling tasks with discrete starting times. Oper. Res. Lett. (1992) 12:293–295Crossref, Google Scholar
• Kelso A. S., Crawford V. P. Job matching, coalition formation and gross substitutes. Econometrica (1982) 50:1483–1504Crossref, Google Scholar
• Kelly F., Steinberg R. A combinatorial auction with multiple winners for universal service. Management Sci. (2000) 46:586–596Link, Google Scholar
• Klemperer P. What really matters in auction design. J. of Econom. Perspectives (2002) 16:169–190Crossref, Google Scholar
• Krishna V., Perry M. Efficient mechanism design. (1998) . Manuscript, Department of Economics, The Pennsylvania State University, University Park, PAGoogle Scholar
• Krishna V., Rosenthal R. W. Simultaneous auctions with synergies. Games and Econom. Behavior (1996) 17:1–31Crossref, Google Scholar
• Kutanoglu E., Wu S. D. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Trans. (1999) 31:813–826Crossref, Google Scholar
• Ledyard J. O., Olson M., Porter D., Swanson J. A., Torma D. P. The first use of a combined value auction for transportation services. (2000) . Social Science Working Paper No. 1093, Division of the Humanities and Social Sciences, California Institute of Technology, Pasadena, CAGoogle Scholar
• Lehmann D., O'Callaghan L., Shoham Y. Truth revelation in rapid, approximately efficient combinatorial auctions. Proc. ACM Conf. on Electronic Commerce (EC-99) (1999) Denver, CO:96–102Google Scholar
• Levin J. An optimal auction for complements. Games and Econom. Behavior (1997) 18:176–192Crossref, Google Scholar
• Leyton-Brown K., Shoham Y., Tennenholtz M. An algorithm for multi-unit combinatorial auctions. Proc. of the Seventeenth National Conf. on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence (2000a) Austin, TX:56–61Google Scholar
• Leyton-Brown K., Pearson M., Shoham Y. Towards a universal test suite for combinatorial auction algorithms. Proc. ACM Conf. on Electronic Commerce (EC-00) (2000b) Minneapolis, MN:66–76Crossref, Google Scholar
• Lovász L., Plummer M. D. Matching theory. Annals of Discrete Mathematics (1986) (29. North-Holland, Elsevier, Amsterdam, The Netherlands)Google Scholar
• Mas-Collel A., Whinston M. D., Green J. R.Microeconomic Theory (1995) (Oxford University Press, New York) Google Scholar
• Milgrom P. Auctioning the radio spectrum. Auction Theory for Privatization (1995) (Cambridge University Press, Cambridge, England) . ForthcomingGoogle Scholar
• Monderer D., Tennenholtz M. Asymptotically optimal multi-object auctions for risk-averse agents. (2000) . Manuscript, Faculty of Industrial Engineering and Management, Technion—Israel Institute of Technology, Haifa, IsraelGoogle Scholar
• Murota K., Tamura A. New characterizations of M-convex functions and connections to mathematical economics. (2000) . RIMS Preprint 1307, Research Institute for Mathematical Sciences, Kyoto University, Kyoto, JapanGoogle Scholar
• Myerson R. Optimal auction design. Math. of Oper. Res. (1981) 6:58–73Link, Google Scholar
• Naor M., Pinkas B., Sumner R. Privacy preserving auctions and mechanism design. Proc. ACM Conf. on Electronic Commerce (EC-99) (1999) Denver, CO:129–139Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (John Wiley, New York) Crossref, Google Scholar
• Nisan N. Bidding and allocation in combinatorial auctions. Proc. ACM Conf. on Electronic Commerce (EC-00) (2000) Minneapolis, MN:1–12Crossref, Google Scholar
• Nisan N., Ronen A. Computationally feasible VCG mechanisms. Proc. ACM Conf. on Electronic Commerce (EC-00) (2000) Minneapolis, MN:242–252Crossref, Google Scholar
• Nisan N., Segal I. The communications complexity of efficient allocation problems. (2002) . Working paper, Institute of Computer Science, Hebrew University, Jerusalem, IsraelGoogle Scholar
• Padberg M. W. On the facial structure of set packing polyhedra. Math. Programming (1973) 5:199–215Crossref, Google Scholar
• Padberg M. W. On the complexity of the set packing polyhedra. Ann. of Discrete Math. (1975) 1:421–434Crossref, Google Scholar
• Padberg M. W. Covering, packing and knapsack problems. Ann. of Discrete Math. (1979) 4:265–287Crossref, Google Scholar
• Papadimitriou C. H., Steiglitz K.Combinatorial Optimization (1982) (Prentice-Hall, Inc., Englewood Cliffs, NJ) Google Scholar
• Parkes D. C. iBundle: an efficient ascending price bundle auction. Proc. ACM Conf. on Electronic Commerce (EC-99) (1999) Denver, CO:148–157Crossref, Google Scholar
• Parkes D. C., Ungar L. Iterative combinatorial auctions: theory and practice. Proc. 17th National Conf. on Artificial Intelligence (2000) Austin, TX:74–81Google Scholar
• Rassenti S. J., Smith V. L., Bulfin R. L. A combinatorial auction mechanism for airport time slot allocation. Bell J. of Econom. (1982) 13:402–417Crossref, Google Scholar
• Rochet J.-C., Stole L. The economics of multidimensional screening. (2001) . Manuscript, Graduate School of Business, University of Chicago, Chicago, ILGoogle Scholar
• Rothkopf M. H., Pekec A., Harstad R. M. Computationally manageable combinatorial auctions. Management Science (1998) 44:1131–1147Link, Google Scholar
• Sandholm T. An algorithm for optimal winner determination in combinatorial auctions. Proc. of IJCAI-99 (1999) Stockholm, Sweden:542–547Google Scholar
• Sassano A. On the facial structure of the set covering polytope. Math. Programming (1989) 44:181–202Crossref, Google Scholar
• Schrijver A.Theory of Linear and Integer Programming (1986) (John Wiley, New York) Google Scholar
• Srinivasan S., Stallert J., Whinston A. B. Portfolio trading and electronic networks. (1998) . Working paper, Center for Research in Electronic Commerce, The University of Texas at Austin, Austin, TexasGoogle Scholar
• Strevell M., Chong P. Gambling on vacation. Interfaces (1985) 15:63–67Link, Google Scholar
• van Hoesel S., Müller R. Optimization in electronic markets: examples in combinatorial auctions. Netnomics (2001) 3:23–33Crossref, Google Scholar
• Vickrey W. Counterspeculation, auctions, and competitive sealed tenders. J. of Finance (1961) 16:8–37Crossref, Google Scholar
• Wellman M. P., Walsh W. E., Wurman P. R., MacKie-Mason J. K. Auction protocols for decentralized scheduling. Games and Econom. Behavior (2001) 35:271–303Crossref, Google Scholar
• Williams S. R. A characterization of efficient, Bayesian incentive compatible mechanisms. Econom. Theory (1999) 14:155–180Crossref, Google Scholar
• Wolsey L. Integer programming duality: Price functions and sensitivity analysis. Math. Programming (1981) 20:173–195Crossref, Google Scholar
• Wurman P. R., Wellman M. AkBA: A progressive, anonymous-price combinatorial auction. Proc. Second ACM Conf. on Electronic Commerce (EC-00) (2000) Minneapolis, MN:21–29Crossref, Google Scholar
• Ygge F. Improving the computational efficiency of combinatorial auction algorithms. (1999) . EnerSearch Public Report:EnS 99:08, EnerSearch AB, Göteborg, SwedenGoogle Scholar
• Yokoo M., Sakurai Y., Matsubara S. Robust combinatorial auction protocol against false-name bids. Artificial Intelligence J. (2001) 130:167–181Crossref, Google Scholar