IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1911.09813.html
   My bibliography  Save this paper

Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives

Author

Listed:
  • Haris Aziz
  • Hau Chan
  • Barton E. Lee
  • Bo Li
  • Toby Walsh

Abstract

We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, we prove that the corresponding optimization problem, where the goal is to locate facilities to minimize either the total cost to all agents or the maximum cost of any agent is NP-hard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilities have identical capacities. We then consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that several natural mechanisms studied in the uncapacitated setting either lose strategyproofness or a bound on the solution quality for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.

Suggested Citation

  • Haris Aziz & Hau Chan & Barton E. Lee & Bo Li & Toby Walsh, 2019. "Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives," Papers 1911.09813, arXiv.org.
    • Handle: RePEc:arx:papers:1911.09813
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1911.09813
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Aardal, Karen & van den Berg, Pieter L. & Gijswijt, Dion & Li, Shanfei, 2015. "Approximation algorithms for hard capacitated k-facility location problems," European Journal of Operational Research, Elsevier, vol. 242(2), pages 358-368.
    2. H. Moulin, 1980. "On strategy-proofness and single peakedness," Public Choice, Springer, vol. 35(4), pages 437-455, January.
    3. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    4. N. Megiddo, 1979. "An O(n log2 n) Algorithm for the kth Longest Path in a Tree with Applications to Location Problems," Discussion Papers 379, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    5. Nimrod Megiddo, 1981. "The Maximum Coverage Location Problem," Discussion Papers 490, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    6. Eun Heo, 2013. "Strategy-proof rules for two public goods: double median rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(4), pages 895-922, October.
    7. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    8. Eiichi Miyagawa, 2001. "Locating libraries on a street," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(3), pages 527-541.
    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. Haris Aziz & Alexander Lam & Barton E. Lee & Toby Walsh, 2021. "Strategyproof and Proportionally Fair Facility Location," Papers 2111.01566, arXiv.org, revised Nov 2023.

    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. Aziz, Haris & Chan, Hau & Lee, Barton E. & Parkes, David C., 2020. "The capacity constrained facility location problem," Games and Economic Behavior, Elsevier, vol. 124(C), pages 478-490.
    2. Carmelo Rodríguez-à lvarez, 2017. "On single-peakedness and strategy-proofness: ties between adjacent alternatives," Economics Bulletin, AccessEcon, vol. 37(3), pages 1966-1974.
    3. Alcalde-Unzu, Jorge & Vorsatz, Marc, 2018. "Strategy-proof location of public facilities," Games and Economic Behavior, Elsevier, vol. 112(C), pages 21-48.
    4. Bettina Klaus & Panos Protopapas, 2020. "On strategy-proofness and single-peakedness: median-voting over intervals," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(4), pages 1059-1080, December.
    5. Haris Aziz & Alexander Lam & Barton E. Lee & Toby Walsh, 2021. "Strategyproof and Proportionally Fair Facility Location," Papers 2111.01566, arXiv.org, revised Nov 2023.
    6. Gordon, Sidartha, 2007. "Public decisions: Solidarity and the status quo," Games and Economic Behavior, Elsevier, vol. 61(2), pages 225-241, November.
    7. Haris Aziz & Alexander Lam & Mashbat Suzuki & Toby Walsh, 2022. "Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism," Papers 2205.14798, arXiv.org, revised Jun 2022.
    8. Protopapas, Panos, 2018. "On strategy-proofness and single-peakedness: median-voting over intervals," MPRA Paper 83939, University Library of Munich, Germany.
    9. James Schummer, 1999. "Almost-dominant Strategy Implementation," Discussion Papers 1278, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    10. Souvik Roy & Soumyarup Sadhukhan, 2019. "A characterization of random min–max domains and its applications," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(4), pages 887-906, November.
    11. Freixas, Josep & Parker, Cameron, 2015. "Manipulation in games with multiple levels of output," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 144-151.
    12. Roy, Souvik & Storcken, Ton, 2019. "A characterization of possibility domains in strategic voting," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 46-55.
    13. Michel Breton & Vera Zaporozhets, 2009. "On the equivalence of coalitional and individual strategy-proofness properties," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 33(2), pages 287-309, August.
    14. Arribillaga, R. Pablo & Bonifacio, Agustín G., 2024. "Obvious manipulations of tops-only voting rules," Games and Economic Behavior, Elsevier, vol. 143(C), pages 12-24.
    15. M. Sanver, 2009. "Strategy-proofness of the plurality rule over restricted domains," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 39(3), pages 461-471, June.
    16. Sanver, M. Remzi, 2008. "Nash implementability of the plurality rule over restricted domains," Economics Letters, Elsevier, vol. 99(2), pages 298-300, May.
    17. Barberà, Salvador & Berga, Dolors & Moreno, Bernardo, 2010. "Individual versus group strategy-proofness: When do they coincide?," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1648-1674, September.
    18. Shurojit Chatterji & Arunava Sen, 2011. "Tops-only domains," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 46(2), pages 255-282, February.
    19. Shin Sato, 2012. "On strategy-proof social choice under categorization," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(3), pages 455-471, March.
    20. Alexander Reffgen, 2011. "Generalizing the Gibbard–Satterthwaite theorem: partial preferences, the degree of manipulation, and multi-valuedness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 37(1), pages 39-59, June.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:1911.09813. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.