Honest signaling in zero-sum games is hard, and lying is even harder
From MaRDI portal
Publication:5111408
DOI10.4230/LIPICS.ICALP.2017.77zbMATH Open1441.68080arXiv1510.04991OpenAlexW2963620975MaRDI QIDQ5111408FDOQ5111408
Publication date: 27 May 2020
Abstract: We prove that, assuming the exponential time hypothesis, finding an epsilon-approximately optimal symmetric signaling scheme in a two-player zero-sum game requires quasi-polynomial time. This is tight by [Cheng et al., FOCS'15] and resolves an open question of [Dughmi, FOCS'14]. We also prove that finding a multiplicative approximation is NP-hard. We also introduce a new model where a dishonest signaler may publicly commit to use one scheme, but post signals according to a different scheme. For this model, we prove that even finding a (1-2^{-n})-approximately optimal scheme is NP-hard.
Full work available at URL: https://arxiv.org/abs/1510.04991
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Signaling and communication in game theory (91A28) Algorithmic game theory and complexity (91A68)
Cited In (5)
- Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models
- Algorithms for Persuasion with Limited Communication
- Delegated online search
- Public Bayesian persuasion: being almost optimal and almost persuasive
- A note on hardness of computing recursive teaching dimension
This page was built for publication: Honest signaling in zero-sum games is hard, and lying is even harder
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111408)
