Competitive Profit Maximization: Balancing Agent Gains and Social Welfare in Social Networks

TL;DR

This study bridges the gap between simple "Influence Maximization" (counting heads) and "Profit Maximization" (counting dollars) in competitive markets. By defining two distinct games—PM-A (Agent-focused) and PM-S (Society-focused)—the authors prove that even in a chaotic competitive environment, any Nash Equilibrium will capture at least 50% of the maximum possible social utility.

Problem & Motivation: Beyond the Viral Count

Classical Viral Marketing research focuses on the quantity of adoption. However, a "free sample" (seeding) costs money, and different customers bring different profit margins. Furthermore, in the real world, brands like Ford and Toyota compete simultaneously.

The authors identify a critical gap: existing competitive models often ignore the Social Utility (customer satisfaction). They argue that a system that considers how much customers value a product (PM-S) is mathematically more robust and leads to better overall outcomes than one where agents only look at their own bottom line (PM-A).

Methodology: Valid Utility Systems

The core innovation lies in reducing these complex social games to Valid Utility Systems. To achieve this, the authors verify three mathematical properties:

1. Submodularity: The "diminishing returns" property—adding a seed node to a large set helps less than adding it to a small set.
2. Private vs. Social Utility: An agent's profit must be at least as large as the difference they make to the total social welfare.
3. Feasibility: The sum of all individual profits cannot exceed the total social utility.

The PM-S Social Utility Function

The PM-S social utility is elegantly simplified in the paper. It combines agent profits (Price - Cost) and customer satisfaction (Value - Price). When summed, the "Price" terms cancel out, leaving: ${\gamma }^g(S)={\sum }_{v\in {\varphi }^g(S)}({\pi }_v-c)$ This formula represents the net "Social Surplus"—the total value created minus the total cost incurred.

Figure 1: Conceptual visualization of influence diffusion in a social network with multiple competing agents.

Experiments & Results: The 1/2 Bound

The paper utilizes the Price of Anarchy (PoA) framework to determine how much efficiency is lost due to competition.

• PM-A Results: Because the social utility in the Agent-only model is not "non-decreasing" (adding more seeds might actually decrease total profit due to costs), the 1/2 bound is subject to an additive term.
• PM-S Results: Because PM-S includes customer utility, the function becomes non-decreasing and submodular. This yields a clean 1/2 PoA bound, meaning the competitive outcome is never worse than half of the coordinated global optimum.

The Best Response Algorithm

For an individual agent trying to find the best strategy against competitors, the authors provide a Greedy Approximation Algorithm. Since finding the optimal seed set is NP-hard, they prove that a greedy selection (repeatedly picking the node with the highest marginal gain) achieves a (1 - 1/e) approximation.

Figure 2: The approximation guarantee for the Greedy Best Response algorithm, ensuring near-optimal performance for individual agents.

Critical Analysis & Conclusion

Takeaway

The most profound insight of this paper is that altruism (considering society) leads to mathematical stability. By including customer satisfaction in the objective function (PM-S), the system's performance at equilibrium becomes much easier to bound and guarantee compared to a purely selfish profit-seeking model (PM-A).

Limitations & Future Work

While the IC model is a strong foundation, modern social networks often exhibit "threshold" behaviors where a node only activates if a certain percentage of friends join. The authors acknowledge that extending this "Valid Utility System" approach to Linear Threshold (LT) models is the next logical frontier. Additionally, the model assumes costs and prices are static; a more dynamic model incorporating price wars would be a significant leap forward in game-theoretic marketing research.