| paper | d4-conf-wine-2016-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A deterministic ordinal universally truthful mechanism runs in polynomial time and achieves \(W(q)\ge \frac{k+1}{2k}\mathrm{OPT}(w)\ge \mathrm{OPT}(w)/2\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4.6
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), an integer \(k\), and ordinal rankings over types induced by a hidden symmetric metric \(w\), construct an ordinal, universally truthful mechanism that does not observe \(w\). It may divide each type's mass among \(k\) clusters, with \(q_{tj}\ge 0\), \(\sum_j q_{tj}=\mu_t\), and \(\sum_t q_{tj}=1/k\); each individual is assigned to exactly one cluster. Can it return \(q\) with expected welfare at least half the maximum feasible welfare, where \(W(q)=\frac12\sum_{j=1}^k\sum_{t,u\in T}q_{tj}q_{uj}w_{tu}\)?
A population with finitely many complete types, rational masses \(\mu\), type-level ordinal rankings, and a hidden symmetric metric pair-weight function \(w\). The decision variables \(q_{tj}\) give the mass of type \(t\) assigned to cluster \(j\), subject to the type-mass and equal-cluster-mass constraints; maximize \(W(q)=\frac12\sum_{j,t,u}q_{tj}q_{uj}w_{tu}\) using only the rankings and masses.
Covers Theorem 4.6's ordinal, universally truthful \(2\)-approximation for \(k\)-sum clustering; it leaves the paper's matching, densest-subgraph, and traveling-salesman results and its other clustering results unmirrored.
The strongest mirror I believe is the paper’s \(k\)-sum clustering result. Theorem 4.6, proved in this paper, says that there is an efficient ordinal, universally truthful \(2\)-approximation algorithm for \(k\)-sum clustering: partition \(N\) agents into \(k\) equal-sized clusters to maximize the sum of within-cluster edge weights, given only their rankings and assuming the hidden weights satisfy the triangle inequality. The proof uses a uniformly random equal-sized partition. The theorem is an approximation result, not a result putting exact optimization in P. The paper’s NP-hardness statements are cited in prose, not given as numbered hardness theorems, so I would not use them as anchors.
Here is the continuous problem I would hand to a prover. There is an atomless population with a finite type set \(T\), rational masses \(\mu_t\) summing to one, and \(k\) clusters, each of mass \(1/k\). A type is a complete description for this problem: its members have the same ordinal ranking over types, and pair weights are determined by the two types. The hidden symmetric pair-weight kernel \(w_{tu}\) obeys the paper’s triangle inequality; the mechanism sees the rankings, not the weights. Its input is \(T\), \(\mu\), \(k\), and the ordinal rankings. Its output is a partition of the population, compactly represented by masses \(q_{tj}\), where \(q_{tj}\) is the mass of type \(t\) placed in cluster \(j\), subject to
\[
\sum_{j=1}^k q_{tj}=\mu_t
\quad\text{and}\quad
\sum_{t\in T}q_{tj}=\frac1k.
\]
The welfare is
\[
W(q)=\frac12\sum_{j=1}^k\sum_{t,u\in T}q_{tj}q_{uj}w_{tu}.
\]
Although \(q_{tj}\) can be fractional, every actual person is assigned to one cluster; the fractions describe how the mass of a type is divided.
Call this Continuous Ordinal \(k\)-Sum Clustering: given that input, construct an ordinal, universally truthful mechanism whose expected welfare is at least half the best feasible continuous welfare. The equal-split solution \(q_{tj}=\mu_t/k\) already achieves that guarantee. Let
\[
D=\frac12\sum_{t,u\in T}\mu_t\mu_u w_{tu}.
\]
Equal splitting gives welfare \(D/k\). By the triangle inequality, any feasible partition has welfare at most \(2D/k\), so equal splitting is a \(2\)-approximation. It is efficiently computable in \(\tau=|T|\), \(k\), and the mass bit length \(L\); it ignores the rankings, so it is ordinal and truthful for every realization. The finite random partition in Theorem 4.6 has pairwise co-clustering probability \((N/k-1)/(N-1)\), which tends to \(1/k\) as the population grows. The continuous model is thus the high-multiplicity limit of the theorem’s own algorithm and objective.
The regime I have in mind is a large workforce or cohort being divided into equal-sized, diverse project teams. There may be millions of people but relatively few complete skill-and-preference profiles, with members of each profile interchangeable for the weights and rankings used by the problem. Here \(N\) is much larger than \(\tau\), and \(k\) is fixed or grows slowly enough that each team still contains a large population. The type masses are the natural quantities to report; dividing a type across teams at the mass level is precisely the aggregate description of assigning its individual members integrally.
I expect this mirror to be tractable, in the sense of the stated \(2\)-approximation question. It mirrors only Theorem 4.6’s \(k\)-sum clustering result; it makes no claim about the paper’s other problems or about exact hidden-weight optimization. Further questions include whether the factor \(2\) is tight for this continuous ordinal problem, and whether using the rankings can improve it while retaining universal truthfulness.
The weakest point is that the continuous theorem inherits a very simple, report-independent algorithm. Also, in a nonatomic model, one person’s report cannot change aggregate type masses, so individual truthfulness has little force. That limits what this mirror says about strategic mechanisms. It does not erase the computational question about ordinal approximation of the same metric welfare objective, and the finite high-multiplicity instances still have meaningful individual deviations. The authors should recognize the continuous problem as their clustering objective with a distributional population representation; the change is in the population and its mass allocation, not in the outcome criterion.
Theorem 4.6 is a genuine anchor, and I don’t see an honest way to defeat its best continuous mirror universally.
The strongest case against it is that the continuous guarantee is almost already visible in the paper’s finite algorithm. For a unit-mass population, let \(D=\tfrac12\sum_{t,u}\mu_t\mu_u w_{tu}\). Splitting every type evenly across the \(k\) clusters gives welfare \(D/k\). For any partition into clusters of mass \(1/k\), the triangle inequality bounds its welfare by \(2D/k\), so this report-independent split is a \(2\)-approximation. In the paper’s finite random partition, a pair’s probability of sharing a cluster tends to \(1/k\) as \(N\) grows. There is no new pricing problem or continuous-optimization technique here; the result is close to the limit of an algorithm the paper already gives.
There is also little strategic content in this particular mirror. An atomless agent cannot change the aggregate masses by misreporting, so individual truthfulness is vacuous. But the finite algorithm in Theorem 4.6 is already independent of reports, so that weakness is present in the anchor too.
Those points make this a weak candidate for a major new result, not an invalid or out-of-scope question. The population itself is continuous, and a workforce or large cohort divided into diverse teams can plausibly have many people across a small set of complete skill-and-preference types. The objective depends on pair weights, not personal identity, so aggregation preserves the information the question uses. Nor does the finite theorem establish that the continuous model has already been studied: it makes the continuous guarantee easy to anticipate, but that is not a novelty collision under the programme’s rules.
The best negative case, then, is about research priority: this mirror may add little beyond making the finite theorem’s limit explicit. It does not support the stronger claim that no worthwhile continuous mirror exists. The honest negative verdict is weak.
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.