| paper | d4-conf-aaai-2015-0380 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: For every fixed \(s\geq1\), the threshold problem is in \(\mathrm P\). The attained optimum is \(1/s!\), so an assignment exists exactly when \(B\geq1/s!\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.5
Given a finite type set \(T\), rational masses \(\mu_t\), and a fixed coalition size \(s\), let \(\Omega=[0,1)\) be an atomless population with a measurable type map whose type regions have masses \(\mu_t\). Let coalition tasks be unordered sets of \(s\) distinct points, with measure \(\nu_s\) induced by \(\lambda^{\otimes s}/s!\). Find a measurable assignment \(a(S)\in S\) minimizing \(\operatorname*{ess\,sup}_{x\in\Omega} d\rho/d\lambda(x)\), where \(\rho(A)=\nu_s(\{S:a(S)\in A\})\).
Use the atomless population \((\Omega,\lambda)\), partitioned into type regions of masses \(\mu_t\); take unordered \(s\)-member coalitions as unit-cost tasks with measure \(\nu_s\); assign each task to one of its members and minimize maximum per-capita workload. The largest-gap cyclic rule assigns almost every task measurably and has constant workload density \(1/s!\), meeting the total-work lower bound.
The opponent's strongest point is that \(\mu\) alone does not encode coalition-specific values, and values depending only on type composition may let distinct-subset calculations be compressed; the proponent notes this possibility but does not establish when the paper's per-coalition tasks remain distinct.
fatal: False
The mirror covers the fixed-size coalition-allocation subproblem and balancing workload across members; it leaves allocation across all sizes, the cost of evaluating coalition values, coalition-structure generation, stability, and incentives aside.
The strongest mirror I see is the Continuous Size-\(s\) Coalition-Calculation Assignment problem. It mirrors the paper’s allocation task for one fixed coalition size, the subproblem handled by SingleSize, rather than claiming to continuize the whole coalition-formation process.
Theorem 5.5, proved in this paper (its proof is omitted for brevity), is my anchor. In the paper’s notation, for any increment array \(t\) and \(1\le i\le j\le n\), \(C(i,t)=C(j,t)\) if and only if there is an integer \(r\) with \(0\le r\le (n-i)s/(n\pi(t))\) such that \(j=i+r(n\pi(t)/s)\). Thus a given increment array repeats the same generated coalition at precisely those spaced starting agents. DCG uses this to know how many agents can use that array without duplicating its coalitions. The theorem is an algorithmic correctness result, not a claim that the problem is in P or NP-hard; the paper gives no numbered complexity-class result for DCG.
Here is the mirror. The instance has a finite type set \(T\), rational masses \(\mu_t\) summing to one, and a fixed coalition size \(s\). Represent the population by an atomless space \(\Omega=[0,1)\) with Lebesgue mass and a type map whose type-\(t\) region has mass \(\mu_t\). Each \(s\)-element subset \(S\subset\Omega\) is a coalition-calculation task. Give the space of these tasks the measure \(\nu_s\) induced by sampling \(s\) agents independently and treating orderings as the same coalition, scaled so its total mass is \(1/s!\), the limit of \(\binom Ns/N^s\).
A solution is a measurable rule \(a\) that assigns almost every task \(S\) to exactly one of its members: \(a(S)\in S\). Let \(\rho(A)=\nu_s(\{S:a(S)\in A\})\) be the calculation workload assigned to population subset \(A\). The objective is to minimize the maximum per-capita load, \(\operatorname*{ess\,sup}_{x\in\Omega} d\rho/d\lambda(x)\). Each calculation has unit cost, matching the paper’s balancing by number of coalition calculations.
This problem has a concrete continuous solution. Identify \(\Omega\) with a circle; for each coalition, assign the calculation to the member immediately following its largest gap around the circle. Ties occur on a measure-zero set. The rule is measurable and rotation-equivariant, so the assigned workload is uniform across the population: \(d\rho/d\lambda=1/s!\) almost everywhere. That is optimal, since the total task mass is \(1/s!\). Each coalition is assigned once, and no messages between agents are needed if they share the public rule and labels. The predicted answer is tractable, by symmetry and a direct construction.
The intended regime is a large community of agents with many repeated profiles and a small number \(\tau\) of types—for example, a large smart-grid or distributed-computing community with a few standardized participant classes. A coalition task still refers to a particular group of agents; the labels distinguish groups, as the paper’s numeric IDs do, without making agents with the same type different in preferences, costs, or capacities. The continuous problem captures the fixed-size workload-allocation question: every coalition’s calculation goes to a member, and the burden is balanced per capita. It does not cover coalition-structure generation, stability, incentives, or the evaluation complexity of the value function itself.
My weakest point is that in a strongly type-symmetric characteristic function, coalitions with the same type composition may have identical values, so calculating each named coalition separately can be redundant. The mirror is most convincing when coalition-specific calculations remain meaningful even among agents sharing a type—for example, because the calculation concerns a particular selected group. If value depends only on type composition, the paper’s “one calculation per coalition” task may collapse under aggregation, and this mirror becomes less compelling. A natural follow-up is to compare that type-compressed variant with the identity-specific task model, then study weighted calculations and how well the continuous allocation can be rounded for finite populations.
The paper has no named complexity result for a continuous mirror to preserve. Theorem 5.5 is a correctness lemma about when a finite increment array repeats a coalition as its starting agent changes. It does not classify the complexity of allocating coalition calculations. The strongest alternative anchor is therefore the allocation task itself, but the best version of that mirror runs into a dilemma about what counts as a distinct calculation.
If agents fall into a small number of complete types, then coalitions with the same type composition are indistinguishable for the game. For fixed size \(s\), there are only \(\binom{\tau+s-1}{s}\) such compositions. The value for a composition can be calculated once and reused; treating every named subset as a separate unit of work reinstates distinctions the type model says do not matter. If, instead, a coalition’s value depends on which particular agents belong to it, their identities or interaction data matter to the calculation. Those distinctions must be represented in the types or in additional input, so a finite distribution over a small support no longer describes the tasks the paper allocates.
The proposed continuum assignment makes this tension visible. Its measure on unordered \(s\)-tuples and largest-gap rule give a coherent way to distribute *sampled* coalition tasks across an atomless population. But the type distribution \(\mu\) alone does not specify those named tasks or their values. Adding a circle of individual labels supplies that missing structure; it preserves the identity-specific task family rather than obtaining it from the high-multiplicity model. And because the workload objective is measured almost everywhere, it records aggregate task intensity, not the paper’s exact accounting of every separately valued coalition.
So the strongest negative case is not that a continuous allocation model cannot be written down. It can. It is that the plausible high-multiplicity model collapses the paper’s distinct coalition calculations by type composition, while the model that preserves those calculations needs identity-level information absent from a finite type distribution. The paper’s main contribution is precisely the allocation of those identity-indexed calculations. This makes the anchor a poor fit for the programme’s continuous complexity landscape, though the case is not airtight: a separate, explicitly aggregate model of sampled coalition workloads could be worthwhile if the authors recognize it as their problem.
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.