| paper | d4-conf-aaai-2018-0935 |
| 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→NP-hard discrete result → its continuous mirror
Answer: The exact continuous decision problem is $\mathrm{NP}$-hard already for $m=1$ and variable support size $\tau$. It admits an exact algorithm using $\tau^{O(\tau)}L^{O(1)}$ bit operations, and therefore is polynomial-time solvable for every fixed $\tau$. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), initial evaluations \(e_t\in[0,1]\cup\{\ast\}\), a rational symmetric contact kernel \(W_{tu}\), and a rational threshold \(\rho\), decide whether a feasible type-level intervention reaches revenue at least \(\rho\). For an initial voter type choose \(p_t=1\) and \(e_t\le s_t\le1\); for an initial nonvoter choose either \(p_t=s_t=0\) or \(0<p_t\le1\) and \(0<s_t\le p_t\), representing the fraction converted to voters and their aggregate rating mass. Define \(R_t=\frac{\sum_u\mu_uW_{tu}s_u}{\sum_u\mu_uW_{tu}p_u}\), require positive initial voter exposure for every type, let \(C=\sum_t\mu_t c_t\) with \(c_t=s_t-e_t\) for initial voters and \(c_t=s_t\) for initial nonvoters, and let \(U_0\) be the initial population-average personalized rating. Is there an intervention with \(C\le U_0\) and \(\sum_t\mu_tR_t-C-U_0\ge\rho\)?
A population distribution \(\mu\) over complete evaluation-and-contact types, with rational contact kernel \(W\). The decision variables \(p_t,s_t\) encode the post-intervention voter fraction and aggregate rating mass for each type; the objective is to meet a revenue threshold under the paper’s per-capita initial-utility budget.
The mirror covers Theorem 10’s BRIBE-NVKL reward-threshold problem for cohort-structured contact networks; it leaves the paper’s results on arbitrary exact neighborhoods and its greedy-strategy example outside that regime.
The strongest mirror is the paper’s main decision problem, BRIBE-NVKL, in a large, cohort-structured rating network. Imagine a platform with many customers but relatively few stable combinations of current evaluation and social exposure: for example, a cohort’s members all have no opinion yet and draw their peers from the same mix of other cohorts. Let a type be one such complete role: its initial evaluation, either \(e_t\in[0,1]\) or \(\ast\), and its contact profile in the network. The society is a distribution \(\mu\) over finitely many types, with rational masses \(\mu_t\) summing to one. In the intended regime, the number of customers is much larger than the number \(\tau\) of distinct roles.
A concrete network limit is a block model with a rational contact kernel \(W_{tu}\): a member of type \(t\) has contact exposure to type \(u\) proportional to \(W_{tu}\mu_u\). Take \(W\) symmetric to represent an undirected network, and require every type to have positive initial voter exposure. This describes dense or high-degree cohort networks, where the mix of neighbors is stable within a role.
For each type, let \(p_t\) be the fraction that vote after bribery, and \(s_t\) their aggregate rating per unit of type mass. If \(e_t\ne\ast\), then \(p_t=1\) and \(e_t\le s_t\le1\); the average bribe per member is \(s_t-e_t\). If \(e_t=\ast\), either \((p_t,s_t)=(0,0)\), or \(0<p_t\le1\) and \(0<s_t\le p_t\): bribe that fraction \(p_t\), each to rating \(s_t/p_t\), and leave the rest as nonvoters. The type-\(t\) personalized rating after the intervention is
\[ R_t=\frac{\sum_u \mu_u W_{tu}s_u}{\sum_u \mu_u W_{tu}p_u}. \]
The total spend per capita is \(C=\sum_t\mu_t c_t\), where \(c_t=s_t-e_t\) for initial voters and \(c_t=s_t\) for initial nonvoters. Let \(U_0\) be the population-average initial personalized rating. The decision problem asks whether there are feasible \((p_t,s_t)\) with \(C\le U_0\) and
\[ \sum_t\mu_tR_t-C-U_0\ge\rho, \]
for a rational threshold \(\rho\). A solution is the type-level fractions and scores, or equivalently the corresponding bribe amounts and fractions. This preserves the paper’s central choices and payoffs: the provider knows the network structure, can bribe voters or nonvoters, must stay within the initial-utility budget, and values the sum of customers’ personalized ratings minus bribes. It changes the finite graph into a continuum contact model so that large, exchangeable cohorts have a precise representation.
My anchor is Theorem 10, printed as “BRIBE-NVKL is NP-complete.” The paper proves it here: Proposition 5 gives membership in NP, and Proposition 6 gives NP-hardness by reduction from independent set in 3-regular graphs. In full, BRIBE-NVKL takes a known customer network \((C,E)\), an initial evaluation \(\mathit{eval}_0\), and a rational reward threshold \(\rho\). The legal inputs require every customer to have at least one voter in their neighborhood, including themselves as specified by the paper’s network convention. The question is whether there exists a budget-balanced strategy \(\sigma\) whose revenue is at least \(\rho\). The theorem thus establishes NP-completeness of deciding whether the attacker can attain a specified reward in the nonvoters-and-known-locations setting.
I expect the continuous question to be Class B: hardness transfers. In the paper’s reduction, the hard combinatorics are carried by adjacency in the source graph. A type-level contact matrix can retain that incidence structure even when each network role contains many agents. The population need not be the source of the complexity; the network’s pattern of interactions can remain in the continuous instance. This is a prediction, not a result: the reduction must be redone with fractional bribes allowed, and it must show that splitting a type’s mass cannot beat the threshold in ways unavailable to the discrete construction.
That is also the main follow-up question: for the reduction used in Theorem 10, do optimal continuous strategies still concentrate on all-or-nothing choices of the old-customer roles, or can fractional bribery make the problem easier? More broadly, does bounded \(\tau\) yield an exact algorithm, and what is the finite-to-continuous relationship for large block-regular networks—can discrete strategies approximate the continuous optimum, or conversely?
The weakest point is the network limit. The paper defines ratings using exact, named neighbor sets. A block contact kernel represents stable exposure proportions and suppresses individual-level variation in those sets; it fits dense or high-degree cohort networks much better than sparse networks with highly distinctive neighborhoods. Fractional mass choices may also dissolve the reduction’s all-or-nothing structure. So this is a serious mirror for a specific high-multiplicity regime, not a continuous version of every network covered by the paper.
The paper has one clear computational anchor: Theorem 10, BRIBE-NVKL’s NP-completeness. Propositions 1–4 describe revenue and bribing order, but they do not establish a separate complexity result to mirror.
The strongest objection is that the paper’s network is part of the input, and a customer’s personalized rating depends on their actual neighborhood. In a general graph, customers with the same initial evaluation can still play different roles because their neighbors differ. A faithful type would have to include that role; for many instances, this could leave almost every customer in a different type. The proposed contact kernel avoids this by replacing exact neighborhoods with shared exposure proportions. That is a substantial restriction, and a dense block model need not represent the sparse or irregular networks responsible for the paper’s reduction.
But this objection only narrows the regime; it does not rule out a worthwhile mirror. A platform could have large cohorts with the same initial evaluation and the same contact pattern across cohorts. Replicating each role in such a network gives a meaningful high-multiplicity setting. As the cohorts grow, normalized ratings are naturally described by masses and cohort-level exposure. This leaves nonvoter conversion, the budget, and the provider’s average payoff in the model. Fractional bribery could change the answer to the complexity question, and the paper’s reduction does not establish what happens in that limit. That is a reason to ask the continuous question, not a reason to discard it.
I therefore cannot honestly defeat the best version of the anchor. The proponent’s prediction that hardness transfers is unproved, and the particular \(W\)-kernel model needs care about which networks it represents. But the underlying mirror is well-posed for replicated, cohort-structured networks, with population mass as a meaningful quantity. The case against is strongest as a warning that this would cover a specific network regime, not the paper’s arbitrary graphs; it does not support the universal claim that no scenario is worth studying.
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.