Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Introduction

In Bayesian games, players’ payoffs depend on the state of nature, which may be hidden from the players. Instead, players receive a signal regarding the state of nature which they use to form beliefs about their payoffs, and choose their strategies. Thus the strategic decisions and payoffs of the players depend crucially on the information available from the signal they receive. Since applications are often rife with uncertainty, understanding the effect of information available to players is a fundamental problem in game theory; see, e.g., [Bla51, Ake70, Hir71, MW82, LRS10, BBM13]. Whereas for a single player, it is known that more information leads to better payoffs [Bla51], with multiple players, outcomes are more complex and often counterintuitive with “more” (information) not necessarily translating to “better” (payoffs). The latter was first observed by Hirshleifer [Hir71]; recently, Dughmi [Dug14] gave an example where neither full-revelation nor no-revelation is optimal.

While classical work has focused on the role of information in influencing strategies, the computational problem of designing optimal information structures for Bayesian games, commonly called the signaling problem, has received much recent attention [BMS12, DIR14, EFG+12, GD13]. Here, a perfectly-informed principal seeks to reveal selective information to the players to optimize some function of the resulting equilibrium, such as the revenue, or payoff of a particular player. Two-player zero-sum games and network routing games are natural starting points for investigating the signaling problem due to their fundamental importance and appealing structure. They admit a canonical, tractable choice of equilibrium; this also decouples the concerns of optimal-signaling computation and equilibrium computation.

We study signaling in two widely studied classes of games: two-player zero-sum games, and network routing games. As in much of previous work, in our setting players share the same prior belief on the state of nature, and signaling schemes are symmetric: the principal reveals the same information to all players. Further, as previously, our results are for additive approximations in Bayesian zero-sum games, and for multiplicative approximations in Bayesian network routing games. Our main contribution is to derive hardness results for these classes of games that close the gap between what is achievable in polytime (or quasi-polytime) and what is intractable.

In Section 4, we consider Bayesian (two-player) zero-sum games, in which the principal seeks to maximize the value of the game — the equilibrium payoff of the row player.In zero-sum games, this also captures the problem of maximizing a weighted combination of players’ equilibrium payoffs. First, we settle the complexity of the signaling problem with respect to NP-hardness by showing that it is NP-hard to obtain an additive FPTAS (Theorem 4.1). Previous work by Dughmi [Dug14] ruled out an FPTAS assuming the planted clique hardness (see Conjecture 1). Thus, we replace an average-case hardness assumption with the much more conventional worst-case assumption of NP-hardness.

Next, we consider the hardness of obtaining a PTAS for the signaling problem. Since there is a quasi-polytime approximation scheme for signaling given by Cheng et al. [CCD+15], it is unlikely that a PTAS for signaling is NP-hard. We show that assuming planted-clique hardness, there does not exist a PTAS for the signaling problem (Theorem 4.4). Previously, the non-existence of a PTAS was shown (assuming planted-clique hardness) only for implicit zero-sum games with quasi-polynomial-size strategy sets [Dug14]. Complementing these hardness results, we devise a PTAS for a structured class of Bayesian zero-sum games (Theorem 4.14), when the payoff matrices obey a Lipschitz condition.

In Section 5, we consider the signaling problem in (nonatomic, selfish) Bayesian network routing games, wherein the principal seeks to reveal partial information to minimize the average latency of the equilibrium flow. We show that it is NP-hard to obtain any multiplicative approximation better than $\frac{4}{3}$, even with linear latency functions (Theorem 5.1). This yields an optimal inapproximability result for linear latencies, since we show that full revelation obtains the price of anarchy of the routing game as its approximation ratio (Theorem 5.4), which is $\frac{4}{3}$ for linear latency functions [RT02]. These are the first results for the complexity of signaling in Bayesian network routing games.

We also obtain hardness results for two related signaling problems in Bayesian zero-sum games (Section 6). Firstly, we rule out a PTAS for computing the best prior (the maximum prior problem), under the exponential time hypothesis (ETH). Previously, [CCD+15] studied a mixture-selection problem and showed that in the absence of a property called noise-stability, obtaining a PTAS was hard, assuming planted-clique hardness. Our result shows that in their setting a QPTAS is in fact the best possible approximation obtainable, assuming the ETH. Finally, if the principal’s value depends on the players’ strategies, and not just their payoffs, we show that obtaining a PTAS is NP-hard (Theorem 6.1).

Our results for Bayesian zero-sum games are obtained via two main ideas. Our NP-hardness result, the PTAS for a structured class of games, and the PTAS-hardness for the maximum prior problem, all follow by considering the signaling problem from a dual perspective. The signaling problem can be written as a mathematical program (P) with linear objective and constraints, but an infinite number of variables. Ignoring this issue, we can consider the dual problem (D). Motivated by the separation problem for the dual, we consider the dual signaling problem (Section 3). Our key insight is that the dual signaling problem is a rather useful tool for both deriving hardness results and devising approximation algorithms. This usefulness stems from the equivalence of separation and optimization [GLS93], which shows that an algorithm for the separation problem can be used to solve the optimization problem and vice versa. We exploit and build upon this equivalence. We prove that this equivalence holds despite the infinite-dimensionality of (P), and furthermore, is approximation preserving: an FPTAS for signaling yields an FPTAS for the dual signaling problem (Theorem 4.2), and a PTAS for the dual signaling problem yields a PTAS for signaling (Theorem 4.10).

This equivalence paves the way for our results. Whereas, typically, an (approximate) separation oracle is used to (approximately) solve the optimization problem, we exploit this equivalence in an unorthodox fashion by also leveraging the hardness of the dual signaling problem to prove hardness results for the signaling (i.e., primal optimization) problem. We show that it is NP-hard to obtain an FPTAS for the dual signaling problem, and thus obtain that it is NP-hard to obtain an FPTAS for the signaling problem. Notably, in contrast to the (weaker) planted-clique hardness result in [Dug14] for the signaling problem, we obtain our NP-hardness result with minimal effort, a fact that underscores the benefits of moving to the dual signaling problem.

On the positive side, we obtain a PTAS for the dual signaling problem for our structured class of Bayesian zero-sum games, which thus yields a PTAS for the signaling problem for this class. Interestingly, when cast in the mixture-selection framework of Cheng et al. [CCD+15], the signaling problem for our structured class does not satisfy the noise-stability property stated in [CCD+15]. In the absence of noise-stability, [CCD+15] showed planted-clique hardness for obtaining a PTAS. Our result bypasses this hardness result, and obtains a PTAS for a problem for which noise-stability does not hold. Finally, we show that a PTAS for the maximum-prior problem yields a PTAS for the dual signaling problem, and we rule out the latter via a simple, clean reduction from the best-Nash problem and the recent result of Braverman et al. [BKW15]. This result also strengthens the hardness result from [CCD+15] mentioned above, by showing that in the absence of noise-stability, a QPTAS is the best-possible approximation for the mixture selection problem, assuming the ETH.

