| paper | d4-conf-atal-2013-0196 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm P\)) for \(m=1\) and fixed \(k\), with bit running time \(O_k(\tau(L+\log_2(W+1)+1)^3)\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given a finite type set \(T\), binary-rational masses \(\mu_t \geq 0\) summing to \(1\), nonnegative per-member weight polynomials \(a_t(s)\), a nonnegative quota polynomial \(q(s) \leq \sum_{t \in T}\mu_t a_t(s)\), rational endpoints \(s_0 \leq s_1\), and rational bounds \(L < U\), decide whether the continuous least-core value lies in \([L,U]\) for every \(s \in [s_0,s_1]\). For each \(s\), define \(\varepsilon^*(s)\) as the minimum \(\varepsilon\) over \(p_t \geq 0\) satisfying \(\sum_t \mu_t p_t = 1\) and \(\sum_t z_t p_t \geq 1-\varepsilon\) for every \(z \in [0,\mu]\) with \(\sum_t z_t a_t(s) \geq q(s)\). Use the paper’s unary-coefficient convention and fixed polynomial degree.
A continuum of members grouped into finitely many complete voting types, with mass \(\mu_t\) per type and common time-varying per-member weight \(a_t(s)\). Coalitions choose any mass \(z_t \in [0,\mu_t]\); type-level payoff density \(p_t\) gives total payoff \(\sum_t \mu_t p_t = 1\), and the objective is to minimize the least-core slack \(\varepsilon\) against every winning mass coalition.
The paper does not establish that finite-clone least-core values converge to the fractional-coalition value, especially near quota boundaries; the proponent identifies this gap but leaves it open.
fatal: False
The mirror covers Theorem 5.2’s interval decision for the least-core value, using the pointwise least-core formulation behind Theorem 5.1. It leaves the Shapley-value and cost-of-stability results without population mirrors.
I would lead with Theorem 5.2, proved in this paper. It says that Int-LeastCore is solvable in time \(\operatorname{poly}(n^k,W^k,\|L\|,\|U\|,\|t_0\|,\|t_1\|)\): given a dynamic weighted voting game whose weights and quota are degree-\(k\) integer polynomials, rational time endpoints, and rational bounds \(L<U\), decide whether the value of the least core stays in \([L,U]\) throughout the interval. This is under the paper’s unary-coefficient convention. It is the strongest anchor here because it asks for an exact guarantee over an entire time interval, not just a computation at one time point.
A direct population mirror is Continuous Dynamic Least-Core Interval. Take a finite support \(T\) of \(\tau\) player types and rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\). A type is a contractual voting class: every member has the same time-varying per-member weight \(a_t(s)\). Let \(q(s)\) be the quota per unit of population, with \(q(s)\leq\sum_t\mu_t a_t(s)\) throughout the interval \([s_0,s_1]\). In the corresponding \(N\)-member society, there are \(N\mu_t\) members of type \(t\), each with weight \(a_t(s)\), and the quota is \(Nq(s)\). Thus \(s\) remains time; the society is what becomes continuous.
Represent a coalition by its selected mass \(z_t\in[0,\mu_t]\). It wins at time \(s\) when \(\sum_t z_t a_t(s)\geq q(s)\). Let \(p_t\geq0\) be the payoff per unit of type-\(t\) mass, normalized so the grand coalition receives total payoff one. Define
\[ \varepsilon^*(s)= \min_{p,\varepsilon}\ \varepsilon \quad\text{subject to}\quad \sum_t\mu_t p_t=1,\qquad \sum_t z_t p_t\geq 1-\varepsilon \ \ \text{for every }z\in[0,\mu]\text{ with }\sum_tz_ta_t(s)\geq q(s). \]
As in the paper, \(\varepsilon\) need not be nonnegative. Given the type masses and weight polynomials, quota polynomial, rational interval \([s_0,s_1]\), and rational \(L<U\), the problem asks whether \(L\leq\varepsilon^*(s)\leq U\) for every \(s\) in that interval. Its solution is the exact yes/no answer; a useful no-certificate would identify a time and a least-core value outside the bounds.
This is a plausible high-multiplicity regime: for example, a large member-owned platform or cooperative with many account holders in a small number of voting tiers, where each tier follows the same forecast weight trajectory. There are many members but relatively few distinct types. The type description is complete for the game because members in a class have identical voting weights at every time. The payoff \(p_t\) is a type-level allocation: each member receives \(p_t/N\) in the \(N\)-member approximation, so the type’s total allocation is \(\mu_t p_t\). That preserves the paper’s unit-grand-coalition payoff convention.
I expect this mirror to be Class A for fixed polynomial degree. At a fixed time, separation over the continuous coalition set is a fractional-knapsack problem on the \(\tau\) types: find the least-paid mass meeting the quota. That gives a concrete continuous-optimization route for the least-core LP. The harder part is certifying the bounds over the full time interval with a running time polynomial in \(\tau\) and the input bit length. The paper’s result makes that a motivated question, but does not itself settle it for the continuous population model.
The scope is specifically the paper’s least-core interval result and its pointwise least-core machinery. It does not cover the paper’s Shapley-value results: a power measure for an infinitesimal named player would need its own limit definition. It also does not claim that this population mirror was the paper’s original model; its continuum is over time while its players remain finite.
My weakest point is the added fractional-coalition granularity. Finite clones can form only coalitions on a discrete mass grid; the continuous model permits every partial mass \(z_t\). That adds constraints and can change the least-core value, especially near a quota boundary. I regard that as the intended high-multiplicity relaxation, but a key follow-up is to establish when its value is the limit of the finite-clone values, and at what rate. Other immediate questions are whether the all-time decision admits a polynomial algorithm in \(\tau\), and how its complexity changes when the polynomial degree is part of the input.
Theorem 5.2 is a genuine computational result, so the “no named result” objection does not apply. The strongest skeptical angle is that its algorithm depends on a finite set of coalition signatures and finitely many phase transitions. With continuous coalition masses \(z_t\), those signatures range over a continuum. At a fixed time, separation becomes fractional knapsack, so the mirror replaces the paper’s finite-signature machinery with a parametric optimization problem. A later pseudo-polynomial LP formulation for the *finite* weighted-voting least core shows that this area already has substantial optimization machinery, but it does not answer the continuous-population, all-time question. [Tanaka and Matsui (2022)](https://doi.org/10.1016/j.mathsocsci.2021.12.002)
That makes the mirror a distinct computational problem, though. An exact account of how the least-core value changes over time could still be worthwhile under ChoCo’s aims. Nor does the proposed model collapse: with \(N\) similar members, each receiving payoff \(p_t/N\), the mass-level payoff and coalition constraints have a coherent finite-clone interpretation.
The application objection is also limited. Countries in the EU Council are a small, institutionally fixed set, and their populations are not themselves the Council’s players. But a large organization with many voting members in a few contractual classes is a plausible regime. Its transferable-utility assumption deserves scrutiny, yet it is a recognized model choice rather than a failure of high multiplicity.
So my negative case is weak. Theorem 5.2 survives its best mirror: continuous time remains, while the population becomes a finite-support distribution over member types. I cannot honestly defend the universal claim that no worthwhile scenario exists.
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.