Competitive profit maximization in social networks

Weian Li, , Wenjing Liu, Tiantian Chen, Xiaoying Qu, Qizhi Fang, Ker-I Ko

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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.
Original languageEnglish
Pages (from-to)1-9
Number of pages9
JournalTheoretical Computer Science
Volume694
DOIs
StatePublished - 19 Sep 2017

Keywords

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

Fingerprint Dive into the research topics of 'Competitive profit maximization in social networks'. Together they form a unique fingerprint.

  • Cite this

    Li, , W., Liu, W., Chen, T., Qu, X., Fang, Q., & Ko, K-I. (2017). Competitive profit maximization in social networks. Theoretical Computer Science, 694, 1-9. https://doi.org/10.1016/j.tcs.2017.06.026