On Simple Mechanisms for Dependent Items

References

• Alaei S (2011) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. Proc. 52nd Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC).Google Scholar
• Alaei S, Fu H, Haghpanah N, Hartline JD (2013) The simple economics of approximately optimal auctions. Reingold O, ed. Proc. 54th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 628–637.Google Scholar
• Alaei S, Fu H, Haghpanah N, Hartline J, Malekian A (2012) Bayesian optimal auctions via multi- to single-agent reduction. Faltings B, Leyton-Brown K, Ipeirotis P, eds. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York).Google Scholar
• Babaioff M, Immorlica N, Lucier B, Weinberg SM (2014) A simple and approximately optimal mechanism for an additive buyer. Barak B, ed. Proc. 55th IEEE Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 21–30.Google Scholar
• Bateni M, Dehghani S, Hajiaghayi M, Seddighin S (2015) Revenue maximization for selling multiple correlated items. Bansal N, Finocchi I, eds. Algorithms-ESA 2015 23rd Annual Eur. Sympos., vol. 9294 (Springer, New York), 95–105.Google Scholar
• Bhalgat A, Gollapudi S, Munagala K (2013) Optimal auctions via the multiplicative weight method. Kearns MJ, McAfee RP, Tardos É, eds. Proc. Fourteenth ACM Conf. Electronic Commerce (ACM, New York), 73–90.Google Scholar
• Boucheron S, Lugosi G, Massart P (2000) A sharp concentration inequality with applications. Random Structures Algorithms 16(3):277–292.Crossref, Google Scholar
• Briest P, Chawla S, Kleinberg R, Weinberg SM (2015) Pricing lotteries. J. Econom. Theory 156:144–174.Crossref, Google Scholar
• Brustle J, Cai Y, Daskalakis C (2020) Multi-item mechanisms without item-independence: Learnability via robustness. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. Twenty-First ACM Conf. Econom. Comput. (EC’20) (ACM, New York), 715–761.Google Scholar
• Cai Y, Daskalakis C (2011) Extreme-value theorems for optimal multidimensional pricing. Ostrovsky R, ed. Proc. 52nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 522–531.Google Scholar
• Cai Y, Daskalakis C (2017) Learning multi-item auctions with (or without) samples. Preprint, submitted September 1, https://arxiv.org/abs/1709.00228.Google Scholar
• Cai Y, Huang Z (2013) Simple and nearly optimal multi-item auctions. Khanna S, ed. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 564–577.Google Scholar
• Cai Y, Oikonomou A (2021) On simple mechanisms for dependent items. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. (ACM, New York), 242–262.Google Scholar
• Cai Y, Zhao M (2016) Simple mechanisms for subadditive buyers via duality. Preprint, submitted November 21, https://arxiv.org/abs/1611.06910.Google Scholar
• Cai Y, Zhao M (2017) Simple mechanisms for subadditive buyers via duality. Hatami H, McKenzie P, King V, eds. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 170–183.Google Scholar
• Cai Y, Daskalakis C, Weinberg SM (2012a) An algorithmic characterization of multi-dimensional mechanisms. Karloff HJ, Pitassi T, eds. Proc. 44th Sympos. Theory Comput. Conf. (ACM, New York), 459–478.Google Scholar
• Cai Y, Daskalakis C, Weinberg SM (2012b) Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. Roughgarden T, ed. Proc. 53rd Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 130–139.Google Scholar
• Cai Y, Daskalakis C, Weinberg SM (2013) Understanding incentives: Mechanism design becomes algorithm design. Reingold O, ed. Proc. 54th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 618–627.Google Scholar
• Cai Y, Devanur NR, Weinberg SM (2016) A duality based unified approach to Bayesian mechanism design. Wichs D, Mansour Y, eds. Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 926–939.Google Scholar
• Chawla S, Miller JB (2016) Mechanism design for subadditive agents via an ex-ante relaxation. Conitzer V, Bergemann D, Chen Y, eds. Proc. 2016 ACM Conf. Econom. Comput (ACM, New York), 579–596.Google Scholar
• Chawla S, Hartline JD, Kleinberg RD (2007) Algorithmic pricing via virtual valuations. MacKie-Mason JK, Parkes DC, Resnick P, eds. Proc. 8th ACM Conf. Electronic Commerce (ACM, New York), 243–251.Google Scholar
• Chawla S, Malec DL, Sivan B (2010a) The power of randomness in Bayesian optimal mechanism design. Parkes DC, Dellarocas C, Tennenholtz M, eds. Proc. 11th ACM Conf. Electronic Commerce (ACM, New York), 149–158.Google Scholar
• Chawla S, Hartline JD, Malec DL, Sivan B (2010b) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput. (ACM, New York), 311–320.Google Scholar
• Dagan Y, Daskalakis C, Dikkala N, Jayanti S (2019a) Learning from weakly dependent data under Dobrushin’s condition. Beygelzimer A, Hsu D, eds. Proc. Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 99 (PMLR, New York), 914–928.Google Scholar
• Dagan Y, Daskalakis C, Dikkala N, Jayanti S (2019b) Learning from weakly dependent data under Dobrushin’s condition. Preprint, submitted June 21, https://arxiv.org/abs/1906.09247.Google Scholar
• Daskalakis C, Devanur NR, Weinberg SM (2015) Revenue maximization and ex-post budget constraints. Roughgarden T, Feldman M, Schwarz M, eds. Proc. 16th ACM Conf. Econom. Comput. (ACM, New York), 433–447.Google Scholar
• Daskalakis C, Dikkala N, Kamath G (2018) Testing ising models. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1989–2007.Google Scholar
• Daskalakis C, Dikkala N, Kamath G (2019) Testing ising models. IEEE Trans. Inform. Theory 65(11):6829–6852.Crossref, Google Scholar
• Dobruschin P (1968) The description of a random field by means of conditional probabilities and conditions of its regularity. Theory Probability Appl. 13(2):197–224.Crossref, Google Scholar
• Dobrushin R, Shlosman S (1987) Completely analytical interactions: Constructive description. J. Statist. Phys. 46(5–6):983–1014.Crossref, Google Scholar
• Dvoretzky A, Kiefer J, Wolfowitz J (1956) Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Statist. 27(3):642–669.Crossref, Google Scholar
• Gheissari R, Lubetzky E, Peres Y (2018) Concentration inequalities for polynomials of contracting ising models. Electronic Comm. Probability 23:1–12.Google Scholar
• Hart S, Nisan N (2019) Selling multiple correlated goods: Revenue maximization and menu-size complexity. J. Econom. Theory 183:991–1029.Crossref, Google Scholar
• Immorlica N, Singla S, Waggoner B (2020) Prophet inequalities with linear correlations and augmentations. Biró P, Hartline J, Ostrovsky M, Procaccia AD, eds. Proc. 21st ACM Conf. Econom. Comput. (ACM, New York), 159–185.Google Scholar
• Kindermann R, Snell L (1980) Markov Random Fields and Their Applications, vol. 1 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Karloff HJ, Pitassi T, eds. Proc. 44th Sympos. Theory Comput. Conf. (ACM, New York), 123–136.Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probability Banach Spaces 4:197–266.Google Scholar
• Lauritzen SL (1996) Graphical Models (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Levin DA, Peres Y, Wilmer EL (2009) Markov Chains and Mixing Times (American Mathematical Society, Providence, RI).Google Scholar
• Li X, Yao ACC (2013) On revenue maximization for selling multiple independently distributed items. Proc. Natl. Acad. Sci. USA 110(28):11232–11237.Crossref, Google Scholar
• Psomas A, Schvartzman A, Weinberg SM (2019) Smoothed analysis of multi-item auctions with correlated values. Karlin AR, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 417–418.Google Scholar
• Randall D (2006) Slow mixing of Glauber dynamics via topological obstructions. Stein C, ed. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms, vol. 22 (SIAM, Philadelphia), 870–879.Google Scholar
• Ronen A (2001) On approximating optimal auctions. Wellman MP, Shoham Y, eds. Proc. 3rd ACM Conf. Electronic Commerce (ACM, New York), 11–17.Google Scholar
• Rubinstein A, Weinberg SM (2015) Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. Roughgarden T, Feldman M, Schwarz M, eds. Proc. 16th ACM Conf. Econom. Comput. (ACM, New York), 377–394.Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals Probability 12(4):1213–1216.Crossref, Google Scholar
• Stroock DW, Zegarlinski B (1992) The logarithmic Sobolev inequality for discrete spin systems on a lattice. Comm. Math. Phys. 149(1):175–193.Crossref, Google Scholar
• Wu L (2006) Poincaré and transportation inequalities for Gibbs measures under the Dobrushin uniqueness condition. Ann. Probabilities 34(5):1960–1989.Google Scholar
• Yao AC (2015) An n-to-1 bidder reduction for multi-item auctions and its applications. Preprint, submitted June 12, https://arxiv.org/abs/1406.3278.Google Scholar