TIC & FairInf: Balancing Dominance and Equity in Competitive Social Networks

TL;DR

In the world of viral marketing, social media platforms (the "agencies") face a dilemma: how to help multiple competing companies maximize their reach while ensuring that no one is unfairly suppressed. This paper introduces the Timeliness Independent Cascade (TIC) model and the FairInf problem. By exploiting the submodularity of influence spread, the authors develop the Myopic Greedy (MG) algorithm, which ensures a fair distribution of influence (Earning-to-Budget Ratio) across competitors with near-optimal efficiency.

Background & Motivation

Most influence maximization (IM) research focuses on a single entity trying to dominate a network. However, real social networks are battlegrounds for multiple "cascades"—think Coca-Cola vs. Pepsi or competing political narratives.

Prior work often assumes:

1. Binary outcomes: A node is either influenced by A or B.
2. Global knowledge: Each company knows the entire network structure.

The authors argue these assumptions are unrealistic. Instead, they propose a model from the agency's perspective (e.g., Meta or ByteDance), where the platform owner must allocate seeds to various clients fairly based on their budgets.

The TIC Model: Capturing Timeliness and Competition

The Timeliness Independent Cascade (TIC) model introduces a critical realistic constraint: the Decision Deadline ($D_v$).

In TIC, if a node $v$ receives successful activations from various influences ($c_1,c_2,...,c_m$) before its deadline $D_v$, it doesn't just pick the first one. Instead, it "remembers" all successful attempts. At time $D_v$, it decides to adopt color $c_i$ with a probability: $P(v=c_i)=\frac{b_i}{\sum b_j}$ where $b_i$ is the number of times it was successfully activated by influence $c_i$. This captures the "word-of-mouth" frequency effect.

Methodology: The FairInf Problem

The FairInf problem is split into two distinct challenges:

1. Max-Spread: Maximize the total number of influenced nodes regardless of their color.
2. Max-Fairness: Ensure the Earning-to-Budget Ratio (EBR) is balanced across all companies.

The "Individual Spread" Insight

A key theoretical contribution is the proof that a company's influence is monotone and submodular even in TIC. Furthermore, the authors define Individual Spread ($I_{-S}(s)$)—the expected contribution of a seed $s$ to the total spread. Crucially, they prove that this value is constant regardless of which color is assigned to $s$.

The Myopic Greedy (MG) Algorithm

The MG algorithm operates on a simple but proven logic:

1. Sort all chosen seeds by their individual spread.
2. Iterate through the seeds and assign each to the company currently suffering from the lowest EBR.

This "greedy balancing" is mathematically proven to be the optimal strategy for maximizing the fairness metric $f=e_{min}/e_{max}$.

Experimental Validation

The authors tested MG against OPT (Optimal via enumeration) and RAN (Random) on datasets like Douban (1.7M edges).

• Fairness: MG consistently achieved a fairness score near 1.0, almost identical to the computationally expensive OPT.
• Efficiency: While OPT is intractable for large seed sets, MG runs in milliseconds ($O(\log m\sum {\mu }_i)$).

Deep Insight & Conclusion

The genius of this paper lies in its agency-centric view. By proving that individual seed contributions can be localized/quantified ($I_{-S}(s)$), the authors turned a complex competitive game into a manageable resource allocation problem.

Takeaway: For modern social platforms, fairness isn't just an ethical choice—it's a computational one. The TIC model provides a robust framework for managing multi-client viral marketing campaigns where timeliness and frequency of exposure are the primary drivers of adoption.

Limitations: The model assumes the agency chooses all seeds. In reality, companies might select their own seeds without coordination, which would shift the problem back toward a non-cooperative game theory landscape.