Next Article in Journal
Constructing Minimally 3-Connected Graphs
Next Article in Special Issue
Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
Previous Article in Journal
A Modified Network-Wide Road Capacity Reliability Analysis Model for Improving Transportation Sustainability
Open AccessArticle

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 ϵ>0 and unless P=NP, the leader’s problem of finding an optimal pricing is not approximable within n1/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 n1/3ϵ. On the positive side, we devise a strongly polynomial-time O(n)-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. View Full-Text
Keywords: communication networks; shortest paths tree; stackelberg games; network pricing games communication networks; shortest paths tree; stackelberg games; network pricing games
Show Figures

Figure 1

MDPI and ACS Style

Bilò, D.; Gualà, L.; Proietti, G. Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game. Algorithms 2021, 14, 8. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010008

AMA Style

Bilò D, Gualà L, Proietti G. Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game. Algorithms. 2021; 14(1):8. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010008

Chicago/Turabian Style

Bilò, Davide; Gualà, Luciano; Proietti, Guido. 2021. "Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game" Algorithms 14, no. 1: 8. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010008

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Search more from Scilit
 
Search
Back to TopTop