Two firms competing on a social network must split a fixed budget between making their product better for everyone and paying a few well-connected people to adopt it early and spread the word. Economists have solved idealized versions of this trade-off with clean threshold rules. Computer scientists have built fast tools for the seeding half on real graphs. On realistic graphs, though, the combined game is solved by a loop. Each firm repeatedly computes its best reply to the other's current mix of strategies, and the loop stops when no reply improves. That loop is only as good as the reply-finder inside it. Greedy and centrality-guided reply-finders tend to propose the same handful of hub nodes every time. When they do, the loop can stop early at a "solution" that a rival could beat with a strategy the reply-finder never considered, such as defending a remote community or putting everything into quality.
We propose to treat this as premature convergence at the level of the equilibrium computation, not just inside a single optimizer, and to fix it with a reply-finder that returns several strategically different strong replies. Each reply is drawn from a different region of a small, theory-motivated strategy space: how much of the budget goes to quality, and how much the seeds overlap with the opponent's. The claim we will test is narrow. At equal simulation cost, equilibria computed with diverse replies are measurably harder to exploit than those computed with greedy replies. The gap is concentrated where theory predicts non-hub strategies matter: unequal budgets and graphs with community structure.
Core Claim
The closest existing system is the Competitive Budget Allocation method of Competitive Influence Maximization: Integrating Budget Allocation and Seed Selection. It first uses a seed selector (TIM+) to pick a pool of "VIP" nodes. It then solves a simultaneous bidding game over that pool with a double oracle, a loop that grows a restricted game by adding each player's best reply, computed here by a knapsack dynamic program. The same paper reports that competitive seed selectors almost always converge on the same top candidates. We read that observation as a warning, not a convenience. Restricting the game to a shared VIP pool removes, by construction, the defensive strategies that Shielding and Shadowing found optimal for a budget-poor player: protecting your own uncontested neighbors instead of dueling on the opponent's targets. It also removes the all-quality corner that Competitive Diffusion in Social Networks: Quality or Seeding? proves optimal whenever no node's centrality clears the threshold $v_c$. That threshold is the point at which seeding the next node is worth less than a global quality upgrade.
Our proposal differs from CBA in two ways. First, quality is a decision variable alongside seeding, which CBA omits. Second, the best-reply step is replaced by a quality-diversity search, meaning a search that keeps the best solution found in each of several predefined behavioral niches instead of a single overall best. The niches are defined by two numbers: the fraction of budget spent on quality, and the opponent-overlap of the seed bids. The contribution is the diagnosis and its measurement, namely how exploitable greedy double-oracle equilibria are, together with the oracle that removes the problem. We do not claim a new diffusion model.
The Game
Each firm $i \in \{a, b\}$ chooses a quality level $q_i$ at cost $c(q_i)$ and integer bids $x_{i,v}$ on nodes $v$. The bids must satisfy $c(q_i) + \sum_v x_{i,v} \le B_i$, where $B_i$ is firm $i$'s budget. As in CBA, a node becomes a firm's seed if that firm bids strictly more, with ties broken at random. Diffusion follows a competitive independent cascade. An edge with base probability $p_e$ transmits product $i$ with probability $p_e\, g(q_i)$, where $g$ is increasing and concave so that quality has diminishing returns, matching the quality-or-seeding model. A node reached by both products at the same step adopts one in proportion to $g(q_i)$. The payoff is the expected difference in adopters, which keeps the game two-player and constant-sum. We accept this as a scope limit inherited from both the quality-or-seeding paper and CBA.
One technical piece makes the program affordable. We draw one uniform threshold $u_e$ per edge per sample and declare the edge live for firm $i$ when $u_e < p_e g(q_i)$. All quality levels and all candidate strategies can then be scored on the same samples. Comparisons between replies become paired, which reduces their variance, and a quality sweep costs one set of samples instead of one per level. The weighted reverse-reachable estimator from CBA can be reused on top of these coupled samples.
Research Program
The project has three parts. The first is the measurement instrument. We take the strategy mix that any solver outputs for firm $a$ and compute firm $b$'s best reply to it with a large, fixed audit budget, about ten times the solver's budget. That audit reply is the best result from a pooled search: greedy, the knapsack dynamic program, many random restarts, and the diverse oracle itself. The gain this reply achieves is the solver's exploitability. To guard against the audit being blind in the same way as the solver, we also compute exact equilibria by enumeration on small instances: graphs of 30 to 60 nodes with a few budget units and a few quality levels. These give ground truth.
The second part is the diverse oracle. Its archive has cells indexed by quality share, in five bins, and by overlap with the opponent's current support, from pure shadowing to pure shielding, also in five bins. Mutations follow the graph-aware operators of Graph-Aware Evolutionary Algorithms for Influence Maximization: neighbor swaps and embedding-space swaps chosen by a bandit. That paper uses centrality-based initialization and node filtering, which concentrate search on hubs. We drop both, because that concentration is exactly what we want to avoid here. At each round the oracle adds the best few occupied cells to the restricted game, rather than adding only the single best reply.
The third part is analysis. We map the exploitability of each solver against the budget ratio $B_a/B_b$ and against graph modularity. We check whether the diverse solver recovers the known regime structure: a "quality war" at equal budgets and a "seeding race" at unequal budgets, as in the quality-or-seeding paper, and the switch between shielding and shadowing near equal budgets reported in Shielding and Shadowing. We also check whether the greedy solver misses these regimes. A complex-contagion variant on blockmodel graphs tests a sharper tension. There, Think globally, act locally proves that concentrating all seeds in one community is optimal without a competitor. We ask whether a rival makes that concentration exploitable through blocking, as studied in Influence Blocking Maximization under the Competitive Linear Threshold Model.
Baselines
The naive reference points are uniform budget spreading over the VIP pool, which CBA reports it consistently beats, and an all-quality strategy. Both are scored for exploitability with the same audit procedure.
The strongest existing method is CBA itself, extended with a quality dimension. Its knapsack dynamic program is run for each discretized quality level, and the best result is kept. We give it the same coupled samples, the same simulation budget per round (number of payoff evaluations), and the same VIP pool size tuned on a held-out graph. The only number the file reports for CBA concerns payoff estimation, not equilibrium quality. On Wiki-Vote, the weighted reverse-reachable estimator reached a mean absolute error of 9.13, against 23.71 for the next best estimator (Competitive Influence Maximization). There is no reported result on Lacuna for the exploitability of CBA's equilibria or for the quality-extended game. Beating it therefore means lower audited exploitability at matched evaluations, with confidence intervals across at least ten seeds that do not overlap, on graphs with community structure.
The third baseline is continuous mirror descent on a relaxed version of the bids, following Scalable Equilibrium Computation in Multi-agent Influence Games on Networks. That method is guaranteed only for constant-sum, socially concave games under linear Friedkin–Johnsen dynamics. We run it anyway as a strong practical competitor.
Two ablations isolate the key ingredient. The first keeps the diverse oracle's search but adds only the single best reply per round, which tests whether multiple replies matter. The second keeps multiple replies but replaces the theory-motivated niches with generic Hamming-distance diversity, which tests whether the choice of descriptors matters.
Why not just…?
Why not just use random restarts or uniform random sampling for the best reply? Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization found that uniform random sampling was hardly ever beaten by diversity-oriented heuristics. This is a real threat, so random-restart greedy replies are a baseline at matched evaluations. Our reason to expect a gap is that random seed sets rarely hit the narrow shielding configurations: bids placed on the immediate neighbors of the opponent's targets. They also rarely produce the dense single-community clusters that complex contagions need. If random restarts match our oracle, we will report that the trap is cheap to escape and that diversity in strategy type adds nothing.
Why not just run the standard double oracle longer? Given enough rounds, a double oracle with an exact reply-finder converges. Our concern is that greedy reply-finders are not exact, so more rounds can keep re-adding hub strategies. We plot exploitability against the number of rounds for both solvers. If greedy CBA closes the gap with two to three times the rounds, the honest conclusion is that the trap is a matter of efficiency, not correctness.
Why not just seed the strategy pool with hand-designed archetypes such as quality-only, shadow, and shield? This may be the strongest alternative, because the archetypes come from the same theory as our niches. We include it as a baseline: CBA initialized with these three strategies for every quality level. If it matches the diverse oracle, the contribution reduces to a cheap and useful recipe, and we will say so. We expect it to fall short on blockmodel and real graphs, where the right remote community to defend depends on the instance.
Why not just use gradient methods on the continuous relaxation? The convergence guarantee of the mirror-descent approach depends on social concavity, and Shielding and Shadowing notes that vote-share surfaces are non-convex. Running mirror descent as a baseline shows directly whether its solutions are exploitable once rounded to discrete bids.
Proposed Experiments
Small-graph ground truth comes first. These are enumerable instances on star graphs, balanced graphs, small Watts–Strogatz graphs, and small blockmodel graphs. The quality-or-seeding paper shows that the star and balanced graphs bound when seeding is profitable at all, which makes them a correctness check. The decisive test here is whether greedy CBA's exploitability, measured against exact equilibria, is concentrated in instances with unequal budgets and community structure, and whether the diverse oracle removes it.
At scale we use Wiki-Vote, Ego-Facebook, CA-HepTh, p2p-Gnutella08, and NetHEPT, which are the graphs CBA and TCIM used. We use Epinions as a stress test. TCIM, from Algorithmic Design for Competitive Influence Maximization Problems, handled Epinions in under six minutes and reports up to 10,000x speedups over greedy Monte Carlo, so TCIM-style sampling sets our cost target. Synthetic Barabási–Albert and Watts–Strogatz graphs with 1,000 to 10,000 nodes let us sweep modularity.
The metrics are audited exploitability, expected adopter difference at the computed equilibrium, the number of payoff evaluations, and the share of equilibrium probability placed on quality-heavy or shielding cells. The central prediction would be refuted by any of three outcomes: matched-budget exploitability that is statistically indistinguishable from greedy CBA on modular graphs with budget ratios of at least 2, a random-restart baseline that ties the diverse oracle, or a hand-built archetype portfolio that ties it.
References
- Competitive Influence Maximization: Integrating Budget Allocation and Seed Selection
- Shielding and Shadowing: A Tale of Two Strategies for Opinion Control in the Voting Dynamics
- Competitive Diffusion in Social Networks: Quality or Seeding?
- Graph-Aware Evolutionary Algorithms for Influence Maximization
- Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
- Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model
- Scalable Equilibrium Computation in Multi-agent Influence Games on Networks
- Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization
- Algorithmic Design for Competitive Influence Maximization Problems