Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language

References

• Arora S, Barak B (2009) Computational Complexity: A Modern Approach (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Ausubel LM, Baranov OV (2014) Market design and the evolution of the combinatorial clock auction. Amer. Econom. Rev. 104(5):446–451.Crossref, Google Scholar
• Ausubel LM, Cramton P, Milgrom P (2006) The clock-proxy auction: A practical combinatorial auction design. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 115–138.Google Scholar
• Bichler M, Goeree JK (2017) Handbook of Spectrum Auction Design (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bichler M, Paulsen P (2018) A principal-agent model of bidding firms in multi-unit auctions. Games Econom. Behav. 111:20–40.Crossref, Google Scholar
• Bichler M, Hao Z, Adomavicius G (2017) Coalition-based pricing in ascending combinatorial auctions. Inform. Systems Res. 28(1):159–179.Link, Google Scholar
• Bichler M, Shabalin P, Ziegler G (2013) Efficiency with linear prices? A game-theoretical and computational analysis of the combinatorial clock auction. Inform. Systems Res. 24(2):394–417.Link, Google Scholar
• Bichler M, Davenport A, Hohner G, Kalagnanam J (2006) Industrial procurement auctions. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 593–612.Google Scholar
• Bichler M, Goeree J, Mayer S, Shabalin P (2014) Spectrum auction design: Simple auctions for complex sales. Telecomm. Policy 38(7):613–622.Crossref, Google Scholar
• Bichler M, Schneider S, Guler K, Sayal M (2011) Compact bidding languages and supplier selection for markets with economies of scale and scope. Eur. J. Oper. Res. 214(1):67–77.Crossref, Google Scholar
• Boutilier C, Hoos HH (2001) Bidding languages for combinatorial auctions. Nebel B, ed. Proc. Internat. Joint Conf. Artificial Intelligence, vol. 17 (Morgan Kaufmann Publishers, Burlington, MA), 1211–1217.Google Scholar
• Conen W, Sandholm T (2001) Preference elicitation in combinatorial auctions. Proc. 3rd ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 256–259.Google Scholar
• Cramton P (2017) Electricity market design. Oxford Rev. Econom. Policy 33(4):589–612.Crossref, Google Scholar
• Day RW, Cramton P (2012) Quadratic core-selecting payment rules for combinatorial auctions. Oper. Res. 60(3):588–603.Link, Google Scholar
• Day RW, Raghavan S (2007) Fair payments for efficient allocations in public sector combinatorial auctions. Management Sci. 53(9):1389–1406.Link, Google Scholar
• Downey RG, Fellows MR (2012) Parameterized Complexity (Springer Science & Business Media, New York).Google Scholar
• Eilat A, Milgrom P (2011) The CAF auction: Design proposal. Technical report, Stanford University, Stanford, CA.Google Scholar
• Federal Communications Commission (2020a) Auction 107 clock phase technical guide. Technical report, Federal Communications Commission, Washington DC.Google Scholar
• Federal Communications Commission (2020b) Auction of flexible-use service licenses in the 3.7-3.98 GHz band for next-generation wireless services; notice and filing requirements, minimum opening bids, upfront payments, and other procedures for auction 107. Technical report, Federal Communications Commission, Washington, DC.Google Scholar
• Fréville A (2004) The multidimensional 0–1 knapsack problem: An overview. Eur. J. Oper. Res. 155(1):1–21.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability, vol. 174(W. H. Freeman and Co., New York).Google Scholar
• Goeree JK, Holt CA (2010) Hierarchical package bidding: A paper & pencil combinatorial auction. Games Econom. Behav. 70(1):146–169.Crossref, Google Scholar
• Goetzendorff A, Bichler M, Shabalin P, Day RW (2015) Compact bid languages and core pricing in large multi-item auctions. Management Sci. 61(7):1684–1703.Link, Google Scholar
• Gurski F, Rehs C, Rethmann J (2019) Knapsack problems: A parameterized point of view. Theoretical Comput. Sci. 775:93–108.Crossref, Google Scholar
• Iftekhar MS, Tisdell J (2012) Comparison of simultaneous and combinatorial auction designs in fisheries quota market. Marketing Policy 36(2):446–453.Google Scholar
• Kelly F, Steinberg R (2000) A combinatorial auction with multiple winners for universal service. Management Sci. 46(4):586–596.Link, Google Scholar
• Kroemer C, Bichler M, Goetzendorff A (2017) About inconsistent bidding and its impact on efficiency in the combinatorial clock auction. Bichler M, Goeree JK, eds. Handbook of Spectrum Auction Design (Cambridge University Press, Cambridge, UK), 338–370.Crossref, Google Scholar
• Kulik A, Shachnai H (2010) There is no EPTAS for two-dimensional knapsack. Inform. Processing Lett. 110(16):707–710.Crossref, Google Scholar
• Lavi R, Swamy C (2011) Truthful and near-optimal mechanism design via linear programming. J. ACM 58(6):1–24.Crossref, Google Scholar
• Lehmann D, Müller R, Sandholm T (2006) The winner determination problem. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 297–318.Google Scholar
• Lehmann D, Oćallaghan LI, Shoham Y (2002) Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5):577–602.Crossref, Google Scholar
• Levin J, Skrzypacz A (2016) Properties of the combinatorial clock auction. Amer. Econom. Rev. 106(9):2528–2551.Crossref, Google Scholar
• Milgrom P (2004) Putting Auction Theory to Work (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Milgrom P (2009) Assignment messages and exchanges. AEJ Micro 1(2):95–113.Google Scholar
• Mitchell JE (2002) Branch-and-cut algorithms for combinatorial optimization problems. Pardalos PM, Resende MGC, eds. Handbook of Applied Optimization (Oxford University Press, Oxford, UK), 65–77.Google Scholar
• Nisan N (2006) Bidding languages. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 400–420.Google Scholar
• Nisan N, Ronen A (2001) Algorithmic mechanism design. Games Econom. Behav. 35(1–2):166–196.Crossref, Google Scholar
• Nisan N, Segal I (2006) The communication requirements of efficient allocations and supporting prices. J. Econom. Theory 129(1):192–224.Crossref, Google Scholar
• Papavasiliou A, Papalexopoulos AD, Oren S (2017) Market design for a decarbonized electricity market. Rossetto N, ed. Design the Electricity Market(s) of the Future (European University Institute, Florence, Italy), 27–30.Google Scholar
• Parkes D (2006) Iterative combinatorial auctions. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 41–78.Google Scholar
• Pekec A, Rothkopf MH (2003) Combinatorial auction design. Management Sci. 49(11):1485–1503.Link, Google Scholar
• Porter D, Rassenti S, Roopnarine A, Smith V (2003) Combinatorial auction design. Proc. National Acad. Sci. USA 100(19):11153–11157.Crossref, Google Scholar
• Sandholm T (2002) Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence 135(1–2):1–54.Crossref, Google Scholar
• Sandholm T, Boutilier C (2006) Preference elicitation in combinatorial auctions. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 421–488.Google Scholar
• Scheffel T, Ziegler G, Bichler M (2012) On the impact of package selection in combinatorial auctions: an experimental study in the context of spectrum auction design. Experiment. Econom. 15(4):667–692.Crossref, Google Scholar
• Varnamkhasti MJ (2012) Overview of the algorithms for solving the multidimensional knapsack problems. Adv. Stud. Biology 4(1):37–47.Google Scholar