| paper | d4-conf-atal-2016-0228 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact polynomial-time solvable in \(m,\tau,L\), returning rational \(\epsilon^\ast\) and an optimal rational payoff-rate vector \(p^\ast\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.2
Given rational type masses \(\mu\) with \(\sum_t\mu_t=1\) and an explicitly represented rational piecewise-affine coalition-value function \(v(q)\) over feasible submass vectors \(q\in[0,\mu]\), compute the minimum \(\epsilon\) and nonnegative payoff rates \(p_t\) satisfying \(p^\top\mu=v(\mu)\) and \(p^\top q\ge v(q)-\epsilon\lVert q\rVert_1\) for every feasible deviation \(q\); return an exact optimum or certificate.
A characteristic-function game with \(\tau\) complete agent types: type \(t\) has mass \(\mu_t\), a deviating coalition is any submass vector \(q\le\mu\), and its value \(v(q)\) is given piecewise-affinely. Each type receives a common payoff rate \(p_t\), with total payoff fixed to \(v(\mu)\).
The explicit piecewise-affine encoding supplies tractability independently of Theorem 3.2’s \(W\)-only reduction, so this mirror does not test whether that structural simplification survives for continuous societies.
fatal: False
Covers the type-mass version of the grand-coalition weak least-core payoff task associated with Theorem 3.2. It leaves aside the theorem’s \(W\)-only sufficiency result, the search for \(W\), optimal coalition structure generation, the weak least-core+ result, and the operation savings.
The strongest anchor I see is Theorem 3.2, proved in this paper. It says that for the grand coalition, the minimum weak-\(\epsilon\) needed for a stable payoff vector can be found using only the coalitions in the Synergy Coalition Group \(W\). The paper gives the LP: minimize \(\epsilon\), subject to \(x_i\ge 0\), \(\sum_{i\in N}x_i=v(N)\), and \(\sum_{i\in C}x_i\ge v(C)-|C|\epsilon\) for every \((C,v(C))\in W\). Lemma 3.1 supplies the reason this restricted set of constraints suffices. The paper’s introduction also says coalition structure generation is NP-complete, citing [27], but it gives no numbered hardness theorem of its own; I would not use that sentence as a named anchor.
A plausible high-multiplicity regime is a large cooperative energy or computing consortium. Members share a small number \(\tau\) of complete types—say, types determined by technology, capacity, costs, and contractual terms—and the consortium pools the value of their joint activity. There may be millions of members but only dozens of types. A coalition is described by its type-mass vector \(q\), where \(q_t\) is the mass of type \(t\) participating. Its value depends on that aggregate composition. This preserves the paper’s question about how to divide transferable value so that subcoalitions have no excessive incentive to leave.
Here is the continuous problem I would hand to a prover: Type-Mass Weak Least-Core. An instance gives rational masses \(\mu\in\mathbb{Q}_{\ge0}^{\tau}\) with \(\sum_t\mu_t=1\), and a coalition-value function \(v(q)\) for every \(q\in[0,\mu]\). To make the input finite and computationally meaningful, give \(v\) as a rational piecewise-affine function: an explicit partition of \([0,\mu]\) into rational polyhedra \(P_r\), with \(v(q)=a_r^\top q+b_r\) on each \(P_r\), and \(v(0)=0\). The task is to return type-level payoff rates \(p_t\ge0\) and the smallest \(\epsilon\) such that
\[
p^\top\mu=v(\mu),\qquad
p^\top q\ge v(q)-\epsilon\lVert q\rVert_1
\quad\text{for every }q\in[0,\mu].
\]
The \(p_t\) values are the common per-unit payoffs for members of type \(t\); \(q\) ranges over every possible deviating subpopulation. The output is an exact optimal payoff vector and slack, or an equivalent exact certificate.
I expect this specified version to be tractable. For each polyhedral piece \(P_r\), finding the most violating deviation is a linear optimization problem: maximize \(v(q)-p^\top q-\epsilon\lVert q\rVert_1\) over \(P_r\). Equivalently, the robust constraints over each piece can be dualized into a finite rational LP. Thus the running time can be polynomial in the encoding size of the pieces, \(\tau\), and the rational bit length \(L\), with no dependence on the number of individual agents. A continuous analogue of the \(W\)-only reduction would be an interesting structural result, but the underlying payoff problem is already well-posed without presuming that reduction.
The authors should recognize this as the continuous version of their grand-coalition weak least-core problem: individual payoff coordinates become type-level rates, and finite subsets become submasses. My case deliberately covers Theorem 3.2’s grand-coalition payoff result, not the whole SCG-DP algorithm or its search for an optimal coalition structure. It keeps the population as the continuous object; it does not rely on making outcomes or time continuous.
The soft spot is the value-function representation. The paper permits an arbitrary characteristic function, while this mirror assumes coalition values are determined by aggregate type masses and have an explicit piecewise-affine description. That is a plausible regime for production or pooling values, but it is a restriction, and the paper itself does not establish the claimed polynomial bound. With arbitrary value tables or a pricing problem that is hard to solve, the tractability case may disappear. The follow-up questions are whether a continuous \(W\) can give an exact reduction, how far tractability extends beyond piecewise-affine values, and whether the paper’s optimal-structure and weak-least-core+ result has a tractable continuous counterpart.
The strongest anchor is real: Theorem 3.2 is a named result about finding the weak least core using only the Synergy Coalition Group \(W\). So I would not dismiss it for lacking a computational result. A plausible population regime is a large energy or production consortium with many members in a small number of complete types. If coalition value depends only on the masses of those types, a payoff rate for each type is also defensible: symmetry lets us average payoffs among indistinguishable members.
The best negative case is that the paper’s computational challenge is finding \(W\), not solving the least-core LP once its constraints are known. The theorem does not show that \(W\) is small or efficiently found. In the proposed mirror, an explicit piecewise-affine value function makes the task a standard robust LP: maximize the violation over each supplied polyhedral region, then dualize. That is a valid continuous problem, but its tractability follows from the chosen input representation rather than from a continuous counterpart of the paper’s SCG reduction. In a familiar subclass—monotone, concave, positively homogeneous production values—a supporting price vector gives a core allocation, so the minimum \(\epsilon\) is already zero. To avoid that collapse, one needs nonconvex values; but with an explicit piecewise-affine description the same generic LP argument applies, while a more compact oracle or circuit representation moves the complexity into the pricing problem.
A stronger proposed mirror would ask for a continuous analogue of \(W\): when can infinitely many possible submasses be reduced to a finite certificate that suffices for both coalition stability and optimal coalition formation? That would target the paper’s structural contribution more directly. But whether it is tractable depends on the chosen class of value functions, and the paper itself does not identify a natural continuous analogue or input model. A high-multiplicity game also needs a scaling law to turn finite coalition values into a limit; scalable convex technologies tend to restore the core, while persistent nonconvexities require more modelling choices.
That is the best case against: the most natural scalable regime makes the least-core objective degenerate, and the proposed tractable nonconvex formulation largely builds its tractability into the encoding. It does not defeat every worthwhile mirror. A carefully chosen nonconvex production model could make the continuous analogue of the SCG reduction a substantive question, so the universal negative remains weak.
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.