{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:43:26Z","timestamp":1763664206923,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008001","name":"Universit\u00e4t zu K\u00f6ln","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>In a Stackelberg Pricing Game a distinguished player, the leader<\/jats:italic>, chooses prices for a set of items, and the other players, the followers<\/jats:italic>, each seek to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have a base set of items, some with fixed prices, some priceable, and constraints on the subsets that are feasible for each follower. In this combinatorial setting, Briest et al. and Balcan et al. independently showed that the maximum revenue can be approximated to a factor of $$H_k\\sim \\log k$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \u223c<\/mml:mo>\n log<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where k<\/jats:italic> is the number of priceable items. Our results are twofold. First, we strongly generalize the model by letting the follower minimize any continuous function plus a linear term over any compact subset of $${\\mathbb {R}}^n_{\\ge 0}$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n \n \u2265<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>; the coefficients (or prices<\/jats:italic>) in the linear term are chosen by the leader and determine her revenue. In particular, this includes the fundamental case of linear programs. We give a tight lower bound on the revenue of the leader, generalizing the results of Briest et al.\u00a0and Balcan et al. Besides, we prove that it is strongly NP-hard to decide whether the optimum revenue exceeds the lower bound by an arbitrarily small factor. Second, we study the parameterized complexity of computing the optimal revenue with respect to the number k<\/jats:italic> of priceable items. In the combinatorial setting, given an efficient algorithm for optimal follower solutions, the maximum revenue can be found by enumerating the $$2^k$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> subsets of priceable items and computing optimal prices via a result of Briest et al., giving time $$O(2^k|I|^c)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n |<\/mml:mo>\n I<\/mml:mi>\n \n |<\/mml:mo>\n c<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where |I<\/jats:italic>| is the input size. Our main result here is a W[1]-hardness proof for the case where the followers minimize a linear program, ruling out running time $$f(k)|I|^c$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n |<\/mml:mo>\n I<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n c<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> unless $$\\mathsf {FPT} =\\mathsf {W[1]} $$<\/jats:tex-math>\n \n FPT<\/mml:mi>\n =<\/mml:mo>\n \n W<\/mml:mi>\n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and ruling out time $$|I|^{o(k)}$$<\/jats:tex-math>\n \n \n |<\/mml:mo>\n I<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \n o<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> under the Exponential-Time Hypothesis.<\/jats:p>","DOI":"10.1007\/s10107-020-01495-0","type":"journal-article","created":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T13:02:28Z","timestamp":1587214948000},"page":"653-695","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Revenue maximization in Stackelberg Pricing Games: beyond the combinatorial setting"],"prefix":"10.1007","volume":"187","author":[{"given":"Toni","family":"B\u00f6hnlein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,18]]},"reference":[{"key":"1495_CR1","unstructured":"Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., Zhu, A.: An: approximation algorithms for k-anonymity. J. Privacy Technol. (JOPT) (2005)"},{"key":"1495_CR2","doi-asserted-by":"publisher","first-page":"1174","DOI":"10.1007\/s00453-015-9993-x","volume":"74","author":"M Ba\u00efou","year":"2016","unstructured":"Ba\u00efou, M., Barahona, F.: Stackelberg bipartite vertex cover and the preflow algorithm. Algorithmica 74, 1174\u20131183 (2016)","journal-title":"Algorithmica"},{"key":"1495_CR3","unstructured":"Balcan, M.-F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008, pp 50\u201359 (2008)"},{"key":"1495_CR4","unstructured":"Berbeglia, G., Joret, G.: Assortment optimisation under a general discrete choice model: a tight analysis of revenue-ordered assortments. (2016) arXiv preprint arXiv:1606.01371"},{"key":"1495_CR5","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/j.tcs.2014.11.009","volume":"562","author":"D Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Specializations and generalizations of the Stackelberg minimum spanning tree game. Theor. Comput. Sci. 562, 643\u2013657 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"1495_CR6","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Proietti, G., Widmayer, P.: Computational aspects of a 2-player Stackelberg shortest paths tree game. In: Internet and Network Economics, pp. 251\u2013262. Springer (2008)","DOI":"10.1007\/978-3-540-92185-1_32"},{"key":"1495_CR7","volume-title":"Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity","author":"J Borwein","year":"1987","unstructured":"Borwein, J., Borwein, P.: Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. Wiley, Hoboken (1987)"},{"key":"1495_CR8","doi-asserted-by":"crossref","unstructured":"Briest, P., Chalermsook, P., Khanna, S., Laekhanukit, B., Nanongkai, D.: Improved hardness of approximation for stackelberg shortest-path pricing. In: Internet and Network Economics, pp. 444\u2013454. Springer (2010)","DOI":"10.1007\/978-3-642-17572-5_37"},{"issue":"1","key":"1495_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/net.20457","volume":"60","author":"P Briest","year":"2012","unstructured":"Briest, P., Gual\u00e0, L., Hoefer, M., Ventre, C.: On stackelberg pricing with computationally bounded customers. Networks 60(1), 31\u201344 (2012)","journal-title":"Networks"},{"issue":"3\u20134","key":"1495_CR10","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/s00453-010-9480-3","volume":"62","author":"P Briest","year":"2012","unstructured":"Briest, P., Hoefer, M., Krysta, P.: Stackelberg network Pricing Games. Algorithmica 62(3\u20134), 733\u2013753 (2012)","journal-title":"Algorithmica"},{"key":"1495_CR11","unstructured":"Cabello, S.: Stackelberg shortest path tree game. Revisited (2012). arXiv preprintarXiv:1207.2317"},{"key":"1495_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s00453-009-9299-y","volume":"59","author":"J Cardinal","year":"2011","unstructured":"Cardinal, J., Demaine, E.D., Fiorini, S., Joret, G., Langerman, S., Newman, I., Weimann, O.: The Stackelberg minimum spanning tree game. Algorithmica 59, 129\u2013144 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"1495_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10878-011-9414-2","volume":"25","author":"J Cardinal","year":"2013","unstructured":"Cardinal, J., Demaine, E.D., Fiorini, S., Joret, G., Newman, I., Weimann, O.: The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs. J. Comb. Optim. 25(1), 19\u201346 (2013)","journal-title":"J. Comb. Optim."},{"issue":"6","key":"1495_CR14","doi-asserted-by":"publisher","first-page":"2424","DOI":"10.1137\/100787799","volume":"42","author":"T Chakraborty","year":"2013","unstructured":"Chakraborty, T., Huang, Z., Khanna, S.: Dynamic and non-uniform pricing strategies for revenue maximization. SIAM J. Comput. 42(6), 2424\u20132451 (2013)","journal-title":"SIAM J. Comput."},{"key":"1495_CR15","unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23\u201325, 2005, pp. 1164\u20131173 (2005)"},{"issue":"4","key":"1495_CR16","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"1495_CR17","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1080\/00029890.2006.11920276","volume":"113","author":"JW Hagood","year":"2006","unstructured":"Hagood, J.W., Thomson, B.S.: Recovering a function from a dini derivative. Am. Math. Mon. 113, 34\u201346 (2006)","journal-title":"Am. Math. Mon."},{"issue":"4","key":"1495_CR18","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1495_CR19","first-page":"117","volume":"57","author":"G Joret","year":"2011","unstructured":"Joret, G.: Stackelberg network pricing is hard to approximate. Networks 57(2), 117\u2013120 (2011)","journal-title":"Networks"},{"key":"1495_CR20","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1287\/mnsc.44.12.1608","volume":"44","author":"M Labb\u00e9","year":"1998","unstructured":"Labb\u00e9, M., Marcotte, P., Savard, G.: A Bilevel model of taxation and its application to optimal highway pricing. Manag. Sci. 44, 1608\u20131622 (1998)","journal-title":"Manag. Sci."},{"key":"1495_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1002\/net.20074","volume":"46","author":"S Roche","year":"2005","unstructured":"Roche, S., Savard, G., Marcotte, P.: An approximation algorithm for Stackelberg network pricing. Networks 46, 57\u201367 (2005)","journal-title":"Networks"},{"key":"1495_CR22","doi-asserted-by":"publisher","first-page":"1393","DOI":"10.1016\/j.ejor.2006.08.064","volume":"189","author":"S van Hoesel","year":"2008","unstructured":"van Hoesel, S.: An overview of Stackelberg pricing in networks. Eur. J. Oper. Res. 189, 1393\u20131402 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"1495_CR23","volume-title":"Marktform und Gleichgewicht","author":"H von Stackelberg","year":"1934","unstructured":"von Stackelberg, H.: Marktform und Gleichgewicht. Springer, Berlin (1934)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01495-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01495-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01495-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T18:53:03Z","timestamp":1618944783000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01495-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,18]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["1495"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01495-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,4,18]]},"assertion":[{"value":"5 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}