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. 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.
    2. 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.
    3. 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.
    4. Bramoulle, Yann & Kranton, Rachel, 2007. "Public goods in networks," Journal of Economic Theory, Elsevier, vol. 135(1), pages 478-494, July.
    5. 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.
    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. Ying Chen & Tom Lane & Stuart McDonald, 2023. "Endogenous Network Formation in Local Public Goods: An Experimental Analysis," Discussion Papers 2023-02, The Centre for Decision Research and Experimental Economics, School of Economics, University of Nottingham.
    7. Bayer, Péter & Herings, P. Jean-Jacques & Peeters, Ronald, 2021. "Farsighted manipulation and exploitation in networks," Journal of Economic Theory, Elsevier, vol. 196(C).
    8. Jadbabaie, Ali & Kakhbod, Ali, 2019. "Optimal contracting in networks," Journal of Economic Theory, Elsevier, vol. 183(C), pages 1094-1153.
    9. 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.
    10. Lionel Richefort, 2018. "Warm-glow giving in networks with multiple public goods," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(4), pages 1211-1238, November.
    11. 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.
    12. Dunia Lopez-Pintado, 2016. "Influence networks and public goods," UMASS Amherst Economics Working Papers 2016-12, University of Massachusetts Amherst, Department of Economics.
    13. Artem Sedakov, 2020. "Characteristic Function and Time Consistency for Two-Stage Games with Network Externalities," Mathematics, MDPI, vol. 8(1), pages 1-9, January.
    14. Acemoglu, Daron & Malekian, Azarakhsh & Ozdaglar, Asu, 2016. "Network security and contagion," Journal of Economic Theory, Elsevier, vol. 166(C), pages 536-585.
    15. Battigalli, Pierpaolo & Panebianco, Fabrizio & Pin, Paolo, 2023. "Learning and selfconfirming equilibria in network games," Journal of Economic Theory, Elsevier, vol. 212(C).
    16. Ghosh, Papiya & Kundu, Rajendra P., 2019. "Best-shot network games with continuous action space," Research in Economics, Elsevier, vol. 73(3), pages 225-234.
    17. 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.
    18. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    19. 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.
    20. 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.

    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.