Aggregation of Continuous Preferences in One Dimension

The strongest honest mirror is a high-multiplicity version of the paper’s linear aggregation problem. The paper does not itself continuize the population: it has a finite list of named voters, each supplying a continuous trajectory. But its voters already have exactly the kind of complete type that can be duplicated in a high-multiplicity society.

My lead anchor is Theorem 5, proved by the authors rather than cited from elsewhere (the conference version defers its proof to the full version): \((L,L,\infty,1)\)-CV is solvable in polynomial time.

Call the mirror Population Linear Forecast Aggregation. An instance consists of rational masses \(\mu_1,\ldots,\mu_\tau\), with \(\sum_j\mu_j=1\), and \(\tau\) linear voter types

\[ v^j(t)=a_jt+b_j,\qquad t\in[0,1]. \]

Type \(j\) represents all agents with the same ideal trajectory and every other parameter relevant to the problem. The mass \(\mu_j\) is their fraction of the population. The decision is a linear consensus curve

\[ W(t)=at+b \]

with values in \([0,1]\). The objective is the mass-normalized version of the paper’s utilitarian worst-time loss:

\[ \min_{a,b}\ \sum_{j=1}^{\tau}\mu_j \max_{t\in[0,1]}\left|v^j(t)-W(t)\right|. \]

A solution is an optimal pair \((a,b)\), together with its curve \(W\).

This is a literal high-multiplicity relaxation of the authors’ problem. If \(n_j\) named voters have type \(j\), then \(\mu_j=n_j/n\), and the original objective is just \(n\) times the displayed objective, so the set of optimizers is unchanged. The continuous instance can therefore describe millions of agents while its input contains only \(\tau\) types and their masses.

The problem is exactly an LP. Since the difference of two linear functions is linear,

\[ d_j(a,b)=\max\left\{ |b-b_j|, \left|a+b-(a_j+b_j)\right| \right\}. \]

Introduce variables \(d_j\) and minimize \(\sum_j\mu_jd_j\), subject to

\[ d_j\ge \pm(b-b_j),\qquad d_j\ge \pm\bigl(a+b-a_j-b_j\bigr), \]

for every \(j\), together with \(0\le b\le1\) and \(0\le a+b\le1\). Thus the continuous population problem is solvable exactly in time polynomial in \(\tau\) and the rational encoding length, independently of the total number \(n\) of agents.

A convincing regime is a large fleet of sensors, smart-home controllers, or forecasting agents. Many devices may run the same calibrated model and have the same ideal affine forecast or consumption trajectory. The number of devices can be enormous, while the number of calibration or behavioural classes remains modest. This is not merely a story imposed from outside: it is the paper’s own collaborative-forecasting and energy-aggregation setting, with duplicate voters compressed into types. The authors should recognise the mirror as their \((L,L,\infty,1)\) problem with the finite electorate represented by its empirical distribution.

I expect this mirror to be Class A. It does not claim that continuity creates hardness; it shows that population multiplicity can be removed without changing the underlying optimization, and that the resulting weighted problem is an explicit LP. It also opens natural follow-up questions: whether piecewise-linear trajectory types retain polynomial solvability, whether the \((L,L,\infty,q)\) approximation result of Theorem 3 extends with mass weights, and how continuous solutions round back to finite populations.

A second, broader anchor is Theorem 2, also proved by the authors rather than imported from a citation. It states that, for every input class \(\mathcal T_{\mathrm{input}}\subseteq C\), \((\mathcal T_{\mathrm{input}},C,1,1)\)-CV is polynomial-time solvable using the pointwise median construction.

The corresponding population problem is Population Median-Curve Aggregation. The input is a finite distribution \((\mu_j,v^j)_{j=1}^{\tau}\) over continuous trajectories \(v^j:[0,1]\to[0,1]\). The output is any continuous curve \(W:[0,1]\to[0,1]\) minimizing

\[ \sum_{j=1}^{\tau}\mu_j \int_0^1 |v^j(t)-W(t)|\,dt. \]

Equivalently, for every \(t\), \(W(t)\) is a weighted median of the values \(v^1(t),\ldots,v^\tau(t)\). Choosing the midpoint of the weighted-median interval gives a continuous selector. Under the same function-oracle model used in Theorem 2, the algorithm depends on the number of types rather than the number of agents. With piecewise-linear function encodings, one can instead construct the median curve by sweeping the finitely many pairwise intersections.

This is again Class A. It preserves the paper’s continuous time axis, continuous voter preferences, continuous output, and \(L^1\)-over-time utilitarian objective; the only new operation is replacing equal-weight named voters by population masses.

I would not use Theorem 1 as a positive anchor. Its NP-hardness for \((F_z,F_z,1,\infty)\)-CV, proved through CLOSEST STRING, can be copied into a weighted finite-support formulation, but the reduction appears to rely on many potentially distinct trajectory types. That would establish ordinary discrete hardness, not a compelling high-multiplicity phenomenon. Similarly, the paper’s general intractability result does not need to be mirrored for the positive case.

The weakest point is that the lead mirror is deliberately a restricted linear case with only two output parameters. The opposing analyst can argue that the computational content comes mainly from this low-dimensional restriction, not from population continuization. The answer is that the programme only requires one faithful continuous mirror of one named computational result. Here the restriction is not invented to make the problem easy: it is precisely the paper’s own \((L,L,\infty,1)\) realization, and its high-multiplicity interpretation is natural, exactly encoded, and algorithmically independent of the potentially huge electorate. The second mirror broadens the case to arbitrary continuous voter trajectories, at the cost of relying on the paper’s oracle representation.