IDEAS home Printed from https://ideas.repec.org/a/spr/indpam/v53y2022i4d10.1007_s13226-022-00217-w.html
   My bibliography  Save this article

On independent cliques and linear complementarity problems

Author

Listed:
  • Karan N. Chadha

    (Stanford University)

  • Ankur A. Kulkarni

    (Indian Institute of Technology Bombay)

Abstract

In recent work (Pandit and Kulkarni [Discrete Applied Mathematics, 244 (2018), pp. 155–169]), the independence number of a graph was characterized as the maximum of the $$\ell _1$$ ℓ 1 norm of solutions of a Linear Complementarity Problem (LCP) defined suitably using parameters of the graph. Solutions of this LCP have another relation, namely, that they corresponded to Nash equilibria of a public goods game. Thus the maximum $$ \ell _1 $$ ℓ 1 norm has an important economic interpretation as the maximum total investment over all equilibria of this game. Motivated by this, we consider a perturbation of this LCP that corresponds to a public goods game with imperfect substitutability. We identify the combinatorial structures on the graph that correspond to the maximum $$\ell _1$$ ℓ 1 norm of solutions (equivalently, investment maximizing equilibria) of the new LCP. We show that these solutions correspond to “independent cliques" – collections of cliques such that no two vertices from two distinct cliques are adjacent. When the perturbation becomes null, these cliques collapse to singletons and we recover the earlier relation to maximum independent sets. Independent cliques have been studied before as a generalization of independent sets. Our work establishes an intricate connection between independent cliques, LCPs and public goods games.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:indpam:v:53:y:2022:i:4:d:10.1007_s13226-022-00217-w
    DOI: 10.1007/s13226-022-00217-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13226-022-00217-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13226-022-00217-w?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Yann Bramoull? & Rachel Kranton & Martin D'Amours, 2014. "Strategic Interaction and Networks," American Economic Review, American Economic Association, vol. 104(3), pages 898-930, March.
    2. Pandit, Parthe & Kulkarni, Ankur A., 2018. "Refinement of the equilibrium of public goods games over networks: Efficiency and effort of specialized equilibria," Journal of Mathematical Economics, Elsevier, vol. 79(C), pages 125-139.
    3. M. Seetharama Gowda & Jong-Shi Pang, 1992. "On Solution Stability of the Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 77-83, February.
    4. Jing Hu & John Mitchell & Jong-Shi Pang & Bin Yu, 2012. "On linear programs with linear complementarity constraints," Journal of Global Optimization, Springer, vol. 53(1), pages 29-51, May.
    5. 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. Chadha, Karan N. & Kulkarni, Ankur A., 2020. "Aggregate play and welfare in strategic interactions on networks," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 72-86.
    2. Shraddha Pathak & Ankur A. Kulkarni, 2022. "A Scalable Bayesian Persuasion Framework for Epidemic Containment on Heterogeneous Networks," Papers 2207.11578, arXiv.org.
    3. Allouch, Nizar, 2017. "The cost of segregation in (social) networks," Games and Economic Behavior, Elsevier, vol. 106(C), pages 329-342.
    4. Cabrales, Antonio & Calvó-Armengol, Antoni & Zenou, Yves, 2011. "Social interactions and spillovers," Games and Economic Behavior, Elsevier, vol. 72(2), pages 339-360, June.
    5. Chen, Ying-Ju & Zenou, Yves & Zhou, Junjie, 2022. "The impact of network topology and market structure on pricing," Journal of Economic Theory, Elsevier, vol. 204(C).
    6. Jadbabaie, Ali & Kakhbod, Ali, 2019. "Optimal contracting in networks," Journal of Economic Theory, Elsevier, vol. 183(C), pages 1094-1153.
    7. Bulat Sanditov & Saurabh Arora, 2016. "Social network and private provision of public goods," Journal of Evolutionary Economics, Springer, vol. 26(1), pages 195-218, March.
    8. Belhaj, Mohamed & Bramoullé, Yann & Deroïan, Frédéric, 2014. "Network games under strategic complementarities," Games and Economic Behavior, Elsevier, vol. 88(C), pages 310-319.
    9. Bayer, Péter & Herings, P. Jean-Jacques & Peeters, Ronald, 2021. "Farsighted manipulation and exploitation in networks," Journal of Economic Theory, Elsevier, vol. 196(C).
    10. Acemoglu, Daron & Malekian, Azarakhsh & Ozdaglar, Asu, 2016. "Network security and contagion," Journal of Economic Theory, Elsevier, vol. 166(C), pages 536-585.
    11. Battigalli, Pierpaolo & Panebianco, Fabrizio & Pin, Paolo, 2023. "Learning and selfconfirming equilibria in network games," Journal of Economic Theory, Elsevier, vol. 212(C).
    12. Zhang, Yang & Du, Xiaomin, 2017. "Network effects on strategic interactions: A laboratory approach," Journal of Economic Behavior & Organization, Elsevier, vol. 143(C), pages 133-146.
    13. Boris van Leeuwen & Theo Offerman & Arthur Schram, 2020. "Competition for Status Creates Superstars: an Experiment on Public Good Provision and Network Formation," Journal of the European Economic Association, European Economic Association, vol. 18(2), pages 666-707.
    14. Bulat Sanditov & Saurabh Arora, 2016. "Social network and private provision of public goods," Journal of Evolutionary Economics, Springer, vol. 26(1), pages 195-218, March.
    15. Péter Bayer & György Kozics & Nóra Gabriella Szőke, 2020. "Best-Response Dynamics in Directed Network Games," CEU Working Papers 2020_1, Department of Economics, Central European University.
    16. Allouch, Nizar, 2015. "On the private provision of public goods on networks," Journal of Economic Theory, Elsevier, vol. 157(C), pages 527-552.
    17. Tatsuhiro Shichijo & Emiko Fukuda, 2019. "A dynamic game analysis of Internet services with network externalities," Theory and Decision, Springer, vol. 86(3), pages 361-388, May.
    18. Topa, Giorgio & Zenou, Yves, 2015. "Neighborhood and Network Effects," Handbook of Regional and Urban Economics, in: Gilles Duranton & J. V. Henderson & William C. Strange (ed.), Handbook of Regional and Urban Economics, edition 1, volume 5, chapter 0, pages 561-624, Elsevier.
    19. Yang Sun & Wei Zhao & Junjie Zhou, 2021. "Structural Interventions in Networks," Papers 2101.12420, arXiv.org, revised Feb 2021.
    20. Nizar Allouch & Maia King, 2019. "Constrained public goods in networks," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 21(5), pages 895-902, October.

    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:indpam:v:53:y:2022:i:4:d:10.1007_s13226-022-00217-w. 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.