Maximizing influence propagation for new agents in Competitive Environments

In a competitive environment, competing agents would maximize their ideas´ influence for higher profits. For example, in an unsaturated market, when a new company participates in the market sharing competition, it would distribute free tryout or discount to several customers, let them adopt the product or service, and influence others to use this product as propagation goes. This situation can also be applied to other scenarios, such as spreading new ideas in online social networks, political elections, and so on. In this paper, we use a model called Dynamic Influence in Competitive Environments (DICE) to perform the influence propagation. We first prove that finding the optimal utility for the new agent is an NP-hard problem under DICE. Then, we provide an algorithm for these new companies, and prove that the algorithm has a (1/3 - ϵ/n)-approximation ratio to the maximum payoff value. Performance results show that our algorithm has a better performance compared to existing strategies in terms of maximizing the utility for new agents.