2026-07-20T11:45:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7405 2024-03-06T10:40:26Z ddc:004 open_access

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder Rubinstein, Aviad Signaling Zero-sum Games Algorithmic Game Theory birthday repetition 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aviad Rubinstein 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.77 urn:nbn:de:0030-drops-74057 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.77 eng https://creativecommons.org/licenses/by/3.0/legalcode