d4-conf-ijcai-2019-1024

The strongest mirror is a continuous biOWA multi-winner election. A voter’s type is their complete grade vector \(v^t\in\{-T,\ldots,T\}^m\) over the candidates. The society is a rational distribution \(\mu\) over its \(\tau\) supported types, where \(\mu_t\) is the fraction of voters of type \(t\). For a committee \(S\) of size \(k\), type \(t\)’s satisfaction remains exactly the paper’s additive utility, \(u_t(S)=\sum_{c\in S}v^t_c\).

To define the same rank-sensitive aggregation for a continuum of voters, give the instance two rank-weight profiles, \(\nu^+=a_0^+\delta_0+a^+(q)\,dq\) and \(\nu^-=a_0^-\delta_0+a^-(q)\,dq\). Each density is a rational, nonnegative, nonincreasing step function, and each profile may have an atom at rank \(0\). Let \(Q_S^+(q)\) be the ascending quantile of the positive parts of voter satisfaction under \(\mu\), and \(Q_S^-(q)\) the descending quantile of the negative parts. The committee’s score is

\[ G(S)=\int_{[0,1]} Q_S^+(q)\,d\nu^+(q) -\int_{[0,1]} Q_S^-(q)\,d\nu^-(q). \]

The C-biOWA-MWE problem is: given the supported ballot types and their rational masses, \(k\), and the two rank profiles, return a size-\(k\) committee maximizing \(G(S)\). Its decision version asks whether some size-\(k\) committee has score at least a given rational threshold. The population is the continuous object; the candidate set and committee remain discrete.

My named anchor is Proposition 3, proved in this paper. It states that for every \(x\in\mathbb{R}^n\) and nonnegative decreasing weight vectors \(\alpha,\beta\),

\[ g_{\alpha,\beta}(x) =\min_{\tau\in\Pi}\sum_{i=1}^{n} \left(\alpha_{\tau(i)}x_i^+-\beta_{\tau(i)}x_i^-\right), \]

where \(\Pi\) is the set of permutations of \(\{1,\ldots,n\}\). Thus one shared permutation suffices to express the biOWA value as a linear minimum. The paper computes with this result: it derives an LP for the aggregation and uses it to formulate a MIP for biOWA-MWE. This is a formulation anchor, rather than a numbered complexity theorem; the paper’s NP-hardness claim appears in prose.

The mirror preserves a direct finite-population dictionary. For \(N\) voters, take rank-bin weights \(\alpha_i=\nu^+(((i-1)/N,i/N])\) and \(\beta_i=\nu^-(((i-1)/N,i/N])\), assigning any atom at zero to the first bin. The continuous score then agrees with the finite biOWA score. Conversely, a finite nonincreasing weight vector can be represented on its \(N\) rank bins by a nonincreasing step density. So the quantile integral is a way to aggregate voter mass while keeping the paper’s ranking-based treatment of gains and losses; it does not replace biOWA with an ordinary average.

A plausible regime is a large membership organization choosing a fixed-size council, where members use a common graded ballot format and many submit the same candidate-grade vector. For example, \(N\) may be in the hundreds of thousands while only dozens or hundreds of distinct ballot types occur. In this model, the grade vector is a complete type: two members with the same vector are indistinguishable for every utility the problem uses. This is precisely the paper’s Section 4 question—choosing a committee to maximize voter satisfaction with special treatment of negative evaluations—with the voter histogram expressed in masses.

I expect the exact problem to be Class B, with hardness transferring. Take two ballot types of mass \(1/2\), nonnegative grades, \(\nu^+=\delta_0\), and \(\nu^-=0\). Then \(G(S)\) is the smaller of the two types’ total committee utilities. The finite counterpart is the valid decreasing OWA vector \(\alpha=(1,0,\ldots,0)\), which selects the minimum utility; repeating each type across an arbitrarily large electorate leaves that minimum-selection objective unchanged. The paper says its biOWA-MWE problem is NP-hard through the min-max, or minimum-selecting-items, subproblem, citing prior work that establishes hardness with two scenarios. That hardness concerns selecting candidates, not having a small electorate, so taking the population to a continuum does not remove it. The article has no numbered NP-hardness result to use as an anchor; Proposition 3 is the numbered result I rely on, while the hardness discussion informs my expected direction.

This leaves useful follow-up questions: which restricted weight profiles or ballot domains admit exact algorithms; whether parameters beyond support size, such as committee size or special candidate structure, yield tractability; and what approximation guarantees survive when the minimum-selection subcase is present. Support size alone is unlikely to help: hardness already arises with two types, barring \(P=NP\).

The weakest point is that the paper gives each finite electorate its own pair of rank-weight vectors, whereas the mirror specifies coherent continuum rank profiles. That is a real co-modification needed to define rank aggregation over voter mass. The core hardness example is less exposed to it: the atom at rank zero reproduces the paper’s permitted first-rank-only weight vector at every electorate size. The authors could reasonably recognize this as a continuous-population version of their election problem, while still questioning how broadly the chosen family of rank profiles represents their full finite model.