Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game ^†

Abstract

Consider a communication network represented by a directed graph $G=(V,E)$ of n nodes and m edges. Assume that edges in E are partitioned into two sets: a set C of edges with a fixed non-negative real cost, and a set P of edges whose costs are instead priced by a leader. This is done with the final intent of maximizing a revenue that will be returned for their use by a follower, whose goal in turn is to select for his communication purposes a subnetwork of Gminimizing a given objective function of the edge costs. In this paper, we study the natural setting in which the follower computes a single-source shortest paths tree of G, and then returns to the leader a payment equal to the sum of the selected priceable edges. Thus, the problem can be modeled as a one-round two-player Stackelberg Network Pricing Game, but with the novelty that the objective functions of the two players are asymmetric, in that the revenue returned to the leader for any of her selected edges is not equal to the cost of such an edge in the follower’s solution. As is shown, for any $ϵ>0$ and unless $\mathsf{P}=\mathsf{NP}$, the leader’s problem of finding an optimal pricing is not approximable within $n^{1/2-ϵ}$, while, if G is unweighted and the leader can only decide which of her edges enter in the solution, then the problem is not approximable within $n^{1/3-ϵ}$. On the positive side, we devise a strongly polynomial-time $O\left(n\right)$-approximation algorithm, which favorably compares against the classic approach based on a single-price algorithm. Finally, motivated by practical applications, we consider the special cases in which edges in C are unweighted and happen to form two popular network topologies, namely stars and chains, and we provide a comprehensive characterization of their computational tractability.

1. Introduction

Leader–follower games were introduced by von Stackelberg in 1934 [1], with the aim of modeling heterogeneous markets, namely markets in which one or more players are in a leadership position, and can in practice manipulate the market to their own advantage, by directly influencing the choices of the remaining subjects. In the basic formulation, the game is played by only two players: the leader who moves first and the follower who observes the leader’s move and then makes his (throughout the paper, we adopt the convention of referring to the leader and the follower with female and male pronouns, respectively) own move, after which the game is over. The strategic aspect of the game consists of the fact that the follower computes a solution by optimizing an objective (public) function, while the leader has her own objective function, which is, by the way, computed over the solution selected by the follower. In this way, to optimize her revenue, the leader has to entail in her move the optimal response which will be given by the follower.

Leader–follower games have received considerable attention from the computer science community, mainly because the Internet is a perfect paradigm of heterogenous market. In fact, the Internet is a vast, pervasive electronic market mainly composed of millions of independent end-users, whose actions are by the way influenced by the owners of physical/logical portions of the network, for instance service providers. Under this perspective, it turns out to be particularly intriguing the problem of analyzing the antagonism emerging between leaders and followers whenever a communication subnetwork must be allocated.

1.1. Stackelberg Network Pricing Games

Network games can be easily regarded as Stackelberg games, as soon as a situation arises in which a subset of dominant players controls a higher-level decision phase in which part of the game instance is set, for example by routing a substantial amount of a network flow [2] or by deciding the cost of a subset of network arcs. In particular, games of this latter type, which are of interest for this paper, are widely known as Stackelberg Network Pricing Games (SNPGs).

A SNPG can be formalized as follows: We are given either a directed or an undirected graph $G=(V,E=C\cup P,C\cap P=\varnothing )$, with an edge cost function $c:e\in C\to {\mathbb{R}}_{\ge 0}$, while edges in P need to be priced by the leader. In the following, we assume that $n=\left|V\right|$ and $m=\left|C\right|+\left|P\right|$. As usual, we also permit the existence of parallel pairs of weighted and priceable edges. Then, the leader moves first and chooses a pricing function $p:e\in P\to {\mathbb{R}}_{\ge 0}$ for her edges, in an attempt to maximize her objective function $f_1(p,H\left(p\right))$, where $H\left(p\right)$ denotes the decision which will be taken by the follower, consisting in the choice of a subgraph of G. This notation stresses the fact that the leader’s problem is implicit in the follower’s decision. Once observed the leader’s choice, the follower reacts by selecting a subgraph $H\left(p\right)=(V^{\prime },E^{\prime })$ of G which minimizes his objective function $f_2(p,H)$, parameterized in p. Note that the leader’s strategy affects both the follower’s objective function and the set of feasible decisions, while the follower’s choice only affects the leader’s objective function. Throughout the paper, we naturally assume that $f_1$ is price-additive, i.e., $f_1(p,H\left(p\right))={\sum }_{e\in P\cap E^{\prime }}p\left(e\right)$. This means the leader decides edge prices having in mind that her revenue equals the overall price of her selected edges.

The most immediate SNPG is that in which we are given two specified nodes in G, say $s,t$, and the follower wants to travel along a shortest path in G between s and t (see [3] for a survey). This problem has been shown to be APX-hard [4], as well as not approximable within a factor of $2-o\left(1\right)$ unless P = NP [5], while an $O(log|P\left|\right)$-approximation is provided in [6]. For the case of multiple followers (each with a specific source-destination pair), Labbé et al. [7] derived a bilevel LP formulation of the problem (and proved NP-hardness), while Grigoriev et al. [8] presented algorithms for a restricted shortest path problem on parallel edges. Another basic SNPG is that in which the follower wants to use a minimum spanning tree of G (now considered as undirected). For this game, in [9], the authors proved the APX-hardness already when the number of possible edge costs is 2 and gave an $O(logn)$-approximation algorithm. Better approximations are possible when the leader can also choose the positions of her edges [10].

All the above examples fall within the class of SNPGs handled by the general model proposed in [11], which encompasses all the cases where each follower aims at optimizing a polynomial-time network optimization problem in which the cost of the network is given by the sum of prices and costs of contained edges, namely

$$f_2(p,H)=\sum _{e\in P\cap E\left(H\right)}p\left(e\right)+\sum _{e\in C\cap E\left(H\right)}c\left(e\right).$$

(1)

Thus, in this model, we have that $f_1$ coincides with $f_2$ once this is restricted to the leader’s edges. To this respect, the leader’s and follower’s maximization and minimization functions are therefore symmetric. The authors showed that all SNPGs in this class can be tightly approximated within $(1+ϵ)({\mathcal{H}}_k+{\mathcal{H}}_{\left|P\right|})$, for any $ϵ>0$, where k denotes the number of followers, while ${\mathcal{H}}_i$ is the i-th harmonic number.

