  We consider a simple and altruistic multiagent system in which the agents are
eager to perform a collective task but where their real engagement depends on
the willingness to perform the task of other influential agents. We model this
scenario by an influence game, a cooperative simple game in which a team (or
coalition) of players succeeds if it is able to convince enough agents to
participate in the task (to vote in favor of a decision). We take the linear
threshold model as the influence model. We show first the expressiveness of
influence games showing that they capture the class of simple games. Then we
characterize the computational complexity of various problems on influence
games, including measures (length and width), values (Shapley-Shubik and
Banzhaf) and properties (of teams and players). Finally, we analyze those
problems for some particular extremal cases, with respect to the propagation of
influence, showing tighter complexity characterizations.
