IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v54y2007i4p411-420.html
   My bibliography  Save this article

Pricing bridges to cross a river

Author

Listed:
  • Mustapha Bouhtou
  • Alexander Grigoriev
  • Stan van Hoesel
  • Anton F. van der Kraaij
  • Frits C.R. Spieksma
  • Marc Uetz

Abstract

We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX‐hard. Moreover, we analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + lnD)‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = NP, and we prove the existence of an n‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007

Suggested Citation

  • Mustapha Bouhtou & Alexander Grigoriev & Stan van Hoesel & Anton F. van der Kraaij & Frits C.R. Spieksma & Marc Uetz, 2007. "Pricing bridges to cross a river," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(4), pages 411-420, June.
    • Handle: RePEc:wly:navres:v:54:y:2007:i:4:p:411-420
    DOI: 10.1002/nav.20216
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20216
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20216?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Martine Labbé & Patrice Marcotte & Gilles Savard, 1998. "A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing," Management Science, INFORMS, vol. 44(12-Part-1), pages 1608-1622, December.
    2. Bouhtou, M. & van Hoesel, C.P.M. & van der Kraaij, A.F. & Lutton, J.L., 2003. "Tariff optimization in networks," Research Memorandum 011, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    3. Grigoriev, A. & van Hoesel, C.P.M. & van der Kraaij, A.F. & Uetz, M.J. & Bouhtou, M., 2004. "Pricing network edges to cross a river," Research Memorandum 009, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tawfik, Christine & Gendron, Bernard & Limbourg, Sabine, 2022. "An iterative two-stage heuristic algorithm for a bilevel service network design and pricing model," European Journal of Operational Research, Elsevier, vol. 300(2), pages 512-526.
    2. Christine Tawfik & Sabine Limbourg, 2018. "Pricing Problems in Intermodal Freight Transport: Research Overview and Prospects," Sustainability, MDPI, vol. 10(9), pages 1-22, September.
    3. Martine Labbé & Alessia Violin, 2016. "Bilevel programming and price setting problems," Annals of Operations Research, Springer, vol. 240(1), pages 141-169, May.
    4. José Correa & Tobias Harks & Vincent J. C. Kreuzen & Jannik Matuschke, 2017. "Fare Evasion in Transit Networks," Operations Research, INFORMS, vol. 65(1), pages 165-183, February.
    5. José Correa & Tobias Harks & Vincent J. C. Kreuzen & Jannik Matuschke, 2017. "Fare Evasion in Transit Networks," Operations Research, INFORMS, vol. 65(1), pages 165-183, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Grigoriev, A. & van Hoesel, C.P.M. & van der Kraaij, A.F. & Uetz, M.J. & Bouhtou, M., 2004. "Pricing network edges to cross a river," Research Memorandum 009, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Olivier Bochet, 2007. "Nash Implementation with Lottery Mechanisms," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 28(1), pages 111-125, January.
    3. van Hoesel, Stan, 2008. "An overview of Stackelberg pricing in networks," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1393-1402, September.
    4. Jean Cardinal & Erik D. Demaine & Samuel Fiorini & Gwenaël Joret & Ilan Newman & Oren Weimann, 2013. "The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs," Journal of Combinatorial Optimization, Springer, vol. 25(1), pages 19-46, January.
    5. Hoesel Stan van & Kraaij Anton F. van der & Mannino Carlo & Bouhtou Mustapha & Oriolo Gianpaolo, 2003. "Polynomial cases of the tarification problem," Research Memorandum 063, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    6. Luce Brotcorne & Martine Labbé & Patrice Marcotte & Gilles Savard, 2008. "Joint Design and Pricing on a Network," Operations Research, INFORMS, vol. 56(5), pages 1104-1115, October.
    7. Aimé Kamgaing Kuiteingf & Patrice Marcotte & Gilles Savard, 2017. "Network Pricing of Congestion-Free Networks: The Elastic and Linear Demand Case," Transportation Science, INFORMS, vol. 51(3), pages 791-806, August.
    8. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    9. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    10. Ke, Ginger Y. & Zhang, Huiwen & Bookbinder, James H., 2020. "A dual toll policy for maintaining risk equity in hazardous materials transportation with fuzzy incident rate," International Journal of Production Economics, Elsevier, vol. 227(C).
    11. S. Dempe & J. F. Bard, 2001. "Bundle Trust-Region Algorithm for Bilinear Bilevel Programming," Journal of Optimization Theory and Applications, Springer, vol. 110(2), pages 265-288, August.
    12. Mustapha Bouhtou & Stan van Hoesel & Anton F. van der Kraaij & Jean-Luc Lutton, 2007. "Tariff Optimization in Networks," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 458-469, August.
    13. Alizadeh, S.M. & Marcotte, P. & Savard, G., 2013. "Two-stage stochastic bilevel programming over a transportation network," Transportation Research Part B: Methodological, Elsevier, vol. 58(C), pages 92-105.
    14. Longsheng Sun & Mark H. Karwan & Changhyun Kwon, 2018. "Generalized Bounded Rationality and Robust Multicommodity Network Design," Operations Research, INFORMS, vol. 66(1), pages 42-57, 1-2.
    15. S A Gabriel & Y Shim & A J Conejo & S de la Torre & R García-Bertrand, 2010. "A Benders decomposition method for discretely-constrained mathematical programs with equilibrium constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(9), pages 1404-1419, September.
    16. Wang, Zhenjie & Zhang, Dezhi & Tavasszy, Lóránt & Fazi, Stefano, 2023. "Integrated multimodal freight service network design and pricing with a competing service integrator and heterogeneous shipper classes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    17. Fred E. Benth & Geir Dahl & Carlo Mannino, 2012. "Computing Optimal Recovery Policies for Financial Markets," Operations Research, INFORMS, vol. 60(6), pages 1373-1388, December.
    18. Marcotte, Patrice & Savard, Gilles & Zhu, Daoli, 2009. "Mathematical structure of a bilevel strategic pricing model," European Journal of Operational Research, Elsevier, vol. 193(2), pages 552-566, March.
    19. Gabriel, Steven A. & Leuthold, Florian U., 2010. "Solving discretely-constrained MPEC problems with applications in electric power markets," Energy Economics, Elsevier, vol. 32(1), pages 3-14, January.
    20. José Correa & Tobias Harks & Vincent J. C. Kreuzen & Jannik Matuschke, 2017. "Fare Evasion in Transit Networks," Operations Research, INFORMS, vol. 65(1), pages 165-183, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:54:y:2007:i:4:p:411-420. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.