| paper | d4-conf-ecai-2008-0158 |
| 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: Continuous CS-core membership is in \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational masses \(x_r\), weights \(w_r\), payoff densities \(a_r\), a quota \(q\), and a block assignment for finitely many cells \(r\), with the candidate outcome satisfying each block’s feasibility and payoff condition, decide whether every measurable coalition of weight at least \(q\) receives payoff at least \(1\). Equivalently, decide whether the minimum of \(\sum_r a_r z_r\), subject to \(\sum_r w_r z_r \ge q\) and \(0 \le z_r \le x_r\), is at least \(1\).
An atomless unit-mass population with finitely many rational weight and payoff cells; a candidate partition into blocks; and payoff density constant on each cell. A blocking coalition chooses mass \(z_r\) from each cell, and the decision is whether any such choice has weight at least \(q\) and payoff below \(1\).
The proposed mirrors cover Theorem 3 through a stability test for a specified outcome, and Theorem 2 through CS-core existence over divisible type masses. They leave the core comparisons, Theorems 4–5, and the heuristics unmirrored.
The strongest mirror is the CS-core problem itself. In a large resource-sharing system, let a type specify an agent’s weight, and let \(\mu_t\) be the fraction of the population with that weight. For example, millions of interchangeable compute providers might fall into \(\tau\) capacity classes, with \(N\gg\tau\). A coalition succeeds when its total contribution reaches a quota; success yields one unit of transferable payoff. A coalition structure assigns the population to simultaneous tasks, and stability asks whether any group could leave and form a winning coalition that can guarantee its members a total payoff of one.
Formally, take an atomless unit-mass population \(\Omega\), divided into finitely many types \(t\) with rational masses \(\mu_t\) summing to one. Type \(t\) contributes \(w_t\) per unit mass. Write \(W=\sum_t\mu_t w_t\) for total weight and let \(q\in(0,W]\) be the quota. A coalition is any measurable \(A\subseteq\Omega\), with weight \(w(A)=\int_A w\,d\mu\); it wins exactly when \(w(A)\ge q\). An outcome is a measurable partition \(\mathcal P\) and a nonnegative payoff density \(p\). Each block \(B\in\mathcal P\) must receive its value, \(\int_B p=v(B)\), and the outcome is in the CS-core if every winning \(A\) has \(\int_A p\ge1\). This preserves the paper’s quota, coalition structures, transferable payoff, and blocking condition. The population mass can be split among blocks, as a continuous population requires.
My lead is NONEMPTY-CS-CORE∞: given the rational type masses and weights and quota \(q\), does there exist such a partition and payoff density? A solution is a stable outcome \((\mathcal P,p)\). I expect this problem to be tractable: in this model, the CS-core is nonempty exactly when \(W/q\) is an integer. If \(W=kq\), split every type mass equally among \(k\) blocks and set the payoff density of type \(t\) to \(w_t/q\). Each block has weight and payoff one, and every winning coalition gets at least one. Conversely, atomless mass lets coalitions choose any desired amount of weight. Stability forces each winning block to have exactly weight \(q\), and the total weight left in losing blocks must be zero; otherwise a winning coalition can combine some losing mass with part of a winning block and obtain less than one. So the total weight must be an integer multiple of \(q\). The decision can therefore be made by rational arithmetic.
The paper’s Theorem 2, proved there by a reduction from PARTITION, states that deciding whether a weighted voting game has a nonempty CS-core is NP-hard. Its continuous mirror asks the same existence question over type masses. The relaxation changes the answer on the reduction itself: for its PARTITION instances, total weight is \(2K\) and quota is \(K\), so \(W/q=2\). The continuous instance has a stable outcome even when the original PARTITION instance is a no-instance: divide every type mass in half between two blocks. That is a particularly clear case of the subset-selection obstruction disappearing when mass is divisible.
A second anchor is IN-CS-CORE∞, the specified-outcome question. Its input is the same society plus a candidate partition and a finite rational description of its payoff density: cells \(r\), each with mass \(x_r\), type \(t(r)\), payoff density \(a_r\), and a block assignment. The cell masses must sum to each type’s mass, and each block must receive its value. Ask whether the outcome is in the CS-core; a solution is yes or no, with a violating coalition as a witness for no. A coalition can select any fraction \(z_r\in[0,x_r]\) from each cell, so the lowest payoff of a winning deviation is found by the linear program
\[
\min \sum_r a_r z_r
\quad\text{subject to}\quad
\sum_r w_{t(r)}z_r\ge q,\qquad 0\le z_r\le x_r.
\]
The outcome is stable exactly when this minimum is at least one. Thus this mirror is in P.
The paper’s Theorem 3, also proved there, says that given a weighted voting game, a coalition structure, and an imputation, deciding whether the outcome is in the CS-core is coNP-complete. The continuous version replaces discrete subset choice with fractional selection from the cells, giving the LP above. Both hardness anchors therefore point to tractable continuous questions, but by different routes: the first has a structural characterization; the second has a polynomial separation test. These mirrors cover the paper’s two hardness results about CS-core existence and membership, not its core comparisons, small-weight algorithm, or heuristics.
The weakest point is that atomlessness is a substantive change: it lets a type’s mass be divided among coalitions, while the paper’s agents are indivisible. The PARTITION reductions use individually weighted players, so they do not establish hardness in a regime with many agents but few shared types. That is also why I find the mirror plausible for large populations of interchangeable providers, but not for a small committee or a setting where particular agents must remain intact. Further questions include whether the existence characterization survives type-specific task quotas or values, and how quickly a discrete high-multiplicity instance approaches the continuous answer as its type counts grow.
The strongest negative case is that the mirror fits only a particular regime: large pools of interchangeable agents whose relevant attributes can be summarized by weight. Where each weight belongs to a distinct actor, or agents have task-specific constraints that affect which coalitions can form, a distribution over weight types loses information the CS-core uses. The paper’s PARTITION reduction illustrates that individualized weights can carry the combinatorics. But that establishes a limit on the reduction’s relevance to high multiplicity; it does not rule out repeated types.
That objection does not defeat NONEMPTY-CS-CORE∞ in the better scenario: a large pool of equivalent compute providers or robots, with a few capacity classes and interchangeable tasks. Scale the quota with the population, and type masses describe the proportions of providers assigned to each task. Splitting a type’s mass among blocks then represents assigning different providers of that type to different tasks. The model preserves the paper’s coalition values and blocking question without tracking names.
Nor does the objection defeat IN-CS-CORE∞. A finite rational list of type-and-payoff cells is a reasonable input for a specified outcome. A deviating coalition selects portions of those cells, and the stated LP checks whether any winning deviation gets payoff below one. Arbitrary measurable payoff functions would be an encoding problem, but they are not needed to pose this finite-input version.
The credible negative point is narrower: exact stability may be sensitive to rounding, so a continuous answer need not settle stability for a particular finite population. That limits what the mirror says about finite instances; it does not make either continuous question ill-posed or uninteresting. I cannot honestly defeat both anchors across all plausible scenarios. The negative case is weak, and under the programme’s stated criteria both mirrors survive.
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.