Honest signaling in zero-sum games is hard, and lying is even harder

DOI10.4230/LIPICS.ICALP.2017.77MaRDI QIDQ5111408zbMATH OpenOpenAlexFDO

Authors Aviad Rubinstein

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1510.04991

zbMATH Keywords

zero-sum gamessignalingalgorithmic game theorybirthday repetition

Mathematics Subject Classification ID

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)

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.

Recommendations

• Games with zero-knowledge signaling
• On the hardness of designing public signals
• Dishonest signalling in a variant of pygmalion game
• Noise-proof equilibria in two-action signaling games
• Algorithms for persuasion with limited communication

Cited in

(7)

• Delegated online search
• Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models
• On the hardness of designing public signals
• Dishonest signalling in a variant of pygmalion game
• Public Bayesian persuasion: being almost optimal and almost persuasive
• Algorithms for persuasion with limited communication
• 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)