Document Open Access Logo

Interactive Communication in Bilateral Trade

Authors Jieming Mao, Renato Paes Leme, Kangning Wang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.105.pdf
  • Filesize: 0.72 MB
  • 21 pages

Document Identifiers

Author Details

Jieming Mao
  • Google Research, New York, NY, USA
Renato Paes Leme
  • Google Research, New York, NY, USA
Kangning Wang
  • Duke University, Durham, NC, USA

Cite AsGet BibTex

Jieming Mao, Renato Paes Leme, and Kangning Wang. Interactive Communication in Bilateral Trade. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 105:1-105:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.105

Abstract

We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents don't stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Solution concepts in game theory
  • Theory of computation → Exact and approximate computation of equilibria
Keywords
  • Bayesian persuasion
  • bilateral trade
  • information design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Noga Alon, Noam Nisan, Ran Raz, and Omri Weinstein. Welfare maximization with limited interaction. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1499-1512, 2015. URL: https://doi.org/10.1109/FOCS.2015.95.
  2. Sepehr Assadi. Combinatorial auctions do need modest interaction. ACM Trans. Econ. Comput., 8(1), March 2020. URL: https://doi.org/10.1145/3381521.
  3. Robert J Aumann and Sergiu Hart. Long cheap talk. Econometrica, 71(6):1619-1660, 2003. Google Scholar
  4. Robert J Aumann and Michael Maschler. Repeated games with incomplete information. MIT press, 1995. Google Scholar
  5. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137-166, 2003. URL: https://doi.org/10.1137/S0097539700375944.
  6. Moshe Babaioff, Yang Cai, Yannai A Gonczarowski, and Mingfei Zhao. The best of both worlds: Asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 373-373, 2018. Google Scholar
  7. Moshe Babaioff, Kira Goldner, and Yannai A Gonczarowski. Bulow-klemperer-style results for welfare maximization in two-sided markets. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2452-2471. SIAM, 2020. Google Scholar
  8. Ashwinkumar Badanidiyuru, Kshipra Bhawalkar, and Haifeng Xu. Targeting and signaling in ad auctions. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2545-2563. SIAM, 2018. Google Scholar
  9. Santiago R Balseiro, Vahab Mirrokni, Renato Paes Leme, and Song Zuo. Dynamic double auctions: Towards first best. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 157-172. SIAM, 2019. Google Scholar
  10. Dirk Bergemann, Benjamin Brooks, and Stephen Morris. The limits of price discrimination. American Economic Review, 105(3):921-57, 2015. Google Scholar
  11. Dirk Bergemann, Benjamin Brooks, and Stephen Morris. First-price auctions with general information structures: Implications for bidding and revenue. Econometrica, 85(1):107-143, 2017. Google Scholar
  12. Dirk Bergemann and Stephen Morris. Information design: A unified perspective. Journal of Economic Literature, 57(1):44-95, 2019. Google Scholar
  13. Dirk Bergemann and Martin Pesendorfer. Information structures in optimal auctions. Journal of economic theory, 137(1):580-609, 2007. Google Scholar
  14. Liad Blumrosen and Shahar Dobzinski. Reallocation mechanisms. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, pages 617-617, 2014. Google Scholar
  15. Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 589-590, 2017. Google Scholar
  16. Yang Cai, Kira Goldner, Steven Ma, and Mingfei Zhao. On multi-dimensional gains from trade maximization. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1079-1098. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.67.
  17. Kalyan Chatterjee and William Samuelson. Bargaining under incomplete information. Operations research, 31(5):835-851, 1983. Google Scholar
  18. Riccardo Colini-Baldeschi, Paul W Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, and Stefano Turchetta. Approximately efficient two-sided combinatorial auctions. ACM Transactions on Economics and Computation (TEAC), 8(1):1-29, 2020. Google Scholar
  19. Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1424-1443. SIAM, 2016. Google Scholar
  20. Constantinos Daskalakis, Christos Papadimitriou, and Christos Tzamos. Does information revelation improve revenue? In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 233-250, 2016. Google Scholar
  21. Shahar Dobzinski, Noam Nisan, and Sigal Oren. Economic efficiency requires interaction. In the 46th annual ACM symposium on Theory of computing (STOC), 2014. Google Scholar
  22. Laura Doval and Jeffrey C Ely. Sequential information design. Econometrica, 88(6):2575-2608, 2020. Google Scholar
  23. Shaddin Dughmi, David Kempe, and Ruixin Qiang. Persuasion with limited communication. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 663-680, 2016. Google Scholar
  24. Shaddin Dughmi and Haifeng Xu. Algorithmic bayesian persuasion. SIAM Journal on Computing, 50(3), 2021. Google Scholar
  25. Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Efficient two-sided markets with limited information. ACM Symposium on Theory of Computing, STOC’21, 2020. Google Scholar
  26. Yuval Emek, Michal Feldman, Iftah Gamzu, Renato PaesLeme, and Moshe Tennenholtz. Signaling schemes for revenue maximization. ACM Transactions on Economics and Computation (TEAC), 2(2):1-19, 2014. Google Scholar
  27. Péter Eső and Balazs Szentes. Optimal information disclosure in auctions and the handicap auction. The Review of Economic Studies, 74(3):705-731, 2007. Google Scholar
  28. Matthew Gentzkow and Emir Kamenica. Costly persuasion. American Economic Review, 104(5):457-62, 2014. Google Scholar
  29. Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590-2615, 2011. Google Scholar
  30. Zi Yang Kang and Jan Vondrák. Fixed-price approximations to optimal efficiency in bilateral trade. Available at SSRN 3460336, 2019. Google Scholar
  31. Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2):265-281, 1983. Google Scholar
  32. Noam Nisan and Avi Wigderson. Rounds in communication complexity revisited. SIAM J. Comput., 22(1):211-219, February 1993. URL: https://doi.org/10.1137/0222016.
  33. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209-213, New York, NY, USA, 1979. ACM. URL: https://doi.org/10.1145/800135.804414.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact