Abstract
In the study of strategic information disclosure, symmetric signaling in zero-sum games represents a fundamental challenge. While zero-sum games are typically computationally tractable, the problem of determining an optimal signaling scheme has remained elusive. This paper establishes that, under the Exponential Time Hypothesis (ETH), finding an $\epsilon$-approximately optimal symmetric signaling scheme requires quasi-polynomial time. This result is tight, matching existing upper bounds and resolving a long-standing open question. Furthermore, the paper demonstrates that finding a multiplicative approximation is NP-hard.
Introduction
Signaling, a core concept in information economics, involves a "principal" who possesses private knowledge about the state of the world and strategically reveals this information to agents to influence their equilibrium behavior. In the context of Symmetric Zero-Sum Signaling, two players, Alice and Bob, engage in a zero-sum game where the payoff matrix is drawn from a known distribution. A signaling scheme observes the specific realization of the matrix and broadcasts a public signal to both players. Alice’s objective is to design a scheme that maximizes her expected payoff in the resulting Nash equilibrium.
Historically, zero-sum games are considered the "easy" case of game theory, solvable in polynomial time via linear programming. However, the meta-level problem of information design—deciding what to tell the players—introduces significant complexity. Dughmi (2014) previously showed that finding an optimal signaling scheme is hard under the "Planted Clique" assumption. This research moves beyond average-case assumptions to provide a firm worst-case complexity foundation using the Exponential Time Hypothesis (ETH).
Methodology: Birthday Repetition and Payoff Engineering
The core of the proof relies on a sophisticated reduction from Constraint Satisfaction Problems (CSPs). The author transforms a CSP over $n$ variables into a distribution over $N \times N$ zero-sum games, where $N = 2^{\Theta(\sqrt{n})}$.
The Birthday Repetition Technique
The reduction utilizes "birthday repetition" to bridge the gap between the CSP and the game strategies. In this construction, Alice and Bob’s strategies correspond to assignments for small subsets of variables (of size approximately $\sqrt{n}$). Due to the logic of the birthday paradox, two such random subsets are highly likely to share at least one constraint.
If the underlying CSP is unsatisfiable, any signaling scheme will inevitably force Alice and Bob to "clash" on these shared constraints. This clash is engineered to diminish Alice's payoff, thereby linking the satisfiability of the CSP to the existence of a high-payoff signaling scheme.
Payoff Structure Design
To ensure the players adhere to the signals provided, the author employs a hierarchical payoff structure: $$U = \delta \tau^{A,Z} - \delta^2 \tau^{B,Z} + \delta^3 \tau^{A,B}$$ In this equation, $\tau$ represents consistency checks between Alice (A), Bob (B), and the "State of Nature" (Z). By using a hierarchy of small constants ($\delta \gg \delta^2 \gg \delta^3$), the game ensures that:
- Alice is incentivized to be consistent with the state of nature.
- Bob is incentivized to be consistent with the state of nature (to minimize Alice's gain).
- Alice and Bob are incentivized to be consistent with each other.
This hierarchy forces the signaling scheme to reflect a valid, consistent assignment to the original CSP for Alice to achieve an optimal payoff.
Key Results and Complexity Bounds
The paper provides two primary hardness results that define the computational landscape of symmetric signaling.
Additive Approximation and ETH
The most significant result is the additive hardness bound. The paper proves that, assuming ETH, finding an additive $\epsilon$-approximation for Symmetric Zero-Sum Signaling requires $n^{\Omega(\log n)}$ time. This result is particularly impactful because it matches the quasi-polynomial time algorithm previously proposed by Cheng et al. (2015). By providing a matching lower bound, the author effectively settles the complexity of the problem, ruling out the possibility of a Polynomial Time Approximation Scheme (PTAS).
Multiplicative Hardness
Beyond additive approximations, the paper addresses multiplicative factors. It proves that finding a multiplicative $(1-\epsilon)$-approximation is NP-hard. This suggests that even if we relax the requirement from absolute error to relative error, the problem remains intractable for polynomial-time algorithms.
Discussion and Limitations
This work clarifies that the difficulty of signaling is not merely a byproduct of complex game structures; even in the simplest zero-sum settings, the strategic revelation of information is fundamentally hard. By shifting the hardness assumption from the Planted Clique conjecture to ETH, the result rests on a more robust theoretical foundation.
However, some open questions remain. The multiplicative hardness result currently relies on a construction that includes both positive and negative payoffs. In many standard economic applications, payoffs are restricted to non-negative values. Whether multiplicative hardness persists in strictly non-negative settings is a subject for future research. Additionally, this study focuses on symmetric (public) signaling. The complexity of private signaling, where players receive different information, remains a distinct and fertile area for investigation.
Summary updated