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

Aviad Rubinstein

This paper, titled "Honest signaling in zero-sum games is hard; and lying is even harder!" by Aviad Rubinstein, explores the computational limits of "signaling"—the strategic revelation of information—within the framework of game theory.

TL;DR

The paper proves that finding an optimal way to reveal information in a zero-sum game is computationally difficult. Assuming the Exponential Time Hypothesis (ETH), even an approximately optimal "honest" signaling scheme requires quasi-polynomial time, while a "dishonest" scheme (where the signaler can lie about their strategy) is NP-hard to optimize even slightly.

What Problem Does This Paper Address?

In many economic scenarios, one party (the signaler) has access to private information that others do not. By choosing how much of that information to reveal, the signaler can influence the behavior of other players. This is known as signaling or Bayesian persuasion.

The authors focus on Zero-Sum Signaling. Imagine a game between Alice and Bob where Alice’s gain is Bob’s loss. A third party, Sam (the signaler), knows the exact payoff matrix being played, but Alice and Bob only know the general distribution. Sam wants to send a public signal to both players to help Alice maximize her expected payoff.

While previous work suggested this problem was hard based on specific average-case assumptions (like the "Planted Clique" problem), this paper seeks to establish hardness based on more standard, worst-case complexity assumptions (like ETH) and to explore what happens if Sam is allowed to be "dishonest."

Methods

The paper utilizes a sophisticated reduction technique called "birthday repetition." 1. Reduction from 2-CSP: The author reduces a 2-ary Constraint Satisfaction Problem (2-CSP)—a known hard problem—to a distribution of zero-sum games. 2. Birthday Paradox Utility: By mapping Alice and Bob’s strategies to assignments of variables in the CSP, the "birthday paradox" ensures that if they choose random subsets of variables, they will likely share a constraint. If the CSP is unsatisfiable, Alice’s payoff inevitably suffers. 3. The Lying Model: The author introduces a novel model for "dishonest signaling." In this setup, Sam publicly commits to one signaling rule ($\phi_{alleged}$) but secretly uses another ($\phi_{real}$). Alice and Bob update their beliefs based on the alleged rule, but the actual payoffs are determined by the real signals sent.

Datasets

As a theoretical computer science paper focused on computational complexity proofs, no empirical datasets were used. The "instances" used for evaluation are mathematical constructions derived from 3SAT and 2-CSP problems.

Key Insights and Ideas

  • The Quasi-Polynomial "Sweet Spot": The paper shows that finding an $\epsilon$-optimal honest signaling scheme requires $n^{\Omega(\log n)}$ time. This is a "tight" result, meaning it matches the best-known existing algorithms, effectively closing a gap in the field.
  • ETH vs. Planted Clique: By basing the hardness on the Exponential Time Hypothesis (ETH) rather than the Planted Clique assumption, the results become more robust and widely accepted within the complexity community.
  • The Power of Deception: The most striking insight is the "Lying is even harder" result. In the dishonest model, Sam can exploit Bob’s trust to a massive degree. Because Bob acts on a "fake" posterior distribution, Sam can engineer scenarios where Alice wins big, making the optimization problem for Sam extremely sensitive and NP-hard to approximate even within a tiny margin ($1 - 2^{-n}$).

Key Results

  • Theorem 1.2 (Main Result): Assuming ETH, finding an additive $\epsilon$-approximation for Zero-Sum Signaling requires quasi-polynomial time ($n^{\Omega(\log n)}$).
  • Theorem 1.3: Finding a multiplicative $(1-\epsilon)$-approximation for the same problem is NP-hard.
  • Theorem 1.5: In the "Zero-Sum Lying" model, finding a signaling scheme that is even remotely close to optimal (within an additive $1 - 2^{-n}$) is NP-hard.

Limitations and Future Work

  • Gullibility Assumption: The dishonest signaling model assumes that Alice and Bob are "perfectly gullible"—they never catch on that Sam is lying, even if the game is repeated. The author suggests that future research could look at "distribution testing," where players might eventually stop believing signals if they don't match historical outcomes.
  • Signaler Incentives: The model assumes Sam wants Alice to win (perhaps he owns her stock). The paper notes that exploring Sam’s actual incentives and "punishing mechanisms" for dishonest signalers would be a valuable next step.
  • General-Sum Games: The results are specific to zero-sum games. Extending these hardness results to general-sum games (where players' interests might partially align) remains an open area for exploration.

Summary updated

Abstract

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.
BibTeX
@inproceedings{rubinstein2017honest,
  author = {Aviad Rubinstein},
  title = {{Honest signaling in zero-sum games is hard, and lying is even harder}},
  booktitle = {ICALP},
  year = {2017},
  url = {https://openreview.net/forum?id=mVC5boE1H7r},
}
Figure