Bilateral Trade: A Regret Minimization Perspective

References

• [1] Agrawal S, Devanur NR (2014) Bandits with concave rewards and convex knapsacks. Proc. ACM Conference on Economics and Computation (EC) (ACM, New York), 989–1006.Google Scholar
• [2] Amin K, Rostamizadeh A, Syed U (2013) Learning prices for repeated auctions with strategic buyers. Proc. Internat. Conf. Neural Information Processing Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY), 1169–1177.Google Scholar
• [3] Anthony M, Bartlett PL (2002) Neural Network Learning: Theoretical Foundations. (Cambridge University Press, Cambridge, UK).Google Scholar
• [4] Audibert J, Bubeck S (2009) Minimax policies for adversarial and stochastic bandits. Proc. 22nd Ann. Conf. Learning Theory (COLT). https://www.cs.mcgill.ca/∼colt2009/proceedings.html.Google Scholar
• [5] Azar Y, Fiat A, Fusco F (2022) An α-regret analysis of adversarial bilateral trade. Proc. Ann. Conf. Neural Information Processing Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY).Google Scholar
• [6] Babaioff M, Dughmi S, Kleinberg R, Slivkins A (2015) Dynamic pricing with limited supply. ACM Trans. Econom. Comput. 3(1):1–26.Crossref, Google Scholar
• [7] Badanidiyuru A, Kleinberg R, Slivkins A (2018) Bandits with knapsacks. J. ACM 65(3):1–55.Crossref, Google Scholar
• [8] Bartók G, Foster DP, Pál D, Rakhlin A, Szepesvári C (2014) Partial monitoring—classification, regret bounds, and algorithms. Math. Oper. Res. 39(4):967–997.Link, Google Scholar
• [9] Blum A, Hartline JD (2005) Near-optimal online auctions. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (ACM, New York), 1156–1163.Google Scholar
• [10] Blum A, Kumar V, Rudra A, Wu F (2004) Online learning in online auctions. Theoret. Comput. Sci. 324(2–3):137–146.Crossref, Google Scholar
• [11] Blumrosen L, Dobzinski S (2014) Reallocation mechanisms. Proc. ACM Conference on Economics and Computation (EC) (ACM, New York), 617.Google Scholar
• [12] Blumrosen L, Dobzinski S (2021) (Almost) efficient mechanisms for bilateral trading. Games Econom. Behav. 130:369–383.Crossref, Google Scholar
• [13] Braun A, Kesselheim T (2021) Truthful mechanisms for two-sided markets via prophet inequalities. Proc. ACM Conf. Economics and Computation (EC) (ACM, New York), 202–203.Google Scholar
• [14] Broder J, Rusmevichientong P (2012) Dynamic pricing under a general parametric choice model. Oper. Res. 60(4):965–980.Link, Google Scholar
• [15] Brustle J, Cai Y, Wu F, Zhao M (2017) Approximating gains from trade in two-sided markets via simple mechanisms. Proc. ACM Conf. Economics and Computation (EC) (ACM, New York), 589–590.Google Scholar
• [16] Bubeck S, Devanur NR, Huang Z, Niazadeh R (2017) Online auctions and multi-scale online learning. Proc. ACM Conf. Econom. Computat. (EC) (ACM, New York), 497–514.Google Scholar
• [17] Cesa-Bianchi N, Cesari T, Perchet V (2019) Dynamic pricing with finitely many unknown valuations. Proc. 30th Internat. Conf. Algorithmic Learning Theory (PMLR), 247–273.Google Scholar
• [18] Cesa-Bianchi N, Cesari TR, Colomboni R, Fusco F, Leonardi S (2021) A regret analysis of bilateral trade. Proc. ACM Conf. Econom. Computat. (EC) (ACM, New York), 289–309.Google Scholar
• [19] Cesa-Bianchi N, Gentile C, Mansour Y (2015) Regret minimization for reserve prices in second-price auctions. IEEE Trans. Inform. Theory 61(1):549–564.Crossref, Google Scholar
• [20] Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games. (Cambridge University Press, New York).Crossref, Google Scholar
• [21] Cesa-Bianchi N, Lugosi G, Stoltz G (2006) Regret minimization under partial monitoring. Math. Oper. Res. 31(3):562–580.Link, Google Scholar
• [22] Cesari TR, Colomboni R (2021) A nearest neighbor characterization of Lebesgue points in metric measure spaces. Math. Stat. Learning 3(1):71–112.Crossref, Google Scholar
• [23] Cohen MC, Lobel I, Leme RP (2020) Feature-based dynamic pricing. Management Sci. 66(11):4921–4943.Link, Google Scholar
• [24] Colini-Baldeschi R, de Keijzer B, Leonardi S, Turchetta S (2016) Approximately efficient double auctions with strong budget balance. ACM-SIAM Symposium on Discrete Algorithms (SODA) (ACM, New York), 1424–1443.Google Scholar
• [25] Colini-Baldeschi R, Goldberg PW, de Keijzer B, Leonardi S, Turchetta S (2017) Fixed price approximability of the optimal gain from trade. Internat. Conf. Web Internet Econom. (Springer, Berlin), 146–160.Google Scholar
• [26] Cover T (1965) Behavior of sequential predictors of binary sequences. Proc. 4th Prague Conf. Information Theory, Statistical Decision Functions and Random Processes, 263–272 (Publishing House of the Czechoslovak Academy of Sciences).Google Scholar
• [27] Daskalakis C, Syrgkanis V (2016) Learning in auctions: Regret is hard, envy is easy. IEEE Symposium on Foundations of Computer Science (FOCS) (IEEE, Piscataway, NJ), 219–228.Google Scholar
• [28] den Boer AV (2015) Dynamic pricing and learning: Historical origins, current research, and new directions. Surv. Oper. Res. Management Sci. 20(1):1–18.Crossref, Google Scholar
• [29] den Boer AV, Keskin NB (2020) Discontinuous demand functions: Estimation and pricing. Management Sci. 66(10):4516–4534.Link, Google Scholar
• [30] Deng Y, Mao J, Sivan B, Wang K (2022) Approximately efficient bilateral trade. Proc. ACM Symposium on Theory of Computing (STOC) (ACM, New York), 718–721.Google Scholar
• [31] Devanur NR, Peres Y, Sivan B (2019) Perfect Bayesian equilibria in repeated sales. Games Econom. Behav. 118:570–588.Crossref, Google Scholar
• [32] Drutsa A (2018) Weakly consistent optimal pricing algorithms in repeated posted-price auctions with strategic buyer. Proc. Internat. Conf. Machine Learning, (PMLR), 1318–1327.Google Scholar
• [33] Dütting P, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2021) Efficient two-sided markets with limited information. Proc. Symposium on Theory of Computing (STOC) (ACM, New York), 1452–1465.Google Scholar
• [34] Fei Y (2022) Improved approximation to first-best gains-from-trade. WINE. Lecture Notes in Computer Science, vol. 13778 (Springer, New York), 204–218.Google Scholar
• [35] Hagerty KM, Rogerson WP (1987) Robust trading mechanisms. J. Econom. Theory 42(1):94–107.Crossref, Google Scholar
• [36] Ho C, Slivkins A, Vaughan JW (2016) Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. J. Artificial Intelligence Res. 55:317–359.Crossref, Google Scholar
• [37] Kang ZY, Pernice F, Vondrák J (2022) Fixed-price approximations in bilateral trade. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (ACM, New York), 2964–2985.Google Scholar
• [38] Kleinberg RD, Leighton FT (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions. Proc. IEEE Symposium on Foundations of Computer Science (FOCS) (IEEE, Piscataway, NJ), 594–605.Google Scholar
• [39] Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [40] Li Y, Long PM, Srinivasan A (2001) Improved bounds on the sample complexity of learning. J. Comput. System Sci. 62(3):516–527.Crossref, Google Scholar
• [41] Lykouris T, Syrgkanis V, Tardos E (2016) Learning and efficiency in games with dynamic population. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (ACM, New York), 120–129.Google Scholar
• [42] Massart P (1990) The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Probab. 18(3):1269–1283.Crossref, Google Scholar
• [43] Mohri M, Medina AM (2014) Optimal regret minimization in posted-price auctions with strategic buyers. Proc. Internat. Conf. Neural Information Processing Systems (NeurIPS) (Curran Associates, Inc., Red Hook, NY), 1871–1879.Google Scholar
• [44] Myerson RB, Satterthwaite MA (1983) Efficient mechanisms for bilateral trading. J. Econom. Theory. 29(2):265–281.Crossref, Google Scholar
• [45] Naaman M (2021) On the tight constant in the multivariate Dvoretzky–Kiefer–Wolfowitz inequality. Statist. Probab. Lett. 173:109088.Crossref, Google Scholar
• [46] Slivkins A (2019) Introduction to multi-armed bandits. Foundations Trends Machine Learn. 12(1–2):1–286.Crossref, Google Scholar
• [47] Slivkins A, Zeevi A (2015) Dynamic pricing under model uncertainty. Tutorial given at the 16th ACM Conference on Economics and Computation (ACM, New York).Google Scholar
• [48] Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance. 16(1):8–37.Crossref, Google Scholar
• [49] Williams D (1991) Probability with Martingales (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar