REVIEW 1 cited by
Honest signaling in zero-sum games is hard, and lying is even harder
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 1 Pith paper
-
Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud
Efficient algorithms exist for optimal private Bayesian persuasion of voters under k-voting and plurality rules, but optimal public persuasion is NP-hard to approximate by any factor.
Discussion (0). Continue with ORCID to comment.