| paper | d4-conf-ijcai-2011-0464 |
| 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: \(\mathrm P\): polynomial-time solvable in \(m,\tau,L\); the minimum subsidy can also be computed exactly. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3, item 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), a rational distribution \(\mu\), total mass \(M>2\), and type masses \(a_t=M\mu_t\), let \(V\) be a rational, nonnegative, monotone, superadditive value function on \(\prod_{t\in T}[0,a_t]\), represented by an explicit rational piecewise-affine subdivision. What is the minimum \(\Delta\ge 0\) for which there are per-unit type payoffs \(p_t\) satisfying \(\sum_t p_ta_t=V(a)+\Delta\) and \(\sum_t p_tq_t\ge V(q)\) for every \(q\le a\) with \(\sum_tq_t\le 2\)?
A continuous TU game with types \(t\), masses \(a_t=M\mu_t\), and coalition values \(V(q)\); choose common per-unit payoffs \(p_t\) and minimize the grand-coalition subsidy \(\Delta\), subject to stability against every coalition mass vector \(q\) of total mass at most \(2\).
A cap of \(2\) absolute mass units is scale-dependent: with normalized total mass \(1\), it becomes \(2/M\), while a fixed-share cap no longer inherits the paper’s \(k=2\) bound.
fatal: False
Covers the bounded-coalition-size stability result in Proposition 3, item 1. It leaves the other restricted-cooperation bounds, the CoS and least-core comparisons, and the paper’s conjectures aside.
My strongest anchor is Proposition 3, item 1, proved in this paper. It says that for a superadditive TU game whose permitted deviating coalitions have size at most \(k\), the relative cost of stability is at most \(\min\{k,\sqrt n\}\). For \(k=2\), it also gives a greedy algorithm that finds a stable superimputation of cost \(2\). The proposition says the bounds are tight up to a small additive constant. This is a constructive algorithmic result, though the paper does not state a formal complexity classification such as P or NP-hardness. The grand coalition’s value must remain intact when applying the deviation restriction, as the proposition’s proof and cost ratio require.
A credible high-multiplicity setting is a large cooperative of micro-producers or service providers. Each type records all attributes relevant to participation and value, such as capacity, technology, market, and reservation terms. A type’s mass is its share of the population; the total mass can also be measured in participant-equivalent units. There may be a very large total mass \(M\) but only \(\tau\) types. The cooperative’s value depends on the composition of a coalition, not on the names of its members. An institutional rule limits breakaway coalitions to two participant-equivalent units, and an outside authority can subsidize the grand coalition. That cap has an economic interpretation even when the population is large: it limits the absolute size of a breakaway, rather than its share of the whole population.
Here is the continuous problem I would put to a prover, Two-Unit Cost of Stability. An instance has a finite type set \(T\), a rational population distribution \(\mu\), total mass \(M>2\), and type masses \(a_t=M\mu_t\). It also has a nonnegative, monotone, superadditive coalition-value function \(V\) on \(\prod_{t\in T}[0,a_t]\), with \(V(0)=0\). To make the computational question finite, give \(V\) as a rational piecewise-affine function on an explicit rational polyhedral subdivision, with \(H\) cells. A coalition is a mass vector \(q\le a\) with \(\sum_t q_t\le2\).
Find the minimum subsidy \(\Delta^*\) and a per-unit payoff \(p_t\) for each type such that
\[ \Delta\ge0,\qquad \sum_t p_t a_t=V(a)+\Delta,\qquad \sum_t p_t q_t\ge V(q) \quad\text{for every allowed }q. \]
A solution is an optimal rational pair \((p,\Delta^*)\). The payoff is per unit of type mass; requiring a common payoff within a type is appropriate because members of that type are interchangeable in this model. The finite result predicts the continuous guarantee \(\Delta^*\le V(a)\), or equivalently a total grand-coalition payment at most \(2V(a)\). Computing the exact minimum goes beyond the finite proposition’s witness guarantee, but it asks the paper’s underlying Cost of Stability question.
For the stated input representation, I expect the optimization problem to be Class A. Given a candidate \(p\), a violated stability constraint can be found by maximizing \(V(q)-p\cdot q\) over the allowed mass vectors. On each listed cell this is a linear program, so the explicit subdivision gives a polynomial separation procedure; the outer problem is an LP in \(\tau\) payoff variables and the subsidy. The continuous analogue of the factor-two guarantee is a separate theorem to establish. I expect it to hold in this restricted model, but the finite greedy proof does not establish it.
This mirror covers only Proposition 3’s bounded-coalition stability result. It does not mirror the paper’s comparison between the strong least core and the Cost of Stability, its conjectures, or all of its restricted-network results. Those are separate questions.
The weakest point is the move from coalitions of at most two discrete agents to coalitions of at most two units of continuous mass. The continuous model includes fractional mixtures of types that have no direct counterpart in the greedy pair-selection proof. The type-based value function and explicit piecewise-linear representation also narrow the paper’s arbitrary characteristic functions. The scenario is plausible, and the question remains about the same stability-and-subsidy problem, but the finite bound cannot simply be declared to carry over.
Proposition 3(1) is the strongest anchor, but its key parameter is the *integer number of agents* in a permitted coalition. The proof uses that directly: choose a coalition \(S\) of size at most \(k\), then use its agents to bound the total weight of the balanced collection. That step has no immediate analogue for divisible mass. In a continuous model, coalitions can be arbitrarily small, and two coalitions may intersect only on a set of zero mass.
The proposed “two-unit” version exposes the modelling problem. If the population has total mass \(1\), a cap of \(2\) permits every coalition. If the cap means two participant-equivalent units in a population of size \(M\), it becomes a share of \(2/M\), which vanishes as \(M\) grows. Mass vectors also permit fractions of those units to cooperate. A cap fixed as a positive share \(\kappa\) avoids that issue, but the paper’s bound \(\min\{k,\sqrt n\}\) then has \(k\) growing with \(n\); it supplies no finite continuum guarantee. These choices define different cooperation regimes, and none carries Proposition 3’s cardinality argument across intact.
The proposed piecewise-affine model does make exact Cost of Stability a coherent computational problem. Given that representation, violated constraints can be found by checking the listed cells, so the outer optimization is an LP with a polynomial separation procedure. But that tractability comes from supplying an explicit subdivision of the continuous value function. It does not recover the paper’s finite-agent bound, and the resulting running time is measured in a representation that may be much larger than a natural compact description of coalition values. This weakens the case that the proposed problem tests what Proposition 3 discovered.
That is a substantial objection to this anchor, not a decisive objection to every mirror. A continuous TU game whose value depends on type masses is a sensible object; per-type payoffs and a minimum stabilizing subsidy are recognizable versions of the paper’s question. The paper’s CoS and least-core comparisons also invite continuous formulations without a bounded-coalition cap. I cannot honestly rule those out as worthwhile computational questions. The negative case is therefore strongest against claiming that Proposition 3’s finite \(k\)-bound continues to the continuum; it does not establish that this paper has no worthwhile continuous 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.