| paper | d4-conf-sagt-2009-0026 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given finitely many types \(T\) with rational masses \(\mu_t>0\), \(\sum_{t\in T}\mu_t=1\), rational per-member weights \(a_t\ge 0\), quota \(0\le q\le\sum_{t\in T}\mu_t a_t\), and subsidy bound \(\Delta\ge 0\), does there exist a nonnegative per-member payoff \(p_t\) for each type such that \(\sum_{t\in T}\mu_t p_t\le 1+\Delta\) and \(\sum_{t\in T}p_t x_t\ge 1\) for every winning mass vector \(x\) with \(0\le x_t\le\mu_t\) and \(\sum_{t\in T}a_t x_t\ge q\)?
A unit-mass population divided into weight types \(t\), where type \(t\) has mass \(\mu_t\) and each member has voting weight \(a_t\). The center chooses a payoff density \(p_t\) for each type, minimizing \(\sum_t\mu_t p_t-1\), subject to every mass coalition meeting quota \(q\) receiving total payoff at least \(1\).
The game concerns transferable-payoff coalitional stability and uses voting weight as its type, rather than the voter-preference types central to ChoCo’s usual model, so its fit is less direct.
fatal: False
The mirror covers CoS-WVG from Theorem 4.1; it leaves Super-Imputation-Stability-WVG, the unary-weight algorithm, the FPTAS, and coalition-structure results aside.
My lead is Continuous WVG Cost of Stability, mirroring the CoS-WVG part of Theorem 4.1. That theorem says that, for weighted voting games with integer weights encoded in binary, both Super-Imputation-Stability-WVG and CoS-WVG are coNP-complete. CoS-WVG asks, given a game and a payment bound \(\Delta\), whether \(\CoS(G)\le\Delta\); the stability problem asks whether a supplied payoff allocation is in the adjusted game’s core. The theorem is proved in this paper: its hardness reduction is from Partition. For CoS-WVG, the paper’s coNP-membership argument invokes a result of Malizia et al. (2007).
Here is the continuous problem. An instance gives a finite set of weight types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a rational per-member voting weight \(a_t\ge0\) for each type, a quota \(q\le\sum_t\mu_t a_t\), and a rational subsidy bound \(\Delta\). A coalition is specified by how much mass \(x_t\in[0,\mu_t]\) it draws from each type. It wins when \(\sum_t a_t x_t\ge q\), and any winning coalition has worth \(1\), as in the paper’s simple WVG. The center chooses a nonnegative per-member payoff \(p_t\) for each type. The question is whether there is a stable allocation with total payment at most \(1+\Delta\): for every winning mass vector \(x\), it must satisfy \(\sum_t p_t x_t\ge1\), while \(\sum_t\mu_t p_t\le1+\Delta\). Equivalently, the continuous cost of stability is the minimum of \(\sum_t\mu_t p_t-1\) over allocations satisfying those stability constraints.
The regime is a large membership body—say, a cooperative or federation—with many members but relatively few standardized voting-weight classes. The type is a member’s complete relevant description, here their voting weight; mass is the fraction of the membership in that class. The coalition and payoff variables are densities over those classes. This keeps the paper’s question intact: what is the least outside payment that makes the grand coalition stable? It continuizes the population, not the outcome or the voting rule. In a finite symmetric WVG, restricting equal-weight members to equal payoffs loses no optimum: one can average an allocation over permutations of those members. That makes the type-level payoff choice especially natural.
I expect this mirror to be tractable (Class A), even though its discrete anchor is coNP-complete. The continuous stability constraints have a polynomial-time separation procedure: given \(p\), find the cheapest winning coalition by solving a fractional knapsack problem, filling type capacities in increasing order of \(p_t/a_t\) until the quota is reached. If that coalition receives less than \(1\), it gives a violated constraint; otherwise none exists. The cost-minimization problem is therefore an LP with \(\tau\) payoff variables and a polynomial-time separation oracle, suggesting an exact algorithm polynomial in the support size \(\tau\) and the binary input length. The likely source of the discrete hardness—the all-or-nothing choice of which players enter a coalition—has become fractional mass selection. A further question is to formalize that algorithm and determine precisely how its running time depends on \(\tau\) and the rational input encoding.
The scope is the grand-coalition WVG cost-of-stability decision problem in Theorem 4.1. It does not claim to mirror arbitrary coalitional games or the paper’s coalition-structure results. The paper’s unary-weight algorithm and FPTAS are consistent with asking what happens when coalition choices become divisible, but they are not separate anchors for this case.
The weakest point is the regime’s plausibility. Weighted voting games often represent a small number of indivisible organizations or jurisdictions; those are not a large, interchangeable membership population. The mirror is most convincing when the players really are numerous members in a few standardized weight classes and fractional participation is an honest aggregate description. That limitation leaves a specific, meaningful question: whether the authors would accept stability against every measurable subcoalition as the continuous-population version of stability against every discrete coalition.
The strongest case against is about fit with ChoCo’s target, rather than the mathematics. Theorem 4.1 is a genuine computational anchor: it proves coNP-completeness for CoS-WVG. But the problem is cooperative-game stability. It asks whether transferable payoffs deter every coalition from leaving, not how a population’s preferences determine a social choice. A society typed only by voting weight is therefore a less direct fit for ChoCo’s usual population-of-voter-types model.
There is also a real modeling step in the proposed mirror. A coalition can take any fraction of each weight class, and any such coalition that reaches the quota gets worth \(1\). That represents a divisible-membership federation. It does not literally describe indivisible organizations or voters who cannot split themselves across coalitions. In an electorate, the interpretation of a winning coalition’s transferable worth and subsidy also needs explaining.
Those objections weaken the fit, but they do not defeat the best version of the mirror. In a large federation with many interchangeable members in a few weight classes, fractional membership is a plausible population limit, and the paper itself presents weighted voting games as models of political bodies. For that model, stability requires \(\sum_t p_t x_t\ge 1\) for every winning mass vector \(x\). The constraints have a fractional-knapsack separation procedure, so the mirror is a well-posed computational question with a credible tractability route. Replicating each type and scaling the quota gives a natural finite-to-continuous bridge.
I cannot make a strong universal case against this anchor. The remaining objection is that the model may suit ChoCo’s remit less directly than election problems based on voter preferences. The large-federation scenario answers that concern well enough that the proposed mirror survives.
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.