| paper | d4-conf-sagt-2018-0021 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L,\log(1/\delta)\) under the stated certified exponential-evaluation model. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_t\ge 0\), \(\sum_{t=1}^{\tau}\mu_t=1\), and \(q\) audience classes with rational weights \(w_j\ge 0\) and rates \(\lambda_{tj}\ge 0\), define \(\Sigma(a)=\sum_{j=1}^{q} w_j(1-\exp(-\sum_{t=1}^{\tau}\lambda_{tj}a_t))\) for coalition masses \(a\in[0,\mu]\). For rational \(0\le\eta\le\Sigma(\mu)\), determine the bit complexity, in \(\tau,q\), input length \(L\), and accuracy \(\delta\), of approximating the least \(r\in[0,1]\) for which there is a type-level per-capita allocation \(p\ge0\) satisfying \(\sum_t\mu_tp_t=\Sigma(\mu)\) and \(\sum_ta_tp_t\ge(1-r)\Sigma(a)\) for every \(a\in[0,\mu]\) with \(\Sigma(a)\ge\eta\). Return an additive-\(\delta\) approximation to the optimum and a \(\delta\)-feasible allocation in a specified weak-optimization model for the exponential terms.
A population divided into interchangeable types \(t\), each carrying mass \(\mu_t\), faces \(q\) audience classes. Selecting coalition mass \(a_t\) of each type produces Poisson aggregate spread \(\Sigma(a)=\sum_j w_j(1-\exp(-\sum_t\lambda_{tj}a_t))\). A type-level payment \(p_t\) gives coalition \(a\) total payment \(\sum_ta_tp_t\); grand-coalition payments sum to \(\Sigma(\mu)\), and only coalitions with \(\Sigma(a)\ge\eta\) earn profit.
The mirror covers continuous versions of the influence-game RLCV and ALCV questions anchored by Theorems 4 and 5. It leaves the core characterization, the special-case RLCV algorithm, and the LADV algorithm outside its scope.
The strongest mirror I see is a Poissonized, high-multiplicity influence game. Imagine \(N\) potential seed-side people, with \(N\) large compared with the number \(\tau\) of distinct types. A type is a complete influence profile: every member has the same rates of reaching the same audience classes. A coalition can contain any mass \(a_t\in[0,\mu_t]\) of type \(t\), where \(\mu_t\) is that type’s population mass and \(\sum_t\mu_t=1\). These are actual fractions of an atomless population, not probabilities of selecting named people.
Here is a concrete model. Let \(j=1,\ldots,q\) index audience classes with masses \(w_j\). Each selected unit of type \(t\) makes independent, infinitesimal influence attempts toward class \(j\) at rate \(\lambda_{tj}\). In the large-population limit, attempts to reach that class have Poisson intensity \(\sum_t\lambda_{tj}a_t\), so expected spread is \(\Sigma(a)=\sum_j w_j(1-\exp(-\sum_t\lambda_{tj}a_t))\). With threshold \(\eta\), coalition profit is \(F(a)=\Sigma(a)\) if \(\Sigma(a)\ge\eta\), and \(0\) otherwise. This is a natural weak-influence limit of independent-cascade reach: many interchangeable people each make a tiny contribution, while the coalition’s total mass determines the aggregate chance of reaching the audience.
A type-level allocation is a per-capita payment \(p_t\ge0\); coalition \(a\) receives \(\sum_t a_tp_t\), and the grand coalition must receive \(\sum_t\mu_tp_t=\Sigma(\mu)\). The paper’s two least-core questions then have direct continuous forms:
These are optimization questions on the underlying cooperative game, not on an encoding. A precise computational version can ask for an additive-\(\epsilon\) solution in the standard weak-optimization model for the explicitly given concave exponential \(\Sigma\).
The lead anchor is Theorem 4, proved in this paper by a reduction from SAT: *it is NP-hard to compute \(\mathrm{RLCV}(\Gamma_f)\), even under an influence cooperative game.* It is a good anchor because the result is specifically about the thresholded influence game, rather than only a general truncated-submodular oracle model. I expect the Poisson-RLCV\(_\infty\) question to be Class A. For fixed \(p,r\), finding a violated coalition amounts to maximizing \((1-r)\Sigma(a)-\sum_ta_tp_t\) over the box and the successful-coalition region. For \(r\in[0,1]\), the objective is concave, and the region \(\Sigma(a)\ge\eta\) is convex. That gives a convex-optimization route to pricing and hence to the least-core problem. Whether the precise weak-oracle and bit-complexity bounds are polynomial is part of the question.
A second worthwhile anchor is Theorem 5, also proved here: *the ALCV problem for influence cooperative games cannot be approximated within \(1.139\) under the Unique Games Conjecture.* The paper proves this by reducing MAX-CUT to ALCV and invoking the conjectured MAX-CUT inapproximability. I expect the continuous Poisson-ALCV\(_\infty\) problem to be Class A for a related reason: its violated-coalition search maximizes the concave function \(\Sigma(a)-\sum_ta_tp_t\) over the convex successful-coalition region. The open follow-up is whether the discrete \(1.139\) obstruction disappears in this high-multiplicity limit, and whether the same conclusion holds beyond this concave Poissonized regime.
The regime is many near-interchangeable seed-side people per type, with \(\tau\) and the number of audience classes much smaller than \(N\). The scale effect remains central: advertisers pay only once influence reaches \(\eta\). The model retains the paper’s population of potential influencers, expected influence profit, truncation, coalition deviation, and least-core notions. The change to per-capita rates and fractional type mass is the natural co-modification for that population limit. The authors could reasonably recognize it as a continuous version of their influence cooperative game.
My weakest point is that the paper’s reductions use discrete seed identities and graph structure. The mirror does not claim those reductions literally transfer; the Poisson limit smooths influence and may remove precisely the combinatorics responsible for hardness. Nor does this case cover all of the paper: it targets only the RLCV and ALCV hardness results for influence games, not the core theorem, the \(\eta=0\) RLCV algorithm, or LADV. The case stands as a focused question about whether those hardness results survive when the influential population itself becomes continuous.
The strongest negative case is that neither hardness theorem is about repeated, interchangeable players. Theorem 4’s SAT reduction gives seed nodes distinct literal, clause, and dummy-node roles; Theorem 5’s MAX-CUT reduction makes each seed’s neighborhood encode a graph vertex’s incident edges. To preserve those constructions as influence games, a type must retain the relevant network relationships. Merging players with merely similar aggregate influence rates can erase coalition overlap, which is central to both reductions. Keeping enough detail to preserve it can leave \(\tau\) growing with the instance, so these theorems themselves do not establish a high-multiplicity complexity landscape.
That is a real limitation of the proposed mirrors, but it does not defeat their better versions. The paper’s own influence setting admits a plausible regime of large cohorts with the same complete influence profile, facing a small number of audience classes. In a weak-edge limit, the expected spread can be \(\Sigma(a)=\sum_j w_j(1-e^{-\sum_t\lambda_{tj}a_t})\). This retains seed-side population mass, coalition deviations, influence profit, and the threshold. It is a new restricted regime rather than a limit of the SAT or MAX-CUT gadgets, but the programme explicitly allows a plausible scenario different from the paper’s hardness instances.
That regime gives meaningful versions of both anchors. For Theorem 4, one can ask for the relative least-core value when only coalitions with \(\Sigma(a)\ge\eta\) earn profit. For Theorem 5, set \(\eta=0\) and ask for the absolute least-core value. For fixed allocation and candidate value, pricing searches optimize a concave function over a convex box or successful-coalition region, suggesting a convex-optimization route. A careful weak-oracle and bit-complexity analysis remains to be done, but that is a worthwhile computational question; its potentially easier answer is not an objection under this programme.
So the honest negative case is narrow: the paper’s reductions encode individualized network structure, and its theorems do not themselves show that the same hardness survives—or even that the same gadgets make sense—at low support size. But I cannot honestly turn that into the requested universal claim. A repeated-cohort influence model is plausible and close enough to the paper’s stated problem to be recognizable as a continuous mirror. Neither “already done continuously” nor existing high-multiplicity work defeats it. The negative case is therefore weak against the two anchors’ strongest versions.
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.