On independent cliques and linear complementarity problems

Karan N. Chadha () and Ankur A. Kulkarni ()
Additional contact information
Karan N. Chadha: Stanford University
Ankur A. Kulkarni: Indian Institute of Technology Bombay

Indian Journal of Pure and Applied Mathematics, 2022, vol. 53, issue 4, 1036-1057

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

Keywords: Linear Complementarity Problems; Independent Sets; Dominating Sets; Cliques (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13226-022-00217-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:indpam:v:53:y:2022:i:4:d:10.1007_s13226-022-00217-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/13226

DOI: 10.1007/s13226-022-00217-w

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().