Abstract
Traditional models of social influence often treat behavior spread as a passive contagion. This paper introduces Influence Games, a game-theoretic framework where individuals are modeled as strategic agents seeking stable states, or Pure-Strategy Nash Equilibria (PSNE). By treating influence as a strategic interaction rather than a simple diffusion process, we can more accurately identify the "most influential" nodes—those capable of driving a network toward a unique, stable outcome. We provide efficient algorithms for finding equilibria and demonstrate the model's effectiveness on both synthetic networks and real-world US Senate voting data.
Introduction
Most existing research on social influence relies on diffusion models, such as the Linear Threshold Model, where influence is a unidirectional process. In these models, once an individual adopts a behavior, they rarely revert, ignoring the strategic nature of human decision-making. In reality, individuals often adjust their choices based on the final, stable state of their peers. This paper addresses the challenge of identifying a minimal set of influential individuals who can strategically commit to a behavior to force the entire network into a specific, unique equilibrium.
Methodology: Influence Games
The core of our framework is the Linear Influence Game (LIG). In an LIG, each player $i$ has a personal threshold $t_i$ and receives weighted influence $w_{ij}$ from neighbors $j$. A player adopts a behavior if the sum of influences from their neighbors exceeds their threshold; otherwise, they reject it.
Stability as Nash Equilibrium
A state is considered stable if it constitutes a Pure-Strategy Nash Equilibrium (PSNE), meaning no individual has an incentive to change their behavior given the current actions of their neighbors.
Algorithmic Contributions
Finding PSNE in general networks is NP-complete. To address this computational hurdle, the paper proposes several specialized approaches:
- Tree-Structured Networks: An efficient $O(nd)$ algorithm for finding equilibria in trees.
- Divide-and-Conquer: A heuristic using vertex separators to decompose complex graphs into manageable sub-problems.
- Influence Identification: Mapping the problem of finding the "most influential nodes" to the Minimum Hitting Set problem, allowing for a greedy approximation algorithm with provable logarithmic guarantees.
Experimental Evaluation
The framework was evaluated using three primary datasets:
- Random Directed Graphs: To test baseline algorithmic performance and scalability.
- Preferential-Attachment Graphs: To simulate real-world scale-free social structures where a few nodes have high connectivity.
- US Congressional Voting Data: Using influence weights derived from the 101st and 110th US Senates to identify key political influencers.
Key Results and Insights
Our experiments highlight the critical distinction between "reach" and "strategic influence." In the US Senate analysis, the model identified influential senators who were not necessarily the most "connected" or popular, but whose positions were critical for stabilizing the voting outcomes. For example, in the 101st Senate, key influencers included senators like Rockefeller and Dole, despite them not having the highest degree in the network.
As shown in Figure 4, while the number of stable states grows with network size, the specialized search heuristics remain computationally feasible for networks of moderate size. The divide-and-conquer heuristic significantly outperformed standard backtracking; for the 110th Senate (100 nodes), it reduced the computation time for finding all stable states from 15 hours to approximately 7 hours.
Conclusion
Influence Games provide a robust alternative to traditional diffusion models by accounting for the strategic nature of social interactions. While finding equilibria remains computationally intensive for massive networks, the proposed heuristics offer a path toward scalability. Future work will explore dynamic influence weights and multi-action games to better capture the complexities of real-world social dynamics.
Summary updated