| paper | d4-journals-jair-2018-0064 |
| 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: Polynomial-time solvable for \(m=1\), with running time \(O(\tau L^2)\) bit operations. Feasibility holds exactly when \(\sum_t\mu_t w_t\leq q(1+\Delta)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 18
statement extracted from the paper’s text layer
Given finitely many types with rational masses \(\mu_t>0\), voting weights \(w_t\), a quota \(q\), and a subsidy bound \(\Delta\), decide whether there are nonnegative per-capita payments \(p_t\) such that \(1\leq\sum_t\mu_t p_t\leq1+\Delta\) and \(\sum_t p_t x_t\geq1\) for every mass coalition \(x\) with \(0\leq x_t\leq\mu_t\) and \(\sum_t w_t x_t\geq q\).
A threshold cooperative game over a population of total mass one, represented by rational type masses \(\mu_t\) and weights \(w_t\). A coalition chooses mass \(x_t\) from each type and is winning when \(\sum_t w_t x_t\geq q\); its value is one. Choose per-capita payments \(p_t\) minimizing \(\sum_t\mu_t p_t-1\), subject to nonnegative payments and \(\sum_t p_t x_t\geq1\) for every winning coalition.
The fixed-payout part of Theorem 18 permits different payments to equal-weight players, which the proposed weight-only types do not capture; this bounds that part of the mirror but leaves the cost-of-stability question intact.
fatal: False
The mirror covers the Cost-of-Stability-WVG decision result in Theorem 18; it does not cover the paper's general bounds, least-core comparisons, or arbitrary asymmetric fixed-payout inputs.
The strongest mirror is the paper’s weighted voting game result. Theorem 18, proved in this paper, says that both Super-Imputation-Stability-WVG—whether a proposed payout is stable after a specified subsidy—and Cost-of-Stability-WVG—whether the cost of stability is at most a specified amount—are coNP-complete. The games have binary-encoded integer weights and quota; payouts and subsidies are binary-encoded rationals. The hardness reductions use Partition.
I would mirror that anchor with Continuous Cost-of-Stability for Weighted Voting Games. An instance has a finite set of types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a voting weight \(w_t\) for each type, a quota \(q\) with \(0<q\leq\sum_t\mu_t w_t\), and a subsidy bound \(\Delta\). A coalition is any mass vector \(x\) with \(0\leq x_t\leq\mu_t\); it wins when \(\sum_t w_t x_t\geq q\), and its value is then \(1\), otherwise \(0\). A solution is a nonnegative per-agent payment \(p_t\) for each type such that every winning coalition receives at least \(1\), while total payment satisfies \(\sum_t\mu_t p_t\leq1+\Delta\). The decision question is whether such a payment exists. The continuous cost of stability is the minimum of \(\sum_t\mu_t p_t-1\) over stable payments. Given a proposed \(p\), the corresponding stability check asks whether any winning \(x\) receives less than \(1\).
This is a population mirror: \(x_t\) is the fraction of the population of type \(t\) that joins a deviation. It does not replace the population with fractional outcomes or probabilities. A plausible regime is a large federation whose members fall into a few voting-weight tiers, where any coalition meeting a quota can pursue a common project worth one normalized unit, and an outside sponsor subsidizes cooperation by the grand coalition. There might be hundreds of thousands of members but only a handful of types. Weight is a complete type description in this game: players with the same weight have identical effects on every coalition’s value. Requiring one payment per type does not simplify away a relevant distinction, since a discrete payout can be averaged across equal-weight players without changing its total or stability.
I expect this mirror to be tractable. For a proposed payment vector \(p\), separation reduces to the linear program
\[
\min \left\{\sum_t p_t x_t:\ \sum_t w_t x_t\geq q,\ 0\leq x_t\leq\mu_t\right\}.
\]
A coalition blocks exactly when this minimum is below \(1\). The cost decision adds the payment-budget constraint and uses this separation problem to test feasibility. Thus the continuous problem has a polynomial-time LP-based route in the support size \(\tau=|T|\) and the input bit length. The continuous mirror even permits exact optimization, whereas the paper’s discrete decision problems are coNP-complete.
The fixed-payout stability query is the separation step in that cost problem, so both clauses of Theorem 18 have a direct counterpart in this model. The scope here is deliberately limited to Theorem 18’s weighted-voting computational results; I am not claiming a continuous version of the paper’s general axiomatic bounds or least-core comparisons.
The weakest point is that the paper’s hardness reduction encodes Partition through individual binary weights. Those instances can have as many distinct weight types as players, so they do not themselves exhibit a large population with small support. That limits how directly the hardness construction motivates the few-type regime. It does not make the mirror a different problem: the winning rule, coalitional deviations, stability condition, and subsidy objective are preserved, while only the available mass of each identical type becomes divisible. A natural follow-up is to quantify the gap between discrete and continuous costs as the number of members per type grows, and to ask when the continuous solution gives useful bounds or approximations for finite high-multiplicity instances.
I can’t honestly make a strong universal case against this mirror. The narrowest objection is to the proposed scenario: weighted voting often represents indivisible institutions, and splitting one institution into fractional coalition members can change which deviations are possible. Also, a fixed payout vector with different payments to equal-weight players needs payment included in the type, so its support need not stay small.
That objection does not defeat the cost-of-stability mirror. A plausible regime is a large association whose members fall into a few voting-weight tiers, where any coalition reaching a quota can produce the same normalized value. In that regime, fractional mass describes how much of each tier deviates. The cost problem can use one payment per weight type: symmetry lets us average any feasible payments across players of equal weight without changing feasibility or total payment.
Both computational questions in Theorem 18 have a direct continuous counterpart. For a proposed type-payment vector \(p\), checking stability reduces to minimizing \(\sum_t p_t x_t\) subject to \(\sum_t w_t x_t\ge q\) and \(0\le x_t\le\mu_t\). This is a linear program. Cost-of-stability feasibility can then use that check as a separation oracle, giving an exact polynomial-time route in the support size and input bit length. That tractability is a substantive Class A result under the programme’s stated aims; it cannot serve as an objection simply because the answer differs from the paper’s hardness result.
The paper’s Partition reduction has one limitation for the mirror: its instances can use as many distinct weights as players, so they do not establish hardness in a few-type population. That limits how directly the reduction motivates the high-multiplicity regime, but it does not make the regime incoherent or the question unworthy.
So the honest negative case is weak. The fixed-payment query needs care about what counts as a type, and the institutional interpretation can be strained. Neither defeats the cost-of-stability mirror for large populations with repeated weight tiers; the proposed LP formulation makes that anchor unusually strong.
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.