Optimal Seeding in Large-Scale Super-Modular Network Games
(2024) In IEEE Control Systems Letters 8. p.1811-1816- Abstract
We study optimal seeding problems for binary super-modular network games. The system planner's objective is to design a minimal cost seeding guaranteeing that at least a predefined fraction of the players adopt a certain action in every Nash equilibrium. Since the problem is known to be NP-hard and its exact solution would require full knowledge of the network structure, we focus on approximate solutions for large-scale networks with given statistics. In particular, we build on a local mean-field approximation of the linear threshold dynamics that is known to hold true on large-scale locally tree-like random networks. We first reduce the optimal intervention design problem to a linear program with an infinite set of constraints. We then... (More)
We study optimal seeding problems for binary super-modular network games. The system planner's objective is to design a minimal cost seeding guaranteeing that at least a predefined fraction of the players adopt a certain action in every Nash equilibrium. Since the problem is known to be NP-hard and its exact solution would require full knowledge of the network structure, we focus on approximate solutions for large-scale networks with given statistics. In particular, we build on a local mean-field approximation of the linear threshold dynamics that is known to hold true on large-scale locally tree-like random networks. We first reduce the optimal intervention design problem to a linear program with an infinite set of constraints. We then show how to approximate the solution of the latter by standard linear programs with finitely many constraints. Our solutions are then numerically validated.
(Less)
- author
- Messina, Sebastiano ; Cianfanelli, Leonardo ; Como, Giacomo LU and Fagnani, Fabio
- organization
- publishing date
- 2024
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- linear threshold dynamics, optimal seeding, Super-modular network games
- in
- IEEE Control Systems Letters
- volume
- 8
- pages
- 6 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- external identifiers
-
- scopus:85197077307
- ISSN
- 2475-1456
- DOI
- 10.1109/LCSYS.2024.3418308
- language
- English
- LU publication?
- yes
- id
- 1bd8dcf8-1dc8-401f-979c-fe495cd78c16
- date added to LUP
- 2024-11-28 14:53:30
- date last changed
- 2025-04-04 15:08:43
@article{1bd8dcf8-1dc8-401f-979c-fe495cd78c16,
abstract = {{<p>We study optimal seeding problems for binary super-modular network games. The system planner's objective is to design a minimal cost seeding guaranteeing that at least a predefined fraction of the players adopt a certain action in every Nash equilibrium. Since the problem is known to be NP-hard and its exact solution would require full knowledge of the network structure, we focus on approximate solutions for large-scale networks with given statistics. In particular, we build on a local mean-field approximation of the linear threshold dynamics that is known to hold true on large-scale locally tree-like random networks. We first reduce the optimal intervention design problem to a linear program with an infinite set of constraints. We then show how to approximate the solution of the latter by standard linear programs with finitely many constraints. Our solutions are then numerically validated.</p>}},
author = {{Messina, Sebastiano and Cianfanelli, Leonardo and Como, Giacomo and Fagnani, Fabio}},
issn = {{2475-1456}},
keywords = {{linear threshold dynamics; optimal seeding; Super-modular network games}},
language = {{eng}},
pages = {{1811--1816}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
series = {{IEEE Control Systems Letters}},
title = {{Optimal Seeding in Large-Scale Super-Modular Network Games}},
url = {{http://dx.doi.org/10.1109/LCSYS.2024.3418308}},
doi = {{10.1109/LCSYS.2024.3418308}},
volume = {{8}},
year = {{2024}},
}