| paper | Not in My Backyard! Temporal Voting Over Public Chores |
| authors | Edith Elkind, Tzeh Yuan Neoh, Nicholas Teh |
| venue | IJCAI 2025 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.7
statement extracted from the paper’s text layer
Input a finite project set \(P\), timesteps \([\ell]\), and an explicitly listed rational distribution \(\mu=(\mu_1,\ldots,\mu_R)\) over complete disapproval types \(D^r=(D^r_1,\ldots,D^r_\ell)\), with \(m=|P|\). Let \(\ell_+=|\{k:\bigcup_{r:\mu_r>0}D^r_k=P\}|\), \(D_\infty(\mu,o)=\max_{r:\mu_r>0}|\{k:o_k\in D^r_k\}|\), and \(\operatorname{OPT}_\infty(\mu)=\min_{o'\in P^\ell}D_\infty(\mu,o')\). Compute an integral outcome \(o\in P^\ell\) satisfying \(D_\infty(\mu,o)\le\min(m,1+R^2/\ell_+)\operatorname{OPT}_\infty(\mu)\) when \(\ell_+>0\); when \(\ell_+=0\), choose a project disapproved by no positive-mass type at each timestep.
A high-multiplicity temporal public-chores election with complete profile types \(D^r\), rational masses \(\mu_r\), integral project choices \(o_k\in P\), and support-maximum disutility \(D_\infty\); the decision variables are the project choices and the objective is the \(R\)-parameterized MIN-MAX approximation.
The mirror covers the Section 3 MIN-MAX approximation and feasibility results, chiefly Theorems 3.7 and 3.2, but leaves MIN-SUM, temporal-fairness prices, manipulation, online competitiveness, and later fairness results without direct mirrors.
The strongest mirror is a high-multiplicity version of the paper’s public-chores model, with residents grouped by complete temporal disapproval profiles. The projects remain indivisible and the outcome remains an integral sequence; only the population becomes a rational distribution.
Let \(P\) be the projects and let \([\ell]\) be the timesteps. A type \(r\) is a complete vector \(D^r=(D^r_1,\ldots,D^r_\ell)\), where \(D^r_k\subseteq P\) is the set of projects that type disapproves at timestep \(k\). A continuous society is an explicitly listed distribution \(\mu_1,\ldots,\mu_R\), with \(\mu_r>0\) and \(\sum_r\mu_r=1\). The mass \(\mu_r\) is the fraction of residents having that profile.
For an outcome \(o=(o_1,\ldots,o_\ell)\in P^\ell\), define
\[ d_r(o^{(t)})=\left|\{k\le t:o_k\in D^r_k\}\right| \]
and
\[ D_\infty(\mu,o^{(t)})=\max_{r:\mu_r>0}d_r(o^{(t)}). \]
This is deliberately a support maximum rather than an average: the paper’s MIN-MAX objective protects every individual, so a type with positive mass must impose the same constraint as each of its members. Clearing denominators in \(\mu\) produces exactly the corresponding finite electorate with cloned agents.
The most credible regime is a large municipality with millions of residents but comparatively few exposure profiles. Residents in the same neighbourhood, housing block, distance band, household structure, or employment pattern may have the same exposure to noise, traffic, crowding, and disruption from every candidate project at every scheduled timestep. Thus \(N\) can be very large while \(R\), the number of distinct disapproval profiles, is moderate. This is not a claim that every temporal-voting instance has low multiplicity; it is a concrete NIMBY regime in which the paper’s own public-chores interpretation becomes more natural after aggregation.
My lead anchor is Theorem 3.7, proved in this paper. It states that there is a
\[ \min\left(m,1+\frac{n^2}{\ell_+}\right) \]
approximation algorithm for the MIN-MAX objective, where \(\ell_+\) is the number of timesteps at which every project is disapproved by at least one agent.
The corresponding continuous problem is:
Continuous MIN-MAX Public Chores Approximation. Given \(P\), \([\ell]\), the rational type distribution \(\mu\), and the disapproval vectors \(D^1,\ldots,D^R\), output an outcome \(o\in P^\ell\) such that
\[ D_\infty(\mu,o)\le \min\left(m,1+\frac{R^2}{\ell_+(\mu)}\right) \operatorname{OPT}_\infty(\mu), \]
where
\[ \operatorname{OPT}_\infty(\mu)= \min_{o'\in P^\ell}D_\infty(\mu,o') \]
and
\[ \ell_+(\mu)= \left|\left\{k:\bigcup_{r:\mu_r>0}D^r_k=P\right\}\right|. \]
If \(\ell_+(\mu)=0\), the trivial zero-disutility case is handled separately.
The paper’s LP already gives the mechanism for this mirror. Replace one constraint for every named agent by one constraint for every positive-mass type:
\[ \min \eta \]
subject to
\[ \sum_{p\in P}c_{p,k}\ge 1 \qquad(k\in[\ell]), \]
\[ \sum_{k=1}^{\ell}\sum_{p\in D^r_k}c_{p,k}\le\eta \qquad(r\in[R]), \]
\[ c_{p,k}\ge 0. \]
Rounding the LP solution exactly as in the proof of Theorem 3.7 gives an outcome. The vertex argument now has \(R+\ell\), rather than \(n+\ell\), relevant constraints, and the averaging argument gives \(R\eta\ge\ell_+(\mu)\). Hence the paper’s proof yields the factor with \(R\) replacing \(n\). The result is tractable in the high-multiplicity regime: the running time and approximation guarantee depend on the number of distinct profiles, not the number of residents. This is a genuine algorithmic benefit even though the exact problem remains difficult.
The masses are not numerically visible in this particular objective, apart from determining which types are present. That is faithful rather than accidental: MIN-MAX asks that every resident be protected, so multiplying a type’s population cannot make its burden constraint disappear. The continuous contribution is compression of a huge cloned electorate into its finite profile support, together with an approximation guarantee governed by \(R\).
A second, complementary anchor is Theorem 3.2, also proved in this paper. It establishes that MIN-MAX-DEC is NP-complete even with \(m=2\), \(\gamma=2\), and a single constraint.
Its continuous counterpart is:
Continuous MIN-MAX-DEC. Given \(P\), \([\ell]\), a rational distribution \(\mu\) over disapproval types, and an ordered set
\[ A=\{(t_1,\lambda_1),\ldots,(t_q,\lambda_q)\}, \]
decide whether there exists \(o\in P^\ell\) such that, for every \((t_j,\lambda_j)\in A\),
\[ \max_{r:\mu_r>0}d_r(o^{(t_j)})\le\lambda_j. \]
A solution is the outcome vector \(o\), which can be checked in polynomial time from the explicit type support.
This problem is expected to be NP-complete under explicit rational-support encoding. Given any finite instance from Theorem 3.2, set \(\mu_r=n_r/n\), where \(n_r\) is the number of agents having type \(r\). Every feasible continuous outcome is then feasible for the cloned discrete electorate and vice versa. Thus the hardness transfers by rational-clone equivalence. The restrictions \(m=2\), \(\gamma=2\), and \(q=1\) belong to the source hard instances; the continuous formulation itself may be stated without them, or with an explicit population scale if one wants to reproduce the incidence bound exactly.
This second mirror is therefore Class B rather than Class A: the combinatorics live in the temporal project choices and disapproval profiles, not merely in the number of named residents. It is useful precisely because it marks the boundary of the relaxation. The continuous representation may eliminate redundant multiplicity, but it does not magically remove hardness that survives after cloning.
The two questions generate natural follow-ups. For the approximation problem, one should ask whether the factor \(\min(m,1+R^2/\ell_+)\) can be improved, whether exact optimization is tractable for structured exposure profiles, and whether a mass-sensitive objective such as a weighted quantile of resident disutility gives a different landscape. For the decision problem, one should determine the smallest number of distinct types needed for NP-hardness, classify parameterizations by \(R\), \(m\), \(\ell\), or \(q\), and identify whether any hardness remains when the profile support is fixed but the population masses have large binary descriptions.
The mirror covers the paper’s Section 3 welfare-optimization results, especially Theorems 3.7 and 3.2. I would not claim a direct mirror for the strategyproofness results, because a unilateral deviation by an atomless individual has zero mass and would require replacing individual manipulation by a positive-mass cohort deviation. Nor would I claim the online results without separately specifying how future type distributions and project availability are revealed.
The weakest point is that, for MIN-MAX, the actual values of \(\mu_r\) do not affect feasibility once they are positive. A sceptical referee could call this support compression rather than a fully mass-sensitive continuous theory. I would concede that limitation. The defence is that changing MIN-MAX into an average or quantile objective would no longer be the paper’s egalitarian problem. This is the faithful mirror: a population with millions of cloned residents, represented by a distribution over exposure types, retaining exactly the paper’s individual-protection semantics. Its contribution is not to fractionalize public chores, but to expose which results depend on named population size and which survive in the high-multiplicity limit.
The two anchors do not establish a substantive continuization. They establish, at most, a lossless quotient of the discrete instance.
For every temporal disapproval profile \(r\), the relevant type space is finite:
\[ \mathcal T=(2^P)^\ell,\qquad |\mathcal T|=2^{m\ell}. \]
Under the proposed MIN-MAX objective,
\[ D_\infty(\mu,o)=\max_{r:\mu_r>0}d_r(o). \]
Thus \(D_\infty(\mu,o)\) depends only on \(\operatorname{supp}(\mu)\), not on the masses. A type representing \(10^{-12}\) of the population constrains the outcome exactly as much as one representing \(90\%\), and changing masses arbitrarily while preserving support changes nothing. This is not objection to high multiplicity itself: it is a specific degeneracy caused by the paper’s support-sensitive \(L^\infty\) objective. The population has disappeared except for the question of which profiles occur.
The same remains true in the best geometric repair. If residents are indexed by location and one uses the natural continuum analogue,
\[ \operatorname*{ess\,sup}_{x\sim\mu} d_x(o), \]
the answer depends only on the essential support of the induced disapproval-profile distribution. Since disapproval profiles are finite, the location model collapses back to finitely many profile classes. Making masses matter would require replacing MIN-MAX by a quantile, expected disutility, CVaR, or another mass-sensitive objective. That could be worthwhile, but it would be a new welfare problem rather than a mirror of Theorems 3.2 or 3.7.
Theorem 3.7’s proof does indeed go through with \(R\) in place of \(n\). But this is exactly what one gets by deleting duplicate constraint rows from the paper’s LP. The resulting bound is
\[ \min\!\left(m,1+\frac{R^2}{\ell_+}\right), \]
yet every quantity in it—\(R\), \(\ell_+\), the LP, and the optimum—is determined by profile support. The theorem is therefore a useful compressed-input implementation result, but not a computational consequence of population mass. It would be unchanged if all profile frequencies were replaced by any other positive frequencies.
Theorem 3.2 has the same defect. The proposed feasibility problem satisfies
\[ \operatorname{Feas}(\mu)=\operatorname{Feas}(\nu) \quad\text{whenever}\quad \operatorname{supp}(\mu)=\operatorname{supp}(\nu). \]
Clearing denominators gives the original cloned electorate exactly, and quotienting a discrete electorate by identical profiles gives the proposed “continuous” instance exactly. The NP-hardness is therefore a hardness result about temporal project choices and profile incidence, expressed with a support encoding. That is not objectionable because hardness survives—Class B is legitimate—but no population-continuous phenomenon is being studied. The proposed questions about huge binary masses are vacuous for this objective, since the masses never enter feasibility.
The strongest possible repair is the normalized MIN-SUM objective
\[ W_\mu(o)=\sum_r\mu_r d_r(o), \]
which is a genuine high-multiplicity model. But it is simply the paper’s MIN-SUM objective after dividing by population size, and it separates timestep by timestep:
\[ o_k\in\arg\min_{p\in P} \sum_{r:p\in D^r_k}\mu_r. \]
It provides a sensible weighted baseline, not a new complexity landscape. Strategic results fare worse: an individual atomless deviation has zero effect on \(\mu\), so strategyproofness becomes vacuous; positive-mass cohort manipulation is a different notion.
The honest limitation is that this does not prove that no one could productively study the high-multiplicity NIMBY model. The \(R\)-parameterized implementation may be useful, and weighted welfare is legitimate. But the proponent has not shown a continuous mirror in the ChoCo sense: for both named anchors, the distribution is discarded before the computational problem begins.
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.