| paper | d4-conf-aaai-2015-0565 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 and Theorem 2 identify payment concepts that optimize stability, but neither asserts an algorithm, a computational formulation used by the paper, or a complexity result. The proposed type-mass least-core optimization is coherent, yet it is a new computational extension rather than a continuous analogue of a named computational result in this paper.
fails bit a — no named computational result to mirror
The proposed extension captures the least-core stability objective under common additive noise; it does not transfer the paper’s results for the nucleolus, partial nucleolus, or multiplicative solution concepts.
The strongest possible positive case is a continuous version of the paper’s payment-selection problem. Imagine a very large organization with many interchangeable people in a finite set of roles or skill types. Type \(t\) has population mass \(\mu_t\); a coalition is described by how much mass \(q_t\) it draws from each type. Its estimated value is \(v(q)\), and the decision is a per-person payment \(p_t\), with total payments fixed at the grand coalition’s estimated value. The objective is to maximize the probability that every coalition remains stable after values are revealed.
A concrete version would take rational \(\mu\), a rational piecewise-linear specification of \(v(q)\) over \(0\le q_t\le\mu_t\), and a specified common additive noise distribution with full support. The question is to find a payment vector \(p\) satisfying \(\sum_t\mu_t p_t=v(\mu)\) that maximizes
\[
\Pr\!\left[\forall q\ne 0,\mu:\ \sum_t q_t p_t\ge v(q)-D\right].
\]
The solution is such a vector \(p\). With common noise, this is equivalent to minimizing the largest coalition excess, the continuous analogue of the least-core objective. Under the stated piecewise-linear input representation, that minimization can be written as an LP using the vertices of the value-function pieces.
The paper’s closest result is Theorem 1, proved here: when every proper coalition has the same noise realization, and the noise distribution has full support, a payment maximizes ex-post stability exactly when it is in the least core; even without full support, every least-core payment maximizes stability. This gives the candidate mirror its strongest connection to the paper’s own problem. But Theorem 1 characterizes optimal payments; it does not classify the complexity of computing them. Theorem 2 likewise characterizes the nucleolus as uniquely optimal under confidence for specified sequences of independent noise distributions. It too is a solution-concept characterization, not a complexity result.
Under the requested anchor rule, then, this paper has no eligible named computational result: none of its numbered theorems, lemmas, corollaries, or propositions asserts that a computational problem is in P, hard, FPT, or otherwise classifies its complexity. The continuous LP question above is a plausible extension, but it cannot honestly be presented as a mirror of a qualifying anchor. Its main weakness is that the paper studies which payment concepts maximize stability under noise, while the programme asks for complexity results about computational problems. The paper’s agents remain finite and individually named; moving to type masses would be a model extension, not a result the authors already establish.
The strongest objection is that this paper has no named computational result for ChoCo to continuize. Theorem 1 is the closest anchor: it characterizes which payments maximize ex-post stability under perfectly correlated noise. Theorem 2 characterizes the nucleolus under a sequence of independent-noise distributions. Neither gives an algorithm, a complexity bound, or a computational classification. The same is true of the multiplicative results. They are solution-concept characterizations, not complexity results.
The proposed mass-based least-core problem is coherent, but getting to it adds substantial modeling choices: agents must be interchangeable within finitely many types, coalition values must depend only on type masses, and the value function needs a finite representation such as the proposed piecewise-linear input. The paper specifies none of these. One could study the resulting continuous optimization problem, but that would be a new computational project motivated by Theorem 1, not a mirror of a computational result in the paper. Its complexity would depend on the chosen representation and pricing problem; the theorem itself supplies no algorithmic claim to carry over.
Theorem 2 is an even weaker anchor for a continuous population: its independent noise is indexed by the finitely many proper coalitions. With a continuum of coalition masses, that assumption does not by itself give a well-defined measurable probability of stability. A regular correlated noise process might repair the model, but the theorem would no longer establish the result. The common-noise version behind Theorem 1 avoids this issue, so it remains the strongest candidate.
I would not argue that an anonymous mass game is inherently nonsensical; a large workforce with type-dependent coalition values is plausible. So the negative case is strong against calling this a continuization of the paper’s computational results, but weak against the broader claim that the continuous least-core problem could be worthwhile. That problem survives as a sensible new question, even though this paper does not provide a named computational finding to mirror.
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.