| paper | d4-conf-aldt-2021-0002 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 5
Given \(m\) alternatives, rational masses \(\mu_t\) for \(\tau\) complete preference types, and rational piecewise-linear utilities \(u_t(S,q)\) that increase with community share \(q\), decide whether there is an assignment \(x_{t,S}\geq 0\), with \(\sum_S x_{t,S}=\mu_t\) and \(q_S=\sum_t x_{t,S}\), such that no positive-mass coalition can profit by moving together to any alternative.
A continuous population of infinitesimal agents partitioned into \(\tau\) complete preference types, each with mass \(\mu_t\). The decision variables \(x_{t,S}\) assign each type's mass among alternatives; the induced shares \(q_S\) determine utilities. Stability means that for every destination \(S\) and feasible \(\delta>0\), the mass currently elsewhere that prefers \((S,q_S+\delta)\) to its current outcome is less than \(\delta\).
The paper's reduction uses \(m\) linear in the number of voters and gives no evidence that its voters have small support \(\tau\); splitting type mass may also change whether a stable assignment exists.
fatal: False
The mirror covers the two-alternative stable-assignment algorithm in Theorem 1 and the variable-alternative stable-existence question in Proposition 5. It does not cover preference elicitation, uniqueness, strategyproofness, or the paper's separate result on checking a given assignment for stability.
I see two defensible mirrors. The lead is the paper’s two-alternative result, where monotonicity gives a direct reason to expect tractability. A broader mirror of its multi-alternative hardness result is worth asking too, but its answer is less certain.
Lead — Two-Protocol Stable Mass Forking. In the published chapter, Theorem 1 proves that Algorithm 1 finds a stable assignment in polynomial time for every monotonic profile with two alternatives. The authors prove this result there: starting with everyone at \(A\), the algorithm repeatedly moves a group to \(B\) when the group can profit by doing so, and stops at stability. [Published chapter](https://doi.org/10.1007/978-3-030-87756-9_22)
A plausible high-multiplicity setting is a large protocol community: many miners, maintainers, or users choose between two versions, and their preferences depend on both the protocol and the size of the community that adopts it. A type is a complete preference over those outcomes; mass is the fraction of the population with that type. For an explicit finite input, represent each type’s ordinal preferences by rational piecewise-linear functions \(u_t(S,q)\), strictly increasing in community size \(q\). The utilities encode comparisons; they are not the social objective.
Given type masses \(\mu_t\), the decision variable is an assignment \(x_{t,S}\geq 0\), with \(\sum_S x_{t,S}=\mu_t\); the resulting community size is \(q_S=\sum_t x_{t,S}\). A solution is an assignment with no profitable positive-mass fork. More precisely, for every destination \(S\) and every feasible coalition mass \(\delta>0\), the mass of agents outside \(S\) who would prefer joining it at size \(q_S+\delta\) must be less than \(\delta\):
\[
\sum_{R\ne S}\sum_{t:\,u_t(S,q_S+\delta)>u_t(R,q_R)}x_{t,R}<\delta.
\]
That condition captures the paper’s stability question in population shares. I expect the two-alternative problem to be tractable: the batch-move argument depends on monotonicity, not on people being indivisible. With finitely many encoded types, the relevant preference thresholds can be checked directly, and each batch can move a type’s mass at most once. Further questions include whether the forward and reverse procedures characterize uniqueness, and how much preference information is needed to find the assignment.
Broader, less certain mirror — Multi-Protocol Stable Mass Forking. Proposition 5 states that deciding whether a forking problem with a variable number of alternatives admits a stable assignment is NP-complete. The authors prove it by adapting a reduction from Darmann’s core-stability result for group activity selection; their proof is a sketch, and the number of alternatives in the reduction is linear in the number of voters. They leave the fixed-alternative case, including three alternatives, open. [Published chapter](https://doi.org/10.1007/978-3-030-87756-9_22)
Use the same type and mass representation, now with \(m\) protocols. The instance gives rational masses for \(\tau\) types and their preferences over protocol and community size; the question is whether there exists an assignment \(x_{t,S}\) satisfying the stability condition above for every destination \(S\) and every feasible \(\delta\). This is a decision problem about stable communities, not about fractional protocol outcomes. It fits large federated or blockchain ecosystems with many possible protocol branches and far more participants than distinct preference types.
My tentative expectation is hardness transfers when \(m\) is part of the input: the source result’s reduction is driven by the alternative agenda, which the programme’s heuristic identifies as the kind of combinatorics likely to survive. But that is a hypothesis for the prover, not a consequence of Proposition 5. The continuous question allows a type’s mass to split across communities, while the paper’s agents are indivisible; a reduction must show that this extra flexibility does not create stable assignments that were unavailable before. The most immediate follow-ups are whether the continuous problem remains hard for fixed \(m=3\), and whether hardness persists when the population is large relative to the number of types.
The weakest point in the case is that the paper specifies ordinal rankings only at integer community sizes, whereas a finite continuous input needs an encoding of preferences over real sizes. Piecewise-linear utilities supply one sensible encoding, but they restrict the domain. That issue makes the multi-alternative hardness mirror uncertain. It does less damage to the lead: Theorem 1’s central mechanism is monotonic mass movement, and the authors’ underlying question—whether a stable partition exists and how to find one—is exactly what the two-protocol mass problem asks.
The strongest case against is that the paper gives no single continuous model for its size-dependent preferences. Its agents rank outcomes at integer community sizes \(1,\ldots,n\). A mirror must choose what size means in a large society—absolute population or share—and how preferences extend to fractional sizes. The proposed share-based utility curves are plausible, but they add structure the paper does not specify. That makes the mirror a new modeling choice rather than a forced continuation of the theorem. It does not, by itself, make the question unworthy.
For Theorem 1, the algorithm’s central move is already aggregate: find a group willing to move together, then repeat. With finitely many types and encoded preference thresholds over community shares, that batch-move idea appears to carry over directly. This makes the continuous result look like a modest extension rather than a problem that calls for new optimization machinery. The same concern applies to the proposed uniqueness question. The elicitation question changes more substantially: querying one representative could reveal preferences for an entire type, whereas the paper queries individuals. These are reasons to demand a precise input model and a clear payoff from the extension. They do not defeat the lead mirror; the two-protocol mass-stability problem remains coherent and well matched to the community-size preferences in the paper.
Proposition 5 provides still less support for a high-multiplicity hardness mirror. The paper’s reduction has a number of alternatives linear in the number of voters, and it gives no indication that the constructed voters fall into a small number of preference types. A mass assignment can also split a type across communities, so the discrete reduction cannot simply be carried over. A better target would be fixed \(m=3\), or a variable-\(m\) model with \(\tau\) much smaller than the population. Both are sensible questions, but the paper establishes no hardness result for either continuous version. The reduction therefore motivates exploration without establishing a particularly compelling high-multiplicity regime.
Strategyproofness offers little rescue for the negative case or the positive one: in an atomless population, one person’s report has zero mass, so unilateral strategyproofness risks becoming vacuous. A positive-mass group manipulation could be meaningful, but it would need its own reporting model.
My best argument against is therefore about priority: the two-alternative mirror may yield a small extension of an aggregate algorithm, while the multi-alternative hardness claim has no demonstrated small-support basis. I cannot honestly turn that into the universal conclusion that no worthwhile mirror exists. The lead remains a plausible continuous-population computational question; the negative case is weak precisely there.
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.