Bicriteria Multidimensional Mechanism Design with Side Information

References

• [1] Abhishek V, Hajek B (2010) Efficiency loss in revenue optimal auctions. 49th IEEE Conf. Decision Control (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1082–1087.Google Scholar
• [2] Aggarwal G, Goel G, Mehta A (2009) Efficiency of (revenue-)optimal mechanisms. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 235–242.Google Scholar
• [3] Agrawal P, Balkanski E, Gkatzelis V, Ou T, Tan X (2022) Learning-augmented mechanism design: Leveraging predictions for facility location. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 497–528.Google Scholar
• [4] Akbarpour M, Kominers SD, Li S, Milgrom PR (2021) Investment incentives in near-optimal mechanisms. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 26–26.Google Scholar
• [5] Anshelevich E, Kar K, Sekar S (2016) Pricing to maximize revenue and welfare simultaneously in large markets. Cai Y, Vetta A, eds. Web and Internet Economics (Springer, Berlin), 145–159. Crossref, Google Scholar
• [6] Ausubel L, Baranov O (2017) A practical guide to the combinatorial clock auction. Econom. J. 127(605):F334–F350.Google Scholar
• [7] Ausubel LM, Milgrom P (2006) The lovely but lonely Vickrey auction. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 22–26.Google Scholar
• [8] Babaioff M, Immorlica N, Lucier B, Weinberg SM (2020) A simple and approximately optimal mechanism for an additive buyer. J. ACM 67(4):1–40.Crossref, Google Scholar
• [9] Balcan MF (2020) Data-driven algorithm design. Roughgarden T, ed. Beyond the Worst-Case Analysis of Algorithms (Cambridge University Press, Cambridge, UK), 626–645.Crossref, Google Scholar
• [10] Balcan MF, Blum A, Mansour Y (2008) Item pricing for revenue maximization. Proc. Ninth ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 50–59. Google Scholar
• [11] Balcan MF, Prasad S, Sandholm T (2020) Efficient algorithms for learning revenue-maximizing two-part tariffs. Bessiere C, ed. Proc. 29th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization, Yokohama), 332–338.Google Scholar
• [12] Balcan MF, Prasad S, Sandholm T (2021) Learning within an instance for designing high-revenue combinatorial auctions. Zhou ZH, ed. Proc. 30th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization, Montreal), 31–37.Google Scholar
• [13] Balcan MF, Prasad S, Sandholm T (2023) Bicriteria multidimensional mechanism design with side information. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates, Red Hook, NY), 40832–40852.Crossref, Google Scholar
• [14] Balcan MF, Prasad S, Sandholm T (2025) Increasing revenue in efficient combinatorial auctions by learning to generate artificial competition. Proc. 39th Annual AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 13572–13580.Google Scholar
• [15] Balcan MF, Sandholm T, Vitercik E (2018) A general theory of sample complexity for multi-item profit maximization. Proc. ACM 2018 Conf. Econom. Comput. (Association for Computing Machinery, New York), 173–174.Google Scholar
• [16] Balcan MF, Sandholm T, Vitercik E (2019) Estimating approximate incentive compatibility. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 867–867.Google Scholar
• [17] Balcan MF, Blum A, Hartline JD, Mansour Y (2005) Mechanism design via machine learning. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 605–614.Google Scholar
• [18] Baliga S, Vohra R (2003) Market research and market design. Adv. Theoret. Econom. 3(1):1059.Google Scholar
• [19] Balkanski E, Gkatzelis V, Tan X (2023) Strategyproof scheduling with predictions. Proc. 14th Innovations Theoret. Comput. Sci. Conf., vol. 251 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 11.Google Scholar
• [20] Balkanski E, Gkatzelis V, Tan X, Zhu C (2024) Online mechanism design with predictions. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1184–1184.Google Scholar
• [21] Banerjee S, Gkatzelis V, Gorokh A, Jin B (2022) Online Nash social welfare maximization with predictions. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1–19.Google Scholar
• [22] Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813. Crossref, Google Scholar
• [23] Bichler M, Goeree JK (2017) Handbook of Spectrum Auction Design (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [24] Bichler M, Fux V, Goeree JK (2019) Designing combinatorial exchanges for the reallocation of resource rights. Proc. Natl. Acad. Sci. USA 116(3):786–791.Crossref, Google Scholar
• [25] Börgers T (2015) An Introduction to the Theory of Mechanism Design (Oxford University Press, New York).Crossref, Google Scholar
• [26] Bulow J, Klemperer P (1996) Auctions versus negotiations. Amer. Econom. Rev. 86(1):180–194.Google Scholar
• [27] Caragiannis I, Kalantzis G (2024) Randomized learning-augmented auctions with revenue guarantees. Larson K, ed. Proc. 33rd Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization, Jeju), 2687–2694.Google Scholar
• [28] Chakraborty T, Huang Z, Khanna S (2013) Dynamic and nonuniform pricing strategies for revenue maximization. SIAM J. Comput. 42(6):2424–2451.Crossref, Google Scholar
• [29] Chiesa A, Micali S, Zhu ZA (2015) Knightian analysis of the Vickrey mechanism. Econometrica 83(5):1727–1754.Crossref, Google Scholar
• [30] Christodoulou G, Sgouritsa A, Vlachos I (2024) Mechanism design augmented with output advice. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds. Advances in Neural Information Processing Systems, vol. 37 (Curran Associates, Red Hook, NY), 41934–41953.Crossref, Google Scholar
• [31] Clarke EH (1971) Multipart pricing of public goods. Public Choice 11:17–33. Crossref, Google Scholar
• [32] Cole R, Roughgarden T (2014) The sample complexity of revenue maximization. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 243–252.Google Scholar
• [33] Conitzer V, Sandholm T (2002) Complexity of mechanism design. Proc. 18th Annual Conf. Uncertainty Artificial Intelligence (Morgan Kaufmann Publishers, San Francisco), 103–110.Google Scholar
• [34] Conitzer V, Sandholm T (2003) Applications of automated mechanism design. UAI-03 Workshop Bayesian Model. Appl.Google Scholar
• [35] Cramton P (2013) Spectrum auction design. Rev. Indust. Organ. 42(2):161–190.Crossref, Google Scholar
• [36] Cramton P (2017) Electricity market design. Oxford Rev. Econom. Policy 33(4):589–612.Crossref, Google Scholar
• [37] Cramton P, Gibbons R, Klemperer P (1987) Dissolving a partnership efficiently. Econometrica 55(3):615–632.Crossref, Google Scholar
• [38] Cramton P, Shoham Y, Steinberg R (2006) Combinatorial Auctions (MIT Press, Cambridge, MA).Google Scholar
• [39] Crémer J, McLean RP (1988) Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica 56(6):1247–1257.Crossref, Google Scholar
• [40] Curry M, Sandholm T, Dickerson J (2023) Differentiable economics for randomized affine maximizer auctions. Elkind E, ed. Proc. 32nd Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization, Macau), 2633–2641.Google Scholar
• [41] Daskalakis C, Pierrakos G (2011) Simple, optimal and efficient auctions. Chen N, Elkind E, Koutsoupias E, eds. Internet and Network Economics (Springer, Berlin), 109–121. Crossref, Google Scholar
• [42] Day RW, Cramton P (2012) Quadratic core-selecting payment rules for combinatorial auctions. Oper. Res. 60(3):588–603.Link, Google Scholar
• [43] Day R, Milgrom P (2008) Core-selecting package auctions. Internat. J. Game Theory 36(3):393–407.Crossref, Google Scholar
• [44] Day RW, Raghavan S (2007) Fair payments for efficient allocations in public sector combinatorial auctions. Management Sci. 53(9):1389–1406.Link, Google Scholar
• [45] Devanur NR, Huang Z, Psomas CA (2016) The sample complexity of auctions with side information. Proc. 48th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 426–439.Google Scholar
• [46] Diakonikolas I, Papadimitriou C, Pierrakos G, Singer Y (2012) Efficiency-revenue trade-offs in auctions. Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. Proc. 39th Internat. Colloquium Automata, Languages, Programming (Springer, Berlin), 488–499.Google Scholar
• [47] Duan Z, Sun H, Chen Y, Deng X (2023) A scalable neural network for DSIC affine maximizer auction design. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates, Red Hook, NY).Google Scholar
• [48] Dütting P, Feng Z, Narasimhan H, Parkes D, Ravindranath SS (2019) Optimal auctions through deep learning. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (JMLR.org), 1706–1715.Google Scholar
• [49] Edelman B, Ostrovsky M, Schwarz M (2007) Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. Amer. Econom. Rev. 97(1):242–259.Crossref, Google Scholar
• [50] Gkatzelis V, Schoepflin D, Tan X (2025) Clock auctions augmented with unreliable advice. Proc. 2025 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2629–2655.Google Scholar
• [51] Gkatzelis V, Kollias K, Sgouritsa A, Tan X (2022) Improved price of anarchy via predictions. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 529–557.Google Scholar
• [52] 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
• [53] Goldberg A, Hartline J, Wright A (2001) Competitive auctions and digital goods. Kosaraju SR, ed. Proc. 12th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
• [54] Green J, Laffont JJ (1977) Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica 45(2):427–438.Crossref, Google Scholar
• [55] Grotschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimizations (Springer-Verlag, Berlin).Crossref, Google Scholar
• [56] Groves T (1973) Incentives in teams. Econometrica 41(4):617–631.Crossref, Google Scholar
• [57] Guruswami V, Hartline JD, Karlin AR, Kempe D, Kenyon C, McSherry F (2005) On profit-maximizing envy-free pricing. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1164–1173.Google Scholar
• [58] Hart S, Nisan N (2013) The menu-size complexity of auctions. Proc. 14th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 565–566.Google Scholar
• [59] Hart S, Reny PJ (2015) Maximal revenue with multiple goods: Nonmonotonicity and other observations. Theoret. Econom. 10(3):893–922.Crossref, Google Scholar
• [60] Hartline JD, Roughgarden T (2009) Simple versus optimal mechanisms. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 225–234.Google Scholar
• [61] Hohner G, Rich J, Ng E, Reid G, Davenport AJ, Kalagnanam JR, Lee HS, An C (2003) Combinatorial and quantity-discount procurement auctions benefit Mars, Incorporated and its suppliers. Interfaces 33(1):23–35.Link, Google Scholar
• [62] Holmström B (1979) Groves’ scheme on restricted domains. Econometrica 47(5):1137–1144.Crossref, Google Scholar
• [63] Holzman R, Kfir-Dahav N, Monderer D, Tennenholtz M (2004) Bundling equilibrium in combinatorial auctions. Games Econom. Behav. 47(1):104–123.Crossref, Google Scholar
• [64] Horvitz E, Ruan Y, Gomez C, Kautz H, Selman B, Chickering M (2001) A Bayesian approach to tackling hard computational problems. Proc. 17th Conf. Uncertainty Artificial Intelligence (Morgan Kaufmann Publishers, San Francisco), 235–244.Google Scholar
• [65] Hyafil N, Boutilier C (2004) Regret minimizing equilibria and mechanisms for games with strict type uncertainty. Proc. 20th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 268–277.Google Scholar
• [66] Khodak M, Balcan MFF, Talwalkar A, Vassilvitskii S (2022) Learning predictions for algorithms with predictions. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Advances in Neural Information Processing Systems, vol. 35 (Curran Associates, Red Hook, NY), 3542–3555.Google Scholar
• [67] Kinoshita H, Osogami T, Miyaguchi K (2024) Socially efficient mechanism on the minimum budget. Preprint, submitted July 26, https://arxiv.org/abs/2407.18515.Google Scholar
• [68] Kleinberg R, Yuan Y (2013) On the ratio of revenue to welfare in single-parameter mechanism design. Proc. 14th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 589–602.Google Scholar
• [69] Krishna V, Perry M (1998) Efficient mechanism design. Working paper, Pennsylvania State University, University Park.Google Scholar
• [70] Leyton-Brown K, Milgrom P, Segal I (2017) Economics and computer science of a radio spectrum reallocation. Proc. Natl. Acad. Sci. USA 114(28):7202–7209.Crossref, Google Scholar
• [71] Li S (2017) Obviously strategy-proof mechanisms. Amer. Econom. Rev. 107(11):3257–3287.Crossref, Google Scholar
• [72] Likhodedov A, Sandholm T (2004) Methods for boosting revenue in combinatorial auctions. Proc. 19th Natl. Conf. Artificial Intelligence (AAAI Press, Washington, DC), 232–237.Google Scholar
• [73] Likhodedov A, Sandholm T (2005) Approximating revenue-maximizing combinatorial auctions. Proc. 20th Natl. Conf. Artificial Intelligence (AAAI Press, Washington, DC), 267–273.Google Scholar
• [74] Lu P, Wan Z, Zhang J (2024) Competitive auctions with imperfect predictions. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1155–1183.Google Scholar
• [75] Malakhov A, Vohra RV (2009) An optimal auction for capacity constrained bidders: A network perspective. Econom. Theory 39(1):113–128.Crossref, Google Scholar
• [76] McAfee RP, Reny PJ (1992) Correlated information and mechanism design. Econometrica 60(2):395–421.Crossref, Google Scholar
• [77] Medina A, Vassilvitskii S (2017) Revenue optimization with approximate bid predictions. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Red Hook, NY).Google Scholar
• [78] Mitzenmacher M, Vassilvitskii S (2022) Algorithms with predictions. Comm. ACM 65(7):33–35.Crossref, Google Scholar
• [79] Morgenstern J, Roughgarden T (2016) Learning simple auctions. Feldman V, Rakhlin A, Shamir O, eds. Proc. 29th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 49 (JMLR.org), 1298–1318.Google Scholar
• [80] Myerson R (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• [81] Myerson R, Satterthwaite M (1983) Efficient mechanisms for bilateral trading. J. Econom. Theory 29(2):265–281.Crossref, Google Scholar
• [82] Pai MM, Vohra R (2014) Optimal auctions with financially constrained buyers. J. Econom. Theory 150:383–425.Crossref, Google Scholar
• [83] Pieroth F, Sandholm T (2024) Verifying approximate equilibrium in auctions. Preprint, submitted August 21, https://arxiv.org/abs/2408.11445.Google Scholar
• [84] Prasad S, Balcan MF, Sandholm T (2025) Revenue-optimal efficient mechanism design with general type spaces. Preprint, submitted May 19, https://arxiv.org/abs/2505.13687.Google Scholar
• [85] Prasad S, Balcan MF, Sandholm T (2026) Weakest bidder types and new core-selecting combinatorial auctions. Proc. 40th AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 17206–17214.Google Scholar
• [86] Roberts K (1979) The characterization of implementable social choice rules. Laffont JJ, ed. Aggregation and Revelation of Preferences (North-Holland, Amsterdam), 321–349.Google Scholar
• [87] Roth AE (2018) Marketplaces, markets, and market design. Amer. Econom. Rev. 108(7):1609–1658.Crossref, Google Scholar
• [88] Rothkopf M, Pekeč A, Harstad R (1998) Computationally manageable combinatorial auctions. Management Sci. 44(8):1131–1147.Link, Google Scholar
• [89] Sandholm T (2007) Expressive commerce and its application to sourcing: How we conducted $35 billion of generalized combinatorial auctions. AI Magazine 28(3):45–58.Google Scholar
• [90] Sandholm T (2013) Very-large-scale generalized combinatorial multi-attribute auctions: Lessons from conducting $60 billion of sourcing. Neeman Z, Roth A, Vulkan N, eds. Handbook of Market Design (Oxford University Press, Oxford, UK), 379–412.Crossref, Google Scholar
• [91] Sandholm T, Likhodedov A (2015) Automated design of revenue-maximizing combinatorial auctions. Oper. Res. 63(5):1000–1025.Link, Google Scholar
• [92] Sandholm T, Suri S, Gilpin A, Levine D (2005) CABOB: A fast optimal algorithm for winner determination in combinatorial auctions. Management Sci. 51(3):374–390.Link, Google Scholar
• [93] Varian HR, Harris C (2014) The VCG auction in theory and practice. Amer. Econom. Rev. 104(5):442–445.Crossref, Google Scholar
• [94] Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8–37.Crossref, Google Scholar
• [95] Vohra RV (2011) Mechanism Design: A Linear Programming Approach, Econometric Society Monographs (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [96] Walsh W, Parkes D, Sandholm T, Boutilier C (2008) Computing reserve prices and identifying the value distribution in real-world auctions with market disruptions. Proc. 23rd AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC).Google Scholar
• [97] Xu C, Lu P (2022) Mechanism design with predictions. De Raedt L, ed. Proc 31st Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization, Vienna), 571–577.Google Scholar