Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

References

• [1] Abraham I, Athey S, Babaioff M, Grubb M (2020) Peaches, lemons, and cookies: Designing auction markets with dispersed information. Games Econom. Behav. 124:454–477.Crossref, Google Scholar
• [2] Amer A, Talgam-Cohen I (2021) Auctions with interdependence and SOS: Improved approximation. Preprint, submitted July 19, https://arxiv.org/abs/2107.08806.Google Scholar
• [3] Athey S (2001) Single crossing properties and the existence of pure strategy equilibria in games of incomplete information. Econometrica 69(4):861–889.Crossref, Google Scholar
• [4] Ausubel LM (1999) A generalized Vickrey auction. Working paper, Department of Economics, University of Maryland, College Park, MD.Google Scholar
• [5] Babaioff M, Kleinberg R, Paes Leme R (2012) Optimal mechanisms for selling information. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 92–109.Google Scholar
• [6] Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813.Crossref, Google Scholar
• [7] Bergemann D, Shi X, Välimäki J (2009) Information acquisition in interdependent value auctions. J. Eur. Econom. Assoc. 7(1):61–89.Crossref, Google Scholar
• [8] Bian AA, Levy KY, Krause A, Buhmann JM (2017) Non-monotone continuous dr-submodular maximization: Structure and algorithms. Adv. Neural Inform. Processing Systems, Annual Conf. Neural Inform. Processing Systems, vol. 30 (NeurIPS, San Diego), 486–496.Google Scholar
• [9] Bikhchandani S (2006) Ex post implementation in environments with private goods. Theoret. Econom. 1(3):369–393.Google Scholar
• [10] Chawla S, Fu H, Karlin A (2014) Approximate revenue maximization in interdependent value settings. Proc. 15th ACM Conf. Econom. Comput. (ACM, New York), 277–294.Google Scholar
• [11] Che YK, Kim J, Kojima F (2015) Efficient assignment with interdependent values. J. Econom. Theory 158:54–86.Crossref, Google Scholar
• [12] Clarke EH (1971) Multipart pricing of public goods. Public Choice 11(1):17–33.Crossref, Google Scholar
• [13] Constantin F, Parkes DC (2007) On revenue-optimal dynamic auctions for bidders with interdependent values. Collins J, Faratin P, Parsons S, Rodríguez-Aguilar JA, Sadeh NM, Shehory O, Sklar E, eds. Agent-Mediated Electronic Commerce and Trading Agent Design and Analysis (AAMAS) 2007 Workshop, (AMEC), and (AAAI) 2007 Workshop, (TADA) 2007, Selected and Revised Papers. Lecture Notes in Business Information Processing, vol. 13 (Springer, New York), 1–15.Google Scholar
• [14] Constantin F, Ito T, Parkes DC (2007) Online auctions for bidders with interdependent values. AAMAS 110 (IFAAMAS).Google Scholar
• [15] Dasgupta P, Maskin E (2000) Efficient auctions. Quart. J. Econom. 115(2):341–388.Crossref, Google Scholar
• [16] d’Aspremont C, Gérard-Varet LA (1982) Bayesian incentive compatible beliefs. J. Math. Econom. 10(1):83–103.Crossref, Google Scholar
• [17] Dobzinski S, Fu H, Kleinberg RD (2011) Optimal auctions with correlated bidders are easy. Proc. Forty-Third Annual ACM Sympos. Theory Comput. (ACM, New York), 129–138.Google Scholar
• [18] Eden A, Goldner K, Zheng S (2022) Private interdependent valuations. Naor JS, Buchbinder N, eds. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms, SODA 2022, Virtual Conf. (SIAM, Philadelphia), 2920–2939.Google Scholar
• [19] Eden A, Feldman M, Fiat A, Goldner K (2018) Interdependent values without single-crossing. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 369–369.Google Scholar
• [20] Goldberg AV, Hartline JD, Wright A (2001) Competitive auctions and digital goods. Proc. 12th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 735–744.Google Scholar
• [21] Groves T (1973) Incentives in teams. Econometrica 41(4):617–631.Crossref, Google Scholar
• [22] Ito T, Parkes DC (2006) Instantiating the contingent bids model of truthful interdependent value auctions. AAMAS (ACM, New York), 1151–1158.Google Scholar
• [23] Jehiel P, Moldovanu B (2001) Efficient design with interdependent valuations. Econometrica 69(5):1237–1259.Crossref, Google Scholar
• [24] Jehiel P, Meyer-ter Vehn M, Moldovanu B, Zame WR (2006) The limits of ex post implementation. Econometrica 74(3):585–610.Crossref, Google Scholar
• [25] Klein M, Moreno GA, Parkes DC, Plakosh D, Seuken S, Wallnau KC (2008) Handling interdependent values in an auction mechanism for bandwidth allocation in tactical data networks. NetEcon (ACM, New York), 73–78.Google Scholar
• [26] Klemperer P (1998) Auctions with almost common values: The wallet game and its applications. Eur. Econom. Rev. 42(3):757–769.Crossref, Google Scholar
• [27] Li Y (2017) Approximation in mechanism design with interdependent values. Games Econom. Behav. 103:225–253.Crossref, Google Scholar
• [28] Maskin E (1992) Auctions and privatization. Siebert H, ed. Privatization (Institut fur Weltwirtschaften der Universität Kiel, Kiel, Germany), 115–136.Google Scholar
• [29] McLean R, Postlewaite A (2015) Implementation with interdependent valuations. Theoret. Econom. 10:923–952.Crossref, Google Scholar
• [30] Milgrom PR, Weber RJ (1982) A theory of auctions and competitive bidding. Econometrica 50(5):1089–1122.Crossref, Google Scholar
• [31] Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• [32] Niazadeh R, Roughgarden T, Wang JR (2018) Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization. Annual Conf. Neural Inform. Processing Systems 2018 (NeurIPS, San Diego), 9617–9627.Google Scholar
• [33] Papadimitriou CH, Pierrakos G (2011) On optimal single-item auctions. Proc. 43rd ACM Sympos. Theory Comput. STOC 2011 (ACM, New York), 119–128.Google Scholar
• [34] Robu V, Parkes DC, Ito T, Jennings NR (2013) Efficient interdependent value combinatorial auctions with single minded bidders. IJCAI (U.S.) (IJCAI/AAAI), 339–345.Google Scholar
• [35] Rochet JC (1987) A necessary and sufficient condition for rationalizability in a quasi-linear context. J. Math. Econom. 16(2):191–200.Crossref, Google Scholar
• [36] Ronen A (2001) On approximating optimal auctions. Proc. 3rd ACM Conf. Electronic Commerce (ACM, New York), 11–17.Google Scholar
• [37] Roughgarden T, Talgam-Cohen I (2016) Optimal and robust mechanism design with interdependent values. ACM Trans. Econom. Comput. 4(3):18.1–18.34.Google Scholar
• [38] Soma T, Yoshida Y (2015) A generalization of submodular cover via the diminishing return property on the integer lattice. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems, 28: Annu. Conf. Neural Inform. Processing Systems (NeurIPS, San Diego), 847–855.Google Scholar
• [39] Syrgkanis V, Kempe D, Tardos E (2019) Information asymmetries in common-value auctions with discrete signals. Math. Oper. Res. 44(4):1450–1476.Google Scholar
• [40] Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8–37.Crossref, Google Scholar
• [41] Vohra R (2007) Paths, cycles and mechanism design. Preprint, submitted.Google Scholar
• [42] Wilson RB (1969) Competitive bidding with disparate information. Management Sci. 15(7):446–452.Link, Google Scholar