| paper | d4-conf-ijcai-2021-0312 |
| 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: Achieving a \(g^{1/2-\epsilon}\)-approximation is \(\mathsf{NP}\)-hard for every fixed \(0<\epsilon<1/2\), even with \(\tau=1\); no polynomial-time algorithm exists unless \(\mathsf P=\mathsf{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 36
statement extracted from the paper’s text layer
Given projects \(P\) with costs \(c(p)\), global budget \(B\), project groups \(\mathcal F\) with limits \(b(G)\), and a finite-support distribution \(\mu\) with binary-rational masses over approval types \(A\subseteq P\), choose a feasible bundle \(X\subseteq P\) maximizing \(U_\mu(X)=\sum_A\mu_A|A\cap X|\). For each fixed \(\epsilon>0\), is a polynomial-time \(g^{1/2-\epsilon}\)-approximation impossible unless \(P=NP\), even when \(g=|\mathcal F|\le m^2\) and \(m=|P|\)?
Approval types are subsets \(A\subseteq P\) with binary-rational masses \(\mu_A\) summing to \(1\). Choose project variables \(x_p\in\{0,1\}\) to maximize \(\sum_A\mu_A\sum_{p\in A}x_p\), subject to \(\sum_{p\in P}c(p)x_p\le B\) and \(\sum_{p\in G}c(p)x_p\le b(G)\) for each \(G\in\mathcal F\).
The edge-per-graph-edge groups in the hardness construction may be less representative of ordinary geographic or thematic budget limits; the proponent shows they fit the paper’s formal model but does not establish how common that structure is in practice.
fatal: False
The mirror covers the feasibility hardness in Theorem 11 and the approximation lower bound in Theorem 36. It leaves the paper’s tractability results, approximation algorithms, and other complexity results unmirrored.
The strongest mirror is a continuous-population version of Group-PB that keeps projects indivisible. A project bundle remains a set \(X\subseteq P\); continuity enters through the voter population and its aggregate approval utility.
Lead: Continuous Group-PB Decision. An instance has projects \(P\), integer costs \(c(p)\), a global budget \(B\), project groups \(\mathcal F\) with integer limits \(b(G)\), and a finite-support distribution \(\mu\) over approval types \(A\subseteq P\). Each positive mass \(\mu_A\) is a binary rational and the masses sum to one. Write \(\tau=|\operatorname{supp}(\mu)|\). For a bundle \(X\), its per-capita utility is
\[
U_\mu(X)=\sum_{A\in\operatorname{supp}(\mu)}\mu_A\,|A\cap X|.
\]
Given a rational threshold \(q\), ask whether there is a bundle \(X\) with \(U_\mu(X)\ge q\), total cost at most \(B\), and cost at most \(b(G)\) within every group \(G\in\mathcal F\). Types are complete approval descriptions; there are no voter-specific prices or budgets in this paper’s model. The mirror’s optimization version maximizes \(U_\mu(X)\) under the same project-budget constraints.
This is the same aggregation question the authors study: for a discrete electorate with \(n_A\) voters of approval type \(A\), set \(\mu_A=n_A/n\) and \(q=u/n\). Then \(U_\mu(X)\ge q\) holds exactly when the discrete utility reaches \(u\). Conversely, rational masses have a finite clone realization after taking a common denominator, potentially with exponentially many voters; that compact representation is the high-multiplicity setting.
A plausible regime is a large municipality with \(N\) residents and \(m\) recurring approval patterns, where each pattern is shared by many residents. In the hard instances below, \(\tau=m\) and masses can be uniform, so one can take \(N=m^3\): there are \(m^2\) residents of each type. Approval profiles then represent broad constituencies, while overlapping project groups represent geographic or thematic spending limits. This is a population scenario, not a claim that the project bundle itself should be fractional.
Theorem 11, proved in this paper, is the lead anchor. It states that Group-PB is NP-complete even when \(b_{\max}=1\), the largest group has size \(s=2\), the largest approval ballot has size \(\mathrm{app}=1\), and the group family has layerwidth \(\ell=3\); it is also NP-complete even when \(b_{\max}=1\), \(s=2\), there is one voter (\(n=1\)), and \(\ell=3\). The proofs reduce from Independent Set, using cited hardness results including [CC03].
The first restriction has a direct continuous reduction. Make one project for each vertex of the graph and a group \(\{p_v,p_w\}\) with budget \(1\) for each edge \(\{v,w\}\). Set project costs to \(1\), the global budget to \(k\), and give each singleton approval type \(\{p_v\}\) mass \(1/m\), where \(m\) is the number of vertices. Then \(U_\mu(X)=|X|/m\), so threshold \(q=k/m\) and budget \(k\) force \(k\) selected projects; the edge-group limits make them an independent set. This preserves the app and layerwidth restrictions. The one-voter clause has a continuous counterpart with all mass on the single type \(P\), so \(U_\mu(X)=|X|\) and \(q=k\). It shows that the project-group constraints can carry the hardness even in a one-type society.
I expect this decision mirror to be Class B: hardness transfers. In these reductions, the combinatorics lie in projects and overlapping group limits. The continuous question still asks whether a bundle meeting the authors’ utility threshold and budgets exists.
Continuous Max-Group-PB Approximation is a second, distinct mirror: use the same project, group, and society input, and ask for a feasible bundle maximizing \(U_\mu(X)\). An \(\alpha\)-approximation must return a feasible bundle with utility at least \(\mathrm{OPT}/\alpha\).
Theorem 36, also proved in this paper, is the second anchor. It says that for every \(\epsilon>0\), Max-Group-PB has no polynomial-time \(g^{1/2-\epsilon}\)-approximation unless \(P=NP\), even when the number of groups satisfies \(g\le m^2\). Its proof uses a reduction from Maximum Independent Set and the cited inapproximability result [Zuc07]. In the continuous version, assign mass \(1/m\) to each singleton type \(\{p_v\}\); put a size-two, budget-one group on each graph edge; set costs to \(1\) and the global budget to \(m\). Feasible bundles are exactly independent sets, and their utilities are their sizes divided by \(m\). Approximation ratios are preserved, with \(g=|E|\le m^2\). I likewise expect Class B for this anchor.
The authors should recognize these as their problems: only the explicit list of ballots has been replaced by its type frequencies, and the cost and budget constraints still act on the same projects. The paper itself motivates Group-PB with large cities and overlapping geographic or thematic groups. Existing high-multiplicity PB work supports this regime; it is not a novelty collision with the paper’s finite-voter model.
The scope here is deliberately limited to Theorem 11’s feasibility hardness and Theorem 36’s approximation lower bound. It does not claim that the paper’s tractability results automatically carry over. In particular, an open follow-on is whether the constant-group or hierarchical algorithms remain polynomial when approval masses are binary-encoded rationals: those produce binary-encoded rational project scores, unlike integer scores bounded by an explicitly listed voter count.
My weakest point is that the hardness reductions place the difficult structure in project selection and group constraints, and Theorem 11 even has a one-type case. They give little reason to expect population continuization itself to simplify this paper’s hard instances. The one-type result makes that limit explicit; the uniform-mass, many-type reduction supplies a genuinely large-population regime for the same result. The case is that this is still a faithful and useful mirror of the authors’ computational problem, including where continuity does not remove its hardness.
The strongest case against is about the likely payoff, not whether the mirrors are well posed. In this model, replacing voter counts with a distribution leaves the project bundle \(X\) indivisible. The society enters the objective only through project approval weights \(w_p=\sum_{A\ni p}\mu_A\); the group constraints and their combinatorics stay intact. That gives no obvious mass-transfer LP or pricing problem of the kind that motivates much of ChoCo’s continuous-optimization programme.
Theorem 11’s one-voter branch has little population content: all mass can be placed on the type approving every project. Its other branch is a stronger mirror. Put mass \(1/m\) on each singleton approval type, and the objective becomes \(|X|/m\); the threshold and edge-group limits reproduce the Independent Set question. Theorem 36 has the same kind of construction, so its approximation lower bound transfers as well. Both reductions use a group for each graph edge, with a cap that forbids selecting both endpoint projects. That structure may be a poor fit for ordinary thematic or geographic budgeting, though it is allowed by the paper’s model. A city could also have many residents sharing a small number of approval patterns, so the population regime itself is credible.
Those objections do not defeat either anchor. The edge groups are part of the problem the authors study, and the many-type construction gives a genuine high-multiplicity instance. The resulting question may add less to ChoCo’s continuous-optimization story than a mirror whose new variables admit an LP or convex formulation. But under the programme’s stated scope, low expected payoff is not a fundamental modeling obstruction. I cannot honestly support the universal claim that no worthwhile continuous mirror exists here; the negative case is weak, and both anchors survive it.
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.