ETH-Hardness for Signaling in Symmetric Zero-Sum Games.
Aviad Rubinstein · arXiv (Cornell University) · 2015
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 [CCDEHT'15] and resolves an open question of [Dughmi'14]. We also prove that finding a multiplicative approximation is NP-hard.