Beyond Monopolies: The Complexity of Competing Products in Social Networks

TL;DR

Most mathematical models of social influence assume we are only deciding whether or not to buy one specific product. Apt and Markakis break this mold by introducing a threshold model where multiple products compete for the same users. They prove that while it's easy to see if a product can take over the world, it is computationally "nightmarish" (NP-hard) to calculate the minimum guaranteed spread in a competitive market.

Background: Why Single-Product Models Fail

Traditional models like the Linear Threshold Model (LTM) treat adoption as a binary state. However, the real world is a battleground of alternatives. If you are choosing a mobile carrier, you don't just "adopt" telephony; you choose between AT&T, Verizon, or T-Mobile. This choice is influenced by which networks your friends are on to reduce costs or improve connectivity.

The core challenge here is Ambivalence. In a multi-product world, a node might satisfy the threshold for two different products simultaneously. The order in which people make decisions suddenly changes everything, leading to multiple possible "final states" of the network.

Methodology: The Geometry of Influence

The authors introduce the concept of a $heta$-well-structured graph.

The $heta$-Well-Structured Insight

A network is considered $heta$-well-structured if you can layer the nodes into "levels" such that every node in level $i$ has enough input from nodes in levels $0$ to $i-1$ to exceed its adoption threshold.

Figure 1: Illustration of a social network where nodes have set choices (e.g., $\{t_1,t_2\}$) and specific thresholds.

This structural property allows the authors to prove two critical theorems:

1. Reachability: A product can occupy the entire network if and only if the graph is $heta$-well-structured.
2. Unavoidability: A product must occupy the whole network if it is the only choice for "root" nodes (those with no neighbors) and the structure ensures no other product can gain a foothold.

The "Complexity Gap": Optimism vs. Pessimism

The most striking part of this research is the disparity in computational complexity between finding the Maximum Adoption and Minimum Adoption.

• MAX-ADOPTION (The Optimist's View): If we want to know the maximum number of people we can reach, we can use a "Fast Reduction" algorithm. We simply let everyone who can adopt our product do so immediately. This is solvable in $O(n^2)$ time.
• MIN-ADOPTION (The Pessimist's View): If we want to know the absolute minimum number of people we will reach regardless of how competitors act, the problem becomes NP-hard. In fact, it's not even roughly approximable.

The Partition Reduction

The authors proved the hardness of MIN-ADOPTION by reducing it from the PARTITION problem. They designed a gadget where a product's spread depends on whether a specific set of nodes can perfectly balance their influence.

Figure 2: The gadget used to prove NP-hardness. If a partition exists, the product "top" is blocked; otherwise, it surges through the network.

Critical Insight & Conclusion

This paper serves as a cautionary tale for algorithmic marketing. In a vacuum, your product might look like it's destined for SOTA-level adoption. However, in a competitive social graph, the existence of even one alternative can lead to "path dependency," where the specific sequence of early adoptions determines the ultimate winner.

Takeaway for Researchers: The transition from $P=1$ (single product) to $P>1$ (competing products) doesn't just add a variable; it fundamentally changes the complexity class of the underlying search problems. While influence maximization is already hard, influence guarantee is even harder.

Limitations: The model assumes once a product is adopted, the consumer never switches back or moves to a third option. Future work incorporating "churn" or "re-adoption" would bridge the gap between this theoretical threshold model and the dynamic reality of modern SaaS marketplaces.