Our second main idea, used to rule out a PTAS assuming planted-clique hardness, is a “direct” reduction that combines and strengthens techniques from [Dug14, FNS07]. We utilize the planted clique cover problem defined in [Dug14] — multiple cliques are now planted and one seeks to recover a constant fraction of them — and shown to be at least as hard as the planted clique problem. The idea is to set up a Bayesian zero-sum game where both the principal and the row player must randomize over $\Omega(\log n)$-size high-density node sets for the signaling scheme to achieve large value; recovering these large-density sets from a near-optimal signaling scheme allows one to solve the planted-clique cover (and hence, the planted clique) problem. The FPTAS-hardness reduction in [Dug14] creates a network security game (see Section 2) with payoffs of absolute value $\Omega(\log^{2}n)$ (or alternatively, a quasi-polynomial-size strategy set for the column player) to enforce the above property. Payoffs of magnitude $\Omega(\log n)$ seem necessary with this kind of approach, which therefore only yields an $O({1}/{\log n})$ gap that is insufficient to rule out a PTAS. We abandon the use of network security games and instead leverage a device from [FNS07] to ensure the above “large-spreading” property. This idea is also used to show planted-clique hardness for the best-Nash problem [HK11]; however we are constrained to work with zero-sum games, and therefore need to apply this idea carefully. A subtle, but crucial, technical issue is that we need to significantly tighten the planted-clique recovery result in [Dug14]. To recover a specific planted clique $S$ of size $k=\omega(\log^{2}n)$ (in the presence of other such planted cliques), [Dug14] requires a set $T$ with $|T|=\Theta(k),\ |S\cap T|=\Omega(k)$, whereas we only require that $|T|,|S\cap T|=\Omega(\log n)$, and this is crucial since we can only ensure that spreading takes place over $O(\log n)$-size sets.

Our hardness result for Bayesian routing games is a direct reduction from the problem of computing edge tolls that minimize the total (latency + toll)-cost of the resulting equilibrium flow, which is inapproximable within a factor of $\frac{4}{3}$.

Whereas understanding the role of information in influencing strategies is a classical problem in game theory, the computational problem of designing optimal information structures has been studied more recently. Much of this work has focused on signaling in auctions, where the goal is to maximize revenue [EFG+12, BMS12, GD13] or social welfare [DIR14]. Dughmi [Dug14] initiated the computational study of signaling in Bayesian zero-sum games, and obtained various hardness results under the planted-clique hardness assumption. This work left open the question of whether hardness results can be obtained under standard worst-case assumptions, such as P$\neq$NP, a question that we answer in the affirmative. On the positive side, Cheng et al. [CCD+15] showed that for Bayesian normal form games with a constant number of players and for general objectives of the principal, an $\epsilon$-approximate signaling scheme that maximizes the objective at an $\epsilon$-approximate Nash equilibrium can be computed in quasi-polynomial time. This work left open the question of whether a PTAS is possible for signaling in Bayesian zero-sum games. We preclude this under the planted-clique hardness assumption, and complementing this, design a PTAS for a structured class of games. As noted earlier, the latter result does not follow from [CCD+15] since the resulting signaling problem fails to have small noise stability.

The planted-clique problem was introduced by Jerrum [Jer92] and Kuc̆era [Kuč95], and despite extensive efforts (see, e.g., [AV14, FR10, DGGP11] and the references therein), no polytime algorithm is known for recovering cliques of size $k=o(\sqrt{n})$. There is a quasi-polytime algorithm known when $k\geq 2\log_{2}n$; on the other hand, various algorithmic strategies have been ruled out for this problem [Jer92, FK03, FGR+13]. The planted-clique problem has thus been used in various reductions (see, e.g., [HK11, JP00]), and is an example where an average-case hardness assumption has been used to derive hardness results.

Recently, Rubinstein [Rub15] has independently also obtained hardness results for signaling in zero-sum games. He shows that there is no additive PTAS assuming ETH, and obtaining a multiplicative PTAS is NP-hard. These results are orthogonal to ours, as there is no known reduction between ETH and planted-clique hardness. Further, NP-hardness of a multiplicative PTAS does not rule out an additive FPTAS.

In Bayesian network routing games, [VFH15] study the ability of signaling to reduce the average latency. They define the mediation ratio as the average latency at equilibrium for the best (private) signaling scheme, to the average latency for the social optimum, and give tight bounds on the mediation ratio with graphs consisting of parallel links. On these simple networks, navigation services (such as Waze or Google Maps) cannot do anything to improve the latency of the Nash flow. Our work, in contrast, studies the computational complexity of obtaining the best (public) signaling scheme in general graphs, and conclude that finding an \bigl{(}\frac{4}{3}-\epsilon\bigr{)}-approximation is NP-hard.

Preliminaries and notation

A Bayesian zero-sum game is specified by a tuple \bigl{(}\Theta,\{\mathcal{A}^{\theta}\}_{\theta\in\Theta},\lambda\bigr{)}, where $\Theta=\{1,\dots,M\}$ denotes the states of nature, and $\lambda$ is a prior distribution on the states of nature (thus $\lambda\in\Delta_{M}$). We assume the row and column player has $r,c$ pure strategies respectively. For each state of nature $\theta\in\Theta$, $\mathcal{A}^{\theta}\in^{r\times c}$ specifies the payoffs of the row player in a zero-sum game. Let $\mu\in\Delta_{M}$ be an arbitrary distribution over states of nature. Then $\mathcal{A}^{\mu}:=\sum_{\theta\in\Theta}\mu_{\theta}\mathcal{A}^{\theta}$ is the matrix of expected payoffs for the row player under distribution $\mu$.

A signaling scheme is a policy by which a principal reveals (partial) information about the state of nature. We focus on symmetric signaling schemes which reveals the same information to all the players. A signaling scheme specifies a set of signals $\Sigma$ and a map $\varphi:\Theta\mapsto\Delta_{|\Sigma|}$ from the states of nature $\Theta$ to distributions over the signals in $\Sigma$. Thus, $\varphi(\theta)_{\sigma}$ is the probability that the principal selects signal $\sigma$ when the state of nature is $\theta$. When the state $\theta$ is revealed, the principal computes a signal $\sigma\sim\varphi(\theta)$. Both players receive $\sigma$ and correspondingly update their belief on the state-distribution to $\mu^{\sigma}$, where for each state $\theta$,

The players then, based on their posterior belief, play the zero-sum game given by $\mathcal{A}^{\mu^{\sigma}}$.

Each signal $\sigma$ thus yields a posterior distribution $\mu^{\sigma}\in\Delta_{M}$, and these posterior distributions form a convex decomposition of the prior $\lambda=\sum_{\sigma}\mathop{Pr}(\sigma)\mu^{\sigma}$. As observed in [Dug14], specifying a signaling scheme $(\Sigma,\varphi)$ is in fact equivalent to specifying a distribution $\alpha$ over posterior distributions $\mu\in\Delta_{M}$ that yield a convex decomposition of the prior $\lambda$. Thus, a signaling scheme can also be described as $\alpha:=(\alpha_{\mu})_{\mu\in\Delta_{M}}$, where $\sum_{\mu\in\Delta_{M}}\alpha_{\mu}\mu=\lambda$. The signals $\Sigma$ in such a signaling scheme are described implicitly, and correspond to the posteriors $\mu$ for which $\alpha_{\mu}>0$. This will be our perspective on signaling schemes throughout. In Section 4.2, we will explicitly need to describe the signals, and then use $\mu^{\sigma}$ for the posterior corresponding to signal $\sigma$ and $\alpha_{\sigma}$ for $\mathop{Pr}(\sigma).$

The quality of a signaling scheme $\alpha$ for a Bayesian zero-sum game is then given by $\sum_{\mu\in\Delta_{M}}\alpha_{\mu}\operatorname{val}(\mu)$. The signaling problem in a Bayesian zero-sum game is to find a signaling scheme $\alpha$ that maximizes $\sum_{\mu\in\Delta_{M}}\alpha_{\mu}\operatorname{val}(\mu)$. Let $\operatorname{opt}(\mathcal{I})$ denote the value of the optimal signaling scheme for a Bayesian zero-sum game $\mathcal{I}$. We note that $\operatorname{opt}(\mathcal{I})$ is a concave function of the prior $\lambda$, since if $\lambda^{1}$ and $\lambda^{2}$ form a convex decomposition of $\lambda$, so do the optimal posteriors for $\lambda^{1}$ and $\lambda^{2}$. By Caratheodory’s theorem, $M+1$ posteriors (equivalently, signals) suffice to specify any convex decomposition of the prior. Together, this implies that an optimal signaling scheme can be specified by at most $M+1$ posteriors.

