×

Competitive location and pricing on a line with metric transportation costs. (English) Zbl 1430.90369

Summary: Consider a three-level non-capacitated location/pricing problem: a firm first decides which facilities to open, out of a finite set of candidate sites, and sets service prices with the aim of revenue maximization; then a second firm makes the same decisions after checking competing offers; finally, customers make individual decisions trying to minimize costs that include both purchase and transportation. A restricted two-level problem can be defined to model an optimal reaction of the second firm to known decision of the first.
For non-metric costs, the two-level problem corresponds to Envy-free Pricing or to a special Network Pricing problem, and is \(\mathcal{APX} \)-complete even if facilities can be opened at no fixed cost. Our focus is on the metric 1-dimensional case, a model where customers are distributed on a main communication road and transportation cost is proportional to distance. We describe polynomial-time algorithms that solve two- and three-level problems with opening costs and single \(1^{\text{st}}\) level facility. Quite surprisingly, however, even the two-level problem with no opening costs becomes \(\mathcal{NP} \)-hard when two \(1^{\text{st}}\) level facilities are considered.

MSC:

90B80 Discrete location and assignment
91B24 Microeconomic theory (price theory and economic markets)
91B72 Spatial models in economics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arbib, C.; Karaşan, O. E.; Pınar, M.Ç., On envy-free perfect matching, Discrete Applied Mathematics, 261, 2019, 22-27 (2017) · Zbl 1410.91352
[2] Bard, J. F., An investigation of the linear three level programming problem, IEEE Transaction on System Man Cybernetics, 14, 711-717 (1984) · Zbl 0552.90081
[3] Berglund, P. G.; Kwon, C., Solving a location problem of a stackelberg firm competing with cournot-nash firms, Networks and Spatial Economics, 14, 1, 117-132 (2014) · Zbl 1339.91021
[4] Blair, C., The computational complexity of multi-level linear programs, Annals of Operations Research, 34, 1, 13-19 (1992) · Zbl 0751.90046
[5] Chen, N.; Ghosh, A.; Vassilvitskii, S., Optimal envy-free pricing with metric substitutability, SIAM Journal on Computing, 40, 3, 623-645 (2011) · Zbl 1235.91068
[6] Crama, Y.; Hansen, P.; Jaumard, B., Complexity of product positioning and ball intersection problems, Mathematics of Operations Research, 20, 4, 885-894 (1995) · Zbl 0846.90062
[7] Eiselt, L. G., Sequential location problems, European Journal of Operational Research, 96, 2, 217-231 (1997) · Zbl 0917.90225
[8] Fernandes, C. G.; Ferreira, C. E.; Franco, A. J.P.; Schouery, R. C.S., The envy-free pricing problem, unit-demand markets and connections with the network pricing problem, Discrete Optimization, 22, 141-161 (2016) · Zbl 1390.91136
[9] Fischer, K., Sequential discrete p-facility models for competitive location planning, Annals of Operations Research, 111, 253-270 (2002) · Zbl 1013.90082
[10] Gentile, J.; Pessoa, A. A.; Poss, M.; Roboredo, M. C., Integer programming formulations for three sequential discrete competitive location problems with foresight, European Journal of Operational Research, 265, 872-882 (2018) · Zbl 1374.90273
[11] Guruswami, V., Hartline, J. D., Karlin, A. R., Kempe, D., Kenyon, C., & McSherry, F. (2005). On profit-maximizing envy-free pricing. Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, (pp. 1164-1173). · Zbl 1297.91072
[12] Han, J.; Lu, J.; Hu, Y.; Zhang, G., Tri-level decision-making with multiple followers: Model, algorithm and case study, Information Sciences, 311, 182-204 (2015)
[13] Hansen, P., Kochetov, Y., & Mladenović, N. (2004). Lower bounds for the uncapacitated facility location problem with user preferences. Les Cahiérs du GERAD. G-2004-24.
[14] Heilporn, G.; Labbé, M.; Marcotte, P.; Savard, G., A parallel between two classes of pricing problems in transportation and marketing, Journal of Revenue and Pricing Management, 9, 110-125 (2010)
[15] Heilporn, G.; Labbé, M.; Marcotte, P.; Savard, G., A polyhedral study of the network pricing problem with connected toll arcs, Networks, 55, 3, 234-246 (2010) · Zbl 1200.90031
[16] Heilporn, G.; Labbé, M.; Marcotte, P.; Savard, G., Valid inequalities and branch-and-cut for the clique pricing problem, Discrete Optimization, 8, 393-410 (2011) · Zbl 1233.90095
[17] Hotelling, H., Stability in competition, The Economic Journal, 39, 153, 41-57 (1929)
[18] Jeroslow, R. G., The polynomial hierarchy and a simple model for competitive analysis, Mathematical Programming, 32, 2, 146-164 (1985) · Zbl 0588.90053
[19] Jin, S., & Ryan, S. M. (2014). A three-level model of centralized transmission and decentralized generation expansion planning for an electricity market: Part I. Iowa State University, Technical Report 1-2014,. http://lib.dr.iastate.edu/imse_pubs.
[20] Karakitsiou, A.; Migdalas, A., Locating facilities in a competitive environment, Optimization Letters, 11, 5, 929-945 (2017) · Zbl 1368.90095
[21] Kress, D.; Pesch, E., Sequential competitive location on networks, European Journal of Operational Research, 217, 3, 483-499 (2012) · Zbl 1244.90128
[22] Labbé, M.; Marcotte, P.; Savard, G., A bilevel model of taxation and its application to optimal highway pricing, Management Science, 44, 1595-1607 (1988)
[23] P-P, C.; Mayer, T.; J-F, T., Economic geography (2008), Princeton University Press
[24] Perez, M. D.G.; Pelegrin, B. P., All Stackelberg location equilibria in the Hotelling’s duopoly model on a tree with parametric prices, Annals of Operations Research, 122, 177-192 (2003) · Zbl 1127.90388
[25] Pinto, A. A.; Parreira, T., Price competition in the Hotelling model with uncertainty on costs, Optimization, 64, 2477-2493 (2015) · Zbl 1338.91099
[26] Stackelberg, H., The theory of the market economy (1952), Oxford University Press
[27] Street, A.; Moreira, A.; Arroyo, J. M., Energy and reserve scheduling under a joint generation and transmission security criterion: An adjustable robust optimization approach, IEEE Transaction on Power System, 29, 3-14 (2014)
[28] Tarjan, R. E., Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, Mathematical Programming, 78, 2, 169-177 (1997) · Zbl 0889.90150
[29] Teraoka, Y.; Osumi, S.; Hohjo, H., Some Stackelberg type location game, Computers & Mathematics with Applications, 46, 7, 1147-1154 (2003) · Zbl 1100.91501
[30] Tóth, B. G.; Kovács, K., Solving a huff-like Stackelberg location problem on networks, Journal of Global Optimization, 64, 2, 233-247 (2016) · Zbl 1339.90324
[31] Vicente, L. N.; Calamai, P. H., Bilevel and multilevel programming: a bibliography review, Journal of Global Optimization, 5, 3, 291-306 (1994) · Zbl 0822.90127
[32] Xu, X.; Meng, Z.; Shen, R., A three-level programming model based on conditional value-at-risk for three-stage supply chain management, Computers & Industrial Engineering, 66, 470-475 (2013)
[33] Yao, Y.; Edmunds, T.; Papageorgiou, D.; Alvarez, R., Trilevel optimization in power network defense, IEEE Transaction on System Man Cybernetics, 37, 712-718 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.