| paper | d4-conf-aaai-2021-0467 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A polynomial-time algorithm returns a feasible binary-rational allocation \(x\) satisfying the stronger bound \(W(x)\geq\sqrt{1-1/e}\,\mathrm{OPT}-\epsilon\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Lemma 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type masses \(\mu_t>0\) summing to \(1\), community labels \(c(t)\), rational transmission rates \(\kappa_{st}\), a seed budget \(\beta\), and \(\alpha\in(0,1)\), let \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\beta\). Define limiting reached fractions by \(y_t=1-(1-x_t/\mu_t)\exp(-\sum_s\mu_s\kappa_{st}y_s)\), taking the least fixed point, and set \(\mu_c=\sum_{t:c(t)=c}\mu_t\), \(u_c(x)=\sum_{t:c(t)=c}\mu_t y_t/\mu_c\), and \(W_\alpha(x)=\sum_c\mu_c u_c(x)^\alpha/\alpha\). Does this typed-population welfare objective retain a monotone diminishing-returns property that yields a polynomial-time \(1-1/e\)-approximation to its maximum, with running time measured in \(\tau=|T|\) and the input bit length?
A sparse stochastic block population with a fixed finite set of exchangeable network-role types, rational masses \(\mu_t\), and transmission rates \(\kappa_{st}/N\) between individuals of types \(s\) and \(t\). The decision variables are seed masses \(x_t\), bounded by each type’s mass and a population-scaled budget. A mean-field cascade gives each type’s limiting reached fraction \(y_t\); community utilities are mass-weighted averages, and the objective is the paper’s isoelastic welfare \(W_\alpha(x)=\sum_c\mu_c u_c(x)^\alpha/\alpha\).
The mirror covers Lemma 1 and its role in greedy welfare maximization. It leaves the welfare-principle results, comparisons with existing fairness notions, and empirical findings unmirrored.
My strongest positive case is a mirror of Lemma 1, proved in this paper. It says that, in their influence maximization problem, any welfare function satisfying principles 1–5 is monotone and submodular as a function of the chosen seed set. The paper’s isoelastic welfare functions for \(\alpha<1\) are in this family: each community’s expected influence is monotone submodular, and applying an increasing concave welfare function preserves that structure. The authors then use the standard greedy consequence: a \(1-1/e\) approximation under a cardinality budget. That approximation guarantee is a consequence of the lemma and a cited submodular maximization result, rather than a separate complexity theorem proved here. I would use this as the sole anchor; the paper offers no named hardness result to anchor a hardness-transfer claim.
Lead mirror — Continuous Fair Influence Maximization on a Typed Population. An instance has a finite set \(T\) of complete, exchangeable network-role types, rational masses \(\mu_t>0\) summing to \(1\), a community label \(c(t)\) for each type, and a rational transmission-rate matrix \(\kappa\). Type includes community membership and every modeled difference in connectivity or seed eligibility. Members of a type have the same transmission law to every other type. A directed sparse block network has \(N\mu_t\) agents of type \(t\); each ordered pair from types \(s\) to \(t\) has an independent transmission opportunity with probability \(\kappa_{st}/N\). A cascade follows the paper’s independent-cascade process.
The decision is a seed-mass vector \(x\), where \(x_t\) is the fraction of the whole population selected from type \(t\), \(0\le x_t\le\mu_t\), and \(\sum_t x_t\le\beta\). In a finite population, this means selecting \(Nx_t\) agents of each type; in the limit it is a mass allocation. Let \(y_t(x)\) be the limiting expected fraction of type \(t\) reached by the cascade, averaging over network and cascade randomness. For this sparse block model it can be specified by the least fixed point reached from \(y_t^0=x_t/\mu_t\) under
\[
y_t^{r+1}
=1-\left(1-\frac{x_t}{\mu_t}\right)
\exp\!\left(-\sum_s \mu_s\kappa_{st}y_s^r\right).
\]
The expected influenced fraction in community \(c\) is \(u_c(x)=\sum_{t:c(t)=c}\mu_t y_t(x)/\mu_c\). For a chosen \(\alpha\in(0,1)\), the question is to find a feasible \(x\) maximizing
\[
W_\alpha(x)=\sum_c\mu_c\,\frac{u_c(x)^\alpha}{\alpha}.
\]
A solution is the mass vector itself, with the goal of a certified approximation to the best welfare. This keeps the paper’s underlying decision—where to place peer leaders to maximize group welfare under an influence process. The continuous object is the population and the seed budget, not the fractional utility or the randomness already present in the cascade.
The intended regime is a large public-health or preparedness campaign planned from block-level contact estimates: many residents, relatively few exchangeable roles, and a seed budget that scales with population. The paper’s Sitka study gives a concrete foothold: it models 5,940 people in 16 communities and estimates a stochastic block model because collecting the full citywide network is cumbersome. In a larger city or repeated cohort, the agent count \(N\) can grow while the number of modeled types \(\tau\) remains fixed or modest. Since community alone need not make agents identical, types should split a community when seed eligibility or its connectivity profile differs.
I expect this mirror to be Class A for approximation, not to make exact optimization automatically easy. At finite \(N\), expected spread remains monotone submodular, and restricting seed choices to exchangeable type counts gives diminishing returns in those counts. The natural continuous limit is a diminishing-returns welfare objective, so continuous submodular optimization is a credible route to the same \(1-1/e\)-style guarantee with a number of variables governed by \(\tau\), not \(N\). The paper’s lemma supports this route, but does not prove the limit or a polynomial-time mean-field evaluator. Establishing those bit-complexity bounds—especially near cascade phase transitions—is a further question. Exact optimization may still be hard. Other questions include whether a discrete-to-continuous approximation error can be bounded explicitly, and which network parameters permit stronger guarantees.
The scope is Lemma 1’s welfare-based seed allocation and its greedy approximation rationale under independent cascade. It does not mirror the paper’s axiomatic impossibility propositions, its fairness taxonomy, or its experimental comparisons as separate problems. Nor does it claim that group utilities being fractions already makes the paper continuous.
The weakest point is that the paper’s formal problem takes a realized graph as input, whereas this mirror plans against a stochastic block network specified by type masses and transmission rates. That removes individual realized-neighborhood information, so it is not a mirror of every fixed-graph instance. I think the case survives for the block-population regime: the paper itself studies SBM networks and uses estimated block parameters in its Sitka application. The authors could plausibly recognize this as their welfare-based intervention problem in a high-multiplicity regime, while still rejecting it as a replacement for their general graph-specific formulation.
Lemma 1 is the paper’s strongest computational anchor, but it is a structural result about seed sets in a *realized graph*. A vertex’s marginal influence depends on its position in the graph and on how its reachable paths overlap with those of other seeds. Community membership, degree, or an SBM block generally does not capture that information. If types must preserve the fixed graph’s relevant structure, they will usually be nearly singletons: \(\tau\) grows with \(N\), and seed masses are just multiples of \(1/N\). That gives no useful high-multiplicity compression. The paper’s Sitka example does not remove this obstacle: its block model estimates are used to generate networks for experiments, while the formal optimization still takes a graph and selects individual vertices.
The proponent’s sparse-SBM formulation is the strongest repair. It defines a coherent different input: optimize seed fractions for a random network specified by block masses and transmission rates. Within that model, the mean-field limit and a submodular approximation guarantee are plausible. But the move that makes types complete also changes the decision problem: it averages over network realizations instead of choosing seeds for a known graph. It removes precisely the vertex-level bottlenecks and overlaps that govern the paper’s objective. The resulting question may be valuable, but it is an ex ante intervention-design problem for a network ensemble, not a low-support version of the paper’s fixed-graph problem. A graphon or repeated-block variant faces the same choice: preserve realized topology and retain many types, or summarize it and change the input model.
There is a further limit to what Lemma 1 supplies. It proves submodularity; the \(1-1/e\) guarantee comes from a standard greedy result. A continuous mirror of that anchor would therefore mainly transfer a generic approximation rationale. It would not, by itself, expose the kind of new pricing problem or algorithmic boundary that makes a continuization result especially informative.
This is the best negative case I can make, but it does not defeat the ensemble mirror outright. The paper itself motivates its Sitka study with an estimated SBM because the full network is unavailable, so its authors could plausibly recognize seed-mass optimization under that model as their intervention problem. If that recognition is enough to pass the programme’s gate, the proponent’s anchor survives. The honest weakness in the case against is that no modelling argument here rules out a useful continuous question; it only shows that preserving the paper’s realized-graph problem and obtaining a small complete type space are usually in tension.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.