We say that an algorithm for the signaling problem is an (additive) $\varepsilon$-approximation algorithm if for every instance $\mathcal{I}$ the algorithm runs in polytime and returns a signaling scheme of value at least $\operatorname{opt}(\mathcal{I})-\varepsilon$. A polytime approximation scheme (PTAS) is an algorithm that runs in polytime and returns a solution of value at least $\operatorname{opt}(\mathcal{I})-\varepsilon$ for every instance $\mathcal{I}$ and constant $\varepsilon>0$; an FPTAS is a PTAS whose running time for an instance $\mathcal{I}$ and parameter $\varepsilon$ is \operatorname{poly}\bigl{(}\text{size of\mathcal{I}},\frac{1}{\varepsilon}\bigr{)}.

Some of our results utilize a class of zero-sum games that we call extended security games, wherein the payoff matrix for state $\theta$ is given by

Let ${B}$ and $D$ be matrices having columns $\{b^{1},\ldots,b^{M}\}$, and $\{d^{1},\ldots,d^{M}\}$ respectively. We obtain the following expressions for $\mathcal{A}^{\mu}$ and $\operatorname{val}(\mu)$ for $\mu\in\Delta_{M}$.

A special case of an extended security game (and the reason for this terminology) is the network security game defined by [Dug14]. Given an undirected graph $G=(V,E)$ with $n=|V|$ and a parameter $\rho\geq 0$, the states of nature correspond to the vertices of the graph. The row and column players are called attacker and defender respectively. The attacker and defender’s pure strategies correspond to nodes of $G$. Let $B$ be the adjacency matrix of $G$, and set $\overline{A}=D^{T}=-\rho I_{n\times n}$. Then, for a given state of nature $\theta\in V$, and pure strategies $a,d\in V$ of the attacker and defender, the payoff of the attacker is given by $e_{a}^{T}Be_{\theta}-\rho(e_{a}^{T}+e_{\theta}^{T})e_{d}$. The interpretation is that the attacker gets a payoff of 1 if he selects a vertex $a$ that is adjacent to $\theta$. This payoff is reduced by $\rho$ if the defender’s vertex $d$ lies in $\{\theta,a\}$, and by $2\rho$ if $d=\theta=a$.

Some of our hardness results are based on the hardness of the planted-clique and planted clique cover problems. The latter problem was introduced by Dughmi [Dug14].

Let $G\sim\mathcal{G}(n,p,k,r)$ be a random graph generated by: (1) including every edge independently with probability $p$; and (2) for $i=1,\ldots,r$, picking a set $S_{i}$ of $k$ vertices uniformly at random, adding all edges having both endpoints in $S_{i}$. We call the $S_{i}$s the planted cliques and $p$ the background density. We seek to recover a constant fraction of the planted cliques $S_{1},\ldots,S_{r}$, given $G\sim\mathcal{G}(n,p,k,r)$.

In the planted clique problem $\mathbf{PClique}(n,p,k)$, there is a single planted clique ($r=1$) and the goal is to recover this clique. The following hardness assumption for the planted-clique problem has been used in deriving various hardness results.

For some $k=k(n)$ satisfying $k=\omega(\log n)$ and $k=o(\sqrt{n})$, there is no probabilistic polytime algorithm that solves \mathbf{PClique}\bigl{(}n,\frac{1}{2},k\bigr{)} with constant success probability.

We utilize the ellipsoid method to translate hardness and approximation results for the dual of the signaling problem to signaling.

The ellipsoid method can find a point $x\in X$ or determine that $X=\emptyset$ in time $\operatorname{poly}(n,L)$.

The dual signaling problem

The signaling problem can be formulated as the following mathematical program,

Notice that any feasible $\alpha$ must also satisfy $\sum_{\mu\in\Delta_{M}}\alpha_{\mu}=1$; hence, $\alpha$ is indeed a distribution over $\Delta_{M}$, and a feasible solution to (P) yields a signaling scheme. Let $\operatorname{opt}(\lambda)$ denote the optimal value of (P), and note that this is a concave function of $\lambda$. Although (P) has a linear objective and linear constraints, it is not quite a linear program (LP) since there are an infinite number of variables. Ignoring this issue for now, we consider the following dual of (P).

The separation problem for (D) motivates the following dual signaling problem.

$\operatorname{val}(\mu)\geq w^{T}\mu+\varepsilon$ for some $\mu\in\Delta_{M}$; if so return $\mu\in\Delta_{M}$ s.t. $\operatorname{val}(\mu)\geq w^{T}\mu-\varepsilon$;

$\operatorname{val}(\mu)<w^{T}\mu-\varepsilon$ for all $\mu\in\Delta_{M}$.

Notice that the dual signaling problem is unconstrained: $\lambda$ plays no role.

Bayesian zero-sum games

We now prove the following results for signaling in Bayesian zero-sum games. We show that the signaling problem does not admit an FPTAS unless P=NP (Theorem 4.1) and does not admit a PTAS assuming the hardness of the planted-clique problem (Theorem 4.4). Complementing these hardness results, we present a PTAS for a structured class of extended security games (Theorem 4.14).

There is no FPTAS for the signaling problem, even for network security games, unless P=NP.

There is no FPTAS for the threshold signaling problem, even for network security games, unless P=NP.

The proof follows readily via a reduction from the balanced complete bipartite subgraph (BCBS) problem [GJ79], which illustrates the convenience of working with the dual signaling problem. In BCBS, given a bipartite graph $G=(V\cup W,E)$ and an integer $r\geq 0$, we want to determine if $G$ contains $K_{r,r}$ (i.e., an $r\times r$ biclique). Given a BCBS instance, set $\varepsilon=\frac{1}{2n^{8}}$, where $n=|V|+|W|$, and $\eta=1-(2n+1)\varepsilon$. We create a Bayesian network security game by letting $G$ be the graph in the network security game, and setting $\rho=2rn\varepsilon$. Recall that this means that states of nature correspond to nodes of $G$, so $\Theta=V\cup W$, and the payoff matrix for a distribution $\mu\in\Delta_{\Theta}$ is given by (2) where $B$ is the adjacency matrix of $G$ and $\overline{A}=D^{T}=-\rho I_{n\times n}$. This creates an instance of the threshold signaling problem with precision parameter $\varepsilon$; the prior $\lambda$ is irrelevant. We show that solving this instance would decide the BCBS-instance.

If $G$ has the required subgraph $V^{\prime}$, $W^{\prime}$, set $\mu_{v}=1/r$ for all $v\in V^{\prime}$ and $x_{v}=1/r$ for all $v\in W^{\prime}$. Then, by (2), we have $\operatorname{val}(\mu)\geq x^{T}B\mu-\rho\|\mu+x\|_{\infty}\geq 1-\rho/r=\eta+\varepsilon$. where we have $x^{T}B\mu=1$ since $V^{\prime}$, $W^{\prime}$ form a complete bipartite subgraph.

