{"id":"67604581-9d70-4548-866b-12d9ef016ca7","arxiv_id":"1908.09185","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Coordinated multi-advertiser influence maximization reduces to submodular maximization under two matroids, giving roughly 1/2 approximations in general and a practical 1-1/e algorithm for the Independent Cascade model.","lead":"This paper gives approximation algorithms for a platform that runs many ad campaigns at once on the same social network, where no user should see too many sponsored ads. It shows the revenue-maximization problem can be viewed as optimizing a submodular function under matroid constraints, yielding constant-factor guarantees and a practical algorithm for the Independent Cascade model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6's IC (1-1/e) guarantee rests on an unproved extension of Gandhi et al. rounding to the global seed cap; the negative-correlation inequality at step (1) may not survive that extension.","rationale":"The reader's conditional verdict is well-founded. My independent pass found the same load-bearing gap and an additional scaling typo in Theorem 6. I did not find a fundamental flaw in the Section 3 reduction: the construction of the one/two matroids is correct, and the use of Theorems 2-4 is standard once submodularity is granted. The experimental section is not needed for the theoretical claim and does not mitigate the proof gap. Because the gap is localized to the IC LP-rounding guarantee and likely repairable, I would not lower the verdict below conditional; I also see no reason to raise it, so the reader's CONDITIONAL verdict should stand.","tokens_in":22939,"tokens_out":18623,"duration_ms":197572,"concrete_test":"Run the proposed final-loop rounding on a small LP solution that forces it to pair variables from different advertisers (e.g., two advertisers, two nodes, all z=0.5, r_v=1, K=1), enumerate the joint distribution, and test the negative-correlation inequality Prob[z_v=0 for all v in R_i] ≤ ∏ Prob[z_v=0] for every reverse-reachable set R_i. If the inequality fails on any R_i, step (1) of Theorem 6 is invalid and the (1-1/e) guarantee is unsupported; if it holds on this and several random larger instances, the extension is plausible but still needs a proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline IC result is Theorem 6, which proves E[hat y(j)] ≥ (1-1/e)y(j) using step (1): Prob[hat z_v=0 for all v in R_i] ≤ ∏ Prob[hat z_v=0]. This negative-correlation inequality is guaranteed by Gandhi et al. only for subsets of edges incident to a common node of the bipartite rounding graph. The global seed budget |A0|≤K is not a node-degree constraint, and the footnote's proposed 'final loop' that pairs arbitrary fractional variables is not shown to preserve negative correlation for all subsets of variables incident to a given advertiser. Pairwise rounding can destroy negative association among variables incident to a common advertiser, so the inequality used to lower-bound Pr[hat x_i=1] is unsupported. If it fails, the (1-1/e) claim collapses; the Section 3 matroid-intersection results do not depend on this step. Separately, the definition of hat y(j) just before Theorem 6 omits the n/rho factor present in LP constraint (5); as written, E[hat y(j)] ≥ (1-1/e)y(j) would need a factor rho/n correction, so the proof must be repaired even if negative correlation is established. Both issues are fixable in principle, but they are exactly the load-bearing gap in the paper's strongest algorithmic claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies coordinated advertising campaigns on a social network, where multiple advertisers run independent influence cascades but compete for per-node exposure caps and, optionally, per-advertiser seed set budgets. The host maximizes either expected revenue W or revenue based on expected exposure \\bar W. The main theoretical contribution is a reduction, under the general threshold model with monotone submodular local influence functions, of the multi-product influence maximization problem to monotone submodular maximization over a matroid intersection: with per-advertiser seed caps the feasible region is the intersection of two matroids, giving a (1/(2+\\epsilon))-approximation, and without seed caps it is a single truncated partition matroid, giving a (1-1/e-\\epsilon)-approximation via continuous greedy. For the Independent Cascade model, the paper proposes an LP based on reverse reachable sets, rounded using the dependent rounding algorithm of Gandhi et al., and claims a (1-1/e)-approximation with budgets enforced in expectation. Experiments on four real networks compare greedy and LP-rounding algorithms, study the effect of network similarity and tie strength on competition, and report scalability results for a parallel greedy algorithm.","tokens_in":23209,"tokens_out":33343,"duration_ms":328803,"significance":"The Section 3 reduction is a genuinely useful conceptual contribution: it makes the matroid structure of multi-advertiser constraints explicit, subsumes earlier models of Datta et al. and Aslay et al., and immediately imports known approximation algorithms, improving the previous 1/3 guarantee to essentially 1/2 in the two-matroid case and 1-1/e in the single-matroid case. The reverse-reachability LP-rounding algorithm, if its proof is repaired, would be a practically attractive method for IC networks of tens of thousands of nodes, and the paper's experiments provide useful qualitative evidence about how competition reduces host revenue. The main weakness is that the proof of the headline IC result, Theorem 6, has load-bearing gaps that are not merely cosmetic.","major_comments":[{"comment":"The proof of Theorem 6 compares E[\\hat y(j)] with y(j), but \\hat y(j) is defined immediately before the theorem as \\hat y(j)=\\sum_{i\\in R(j)} \\gamma(j)\\hat x_i, omitting the factor n/\\rho that appears in LP constraint (5). Since y(j)\\le (n/\\rho)\\sum_{i\\in R(j)}\\gamma(j)x_i, the final chain of inequalities yields only E[\\hat y(j)]\\ge (1-1/e)(\\rho/n)y(j), not the claimed E[\\hat y(j)]\\ge (1-1/e)y(j). The proof should redefine \\hat y(j) with the n/\\rho scaling and then handle the cap \\min(B(j), \\gamma(j)E[N_j]) explicitly for the expected-exposure objective.","section":"Section 4.2, definition of \\hat y(j) and Theorem 6 proof"},{"comment":"The proposed extension of dependent rounding to enforce the global seed budget \\sum_{j,v} z_v^{(j)}\\le K is not a consequence of the Gandhi et al. framework and, as described, does not produce a feasible solution with probability 1. Pairwise rounding of arbitrary fractional variables can overshoot the total: three fractional variables of value 0.3 belonging to three different advertisers have fractional total 0.9, yet the described final loop, which pairs them and then rounds the last variable alone, produces a rounded total of 2 with positive probability even when K=1. Thus the claim that all ILP constraints except the budget cap are satisfied is unsupported. Moreover, the negative-correlation inequality (1) used in Theorem 6 requires that for each advertiser j and each RR set R_i, the all-zero event on the variables {z_v^{(j)}: v\\in R_i} is negatively correlated; Gandhi et al. guarantee this property for subsets of edges incident to a common node of the original bipartite graph, and no proof is given that the final loop preserves it. This is a load-bearing step for the (1-1/e) IC guarantee.","section":"Section 4.2, final-loop extension of Gandhi et al."},{"comment":"The proof states that when B(j)\\le \\gamma(j), any nonempty S(j) yields \\gamma(j)q(j)\\ge B(j) 'with probability 1'. This is false: q(j)=n\\cdot|\\{i\\in R(j): R_i\\cap S(j)\\neq\\emptyset\\}|/\\rho is a random RR-set estimate and can be 0 with positive probability even for a nonempty S(j). The error bound should instead be argued under the high-probability event from Lemma 5, where q(j)\\ge 1-\\epsilon/m; this can still give an O(\\epsilon) total estimation error, but the argument as written needs to be corrected.","section":"Section 4.1, payoff estimation error, second case"}],"minor_comments":[{"comment":"The abstract contains a typo: 'orgain' should be 'organic'.","section":"Abstract"},{"comment":"The notation in the LP constraint \\sum_{v\\in R_i} z_v^{(j(i))} is ambiguous, because R_i is defined as a subset of the cloned universe U^{(j)}, while z is indexed by original network nodes v; the authors should state explicitly that the sum is over original nodes whose copies appear in R_i.","section":"Section 4.2"},{"comment":"In the description of the node-swap process, 'performs· n/100 node swaps' should read 'performs s· n/100 node swaps'.","section":"Section 5.3"},{"comment":"The theorem statement should make explicit that the guarantee holds with high probability over the random RR-set sampling, and, in the budgeted case, in expectation over the rounding; the current statement reads as a deterministic worst-case guarantee, which the proof does not provide.","section":"Theorem 6"},{"comment":"The step from E[\\hat y(j)]\\ge (1-1/e)y(j) to an approximation guarantee for the expected-exposure revenue with the cap min(B(j),\\cdot) is omitted; the authors should spell out the inequality E[\\min(B,cX)]\\ge (1-1/e)\\min(B,cE[X]) for nonnegative X.","section":"Section 4.2, proof of Theorem 6"}],"recommendation":"major_revision","confidential_remarks":"The Section 3 matroid-reduction part is solid and likely publishable on its own, and the experimental study is informative. The current version of Theorem 6, however, is not proven: the missing n/\\rho factor and the unproved final-loop rounding are concrete, fixable errors, but they are exactly the load-bearing steps of the paper's strongest algorithmic claim. I would encourage the editor to request a revision in which the IC LP-rounding proof is either repaired with a rigorous global rounding step (e.g., a proper treatment of the cardinality constraint that preserves negative correlation) or the claimed guarantee is weakened accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the Section 3 result is the real contribution and it's clean. Theorem 6's proof, as written, is not clean—there's a missing factor and an unproved extension—but neither issue looks fatal.\n\nSection 3 recasts the multi-advertiser problem as monotone submodular maximization over the intersection of two matroids. That explicit reduction is new for this problem and it immediately improves the guarantees from Datta et al. (1/3) and Tang-Yuan (1/4) to essentially 1/2, and 1-1/e when per-advertiser seed caps are dropped. The argument uses standard building blocks and I see no circularity. This is a useful result worth citing.\n\nThe IC LP-rounding algorithm in Section 4 is a good idea and the experiments are reasonable, but the proof of Theorem 6 has two problems. First, ŷ(j) is defined without the n/ρ factor from LP constraint (5), so the claimed E[ŷ(j)] ≥ (1-1/e)y(j) doesn't follow as written. That's a straightforward fix. Second, the extension of Gandhi et al. rounding to the global seed budget is asserted in a footnote, not proved. The stress-test concern about negative correlation is partly over-stated—after the standard rounding, each advertiser/node has at most one fractional variable, so the final loop mostly pairs variables from different constraints and the product inequality is likely preserved—but the paper doesn't show this, and the proof leans on it at step (1). A referee should ask for a full proof or a citeable version.\n\nThe experiments are fine for what they are, but no code or seeds are provided, so I'd treat the empirical conclusions as illustrative. The observation about intermediate tie strengths is worth reporting.\n\nBottom line: this deserves serious refereeing. The matroid part is solid, and the IC algorithm is likely fixable into a correct (1-1/e) guarantee. I'd engage with it and would cite the Section 3 reduction.","headline":"Clean matroid-intersection result with a promising but currently under-proved IC rounding algorithm—worth a careful referee.","tokens_in":23788,"tokens_out":9024,"would_cite":true,"duration_ms":94404,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W25","90C27","91D30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Shared ad campaigns: optimal revenue within factor 1/2","keywords":["multi-product influence maximization","social advertising","submodular maximization","matroid intersection","reverse reachability","dependent rounding","Independent Cascade model","approximation algorithms"],"falsifier":"Find a small Independent Cascade instance, for instance the star network from the paper's integrality-gap construction, and run the proposed LP-rounding repeatedly. Measure, for one reverse-reachable set $R_i$, the probability that no seed lands in $R_i$ and compare it with the product of the individual probabilities that each node in $R_i$ is left unseeded. If the former ever exceeds the latter, the negative-correlation step in the proof of the $1-1/e$ claim is false, and that claim must be weakened.","tokens_in":22671,"feed_emoji":"📣","tokens_out":8705,"duration_ms":85662,"temperature":0.7,"pith_summary":"The paper asks how a social network should place sponsored ads for many paying advertisers when no user should be exposed to too many sponsored ads. It claims that, under the general threshold model with monotone submodular local influence functions, this coordination problem reduces to monotone submodular maximization over the intersection of two matroids, and therefore admits constant-factor polynomial-time approximation algorithms. It then specializes to the Independent Cascade model, where combining reverse-reachable sets with LP rounding yields a more practical $1-1/e$ approximation, with advertiser budgets enforced in expectation. A careful reader would care because the reduction turns an awkward multi-party constraint problem into standard optimization machinery, and the experiments map when competition between advertisers is most costly.","feed_headline":"Shared ad campaigns: optimal revenue within factor 1/2","feed_subtitle":"Matroid constraints coordinate advertisers on a shared network; IC model gets a 1-1/e guarantee.","key_machinery":"The argument's load-bearing construction is a lifted network with one copy $u_{v,j}$ for each advertiser $j$ and node $v$. Choosing a subset of these copies is equivalent to choosing seed sets for all advertisers; the per-user exposure cap $r_v$ becomes a partition matroid on the copies $X_v$, and the per-advertiser caps $K^{(j)}$ together with the total seed cap $K$ become another partition matroid (truncated when needed) on the copies $U^{(j)}$. Submodularity of influence in the general threshold model makes the revenue functions submodular, so the whole problem becomes a known optimization task. For the Independent Cascade case, a second mechanism carries the practical algorithm: random reverse-reachable sets (the sets of nodes that can reach a randomly sampled target through the random live-edge graph) estimate influence as a maximum-coverage objective, and a dependent-rounding scheme turns the resulting LP solution into integral seed choices while preserving marginals and negative correlation.","core_discovery":"The central claim is that coordinating several ad campaigns on one network, under per-user sponsored-ad exposure caps and advertiser seed-set limits, reduces to maximizing a nonnegative, monotone, submodular function subject to the intersection of two matroids; without per-advertiser seed caps, the feasible region collapses to a single truncated partition matroid. Because the resulting revenue functions are submodular, known approximation algorithms apply: a local-search algorithm gives essentially $1/2$ for the two-matroid case, continuous greedy gives $1-1/e$ for the single-matroid case, and simple greedy gives $1/2$. For the Independent Cascade model, the paper contributes a more efficient $1-1/e$ algorithm based on random reverse-reachable sets and dependent LP rounding, with the caveat that advertiser budgets are only guaranteed in expectation. The paper also establishes experimentally that competition reduces host revenue most when advertiser influence networks are similar and when tie strengths are intermediate.","pith_inferences":["The clean matroid reduction suggests that the experimental competition loss could be quantified as a normalized submodularity gap, and the swap-based similarity experiments could be converted into a predictor: measure the overlap of high-influence neighborhoods across advertisers and compare it with the observed payoff ratio.","The star-graph integrality gap indicates that exact per-run advertiser budgets are qualitatively harder than expected budgets; a natural testable extension is a post-processing step that swaps seeds to restore budget caps and measures how much of the $1-1/e$ guarantee survives.","Because the paper's IC proof assumes an extension of dependent rounding whose negative-correlation property is not proved, an immediate empirical check is to compare the rounding's observed coverage probability against the lower bound used in the proof on random IC instances; if the inequality fails, that guarantee would need repair while the matroid results stand.","If the similarity experiments generalize, platforms could choose which advertisers to co-schedule: advertisers with highly overlapping influential users should be scheduled separately, while those with disjoint influence neighborhoods can share a campaign wave."],"forward_implications":["A platform with arbitrary per-user ad caps and per-advertiser seed caps can coordinate any number of campaigns in polynomial time while keeping at least half of the optimal revenue; with only per-user caps, it can reach $1-1/e$.","The reduction is modular: any future improvement to submodular maximization under matroid intersection automatically improves coordinated ad campaigns, including versions with different costs for targeting seed nodes.","Under the Independent Cascade model, campaigns on networks of tens of thousands of nodes can be computed with a $1-1/e$ guarantee, though a single run may exceed an advertiser's budget; budgets hold on average across runs.","Experiments imply that the host's revenue loss from competition is predictable from network similarity and tie strength: similar influence networks and intermediate tie strengths produce the worst losses."],"supporting_citations":[{"why":"Supplies the advertiser-budget and exposure-payment model that this paper adopts and modifies.","marker":"[3]"},{"why":"Introduces the per-node sponsored-ad exposure constraint and per-advertiser seed-set limits used in the problem definition.","marker":"[11]"},{"why":"Contributes the observation that node exposure bounds plus a total seed bound form a truncated partition matroid, used for the single-matroid case.","marker":"[31]"},{"why":"Provides the local-search approximation algorithm for submodular maximization under multiple matroid constraints, yielding the $1/(2+\\epsilon)$ guarantee.","marker":"[24]"},{"why":"Provides the continuous-greedy algorithm for matroid-constrained submodular maximization, yielding the $1-1/e$ guarantee.","marker":"[6, 35]"},{"why":"Provides the simple greedy algorithm and its $1/(k+1)$ approximation for $k$ matroid constraints.","marker":"[14]"},{"why":"Introduces reverse-reachable sets and the sampling bounds used to reduce influence estimation to maximum coverage.","marker":"[4, 32, 33]"},{"why":"Supplies the dependent-rounding procedure with marginal-preservation and negative-correlation properties used by the LP-rounding algorithm.","marker":"[15]"},{"why":"Establishes submodularity of influence as a function of the seed set in the general threshold model, making the objective submodular.","marker":"[28]"},{"why":"Provides the equivalence between Independent Cascade diffusion and reachability in random graphs, which underlies the reverse-reachability technique.","marker":"[22]"}],"fun_headline_variants":["Coordinated ad campaigns: 1/2 approximation","Ad revenue maximization under matroid constraints","1/2 approximation for coordinated social ads","Submodular ad coordination: 1-1/e for IC","Practical ad coordination: greedy gives 1/2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Independent Cascade $1-1/e$ guarantee depends on the assumption that the final rounding step enforcing the total seed budget does not destroy the rounding's negative-correlation property; if that property fails, the guarantee does not follow, while the matroid-based results remain unaffected.","fun_headline_variants_meta":{"raw":{"variants":["Coordinated ad campaigns: 1/2 approximation","Ad revenue maximization under matroid constraints","1/2 approximation for coordinated social ads","Submodular ad coordination: 1-1/e for IC","Practical ad coordination: greedy gives 1/2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001616,"raw_usage":{"total_tokens":6497,"prompt_tokens":1076,"completion_tokens":5421,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":692,"completion_tokens_details":{"reasoning_tokens":5346}},"tokens_in":692,"tokens_out":5421,"duration_ms":38481,"temperature":1.0,"reasoning_tokens":5346,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:20:48.400843+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a small Independent Cascade instance, for instance the star network from the paper's integrality-gap construction, and run the proposed LP-rounding repeatedly. Measure, for one reverse-reachable set $R_i$, the probability that no seed lands in $R_i$ and compare it with the product of the individual probabilities that each node in $R_i$ is left unseeded. If the former ever exceeds the latter, the negative-correlation step in the proof of the $1-1/e$ claim is false, and that claim must be weakened.","supporting_citations":[{"cited_title":"Viral mar- keting meets social advertising: Ad allocation with minimum regret.Proc","cited_arxiv_id":null,"evidence_quote":"Supplies the advertiser-budget and exposure-payment model that this paper adopts and modifies."},{"cited_title":"Viral marketing for multiple products","cited_arxiv_id":null,"evidence_quote":"Introduces the per-node sponsored-ad exposure constraint and per-advertiser seed-set limits used in the problem definition."},{"cited_title":"Optimizing ad allocation in social advertising","cited_arxiv_id":null,"evidence_quote":"Contributes the observation that node exposure bounds plus a total seed bound form a truncated partition matroid, used for the single-matroid case."},{"cited_title":"Submodular maximization over multiple ma- troids via generalized exchange properties","cited_arxiv_id":null,"evidence_quote":"Provides the local-search approximation algorithm for submodular maximization under multiple matroid constraints, yielding the $1/(2+\\epsilon)$ guarantee."},{"cited_title":"Fisher, George L","cited_arxiv_id":null,"evidence_quote":"Provides the simple greedy algorithm and its $1/(k+1)$ approximation for $k$ matroid constraints."},{"cited_title":"Dependent rounding and its applications to approximation algorithms.Journal of the ACM, 53(3):324–360, 2006","cited_arxiv_id":null,"evidence_quote":"Supplies the dependent-rounding procedure with marginal-preservation and negative-correlation properties used by the LP-rounding algorithm."},{"cited_title":"Submodularity of influence in social networks: From local to global.SIAM Journal on Computing, 39(6):2176–2188, 2010","cited_arxiv_id":null,"evidence_quote":"Establishes submodularity of influence as a function of the seed set in the general threshold model, making the objective submodular."},{"cited_title":"Maximizing the spread of influence in a social network","cited_arxiv_id":null,"evidence_quote":"Provides the equivalence between Independent Cascade diffusion and reachability in random graphs, which underlies the reverse-reachability technique."}],"review_version":1}