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

^{1}

Dipartimento di Scienze Umanistiche e Sociali, Università di Sassari, 21, 07100 Sassari SS, Italy

^{2}

Dipartimento di Ingegneria dell’Impresa, Università di Roma “Tor Vergata”, 50, 00133 Roma (RM), Italy

^{3}

Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, 67100 L’Aquila AQ, Italy

^{4}

Istituto di Analisi dei Sistemi ed Informatica, CNR, Via dei Taurini, 19 - 00185 Roma (RM), Italy

^{*}

Author to whom correspondence should be addressed.

^{†}

This work was partially supported by the “Fondo di Ateneo per la Ricerca 2019” grant of the University of Sassari and by the project E89C20000620005 “ALgorithmic aspects of BLOckchain TECHnology” (ALBLOTECH).

Received: 27 November 2020 / Revised: 23 December 2020 / Accepted: 24 December 2020 / Published: 31 December 2020

(This article belongs to the Special Issue Graph Algorithms and Network Dynamics)

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 $\u03f5>0$ and unless $\mathsf{P}=\mathsf{NP}$ , the leader’s problem of finding an optimal pricing is not approximable within ${n}^{1/2-\u03f5}$ , 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-\u03f5}$ . 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.