Suppose there exists $\mu\in\Delta_{M}$ so that $\operatorname{val}(\mu)\geq\eta-\varepsilon$. We show then that $G$ contains $K_{r,r}$. Let $x$ be the equilibrium strategy of the attacker, so $\operatorname{val}(\mu)=x^{T}B\mu-\rho\|\mu+x\|_{\infty}$. Let $V^{\prime}:=\{v\in V\cup W:\mu_{v}\geq 1/n^{3}\}$ and $W^{\prime}:=\{v\in V\cup W:x_{v}\geq 1/n^{3}\}$. Then $\sum_{v\in V^{\prime}}\mu_{v}=1-\sum_{v\not\in V^{\prime}}\mu_{v}>1-1/n^{2}$. Similarly $\sum_{v\in W^{\prime}}x_{v}>1-1/n^{2}$. Every vertex in $V^{\prime}$ must be adjacent to every vertex in $W^{\prime}$, otherwise $x^{T}B\mu\leq 1-1/n^{6}<\eta$. Thus, $V^{\prime}$ and $W^{\prime}$ must be in different partitions. Assume $V^{\prime}\subseteq V$ and $W^{\prime}\subseteq W$. For each vertex $v$, $\mu_{v}+x_{v}\leq\frac{(1+1/n)}{r}$, otherwise $\operatorname{val}(\mu)<1-(2n+2)\varepsilon$. Hence, $|V^{\prime}|\geq\frac{\sum_{v\in V^{\prime}}\mu_{v}}{(1+1/n)/r}>r\frac{1-1/n^{2}}{(1+1/n)}=r(1-1/n)$, and therefore $|V^{\prime}|\geq r$. Similarly $|W^{\prime}|\geq r$, and this yields the $r\times r$ biclique. ∎

This would be an optimal hardness result since a quasi-PTAS follows from [CCD+15]. Recently, Rubinstein [Rub15] obtains this hardness result via a direct reduction that builds upon ideas in [AIM14]. However, tightening part (ii) of Theorem 2.2 would give a much simpler proof. We leave this as an intriguing open question. Below, we rule out a PTAS for signaling under an orthogonal hardness assumption.

2 Planted-clique hardness of obtaining a PTAS

There is a constant $\varepsilon_{0}$ such that, assuming the planted-clique hardness conjecture (Conjecture 1), there is no $\varepsilon_{0}$-approximation for the signaling problem in Bayesian zero-sum games.

Our hardness result strengthens the one in [Dug14], which rules out an FPTAS assuming the planted-clique conjecture. The reduction therein creates a network security game from a graph G\sim\mathcal{G}\bigl{(}n,\frac{1}{2},k,r\bigr{)} (see Section 2). The idea is that if a signaling scheme achieves value close to 1, then it must place a large weight on posteriors and attacker mixed-strategies that randomize over a large set of nodes. Further, the posterior and attacker must essentially identify dense components of $G$, as otherwise the attacker’s value would be close to the background density $\frac{1}{2}$. As noted earlier, a limitation of this type of construction is that the parameter $\rho$ used in the network security game needs to be roughly $\Omega(\log n)$ to ensure that the posterior and the attacker’s mixed strategies are supported on an $\Omega(\log n)$-size set of nodes. This only yields an \Theta\bigl{(}\frac{1}{\operatorname{polylog}(n)}\bigr{)} gap, which is insufficient to rule out a PTAS. We overcome this obstacle by moving away from a network security game, and instead exploiting an idea of [FNS07] to eliminate all equilibria of $O(\log n)$-size support from the game. Theorem 4.4 follows immediately by combining Lemmas 4.5 and 4.6.

Let $\epsilon>0$, $k=k(n)$ satisfy $k=\omega(\log n)$ and $k=o(\sqrt{n})$, and $r=\Theta(n/k)$. Suppose there is a polytime algorithm that takes as input G\sim\mathcal{G}\bigl{(}n,\frac{1}{2},k,r\bigr{)} with planted cliques $\left\{S_{i}\right\}$, and outputs a family $\mathcal{T}\subseteq 2^{V}$ of clusters satisfying the following with constant probability, for any constant $c_{3}\geq 10^{3}:$

Then there is a polynomial-time algorithm for \mathbf{PClique}\bigl{(}n,\frac{1}{2},k\bigr{)} having constant success probability.

Let $k=k(n)$ satisfy $k=\omega(\log n)$ and $k=o(\sqrt{n})$, and $r=\frac{5n}{k}$. There is a polynomial-time randomized reduction that takes a graph G\sim\mathcal{G}\bigl{(}n,\frac{1}{2},k,r\bigr{)} as input and outputs a Bayesian zero-sum game such that the following hold with high probability.

(Completeness) There is a signaling scheme having value at least $0.99$.

(Soundness) Given a signaling scheme of value at least $0.97$, one can obtain in polytime a collection $\mathcal{T}$ of clusters satisfying condition (* ‣ 4.5) in Lemma 4.5.

Above, and throughout this section, when we say with high probability, we mean success probability $1-\frac{1}{\operatorname{poly}(n)}$. The Bayesian zero-sum game we construct always admits a signaling scheme of large value; however finding a near-optimal signaling scheme in polytime would refute the planted-clique conjecture. Lemma 4.5 (proved in Appendix A) is similar to a planted-clique recovery result proved in [Dug14]. While we utilize similar ideas, our result works under much weaker requirements. Our lemma allows clusters in $\mathcal{T}$ to have size $\Theta(\log n)$ — which is crucial for Lemma 4.6 — whereas in [Dug14], the clusters need to have size $\omega(\log^{2}n)$. In the rest of this section, we prove Lemma 4.6. We use the following parameters.

$a^{\theta}$ is the $\theta$-th column of the adjacency matrix $A_{G}$, so $a^{\theta}_{i}=1$ if $(i,\theta)\in E$ and is 0 otherwise.

$B$ is an $n\times N$ matrix, where each $B_{i,j}$ is set independently to $2-Z$ with probability $\frac{3}{4Z}$, and $2$ otherwise.

$d^{\theta}\in[-Z,Z]^{N}$, where each entry $d^{\theta}_{j}$ is set independently to $2-Z$ with probability $\frac{3}{4Z}$, and $2$ otherwise.

We use Row and Col to denote the row and column players respectively. Let $D$ be the $n\times N$ matrix having rows $(d^{\theta})^{T}$ for $\theta\in\Theta$.

To gain some intuition, observe that for a posterior $\mu$ and Row’s mixed strategy $x$, the row vector $x^{T}\mathcal{A}^{\mu}$ yielding Col’s payoffs is $[x^{T}A_{G}\mu\ \ x^{T}B\ \ \mu^{T}D]$. Thus, if Col plays action $1$ (with probability 1), the expected payoff of Row is equal to $x^{T}A_{G}\mu$. If $\mu$ and $x$ are uniform over $S,T\subseteq V$, the expected payoff is exactly

The remaining $2N$ pure strategies of Col are used to force the principal and Row to choose a posterior $\mu$ and mixed strategy $x$ respectively that are “well spread out”.

The average of the entries in any column of $B$ or $D$ is $\frac{5}{4}>\mathop{max}_{i}a^{\theta}_{i}$. Exploiting this, Claim 4.7(i) implies that if $x$ and $\mu$ both randomize uniformly over a large set of vertices, Col plays column 1. The completeness proof now follows from the oft-used idea of (roughly speaking) choosing posteriors and mixed strategies for Row that randomize uniformly over the planted cliques. Conversely, if $x$ or $\mu$ has support of size at most $c_{2}\log n$, then Claim 4.7(ii) implies that Col can play some column of $B$ or $D$ and make $\operatorname{val}(\mu)$ negative Thus, in order to obtain value close to 1, both $\mu$ and Row have to randomize over $\Omega(\log n)$-size sets of nodes. Using this, one can carefully extract a collection of node-sets satisfying condition (* ‣ 4.5) of Lemma 4.5. This yields the soundness proof.

The following properties about the above construction will be useful.

Let $R\subseteq V$. (i) If $|R|=\omega(\log n)$, with high probability, for every $j\in[N]$, $\frac{1}{|R|}{\sum_{i\in R}B_{i,j}}>1$ and $\frac{1}{|R|}\sum_{i\in R}D_{i,j}>1$. (ii) If $|R|\leq c_{2}\log n$, with high probability, $\exists j,k\in[N]$ such that $B_{i,j}=2-Z=D_{i,k}$ for all $i\in R$.

