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.
Introduction
In strategic environments, information is often as valuable as the actions themselves. Signaling—the strategic disclosure of information by a knowledgeable party to influence the behavior of others—is a cornerstone of information economics. A classic example is the "Market for Lemons," where a seller’s private knowledge about a car's quality dictates the market's equilibrium.
This paper investigates the computational complexity of Zero-Sum Signaling. In this model, two players, Alice and Bob, engage in a zero-sum game where Alice’s gain is Bob’s loss. A third party, Sam (the signaler), observes the true state of the game (the payoff matrix) and broadcasts a public signal to both players. Upon receiving the signal, Alice and Bob update their beliefs and play the resulting Nash equilibrium. Sam’s objective is to design a signaling scheme—a mapping from game states to probability distributions over signals—that maximizes Alice’s expected payoff.
While previous research by Shaddin Dughmi (2014) established that finding an optimal scheme is difficult under the "Planted Clique" assumption, a fundamental question remained: Does an additive Polynomial Time Approximation Scheme (PTAS) exist? This paper resolves this by proving that even finding an approximately optimal solution is computationally intensive.
Complexity of Honest Signaling
The primary contribution of the paper is the proof that finding an $\epsilon$-approximately optimal signaling scheme requires quasi-polynomial time, specifically $n^{\Omega(\log n)}$, assuming the Exponential Time Hypothesis (ETH). This result is particularly significant because it is "tight"; it matches the upper bound of the known quasi-polynomial time algorithm developed by Cheng et al. (2015).
To establish this hardness, the author employs a reduction from the 2-ary Constraint Satisfaction Problem (2-CSP). The reduction maps a 2-CSP instance over $n$ variables to a zero-sum game where Alice and Bob’s strategies correspond to variable assignments. The core technical innovation is the use of "birthday repetition." By leveraging the logic of the birthday paradox, the reduction ensures that if Alice and Bob select random subsets of variables, they are likely to share a constraint. If the underlying CSP is difficult to satisfy, Alice’s payoff in the signaling game is capped, thereby linking the difficulty of the CSP to the difficulty of the signaling problem.
By basing the hardness on ETH rather than the Planted Clique assumption, the paper moves the result from average-case complexity to a more robust worst-case foundation.
The Cost of Dishonesty: Lying in Signaling
Beyond the standard "honest" model, the paper introduces a novel framework for Dishonest Signaling. In this scenario, Sam publicly commits to a specific signaling scheme ($\phi_{alleged}$) to influence Alice and Bob’s beliefs, but secretly executes a different scheme ($\phi_{real}$). Alice and Bob, acting on the assumption of Sam's honesty, play the equilibrium corresponding to the alleged signal, while the actual payoffs are determined by the state and the signal Sam actually sent.
This model reveals a stark increase in computational complexity. While honest signaling is solvable in quasi-polynomial time, the dishonest model is strictly harder. The author proves that in the lying model, even finding a $(1 - 2^{-n})$-approximation is NP-hard. This suggests that the ability to decouple signals from the actual state of nature creates a search space so vast that even a marginal approximation of the optimal "lie" is computationally intractable.
Key Results and Theorems
The paper’s findings are summarized in three landmark results:
- Theorem 1.2 (ETH-Hardness): Assuming ETH, finding an additive $\epsilon$-approximation for Zero-Sum Signaling requires $n^{\Omega(\log n)}$ time. This effectively precludes the existence of a standard PTAS.
- Theorem 1.3 (Multiplicative Hardness): Finding a multiplicative $(1-\epsilon)$-approximation is NP-hard.
- Theorem 1.5 (Lying Hardness): In the dishonest signaling model, finding an additive $(1 - 2^{-n})$-approximation is NP-hard, representing a remarkably strong hardness-of-approximation result.
Conclusion and Future Directions
This research provides a definitive answer to the complexity of signaling in zero-sum games, demonstrating that the problem is inherently quasi-polynomial. Furthermore, it highlights that the power to deceive—while potentially beneficial to the signaler—comes with a significant computational burden.
Several avenues for future research remain. The dishonest model currently assumes that players have unwavering trust in the signaler. Future work could explore repeated games where players update their trust in the signaler based on observed outcomes (reputation dynamics). Additionally, while the multiplicative hardness result currently applies to games with potentially negative payoffs, extending this to strictly non-negative payoff matrices remains an open challenge in the field of algorithmic game theory.
Summary updated