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

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. Manuela Goretti, 2005. "The Brazilian currency turmoil of 2002: a nonlinear analysis," International Journal of Finance & Economics, John Wiley & Sons, Ltd., vol. 10(4), pages 289-306.
    3. Winkler, Bernhard, 2000. "Which kind of transparency? On the need for clarity in monetary policy-making," Working Paper Series 0026, European Central Bank.
    4. Radu Vranceanu & Damien Besancenot & Delphine Dubart, 2014. "Can Rumors and Other Uninformative Messages Cause Illiquidity ?," CEPN Working Papers hal-00841167, HAL.
    5. Bervoets, Sebastian & Faure, Mathieu, 2020. "Convergence in games with continua of equilibria," Journal of Mathematical Economics, Elsevier, vol. 90(C), pages 25-30.
    6. Christian Hellwig, 2004. "Heterogeneous Information and the Benefits of Public Information Disclosures (October 2005)," UCLA Economics Online Papers 283, UCLA Department of Economics.
    7. Laura L. Veldkamp, 2006. "Information Markets and the Comovement of Asset Prices," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 73(3), pages 823-845.
    8. Antonio Cabrales & Rosemarie Nagel & Roc Armenter, 2007. "Equilibrium selection through incomplete information in coordination games: an experimental study," Experimental Economics, Springer;Economic Science Association, vol. 10(3), pages 221-234, September.
    9. 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.
    10. Bannier, Christina E., 2003. "Privacy or Publicity - Who Drives the Wheel?," CFS Working Paper Series 2003/29, Center for Financial Studies (CFS).
    11. George-Marios Angeletos & Chen Lian, 2018. "Forward Guidance without Common Knowledge," American Economic Review, American Economic Association, vol. 108(9), pages 2477-2512, September.
    12. 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.
    13. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    14. Hitoshi Matsushima & Shunya Noda, 2020. "Mechanism Design with Blockchain Enforcement," DSSR Discussion Papers 111, Graduate School of Economics and Management, Tohoku University.
    15. 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).
    16. 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.
    17. V. Bhaskar & Caroline Thomas, 2019. "The Culture of Overconfidence," American Economic Review: Insights, American Economic Association, vol. 1(1), pages 95-110, June.
    18. Itay Goldstein, 2005. "Strategic Complementarities and the Twin Crises," Economic Journal, Royal Economic Society, vol. 115(503), pages 368-390, April.
    19. 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.
    20. 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.

    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.