We first prove (i). The proof is a standard application of Chernoff bounds, and is also essentially shown in [HK11]. We prove the statement for $B$; the argument for $D$ is identical. Fix a column $j\in[N]$. We have \mathop{\mathbf{E}}\bigl{[}\frac{\sum_{i\in R}B_{i,j}}{|R|}\bigr{]}=\frac{5}{4}, where the expectation is over the random construction of $B$. Since $|R|=\omega(\log n)$, the size of $R$ is large enough so that Chernoff bounds imply that \mathop{\mathbf{Pr}}\bigl{[}\frac{\sum_{i\in R}B_{i,j}}{|R|}<\frac{9}{8}\bigr{]}\leq\frac{1}{2N\operatorname{poly}(n)}. The union bound over all $N$ columns yields the claim.

We now prove (ii). The proof again follows from Chernoff bounds, and is the key insight in [FNS07] (also utilized in [HK11]). Fix some $R\subseteq V$ with $|R|=c_{2}\log n$. We prove the statement for $B$; the proof for $D$ is identical. For a given $j\in[N]$, we have \mathop{\mathbf{Pr}}[\exists i\in R\text{ s.t. }B_{i,j}\neq 2-Z]=1-\bigl{(}\frac{3}{4Z}\bigr{)}^{|R|}. So

Taking the union bound over all $R\subseteq V$ with $|R|=c_{2}\log n$, we obtain

Let $\varepsilon>0$, and c\geq 24\cdot 2.1\cdot\mathop{max}\bigl{\{}1,\frac{1+\varepsilon}{\varepsilon^{2}}\bigr{\}}. For all $n\geq 2$, we have

For $c_{2}=10^{5}$ and $\epsilon=0.03$ With high probability, for all $S,T\subseteq V$ with $|S|,|T|\geq c_{2}\log n$, $\text{bi-density}_{G^{-}}(S,T)\leq\frac{1+\epsilon}{2}$.

We use a deterministic signaling scheme that groups together states of nature in the same planted clique. Let $S_{1},\ldots,S_{r}$ be the planted cliques in $G$ in some arbitrary order. Let $S_{i}^{\prime}=S_{i}\setminus\bigcup_{1\leq j<i}S_{j}$ for $i\in[r]$ be the set of vertices in $S_{i}$ that do not appear in earlier cliques. Define $A:=V\setminus\bigcup_{j}S_{j}$ as the remaining vertices. Finally, S_{0}^{\prime}=A\cup\bigl{\{}v\in S_{i}^{\prime}:|S_{i}^{\prime}|<\frac{k}{10^{4}}\bigr{\}}. Our signaling scheme is $(\Sigma,\alpha,\mu)$ where the set of signals is \Sigma=\{0\}\cup\bigl{\{}i\in[r]:|S^{\prime}_{i}|\geq\frac{k}{10^{4}}\bigr{\}}. For each signal $\sigma$, $\alpha_{\sigma}=\frac{|S_{\sigma}^{\prime}|}{n}$ and $\mu_{\sigma}$ is the uniform distribution over $S_{\sigma}^{\prime}$. Note that the signaling scheme is independent of $B$ and $D$.

For posterior $\mu^{\sigma}$, where $\sigma\neq 0$, consider the strategy $x^{\sigma}$ where Row plays the uniform distribution on $S_{\sigma}^{\prime}$. Claim 4.7(i) implies that Col’s best response to $x^{\sigma}$ is to play column 1. Therefore, $\operatorname{val}(\mu^{\sigma})\geq\text{bi-density}(S^{\prime}_{\sigma},S^{\prime}_{\sigma})=1-\frac{1}{|S_{\sigma}^{\prime}|}\geq 1-\frac{10^{4}}{k}$. With $r=\frac{5n}{k}$, we have $|A|\leq e^{0.1}\cdot\mathop{\mathbf{E}}[|A|]\leq e^{-4.9}n$ with high probability due to standard Chernoff bounds (since the events $\{v\in A\}_{v\in V}$ are negatively correlated). Therefore, for suitably large $n$, with high probability, $|S^{\prime}_{0}|\leq|A|+\frac{5n}{k}\cdot\frac{k}{10^{4}}\leq e^{-4.7}n$. So, with high probability, the signaling scheme has value at least \sum_{\sigma\in\Sigma\cap[r]}\alpha_{\sigma}\bigl{(}1-\frac{10^{4}}{k}\bigr{)}\geq(1-e^{-4.7})\bigl{(}1-\frac{10^{4}}{k}\bigr{)}\geq 0.99.

2.2 Soundness proof in Lemma 4.6

Inequality $(**)$ follows since for every $v\in\Theta$, we have $\sum_{\sigma\in\Sigma_{1}}\alpha_{\sigma}(\mu_{\sigma})_{v}$ is at most $\sum_{\sigma\in\Sigma}\alpha_{\sigma}(\mu_{\sigma})_{v}=\lambda_{v}=\frac{1}{n}$. Therefore $\frac{1}{r}\sum_{i=1}^{r}\left(\mathop{max}_{T\in\mathcal{T}}\frac{|T\cap S_{i}|}{|T|}\right)\geq\frac{1}{20}$. This implies that at least a $\frac{1}{39}$-fraction of $S_{1},\ldots,S_{r}$ satisfy $\mathop{max}_{T\in\mathcal{T}}\frac{|T\cap S_{i}|}{|T|}\geq\frac{1}{40}$. Since $|T|\geq c_{2}\log n$ for all $T\in\mathcal{T}$, $\mathcal{T}$ satisfies condition (* ‣ 4.5) in Lemma 4.5.

3 A PTAS for structured extended security games

We now devise a PTAS for a structured class of extended security games (Theorem 4.14). First, we reduce the signaling problem to the dual signaling problem using the ellipsoid method (Theorem 4.10). This reduction applies to all Bayesian zero-sum games. Next, we devise a PTAS for the dual signaling problem for our class of extended network security games (Theorem 4.14).

A polytime algorithm for the dual signaling problem with precision $\varepsilon$ gives a $5\varepsilon$-approximation algorithm for the signaling problem. In particular, a PTAS for the dual signaling problem yields a PTAS for the signaling problem.

Fix $\mu\in\Delta_{M}$. For any $\mu^{\prime}\in S_{\delta}(\mu)$, we have $|\operatorname{val}(\mu)-\operatorname{val}(\mu^{\prime})|\leq M\delta$. Hence, we can efficiently find $\hat{\mu}\in S_{\delta}(\mu)$ such that $w^{T}\hat{\mu}-\operatorname{val}(\hat{\mu})\leq w^{T}\mu-\operatorname{val}(\mu)+M\delta$.

The entries in $\mathcal{A}^{\mu}$ and $\mathcal{A}^{\mu^{\prime}}$ differ by at most $M\delta$. Hence for every mixed-strategy profile $(x,y)\in\Delta_{r}\times\Delta_{c}$, we have $|x^{T}(\mathcal{A}^{\mu}-\mathcal{A}^{\mu^{\prime}})y|\leq M\delta$, and therefore $|\operatorname{val}(\mu)-\operatorname{val}(\mu^{\prime})|\leq M\delta$.

We can efficiently find $\hat{\mu}\in S_{\delta}(\mu)$ that minimizes $w^{T}\mu^{\prime}$ over $\mu^{\prime}\in S_{\delta}(\mu)$ since this can be cast as an LP. Then, we have $w^{T}\hat{\mu}-\operatorname{val}(\hat{\mu})\leq w^{T}\mu-(\operatorname{val}(\mu)-M\delta)$. ∎

