Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Optimal Targeting in Super-Modular Games

Como, Giacomo LU ; Durand, Stephane and Fagnani, Fabio (2022) In IEEE Transactions on Automatic Control 67(12). p.6366-6380
Abstract
We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm for its solution with provable probabilistic convergence properties. We discuss in detail the special case of network coordination games and its relation with the graph-theoretic notion of cohesiveness.... (More)
We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm for its solution with provable probabilistic convergence properties. We discuss in detail the special case of network coordination games and its relation with the graph-theoretic notion of cohesiveness. Finally, through numerical simulations we compare the efficacy of our approach with respect to naive heuristics based on classical network centrality measures. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IEEE Transactions on Automatic Control
volume
67
issue
12
pages
6366 - 6380
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85145256025
ISSN
0018-9286
DOI
10.1109/TAC.2021.3129733
project
Dynamics of Complex Socio-Technological Network Systems
language
English
LU publication?
yes
id
f09f1f7e-8356-4a8c-ac6b-15103f6c3744
date added to LUP
2022-02-14 17:35:32
date last changed
2023-01-16 16:40:59
@article{f09f1f7e-8356-4a8c-ac6b-15103f6c3744,
  abstract     = {{We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm for its solution with provable probabilistic convergence properties. We discuss in detail the special case of network coordination games and its relation with the graph-theoretic notion of cohesiveness. Finally, through numerical simulations we compare the efficacy of our approach with respect to naive heuristics based on classical network centrality measures.}},
  author       = {{Como, Giacomo and Durand, Stephane and Fagnani, Fabio}},
  issn         = {{0018-9286}},
  language     = {{eng}},
  number       = {{12}},
  pages        = {{6366--6380}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Automatic Control}},
  title        = {{Optimal Targeting in Super-Modular Games}},
  url          = {{http://dx.doi.org/10.1109/TAC.2021.3129733}},
  doi          = {{10.1109/TAC.2021.3129733}},
  volume       = {{67}},
  year         = {{2022}},
}