ChoiceGAPs: competitive diffusion as a massive multi-player game in social networks

DOI10.1007/978-3-319-45856-4_21zbMATH Open1364.91132arXiv1410.6118OpenAlexW45429753MaRDI QIDQ5268424FDOQ5268424

V. S. Subrahmanian, Edoardo Serra, Francesca Spezzano

Publication date: 20 June 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of modeling competitive diffusion in real world social networks via the notion of ChoiceGAPs which combine choice logic programs due to Sacca` and Zaniolo and Generalized Annotated Programs due to Kifer and Subrahmanian. We assume that each vertex in a social network is a player in a multi-player game (with a huge number of players) - the choice part of the ChoiceGAPs describe utilities of players for acting in various ways based on utilities of their neighbors in those and other situations. We define multi-player Nash equilibrium for such programs - but because they require some conditions that are hard to satisfy in the real world, we introduce a new model-theoretic concept of strong equilibrium. We show that stable equilibria can capture all Nash equilibria. We prove a host of complexity (intractability) results for checking existence of strong equilibria (as well as related counting complexity results), together with algorithms to find them. We then identify a class of ChoiceGAPs for which stable equilibria can be polynomially computed. We develop algorithms for computing these equilibria under various restrictions. We come up with the important concept of an estimation query which can compute quantities w.r.t. a given strong equilibrium, and approximate ranges of values (answers) across the space of strong equilibria. Even though we show that computing range answers to estimation queries exactly is intractable, we are able to identify classes of estimation queries that can be answered in polynomial time. We report on experiments we conducted with a real-world FaceBook data set surrounding the 2013 Italian election showing that our algorithms have good predictive accuracy with an Area Under a ROC Curve that, on average, is over 0.76.

Full work available at URL: https://arxiv.org/abs/1410.6118

Recommendations

• Complexity of equilibrium in competitive diffusion games on social networks
• A note on competitive diffusion through social networks
• Competitive diffusion on weighted graphs
• Multi-player diffusion games on graph classes
• A game-theoretic approach for modeling competitive diffusion over social networks

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Games involving graphs (91A43)

Cites Work

• Equilibrium points in n -person games
• Qualitative analyses of communicable disease models
• Title not available (Why is that?)
• Using Generalized Annotated Programs to Solve Social Network Diffusion Optimization Problems
• Word of Mouth: Rumor Dissemination in Social Networks

Cited In (1)

• ChoiceGAPs

Uses Software

• ProbLog
• Datalog

This page was built for publication: ChoiceGAPs: competitive diffusion as a massive multi-player game in social networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5268424)