We work with the following finite-dimensional counterparts of (P) and (D) and argue that this approximation only yields a small error.

Since $\lambda\in\operatorname{conv}(S_{\delta}(\lambda))$, (Pδ) is feasible for any $\lambda\in\Delta_{M}$. Clearly, any solution to (Pδ) gives a solution to (P) of equal value. The converse is also approximately true.

Any feasible solution $\alpha$ to (P) of value $v$ gives a solution to (Pδ) of value at least $v-M\delta$. Hence, $\operatorname{opt}\text{\eqref{primd}}\geq\operatorname{opt}\text{\eqref{primal}}-M\delta$.

This is an easy consequence of Claim 4.11. For any $\mu\in S$, let $\tau^{(\mu)}\in\Delta_{S_{\delta}(\mu)}$ be some convex decomposition of $\mu$. Then

Thus, setting $\alpha^{\prime}_{\mu^{\prime}}:=\sum_{\mu\in S}\alpha_{\mu}\tau_{\mu^{\prime}}^{(\mu)}$ for all $\mu^{\prime}\in S_{\delta}$, we obtain that $\alpha^{\prime}$ is a feasible solution to (Pδ). To compare the objective values of $\alpha$ and $\alpha^{\prime}$, note that

Now the basic idea is to solve (Dδ) with the ellipsoid method using the algorithm $\mathcal{B}$ to obtain a separation oracle for (Dδ) with an additive error. In the course of solving (Dδ), we also obtain a polynomial-size LP consisting of the violated inequalities of (Dδ) returned by the separation oracle during the execution of the ellipsoid method whose optimal value is the same as $\operatorname{opt}\text{\eqref{duald}}$. Taking the dual of this compact LP yields an LP of the same form as (Pδ) but with $\alpha_{\mu}$ variables for only polynomially many points in $S_{\delta}$; solving this yields the desired approximate signaling scheme. The additive error in the separation oracle for (Dδ) complicates the arguments slightly.

So for a fixed $\nu$, in polynomial time, the ellipsoid method either certifies that $Q(\nu,-2\varepsilon)=\emptyset$ or returns a point in $Q(\nu,\varepsilon)$. We find the smallest $\nu$ (via binary search) such that the latter case happens; call this value $\nu^{*}$. Then,

The equality above follows since the dual of the minimization LP is above is (Pδ) with the objective function changed to \sum_{\mu\in S_{\delta}}\alpha_{\mu}\bigl{(}\operatorname{val}(\mu)-\varepsilon\bigr{)}=\sum_{\mu\in S_{\delta}}\alpha_{\mu}\operatorname{val}(\mu)-\varepsilon. For any $\epsilon>0$, running the ellipsoid method for $\nu=\nu^{*}-\epsilon$ yields a polynomial-size certificate for the emptiness of $Q(\nu^{*}-\epsilon,-2\varepsilon)$ consisting of the inequality $w^{T}\lambda\leq\nu^{*}-\epsilon$ and the polynomially many violated inequalities $w^{T}\mu-\operatorname{val}(\mu)\geq 2\varepsilon$ returned during the execution of the ellipsoid method. Let $T\subseteq S_{\delta}$ be the polynomial-size set of points for which we obtain these violated inequalities. By duality,

Thus, solving the polynomial-size LP inside the parentheses yields a signaling scheme of value at least $\operatorname{opt}\text{\eqref{primd}}-3\varepsilon-\epsilon$, so taking $\epsilon=\varepsilon$ and using Lemma 4.12, we obtain a signaling scheme of value at least $\operatorname{opt}\text{\eqref{primal}}-5\varepsilon$. ∎

Observe that an extended security game specified by matrices $\overline{A},B,D$ (see (1), (2)) is $\gamma$-Lipschitz if ${D}^{T}$ is $\gamma$-Lipschitz. We place no constraints on the matrices $\overline{A}$ and ${B}$. We design a simple PTAS for the dual signaling problem on $\gamma$-Lipschitz extended security games, for constant $\gamma$. By Theorem 4.10, this yields a PTAS for the signaling problem for $\gamma$-Lipschitz extended security games.

There is a PTAS for the dual signaling problem on $\gamma$-Lipschitz extended security games. This yields a PTAS for the signaling problem on $\gamma$-Lipschitz extended-security games.

Given Theorem 4.10, we only need to prove the first statement. Let $(\mathcal{I},w,\varepsilon)$ be the input to the dual signaling problem where $\mathcal{I}$ is a $\gamma$-Lipschitz extended security game. Set $\varepsilon^{\prime}=\varepsilon/\gamma$. Our algorithm simply finds \hat{\mu}=\operatorname{argmax}_{\mu\in S_{\varepsilon^{\prime}}}\bigl{(}\operatorname{val}(\mu)-w^{T}\mu\bigr{)} by exhaustive search. If $\operatorname{val}(\hat{\mu})-w^{T}\hat{\mu}\geq 0$, we state that we are in case (i) and return $\hat{\mu}$; else we state that we are in case (ii).

First, note that the algorithm runs in time \operatorname{poly}\bigl{(}\text{size of\mathcal{I}},M^{\frac{\gamma}{\varepsilon}}\bigr{)}, since |S_{\varepsilon^{\prime}}|\leq{M\choose{1/\varepsilon^{\prime}}}\bigl{(}\frac{1}{\varepsilon^{\prime}}\bigr{)}^{1/\varepsilon^{\prime}} (there are ${M\choose{1/\varepsilon^{\prime}}}$ choices for the support, and at most $\frac{1}{\varepsilon^{\prime}}$ choices for each of the at most $\frac{1}{\varepsilon^{\prime}}$ coordinates in the support).

Let $\mu^{*}$ maximize $\operatorname{val}(\mu)-w^{T}\mu$, and $x^{*}$ be the equilibrium strategy for the row player in the resulting zero-sum game. We claim that $\operatorname{val}(\mu^{*})-w^{T}\mu^{*}\leq\operatorname{val}(\hat{\mu})-w^{T}\hat{\mu}+\varepsilon$, which shows that we correctly solve the dual signaling problem: if case (i) applies, then $\operatorname{val}(\hat{\mu})-w^{T}\hat{\mu}\geq 0$; if case (ii) applies, then clearly, $\operatorname{val}(\hat{\mu})-w^{T}\hat{\mu}<-\varepsilon$.

We now prove the claim. Since $\mu^{*}\in\operatorname{conv}(S_{\varepsilon^{\prime}}(\mu^{*}))$, there exists some $\mu^{\prime}\in S_{\varepsilon^{\prime}}(\mu^{*})$ such that $x^{*T}{B}\mu^{*}-w^{T}\mu^{*}\leq x^{*T}{B}\mu^{\prime}-w^{T}\mu^{\prime}$. Further, since ${D}^{T}$ is $\gamma$-Lipschitz, for all $j\in[c]$, \bigl{(}x^{*T}\overline{A}+\mu^{*T}{D}^{T}\bigr{)}_{j}\leq\bigl{(}x^{*T}\overline{A}+\mu^{\prime T}{D}^{T}\bigr{)}_{j}+\gamma\varepsilon^{\prime}. Combining these inequalities yields that $\operatorname{val}(\mu^{\prime})-w^{T}\mu^{\prime}\geq\operatorname{val}(\mu^{*})-w^{T}\mu^{*}-\varepsilon$. ∎

Bayesian network routing games

We now consider the signaling problem in Bayesian network routing games and prove an optimal inapproximability result for linear latency functions: It is NP-hard to obtain a multiplicative approximation better than $4/3$ (Theorem 5.1), and this approximation is achieved for linear latency functions by a simple signaling scheme that simply reveals the state of nature (Theorem 5.4).

