ChoiceGAPs: Modeling Social Diffusion as a Massive Multi-player Game

TL;DR

In the real world, "likes" are often mutually exclusive—you support one political candidate or another, but rarely both. ChoiceGAPs introduce a rigorous mathematical framework to model this competition using logic programming. By treating every Facebook user as a player in a massive game, the authors achieve high-accuracy predictions (0.76 AUROC) of election outcomes using a new solution concept called Strong Equilibrium.

Background: The Limits of Individual Diffusion

Most social network research treats information spread like a virus—if your friend has it, you might catch it. However, real life is a zero-sum game of attention and loyalty. If you buy an Android, you aren't buying an iPhone. Current models (like Independent Cascade) struggle to handle this competition effectively, and traditional Game Theory (Nash Equilibrium) fails because it assumes every user is an omniscient strategist who knows the entire network's state.

The Insight: Logic Meets Game Theory

The authors combine Generalized Annotated Programs (GAPs), which handle the "certainty" or "likelihood" of a behavior, with Choice Logic, which handles the "this or that" decision-making process.

1. The Vertex Choice (VC) Rule

The core mechanism is the VC Rule: $b_1(X),\dots ,b_m(X)\hookleftarrow a_1(X),\dots ,a_m(X)$ Here, $a_i$ represents the utility (the "why" or "strength of influence") and $b_i$ represents the decision (the "what"). A user picks the option that provides the highest utility, setting all other competing choices to zero.

2. From Nash to Strong Equilibrium

A Nash Equilibrium requires a player to know everyone else's strategy—a feat impossible on Facebook. The authors propose Strong Equilibrium, which focuses on Coherent Models. These are states where a player's choice is consistent with their local utilities derived from the diffusion process.

Methodology: The VIC2 Class

General ChoiceGAPs are computationally expensive (NP-complete). To solve this for millions of users, the authors identified Vertex Independent Choice (VIC) Programs.

In a VIC2 program (where users choose between two competing options):

• A Strong Equilibrium is guaranteed to exist.
• It can be computed in Polynomial Time using a simple iterative algorithm.
• It avoids the complexity of global knowledge by focusing on local dependency graphs.

Experimental Results: The 2013 Italian Election

To prove the theory, the authors tested ChoiceGAPs on the 2013 Italian general election using Facebook data (65K users, 84K friendships).

Key Findings:

• Accuracy: The model achieved an average AUROC of 0.76, indicating strong predictive power against actual user preferences (likes of political pages).
• Data Efficiency: Surprisingly, accuracy remained stable even when the training data was reduced to only 20% of the network.
• Scalability: Unlike previous logic-based models that stalled on 10K nodes, ChoiceGAPs scaled to the full dataset efficiently.

Critical Insight & Conclusion

ChoiceGAPs represent a major step forward by moving away from "black-box" diffusion models toward "white-box" logical reasoning.

The Takeaway: You don't need a supercomputer or perfect information to predict social trends. By defining simple, local logical rules and finding a "coherent" state, we can simulate the aggregate behavior of millions of individuals with surprising precision.

Limitations: While VIC2 is efficient, more complex competitions (VIC3+) remain NP-hard, suggesting that as binary choices become multi-faceted (e.g., choosing between five different smartphone brands), the computational cost will require new heuristic approaches.