Targeted intervention in random graphs
From MaRDI portal
Publication:2109964
DOI10.1007/978-3-030-57980-7_14zbMATH Open1506.91025arXiv2007.06445OpenAlexW3090291673MaRDI QIDQ2109964
Author name not available (Why is that?)
Publication date: 21 December 2022
Abstract: We consider a setting where individuals interact in a network, each choosing actions which optimize utility as a function of neighbors' actions. A central authority aiming to maximize social welfare at equilibrium can intervene by paying some cost to shift individual incentives, and the optimal intervention can be computed using the spectral decomposition of the graph, yet this is infeasible in practice if the adjacency matrix is unknown. In this paper, we study the question of designing intervention strategies for graphs where the adjacency matrix is unknown and is drawn from some distribution. For several commonly studied random graph models, we show that there is a single intervention, proportional to the first eigenvector of the expected adjacency matrix, which is near-optimal for almost all generated graphs when the budget is sufficiently large. We also provide several efficient sampling-based approaches for approximately recovering the first eigenvector when we do not know the distribution. On the whole, our analysis compares three categories of interventions: those which use no data about the network, those which use some data (such as distributional knowledge or queries to the graph), and those which are fully optimal. We evaluate these intervention strategies on synthetic and real-world network data, and our results suggest that analysis of random graph models can be useful for determining when certain heuristics may perform well in practice.
Full work available at URL: https://arxiv.org/abs/2007.06445
No records found.
No records found.
This page was built for publication: Targeted intervention in random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109964)
