| paper | d4-conf-atal-2018-0323 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the decision problem is in \(\mathrm{P}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.5
statement extracted from the paper’s text layer
Given an initial setting \(\alpha\) and a finite-support distribution of rational masses over types \(z=(x_z,A_z)\), where \(x_z\in[0,1]\) and \(A_z\subseteq[H]\), find a schedule \(y_1,\ldots,y_H\) minimizing \(\sum_{t=1}^{H}|y_t-y_{t-1}|\), with \(y_0=\alpha\), subject to \(\min_{z:t\in A_z,\,\mu_z>0}x_z\le y_t\le\max_{z:t\in A_z,\,\mu_z>0}x_z\) for every period with active positive mass; periods with none impose no constraint.
A society is a finite-support distribution \(\mu\) over occupant types \((x_z,A_z)\), with positive rational masses summing to one. The decision variables are facility locations \(y_t\in[0,1]\); periodwise Pareto efficiency constrains each location to the interval spanned by active types. The objective is total movement from the initial setting, \(\sum_{t=1}^{H}|y_t-y_{t-1}|\); mass values matter only through positive support. The dynamic target recurrence gives an optimal schedule.
The mirror covers Theorem 5.5’s replacement-cost optimality. It does not cover the static participation characterization, the dynamic truthfulness and participation results, or the shifted-median social-cost analysis.
The paper has no named NP-hardness or complexity-class result. Its strongest computational anchor is the optimization result in Theorem 5.5, proved here: the dynamic target rule minimizes replacement cost among all Pareto-efficient social choice functions, even those that are not online. For every agent set \(N\) and profile \(\theta\), it asserts
\[
\mathrm{RC}(\tau,\theta)\leq \mathrm{RC}(f,\theta)
\]
for every Pareto-efficient rule \(f\). The rule chooses each period’s facility location as the median of the previous location and the current period’s leftmost and rightmost agent locations.
A plausible high-multiplicity setting is temperature control in a large building: many occupants fall into a small number of cohorts with the same preferred temperature and schedule. Let a type be \(z=(x_z,A_z)\), where \(x_z\in[0,1]\) is the cohort’s ideal setting and \(A_z\subseteq[H]\) its active periods. An instance gives an initial setting \(\alpha\) and a finite list of types with positive rational masses \(\mu_z\) summing to one. The population may be huge while the number \(\tau\) of distinct types is modest.
Call the mirror Mass Dynamic Replacement. For each period \(t\), let \(S_t=\{z:\mu_z>0,\ t\in A_z\}\). If \(S_t\) is nonempty, define \(l_t=\min_{z\in S_t}x_z\) and \(r_t=\max_{z\in S_t}x_z\). The problem is to find a schedule \(y_1,\ldots,y_H\), with \(y_0=\alpha\), minimizing
\[
\sum_{t=1}^{H}|y_t-y_{t-1}|
\]
subject to \(l_t\leq y_t\leq r_t\) whenever \(S_t\) is nonempty. These constraints are exactly period-by-period Pareto efficiency for the cohort population; an empty period imposes no constraint. A solution is an optimal schedule and its replacement cost. The mirror’s rule is \(y_t=\operatorname{med}(y_{t-1},l_t,r_t)\), or \(y_t=y_{t-1}\) when no cohort is active. Scanning the support to find the period bounds and applying the recurrence takes polynomial time in \(H,\tau\), and the input bit length.
This is a credible population mirror: mass describes shares of a large society, and cohort types preserve the paper’s preferences and schedules. The result covers Theorem 5.5’s replacement-cost optimality. It does not claim to carry over the paper’s truthfulness or participation results: when individuals have zero mass, an individual report or departure cannot move the outcome, so those incentive questions change. Nor does the theorem show that continuization creates the tractability. Its optimal rule already works on finite profiles, and replacement cost depends on the positive-mass types’ extremes, not their mass values. That is the case’s main weakness, but the optimization question itself remains a natural, tractable continuous-population formulation of the paper’s dynamic facility problem.
The only anchor is Theorem 5.5, and its strongest weakness is that it is a pointwise optimality theorem for a rule, not a complexity result for a computational problem. Its continuous counterpart does not acquire a new population-dependent computation.
For any period, Pareto efficiency restricts the facility to the interval between the active population’s leftmost and rightmost locations. With types \(z=(x_z,A_z)\), the proposed mirror therefore uses \([\min x_z,\max x_z]\) over active positive-mass types. The replacement objective depends on the sequence of those intervals and the initial location; the masses matter only through whether they are zero. The paper already gives the optimal recurrence: project the previous location onto the current interval. So the continuous formulation is a reasonable large-building model, but its algorithmic input reduces to the same finite sequence of extrema. The measure’s mass values contribute no computational question.
A stronger, mass-sensitive variant could minimize a weighted sum of occupant discomfort and facility movement. But that changes the objective Theorem 5.5 establishes optimality for. With a finite support it becomes a piecewise-linear optimization problem over the period locations; adding strategic incentives would require a new account of deviations, since an individual of zero mass cannot affect the outcome. Those may be worthwhile questions in their own right, but they do not rescue this anchor: they add a different objective or incentive model.
That is the best negative case, and it has a real limit. The cohort scenario is credible, and a distribution over types is still a sensible instance regime. I cannot rule out that the authors would regard the mass-sensitive extension as their problem. The case against is therefore about the thin computational contribution of this particular mirror, not a convincing proof that no worthwhile continuous 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.