In recent years, the framework of Stackelberg pricing games has been applied on top of several fundamental optimization problems [12,13,14,15,16,17,18]. All these problems fall with the case of symmetric leader–follower objective functions. What about the case in which the symmetry does not hold?

1.2. Asymmetric SNPGs

In this paper, we focus on a natural asymmetric SNPG, namely that in which the follower aims at building a single-source shortest paths tree (SPT) of G rooted at a given node r. More formally, our game, which we call Asymmetric Stackelberg Shortest Paths Tree (ASSPT), can be described as the following bilevel optimization problem (all the paths are assumed to be directed):

• Instance: A directed graph $G=(V,E=C\cup P,C\cap P=\varnothing )$, a function $c:e\in C\to {\mathbb{R}}^{+}$, and a source node $r\in V$.
• Leader feasible solution: A pricing $p:e\in P\to {\mathbb{R}}^{+}$.

  –

  Follower feasible solution: A spanning arborescence $T=(V,E(T\left)\right)$ of G rooted at r (after edges in P have been priced).

  –

  Follower objective: Find a feasible solution minimizing the sum of all the path costs in T from r to any node in G, namely, denoting by $\left|\right|e\left|\right|$ the number of paths in T emanating from r and using e, minimize

  $$f_2(p,T)=\sum _{e\in P\cap E\left(T\right)}p\left(e\right)·\left|\right|e\left|\right|+\sum _{e\in C\cap E\left(T\right)}c\left(e\right)·\left|\right|e\left|\right|.$$

• Leader objective: Find a feasible pricing maximizing the revenue w.r.t. an optimal solution, say $T\left(p\right)$, selected by the follower, namely minimize

  $$f_1(p,T\left(p\right))=\sum _{e\in P\cap E\left(T\right(p\left)\right)}p\left(e\right).$$

This game is clearly asymmetric, since $f_1$ does not coincide with $f_2$ once this is restricted to priced edges, and finds its motivation in SPT-based routing on the Internet. Here, an Autonomous System (i.e., the leader) controlling part of the underlying network infrastructure could suitably adjust the costs of her edges in order to influence the choice of a follower in selecting a subnetwork satisfying his specific connectivity requirements. Actually, if the follower needs to provide a broadcasting service from a source to a set of destination nodes (i.e., final users which will in their turn pay for the service a cost proportional to the sum of the edge costs along a corresponding path from the source node), then buying an SPT rooted at the source allows the follower to certify the usage of a cheapest routing path.

With the study of the ASSPT game, we continue in the effort of analyzing the computational aspects of SPT pricing games, which started in [19,20] with the symmetric version of the game (i.e., that in which the leader’s revenue for each selected edge is given by its price multiplied by the number of paths—emanating from the source—it belongs to). For this game, Bilo et al. [19] proved that finding an optimal pricing for the leader’s edges is NP-hard, as soon as $\left|P\right|=\Theta \left(n\right)$, while it is polynomial-time solvable when $\left|P\right|$ is constant. A faster algorithm for the latter case was improved by Cabello [20]. In the following, as usual, we assume that, when multiple optimal solutions are available for the follower, he selects an optimal solution maximizing the leader’s revenue (At a first glance, this rule looks in contrast with the antagonistic nature of the game. However, if this rule is relaxed, then it is easy to see that an optimal solution for the leader can only be reached within any arbitrary small subtractive term.).

1.3. Our Results

Throughout the paper, we analyze the ASSPT game under several respects. More precisely, we first study the complexity of the game, and we show that finding an optimal pricing for the leader’s edges is an extremely difficult task, even under strongly restrictive assumptions. Indeed, we show that for every $ϵ>0$, the ASSPT game is not approximable within a factor of $n^{1/2-ϵ}$, unless P = NP. Then, we turn our attention to the unweighted ASSPT game, i.e., the one in which $c\left(e\right)=1$ for any $e\in C$, while $p:e\in P\to \{1,+\infty \}$, and we prove that, for every $ϵ>0$, the game is not approximable within a factor of $n^{1/3-ϵ}$, unless $\mathsf{P}=\mathsf{NP}$.

Then, we turn our attention to the development of an approximation algorithm for the ASSPT game, and we devise a pricing strategy that in $O(m+nlogn)$ time returns an $(n-1)$-approximation of the optimal leader’s revenue. Although our algorithm leaves an $O\left(\sqrt{n}\right)$ gap open with the corresponding inapproximability result, remarkably, its running time is strongly polynomial (i.e., it does not depend on the magnitude of the costs of the edges in C). Therefore, it compares favorably with the powerful but non-strongly polynomial single-price algorithm [11], which has a provably logarithmic approximation ratio for any symmetric SNPGs in which $f_2$ is of the form (1), while in contrast we show that for the ASSPT game it can only guarantee an $\Omega \left(n\right)$ factor.

Finally, motivated by practical applications, we study the ASSPT game when edges in C are unweighted and happen to form two popular network communication topologies, namely stars and chains. As far as the star topology is concerned, we first show an equivalence of the ASSPT game with the well-studied Rooted Maximum Leaf Outbranching (RMLO) problem, which asks for finding a spanning arborescence rooted at some prescribed vertex of a digraph with the maximum number of leaves. This problem is known to be NP-hard already on directed acyclic graphs (DAGs), as well as 92-approximable [21,22]. Thus, these results immediately extend to the ASSPT game on unweighted stars. Moreover, we show the APX-hardness of such a game even if G is actually a DAG, and this inapproximability carries over to the RMLO problem on DAGs, as is shown below, which is a result of independent interest. Concerning the chain topology, we show that, if G is a DAG, then our approximation algorithm returns an optimal pricing, even in the weighted case. On the other hand, if G is not a DAG, then we prove the ASSPT game becomes NP-hard, and so the problem of finding a constant-ratio approximation algorithm, for which we conjecture the existence, remains a challenging open problem.

The rest of the paper is organized as follows. Section 2 contains inapproximability results. Section 3 presents our approximation algorithm, along with a bad instance example for the single-price algorithm. Section 4 deals with the star and the chain topology. Section 5 concludes the paper and suggests possible future work.

2. Non-Approximability Results

