| paper | d4-conf-aaai-2007-0358 |
| 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 in \(O(\tau L^2)\) bit operations. The exact optimum is \(\varepsilon^*=1-\theta/(\sum_t\mu_tq_t)\), attained by \(r_t^*=q_t/(\sum_s\mu_sq_s)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given rational type masses μ_t summing to \(1\), per-unit weights \(q_t\), and a threshold θ no greater than the population's total weight, find the smallest ε and rates \(r_t\ge 0\) such that ∑_t μ_t r_t=1 and ∑_t a_t r_t\ge 1-ε for every coalition mass vector with \(0\le a_t\le μ_t\) and ∑_t q_t a_t\ge θ. The decision version asks whether such rates exist for a given ε.
A continuous threshold game with weight types \(t\), mass μ_t, per-unit weight \(q_t\), and threshold θ. A coalition chooses mass \(a_t\) from each type; an allocation assigns payoff rate \(r_t\), with total payoff ∑_t μ_t r_t=1. Minimize the maximum blocking deficit ε. For fixed rates, the least-paid winning coalition is a fractional knapsack problem, yielding a polynomial-size LP.
The opponent's remaining concern is that the resulting LP may be an elementary, modest result; the proponent does not establish a broader research payoff, though this limits priority rather than validity.
fatal: False
The mirror covers Theorem 5's three least-core problems in a type-level population: deciding whether the ε-core is nonempty, testing whether a type-level allocation is in the least core, and constructing an optimum. It leaves the core and nucleolus results, the discrete pseudopolynomial and approximation results, and Theorem 10's nucleolus hardness unaddressed.
The strongest mirror is the least-core result, in a large federation where many members share one of a small number of statutory voting weights. Each member is a player; its type is its weight class. If there are \(n\) members and \(n_t\) of type \(t\), type \(t\) has mass \(\mu_t=n_t/n\). A coalition can be described by the mass \(a_t\) it draws from each type. The cooperative project is worth \(1\) if that coalition reaches the voting threshold and \(0\) otherwise. An allocation is a payoff rate \(r_t\) for each type, with \(\sum_t\mu_t r_t=1\). The objective is to minimize the largest blocking deficit: find the smallest \(\varepsilon\) such that every winning coalition receives at least \(1-\varepsilon\).
The paper’s Theorem 5, proved here by reduction from PARTITION, establishes that three discrete problems are NP-hard: deciding whether a given \(\varepsilon\)-core is nonempty; deciding whether a given imputation lies in the least core; and constructing a least-core imputation. The continuous mirror is Continuous Least-Core of a Threshold Population. Its instance is rational type masses \(\mu_t>0\) summing to \(1\), per-member weights \(q_t\ge0\), and a threshold \(\theta\) no greater than the population’s total weight. It asks for the least \(\varepsilon\) and a type-level allocation \(r\) satisfying \(\sum_t\mu_t r_t=1\), \(r_t\ge0\), and
\[
\sum_t a_t r_t\ge 1-\varepsilon
\quad\text{whenever}\quad
0\le a_t\le\mu_t
\ \text{and}\
\sum_t a_tq_t\ge\theta.
\]
Its decision form asks whether the \(\varepsilon\)-core is nonempty; its construction form outputs an optimal \(r\). One can also test whether a supplied type-level allocation belongs to the least core. This is the symmetric, type-level counterpart of the paper’s membership problem.
This mirror has a direct algorithmic answer. For a fixed \(r\), the least-paid winning coalition solves a fractional knapsack problem:
\[
\min\left\{\sum_t r_ta_t:
0\le a_t\le\mu_t,\
\sum_tq_ta_t\ge\theta\right\}.
\]
Its linear-programming dual uses variables \(\lambda,z_t\ge0\), with \(z_t\ge\lambda q_t-r_t\), and objective \(\lambda\theta-\sum_t\mu_tz_t\). Thus the continuous least-core problem is the polynomial-size LP that minimizes \(\varepsilon\), subject to
\[
\sum_t\mu_t r_t=1,\qquad
r_t,\lambda,z_t,\varepsilon\ge0,\qquad
z_t\ge\lambda q_t-r_t,\qquad
\lambda\theta-\sum_t\mu_tz_t\ge1-\varepsilon.
\]
It is therefore tractable in the number of types and the input bit length. I expect this to be Class A: the discrete hardness dissolves because a coalition can take fractional mass from a type instead of solving an indivisible subset-selection problem. The decision and construction versions follow from the same LP; testing a supplied type-level allocation amounts to comparing its least-paid winning coalition with the optimum.
The authors should recognize this as their problem: the coalition’s value is still the same binary threshold function, and the question is still how stable the grand coalition can be under an allocation. What changes is the population unit. In a large federation, the mass \(a_t\) means the fraction of a weight class joining a coalition, and \(r_t\) is the payoff per unit of that class. The collective outcome remains \(0\) or \(1\); the population becomes continuous. Useful follow-up questions include how the discrete least core converges to this LP when class sizes grow, and exactly how much indivisibility is needed to recover hardness.
My weakest point is also the mirror’s source of tractability: fractional coalition formation is materially different from choosing whole players. The PARTITION reduction can have as many distinct weight types as players, so it does not itself describe the large, few-type regime. And the membership version here tests type-level allocations, not arbitrary unequal payoffs within a class. Those limits mean this mirror does not settle the discrete theorem. They do not make the continuous question a restatement: it asks whether least-core stability in a population made of large, internally interchangeable weight classes admits an exact continuous optimization method.
Theorem 5 is a genuine anchor: it proves NP-hardness for three named least-core problems. The strongest objection is that its PARTITION reduction uses independently chosen player weights. It therefore gives little evidence about the behavior of large populations with repeated weight types. That weakens the reduction as motivation for a high-multiplicity study, but it does not defeat one.
The natural mirror is hard to rule out. Let \(\mu_t\) be the mass of weight type \(t\), \(q_t\) its weight per unit mass, and \(r_t\) its payoff rate. A coalition chooses mass \(a_t\in[0,\mu_t]\); it wins when \(\sum_t q_ta_t\ge\theta\), and receives payoff \(\sum_t r_ta_t\). This describes, for example, a large federation or shareholder population with repeated voting weights. Weight is the only player attribute in the game, so grouping players by weight preserves the model. Symmetrizing payoffs within each weight class preserves least-core feasibility, and a positive threshold with bounded weights requires a winning coalition to have positive mass. The usual identity and atomlessness objections do not bite here.
For a proposed allocation, its least-paid winning coalition is a fractional knapsack problem. Its dual gives the polynomial-size LP described in the case for, with running time polynomial in the number of supported types and input bit length. That is a direct computational question about a continuous population, and it uses the same binary threshold value and stability objective as the paper. The discrete reduction need not carry over for the mirror to be worthwhile; locating where indivisibility matters is part of the programme.
The best remaining case against is about research priority: this mirror may yield a short, elementary result, and the paper’s reduction does not establish that its hardness is relevant to the repeated-type regime. That is a reason to ask for a strong finite-to-continuous connection before investing heavily. It is not a sound reason to reject the mirror. Under the programme’s stated standard, I cannot honestly defeat this anchor: the negative case is weak, and the least-core 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.