Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities

References

• [1] Babaioff M, Nisan N (2004) Concurrent auctions across the supply chain. J. Artificial Intelligence Res. 21(1):595–629.Crossref, Google Scholar
• [2] Babaioff M, Walsh WE (2003) Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation. Proc. 4th ACM Conf. Electronic Commerce EC ‘03 (Association for Computing Machinery, New York), 64–75.Google Scholar
• [3] Babaioff M, Goldner K, Gonczarowski YA (2020) Bulow-Klemperer-style results for welfare maximization in two-sided markets. Chawla S, ed. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms, SODA 2020 (SIAM), 2452–2471.Google Scholar
• [4] Babaioff M, Cai Y, Gonczarowski YA, Zhao M (2018) The best of both worlds: Asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade. Proc. 2018 ACM Conf. Econom. Comput. EC ‘18 (Association for Computing Machinery, New York), 373.Google Scholar
• [5] Blumrosen L, Dobzinski S (2014) Reallocation mechanisms. Proc. Fifteenth ACM Conf. Econom. Comput. EC ‘14 (Association for Computing Machinery, New York), 617.Google Scholar
• [6] Blumrosen L, Dobzinski S (2021) (Almost) efficient mechanisms for bilateral trading. Games Econom. Behav. 130(C):369–383.Crossref, Google Scholar
• [7] Blumrosen L, Mizrahi Y (2016) Approximating gains-from-trade in bilateral trading. Proc. 12th Internat. Conf. Web Internet Econom. Vol. 10123 WINE 2016 (Springer-Verlag, Berlin), 400–413.Google Scholar
• [8] Brustle J, Cai Y, Wu F, Zhao M (2017) Approximating gains from trade in two-sided markets via simple mechanisms. Proc. 2017 ACM Conf. Econom. Comput. EC ‘17 (Association for Computing Machinery, New York), 589–590.Google Scholar
• [9] Bulow J, Klemperer P (1996) Auctions vs. negotiations. Amer. Econom. Rev. 86(1):180–194.Google Scholar
• [10] Cai Y, Zhao M (2019) Simple mechanisms for profit maximization in multi-item auctions. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 217–236.Google Scholar
• [11] Cai Y, Goldner K, Ma S, Zhao M (2021) On multi-dimensional gains from trade maximization. Proc. 32nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics), 1079–1098.Google Scholar
• [12] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput. STOC 2010 (Association for Computing Machinery, New York), 311–320.Google Scholar
• [13] Clarke E (1971) Multipart pricing of public goods. Public Choice 11(1):17–33.Crossref, Google Scholar
• [14] Colini-Baldeschi R, de Keijzer B, Leonardi S, Turchetta S (2016) Approximately efficient double auctions with strong budget balance. Proc. Twenty-Seventh Annual ACM-SIAM Sympos. Discrete Algorithms SODA ‘16 (Society for Industrial and Applied Mathematics, Philadelphia), 1424–1443.Google Scholar
• [15] Colini-Baldeschi R, Goldberg P, de Keijzer B, Leonardi S, Turchetta S (2017) Fixed price approximability of the optimal gain from trade. Lecture Notes in Computer Science, vol. 10660 (Springer-Verlag, Berlin), 146–160.Google Scholar
• [16] Colini-Baldeschi R, Goldberg PW, de Keijzer B, Leonardi S, Roughgarden T, Turchetta R (2020) Approximately efficient two-sided combinatorial auctions. ACM Trans. Econom. Comput. 8(1):4.Google Scholar
• [17] Correa JR, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput. EC ’17 (Association for Computing Machinery, New York), 169–186.Google Scholar
• [18] Deng Y, Mao J, Sivan B, Wang K (2022) Approximately efficient bilateral trade. Proc. 54th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 718–721.Google Scholar
• [19] Dütting P, Roughgarden T, Talgam-Cohen I (2014) Modularity and greed in double auctions. Proc. Fifteenth ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 241–258.Google Scholar
• [20] Dütting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. Umans C, ed. 58th IEEE Annual Sympos. Foundations Comput. Sci. FOCS 2017 (IEEE Computer Society), 540–551.Google Scholar
• [21] Dütting P, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2021) Efficient two-sided markets with limited information. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1452–1465.Google Scholar
• [22] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Czumaj A, ed. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA 2018 (Society for Industrial and Applied Mathematics, Philadelphia), 700–714.Google Scholar
• [23] Feldman M, Gonen R (2018) Removal and threshold pricing: Truthful two-sided markets with multi-dimensional participants. Deng X, ed. Algorithmic Game Theory (Springer International Publishing, Cham, Switzerland), 163–175.Crossref, Google Scholar
• [24] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Indyk P, ed. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2015 (Society for Industrial and Applied Mathematics, Philadelphia), 123–135.Google Scholar
• [25] Gerstgrasser M, Goldberg PW, de Keijzer B, Lazos P, Skopalik A (2019) Multi-unit bilateral trade. Proc. AAAI Conf. Artificial Intelligence, 1973–1980.Google Scholar
• [26] Groves T (1973) Incentives in teams. Econometrica 41(4):617–631.Crossref, Google Scholar
• [27] Hajiaghayi MT, Kleinberg RD, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. Twenty-Second AAAI Conf. Artificial Intelligence (AAAI Press), 58–65.Google Scholar
• [28] Kang ZY, Vondrák J (2019) Fixed-price approximations to optimal efficiency in bilateral trade. Preprint, submitted September 22, http://dx.doi.org/10.2139/ssrn.3460336.Google Scholar
• [29] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. Forty-Fourth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• [30] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• [31] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probab. Banach Spaces 4:197–266.Google Scholar
• [32] Lucier B (2017) An economic view of prophet inequalities. SIGecom. Exchanges 16(1):24–47.Crossref, Google Scholar
• [33] McAfee R (1992) A dominant strategy double auction. J. Econom. Theory 56(2):434–450.Crossref, Google Scholar
• [34] Myerson RB (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• [35] Myerson R, Satterthwaite M (1983) Efficient mechanisms for bilateral trading. J. Econom. Theory 29(2):265–281.Crossref, Google Scholar
• [36] Niazadeh R, Yuan Y, Kleinberg R (2014) Simple and near-optimal mechanisms for market intermediation. Liu TY, Qi Q, Ye Y, eds. Web and Internet Economics (Springer International Publishing, Cham, Switzerland), 386–399.Crossref, Google Scholar
• [37] Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12:1213–1216.Crossref, Google Scholar
• [38] Segal-Halevi E, Hassidim A, Aumann Y (2016) SBBA: A strongly-budget-balanced double-auction mechanism. Gairing M, Savani R, eds. Algorithmic Game Theory SAGT 2016, Lecture Notes in Computer Science, vol. 9928 (Springer, Berlin), 260–272.Crossref, Google Scholar
• [39] Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8–37.Crossref, Google Scholar