The Performance of Deferred-Acceptance Auctions

References

• Ausubel L (2004) An efficient ascending-bid auction for multiple objects. Amer. Econom. Rev. 94(5):1452–1475.Crossref, Google Scholar
• Ausubel L (2006) An efficient dynamic auction for heterogeneous commodities. Amer. Econom. Rev. 96(3):602–629.Crossref, Google Scholar
• Ausubel LM, Milgrom P (2006) The lovely but lonely Vickrey auction. Combinatorial Auctions (MIT Press, Boston), 17–40.Google Scholar
• Babaioff M, Lavi R, Pavlov E (2009) Single-value combinatorial auctions and algorithmic implementation in undominated strategies. J. ACM 56(1):4:1–4:32.Crossref, Google Scholar
• Bikhchandani S, de Vries S, Schummer SJ, Vohra RV (2011) An ascending Vickrey auction for selling bases of a matroid. Oper. Res. 59(2):400–413.Link, Google Scholar
• Blumrosen L, Nisan N (2009) On the computational power of demand queries. SIAM J. Comput. 39(4):1372–1391.Crossref, Google Scholar
• Blumrosen L, Nisan N (2010) Informational limitations of ascending combinatorial auctions. J. Econom. Theory 145(3):1203–1223.Crossref, Google Scholar
• Blumrosen L, Zohar O (2015) Multilateral deferred-acceptance mechanisms. Markakis E, Schäfer G, eds. Proc. 11th Internat. Conf. Web and Internet Econom., WINE ’15 (Springer, Berlin), 173–186.Crossref, Google Scholar
• Borodin A, Lucier B (2010a) On the limitations of greedy mechanism design for truthful combinatorial auctions. Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide M, Spirakis PG, eds. Proc. 37th Internat. Colloquium on Automata, Languages and Programming, ICALP ’10 (Springer, Berlin), 90–101.Crossref, Google Scholar
• Borodin A, Lucier B (2010b) Price of anarchy for greedy auctions. Charikar M, ed. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’10 (SIAM, Philadelphia), 537–553.Google Scholar
• Briest P, Krysta P, Vöcking B (2011) Approximation techniques for utilitarian mechanism design. SIAM J. Comput. 40(6):1587–1622.Crossref, Google Scholar
• Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. Jansen K, Khuller S, eds. Proc. 3rd Internat. Workshop on Approximation Algorithms for Combinatorial Optim. (Springer, London), 84–95.Crossref, Google Scholar
• Chrobak M, Kenyon C, Young NE (2006) The reverse greedy algorithm for the metric k-median problem. Inform. Processing Lett. 97(2):68–72.Crossref, Google Scholar
• Cramton P (2006) Simultaneous ascending auctions. Combinatorial Auctions (MIT Press, Boston), 79–98.Google Scholar
• Day RW, Milgrom P (2008) Core-selecting package auctions. Internat. J. Game Theory 36(3):393–348.Crossref, Google Scholar
• Demange G, Gale D, Sotomayor M (1986) Multi-item auctions. J. Political Econom. 94(4):863–872.Crossref, Google Scholar
• Devanur NR, Mihail M, Vazirani VV (2005) Strategyproof cost-sharing mechanisms for set cover and facility location games. Decision Support Systems 39(1):11–22.Crossref, Google Scholar
• Drake DE, Hougardy S (2003) A simple approximation algorithm for the weighted matching problem. Inform. Processing Lett. 85(4):211–213.Crossref, Google Scholar
• Dütting P, Roughgarden T, Talgam-Cohen I (2014) Modularity and greed in double auctions. Babaioff M, Conitzer V, Easley D, eds. Proc. 15th ACM Conf. Econom. Comput., EC ’14 (ACM, New York), 241–258.Crossref, Google Scholar
• Ensthaler L, Giebe T (2015) A dynamic auction for multi-object procurement under a hard budget constraint. Res. Policy 43(1):179–189.Crossref, Google Scholar
• Fiat A, Goldberg AV, Hartline JD, Karlin AR (2002) Competitive generalized auctions. Reif JH, ed. Proc. 34th ACM Sympos. Theory Comput., SODA ’02 (ACM, New York), 72–81.Crossref, Google Scholar
• Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• Goemans MX, Williamson DP (1997) The primal-dual method for approximation algorithms and its application to the network design problems. Approximation Algorithms for NP-Hard Problems, Chap. 4 (PWS Publishing, Boston), 144–191.Google Scholar
• Gul F, Stacchetti E (2000) The English auction with differentiated commodities. J. Econom. Theory 92(1):66–95.Crossref, Google Scholar
• Håstad J (1999) Clique is hard to approximate within n1−ε. Acta Mathematica 182(1):105–142.Crossref, Google Scholar
• Hazan E, Safra S, Schwartz O (2006) On the complexity of approximating k-set packing. Comput. Complexity 15(1):20–39.Crossref, Google Scholar
• Immorlica N, Pountourakis E (2012) On budget-balanced group-strategyproof cost-sharing mechanisms. Goldberg PW, ed. Proc. 8th Workshop on Internet and Network Econom., WINE ’12 (Springer, Berlin), 244–255.Crossref, Google Scholar
• Immorlica N, Mahdian M, Mirrokni VS (2008) Limitations of cross-monotonic cost-sharing schemes. ACM Trans. Algorithms 4(2):24:1–24:25.Crossref, Google Scholar
• Jarman F, Meisner V (2002) Ascending auctions with package bidding. Frontiers of Theoretical Econom. 1(1):1452–1475.Google Scholar
• Jarman F, Meisner V (2015) Ex-post optimal knapsack procurement. SSRN Working Paper 2548543.Crossref, Google Scholar
• Juarez R (2013a) Group strategyproof cost sharing: The role of indifferences. Games Econom. Behav. 82(C):218–239.Crossref, Google Scholar
• Juarez R (2013b) Optimal group strategyproof cost sharing. Working paper, University of Hawaii, Honolulu, HI.Google Scholar
• Kelso A, Crawford V (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483–1504.Crossref, Google Scholar
• Kim A (2015) Welfare maximization with deferred acceptance auctions in reallocation problems. Bansal N, Finocchi I, eds. Proc. 23rd Annual Eur. Sympos. Algorithms, ESA ’15 (Springer, Berlin), 804–815.Crossref, Google Scholar
• Klemperer P (2010) The product-mix auction: A new auction design for differentiated goods. J. Eur. Econom. Assoc. 8(2–3):526–536.Crossref, Google Scholar
• Korte B, Vygen J (2007) Combinatorial Optimization: Theory and Algorithms (Springer, Berlin).Google Scholar
• Lehmann D, O’Callaghan LI, Shoham Y (2002) Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5):577–602.Crossref, Google Scholar
• Li S (2015) Obviously strategy-proof mechanisms. SSRN Working Paper 2560028.Crossref, Google Scholar
• Marx LM, Loertscher S (2015) Prior-free bayesian optimal double-clock auctions. Working paper, Duke University, Durham, NC.Google Scholar
• Mehta A, Roughgarden T, Sundararajan M (2009) Beyond Moulin mechanisms. Games Econom. Behav. 67(1):125–155.Crossref, Google Scholar
• Milgrom P (2000) Putting auction theory to work: The simultaneous ascending auction. J. Political Econom. 108(2):245–272.Crossref, Google Scholar
• Milgrom P, Segal I (2014) Deferred-acceptance auctions and radio spectrum reallocation. Babaioff M, Conitzer V, Easley D, eds. Proc. 15th ACM Conf. Econom. Comput., EC ’14 (ACM, New York), 185–186.Crossref, Google Scholar
• Milgrom P, Segal I (2015) Deferred-acceptance auctions and radio spectrum reallocation. Working paper, Stanford University, Stanford, CA.Google Scholar
• Moulin H (1999) Incremental cost sharing: Characterization by coalition strategy-proofness. Soc. Choice Welfare 16(2):279–320.Crossref, Google Scholar
• Mu’alem A, Nisan N (2008) Truthful approximation mechanisms for restricted combinatorial auctions. Games Econom. Behav. 64(2):612–631.Crossref, Google Scholar
• Nguyen T, Sandholm T (2014) Optimizing prices in descending clock auctions. Babaioff M, Conitzer V, Easley D, eds. Proc. 15th ACM Conf. Econom. Comput., EC ’14 (ACM, New York), 93–110.Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos É, Vazirani VV, eds. (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Parkes DC, Ungar LH (2000a). Iterative combinatorial auctions: Theory and practice. Kautz HA, Porter BW, eds. Proc. 17th National Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA, 74–81.Google Scholar
• Parkes DC, Ungar LH (2000b) Preventing strategic manipulation in iterative auctions: Proxy agents and price adjustment. Kautz HA, Porter BW, eds. Proc. 17th National Conf. Artificial Intelligence (AAAI, Palo Alto, CA), 82–89.Google Scholar
• Roughgarden T, Sundararajan M (2009) Quantifying inefficiency in cost-sharing mechanisms. J. ACM 56(4):23:1–23:33.Crossref, Google Scholar
• Sakai S, Togasaki M, Yamazaki K (2003) A note on greedy algorithms for maximum weighted independent set problem. Discrete Appl. Math. 126(2–3):313–322.Crossref, Google Scholar
• Tarjan RE (1983) Data Structures and Network Algorithms (SIAM, Philadelphia).Crossref, Google Scholar