| paper | d4-conf-sagt-2025-0010 |
| 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: NP-hard for every fixed \(0<\varepsilon<1\) to achieve approximation factor \(\tau^{1-\varepsilon}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite type set \(\mathcal T\) with rational masses \(\mu_t\) summing to \(1\), a finite state set \(\Theta\) with rational prior \(q\), and rational opinions \(a_{t\theta}\in[0,1]\), choose a finite public signaling scheme \(x_{\theta j}\ge 0\) with \(\sum_j x_{\theta j}=q_\theta\). For each signal \(j\), let \(p_j=\sum_\theta x_{\theta j}\) and, when \(p_j>0\), let \(z_{tj}=\sum_\theta a_{t\theta}x_{\theta j}/p_j\). What is the maximum expected covered population mass, \(\sum_j p_j\sum_{t\in\mathcal T}\mu_t\mathbf{1}[z_{tj}\ge 1/2]\)?
The no-influence subcase of public Bayesian persuasion, with a society represented by type masses \(\mu_t\), state-dependent type opinions \(a_{t\theta}\), and decision variables \(x_{\theta j}\); the objective is expected mass whose opinion lies in \([1/2,1]\).
The mirror covers the range-based persuasion results represented by Theorem 5 and the mass-weighted low-rank case of Theorem 2; it leaves the paper’s other sender objectives and its French–DeGroot and multidimensional extensions aside.
The cleanest mirror changes only the population. The paper already has real-valued opinions and probabilities over states and signals; those are not the continuization. Instead, let the society be a finite-support distribution \(\mu\) over customer or voter types. A type records everything that affects its agents’ behavior: their preconception in each state, susceptibility to influence, influence pattern, and desired opinion ranges. Each type has rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). A type-level FJ model can use an influence kernel \(K\), with equilibrium \(z_\sigma(t)=(1-\lambda_t)s_\sigma(t)+\lambda_t\sum_{t'}\mu_{t'}K(t,t')z_\sigma(t')\), assuming convergence.
This is a natural regime for a large marketplace: many customers fall into segments with the same state-dependent views of a product and the same willingness-to-buy threshold. If there are \(\tau\) segments and \(r\) customers per segment, then \(N=r\tau\); the mirror uses the segment masses, not individual customer counts. The seller still chooses the paper’s public Bayesian signaling scheme.
My lead anchor is Theorem 5, proved in this paper. It says that for the objective \(f_{\mathrm{na}}\), which counts agents whose opinions lie in their desired ranges, it is NP-hard to compute a signaling scheme with an \(n^{1-\varepsilon}\)-approximation, for every constant \(\varepsilon>0\). The proof reduces from Independent Set; it uses the independent-set inapproximability result of Zuckerman, cited as [44, Theorem 1.1].
The corresponding population question is Maximum-Mass Range Persuasion. Its input is a rational prior \(q\) over finitely many states \(\Theta\), a finite set of types \(\mathcal T\) with rational masses \(\mu_t\), and a rational preconception \(a_{t\theta}\in[0,1]\) for each type and state. Give every type the desired range \([1/2,1]\), and take the no-influence FJ subcase, as in the hardness construction. Choose a finite public signaling scheme represented by \(x_{\theta j}\ge 0\), with \(\sum_j x_{\theta j}=q_\theta\). For signal \(j\), let \(p_j=\sum_\theta x_{\theta j}\) and \(z_{tj}=\sum_\theta a_{t\theta}x_{\theta j}/p_j\). The task is to maximize the expected covered population mass, \(\sum_j p_j\sum_t\mu_t\mathbf 1[z_{tj}\ge 1/2]\); a solution is the signaling scheme attaining that value.
The reduction transfers directly. For a graph on \(n\) vertices, use one type and one state per vertex, uniform masses and prior, and the paper’s preconception values: \(3/4\) in a type’s own state, \(0\) in states corresponding to its neighbors, and \(1/2-1/(8n)\) otherwise. The types above threshold under any signal form an independent set. Replacing each type by \(r\) identical customers leaves the covered *mass* and approximation ratio unchanged. Thus the mirror is NP-hard to approximate within \(\tau^{1-\varepsilon}\) for every constant \(\varepsilon>0\), where \(\tau\) is the type support size. This is hardness that transfers: the graph is encoded in the type profiles and states. The mirror does not make the graph disappear.
A useful companion is Theorem 2, also proved here: when the paper’s preconception matrix \(S\) has constant rank, an optimal signaling scheme for every range-based objective can be computed in polynomial time. Its mass version asks for the optimal expected fraction of the population whose type opinions lie in their desired ranges, subject to the same constant-rank condition on the full-revelation type-by-state equilibrium matrix. For fixed rank, the paper’s cell-decomposition and LP approach gives a polynomial-time solution in the number of types, states, ranges, and input bit length. This is a tractability result for the same public-signal problem, now expressed over type masses.
The authors should recognize both questions: the sender, public signals, Bayesian updates, FJ equilibrium, and range objectives are unchanged. Theorem 5 itself works in the no-influence case, so using that case in the lead mirror preserves its actual problem rather than stripping away a feature its hardness proof uses. The mirror covers the paper’s range-based persuasion results, particularly the counting objective and the low-rank tractable case; it does not claim to continuize the state space, opinions, or time.
The soft spot is that the hard instances have \(\tau=m=n\): there is one distinct type per graph vertex, and one state per vertex. Replicating each type gives arbitrarily many agents per type, but does not reduce the combinatorial input. The paper therefore supports a credible high-multiplicity mirror, while this hardness result alone does not show hardness when the number of types is small or fixed. That points to a useful boundary question: how does complexity change with \(\tau\), the number of states, and the rank of the type-by-state matrix? In particular, the threshold problem seems amenable to a posterior-cell algorithm exponential in \(\tau\) and polynomial in the remaining input size, so the type support—not the continuum population size—is where this hardness appears to live.
I cannot make an honest case that defeats both anchors. The strongest reservation is about how much they establish specifically about population scale. In the Theorem 5 mirror, the hard instance has one type and one state per graph vertex. Replicating each type increases the headcount but leaves the signaling choices and approximation gap unchanged. The hardness is therefore tied to the number of distinct response profiles, not to having a large population. In the natural few-segment regime, Theorem 2 points the other way: fixed type support bounds the rank and gives polynomial-time optimization. That makes the proposed complexity story narrower than a claim that scale itself creates a new computational landscape.
But this is a reservation about the contribution’s reach, not a reason the mirrors fail. Theorem 5 has a named approximation-hardness result, and its no-influence case is a legitimate part of the paper’s persuasion model. A seller communicating with many customers in recurring segments is a sensible setting; the objective is covered population mass, and it does not require tracking individual identities. Replacing equal masses by general rational masses gives an even stronger mirror, with the same public signal and state-dependent type profiles. The independent-set construction then remains meaningful over the support of the population. Replication’s lack of effect is not, under the programme’s criteria, a disqualifier.
Theorem 2 also survives. Weighting each type’s contribution to the range objective by its mass preserves the question, and the low-rank condition has a plausible interpretation when customer views vary across states along a few shared dimensions. The result may be a direct weighted extension of the paper’s cell-decomposition method, but that makes it incremental rather than ill-posed. Nor does the FJ network create a decisive objection: network structure can make aggregation delicate, but the hardness anchor already holds with no influence, and the paper explicitly includes that subcase.
So the negative case is weak. The best argument is that these results do not show hardness driven by sheer population size, and their value depends on whether recurring, fully specified customer types are a compelling regime. That may narrow the paper’s fit with the programme, but it does not defeat either mirror; the material given offers no sound basis for claiming that neither is worthwhile.
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.