d4-conf-aaai-2026-2442

The strongest mirror is Theorem 5.1, proved in this paper. For every constant \(\xi>0\), it gives an efficient \((1+\xi,\beta)\)-approximation for Kemeny rank aggregation: under \(\varepsilon\)-DP, \(\beta=\widetilde O_\xi(m^{27/7}/(\varepsilon n))\); under \((\varepsilon,\delta)\)-DP, \(\beta=\widetilde O_{\xi,\delta}(m^{65/22}\sqrt{\log(1/\delta)}/(\varepsilon n))\). Here the cost is expected average Kendall distance, and the algorithm runs in time polynomial in \(n\) and \(m\). This is an algorithmic anchor: the paper has no numbered hardness result. Its introduction does state that Kemeny rank aggregation is NP-hard, citing earlier work, but that is an unnumbered claim and not my anchor.

My lead question is Support-Compressed Private Mass-Kemeny PTAS. An instance has \(m\) candidates; a population size \(N\); parameters \(\varepsilon,\delta,\xi\); and a distribution \(\mu\) supported on \(\tau\) rankings, given by binary rational masses with \(N\mu_\pi\) integral. A neighboring society moves mass \(1/N\) from one ranking type to another, corresponding to one person changing their ranking. The task is to give a randomized mechanism that outputs a consensus ranking \(\psi\in S_m\), is \((\varepsilon,\delta)\)-DP for that adjacency, and satisfies
\[ \mathbb E[K_\mu(\psi)]\le (1+\xi)\operatorname{OPT}_K(\mu) +\widetilde O_{\xi,\delta}\!\left( \frac{m^{65/22}\sqrt{\log(1/\delta)}}{\varepsilon N} \right), \]
where \(K_\mu(\psi)=\sum_\pi\mu_\pi K(\psi,\pi)\). The pure-DP version asks for the corresponding \(\widetilde O_\xi(m^{27/7}/(\varepsilon N))\) additive error. The continuous-computation target is runtime polynomial in \(m,\tau,L,\log N\), where \(L\) is the input bit length. That runtime is a proposed high-multiplicity question: Theorem 5.1 itself guarantees time polynomial in \(N\) and \(m\), not in the compressed input length.

This is a credible mirror because a ranking is a complete type for this task, and mass is the fraction of people with that ranking. Think of a large electorate ranking a fixed candidate slate: \(N\) can be very large while the number \(\tau\) of distinct ballots is much smaller. The target remains private consensus ranking over those people’s preferences. DP retains a per-person unit of size \(1/N\); it is a constraint on this population model, not a substitute for making the population continuous.

I expect this mechanism question to be tractable. The Kemeny objective factors through pairwise masses \(w_{uv}=\sum_{\pi:\,u\prec_\pi v}\mu_\pi\), which can be computed from the support. The resulting ordering objective is a bounded weighted feedback-arc-set instance, the structure used by the paper’s cited PTAS. The open computational issue in my formulation is whether the paper’s privacy and additive-error guarantees can be achieved on support-compressed input. The exact optimization version is different: the paper’s introduction notes NP-hardness even with as few as four input rankings, so hardness transfers through rational societies with \(\tau\le4\). That hardness is driven by the candidate set, not by population multiplicity.

This case covers Theorem 5.1’s central-model Kemeny result only. It does not claim a mirror for the footrule result, the local model, or the paper’s privacy-query machinery as a standalone problem. My weakest point is that the theorem does not establish the proposed support-sensitive runtime, and the exact nonatomic limit erases the per-person DP adjacency. The positive case is therefore for the high-multiplicity family with explicit mass granularity \(1/N\), whose core objective and privacy guarantee the authors should recognize as theirs.