| paper | d4-conf-ecai-2025-0359 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The worst-case approximation ratio is \(R=+\infty\), both in general and when \(m=\tau=3\), all project pairs conflict, and \(T=\{\{1\},\{2\},\{3\}\}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite project set, rational positive project costs, a rational budget, pairwise project conflicts, and a rational distribution \(\mu\) over approval types, does Modified UG have a finite worst-case approximation ratio for maximizing \(\operatorname{SW}_{\mu}(W)=\sum_t\mu_t|t\cap W|\)? Here \(W\) is an integral feasible project set, and Modified UG scans projects in descending order of \(\sum_{t:p\in t}\mu_t/\operatorname{cost}(p)\), adding each when feasible. In particular, does the ratio remain unbounded with three projects, all pairs conflicting, and support on three singleton approval types?
A continuous population is a finite-support distribution \(\mu\) over approval types \(t\subseteq P\). The planner chooses an integral project set \(W\), feasible under the budget and conflicts, to maximize expected additive approval welfare \(\sum_t\mu_t|t\cap W|\); Modified UG orders projects by marginal approval mass divided by cost.
The witness couples a vanishing approval mass to a project cost of order \(\delta^2\), so increasing population alone at fixed project costs does not create the gap; additive utility also reduces the type distribution to project approval marginals. The proponent permits costs to vary across instances, preserving the stated mirror, but this limits its relevance to multiplicity-driven complexity.
fatal: False
The mirror covers Proposition 1 and the conflict-aware Modified UG allocation rule. It leaves the LLM experiments, prompt strategies, preference inference, and model-performance metrics aside.
The paper gives no named NP-hardness, polynomial-time, or parameterized-complexity result. Its strongest formal computational anchor for a continuous mirror is Proposition 1, proved in Appendix C.1. It says that there are participatory-budgeting instances for which the ratio of optimal social welfare to the welfare returned by the Modified Utilitarian Greedy algorithm is unbounded: for a family indexed by the number of voters \(n\), that ratio tends to infinity as \(n\to\infty\). The proof uses three projects, makes every pair incompatible, and gives the projects costs \(\epsilon,\epsilon,\beta\). Two voters support one cheap project each; the other \(n-2\) voters support the project costing \(\beta\). With a tie broken in favor of a cheap project, greedy selects it and earns welfare \(1\), while the expensive project earns welfare \(n-2\).
My lead mirror is Continuous Modified-UG Gap\(_\infty\). Its underlying allocation instance consists of a finite project set \(P\), rational project costs, a rational budget \(\beta\), pairwise project conflicts, and a finite support distribution \(\mu\) over approval types \(t\subseteq P\), with rational masses summing to \(1\). A type is a complete approval ballot; its mass is the fraction of the population casting that ballot. The decision is an integral project set \(W\subseteq P\), feasible under the budget and conflicts, maximizing
\[
\operatorname{SW}_{\mu}(W)=\sum_t \mu_t\,|t\cap W|.
\]
The Modified UG rule orders projects by weighted approval \(\sum_{t:p\in t}\mu_t\) divided by cost, then greedily adds feasible projects.
The associated gap question is: for every integer \(K\), can one give a rational instance with \(\operatorname{OPT}_{\mu}/\operatorname{SW}_{\mu}(W_{\mathrm{UG}})\ge K\)? A witness is completely specified by three projects, budget \(1\), pairwise conflicts among all three, and three types \(t_1=\{p_1\}\), \(t_2=\{p_2\}\), \(t_3=\{p_3\}\), with masses \(\delta,\delta,1-2\delta\), where \(\delta=1/(K+4)\). Set costs to \(\delta^2,\delta^2,1\), and break the \(p_1,p_2\) tie in favor of \(p_1\). Greedy selects \(p_1\), with welfare \(\delta\); the optimum selects \(p_3\), with welfare \(1-2\delta\). The ratio is \(K+2\). Thus a solution for each \(K\) is the rational instance and the corresponding greedy and optimal allocations.
The regime is a large citywide participatory budget: many residents submit ballots from a relatively small set of recurring approval patterns. Projects and their costs are common to the decision maker; residents sharing an approval set are indistinguishable for this welfare calculation. Here \(N\), the number of residents, can grow while the support stays at three types. This is a plausible high-multiplicity version of the paper’s PB-with-conflicts setting, and the authors could recognize it as a question about the same allocation rule and welfare objective. In fact, the witness uses masses that are just normalized finite voter counts.
I expect the unbounded gap to persist. In the programme’s trichotomy, this has the same direct-embedding flavor as Class B, but Proposition 1 is an approximation result, not a hardness result, so I would not label it Class B hardness. The further questions are whether restrictions on project costs or minimum type masses restore a constant approximation, and what the exact welfare-maximization problem’s complexity is when the input is given by \((m,\tau,L)\).
This mirror covers Proposition 1 and the paper’s conflict-aware PB model. It does not continuize the LLM experiments, prompt strategies, preference inference, or model-performance metrics. That is deliberate: the result it mirrors concerns the mathematical allocation rule, not an LLM’s ability to implement it.
My weakest point is that the proposed continuous statement is very close to a normalized version of the paper’s finite construction. It establishes that the bad approximation behavior survives the type-mass representation, but it does not, by itself, open a new complexity question or say much about continuous optimization technology. And the paper’s formal anchor is narrower than the programme’s ideal: there is no named complexity-class result here to ask whether continuization dissolves.
The strongest case against the proposed mirror is that Proposition 1 is an approximation failure driven by costs, not by population multiplicity. In the witness, the small group’s share is \(\delta\), and its project costs \(\delta^2\). The greedy rule therefore favors that project because its support-to-cost ratio is \(1/\delta\), even as its welfare contribution vanishes. With a fixed project menu and fixed positive costs, this particular gap cannot grow through population size alone: if the greedy rule selects \(p_1\) ahead of \(p_3\), then \(\mu_1/c_1\geq\mu_3/c_3\), which bounds \(\mu_3/\mu_1\) by \(c_3/c_1\).
There is also little type-level computation to study here. For additive approval utility,
\[
\operatorname{SW}_{\mu}(W)=\sum_{p\in W}\Pr_{t\sim\mu}[p\in t].
\]
The allocation and Modified UG depend only on the marginal approval mass for each project; correlations among ballots and the support size \(\tau\) disappear. The proposed continuous witness thus translates the paper’s existing construction into normalized approval counts, with essentially the same proof and the same cost pathology. That makes it a thin contribution to a programme aimed at discovering how continuous populations change computational structure.
This case does not defeat the anchor under the programme’s stated standard. A citywide PB with recurring approval patterns is a credible high-multiplicity regime, the mass model is well posed, and Proposition 1 gives a named algorithmic approximation result to mirror. The normalization and the already-known answer do not make the question invalid. I would argue that this mirror is a low-priority, limited-payoff one; I cannot honestly argue that no worthwhile continuous mirror exists in any scenario.
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.