IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2003.07106.html

Exact capacitated domination: on the computational complexity of uniqueness

Author

Listed:
  • Gregory Gutin
  • Philip R Neary
  • Anders Yeo

Abstract

In this paper we consider a local service-requirement assignment problem named exact capacitated domination from an algorithmic point of view. This problem aims to find a solution (a Nash equilibrium) to a game-theoretic model of public good provision. In the problem we are given a capacitated graph, a graph with a parameter defined on each vertex that is interpreted as the capacity of that vertex. The objective is to find a DP-Nash subgraph: a spanning bipartite subgraph with partite sets D and P, called the D-set and P-set respectively, such that no vertex in P is isolated and that each vertex in D is adjacent to a number of vertices equal to its capacity. We show that whether a capacitated graph has a unique DP-Nash subgraph can be decided in polynomial time. However, we also show that the nearby problem of deciding whether a capacitated graph has a unique D-set is co-NP-complete.

Suggested Citation

  • Gregory Gutin & Philip R Neary & Anders Yeo, 2020. "Exact capacitated domination: on the computational complexity of uniqueness," Papers 2003.07106, arXiv.org, revised Jul 2022.
    • Handle: RePEc:arx:papers:2003.07106
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Morris, Stephen & Shin, Hyun Song, 1998. "Unique Equilibrium in a Model of Self-Fulfilling Currency Attacks," American Economic Review, American Economic Association, vol. 88(3), pages 587-597, June.
    2. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    3. Stefanie Gerke & Gregory Gutin & Sung-Ha Hwang & Philip Neary, 2019. "Public goods in networks with constraints on sharing," Papers 1905.01693, arXiv.org, revised Jun 2023.
    4. Bramoulle, Yann & Kranton, Rachel, 2007. "Public goods in networks," Journal of Economic Theory, Elsevier, vol. 135(1), pages 478-494, July.
    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. Peter Coles & John Cawley & Phillip B. Levine & Muriel Niederle & Alvin E. Roth & John J. Siegfried, 2010. "The Job Market for New Economists: A Market Design Perspective," Journal of Economic Perspectives, American Economic Association, vol. 24(4), pages 187-206, Fall.
    2. repec:hal:cepnwp:hal-00841167 is not listed on IDEAS
    3. Christian Hellwig, 2004. "Heterogeneous Information and the Benefits of Public Information Disclosures (October 2005)," UCLA Economics Online Papers 283, UCLA Department of Economics.
    4. Muriel Niederle & Alvin E. Roth, 2009. "The Effects of a Centralized Clearinghouse on Job Placement, Wages, and Hiring Practices," NBER Chapters, in: Studies of Labor Market Intermediation, pages 235-271, National Bureau of Economic Research, Inc.
    5. Bannier, Christina E., 2003. "Privacy or Publicity - Who Drives the Wheel?," CFS Working Paper Series 2003/29, Center for Financial Studies (CFS).
    6. Karan N. Chadha & Ankur A. Kulkarni, 2022. "On independent cliques and linear complementarity problems," Indian Journal of Pure and Applied Mathematics, Springer, vol. 53(4), pages 1036-1057, December.
    7. Hitoshi Matsushima & Shunya Noda, 2020. "Mechanism Design with Blockchain Enforcement," DSSR Discussion Papers 111, Graduate School of Economics and Management, Tohoku University.
    8. Carvalho, José-Raimundo & Magnac, Thierry & Xiong, Qizhou, 2016. "College Choice and the Selection of Mechanisms: A Structural Empirical Analysis," IWH Discussion Papers 3/2016, Halle Institute for Economic Research (IWH).
    9. Arthur Schram & Boris Van Leeuwen & Theo Offerman, 2013. "Superstars Need Social Benefits: An Experiment on Network Formation," Working Papers 1306, Departament Empresa, Universitat Autònoma de Barcelona, revised Jul 2013.
    10. Itay Goldstein, 2005. "Strategic Complementarities and the Twin Crises," Economic Journal, Royal Economic Society, vol. 115(503), pages 368-390, April.
    11. Itai Ashlagi & Flip Klijn, 2012. "Manipulability in matching markets: conflict and coincidence of interests," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(1), pages 23-33, June.
    12. Georgy Lukyanov & David Li, 2025. "Belief Diversity and Cooperation," Papers 2509.08851, arXiv.org.
    13. Morris, Stephen & Shin, Hyun Song, 1999. "Risk Management with Interdependent Choice," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 15(3), pages 52-62, Autumn.
    14. Abraham Aldama & Daniel Draganoff & Gantavya Pahwa, 2024. "An experiment in the role of identity in fostering coordination," Journal of the Economic Science Association, Springer;Economic Science Association, vol. 10(2), pages 294-309, December.
    15. Ennis, Huberto M. & Keister, Todd, 2005. "Government policy and the probability of coordination failures," European Economic Review, Elsevier, vol. 49(4), pages 939-973, May.
    16. Chanelle Duley & Prasanna Gai, 2020. "When the penny doesn't drop - Macroeconomic tail risk and currency crises," National Institute of Economic and Social Research (NIESR) Discussion Papers 520, National Institute of Economic and Social Research.
    17. Goldstein, Itay & Jiang, Hao & Ng, David T., 2017. "Investor flows and fragility in corporate bond funds," Journal of Financial Economics, Elsevier, vol. 126(3), pages 592-613.
    18. Bo Cowgill & Jonathan M. V. Davis & B. Pablo Montagnes & Patryk Perkowski, 2025. "Stable Matching on the Job? Theory and Evidence on Internal Talent Markets," Management Science, INFORMS, vol. 71(3), pages 2508-2526, March.
    19. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    20. , & ,, 2013. "Selection-free predictions in global games with endogenous information and multiple equilibria," Theoretical Economics, Econometric Society, vol. 8(3), September.
    21. Luisa Corrado & Marcus Miller & Lei Zhang, 2007. "Bulls, bears and excess volatility: can currency intervention help?," International Journal of Finance & Economics, John Wiley & Sons, Ltd., vol. 12(2), pages 261-272.

    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:2003.07106. 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.