{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:29:52Z","timestamp":1760239792364,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2019s solution. As is shown, for any \u03f5&gt;0 and unless P=NP, the leader\u2019s problem of finding an optimal pricing is not approximable within n1\/2\u2212\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 n1\/3\u2212\u03f5. 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.<\/jats:p>","DOI":"10.3390\/a14010008","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T10:10:37Z","timestamp":1609409437000},"page":"8","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3169-4300","authenticated-orcid":false,"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[{"name":"Dipartimento di Scienze Umanistiche e Sociali, Universit\u00e0 di Sassari, 21, 07100 Sassari SS, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6976-5579","authenticated-orcid":false,"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria dell\u2019Impresa, Universit\u00e0 di Roma \u201cTor Vergata\u201d, 50, 00133 Roma (RM), Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1009-5552","authenticated-orcid":false,"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria e Scienze dell\u2019Informazione e Matematica, Universit\u00e0 degli Studi dell\u2019Aquila, 67100 L\u2019Aquila AQ, Italy"},{"name":"Istituto di Analisi dei Sistemi ed Informatica, CNR, Via dei Taurini, 19 - 00185 Roma (RM), Italy"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1017\/S1053837216000894","article-title":"Heinrich von Stackelberg, Market Structure and Equilibrium","volume":"38","author":"Kolev","year":"2016","journal-title":"J. Hist. Econ. Thought"},{"key":"ref_2","unstructured":"Larmore, L.L., and Goemans, M.X. (2003, January 9\u201311). Pricing network edges for heterogeneous selfish users. Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA."},{"key":"ref_3","unstructured":"Van Hoesel, C. (2006). An overview of Stackelberg pricing in networks. Research Memorandum 043, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR)."},{"key":"ref_4","first-page":"117","article-title":"Stackelberg network pricing is hard to approximate","volume":"57","author":"Joret","year":"2011","journal-title":"Networks"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Saberi, A. (2010). Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. Internet and Network Economics, Springer.","DOI":"10.1007\/978-3-642-17572-5"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1002\/net.20074","article-title":"An approximation algorithm for Stackelberg network pricing","volume":"46","author":"Roch","year":"2005","journal-title":"Networks"},{"key":"ref_7","first-page":"1608","article-title":"A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing","volume":"44","author":"Marcotte","year":"1998","journal-title":"Manag. Sci."},{"key":"ref_8","first-page":"140","article-title":"Pricing Network Edges to Cross a River","volume":"Volume 3351","author":"Persiano","year":"2004","journal-title":"Proceedings of the Approximation and Online Algorithms, Second International Workshop, WAOA 2004, Bergen, Norway, 14\u201316 September 2004"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10878-011-9414-2","article-title":"The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs","volume":"25","author":"Cardinal","year":"2013","journal-title":"J. Comb. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1016\/j.tcs.2014.11.009","article-title":"Specializations and generalizations of the Stackelberg minimum spanning tree game","volume":"562","author":"Leucci","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1007\/s00453-010-9480-3","article-title":"Stackelberg Network Pricing Games","volume":"62","author":"Briest","year":"2012","journal-title":"Algorithmica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1002\/net.20457","article-title":"On stackelberg pricing with computationally bounded customers","volume":"60","author":"Briest","year":"2012","journal-title":"Networks"},{"key":"ref_13","first-page":"213","article-title":"On the Stackelberg fuel pricing problem","volume":"Volume 1231","author":"Bistarelli","year":"2014","journal-title":"Proceedings of the 15th Italian Conference on Theoretical Computer Science, Perugia, Italy, 17\u201319 September 2014"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1174","DOI":"10.1007\/s00453-015-9993-x","article-title":"Stackelberg Bipartite Vertex Cover and the Preflow Algorithm","volume":"74","author":"Barahona","year":"2016","journal-title":"Algorithmica"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/140998846","article-title":"Pricing on Paths: A PTAS for the Highway Problem","volume":"45","author":"Grandoni","year":"2016","journal-title":"SIAM J. Comput."},{"key":"ref_16","first-page":"46:1","article-title":"Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting","volume":"Volume 80","author":"Chatzigiannakis","year":"2017","journal-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, 10\u201314 July 2017"},{"key":"ref_17","first-page":"239","article-title":"Stackelberg Packing Games","volume":"Volume 11646","author":"Friggstad","year":"2019","journal-title":"Proceedings of the Algorithms and Data Structures\u201416th International Symposium, WADS 2019, Edmonton, AB, Canada, 5\u20137 August 2019"},{"key":"ref_18","first-page":"83","article-title":"On the Complexity of Stackelberg Matroid Pricing Problems","volume":"Volume 12126","author":"Gasieniec","year":"2020","journal-title":"Proceedings of the Combinatorial Algorithms\u201431st International Workshop, IWOCA 2020, Bordeaux, France, 8\u201310 June 2020"},{"key":"ref_19","first-page":"251","article-title":"Computational Aspects of a 2-Player Stackelberg Shortest Paths Tree Game","volume":"Volume 5385","author":"Papadimitriou","year":"2008","journal-title":"Proceedings of the Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, 17\u201320 December 2008"},{"key":"ref_20","unstructured":"Cabello, S. (2012). Stackelberg Shortest Path Tree Game, Revisited. arXiv."},{"key":"ref_21","first-page":"86","article-title":"On Finding Directed Trees with Many Leaves","volume":"Volume 5917","author":"Chen","year":"2009","journal-title":"Proceedings of the Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, 10\u201311 September 2009"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/070710494","article-title":"Spanning Directed Trees with Many Leaves","volume":"23","author":"Alon","year":"2009","journal-title":"SIAM J. Discret. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","article-title":"Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number","volume":"3","author":"Zuckerman","year":"2007","journal-title":"Theory Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","article-title":"A short note on the approximability of the maximum leaves spanning tree problem","volume":"52","author":"Galbiati","year":"1994","journal-title":"Inf. Process. Lett."},{"key":"ref_25","unstructured":"Leighton, F.T., and Shor, P.W. (1997, January 4\u20136). A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, TX, USA."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","article-title":"Some APX-completeness results for cubic graphs","volume":"237","author":"Alimonti","year":"2000","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/8\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:48:14Z","timestamp":1760179694000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010008"],"URL":"https:\/\/doi.org\/10.3390\/a14010008","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,12,31]]}}}