| paper | d4-conf-ecai-2024-0210 |
| 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: \(\mathrm{NP}\)-complete, even with positive dyadic masses; polynomial-time solvable in \(m,\tau,\ell,L\) if and only if \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given a project set \(P\), horizon \(\ell\), and a support of \(\tau\) UP approval-trajectory types \(\theta\), each with binary-rational mass \(\mu_\theta>0\) summing to \(1\), is there an outcome \(o\in P^\ell\) such that \(u_\theta(o)=\sum_{t=1}^{\ell}\mathbf{1}[o_t\in S_{\theta t}]\ge 1\) for every supported type? Here each \(S_{\theta t}\) is a singleton project approval set.
A society is a finite support of complete approval trajectories with masses \(\mu_\theta\); each type receives the paper’s integral utility from the shared outcome sequence \(o\in P^\ell\), and the objective is \(\min_{\theta:\mu_\theta>0}u_\theta(o)\). The mass values specify population shares, while every represented type counts in the egalitarian minimum.
The mirror covers the EGAL-DEC hardness in Theorem 3.1 and the CP, timestep-parameterized hardness in Theorem 3.5. It leaves the paper’s strategyproofness, NOM, proportionality, price-of-proportionality, and other welfare results unmirrored.
My lead is a continuous version of egalitarian welfare maximization over temporal approval trajectories. A type \(\theta\) is a resident’s complete approval vector \((S_{\theta 1},\ldots,S_{\theta\ell})\). The society is a finite support of such types with positive rational masses \(\mu_\theta\) summing to \(1\). An outcome remains a sequence \(o\in P^\ell\), choosing one project at each timestep. Every resident of type \(\theta\) gets utility
\[
u_\theta(o)=\sum_{t=1}^{\ell}\mathbf{1}[o_t\in S_{\theta t}],
\]
so the continuous egalitarian welfare is
\[
\operatorname{EGAL}_\mu(o)=\min_{\theta:\,\mu_\theta>0}u_\theta(o).
\]
The mass is each type’s share of society; the minimum protects every represented resident, including those in a small type.
A plausible regime is a large city or school district making a sequence of public choices, with many residents but relatively few distinct approval trajectories. For example, a population of hundreds of thousands may have hundreds or thousands of recurring trajectories. Each trajectory type can represent arbitrarily many residents. This is a population distribution over complete preference types; the timeline and each per-date choice remain as in the paper.
The lead question is UP Continuous Trajectory EGAL-DEC: given \(P\), \(\ell\), a support of \(\tau\) types with binary-rational masses, and singleton approval sets \(S_{\theta t}\) at every timestep, is there an outcome \(o\in P^\ell\) with \(u_\theta(o)\ge 1\) for every supported type? A solution is a yes/no answer, with a sequence \(o\) as a certificate for yes.
Its anchor is Theorem 3.1, proved in this paper: EGAL-DEC is NP-complete even when every agent approves exactly one project at every timestep and the guarantee is \(\lambda=1\). The continuous version keeps exactly that guarantee, with each represented type required to receive at least one approved project. The theorem’s vertex-cover reduction transfers: turn each agent into a type and assign it mass \(1/n\), merging identical types if needed. The discrete minimum over agents then equals the minimum over positive-mass types. I expect hardness to transfer. This is a class B mirror: the finite problem embeds in the distributional one.
A second, prover-ready question is CP Continuous Trajectory EGAL-DEC, the same decision problem restricted so that every supported type approves at least one project at every timestep, with parameter \(\ell\). Its anchor is Theorem 3.5, also proved here: EGAL-DEC is W[2]-hard parameterized by the number of timesteps, even with complete preferences and \(\lambda=1\). The theorem’s Dominating Set reduction likewise becomes a distribution over approval-trajectory types by assigning each original agent positive mass. I expect W[2]-hardness to transfer for this restricted mirror too. A follow-up is whether additional structure on the trajectories—beyond complete preferences—yields useful algorithms or approximation guarantees.
The mirror covers the paper’s egalitarian welfare decision problem. It does not try to extend the paper’s strategyproofness or proportionality results; those need separate mirrors. The authors should recognize this as their problem in a high-multiplicity regime: the type records every approval relevant to the model, and all residents of that type have the same utility for every outcome. The masses specify the society while the objective keeps the paper’s worst-served-resident criterion.
The weakest point is that these hardness anchors do not show that continuity changes the answer. Under this egalitarian objective, the exact mass values do not affect feasibility once a type has positive mass; the reductions also use a growing number of distinct types. They establish the mirror and its hardness, rather than a tractability gain for small support. That limit is credible and useful: it identifies an expected boundary for continuization instead of claiming a benefit the results do not support.
The strongest negative case is that egalitarian welfare discards the distribution’s masses. For any society with support \(T^+\), make a finite profile with one agent for each type in \(T^+\). For every outcome \(o\),
\[
\operatorname{EGAL}_{\mu}(o)=\min_{\theta\in T^+}u_\theta(o).
\]
Conversely, a finite profile maps to a distribution by merging agents with identical approval trajectories. This is an exact correspondence for the UP and CP questions, including their outcome sets and feasibility conditions. Theorem 3.1 and Theorem 3.5 transfer, but their reductions use a growing number of distinct types. For these anchors, the computational input is the set of trajectories; the population shares have no role in the question.
That makes the proposed mirrors look like support-compressed versions of the paper’s existing problem, rather than new continuous optimization problems. Theorem 3.2 already gives an FPT algorithm in the number of agents, which becomes an FPT algorithm in the number of distinct trajectories after compression. This supports a skeptical view of the research payoff: a continuous formulation may mainly supply new notation and a high-multiplicity interpretation, without opening a distinct algorithmic question.
That argument does not defeat the anchors under the programme’s rules. A district with many residents sharing a modest number of approval trajectories is a plausible high-multiplicity regime, and requiring every represented type to receive positive utility is a coherent worst-served-resident objective. The fact that a small type counts as much as a large one is part of egalitarian welfare. Theorems 3.1 and 3.5 therefore remain valid mirrors; their reliance on many types is not itself a reason to reject them.
A more mass-sensitive question, such as maximizing a distribution-weighted \(p\)-mean of type utilities, would use the shares directly, and Section 6 already gives it a computational anchor. But that would broaden the target beyond the two results the other analyst selected. I cannot make an honest case that no worthwhile continuous mirror exists in any scenario. The support-only formulation is a reason to doubt how much new work these particular egalitarian mirrors warrant; it is not a sound basis for claiming the mirrors fail the programme’s test.
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.