In this section, we prove that the ASSPT game along with some basic variants of it are very hard to approximate. For the sake of simplifying the presentation, we first analyze a binary pricing version of the game, denoted as $\mathrm{ASSPT}\left(\{{\rho }_1,{\rho }_2\}\right)$, in which the leader is constrained to price her edges either ${\rho }_1$ or ${\rho }_2$. Then, we start by proving the following:

Theorem 1.

For every ${\rho }_2>{\rho }_1\ge 0$, with ${\rho }_2/{\rho }_1=O\left(1\right)$, and for every constant $ϵ>0$, the $\mathrm{ASSPT}\left(\{{\rho }_1,{\rho }_2\}\right)$ game is not approximable within a factor of $n^{1/2-ϵ}$, unless $\mathsf{P}=\mathsf{NP}$, even on DAGs.

Proof. 

The reduction is from the Maximum Independent Set (MIS) problem, i.e., the problem of finding a maximum cardinality set I of vertices of a given undirected graph G of n vertices such that no pair of vertices in I is linked by an edge of G. More precisely, we describe how a graph G of n vertices—which is provided as an instance of the MIS problem—can be transformed into an instance of the $\mathrm{ASSPT}\left(\{{\rho }_1,{\rho }_2\}\right)$ on a graph $G^{\prime }$ of $N=\Theta \left(n^2\right)$ vertices. The claim then follows from the fact that the MIS problem is not approximable within a factor of $n^{1-{ϵ}^{\prime }}$ for every constant ${ϵ}^{\prime }>0$, unless $\mathsf{P}=\mathsf{NP}$, even if G is a connected graph [23].

The reduction works as follows. From a given undirected connected graph $G=(V,E)$ of n vertices, we build a three-layered DAG $G^{\prime }$. The first layer of $G^{\prime }$ contains the root vertex r (w.l.o.g., we can assume that $r\notin V$), the second layer of $G^{\prime }$ contains a copy of all the vertices of G, while the third layer of $G^{\prime }$ contains n copies of all the vertices of G. We observe that $G^{\prime }$ has $N=\Theta \left(n^2\right)$ vertices. The set of fixed-cost edges is the following: there is an edge of cost ${\rho }_2$ from r to every vertex in the second layer, and there is an edge of cost $\rho =max\{0,2{\rho }_1-{\rho }_2\}$ from a vertex u in the second layer to all the copies of vertex v in the third layer iff $(u,v)\in E$. The set P of leader’s edges is the following: there is an edge from r to every vertex in the second layer, and every vertex u in the second layer has an outgoing edge towards each of its copies in the third layer. An example of the reduction is shown in Figure 1.

By the connectivity property of G, there is a fixed-cost path of length ${\rho }_2$ from r to every vertex in the second layer, and a fixed-cost path of length ${\rho }_2+\rho$ from r to every vertex in the third layer. Let ${\rho }^{\prime }$ be equal to ${\rho }_1$ if ${\rho }_1>0$, and ${\rho }_2$ otherwise. In what follows, we prove that every pricing $p:P\to \{{\rho }_1,{\rho }_2\}$ defines an independent set $I_p$ of G, and yields a revenue of at most ${\rho }_{2}n+{\rho }^{\prime }n\left|I_p\right|$. Moreover, we also prove that for every independent set I of G, there exists a pricing p yielding a revenue of at least ${\rho }^{\prime }n\left|I\right|$, and such that $I_p=I$. The claim then follows from the non-approximability result of the MIS problem and because $G^{\prime }$ has $N=\Theta \left(n^2\right)$ vertices. Indeed, for the sake of contradiction, assume that $\mathrm{ASSPT}\left(\{{\rho }_1,{\rho }_2\}\right)$ is approximable within a factor of $N^{1/2-ϵ}=n^{1-2ϵ}$, for some constant $ϵ>0$, by a polynomial-time algorithm $\mathcal{A}$. Let $p^{*}$ be an optimal pricing such that $I_{p^{*}}=I^{*}$ is a maximum independent set of G and let p be the pricing computed by $\mathcal{A}$. The revenue yielded by $p^{*}$ is of at least ${\rho }^{\prime }n\left|I^{*}\right|$, while the revenue yielded by p is of at most ${\rho }_{2}n+{\rho }^{\prime }n\left|I_p\right|$. Since $\frac{{\rho }^{\prime }n\left|I^{*}\right|}{{\rho }_{2}n+{\rho }^{\prime }n\left|I_p\right|}\le n^{1-2ϵ}$, we have that $\frac{|I^{*}|}{|I_p|}\le n^{1-2ϵ}\left(1+\frac{{\rho }_2}{{\rho }^{\prime }\left|I_p\right|}\right)=O\left(n^{1-2ϵ}\right)$, and, therefore, $\mathcal{A}$ can be used to compute—in polynomial time—an $\left(n^{1-2ϵ}\right)$-approximate solution for the MIS problem instance. However, this contradicts the fact that the MIS problem is not approximable within a factor of $n^{1-{ϵ}^{\prime }}$, for any constant ${ϵ}^{\prime }>0$, unless $\mathsf{P}=\mathsf{NP}$.

Let $e_u$ denote any leader’s edge from a vertex u in the second layer to one of its copies in the third layer. For a pricing p, let $I_p$ denote the set of vertices u having some $e_u$ with $p\left(e_u\right)>0$ being part of an SPT of $G^{\prime }$. The edge $e_u$ is contained in an SPT of $G^{\prime }$ iff

$$\forall v\in V\mathrm{s}.\mathrm{t}.(u,v)\in E,p(r,u)+p\left(e_u\right)\le p(r,v)+\rho .$$

From the above inequalities, we have that $e_u$ is contained in an SPT of $G^{\prime }$ and $p\left(e_u\right)>0$ iff

