Abstract
We study a network formation game where agents
receive benefits by forming connections to other
agents but also incur both direct and indirect costs
from the formed connections. Specifically, once the
agents have purchased their connections, an attack
starts at a randomly chosen vertex in the network
and spreads according to the independent cascade
model with a fixed probability, destroying any infected agents. The utility or welfare of an agent
in our game is defined to be the expected size of
the agent’s connected component post-attack minus
her expenditure in forming connections. Our goal
is to understand the properties of the equilibrium
networks formed in this game. Our first result concerns the edge density of equilibrium networks. A
network connection increases both the likelihood of
remaining connected to other agents after an attack
as well the likelihood of getting infected by a cascading spread of infection. We show that the latter
concern primarily prevails and any equilibrium network in our game contains only O(n log n) edges
where n denotes the number of agents. On the other
hand, there are equilibrium networks that contain
?(n) edges showing that our edge density bound
is tight up to a logarithmic factor. Our second result shows that the presence of attack and its spread
through a cascade does not significantly lower social welfare as long as the network is not too dense.
We show that any non-trivial equilibrium network
with O(n) edges has ?(n2) social welfare, asymptotically similar to the social welfare guarantee in
the game without any attacks