A finite convergence algorithm for solving linear-quadratic network games with strategic complements and bounded strategies

Abstract

We propose a new algorithm for solving a class of linear-quadratic network games with strategic complements and bounded strategies. The algorithm is based on the sequential solution of linear systems of equations and we prove that it finds the exact Nash equilibrium of the game after a finite number of iterations. The new algorithm is then applied to a social network model of juvenile delinquency which has been investigated recently where we also consider random perturbations of some data. Experimental results show the efficiency of the algorithm in solving large scale problems.

Keywords:

• Network games
• Nash equilibrium
• key player
• social network

Acknowledgments

The authors wish to thank the three anonymous reviewers for their useful comments, remarks and suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The authors are members of the Gruppo Nazionale per l'Analisi Matematica, la Probabilità e le loro Applicazioni (GNAMPA – National Group for Mathematical Analysis, Probability and their Applications) of the Istituto Nazionale di Alta Matematica (INdAM – National Institute of Higher Mathematics). The research of F. Raciti was partially supported by the research project ‘Programma ricerca di ateneo UNICT 2020-22 linea 2-OMNIA’ of the University of Catania. This support is gratefully acknowledged.

Notes on contributors

M. Passacantando

M. Passacantando received the M.S. and Ph.D. degrees in Mathematics from the University of Pisa (Italy). He has been an Assistant Professor and then an Associate Professor of Operations Research at University of Pisa from 2002 to 2022. He is currently an Associate Professor of Operations Research (qualified for Full Professorship) with the Department of Business and Law, University of Milan-Bicocca. His research is mainly devoted to variational inequalities and equilibrium problems. In the last years, his work focused on game theoretic models applied to service provisioning problems in cloud and multicloud systems and infrastructure and spectrum sharing in mobile networks.

F. Raciti

F. Raciti earned his Ph.D. in Theoretical Physics from the University of Catania (Italy), where he has been an Assistant Professor and then an Associate Professor of Mathematical Analysis. He is currently an Associate Professor of Operations Research at the University of Catania and has received the National (Italian) Habilitation as a Full Professor of Operations Research. He has published research work in the field of variational inequalities, optimization, inverse problems, and stochastic equilibrium problems.