| paper | d4-conf-aaai-2021-0123 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: every valid input is a YES-instance. The promised-input decision time is \(O(1)\), or \(O(L)\) when reading the entire input. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(d\), a rational status quo \(r\), a finite type set \(T\subseteq\mathbb{Q}^d\), rational masses \(\mu_t>0\) summing to \(1\), and a valid finite initial coalition structure with rational per-type allocations, does every maximal run of two-coalition compromise transitions terminate at a coalition whose proposal maximizes approval mass and whose mass equals that proposal’s total approval mass? Proposals are in \(\mathbb{Q}^d\); each transition moves all approving mass from its two source coalitions into the new coalition, which must be larger than either source.
A finite-support population of ideal-point types \(t\in T\subseteq\mathbb{Q}^d\), each carrying mass \(\mu_t\), with coalitions represented by rational per-type mass allocations and proposals in \(\mathbb{Q}^d\). Compromise transitions move approving mass between coalitions; success means some coalition contains all mass approving a proposal with maximum approval mass.
The paper supplies no finite-cost method for selecting transitions or finding compromise proposals, so this mirror gives a process-correctness guarantee without a bit-complexity algorithm.
fatal: False
The mirror covers Euclidean compromise convergence and, separately, the hypercube minimum-arity results for \(d=3\) and \(d=4\); it leaves other transition classes, sparse-space counterexamples, and run-length bounds outside its scope.
The strongest positive case is a mirror of the paper’s coalition dynamics. The paper has no named NP-hardness, P, or parameterized-complexity result. Its numbered computational results concern termination, success, and how many coalitions must participate in a compromise. Those are still credible anchors for a continuous-population analysis.
A plausible regime is a large online deliberation or referendum community. Each member’s type is their complete ideal position: either a point in a fixed rational coordinate system or a binary stance vector on \(d\) issues. Many people may share each type, so the population has \(N\) members but only \(\tau\) distinct types, with \(N\gg\tau\). The type masses record fractions of the community. The proposal domain, metric, status quo, and coalition operations remain those of the paper; the electorate is the continuous object.
Lead anchor — Theorem 3, proved here. The paper proves that in every Euclidean deliberation space, every maximal run consisting of compromise transitions is a successful deliberation. Here, “successful” means the run is finite and ends with a coalition supporting a most-approved proposal and containing all its approvers.
The corresponding problem is Rational-Mass Euclidean Compromise Convergence. An instance consists of a dimension \(d\), a rational status quo \(r\), finitely many rational ideal-point types \(T\subseteq\mathbb Q^d\), rational masses \(\mu_t>0\) summing to \(1\), and an initial finite coalition structure. Represent each coalition \(j\) by its proposal \(p_j\in\mathbb Q^d\) and the rational mass \(x_{tj}\) of each type it contains, with \(\sum_j x_{tj}=\mu_t\). Every type with positive mass in a coalition must approve its proposal. A legal transition selects two coalitions and a proposal \(q\), moves into a new \(q\)-coalition all mass in those coalitions whose types satisfy \(\|t-q\|<\|t-r\|\), and leaves the remaining mass in the old coalitions. The new coalition must have strictly more mass than either source coalition.
The question is: does every maximal legal run from the supplied initial structure terminate successfully? The solution is yes or no; a no answer has a finite witness run ending in an unsuccessful terminal structure.
I expect the paper’s guarantee to carry over exactly. Take a common denominator \(N\) for the input masses and initial coalition allocations, and replace each type’s mass by \(N\mu_t\) identical agents. Every legal mass transition then corresponds to a discrete transition, with coalition-size comparisons and most-approved proposals preserved up to the common scale. Thus this mirror is a clean high-multiplicity identity, and the theorem gives a yes answer for every valid instance. For finite rational support, restricting proposals to rational points preserves the available approval patterns: approvals are defined by strict inequalities, so any feasible finite pattern has a rational witness.
The next question this raises is the bit-complexity of finding a short successful run in terms of \(d\), \(\tau\), the initial number of coalitions, and input bit length \(L\). Expanding masses to \(N\) individuals proves finite termination, but \(N\) can be exponential in \(L\); it does not by itself give a compact algorithm.
Second anchor — Proposition 8, proved here. In the paper’s \(d\)-hypercube setting, \(\ell^*(d)\) is the smallest number of coalitions whose participation in each compromise suffices to guarantee successful deliberation. The proposition establishes \(\ell^*(3)=3\) and \(\ell^*(4)=5\).
The corresponding problem is Mass Hypercube Compromise Arity. Given \(d\), compute the least \(\ell\) such that, for every finite rational-mass population over \(\{0,1\}^d\) and every valid initial coalition structure, every maximal run of \(\ell\)-compromise transitions terminates successfully; report \(\infty\) if no such \(\ell\) exists. An \(\ell\)-compromise selects \(\ell\) coalitions, moves from each all mass approving a proposed binary vector into a new coalition, and requires that coalition’s mass to exceed that of every selected source coalition. The solution is the threshold value. For \(d=3\) and \(d=4\), I expect the answers to remain \(3\) and \(5\): rational masses can be scaled to integer populations, and integer populations divided by their total mass give rational distributions. Any difficulty in computing the general threshold should therefore come from the discrete, dimension-dependent problem, rather than from the continuum.
These mirrors cover specific results, not the whole paper: Euclidean compromise convergence and the minimum arity needed for guaranteed success in binary issue spaces. The hypercube example also gives a particularly natural regime: on four binary issues there are at most \(16\) ideal-position types, even when thousands of people participate.
The weakest point is that the paper analyzes an abstract, cooperative process; it makes no empirical claim that real deliberators follow these transitions. Also, rational type masses can be expanded into a finite electorate, so the mirror may simply inherit the discrete answer rather than expose new tractability. That limits the novelty claim, but not the fit: type-level approval, coalition mass, and the transition rule preserve the paper’s actual question. The most convincing positive case is therefore a precise high-multiplicity mirror of its dynamics, with the further algorithmic challenge being whether useful guarantees can be expressed directly in \(\tau\) and \(L\), without expanding the population.
The strongest case against is a mismatch with ChoCo’s computational target. The paper proves properties of an abstract deliberation process: which transition rules guarantee success, and how long runs can be. It does not give an algorithm for choosing a proposal or selecting a transition. A mass version of “does every maximal run succeed?” remains a question about dynamics, not an algorithmic problem with a specified input, output, and computation cost. The bounds on numbers of transitions do not supply that missing algorithm.
Theorem 3’s proposed mass mirror is especially close to a change of representation. For rational masses and initial coalition allocations, take a common denominator \(N\) and replace each mass \(x_{tj}\) by \(Nx_{tj}\) identical agents. Approval sets, coalition-size comparisons, and success are preserved, so runs correspond exactly. This does not make the mass question invalid; an identity between the models can itself be a result. But it leaves no distinct computational task in the anchor. Asking for an algorithm that constructs a short successful run or finds each compromise proposal could provide one, but that adds a transition-selection problem the paper deliberately leaves abstract. Any such proposal must specify how the mediator searches the proposal space and pays for that search.
A genuinely atomless Euclidean population would be a more distinct mirror, but the paper’s success condition can fail to exist there. Put the status quo at \(0\), let ideal points be uniformly distributed on \([-1,1]\), and let proposals range over \(\mathbb R\). For \(p>0\), the approvers are precisely those with \(v>p/2\), so the approval mass approaches \(1/2\) as \(p\) tends to zero, but never reaches it. There is no most-approved alternative. One could redefine success using a supremum or restrict proposals, but either choice changes the target. Thus the finite rational-support version avoids this problem by returning to the model that scales exactly to a finite electorate.
Proposition 8 is an even harder anchor to distinguish. On a \(d\)-hypercube there are only \(2^d\) possible ideal-point types and finitely many proposals. Clearing denominators converts every rational mass profile into integer multiplicities while preserving every \(\ell\)-compromise. So the universal threshold \(\ell^*(d)\) asks the same combinatorial question over the same profiles. A per-instance task—such as finding the smallest arity sufficient for one given mass profile—would be a different computational problem, not the result Proposition 8 establishes.
These points do not establish that no useful mirror exists. A large deliberation platform with many people sharing binary issue positions is a convincing high-multiplicity regime, and the authors’ dynamics naturally extend to masses. The negative case is strongest only under ChoCo’s narrower demand for computational problems and algorithms: the cited anchors are convergence theorems whose direct mass versions either inherit the finite-agent dynamics or require a new proposal-selection model. I cannot honestly claim that this defeats every worthwhile mirror. If process analysis and transition-search algorithms count as computational questions in the programme, the rational-mass versions remain credible anchors.
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.