| paper | d4-conf-aaai-2026-0398 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in binary input length: feasibility holds exactly when $\frac{B}{P}\sum_{j=1}^{\tau}\frac{\mu_jp_j}{u_j}\le\theta$. A direct exact algorithm uses $O(\tau L^2)$ bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a fixed finite set of municipality types \(T\), rational masses \(\mu_j\) summing to \(1\), resident counts \(p_j\), invitation caps \(u_j\), a letter budget \(B\) per unit of municipality mass, and a contact limit \(\theta\), does there exist a distribution over assignments \(a_j:[0,\mu_j]\to\{0,\ldots,u_j\}\) such that in every draw \(\sum_{j\in T}\int_0^{\mu_j}a_j(z)\,dz=B\), contacted mass \(\sum_{j\in T}|\{z:a_j(z)>0\}|\le\theta\), and \(\mathbb{E}[a_j(z)]=Bp_j/P\) for almost every \(z\), where \(P=\sum_{j\in T}\mu_jp_j\)?
A society is atomless mass over municipality types \(j\), each specifying resident count \(p_j\) and cap \(u_j\). Each municipality still receives an integral number of letters; the randomized decision selects measurable mass of municipalities of each type. The proposed feasibility criterion is \(Bp_j/P\le u_j\) for every \(j\) and \(B\sum_{j\in T}\mu_jp_j/(Pu_j)\le\theta\).
The paper's society consists of constituents, while this construction treats municipal units as the mass and scales campaign capacity with their count, so its fit to the paper's central regime remains uncertain.
fatal: False
The mirror covers Theorem 2's FEASIBLECITIES decision problem; it does not cover the optimization and approximation results for MINFEASIBLECITIES or the monotonicity and proportionality results.
My lead is a high-multiplicity version of FEASIBLECITIES, the paper’s named NP-hard decision problem.
The anchor is Theorem 2, proved in this paper: given city populations \(\vec\pi\), invitation caps \(\vec u\), a letter budget \(\ell\), and a limit \(t\) on contacted cities per draw, decide whether there is a distribution over allocations \(a\) with \(\sum_i a_i=\ell\), \(0\le a_i\le u_i\), at most \(t\) nonzero entries, and \(\mathbb E[a_i]=\pi_i\ell\) for every city. The theorem proves this problem NP-hard, by reduction from PARTITION.
Here is a continuous version I would ask the authors to recognize. Suppose register-holding municipalities come in a fixed set \(T\) of complete types. A type \(j\) specifies a municipality’s resident population \(p_j\) and invitation cap \(u_j\); all municipalities of that type are identical for this problem. Let \(\mu_j\) be the fraction of municipalities of type \(j\), with \(\sum_j\mu_j=1\), and let \(P=\sum_j\mu_jp_j\) be average population per municipality. The corresponding resident share of type \(j\) is \(\mu_jp_j/P\).
Atomless City-Sampling Feasibility takes rational \((\mu_j)_{j\in T}\), integer \((p_j,u_j)_{j\in T}\), a letter budget \(B\) per municipality, and a contact limit \(\theta\), the fraction of municipalities that may be contacted in any draw. Its society is an atomless mass of municipal units: type \(j\) occupies mass \(\mu_j\). A solution is a distribution over assignments \(a_j(z)\in\{0,\ldots,u_j\}\), for \(z\in[0,\mu_j]\), such that, in every draw, total letters are \(B\), and contacted mass \(\sum_j|\{z:a_j(z)>0\}|\) is at most \(\theta\). It must also satisfy \(\mathbb E[a_j(z)]=Bp_j/P\) for almost every municipality of each type. If invitations within a municipality are selected uniformly, this gives every resident the same invitation probability, \(B/P\).
This is the limit in which \(N\) municipalities have type frequencies approaching \(\mu\), the letter budget is \(NB\), and the contact limit is \(\theta N\). Municipalities remain the decision units, and each contacted unit still receives an integral number of letters within its cap. What becomes continuous is the population of indistinguishable municipal units. Fractional type mass is the co-modification required to express that limit; it does not make individual invitations fractional.
I expect this mirror to be tractable. The exact feasibility condition is \(Bp_j/P\le u_j\) for every type and
\[
B\sum_{j\in T}\frac{\mu_jp_j}{P u_j}\le\theta.
\]
For necessity, a type’s expected letters require at least its expected letters divided by its cap in contacted mass. For sufficiency, contact mass \(r_j=\mu_jBp_j/(Pu_j)\) of each type and give each contacted municipality \(u_j\) letters. The total letters are \(B\); randomizing which municipalities in each type are contacted gives every municipality the required expectation. A uniform random shift of an interval of length \(r_j\) around the type’s interval of mass \(\mu_j\) is one explicit way to do that. The decision is therefore checkable with \(O(|T|)\) rational arithmetic. This is a concrete Class A candidate: the finite PARTITION obstruction may disappear when repeated city types can be represented by divisible mass.
The regime I have in mind is a large jurisdiction, or repeated large-scale assembly campaigns, with many register-holding local units and relatively few exact population-and-cap profiles. The profiles are the types; their multiplicities grow with \(N\). The paper’s register-access bottleneck remains central, and equal resident chances, per-city caps, and a per-draw contact limit all survive.
The weakest point is the scaling. The paper’s example fixes 20,000 letters and 80 municipalities; this mirror scales both the letter budget and contact limit with the number of municipalities. It also treats municipal units as the population being continuized, with residents represented as weights. The authors may judge that too far from the paper’s regime, or require a stronger finite-to-continuous rounding result before accepting it as their problem. That is the right follow-up question: quantify the finite error when type multiplicities are large, and determine when the continuous feasibility condition yields an actual allocation for the finite instance. This case covers Theorem 2’s feasibility question; it does not claim to mirror the paper’s monotonicity or proportionality results.
Theorem 2 is a real computational anchor: it proves NP-hardness of a named feasibility problem. The strongest objection is about what its proposed continuum treats as the population. In the assembly, the people are the constituents; municipalities are named administrative units that control access to those people. To preserve the shared invitation cap and city-level lottery, a citizen’s type would need to include their municipality. That leaves the municipality-level decisions discrete. Grouping cities by population and cap instead makes municipalities—not constituents—the agents whose mass is being continuized. The paper already aggregates residents within each city into \(\pi_i\); turning that resident mass continuous adds no new city-allocation variables.
The proponent’s scaled construction is the strongest answer to this objection. It is mathematically coherent, and the paper’s constraints survive if a growing jurisdiction has many municipalities from a fixed set of population-and-cap profiles, while the letter budget and contact limit both grow with the number of municipalities. But that is a narrower regime than the paper’s motivating campaign: with a fixed letter budget and fixed number of contacts, the per-city expected invitations and the normalized contacted mass vanish as the number of cities grows. Avoiding that degenerate limit requires changing the scale of the campaign and replacing the finite count of contacted cities with a mass constraint. The resulting problem concerns many interchangeable jurisdictions, rather than a large constituent population served through a fixed administrative structure.
There is also a gap in the claimed bridge back to finite instances. The atomless construction can allocate any real mass of a city type to the contacted set. A finite instance must choose an integer number of cities, and its exact feasibility can depend on that rounding. The proposed \(O(|T|)\) condition therefore characterizes the continuum model; it does not by itself show when a large finite campaign inherits its yes/no answer. If the number of exact profiles grows with the instance, the reduction’s combinatorics may return.
These points make the mirror’s practical reach uncertain, but they do not defeat it. Many small municipalities can share exact profiles, and campaign budgets may scale with population. The continuum question is legitimate under the programme’s rules, and its simple answer cannot count against it. So the honest negative case is weak: it challenges whether the scenario is central enough to the paper’s problem, but it cannot establish that no worthwhile mirror exists.
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.