We introduce a new approach to the study of influence in strategic settings
where the action of an individual depends on that of others in a
network-structured way. We propose \emph{influence games} as a
\emph{game-theoretic} model of the behavior of a large but finite networked
population. Influence games allow \emph{both} positive and negative
\emph{influence factors}, permitting reversals in behavioral choices. We
embrace \emph{pure-strategy Nash equilibrium (PSNE)}, an important solution
concept in non-cooperative game theory, to formally define the \emph{stable
outcomes} of an influence game and to predict potential outcomes without
explicitly considering intricate dynamics. We address an important problem in
network influence, the identification of the \emph{most influential
individuals}, and approach it algorithmically using PSNE computation.
\emph{Computationally}, we provide (a) complexity characterizations of various
problems on influence games; (b) efficient algorithms for several special cases
and heuristics for hard cases; and (c) approximation algorithms, with provable
guarantees, for the problem of identifying the most influential individuals.
\emph{Experimentally}, we evaluate our approach using both synthetic influence
games as well as several real-world settings of general interest, each
corresponding to a separate branch of the U.S. Government.
\emph{Mathematically,} we connect influence games to important game-theoretic
models: \emph{potential and polymatrix games}.

本文介绍了一种新的方法来研究策略环境中的影响力问题，提出了 “影响力博弈” 作为大型但有限的网络人口行为的博弈理论模型，通过计算纯策略 Nash 均衡来确定影响力游戏的稳定结果并预测潜在结果，提供了各种影响力博弈问题的复杂性特征、高效算法和近似算法，并通过实验和数学建模将影响力博弈与潜力游戏和多元游戏等关键博弈理论模型相连接。