IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v42y2017i2p377-388.html
   My bibliography  Save this article

A Sublogarithmic Approximation for Tollbooth Pricing on Trees

Author

Listed:
  • Iftah Gamzu

    (Yahoo! Research, Haifa, Israel)

  • Danny Segev

    (Department of Statistics, University of Haifa, Haifa 31905, Israel)

Abstract

An instance of the tollbooth problem consists of an undirected network and a collection of single-minded customers, each of which is interested in purchasing a fixed path subject to an individual budget constraint. The objective is to assign a per-unit price to each edge in a way that maximizes the collective revenue obtained from all customers. The revenue generated by any customer is equal to the overall price of the edges in her desired path, when this cost falls within her budget; otherwise, that customer will not purchase any edge. Our main result is a deterministic algorithm for the tollbooth problem on trees whose approximation ratio is O (log m /log log m ), where m denotes the number of edges in the underlying graph. This finding improves on the currently best performance guarantees for trees, and up until recently, also on the best ratio for paths (commonly known as the highway problem). An additional interesting consequence is a computational separation between tollbooth pricing on trees and the original prototype problem of single-minded unlimited supply pricing, under a plausible hardness hypothesis.

Suggested Citation

  • Iftah Gamzu & Danny Segev, 2017. "A Sublogarithmic Approximation for Tollbooth Pricing on Trees," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 377-388, May.
    • Handle: RePEc:inm:ormoor:v:42:y:2017:i:2:p:377-388
    DOI: 10.1287/moor.2016.0803
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2016.0803
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2016.0803?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. Grigoriev, A. & van Loon, J. & Sviridenko, M. & Uetz, M.J. & Vredeveld, T., 2008. "Optimal bundle pricing with monotonicity constraint," Research Memorandum 015, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Aggarwal, Gagan & Fiat, Amos & Goldberg, Andrew V. & Hartline, Jason D. & Immorlica, Nicole & Sudan, Madhu, 2011. "Derandomization of auctions," Games and Economic Behavior, Elsevier, vol. 72(1), pages 1-11, May.
    Full references (including those not matched with items on IDEAS)

    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. & Hiller, B. & Marban, S. & Vredeveld, T. & van der Zwaan, G.R.J., 2010. "Dynamic pricing problems with elastic demand," Research Memorandum 053, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).

    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:inm:ormoor:v:42:y:2017:i:2:p:377-388. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.