In a Bayesian network routing game, the edge latency functions $\{l_{e}^{\theta}\}_{e\in E}$ may depend on the state of nature $\theta\in\Theta$ (and, as before, we have a prior $\lambda\in\Delta_{\Theta}$). The principal seeks to minimize the latency of the Nash flow. Given $\mu\in\Delta_{\Theta}$, the expected latency function on each edge $e$ is $l_{e}^{\mu}(x_{e}):=\sum_{\theta\in\Theta}\mu_{\theta}l_{e}^{\theta}(x_{e})$. Define $\operatorname{val}(\mu):=C(l^{\mu};f^{\mu})$, where $f^{\mu}$ is the Nash flow for latency functions $\{l^{\mu}_{e}\}$. The signaling problem in a Bayesian routing game is to determine $(\alpha_{\mu})_{\mu\in\Delta_{M}}\geq 0$ of finite support specifying a convex decomposition of $\lambda$ (i.e., $\sum_{\mu\in\Delta_{M}}\alpha_{\mu}\mu=\lambda$) that minimizes the expected latency of the Nash flow, $\sum_{\mu\in\Delta_{M}}\alpha_{\mu}\operatorname{val}(\mu)$.

For any $\epsilon>0$, obtaining a $(4/3-\epsilon)$-approximation for the signaling problem in Bayesian routing games is NP-hard, even in single-commodity games with linear latency functions.

There are optimal tolls where the toll on every edge is or $\infty$. If P $\neq$ NP, there is no $\left(\frac{4}{3}-\epsilon\right)$-approximation algorithm for the problem of computing optimal tolls in networks with linear latency functions, for any $\epsilon>0$.

Let \Gamma=\bigl{(}G=(V,E),l,s,t,d\bigr{)} be an instance of a routing game with linear latencies. Let $m=|E|\geq 2$. By scaling latency functions suitably, we may assume that $d=1$. Then, for any latency functions $l^{\prime}$, the latency of the Nash flow for $l^{\prime}$ equals the common delay of all flow-carrying $s$-$t$ paths. Let $L=C(l;f^{\mathit{NE}})$ be the latency of the Nash flow for $l$. Let $\tau^{*}$ be optimal $\{0,\infty\}$-tolls, L^{*}=C\bigl{(}l+\tau^{*},f^{\mathit{NE}}(\tau^{*})\bigr{)} be the optimal cost, and $K^{*}:=\{e\in E:\tau_{e}^{*}=\infty\}$. We can view $\tau^{*}$ as simulating the removal of edges in $K^{*}$.

We create the following Bayesian routing game. Let \bigl{(}G_{1}=(V_{1},E_{1}),s_{1},t_{1}\bigr{)} and \bigl{(}G_{2}=(V_{2},E_{2}),s_{2},t_{2}\bigr{)} be two copies of $(G,l,s,t)$. Add vertices $s$, $t$, and edges $(s,s_{1})$, $(s,s_{2})$ and $(t_{1},t)$, $(t_{2},t)$. Call the graph thus created $H$. For $e\in E_{1}\cup E_{2}$ with corresponding edge $e^{\prime}\in E$, set the latency function in the new graph $h_{e}(x)=l_{e^{\prime}}(x)$, and set $h_{e}(x)=0$ for $e=(s,s_{1}),(s,s_{2}),(t_{1},t),(t_{2},t)$. The states of nature correspond to edges in $H$. We set $\lambda_{\theta}=1/m^{2}$ for all $\theta\in E_{1}\cup E_{2}$; the remaining $1-\frac{2}{m}$ mass is spread equally on $(s,s_{1})$, $(s,s_{2})$. We set $h_{e}^{\theta}(x)=h_{e}(x)+8m^{3}L$ if $\theta=e$ and $h_{e}(x)$ otherwise. Our Bayesian routing game is \bigl{(}(G,\{h^{\theta}_{e}\}_{\theta,e},s,t,d),\lambda\bigr{)}.

The idea here is that state $\theta$ encodes the removal of edge $\theta$: specifically, if \mu_{\theta}=\Omega\bigl{(}\frac{1}{m}\bigr{)} for a posterior $\mu$, then $h^{\mu}$ simulates removing edge $\theta$ due to the large constant term $8m^{3}L$. Let $K_{i}$ be the edge-set corresponding to $K^{*}$ in $G_{i}$, for $i=1,2$. The prior $\lambda$ is set up so that: (a) it admits a convex decomposition into posteriors $\mu^{1},\mu^{2}$, where $h^{\mu^{i}}$ simulates that $G_{i}\setminus K_{i}$ is connected to $s$ and $G_{3-i}$ is disconnected from $s$; and (b) any convex-decomposition of $\lambda$ must be such that a large weight is placed on posteriors $\mu$, where $h^{\mu}$ simulates that only one of $G_{i}$ is connected to $s$, so that $\{\mu_{e}8m^{3}L\}_{e\in E_{i}}$ yields tolls $\tau$ for edges in $E$ such that C\bigl{(}l+\tau,f^{\mathit{NE}}(\tau)\bigr{)}\leq\operatorname{val}(\mu). Lemma 5.3 makes the statements in (a) and (b) precise, and Theorem 5.1 follows immediately from Lemma 5.3 and Theorem 5.2.

There is a signaling scheme for the above Bayesian routing game with latency $L^{*}$. Further, given a signaling scheme $\alpha$ for the above Bayesian routing game with expected latency $L^{\prime}$, one can obtain tolls $\tau$ such that the routing game $(G,l+\tau,s,t,d)$ has Nash latency at most $\frac{L^{\prime}}{1-4/m}$.

We first show the existence of a signaling scheme with latency $L^{*}$. Define posterior $\mu^{1}\in\Delta_{E_{H}}$ as: $\mu^{1}_{\theta}=2/m^{2}$ for all $\theta\in K_{1}\cup E_{2}\setminus K_{2}$, $\mu^{1}_{(s,s_{2})}=(1-2/m)$. Define $\mu^{2}$ symmetrically as: $\mu^{2}_{\theta}=2/m^{2}$ for all $\theta\in K_{2}\cup E_{1}\setminus K_{1}$, $\mu^{2}_{(s,s_{1})}=(1-2/m)$. Then $\lambda=(\mu^{1}+\mu^{2})/2$, and this is our signaling scheme. We will show that $\operatorname{val}(\mu^{1})=\operatorname{val}(\mu^{2})\leq L^{*}$, proving the lemma.

Consider distribution $\mu^{1}$; the argument for $\mu^{2}$ is symmetrical. The idea is that an edge $e$ with $\mu_{e}^{1}>0$ has $h^{\mu^{1}}_{e}(x)\geq 8mL$, which effectively deletes $e$ from $H$; other edges have $h^{\mu_{1}}_{e}(x)=h_{e}(x)$. So $\mu^{1}$ simulates retaining edges in $G_{1}\setminus K_{1}$. Let $f=f^{\mathit{NE}}(\tau^{*})$ be the Nash flow in the routing game $(G,l+\tau^{*},s,t,d)$. So $C(l+\tau^{*};f)=L^{*}$. Recall that $d=1$, so every $s$-$t$ path in $G$ has latency at least $L^{*}$. Then the flow that sends $d$ on edges $(s,s_{1})$ and $(t_{1},t)$ and $f$ on edges of $G_{1}$, is feasible. On every edge $e\in E(H)$ with positive flow, $\mu_{e}^{1}=0$, so the latency of this flow under $h^{\mu^{1}}$ is $L^{*}$. Further, this is a Nash flow for $h^{\mu^{1}}$: any $s$-$t$ path $P$ either contains an edge with $\mu_{e}^{1}>0$, and if not, contains an $s_{1}$-$t_{1}$ path; in the latter case, there is a corresponding $s$-$t$ path $Q$ in $G$, and the latency of $P$ under $h^{\mu^{1}}$ equals $(l+\tau^{*})_{Q}(f)$, which is at least $L^{*}$ since $f$ is the Nash flow for $l+\tau^{*}$.

