Browsing by Author "Fang, Qizhi"

Now showing 1 - 2 of 2

Centralized and decentralized rumor blocking problems
(2017-07-01)
Chen, Xin
;
Nong, Qingqin
;
Feng, Yan
;
Cao, Yongchang
;
Gong, Suning
This paper consists of two parts. In the first part, we study a centralized rumor blocking problem with a novel social objective function different from those in the literature. We will show that this objective function is non-decreasing and submodular and hence corresponding rumor blocking problem has a greedy approximation with objective function value at least of the optimal. In the second part, we study a decentralized rumor blocking problem with two selfish protectors, which falls into a 2-player non-cooperate game model. We will show that this game is a basic valid utility system and hence the social utility of any Nash equilibrium in the game is at least a half of the optimal social utility.
Competitive profit maximization in social networks
(2017-09-19)
Li, Weian
;
Liu, Wenjing
;
Chen, Tiantian
;
Qu, Xiaoying
;
Fang, Qizhi
We study the competitive profit maximization problem in a social network, which can be viewed as the profit maximization problem in a game-theoretic setting. We formulate two models called the profit maximization-agent (PM-A) game and the profit maximization-society (PM-S) game. By reducing them to be valid utility systems, we show that any Nash equilibrium provides an excepted social utility within a factor 1/2 (subject to a function-dependent additive term) of the optimum in the PM-A game and a factor of 1/2 of the optimum in the PM-S game. Furthermore, for the PM-S game, a polynomial-time algorithm is given for each player that can approximate the best response within a factor (1 - 1/e). (C) 2017 Elsevier B.V. All rights reserved.