IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v214y2011i2p317-330.html
   My bibliography  Save this article

A cooperative location game based on the 1-center location problem

Author

Listed:
  • Puerto, Justo
  • Tamir, Arie
  • Perea, Federico

Abstract

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG). We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the lp metric spaces defined over .

Suggested Citation

  • Puerto, Justo & Tamir, Arie & Perea, Federico, 2011. "A cooperative location game based on the 1-center location problem," European Journal of Operational Research, Elsevier, vol. 214(2), pages 317-330, October.
    • Handle: RePEc:eee:ejores:v:214:y:2011:i:2:p:317-330
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171100364X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nimrod Megiddo, 1978. "Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree," Mathematics of Operations Research, INFORMS, vol. 3(3), pages 189-196, August.
    2. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    3. G. Y. Handler, 1973. "Minimax Location of a Facility in an Undirected Tree Graph," Transportation Science, INFORMS, vol. 7(3), pages 287-293, August.
    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. 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.
    2. Lindong Liu & Yuqian Zhou & Zikang Li, 2022. "Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(1), pages 81-99, 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. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
    2. Ichiro Nishizaki & Tomohiro Hayashida & Yuki Shintomi, 2016. "A core-allocation for a network restricted linear production game," Annals of Operations Research, Springer, vol. 238(1), pages 389-410, March.
    3. Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
    4. Ichiro Nishizaki & Tomohiro Hayashida & Shinya Sekizaki & Kojiro Furumi, 2023. "A two-stage linear production planning model with partial cooperation under stochastic demands," Annals of Operations Research, Springer, vol. 320(1), pages 293-324, January.
    5. Csóka, Péter & Illés, Ferenc & Solymosi, Tamás, 2022. "On the Shapley value of liability games," European Journal of Operational Research, Elsevier, vol. 300(1), pages 378-386.
    6. R. B. Bapat & S. K. Neogy, 2016. "On a quadratic programming problem involving distances in trees," Annals of Operations Research, Springer, vol. 243(1), pages 365-373, August.
    7. Amitai Armon & Iftah Gamzu & Danny Segev, 2014. "Mobile facility location: combinatorial filtering via weighted occupancy," Journal of Combinatorial Optimization, Springer, vol. 28(2), pages 358-375, August.
    8. Zvi Drezner & G. O. Wesolowsky, 1991. "Facility location when demand is time dependent," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 763-777, October.
    9. Balaji Gopalakrishnan & Seunghyun Kong & Earl Barnes & Ellis Johnson & Joel Sokol, 2011. "A least-squares minimum-cost network flow algorithm," Annals of Operations Research, Springer, vol. 186(1), pages 119-140, June.
    10. Noltemeier, H. & Spoerhase, J. & Wirth, H.-C., 2007. "Multiple voting location and single voting location on trees," European Journal of Operational Research, Elsevier, vol. 181(2), pages 654-667, September.
    11. Xiaotie Deng & Toshihide Ibaraki & Hiroshi Nagamochi, 1999. "Algorithmic Aspects of the Core of Combinatorial Optimization Games," Mathematics of Operations Research, INFORMS, vol. 24(3), pages 751-766, August.
    12. Clemens Heuberger, 2004. "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 329-361, September.
    13. Chunsong Bai & Jun Du, 2024. "The Constrained 2-Maxian Problem on Cycles," Mathematics, MDPI, vol. 12(6), pages 1-9, March.
    14. Bergantinos, Gustavo & Vidal-Puga, Juan J., 2007. "A fair rule in minimum cost spanning tree problems," Journal of Economic Theory, Elsevier, vol. 137(1), pages 326-352, November.
    15. Amitabh Basu & Jesús A. De Loera & Mark Junod, 2014. "On Chubanov's Method for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 336-350, May.
    16. Hougaard, Jens Leth & Tvede, Mich, 2015. "Minimum cost connection networks: Truth-telling and implementation," Journal of Economic Theory, Elsevier, vol. 157(C), pages 76-99.
    17. Ichiro Nishizaki & Tomohiro Hayashida & Shinya Sekizaki & Kenta Tanaka, 2023. "Averaged dual solution for linear production games and its characterization," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(2), pages 523-555, June.
    18. O Berman & Z Drezner, 2003. "A probabilistic one-centre location problem on a network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 871-877, August.
    19. Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    20. Daniel Granot & Jeroen Kuipers & Sunil Chopra, 2002. "Cost Allocation for a Tree Network with Heterogeneous Customers," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 647-661, November.

    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:eee:ejores:v:214:y:2011:i:2:p:317-330. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.