KIMI: Mastering Multi-Topic Social Influence with Budget Feasibility

TL;DR

Marketers today don't just sell one product; they manage diverse portfolios. This paper introduces KIMI, the first budget-feasible mechanism for k-topic influence maximization. It solves the NP-hard problem of selecting influencers for different topics (e.g., luxury vs. economy lines) while ensuring they bid their true costs and the total spend stays within individual topic budgets.

The "Multi-Topic" Headache

Influence Maximization (IM) is a classic problem: find the best "seed nodes" to start a viral cascade. However, traditional IM assumes a one-size-fits-all influence. In reality:

1. Topic Sensitivity: A beauty influencer is great for cosmetics but ineffective for gaming hardware.
2. Budget Constraints: Campaigns have strict "wallets" for each product line.
3. The Honesty Gap: Influencers (agents) are rational. If they can lie about their costs to get a higher payout, they will—unless the mechanism is "Truthful."

Previous solutions for $k=1$ (single topic) fall apart when $k>1$ because the marginal gain of an influencer now depends on both the selection order and the specific topic they are assigned to.

Methodology: The Power of k-Submodularity

The core mathematical engine of this paper is k-submodularity. While standard submodularity deals with sets, k-submodularity deals with a vector of $k$ disjoint sets. The authors prove that the influence function remains "Orthant Submodular," meaning the benefit of adding an influencer decreases as the set of already-chosen influencers grows.

The KIMI Mechanism

KIMI operates in two distinct phases:

1. KIMI-Alloc (Allocation): A greedy approach that selects influencer-topic pairs $(e,i)$ that offer the highest marginal-gain-per-cost ratio. It balances this against a "threshold" to ensure the selection doesn't exhaust the budget too early on low-value nodes.
2. KIMI-Pricing (Payment): To ensure Truthfulness, KIMI doesn't just pay what the influencer asks. It calculates a Critical Value—the maximum bid the agent could have submitted while still winning their slot.

Note: The mechanism relies on identifying the optimal marginal gain ${\Delta }_{e,i}$ relative to the current state $x$.

Experimental Proof: Does it Scale?

The researchers tested KIMI on a massive Facebook dataset (72 million edges).

Key Findings:

• Superiority Over Baselines: KIMI significantly outperformed "Uniform" pricing and "Random" selection. While a "Greedy" (non-truthful) algorithm performed best, it is impractical because real-world influencers won't reveal their true costs without the guarantees KIMI provides.
• The "k" Factor: As the number of topics ($k$) increased, KIMI's performance actually improved relative to the budget. This is because a more diverse set of topics allows the algorithm to find "perfect matches" for specific influencers more efficiently.

Figure 1: Comparison of KIMI against Greedy, Uniform, and Random methods across different budget levels.

Critical Insight & Conclusion

The true value of this work lies in the $\frac{5e}{e-1}$ approximation guarantee. In the world of mechanism design, achieving a constant factor approximation while maintaining truthfulness and budget feasibility is a high bar.

KIMI provides a robust framework for platforms like YouTube (FameBit) or IZEA to automate influencer selection across multi-product campaigns. The only remaining challenge is the computational overhead of k-submodular functions in real-time settings, which future work might address through further pruning or distributed computing.

Takeaway: When you have multiple goals and a limited wallet, don't just pick the cheapest influencers—pick the ones whose marginal value per dollar is highest for their specific niche, and pay them their "critical value" to keep the marketplace honest.