| paper | Resource Task Games |
| authors | — |
| venue | AAMAS 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 5.2
Given complete agent types \(\Theta\), rational masses \(\mu_\theta\), finite feasible assignment sets \(\mathcal A_\theta\), and explicitly encoded exact task, value, and cost functions, a candidate mass coalition structure \(Q=(q^1,\ldots,q^\ell)\) satisfies \(\sum_j q^j_{\theta,X}=\mu_\theta\). A deviation selects \(r^j_{\theta,X}\) with \(0\le r^j_{\theta,X}\le q^j_{\theta,X}\), sets \(q=\sum_j r^j\), and gives each participating pair \((\theta,X)\) pessimistic utility \(u^\downarrow_{\theta,X}(q)=\inf_y[v_\theta(t(A(q)+A(y)))-\operatorname{cost}_\theta(X)]\), where \(A(z)=\sum_{\theta,X}z_{\theta,X}X\) and \(y\) ranges over feasible residual mass assignments. Decide whether there is no nonzero deviation for which every participating source cell strictly improves, i.e. \(u^\downarrow_{\theta,X}(q)>u^\downarrow_{\theta,X}(q^j)\) whenever \(r^j_{\theta,X}>0\).
A high-multiplicity RTG with complete types \(\theta\), continuous masses \(\mu_\theta\), coalition variables \(q^j_{\theta,X}\), deviation variables \(r^j_{\theta,X}\), and pessimistic outside assignments \(y_{\theta,X}\); the predicate is absence of a positive-mass blocking coalition under the original task utility minus individual assignment cost.
The proposed \(\exists\mathbf{x}\,\forall\mathbf{y}\) reduction is not valid under unrestricted split mass: mixed \(X\)-assignments can satisfy the fractional extension, so a purity or unanimity gadget and an exact function encoding are still needed.
fatal: False
The mirror covers \(\textsc{PCORE\ MEMBERSHIP}\) from Proposition 5.2 only; it leaves WORST-CASE RESOURCE ASSIGNMENT, PCORE NON-EMPTINESS, and the paper's structural closure and TU-encoding results aside.
The strongest positive case is a single anchor: Proposition 5.2, proved in this paper, which states that PCORE MEMBERSHIP is \(\Pi^p_2\)-complete. I would mirror it with the following problem.
Call the problem \(\textsc{Mass-PCORE-Membership}_{\infty}\). An instance has a finite set of complete agent types \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), finitely many resource and task types, and for each \(\theta\) a finite set \(\mathcal A_\theta\) of feasible individual resource assignments. A type includes its endowment, cost function, and value function, so two agents of the same type are interchangeable in every respect used by the game. For a finite-support coalition \(q\), let \(q_{\theta,X}\) be the mass of type-\(\theta\) agents in that coalition using assignment \(X\). Thus a coalition is represented by a mass vector \(q\), with
\[ \sum_{X\in\mathcal A_\theta}q_{\theta,X}\le \mu_\theta. \]
Its aggregate resource allocation is
\[ A(q)=\sum_{\theta\in\Theta}\sum_{X\in\mathcal A_\theta}q_{\theta,X}X. \]
The remaining population can make any feasible outside assignment \(y\), using the residual mass \(\mu_\theta-\sum_Xq_{\theta,X}\). A type-\(\theta\) member using \(X\) then has pessimistic utility
\[ U^\downarrow_{\theta,X}(q) = \inf_{y} \left[ v_\theta\bigl(t_1(A(q)+A(y)),\ldots,t_k(A(q)+A(y))\bigr) - \operatorname{cost}_\theta(X) \right]. \]
A candidate coalition structure is a finite list \(q^1,\ldots,q^\ell\) whose masses partition every type:
\[ \sum_{j=1}^{\ell}q^j_{\theta,X}=\mu_\theta. \]
The question is whether this structure is in the p-core: namely, whether there is no positive-mass deviating coalition \(q\), together with a specification of which current coalition each deviator leaves, such that every participating type-assignment pair strictly improves its pessimistic utility.
This is recognisably the paper’s problem. The population is now continuous, but the object remains a resource-task game: agents pool resources, tasks have aggregate completion states, agents have costs and preferences over those states, and stability is still defined by the absence of a blocking coalition under pessimistic externalities. The decision variable is a mass allocation over coalitions and resource assignments; the objective is the same stability predicate as in PCORE MEMBERSHIP.
The natural regime is a large fleet of interchangeable resource-bearing units: for example, many edge-computing devices, energy-storage units, or emergency-response teams with a small number of capacity and preference profiles. There may be millions of agents but only a few dozen complete types. Total endowments and task capacities should be normalized per capita, or equivalently scaled with population size; otherwise fixed task capacities would make the large-population limit degenerate. Rational masses \(\mu_\theta=n_\theta/N\) recover finite clone populations after clearing denominators.
I expect this problem to be Class B: hardness transfers. The paper’s \(\Pi^p_2\)-hardness comes from the quantified structure of the p-core test, not from having many named agents. The paper reduces from formulas of the form
\[ \exists \mathbf{x}\,\forall \mathbf{y}\,\phi(\mathbf{x},\mathbf{y}). \]
The same alternation survives in the mass model. Use two large homogeneous types \(X\) and \(Y\), with masses \(1/2\) each. Type \(X\) controls the existential variables and type \(Y\) controls the universal variables. A candidate grand coalition has no resources allocated. A deviating \(X\)-coalition chooses a Boolean assignment to \(\mathbf{x}\); the pessimistic utility takes the infimum over all outside assignments or distributions of the \(Y\)-mass.
To prevent fractional splitting from creating a spurious witness, the value function can give \(X\) positive utility only when the entire \(X\)-mass joins the deviation and each existential variable is assigned purely \(0\) or \(1\). For the universal variables, use the natural fractional extension of a Boolean \(3\)-CNF: a literal has value \(p\) or \(1-p\), and a clause has value \(\min\{1,\) sum of its literal values\(\}\). On pure assignments this agrees exactly with \(\phi\). If a fixed \(X\)-assignment satisfies \(\phi\) for every pure \(Y\)-assignment, each clause is either secured by an \(X\)-literal or is tautological in the \(Y\)-variables, so mixed \(Y\)-mass cannot reduce the value. If some pure \(Y\)-assignment falsifies \(\phi\), that assignment remains an admissible pessimistic outside assignment.
Give \(Y\) a maximum utility already attained at the candidate structure, so no coalition containing \(Y\) can block. Assuming, as in the paper, that \(\phi(\mathbf{0},\mathbf{0})\) is false, the candidate is blocked exactly when there exists an \(X\)-assignment that satisfies \(\phi\) against every \(Y\)-assignment. Hence the continuous problem contains the paper’s \(\Pi^p_2\)-hardness mechanism, while the large population merely supplies repeated interchangeable agents. The combinatorics live in the task agenda and Boolean variables, so this is transferred hardness rather than continuum-specific hardness.
I would not claim that the full arbitrary-function version is already \(\Pi^p_2\)-complete. The continuous representation needs a bit model: rational piecewise-linear functions, arithmetic circuits, or some other explicit encoding. With nonlinear real-valued functions, the problem may acquire additional real-algebraic complexity. That creates useful follow-up questions: whether the finite-type piecewise-linear version has a matching upper bound; how continuous p-core membership rounds to a finite clone population; whether the problem is fixed-parameter tractable in \(|\Theta|\); and whether unrestricted continuous resources produce a genuinely Class C boundary.
My weakest point is that the paper itself assumes finitely many agents and does not analyse mass-splitting or real-valued coalition descriptions. The proposed problem is therefore an extension, not a theorem already implicit in the paper. In particular, positive-mass deviations replace one-agent deviations, and arbitrary task/value functions require a new representation theory. But the extension preserves the paper’s central computational question, has a credible high-multiplicity resource-allocation regime, and retains the paper’s main quantified hardness mechanism. I would limit the claim to this one result and leave WORST-CASE RESOURCE ASSIGNMENT and PCORE NON-EMPTINESS for separate mirrors.
The proponent has chosen a genuine named computational anchor: Proposition 5.2 is a real \(\Pi^p_2\)-completeness result. The strongest objection is therefore not that the paper lacks a computational theorem, but that the proposed mass problem does not preserve the object whose complexity was proved.
The reduction uses two named agents, \(x\) and \(y\). Agent \(x\) chooses one integral Boolean assignment, while agent \(y\) chooses one opposing assignment. In the proposed mirror, a positive-mass coalition of type \(X\) may contain only part of the \(X\)-population and may split its mass across different assignments. The task functions see only aggregate resource totals, so this creates mixed assignments that have no counterpart in the original reduction.
The proponent’s “natural fractional CNF” extension does not fix this. Consider
\[ \phi(x_1,x_2,y)= (\neg x_1\lor x_2) \land(x_1\lor\neg x_2) \land(\neg y\lor x_1\lor x_2) \land(y\lor\neg x_1\lor\neg x_2). \]
No pure assignment to \(x_1,x_2\) satisfies \(\phi\) for every \(y\): the first two clauses force \(x_1=x_2\), while the last two clauses then require contradictory values depending on \(y\). But under the proposed fractional clause semantics, \(x_1=x_2=\tfrac12\) satisfies every clause for both \(y=0\) and \(y=1\): each relevant clause has literal-value sum at least \(1\). Thus the continuous deviation supplies a witness even though the quantified Boolean formula is false. The statement that a pure counterassignment for \(Y\) remains admissible does not prevent this, because it need not falsify the fractional extension.
The obvious repair is to reward \(X\) only when its entire mass joins and every variable is at an endpoint \(0\) or \(1\). But that is a substantive synchronization and purity gadget, not a routine mass replacement. With regular continuous task and value functions, a function that is positive exactly at the endpoint profiles and zero at arbitrarily nearby mixed profiles is discontinuous. One can admit equality tests or an explicit unanimity task, but then the complexity depends on a newly introduced global coordination predicate. Alternatively, one can forbid splitting or require all clones of a type to take the same action; that turns the type mass into one indivisible strategic bloc rather than a population of interchangeable agents. Making each complete Boolean assignment a separate type avoids the problem only by moving the strategic choice into an exponentially large type space.
There is also no settled complexity problem yet in the proponent’s formulation. Coalition masses and pessimistic outside assignments are real vectors, and arbitrary task/value functions can make infima non-attained and certificates non-finite. Restricting to rational piecewise-linear functions would give a usable bit model, but it also makes the exact purity repair unavailable without adding nonregular primitives.
So I would reject the proposed formulation as a direct continuous mirror of Proposition 5.2. It is either a genuinely fractional robust coalition game, in which the paper’s reduction no longer applies, or a synchronized-cohort game engineered to reproduce the reduction, in which the population continuum has been largely neutralized.
That said, the universal negative is not airtight. If one accepts a plausible public-good RTG with explicit discontinuous unanimity tasks and coordinated cohorts, the proponent can construct a recognizable Class-B extension. The honest conclusion is therefore narrower: the current case does not establish a worthwhile mirror without substantial new modelling choices; it does not prove that no such extension could ever be worthwhile.
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.