On the Complexity of Tipping in Super-Modular Games

Abstract

The problem of finding the minimum tipping set in a super modular game is known to be NP-hard. Here, I derive an approximation algorithm to find a small tipping set in such a game. In the special case of the uniform game, the approximation provides the exact minimum tipping set. Interdependent security is a growing field. One model used for interdependent security is the airline security model. This model is used as an example for the approximation methods, and was the working model for many of the proofs and strategies developed to find tipping sets and their approximations. This algebraic approach, which makes use of group theory, is then evaluated for accuracy, It is then applied to a dynamic approach, using a simple learning function without the complete information often assumed.

This method links the non-greedy approximation to a version of SAT, and a type of influence graphs and the covering problem. The approximation fared well when finding the key players in a game, but struggled with cascades.