Competitive profit maximization in social networks

作者：Li, Weian; Liu, Wenjing^*; Chen, Tiantian; Qu, Xiaoying; Fang, Qizhi; Ko, Ker-I

来源：Theoretical Computer Science, 2017, 694: 1-9.

DOI：10.1016/j.tcs.2017.06.026

• Social network
• Profit maximization
• Valid utility system
• Nash equilibrium
• Best response

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).

• 出版日期2017-9-19
• 单位中国海洋大学