IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v56y2013i4p1325-1334.html

A cross-monotonic cost-sharing scheme for the concave facility location game

Author

Listed:
  • Gaidi Li

  • Yu Li

  • Jia Shu

  • Dachuan Xu

Abstract

In this paper, we present a cost-sharing scheme for the concave facility location game by exploring the concavity structure. We show that it is cross-monotonic and competitive, and recovers 1/3 fraction of the total cost. Copyright Springer Science+Business Media, LLC. 2013

Suggested Citation

  • Gaidi Li & Yu Li & Jia Shu & Dachuan Xu, 2013. "A cross-monotonic cost-sharing scheme for the concave facility location game," Journal of Global Optimization, Springer, vol. 56(4), pages 1325-1334, August.
    • Handle: RePEc:spr:jglopt:v:56:y:2013:i:4:p:1325-1334
    DOI: 10.1007/s10898-012-9852-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-012-9852-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-012-9852-0?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    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. Fengmin Wang & Dachuan Xu & Chenchen Wu, 2016. "Combinatorial approximation algorithms for the robust facility location problem with penalties," Journal of Global Optimization, Springer, vol. 64(3), pages 483-496, March.
    2. Lindong Liu & Xiangtong Qi & Zhou Xu, 2016. "Computing Near-Optimal Stable Cost Allocations for Cooperative Games by Lagrangian Relaxation," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 687-702, November.

    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. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    2. Haris Aziz & Sujit Gujar & Manisha Padala & Mashbat Suzuki & Jeremy Vollen, 2022. "Coordinating Monetary Contributions in Participatory Budgeting," Papers 2206.05966, arXiv.org, revised Feb 2023.
    3. Alfredo Valencia-Toledo & Juan Vidal-Puga, 2020. "Reassignment-proof rules for land rental problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 173-193, March.
    4. Balireddi, Sindhura & Uhan, Nelson A., 2012. "Cost-sharing mechanisms for scheduling under general demand settings," European Journal of Operational Research, Elsevier, vol. 217(2), pages 270-277.
    5. Hervé Moulin & Yves Sprumont, 2007. "Fair allocation of production externalities : recent results," Revue d'économie politique, Dalloz, vol. 117(1), pages 7-36.
    6. Mutuswami, Suresh, 2005. "Strategyproofness, Non-Bossiness and Group Strategyproofness in a cost sharing model," Economics Letters, Elsevier, vol. 89(1), pages 83-88, October.
    7. Hiroki Shinozaki, 2025. "Characterizing group strategy-proof rules in the object allocation problem with money," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 64(4), pages 721-764, June.
    8. Hagen, Martin, 2023. "Collusion-proof mechanisms for multi-unit procurement," Games and Economic Behavior, Elsevier, vol. 138(C), pages 281-298.
    9. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    10. Trudeau, Christian & Rosenthal, Edward C., 2026. "The pipeline externalities problem," Journal of Mathematical Economics, Elsevier, vol. 122(C).
    11. You, Jung S., 2015. "Optimal VCG mechanisms to assign multiple bads," Games and Economic Behavior, Elsevier, vol. 92(C), pages 166-190.
    12. repec:aen:journl:ej41-1-lambin is not listed on IDEAS
    13. Anil Chorppath & Tansu Alpcan & Holger Boche, 2015. "Adversarial Behavior in Network Games," Dynamic Games and Applications, Springer, vol. 5(1), pages 26-64, March.
    14. Valencia-Toledo, Alfredo & Vidal-Puga, Juan, 2015. "Non-manipulable rules for land rental problems," MPRA Paper 67334, University Library of Munich, Germany.
    15. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2014. "Egalitarian equivalence and strategyproofness in the queueing problem," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 425-442, June.
    16. Ragavendran Gopalakrishnan & Jason R. Marden & Adam Wierman, 2014. "Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1252-1296, November.
    17. Ruben Juarez & Rajnish Kumar, 2013. "Implementing efficient graphs in connection networks," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(2), pages 359-403, October.
    18. Marden, Jason R. & Shamma, Jeff S., 2015. "Game Theory and Distributed Control****Supported AFOSR/MURI projects #FA9550-09-1-0538 and #FA9530-12-1-0359 and ONR projects #N00014-09-1-0751 and #N0014-12-1-0643," Handbook of Game Theory with Economic Applications,, Elsevier.
    19. Mitra, Manipushpak & Mutuswami, Suresh, 2011. "Group strategyproofness in queueing models," Games and Economic Behavior, Elsevier, vol. 72(1), pages 242-254, May.
    20. Dobzinski, Shahar & Mehta, Aranyak & Roughgarden, Tim & Sundararajan, Mukund, 2018. "Is Shapley cost sharing optimal?," Games and Economic Behavior, Elsevier, vol. 108(C), pages 130-138.
    21. Shinji Ohseto, 2010. "Serial Mechanisms For The Provision Of An Excludable Public Good," The Japanese Economic Review, Japanese Economic Association, vol. 61(4), pages 507-516, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    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:spr:jglopt:v:56:y:2013:i:4:p:1325-1334. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.