| paper | The Strategy-Proofness Landscape of Merging |
| authors | Patricia Everaere, S. Konieczny, P. Marquis |
| venue | JAIR 2007 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The opponent wins at the anchor gate: Theorem 3 is a semantic strategy-proofness classification, not a named computational result under the stipulated rule. The proposed positive-mass problem is well-defined, but it replaces unilateral manipulation by coalition manipulation; in the nonatomic limit, a single agent's report has measure zero. Thus the paper has no qualifying result to mirror, although the repaired coalition question is a plausible related research problem.
fails bit a — no named computational result to mirror
No anchor was greened; the decisive objection is that unilateral manipulation becomes null in the continuum, while positive-mass deviations create a different coalition-manipulation problem.
fatal: True
The proposed mirror covers only Theorem 3's Hamming-sum strategy-proofness boundary; it leaves the other strategy-proofness theorems, examples, and the paper's future complexity question untouched.
The paper has no named theorem of the usual \( \mathrm{P} \), NP-hardness, FPT, or parameterized-complexity kind. The strongest honest positive case therefore depends on treating its exact manipulation classifications as computational-social-choice anchors. If the gate excludes strategy-proofness theorems, then this paper has no qualifying anchor and cannot support a compliant ChoCo mirror.
My lead anchor is Theorem 3, proved in the paper. It states, in full, that for the Hamming-distance, sum-aggregation operator \( \Delta^{d_H,\Sigma}_{\mu} \):
Here \(idw\) rewards consistency of the merged result with \(K\), \(ids\) rewards the merged result entailing \(K\), and \(ip\) measures the fraction of merged models satisfying \(K\).
The continuous mirror I would propose is Minimum-Mass Hamming-Merge Manipulation\(_\infty\).
An instance consists of a finite propositional agenda \(P\), a consistent integrity constraint \(I\), a finite set of base-types \(T=\{K_1,\ldots,K_\tau\}\), and rational masses \(\mu_t\) summing to one. A type is a complete description of an agent relevant to merging: its propositional base \(K_t\), its satisfaction index, and any other parameters used by the instance. Thus agents of the same type are interchangeable. The worlds remain discrete, \(W=\{0,1\}^{|P|}\); only the population is continuous.
For a world \(\omega\), define the mass-normalized Hamming cost
\[ D_\mu(\omega)=\sum_{t\in T}\mu_t\,d_H(\omega,K_t), \]
where \(d_H(\omega,K_t)\) is the distance from \(\omega\) to the closest model of \(K_t\). The merged result is
\[ M(\mu,I)=\operatorname*{arg\,min}_{\omega\models I}D_\mu(\omega). \]
Choose a true type \(K\) of positive mass. A bloc of mass \(0<\alpha\leq\mu_K\) may jointly replace its truthful report \(K\) by any consistent base \(R\), producing
\[ \mu^{\alpha,R}=\mu-\alpha e_K+\alpha e_R. \]
The problem is to find the smallest \(\alpha\) and a report \(R\) such that
\[ i_\bullet\!\left(K,M(\mu^{\alpha,R},I)\right) > i_\bullet\!\left(K,M(\mu,I)\right), \]
where \(i_\bullet\) is one of \(idw\), \(ids\), or \(ip\). A solution is therefore an exact mass threshold together with a witnessing false report and the resulting merged model set. The decision version asks whether such a manipulation exists with \(\alpha\leq q\), for a rational threshold \(q\).
This is not merely fractionalizing outcomes. Worlds, bases, integrity constraints, and the merged result remain discrete. The only continuous object is the population distribution and the amount of mass that coordinates on a report.
The model has a natural high-multiplicity regime. Imagine a large distributed decision system—many local agencies, autonomous controllers, or organizational units—whose belief or goal bases are drawn from a small recurring catalogue of policy templates. There may be millions of agents but only, say, \(10\)–\(50\) distinct base-types. A bloc consists of many interchangeable units with the same true base and the same satisfaction criterion. This is exactly the paper’s anonymous multiset setting, viewed through normalized type masses.
The paper’s own counterexample already demonstrates that the continuous question is nontrivial. Take worlds \(00,01,10,11\), integrity constraint \(I=a\lor b\), true base
\[ [K_1]=\{00,01\}, \]
and another type with
\[ [K_2]=\{10\}. \]
With masses \(\mu_{K_1}=\mu_{K_2}=1/2\), truthful Hamming-sum merging selects \(10\), so \(idw(K_1,M(\mu,I))=0\). If the entire \(K_1\)-bloc of mass \(1/2\) reports the complete base \(K'_1=\{01\}\), the merged models become \(\{01,10,11\}\), giving \(idw(K_1,M(\mu^{1/2,K'_1},I))=1\). Thus the minimum profitable coordinating mass is \(1/2\) in this instance.
This is a genuine high-multiplicity analogue of Theorem 3’s manipulation problem: the finite profile with \(n_t\) copies of each type maps to \(\mu_t=n_t/n\), and multiplying all masses by a common denominator recovers the corresponding finite profile. Conversely, a rational mass instance can be expanded into a finite high-multiplicity society. The Hamming objective is unchanged up to the irrelevant factor \(1/n\).
I would expect the general succinct-formula version to be Class B rather than continuum-specifically hard. The important combinatorics lie in the propositional agenda, model sets, integrity constraint, and choice of report—not in the number of named agents. Hence any hardness of finding a profitable finite coalition should transfer through the rational-mass dictionary. In restricted versions where the worlds and type model-sets are explicit, the problem becomes a finite threshold problem: each candidate world’s cost changes affinely with \(\alpha\), so exact critical masses can be obtained by comparing linear inequalities. That restricted version is plausibly Class A.
The main follow-up questions are whether an optimal report can always be chosen complete, whether the paper’s Corollary 12—complete reports suffice for manipulation under \( \Delta^{d,\Sigma}_\mu \)—has a positive-mass analogue, and how the minimum mass changes under \(ip\), tie-breaking, approximation, and multiple coordinating reports.
The weakest point is fundamental: Theorem 3 concerns unilateral manipulation, whereas a nonatomic population makes a single individual’s deviation outcome-invisible. The bloc deviation is therefore a necessary co-modification, but it is not literally the theorem’s original quantifier. An opposing reader can reasonably call this a new coalition-manipulation problem. My answer is that this is precisely the population-level version of the paper’s question that remains substantive: the report action is unchanged, the merged-base objective is unchanged, and only the mass required to move the aggregate is made explicit. Still, if ChoCo demands a named complexity classification rather than a named strategy-proofness result, the honest verdict is that this paper does not clear the anchor gate.
The strongest negative is decisive at the programme’s anchor gate: Theorem 3 is not a computational result in the relevant sense. It is a semantic classification of when an operator is strategy-proof. It gives no decision problem, algorithm, complexity bound, parameterized result, or reduction. The paper’s only explicit complexity statement is a loose, unlabeled \(\Sigma^p_2\) upper bound in the conclusion, not a named theorem or classification. Thus Theorem 3 cannot itself support a compliant ChoCo mirror.
There is also a deeper mismatch in the proposed continuization. Let a finite profile contain \(n_t\) agents of base-type \(t\), with \(N=\sum_t n_t\) and \(\mu_t=n_t/N\). Theorem 3 concerns one agent changing her report, which changes the population distribution by
\[ \mu'=\mu+\frac{1}{N}(e_R-e_K). \]
In a nonatomic limit, that perturbation has measure zero. The aggregate Hamming objective
\[ D_\mu(\omega)=\sum_t\mu_t d_H(\omega,K_t) \]
does not change when one individual reports differently. Hence the literal continuous analogue of the paper’s strategy-proofness question says that every rule is strategy-proof, simply because no individual has positive aggregate influence. This is not a new complexity landscape; it is the disappearance of the strategic event.
Tie-breaking does not repair the problem canonically. A single agent may break an exact finite-population tie, but retaining that effect in the limit requires an additional infinitesimal-priority or tie-breaking structure that is absent from the paper and is not encoded by the population measure.
Theorem 3’s distinctive condition \(\#(E)=2\) also has no population-level counterpart. A profile with two agents and a profile with two million agents distributed over the same two bases can induce the same \(\mu\), while the theorem treats them as different finite regimes. Replacing \(\#(E)\) by the number of supported types would be a new theorem about type support, not a continuization of the stated result.
The proponent’s repair—allowing a mass \(\alpha>0\) of agents to change their reports—is coherent, but it changes the subject. It is coalition manipulation, not unilateral strategy-proofness. The paper itself identifies coalition manipulation as future work. Its example, where the entire \(K_1\)-bloc of mass \(1/2\) lies, is therefore a new coalition problem whose strategic unit is a bloc, not the individual agent studied by Theorem 3. Calling the bloc a “type” does not remove this change: it merely hides the coalition inside the type. Calling it one weighted agent changes the model in the other direction.
This is not an objection that the resulting answer would be easy, nor an objection to high multiplicity. Repeated belief-base templates in a large distributed system are a plausible high-multiplicity regime. The problem is that no choice of type space gives both properties simultaneously: an individual deviation with the meaning it has in the paper, and a nonzero effect on a nonatomic aggregate. Preserving the first makes the deviation null; preserving the second produces a coalition or weighted-agent problem.
The honest weakness of the negative case is that minimum-mass coalition manipulation is a sensible problem and the authors would likely recognize it as related to their stated future direction. If ChoCo permits such a strategic co-modification as a mirror, the proposed question could be worthwhile. But it should then be graded as a new continuous coalition-manipulation problem, not as the continuous counterpart of Theorem 3. Under the programme’s stated requirement for a named computational result, this paper supplies no surviving anchor.
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.