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

arXiv: https://arxiv.org/abs/1510.04991 · HTML: https://mlsanity.com/paper/1510.04991/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2015.

## Built on by (most cited first, 1 of 1)

- [A Note on Hardness of Computing Recursive Teaching Dimension](https://mlsanity.com/paper/2307.09792/) (2023)

## Abstract (arXiv)

We prove that, assuming the exponential time hypothesis, finding an ε-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.