  We study the optimization problem faced by a perfectly informed principal in
a Bayesian game, who reveals information to the players about the state of
nature to obtain a desirable equilibrium. This signaling problem is the natural
design question motivated by uncertainty in games and has attracted much recent
attention. We present new hardness results for signaling problems in (a)
Bayesian two-player zero-sum games, and (b) Bayesian network routing games.
  For Bayesian zero-sum games, when the principal seeks to maximize the
equilibrium utility of a player, we show that it is NP-hard to obtain an
additive FPTAS. Our hardness proof exploits duality and the equivalence of
separation and optimization in a novel way. Further, we rule out an additive
PTAS assuming planted clique hardness, which states that no polynomial time
algorithm can recover a planted clique from an Erd\H{o}s-R\'enyi random graph.
Complementing these, we obtain a PTAS for a structured class of zero-sum games
(where obtaining an FPTAS is still NP-hard) when the payoff matrices obey a
Lipschitz condition. Previous results ruled out an FPTAS assuming
planted-clique hardness, and a PTAS only for implicit games with
quasi-polynomial-size strategy sets.
  For Bayesian network routing games, wherein the principal seeks to minimize
the average latency of the Nash flow, we show that it is NP-hard to obtain a
(multiplicative) $(4/3 - \epsilon)$-approximation, even for linear latency
functions. This is the optimal inapproximability result for linear latencies,
since we show that full revelation achieves a $(4/3)$-approximation for linear
latencies.
