Positive Influence Dominating Set Games

Author

Guangyuan Wang ; Hua Wang ; Xiaohui Tao ; Ji Zhang ; Xun Yi ; Jianming Yong

Author_Institution

Dept. of Math. & Comput., Univ. of Southern Queensland, Toowoomba, QLD, Australia

fYear

2014

fDate

21-23 May 2014

Firstpage

469

Lastpage

473

Abstract

Motivated by applications in social networks, a new type of dominating set named Positive Influence Dominating Set (PIDS) has been studied in the literature. In this paper, we investigate cooperative cost games arising from PIDS problem on social network graphs. We propose two new game models, Rigid PIDS Game and Relaxed PIDS Game, and focus on their cores. First, a relationship between the cores of both games is obtained. Next, we also prove that the core of the relaxed PIDS game is nonempty if and only if there is no integrality gap for the relaxation linear programming of the PIDS problem on graph G.

Keywords

game theory; set theory; social networking (online); cooperative cost games; game models; positive influence dominating set games; relaxed PIDS game; rigid PIDS game; social network graphs; Approximation methods; Game theory; Games; Linear programming; Optimization; Social network services; Testing; Positive influence dominating set; balancedness; cooperative game; core;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Supported Cooperative Work in Design (CSCWD), Proceedings of the 2014 IEEE 18th International Conference on

Conference_Location

Hsinchu

Type

conf

DOI

10.1109/CSCWD.2014.6846890

Filename

6846890