d4-journals-jair-2023-0023

The strongest mirror I see is the paper’s MaxMin phase, not its entire penalized objective. There is no numbered hardness theorem in this paper; my lead anchor is its approximation result for the underlying multiobjective seeding problem.

Consider a large public campaign on a social platform: millions of users, with seed budgets that grow with population size—for example, a fixed fraction of the population. Users fall into a modest number of exchangeable types, such as demographic group crossed with network role. Members of a type have the same group memberships, seed eligibility, and transmission rates to other types. Their contacts are generated by a common type-mixing model. Thus the regime has \(N\) agents and \(\tau\) types, with \(N\) much larger than \(\tau\). This is a stochastic network model, not a claim that a few demographic labels describe every detail of an arbitrary observed graph.

Here is the continuous problem I would hand to a prover: Mass-Fair Cascade Seeding (MFCS). Its input is a finite type set \(T\), type masses \(\mu_t\) summing to \(1\), overlapping group memberships \(a_{tj}\in\{0,1\}\), a symmetric transmission-rate matrix \(K\), and a seed-mass budget \(\kappa\). Write \(\mu_j=\sum_t a_{tj}\mu_t>0\) for group \(j\)’s population mass. Choose seed masses \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\kappa\). Define the cascade by \(q_t^{(0)}=x_t\) and, for each type \(u\), \(q_u^{(r+1)}=x_u+(\mu_u-x_u)\bigl(1-\exp(-\sum_t K_{tu}q_t^{(r)})\bigr)\). Let \(q(x)\) be the limit of this iteration and \(Q_j(x)=\sum_t a_{tj}q_t(x)\). The task is to find a feasible \(x\) maximizing \(\rho(x)=\min_j Q_j(x)/\mu_j\), and return both the seed-mass profile and its achieved worst-group influence fraction. This is the type-mass analogue of selecting seeds to maximize the minimum proportion of each group reached.

The anchor is Theorem 4.6, proved in this paper, though it uses the MWU method of Udwani (2021). In the paper’s discrete IC network, group influence functions are estimated from group-specific RR samples. For a threshold \(\alpha\), if each group’s RR sample count meets Equation (6), then, when the number of groups satisfies \(|\Psi|=o(k/\log^3 k)\), MWU at precision \(\lambda\) returns an \((\omega(1-1/e)^2-\lambda-\epsilon)\)-approximate solution to the corresponding multiobjective group-influence constraint problem, with probability at least \(1-1/\min_i n_i\). Here \(\epsilon\) is the influence-estimation error, \(\alpha n_i\) are the group thresholds, \(\omega\) approaches \(1\), and the sampled estimates are \(\hat I_{\psi_i}(S)=n_iF(S,R_{\psi_i})\). The RR-count condition depends on \(\alpha,\epsilon,\mathrm{OPT}_i,n_i\), and the union-bound term involving \(|\Psi|\) and \(\binom{n}{k}\). ABRIS-T uses this threshold procedure in a binary search to obtain its MaxMin solution. The theorem is proved for the paper’s discrete graph, not for MFCS; it is the computational result that makes MFCS a well-motivated continuous question.

I would provisionally expect MFCS to be Class A for a fixed or modest number of types and groups, as an approximation problem. The anchor’s leverage is the groupwise influence structure and the MWU-plus-sampling approach, not a special property of individual names. A continuous version could seek a comparable approximation using mass-based influence estimates and a continuous multiobjective optimization method. The key open work is to establish that the cascade model preserves the needed diminishing-returns structure and that the sampling and approximation guarantees survive the limit. I would not claim an exact polynomial-time optimizer from Theorem 4.6.

This mirror covers the fairness-first MaxMin problem in ABRIS-T. It does not mirror the paper’s complete objective combining total spread with a disparity penalty, nor its second greedy phase. Further questions include whether the limiting group-influence functions admit stronger guarantees than the discrete ones, and when the full total-spread/disparity objective is tractable in this type-mass model.

The soft spot is substantial: the paper optimizes seeds on a fixed, realized graph, while MFCS replaces that graph with an exchangeable type-mixing model. If network position varies sharply within types, a small \(\tau\) may erase exactly the structure that determines influence; encoding enough of that structure could make \(\tau\) large. The mirror is most convincing for campaigns planned against a stable, validated mixing model, with a seed budget that scales with population. In that regime, replacing individual counts by group and role masses is a credible version of the authors’ problem.