An Approximation Algorithm for Computing a Tipping Set in Super Modular Games for Interdependent Security

The problem of finding the minimal tipping set in a super modular game is known to be NP-hard. In this paper, we derive an approximation algorithm to find a minimal tipping set. In the special case of the uniform game, the approximation provides the exact result.