Next, we show how to obtain the required tolls from the signaling scheme $\alpha$ (with expected latency $L^{\prime}$). Assume $L^{\prime}\leq L$, otherwise $\tau=0$ suffices. At least $(1-4/m)$ of the probability mass of $\alpha$ must be on posteriors $\mu$ with $\mu_{(s,s_{1})}+\mu_{(s,s_{2})}\geq 1/m$. There must exist such a posterior $\mu^{\prime}$ with $\operatorname{val}(\mu^{\prime})\leq\frac{L^{\prime}}{1-4/m}$. Assume $\mu^{\prime}_{(s,s_{1})}\geq\frac{1}{2m}$; the other case is symmetric. Let $f=f^{\mu^{\prime}}$ be the Nash flow for latency functions $h^{\mu^{\prime}}$. (Again, since $d=1$, every $s$-$t$ path $P$ in $H$ with $f_{e}>0$ for all $e\in P$ satisfies $h^{\mu^{\prime}}_{P}(f)=\operatorname{val}(\mu^{\prime})$.)

Since $h^{\mu^{\prime}}_{(s,s_{1})}\geq 4m^{2}L>\operatorname{val}(\mu^{\prime})$, we must have $f_{(s,s_{1})}=0$, so $f$ is supported on $G_{2}$. Abusing notation, for $e\in E_{2}$, we also use $e$ to denote the corresponding edge in $E$. For every $e\in E_{2}$, we have $h^{\mu^{\prime}}_{e}(x)=l_{e}(x)+\mu_{e}^{\prime}8m^{3}L$. Thus, defining $\tau_{e}=\mu_{e}^{\prime}8m^{3}L$ for all $e\in E$, we obtain that $f$ restricted to $E_{2}$ is a Nash flow for $(G,l+\tau,s,t,d)$, and its latency is at most $\operatorname{val}(\mu^{\prime})$. This is easy to see, since every $s$-$t$ path $P$ in $G$ corresponds to an $s_{2}$-$t_{2}$ path $Q$ in $H$, and $(l+\tau)_{P}(f)=h^{\mu^{\prime}}_{Q}(f)$. ∎

The full-revelation signaling scheme, i.e., revealing the state of nature, has the price of anarchy for the underlying latency functions as its approximation ratio. In particular, for linear latencies, it achieves a $\frac{4}{3}$-approximation.

Recall that the price of anarchy (PoA) for a class of latency functions is the maximum ratio, over all instances involving these latency functions, of the latencies of the Nash flow and optimal flow. For linear latency functions, the PoA is $\frac{4}{3}$ [RT02].

Intuitively, the result follows because full-revelation is the best signaling scheme if one seeks to minimize the expected latency of the optimal flow, and the multiplicative error that results from this change in objective (from the latency of the Nash flow to that of the optimal flow) cannot exceed the price of anarchy.

Consider any signaling scheme $\alpha$. Its cost is

Extensions: hardness results for related problems

We study the closely-related problem of finding $\mu\in\Delta_{M}$ that maximizes $\operatorname{opt}(\mu)$. The proof of Theorem 4.2 in fact shows that a PTAS for the maximum-prior problem yields a PTAS for threshold signaling. Theorem 6.1 uses this implication to rule out a PTAS for the maximum prior problem under the exponential time hypothesis (ETH) by giving a simple, clean reduction from the best-Nash problem in general-sum two-player games, for which a PTAS is ruled out by [BKW15]. Theorem 6.1 establishes the optimal hardness result for the maximum prior problem, since a quasi-PTAS for the maximum prior problem was recently presented in [CCD+15].

Theorem 6.1 also implies that the general maximum prior problem studied in [CCD+15] does not have a PTAS under the ETH, when the objective function is $O(1)$-Lipschitz but not $O(1)$-noise-stable. (For this case, [CCD+15] ruled out a PTAS assuming hardness of planted clique.) This is because the objective function (minimax value) for signaling in zero-sum games is $O(1)$-Lipschitz.

Recall that, as noted earlier, the proof of Theorem 4.2 shows that, for any $\varepsilon$, a polytime $\varepsilon$-approximation for the maximum prior problem yields a polytime algorithm for the threshold signaling problem with precision parameter $2\varepsilon$. Thus, it suffices to show that, assuming ETH, there is some constant $\epsilon_{0}$ such that solving the threshold signaling problem with precision parameter $\epsilon_{0}$, even for extended security games, requires quasipolynomial running time. To show this, we reduce from the problem of finding an $\epsilon$-Nash equilibrium in a general two-player game with $\epsilon$-approximate social welfare, and utilize the following hardness result for this problem.

Let $(\mathcal{R},\mathcal{C})$ be a bimatrix game, where $\mathcal{R},\mathcal{C}\in^{m\times n}$ are the payoffs for the row- and column- players respectively. To avoid confusion with the extended security game, we refer to the row- and column- players in the bimatrix game as the $\mathcal{R}$- and $\mathcal{C}$- players. A pair of mixed strategies $(x,y)$ for the $\mathcal{R}$- and $\mathcal{C}$- players respectively is an $\varepsilon$-approximate equilibrium if:

The social welfare of $(x,y)$ is defined as $x^{T}(\mathcal{R}+\mathcal{C})y$. Let $\mathit{OPT}$ be the maximum social welfare of a (mixed) Nash equilibrium of $(\mathcal{R},\mathcal{C})$. Note that $-2\leq\mathit{OPT}\leq 2$.

We construct an extended security game where the states of nature correspond to the pure strategies of the $\mathcal{C}$-player (in the bimatrix game), and the row-player’s pure strategies (in the extended security game) correspond to the $\mathcal{R}$-player’s strategies (in the bimatrix game). We will set things up so that the expected payoff in the extended security game to the row player under a posterior distribution $\mu$ and when he plays a mixed strategy $x$ is a linear combination of the LHS of (4) (viewing $(x,\mu)$ as a mixed-strategy profile for the bimatrix game $(\mathcal{R},\mathcal{C})$) and the social welfare of $(x,\mu)$ in the bimatrix game $(\mathcal{R},\mathcal{C})$. Let $\epsilon>0$ be a parameter. The payoffs in the extended security game will have absolute value at most $1+O(1/\epsilon)$. We will show that solving the threshold signaling problem for the resulting extended security game with threshold $\eta=\eta^{\prime}-\epsilon$, and precision parameter $\epsilon$ yields a $6\epsilon$-approximate Nash equilibrium of $(\mathcal{R},\mathcal{C})$ with social welfare at least $\eta^{\prime}-2\epsilon$, whenever there is a Nash equilibrium of $(\mathcal{R},\mathcal{C})$ with social welfare at least $\eta^{\prime}$ or we state that we are in case (i) of the threshold signaling problem. So via binary search, we can obtain a $6\epsilon$-approximate Nash equilibrium of $(\mathcal{R},\mathcal{C})$ with social welfare at least $\mathit{OPT}-3\epsilon$. Thus, setting $\epsilon_{0}=\Theta(\epsilon^{*^{2}})$,The $\Theta(e^{*^{2}})$ is because we need additive error $\Theta(\epsilon^{*})$ when payoffs are bounded in absolute value by $1+O(1/\epsilon^{*})$; when we scale payoffs so that they lie in $$, this translates to an$\Theta(\epsilon^{*^{2}})$-approximation. where$\epsilon^{*}$is as given by Theorem 6.2, we obtain that, assuming ETH, the threshold signaling problem with precision parameter$\epsilon_{0}$ requires quasipolynomial time, completing the proof.