$$\left\{\begin{array}{c}p(r,u)={\rho }_1,\hfill \\ p\left(e_u\right)={\rho }^{\prime }\hfill \\ p(r,v)={\rho }_2\hfill & \forall v\in V\mathrm{s}.\mathrm{t}.(u,v)\in E.\hfill \end{array}\right.$$

(2)

This implies that, if edge $e_u$ is in some SPT of $G^{\prime }$ and $p\left(e_u\right)>0$, then no SPT of $G^{\prime }$ contains the edge $e_v$, for every vertex v such that $(u,v)\in E$. As a consequence, the set $I_p$ always defines an independent set of G. Moreover, observe that the revenue yielded by p is at most ${\rho }_{2}n$ for the leader’s edges outgoing from r, and at most ${\rho }^{\prime }n\left|I_p\right|$ for the other edges. Therefore, the total revenue yielded by p is at most ${\rho }_{2}n+{\rho }^{\prime }n\left|I_p\right|$.

To complete the proof, let I be an independent set of G. The pricing p that satisfies the equalities in (2) for every $e_u$ and for every $u\in I$, yields a revenue of at least ${\rho }^{\prime }n\left|I\right|$, and defines an independent set $I_p$ such that $I_p=I$. □

From the above theorem, we can easily derive the following general result:

Theorem 2.

For every $ϵ>0$, the ASSPT game is not approximable within a factor of $n^{1/2-ϵ}$, unless $\mathsf{P}=\mathsf{NP}$, even on DAGs where fixed-cost edges have all cost 1.

Proof. 

Consider the DAG $G^{\prime }$ built in the reduction of Theorem 1 for the case ${\rho }_1=\frac{n+1}{2}$ and ${\rho }_2=n$, which implies $\rho =1$. Build a graph $G^{″}$ from a copy of $G^{\prime }$ by replacing every fixed-cost edge of cost k with k edges all having cost 1. Figure 2 shows an example of the reduction. Observe that $G^{″}$ still contains $\Theta \left(n^2\right)$ vertices.

For a feasible pricing p, let $I_p$ denote the set of vertices u having some $e_u$ with $p\left(e_u\right)>1$ being part of an SPT of $G^{\prime }$. The edge $e_u$ is contained in an SPT of $G^{\prime }$ iff

$$\forall v\in V\mathrm{s}.\mathrm{t}.(u,v)\in E,min\left\{{\rho }_2,p(r,u)\right\}+p\left(e_u\right)\le min\left\{{\rho }_2,p(r,v)\right\}+1.$$

This implies that if edge $e_u$ is in some SPT of $G^{\prime }$ and $p\left(e_u\right)>1$, then no SPT of $G^{\prime }$ contains the edge $e_v$, for every vertex v such that $(u,v)\in E$. Therefore, $I_p$ is an independent set of G. Moreover, p yields a revenue of at most $O\left(n^2\right)+n^2\left|I_p\right|$. In Theorem 1, we show a pricing p in $G^{\prime }$ yielding a revenue R of at least ${\rho }_{2}n\left|I\right|=n^2\left|I\right|$, where I is a maximum independent set of G. It is easy to see that pricing $G^{″}$ with p yields a revenue of at least R. This completes the proof. □

We now turn our attention to the unweighted ASSPT game, i.e., the one in which $c\left(e\right)=1$ for any $e\in C$, while the leader’s price function is restricted to $p:e\in P\to \{1,+\infty \}$. Even in this simplified binary version, the game is very hard:

Theorem 3.

For every $ϵ>0$, the unweighted ASSPT game is not approximable within a factor of $n^{1/3-ϵ}$, unless $\mathsf{P}=\mathsf{NP}$, even on DAGs.

Proof. 

Consider the DAG $G^{″}$ defined in the proof of Theorem 2. $G^{″}$ has been built from the DAG $G^{\prime }$ defined in Theorem 1 for the case ${\rho }_1=\frac{n+1}{2}$ and ${\rho }_2=n$, which implies $\rho =1$.

From $G^{″}$, we build the DAG $G^{‴}$, which is obtained by replacing each edge $e_u$ by a path ${\pi }_u$ of n leader’s edges. Moreover, for every vertex $v^{\prime }\in {\pi }_u$ and for every vertex v such that $(u,v)$ is a unit-cost edge of $G^{″}$, we add the unit-cost edge $(v,v^{\prime })$ to $G^{‴}$. As a consequence, there is a fixed-cost path of length $n+1$ from r to every $v^{\prime }$. Figure 3 shows an example of the reduction. Observe that $G^{‴}$ has $\Theta \left(n^3\right)$ vertices.

Let p be a pricing in $G^{‴}$ that prices edges either 1 or $+\infty$. Let $p^{\prime }$ be a pricing in $G^{″}$ defined as follows. For an edge e incident to the root vertex, $p^{\prime }\left(e\right)=1$ if $p\left(e\right)=1$. An edge $e_u$ has a price of i if the first $i\ge 1$ edges of the corresponding path ${\pi }_u$ in $G^{‴}$ are contained in an SPT of $G^{‴}$, and no SPT of $G^{‴}$ contains the first $i+1$ edges of the corresponding path ${\pi }_u$ in $G^{‴}$. All the remaining edges are priced with an arbitrarily large value (observe that pricing an edge with $+\infty$ is equivalent to pricing it with an arbitrarily large value). Observe that, if p yields a revenue of R, then so does $p^{\prime }$. Indeed, an edge $(r,u)$ is contained in an SPT of $G^{″}$ iff it is contained in an SPT of $G^{‴}$. Furthermore, an edge $e_u$ with price i is contained in an SPT of $G^{″}$ iff the first i edges of the corresponding path ${\pi }_u$ are contained in an SPT of $G^{‴}$.

In the proof of Theorem 2, we show that $p^{\prime }$ defines an independent set $I_{p^{\prime }}$ of G and yields a revenue $R^{\prime }$ of at most $O\left(n^2\right)+n^2\left|I_{p^{\prime }}\right|$. As a consequence, p defines an independent set $I_p=I_{p^{\prime }}$ of G and yields a revenue R of at most $R^{\prime }$. Let I be a maximum independent set of G. Let p be a pricing in $G^{‴}$ which prices an edge e with 1 iff $e=(r,u)$, or $e\in E\left({\pi }_u\right)$ and $u\in I$. Observe that p yields a revenue of $|I_p|+n^2\left|I_p\right|$. This completes the proof. □

3. A Strongly Polynomial $\mathbf{O}\left(\mathbf{n}\right)$-Approximation Algorithm

For symmetric SNPGs, Briest et al. [11] proved the existence of an algorithm, called the single-price algorithm, that guarantees an approximation of $(1+ϵ)({\mathcal{H}}_k+{\mathcal{H}}_{\left|P\right|})$, where k denotes the number of followers. Notice that this result implies an $O(logn)$-approximation for the symmetric version of the Stackelberg SPT game studied in [19]. Therefore, a simple question is whether the single-price algorithm provides a good approximation also for the ASSPT game. Not surprisingly, this is not the case, as illustrated in Figure 4, where we give an instance for which the single-price algorithm returns an $(n-3)$-approximate solution. Thus, the power of the single-price algorithm seems to rely on the alignment of the leader’s and follower’s objective functions.

Besides being only $\Omega \left(n\right)$-approximating, the single-price algorithm has also another drawback, namely it is not strongly polynomial, since it is polynomial in the input size, but its running time depends on the given edge costs. Indeed, for our problem, it requires the testing of $1+\frac{log\lceil c_0\rceil }{log(1+ϵ)}$ different weights for the priceable edges, where $c_0$ is the cost of a cheapest feasible solution not containing leader’s edges. Therefore, in an effort to improve on that, we develop the following simple strategy the leader can play in order to get in strongly polynomial-time an $(n-1)$-approximation of the maximum achievable revenue. Actually, the goal of closing the $O\left(\sqrt{n}\right)$ gap left open w.r.t. the corresponding inapproximability result remains a challenging open problem.

Theorem 4.

For the ASSPT problem, the pricing function p that prices each edge $e=(u,v)\in P$ with $p\left(e\right)=max\{0,d_{G_C}(r,v)-d_{G_C}(r,u)\}$ is computable in $O(m+nlogn)$ time and yields a revenue of at least $\frac{1}{n-1}{R}^{*}$, where $d_{G_C}$ denotes distances computed in $G_C=(V,C)$ and $R^{*}$ denotes the revenue yielded by an optimal pricing.

Proof. 

Let $p^{*}$ be a pricing such that $f_1(p^{*},H\left(p^{*}\right))=R^{*}$. For a path $\pi$, we denote by $\mathtt{revenue}\left(\pi \right)$ the value ${\sum }_{e\in E\left(\pi \right)\cap P}{p}^{*}\left(e\right)$. Let $\pi$ be a path in $H\left(p^{*}\right)$ outgoing from r such that $\mathtt{revenue}\left(\pi \right)\ge \mathtt{revenue}\left({\pi }^{\prime }\right)$, for every other path ${\pi }^{\prime }$ of $H\left(p^{*}\right)$ outgoing from r. Clearly, $\mathtt{revenue}\left(\pi \right)\ge \frac{1}{n-1}{R}^{*}$. In what follows, we show that $f_1(p,H\left(p\right))\ge \mathtt{revenue}\left(\pi \right)$.

Let $e_1,\cdots ,e_k$ denote the edges of $E\left(\pi \right)\cap P$ in the order in which they appear if we traverse $\pi$ starting from r. Let $e_i=(u_i,v_i)$, for every $i=1,\cdots ,k$. Moreover, for every $i=1,\cdots ,k$, let us denote by ${\ell }_i$ the length of the (fixed-cost) subpath of $\pi$ going from $v_{i-1}$ to $u_i$, where $v_0=r$. We have that

$$\forall i=1,\cdots ,k-1,d_{G_C}(r,v_i)+{\ell }_{i+1}\ge d_{G_C}(r,u_{i+1}).$$

Summing over all is, adding up the two equalities $d_{G_C}(r,u_1)={\ell }_1$ and $d_{G_C}(r,v_k)=d_{G_C}(r,v_k)$, and rearranging the terms, we obtain

$$\sum _{i=1}^k\left(d_{G_C}(r,v_i)-d_{G_C}(r,u_i)\right)\ge d_{G_C}(r,v_k)-\sum _{i=1}^k{\ell }_i.$$

(3)

Since $\pi$ is a shortest path in G w.r.t. $p^{*}$, we have that $\mathtt{revenue}\left(\pi \right)+{\sum }_{i=1}^k{\ell }_i\le d_{G_C}(r,v_k),$ from which we get

$$\mathtt{revenue}\left(\pi \right)\le d_{G_C}(r,v_k)-\sum _{i=1}^k{\ell }_i.$$

(4)

Furthermore, notice that $d_{G_C}(r,v)=d_{H\left(p\right)}(r,v)$ for every vertex v. Next, observe that every edge e with $p\left(e\right)>0$ is contained in a SPT of G w.r.t. p. As a consequence, there is a SPT of G w.r.t. p that contains all the edges $e_i$’s for which $p\left(e_i\right)>0$. Therefore,

$$f_1(p,H\left(p\right))\ge \sum _{i=1}^k\left(d_{G_C}(r,v_i)-d_{G_C}(r,u_i)\right).$$

(5)

Combining inequalities (3)–(5), we obtain $f_1(p,H\left(p\right))\ge \mathtt{revenue}\left(\pi \right)$. From this and from the fact that distances from r in $G_C$ can be easily computed in $O\left(\right|C|+nlogn)$, the claim follows. □

We conclude by observing that the upper-bound of the approximation ratio is asymptotically tight. Indeed, the digraph in Figure 4 without edge $e^{\prime }$, shows an example where pricing all edges according to the formula given in the above theorem does not return a better than $(n-3)$-approximate solution.

4. Dealing with Basic Network Topologies

In this section, motivated by practical applications, we consider the special cases in which edges in C are unweighted and happen to form two popular network communication topologies, namely stars and chains, and we provide a comprehensive characterization of their computational tractability.

4.1. Unweigthed Stars

In this section, we focus on instances where edges in C have cost 1 and form a star emanating from the source node r. We show that the problem of finding a pricing maximizing the revenue is equivalent to another problem known in literature as the Rooted Maximum Leaf Outbranching (RMLO) problem, which asks for finding a spanning arborescence rooted at some prescribed vertex of a digraph with the maximum number of leaves. This problem is known to be NP-hard even when restricted to DAGs [22] and even MaxSNP-hard on undirected graphs [24]. Moreover, it admits a 92-approximation algorithm [21]. Hence, the equivalence result immediately implies the existence of a constant-factor approximation algorithm for our problem, with the same approximation ratio. Moreover, we improve the inapproximability result for the RMLO problem by showing that it is APX-hard even for DAGs.

First, we observe that we can restrict ourselves to consider instances of pricing where all nodes can be reached by a path of priceable edges, since any other node would be reached through a single fixed-cost edge in any SPT computed by the follower, and thus it cannot influence the revenue. We can prove the following:

Lemma 1.

Let $G=(V,C\cup P)$ be an instance of the ASSPT game where edges in C have unitary cost and form a star rooted at r. Then, G admits a pricing with revenue greater than or equal to $k\in \mathbb{N}$ if and only if $G^{\prime }=(V,P)$ has a spanning arborescence rooted at r with at least k leaves.

Proof. 

Let T be a spanning arborescence of $G^{\prime }$ rooted at r with at least k leaves. Then, we can define the following pricing for G: $p\left(e\right)=1$, if e enters into a leaf of T, 0 otherwise. It is easy to see that such a pricing yields a revenue of k, since T is a SPT of G.

On the other hand, let us consider a pricing p with revenue $R\ge k$. Let T be the SPT computed by the follower after the leader prices her edges according to p, and let $(r,v)$ be an edge of T. Then, all the edges of the subtree of T rooted at v, say $T\left(v\right)$, must be priceable edges. Moreover, if $(r,v)$ is a fixed-cost edge, then all the edges in $T\left(v\right)$ must have price 0. Now, let $T^{\prime }$ be the subtree of T obtained by removing every fixed-cost edge $(r,v)$ and the corresponding subtree $T\left(v\right)$. From the arguments given above, we have that $R={\sum }_{e\in E\left(T^{\prime }\right)}p\left(e\right)$. Now, we show that the number of leaves of $T^{\prime }$, say ℓ, is at least R. Indeed, we have that

$$R=\sum _{e\in E\left(T^{\prime }\right)}p\left(e\right)\le \sum _{v|v\mathrm{is}\mathrm{a}\mathrm{leaf}\mathrm{in}{T}^{\prime }}{d}_{T^{\prime }}(r,v)\le \ell ,$$

where the last inequality holds since $T^{\prime }$ is a subtree of a SPT of G, which implies that, for each node v, $d_{T^{\prime }}(r,v)\le 1$.

Now, notice that $T^{\prime }$ is an arborescence rooted at r of $G^{\prime }$ as well, but it may not span V. However, we can add priceable edges to $T^{\prime }$ in order to make it spanning. This does not decrease the number of leaves. □

Theorem 5.

The ASSPT game where the edges of C have unitary cost and form a star rooted at r isAPX-hard.

Proof. 

The reduction is from Set Cover problem (SCP). An instance $I=\langle O,\mathcal{S}\rangle$ of SCP consists of a set $O=\{o_1,\cdots ,o_n\}$ of objects and a set $\mathcal{S}=\{S_1,\cdots ,S_m\}$ of m subset of O. The objective is to find a minimum-size collection of subsets in $\mathcal{S}$ whose union is O. In [25], it is shown that SCP is NP-hard.

Given an instance $I=\langle O,\mathcal{S}\rangle$ of SCP, we build the following instance of the ASSPT game. We have the root vertex r, a node $u_j$ for each $S_j$, and a node $v_i$ for each $o_i$. There is a fixed-cost edge (of cost 1) from r to each other node. Moreover, we have a priceable edge $(r,u_j)$ for each $u_j$, and a priceable edge $(u_j,v_i)$ if and only if $o_i\in S_j$ (see Figure 5). We have the following:

Lemma 2.

The instance of the ASSPT game has a pricing yielding a revenue of at least $n+m-k$ if and only if I admits a cover of size at most k.

Proof. 

Let $\mathcal{C}$ be a cover of size k for I. Then, define the following pricing: set $p(r,u_j)=0$ for each $S_j\in \mathcal{C}$, while all the other priceable edges are set to 1. It is easy to see that we obtain a unit of revenue for each $v_i$, and a unit of revenue for each $u_j$ with $S_j\notin \mathcal{C}$, which provides a total revenue of $n+m-k$.

Conversely, let p be a pricing yielding a revenue $R\ge n+m-k$, and let S be the SPT computed by the follower according to p. We define two sets of nodes. Let X be the set containing every $u_j$ which has in S at least one outgoing priceable edge, and let Y be the set containing every $v_i$ which has in S an ingoing priceable edge. Then, since every node has a distance from r of at most 1, an upper bound for R is:

$$R=\sum _{e\in E\left(S\right)\cap P}p\left(e\right)\le \sum _{v_i\in Y}{d}_S(r,v_i)+\sum _{u_j\notin X}max\{1,p(r,u_j)\}\le \left|Y\right|+m-\left|X\right|.$$

We now define a pricing $p^{\prime }$ as follows: $p^{\prime }(r,u_j)=0$ for each $u_j\in X$, while all other edges are priced at 1. Hence, it is easy to see that $p^{\prime }$ yields a revenue of at least $\left|Y\right|+m-\left|X\right|$, since now each $v_i\in Y$ is at distance 1 from r (and there is a path of priceable edges with length 1), and since every $u_j\notin X$ has an ingoing leader’s edge with price 1.

Now, we modify $p^{\prime }$ in such a way that: (i) the revenue does not change; and (ii) in the corresponding SPT $S^{\prime }$ computed by the follower, every $v_i$ has an ingoing priceable edge with price 1. We repeatedly perform the following. Consider any $v_i$ that is not reached in $S^{\prime }$ by a priceable edge with price 1, and consider a node $u_j$ such that $o_i\in S_j$. We change $p^{\prime }(r,u_j)$ from 1 to 0. This does not change the revenue, since we lose a unit of revenue from the edge $(r,u_j)$, while we obtain an additional unit of revenue from the edge $(u_j,v_i)$ which is now selected by the follower.

Finally, we define a cover for I by selecting every $S_j$ corresponding to a node $u_j$ having distance 0 in $p^{\prime }$. Since the revenue of $p^{\prime }$ is at least $n+m-k$, and since in $S^{\prime }$ every $v_i$ is reached by a priceable edge with price 1, it follows that the size of the cover is at most k. This concludes the proof. □

To prove the APX-hardness, we restrict ourselves to instances of the SCP in which each subset has cardinality at most 3, and $m\ge n$. Even in this case, the SCP is APX-hard [26]. We show that a $(1+ϵ)$-approximate algorithm for the ASSPT game would imply a $(1+{ϵ}^{\prime })$-approximate algorithm for the SCP, for a suitable ${ϵ}^{\prime }$. Assume that we have a $(1+ϵ)$-approximate algorithm for the ASSPT, and let $k^{*}$ be the size of an optimum set cover for I. We have that the algorithm returns a pricing p with revenue $R\ge (m+n-k^{*})/(1+ϵ)$. In the proof of Lemma 2, we show that p can be modified in order to yield a revenue of at least $\lceil R\rceil$. Let k be the integer such that $\lceil R\rceil =m+n-k$. Hence, from Lemma 2, we have that p induces a set cover of size k. Then, since $m\le 3k^{*}$, we have that:

$$k\le k^{*}+\frac{ϵ}{1+ϵ}(n+m-k^{*})\le k^{*}+\frac{5ϵ}{1+ϵ}{k}^{*}\le (1+{ϵ}^{\prime })k^{*}.$$

This completes the proof. □

Therefore, from Lemma 1 and Theorem 5, we obtain the following interesting result, which improves over the NP-hardness on DAGs of the RMLO problem given in [22]:

Corollary 1.

The RMLO problem isAPX-hard even on DAGs.

4.2. Unweigthed Chains

In this section we focus on instances where edges in C form a chain, and we show that while on DAGs the problem can be solved optimally, already the seemingly easy instance in which G is not a DAG but edges in C are unweighted becomes NP-hard. However, for such an instance we conjecture the existence of a constant-ratio approximation algorithm, and this is a subject of further research.

Theorem 6.

The ASSPT game where the edges of C form a chain and G is a DAG can be solved in linear time.

Proof. 

We compute $d_{G_C}(r,u)$ for every u in linear time and we set the price of a priceable edge $(u,v)$ to $p^{*}(u,v)=d_{G_C}(r,v)-d_{G_C}(r,u)$. Since priceable edges are all forward edges w.r.t. the fixed-cost path, it is easy to see that in any pricing we have that for every priceable edge $(u,v)$ the distance from u to v is upper bounded by $p^{*}(u,v)$. This implies that the maximum revenue obtainable from $(u,v)$ is at most $p^{*}(u,v)$. As a consequence, we have that the revenue we can obtain from priceable edges entering in the same node v is at most $R\left(v\right):={max}_{u\mid (u,v)\in P}{p}^{*}(u,v)$. Now, the claim follows from the fact that in $p^{*}$ the distance between any two nodes is equal to the distance in $G_C$ between the same nodes, and hence for every node v which is the head of at least one priceable edge, we obtain revenue $R\left(v\right)$. □

Theorem 7.

The ASSPT game where the edges of C have unitary cost and form a chain isNP-hard.

Proof. 

The reduction is again from SCP. Given an instance $I=\langle O=\{o_1,\cdots ,o_n\},\mathcal{S}=\{S_1,\cdots ,S_m\}\rangle$ of SCP we build the following instance $I^{\prime }$ of the ASSPT game. We have the root vertex r, a node $u_j$ for each $S_j$, and a node $v_i$ for each $o_i$. Moreover, let N be an integer that we will fix later. We have $N(n+m)$ additional nodes $w_j^i$, $i=1,\cdots ,n+m,j=1,\cdots ,N$, and $n+m$ nodes $x_i$, $i=1,\cdots ,n+m$.

The fixed-cost edges have all cost 1 and form a path (spanning all nodes) from r to $v_n$. The sequence of the nodes encountered when we traverse the path from r to $v_n$ is the following: $r,w_1^1,\cdots ,w_N^1,\cdots ,w_1^{n+m},\cdots ,w_N^{n+m},x_1,u_1,x_2,u_2,\cdots ,x_m,u_m,x_{m+1},v_1,\cdots ,x_{m+n},v_n$.

The set P of priceable edges is partitioned into two sets, say $P_1$ and $P_2$. $P_1$ is defined as follows: we have an edge $(r,x_i)$ for each i, and an edge $(x_i,w_j^i)$ for each i and each j. $P_2$ is defined similarly as in the reduction of Theorem 5, i.e., it contains an edge $(r,u_j)$ for each $u_j$ and an edge $(u_j,v_i)$ if and only if $o_i\in S_j$ (see Figure 6). We have the following:

Lemma 3.

In any optimal pricing p for the instance $I^{\prime }$ of the ASSPT game, we have $p(r,x_i)=0$ and $p(x_i,w_j^i)=d_{G_C}(r,w_j^i)$, for each $i=1,\cdots ,n+m$, and each $j=1,\cdots ,N$, when $N>8{(m+n)}^2$.

Proof. 

Let p be an optimal pricing for $I^{\prime }$ and assume by contradiction that the lemma is false. Let i be the minimum index for which the property of the lemma does not hold. Let $F_U$ be the set of priceable edges entering in some $w_j^k$, and let $F_D=P\setminus F_U$. The idea is to build a strictly better pricing $p^{\prime }$ from p. The pricing $p^{\prime }$ will lose some revenue from edges in $F_D$ and will obtain more revenue from edges in $F_U$.

Let $a=p(r,x_i)$. We can assume that $a>0$, otherwise p cannot be optimal since we can increase the revenue by simply increasing the price of every edge $(x_i,w_j^i)$ to $d_{G_C}(r,w_j^i)$. Moreover, from the optimality of p, it is clear that we can assume also that $(r,x_i)$ is in $H\left(p\right)$. Given a pricing $p^{″}$ and a node v, we will denote by $d_{p^{″}}\left(v\right)$ the distance of v from r in $H\left(p^{″}\right)$. At the beginning, $p^{\prime }$ is defined as p except that $p^{\prime }(r,x_i)=0$ and $p^{\prime }\left(e\right)=+\infty$ for every edge e not belonging to $H\left(p\right)$. Notice that, for every vertex v, $d_{p^{\prime }}\left(v\right)\ge d_p\left(v\right)-a$. We first modify prices of the edges in $F_D$. We repeatedly perform the following. If there is a node v such that $\delta :=d_p\left(v\right)-d_{p^{\prime }}\left(v\right)<a$, we consider the path P from r to v in $H\left(p\right)$. Let $e_1,\cdots ,e_h$ be the edges of $F_D$ along the path P in the order we encounter them when we traverse P from r to v. If ${\sum }_{j=1}^h{p}^{\prime }\left(e_j\right)\le \delta$, then we set $p^{\prime }\left(e_j\right)=0$ for every $e_j$. Otherwise, let k be the minimum index such that ${\sum }_{j=1}^k{p}^{\prime }\left(e_j\right)>\delta$, we first decrease $p^{\prime }\left(e_k\right)$ by $\delta -{\sum }_{j=1}^{k-1}{p}^{\prime }\left(e_j\right)$, and then we set $p^{\prime }\left(e_j\right)=0$ for each $j<k$. We stop when there is no edge left to be decreased. Notice that, when this happens, we have decreased each edge in $F_D$ at most by a and it is easy to see that the revenue of $p^{\prime }$ obtained from edges in $F_D$ decreases by at most $2a(m+n)$ since all the edges belonging to a path in $H\left(p\right)$ which was decreased by at least a will still be selected by the follower.

We then consider edges in $F_U$. First of all we set $p^{\prime }(x_i,w_j^i)$ to $d_{G_C}(r,w_j^i)$, for every $j=1,\cdots ,N$. Let $F\subseteq F_U$ be the set of edges entering in some vertex $w_j^k$ with $k>i$. For any pricing $p^{″}$, we use $F\left(p^{″}\right)$ to denote the set $F\cap H\left(p^{″}\right)$. Observe that $F\left(p^{\prime }\right)\subseteq F\left(p\right)$, since priceable edges in $F\setminus F\left(p\right)$ are priced to infinity. We now modify $p^{\prime }$ in order to guarantee that $F\left(p^{\prime }\right)=F\left(p\right)$. We repeatedly perform the following. Consider the first node $w_j^k$ when we traverse the fixed-cost path from r to $v_n$ such that $d_{p^{\prime }}\left(w_j^k\right)<d_p\left(w_j^k\right)$. Since we have decreased the prices of edges in $F_D$, we have $(x_k,w_j^k)$ belongs to $H\left(p^{\prime }\right)$. Then, we increase the price of $(x_k,w_j^k)$ by $d_p\left(w_j^k\right)-d_{p^{\prime }}\left(w_j^k\right)$. Moreover, observe that for the same reason, we have that $(x_k,w_j^k)$ still belongs to the new SPT computed by the follower and, since the paths that are increasing their length are paths using the edge $(x_k,w_j^k)$, then no other edge $(x_{k^{\prime }},w_j^{k^{\prime }})$ exits from the SPT. We repeatedly use this argument until for every node $w_j^k$ we have $d_{p^{\prime }}\left(w_j^k\right)\ge d_p\left(w_j^k\right)$. Now, it is easy to see that $F\left(p^{\prime }\right)$ must be equal to $F\left(p\right)$.

We are now ready to bound the revenue of $p^{\prime }$. We have already observed that the revenue we may lose from edges in $F_D$ is upper bounded by $2a(m+n)$, while we do not lose revenue from edges in $F_U$. On the other hand, we can now bound the increment $R_i$ of the revenue we obtain from all the edges $(x_i,w_1^i),\cdots ,(x_i,w_N^i)$. Notice that every edge $(x_i,w_j^i)$ is now selected in $p^{\prime }$. We consider two cases:

Case$i>1$

Since $(r,x_i)$ is in $H\left(p\right)$ and since $p(r,x_{i-1})=0$, we have $a\le 2$. Moreover, since the price of every edge $(x_i,w_j^i)$ increased by at least a, we have that $R_i\ge Na$ which is strictly greater than $2a(m+n)$ when $N>2(m+n)$.

Case$i=1$

When $a>N$, no edge $(x_1,w_j^1)$ was selected in $H\left(p\right)$. As a consequence, we have $R_i={\sum }_{j=1}^{N}j=\frac{N(N+1)}{2}$ which is strictly greater than $2a(m+n)$ when $N>8{(m+n)}^2$, since $a\le d_{G_C}(r,x_1)\le 2N(m+n)$.

Otherwise, when $a\le N$, we have that no edge $(x_1,w_j^1)$ with $j\le \lfloor a\rfloor$ was selected in $H\left(p\right)$. Hence, since the price of every edge $(x_1,w_j^1)$ with $j>\lfloor a\rfloor$ has been increased by at least a, we have that $R_i\ge {\sum }_{j=1}^{\lfloor a\rfloor }j+a(N-\lfloor a\rfloor )$, which is strictly greater than $2a(m+n)$ when $N>4(m+n)$.

 □

In any optimal pricing for the instance $I^{\prime }$ of the ASSPT game, edges in $P_1$ must be priced according to the above lemma and thus they yield to a revenue of $R={\sum }_{i=1}^{N(n+m)}i$. Moreover, once edges in $P_1$ have fixed prices, the instance $I^{\prime }$ is very similar to the unweighted star instance of the reduction of Theorem 5. Indeed, every vertex $u_j$ and every vertex $v_i$ has distance 1 from r in the graph $G^{\prime }=(V,C\cup P_1)$, and $P_2$ is defined as in the proof of Theorem 5. Hence, by using the same arguments given in the proof of Lemma 2, we can show that the instance of the ASSPT game has a pricing yielding a revenue of at least $R+n+m-k$ if and only if I admits a cover of size at most k. □

5. Conclusions

In this paper, we focus on an asymmetric SNPG, namely that in which the follower builds an SPT of a graph and pays a leader as the sum of the selected priced edges. Despite its apparent simplicity, such a game reveals itself as a very hard computational problem, much harder than all the previously studied—yet symmetric—SNPGs.

In search of an explanation for this discrepancy, we aim to investigate at a deeper level the mathematical nature of the corresponding bilevel optimization problem. Indeed, the asymmetry in itself does not fully explain such behavior, as suggested by an easy variation of the ASSPT game in which the follower returns to the leader only the revenue associated with the most expensive selected priced edge, which can be shown to be polynomial-time solvable. Moreover, we plan to analyze other intuitive asymmetric SNPGs, for instance that in which the follower looks for a minimum diameter spanning tree or the one in which he needs to compute a (either exact or approximate) minimum routing-cost spanning tree.