1 Search Results for "Psomas, Alexandros"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.3
Algorithmic Persuasion with Evidence

Authors: Martin Hoefer, Pasin Manurangsi, and Alexandros Psomas

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We consider a game of persuasion with evidence between a sender and a receiver. The sender has private information. By presenting evidence on the information, the sender wishes to persuade the receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender’s utility depends solely on whether or not the receiver takes the action. The receiver’s utility depends on both the action as well as the sender’s private information. We study three natural variations. First, we consider sequential equilibria of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and then the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and then the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, as well as polynomial-time algorithms for special cases. Among our results is an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm for a natural problem in algorithmic economics.
Cite as

Martin Hoefer, Pasin Manurangsi, and Alexandros Psomas. Algorithmic Persuasion with Evidence. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hoefer_et_al:LIPIcs.ITCS.2021.3,
  author =	{Hoefer, Martin and Manurangsi, Pasin and Psomas, Alexandros},
  title =	{{Algorithmic Persuasion with Evidence}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.3},
  URN =		{urn:nbn:de:0030-drops-135420},
  doi =		{10.4230/LIPIcs.ITCS.2021.3},
  annote =	{Keywords: Bayesian Persuasion, Semidefinite Programming, Approximation Algorithms}
}
  • Refine by Author
  • 1 Hoefer, Martin
  • 1 Manurangsi, Pasin
  • 1 Psomas, Alexandros

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Bayesian Persuasion
  • 1 Semidefinite Programming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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