| paper | Incentives for Early Arrival in Cooperative Games (Extended Abstract) |
| authors | Yaoxin Ge, Yao Zhang, Dengji Zhao, Zhihao Gavin Tang, Hu Fu, Pinyan Lu |
| venue | IJCAI 2025 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The numbered results are structural or axiomatic statements about mechanisms, not complexity results with an input encoding, running-time bound, approximation guarantee, or parameterized classification. Algorithm 1 does not supply such a result. The typed-mass synthesis problem is potentially worthwhile, but it is a new re-modeling of individual pivotality, arrival incentives, and Shapley fairness rather than a qualifying computational mirror of a named result.
fails bit a — no named computational result to mirror
The proposed \(R_a/z_a\) rewards are averages, and block-I4EA plus Aumann–Shapley fairness do not preserve the paper's individual first-critical-player allocation or per-player Shapley condition.
fatal: True
The proposed formulation touches Theorems 2–5 and the GM decomposition, but leaves the exact named-player mechanisms without a faithful population analogue and covers no named computational result.
The strongest honest positive case is conditional: this paper has a credible population mirror, but it has no qualifying ChoCo anchor under the stated rule.
None of its named results asserts NP-hardness, membership in \(P\), FPT, W[1]-hardness, or another computational classification. Theorem 1, proved here, says that DMC is I4EA exactly for submodular \(v\); Theorems 2–4, also proved here, establish correctness, completeness, and a structural characterization of RFC; Corollary 1 gives a structural subclass; and Theorem 5 proves that eRFC is SF and OIR, and is I4EA under a stated condition. “Complete” in Theorem 3 means complete as a mechanism, not computational completeness. Algorithm 1 is an algorithm over a set function represented on \(2^N\), but the paper gives no input encoding or running-time classification. Thus there are zero eligible computational anchors, and no per-anchor ChoCo verdict can honestly be claimed.
The best prospective mirror is nevertheless quite natural. I would call it Typed-Mass Online Cooperative Sharing, with Mass-eRFC as its lead mechanism problem.
An instance has \(\tau\) player types, rational masses \(\mu_1,\ldots,\mu_\tau\) with \(\sum_a\mu_a=1\), and a coordinatewise monotone value function
\[
V:[0,\mu_1]\times\cdots\times[0,\mu_\tau]\to\mathbb{Q}_{\ge 0},
\qquad V(0)=0.
\]
A type includes all relevant skills, funding capacity, costs, eligibility, and reward parameters. The value \(V(z)\) is the value created when mass \(z_a\) of each type has arrived. To make the computational problem finite, take \(V\) to be a rational piecewise-linear monotone function given explicitly, with a bounded number of regions.
An arrival history is a rational piecewise-linear path \(z(t)\) from \(0\) to \(\mu\), coordinatewise nondecreasing. A mechanism must output cumulative reward masses \(R_a(t)\), using only the arrived prefix of the path and the restriction of \(V\) to the arrived state. It must satisfy
\[
\sum_a R_a(t)=V(z(t)).
\]
Writing \(\rho_a(t)=R_a(t)/z_a(t)\) for the per-capita reward of type \(a\), online individual rationality requires \(\rho_a(t)\) never to decrease for already-arrived type-\(a\) mass. I4EA requires that moving any positive block of type-\(a\) mass earlier, while preserving the other arrivals, never decreases its final per-capita reward.
For fairness, use the continuum Shapley analogue
\[
\operatorname{ASV}_a(V,\mu)
=
\int_0^1 \partial_a V(\lambda\mu)\,d\lambda,
\]
so the total reward of type \(a\) is \(\mu_a\operatorname{ASV}_a(V,\mu)\). This is the expected marginal contribution under a random-priority arrival process in the continuum. For step-valued games, the derivative can be replaced by the corresponding clone-limit or Stieltjes marginal definition.
The computational problem is: given \(V\), \(\mu\), and a representation bound \(K\), decide whether there is a rational piecewise-linear online policy with at most \(K\) regions satisfying OIR, I4EA, and this mass-Shapley fairness condition, and, if so, output such a policy. Evaluation of the policy on a specified arrival prefix is part of the output guarantee.
The regime is plausible in exactly the settings the paper itself names: a startup with thousands of prospective investors divided into a small number of recurring funding or expertise types, or a large cohort of students divided into a few skill profiles. Here \(n\gg\tau\), mass is the fraction of the cohort arriving, and the action is genuinely about arrival timing and irrevocable online value sharing. Named individuals with idiosyncratic terms become separate types, as required by the high-multiplicity interpretation.
I would expect a Class A result for fixed \(\tau\), bounded piecewise-linear complexity, and structured \(V\), perhaps via a finite critical-state formulation, convex programming, or a continuous analogue of the paper’s GM decomposition. With unrestricted succinct monotone \(V\) and variable \(\tau\), the pricing over type orders and critical regions could instead be hard or continuum-specific. The main follow-up questions are whether Theorem 4’s critical-player characterization has a type-mass version, whether Mass-eRFC can be computed compactly, and whether rational mass solutions round back to finite clone populations with controlled error.
The weakest point is serious: RFC gives the entire value to one named player, whereas a continuum cannot give positive reward to an atomless individual. Mass-eRFC must therefore reward a positive-mass cohort, and the fairness condition becomes Aumann-Shapley or clone-limit fairness rather than literally the paper’s per-player Shapley value. That makes this an author-recognizable extension, not a direct continuization of Theorems 2–5. So the paper is a strong source of a promising mirror question, but not a qualifying computational-continuization case under the programme’s strict anchor rule.
The proposed mirror should be rejected under ChoCo’s anchor rule. The paper contains no qualifying computational result.
Theorem 1 is an axiomatic characterization of when DMC has I4EA. Theorems 2–4 concern OIR, Shapley fairness, completeness of RFC as a mechanism, and a structural characterization of \(0\)-\(1\) games. Theorem 5 gives another axiomatic guarantee for eRFC. None specifies an input encoding, running time, complexity class, approximation guarantee, or parameterized algorithm. “Complete” in Theorem 3 is mechanism-completeness, not computational completeness. Algorithm 1 does not repair this: it ranges over \(2^N\), has no complexity analysis, and assumes arbitrary set-function access. Turning its existence question into a new bounded-piecewise-linear policy-synthesis problem manufactures a computational problem that the paper never states.
More importantly, the proposed Mass-eRFC construction does not preserve the paper’s central object. High multiplicity itself is not the problem: a large cohort of investors or students divided into recurring types is perfectly plausible. The problem is that the paper’s incentives and mechanism are individual and order-sensitive.
In the finite model, DMC gives player \(i\) the quantity
\[
v(S)-v(S\setminus\{i\}),
\]
and RFC gives the entire value to the earliest critical named player. If many identical clones are compressed into one type, a mass quantity \(R_a\) records only the type’s aggregate reward. The ratio \(R_a/z_a\) is an average, not the reward of each clone. It cannot express whether a particular clone benefits from moving earlier or later. That is exactly the deviation tested by I4EA.
The atomless limit makes this substantive rather than merely technical. Removing one individual from a mass vector changes nothing, so individual marginal contribution and individual pivotality disappear. In a finite clone approximation, RFC may award value \(1\) to one earliest critical clone. As the number of clones grows, that reward is concentrated on a zero-mass point; it has no finite per-capita limit. If the reward is instead spread over the type mass, the mechanism is no longer RFC and the individual early-arrival comparison has been replaced by an aggregate or coalition condition.
The Aumann–Shapley expression
\[
\operatorname{ASV}_a(V,\mu)
=
\int_0^1 \partial_a V(\lambda\mu)\,d\lambda
\]
is a legitimate aggregate cost-sharing value in its own right. But it does not restore the paper’s Shapley-fairness condition. It fixes only the total expected reward of a type. It says nothing about which mass receives that reward, and therefore cannot by itself support individual I4EA or the RFC allocation. This is a re-modeling of both fairness and strategic agency, not a direct continuization.
The same failure reaches every structural theorem. Theorem 1’s marginal contribution becomes a differential allocation along an arrival path; “moving one player earlier” becomes a zero-measure perturbation, while moving a positive block earlier is a coalition deviation. Theorems 2–4 depend on a first critical player and on predicates such as \(v(\{i\})=0\) and
\[
S^*=\{i\in S:v(S)-v(S\setminus\{i\})=1\}.
\]
For an atomless population, there is no singleton with positive mass and generally no first member of a positive-measure critical set. A nontrivial \(0\)-\(1\) mass game must either be discontinuous at a threshold or assign value through a singular jump. A Stieltjes formulation can describe the aggregate jump, but it does not produce a first individual receiver.
The GM decomposition has the same boundary. Its finite consistency relies on decomposing restrictions of a set function into finitely many \(0\)-\(1\) games on named coalitions. A continuous layer-cake decomposition of \(V\) would generally be an integral over threshold games, and every threshold component inherits the missing first-critical-agent problem. If one instead makes positive-mass cohorts the “players,” the result is simply a finite weighted cooperative game; the population continuum has become a rescaling device.
The possible repairs all change the subject in one of these ways. Adding arrival priority or identity as a type coordinate preserves the original information, but then the type space is carrying the individual history that the mass model was meant to eliminate. Replacing individuals by positive-mass arrival blocks produces a finite block game. Adding a tagged atom to a continuum preserves the original player, but yields a mixed atomic–nonatomic model. None is a faithful mirror of the paper’s results over a society represented only by type masses.
Thus the positive case identifies a potentially interesting new mean-field online cost-sharing problem. It does not identify a continuous computational mirror of this paper. The universal claim that no conceivable extension could ever be worthwhile is too strong to prove in a modelling domain, but the paper should receive a negative ChoCo verdict: there is no named computational anchor, and every apparently promising mass formulation must replace the individual pivotality and arrival incentives that make the paper’s theorems what they are.
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.