Budget balance or voluntary participation? Incentivizing investments in interdependent security games

In a system of interdependent users, all entities are affected by the security decisions of one another. These users benefit from the improved health of the system when their neighbors invest in security measures; an effect known as positive externality. The externality of these decisions make security a public good, the optimal provision of which in a system of self-interested users requires regulation/incentives through an external mechanism. In this paper we first show that due to the non-excludable nature of security, no mechanism can achieve social optimality and ensure voluntary participation, while maintaining a balanced budget, for all instances of a security game. We then compare two incentive mechanisms in this context for improving security investment among users, namely the Pivotal mechanism and the Externality mechanism. We show that even though both mechanisms incentivize socially optimal investments, they differ in terms of budget requirements and participation. The Pivotal mechanism guarantees users´ participation; however, although (weakly) budget balanced in many game environments, it runs a budget deficit in security games. The Externality mechanism on the other hand is a budget balanced mechanism, but fails to incentivize voluntary participation. We further study the effects of the information available to the mechanism designer on the budget deficit of the Pivotal mechanism.