Document Open Access Logo

Sequential Decision Making With Information Asymmetry (Invited Talk)

Authors Jiarui Gan , Rupak Majumdar , Goran Radanovic , Adish Singla

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2022.4.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Author Details

Jiarui Gan
  • University of Oxford, UK
Rupak Majumdar
  • Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany
Goran Radanovic
  • Max Planck Institute for Software Systems (MPI-SWS), Saarbrücken, Germany
Adish Singla
  • Max Planck Institute for Software Systems (MPI-SWS), Saarbrücken, Germany

Funding

  • Majumdar, Rupak: This research was funded in part by the Deutsche Forschungsgemeinschaft project 389792660 TRR 248-CPEC.

Cite AsGet BibTex

Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Sequential Decision Making With Information Asymmetry (Invited Talk). In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CONCUR.2022.4

Abstract

We survey some recent results in sequential decision making under uncertainty, where there is an information asymmetry among the decision-makers. We consider two versions of the problem: persuasion and mechanism design. In persuasion, a more-informed principal influences the actions of a less-informed agent by signaling information. In mechanism design, a less-informed principal incentivizes a more-informed agent to reveal information by committing to a mechanism, so that the principal can make more informed decisions. We define Markov persuasion processes and Markov mechanism processes that model persuasion and mechanism design into dynamic models. Then we survey results on optimal persuasion and optimal mechanism design on myopic and far-sighted agents. These problems are solvable in polynomial time for myopic agents but hard for far-sighted agents.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Bayesian persuasion
  • Automated mechanism design
  • Markov persuasion processes
  • Markov mechanism processes
  • Myopic agents

Metrics

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

References

  1. Robert J. Aumann and Michael B. Maschler. Repeated Games with Incomplete Information. MIT Press, 1995. Google Scholar
  2. Dirk Bergemann and Juuso Välimäki. Dynamic mechanism design: An introduction. Journal of Economic Literature, 57(2):235-74, 2019. Google Scholar
  3. Andrea Celli, Stefano Coniglio, and Nicola Gatti. Private Bayesian persuasion with sequential games. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'20), pages 1886-1893, 2020. Google Scholar
  4. Krishnendu Chatterjee, Martin Chmelik, and Mathieu Tracol. What is decidable about partially observable markov decision processes with ω-regular objectives. J. Comput. Syst. Sci., 82(5):878-911, 2016. URL: https://doi.org/10.1016/j.jcss.2016.02.009.
  5. Krishnendu Chatterjee and Thomas A. Henzinger. A survey of stochastic ω-regular games. J. Comput. Syst. Sci., 78(2):394-413, 2012. URL: https://doi.org/10.1016/j.jcss.2011.05.002.
  6. Anne Condon. The complexity of stochastic games. Inf. Comput., 96(2):203-224, 1992. URL: https://doi.org/10.1016/0890-5401(92)90048-K.
  7. Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. In Adnan Darwiche and Nir Friedman, editors, Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence (UAI'02), pages 103-110. Morgan Kaufmann, 2002. Google Scholar
  8. Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC'04), pages 132-141, 2004. Google Scholar
  9. Sanmay Das, Emir Kamenica, and Renee Mirka. Reducing congestion through information design. In Proceedings of the 55th Allerton Conference on Communication, Control, and Computing, pages 1279-1284, 2017. Google Scholar
  10. S. Dughmi. Algorithmic information structure design. ACM SIGecom Exch., 15(2):2-24, 2017. Google Scholar
  11. Shaddin Dughmi and Haifeng Xu. Algorithmic Bayesian persuasion. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 412-425. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897583.
  12. J. Ely. Beeps. American Economic Review, 107(1):31-53, 2017. Google Scholar
  13. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM J. Comput., 39(6):2531-2597, 2010. URL: https://doi.org/10.1137/080720826.
  14. J. Filar and K. Vrieze. Competitive Markov Decision Processes. Springer-Verlag, 1997. Google Scholar
  15. Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential decision-making. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, (AAAI'22). AAAI Press, 2022. Google Scholar
  16. Emir Kamenica. Bayesian persuasion and information design. Annual Review of Economics, 11:249-272, 2019. Google Scholar
  17. Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590-2615, 2011. Google Scholar
  18. Andrew Kephart and Vincent Conitzer. Complexity of mechanism design with signaling costs. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS'15), pages 357-365, 2015. Google Scholar
  19. Andrew Kephart and Vincent Conitzer. The revelation principle for mechanism design with reporting costs. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC'16), pages 85-102, 2016. Google Scholar
  20. Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. Artif. Intell., 147(1-2):5-34, 2003. URL: https://doi.org/10.1016/S0004-3702(02)00378-8.
  21. Roger B. Myerson. Incentive compatibility and the bargaining problem. Econometrica, 47(1):61-73, 1979. Google Scholar
  22. Alessandro Pavan. Dynamic mechanism design: Robustness and endogenous types. In Advances in Economics and Econometrics: Eleventh World Congress, volume 1, pages 1-62, 2017. Google Scholar
  23. J. Renault, E. Solan, and N. Vieille. Optimal dynamic information provision. Games and Economic Behavior, 104:329-349, 2017. Google Scholar
  24. Tuomas Sandholm, Vincent Conitzer, and Craig Boutilier. Automated design of multistage mechanisms. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), volume 7, pages 1500-1506, 2007. Google Scholar
  25. Sylvain Sorin. A First Course on Zero-Sum Repeated Games. Springer, 2008. Google Scholar
  26. Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. CoRR, abs/2202.10678, 2022. URL: http://arxiv.org/abs/2202.10678.
  27. Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Automated mechanism design for classification with partial verification. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI'21), volume 35(6), pages 5789-5796, 2021. Google Scholar
  28. Hanrui Zhang and Vincent Conitzer. Automated dynamic mechanism design. Advances in Neural Information Processing Systems (NeurIPS'21), 34, 2021. Google Scholar
  29. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), pages 681-690. Association for Computing Machinery, 2006. Google Scholar
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