| paper | d4-conf-sagt-2013-0004 |
| 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: Polynomial-time solvable: the exact allocation function belongs to \(\mathrm{FP}\) for fixed \(d\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given rational positive type masses \(\mu\), a rational polynomial worth function \(V\) of fixed total degree with \(V(0)=0\), a finite group \(H\) permuting equal-mass types, and an \(H\)-invariant rational distribution \(\Pi\) over coordinatewise nondecreasing piecewise-linear paths from \(0\) to \(\mu\), compute exactly, for each type \(t\), \(\phi_t(V)=\mathbb{E}_{q\sim\Pi}\!\left[\int_0^1 \partial_t V(q(s))\,\dot q_t(s)\,ds\right]\).
A society has a fixed finite set \(T\) of interchangeable contributor types, with rational mass \(\mu_t>0\) for each type. Coalition mass is \(x\in\prod_{t\in T}[0,\mu_t]\), worth is a fixed-degree rational polynomial \(V(x)\), and an explicit invariant mixture of monotone paths from \(0\) to \(\mu\) represents mass arrival orders. The decision output is the exact aggregate marginal allocation \(\phi_t\) to each type; each member of type \(t\) receives \(\phi_t/\mu_t\).
The mirror's easy computation comes from the newly specified fixed-degree polynomial and explicit path-mixture encoding; Proposition 1 itself contains no complexity analysis.
fatal: False
The mirror covers Proposition 1's construction of symmetric quasi-values by averaging marginal operators. It leaves Theorem 1's dimension formula and Theorems 2–3's uniqueness and group-classification results in their finite axiomatic form.
The strongest case I can make is for a narrow mirror of the paper’s marginal-operator construction. The paper has no named result asserting that a problem is NP-hard, in P, FPT, or otherwise classified by complexity. Its best algorithmic anchor is Proposition 1, proved in the paper: for \(G\le S_n\), if a probability distribution \(A_\pi\) over permutations is constant on the left cosets of \(G\), then the weighted average \(\sum_{\pi\in S_n} A_\pi m_\pi\) of the marginal operators is a \(G\)-symmetric quasi-value. Here \(m_\pi\) assigns each player their marginal contribution in arrival order \(\pi\). There is no comparable hardness result in the paper, so this is the anchor I would use.
A plausible regime is a large cooperative organization with many contributors in a fixed number \(\tau\) of interchangeable roles. A type records everything about a contributor that affects the game; \(\mu_t\) is the fraction of the population in role \(t\), with \(\sum_t\mu_t=1\). The society grows while \(\tau\) stays small. A coalition is described by its mass vector \(x\in\prod_{t\in T}[0,\mu_t]\), and its worth is \(V(x)\). This makes the population continuous and the coalition description fractional, as the high-multiplicity setting calls for.
The corresponding prover question could be called Path-Marginal Allocation\(_\infty\). An instance gives rational masses \(\mu\), a rational polynomial worth function \(V\) of fixed total degree with \(V(0)=0\), a finite group \(H\) relabeling equal-mass types, and a finite rational mixture \(\Pi\) of piecewise-linear paths \(q\) from \(0\) to \(\mu\). Each path is coordinatewise nondecreasing, and \(\Pi\) is invariant under \(H\). The task is to compute the exact aggregate allocation to each type:
\[
\phi_t(V)=\mathbb{E}_{q\sim\Pi}\!\left[\int_0^1 \partial_t V(q(s))\,\dot q_t(s)\,ds\right].
\]
Each member of type \(t\) receives \(\phi_t(V)/\mu_t\). The paths are the continuous counterpart of random arrival orders; the integral assigns each type its marginal contributions as mass joins the coalition. A solution is the exact rational vector \((\phi_t)_{t\in T}\). For this explicit input representation, I expect a Class A result: with degree fixed, the integrals along each path segment can be evaluated exactly in time polynomial in the input size. This is a proposed complexity result for the mirror, not a claim made by the paper.
The authors would likely recognize this as a continuous analogue of Proposition 1: averaging marginal contributions over invariant arrival orders becomes averaging marginal contributions over invariant mass-growth paths. The mirror covers that construction only. It does not extend the paper’s dimension formula or its uniqueness classification. In particular, Theorem 2, proved in the paper, says that a finite player set has a unique \(G\)-symmetric quasi-value exactly when \(G\) acts supertransitively—each subset’s stabilizer acts transitively on that subset. Equivalently, \(G=S_\Omega\), \(G=A_\Omega\) for \(|\Omega|>3\), or \(G\) is the exotic \(S_5\) embedding in \(S_6\). That is an axiomatic classification, not a computational result; continuizing it would make a weaker ChoCo case.
The main follow-up questions are whether every suitably symmetric continuous value can be represented by a path mixture, and which such mixtures arise as limits of finite random orders. The mirror’s soft spot is that its tractability comes largely from the explicit polynomial and path-mixture encoding. The paper’s proposition is a construction, not a complexity theorem, and its finite setting already permits direct averaging. So this is a credible population-continuous analogue of one proved result, but a modest computational contribution rather than a strong complexity-landscape mirror.
The negative case is strongest at the level of what the paper actually contributes: it contains no result about the complexity of a computational problem. Theorem 1 gives the dimension of an affine space of quasi-values; Theorems 2 and 3 classify groups for which that space is a singleton. Those are axiomatic and algebraic results. Proposition 1 is the closest thing to an algorithmic anchor, but it says that a coset-invariant average of marginal operators is a \(G\)-symmetric quasi-value. It neither poses a computational problem nor gives a complexity bound.
The proponent’s role-based society is a plausible high-multiplicity setting, and a continuous worth function \(V(x)\) is a coherent model for it. But the proposed Path-Marginal Allocation problem adds the polynomial \(V\) and an explicit mixture of paths as inputs, then asks for their line integrals. That is not the computational content of Proposition 1: it replaces a structural statement about symmetry with evaluation of a newly specified functional. With explicit paths and a fixed-degree polynomial, the calculation is built into the representation. If the inputs are made succinct enough to create a harder computation, the complexity will depend on that new encoding; the paper gives no reason to treat it as a mirror of its result.
The better-matched role-population version does not fix this gap. Let the finite players be many interchangeable contributors in each of a few roles, with coalition worth determined by role counts. Averaging marginal contributions over finite arrival orders may then converge to an average over mass-growth paths. That is a sensible continuous analogue of the construction. But the resulting claim is still that an appropriately invariant average has the corresponding symmetry. Its proof would be an equivariance or limit argument, not a complexity result. Trying instead to continue the dimension or uniqueness classification leads back to the paper’s axiomatic subject. Its arbitrary group actions on individually labeled players do not supply a computational problem over population masses.
So the proposed mirror can be a reasonable neighboring question, but it is not strong evidence that this paper belongs in a programme about the complexity landscape of continuous societies. The case against is weaker than a proof of “no worthwhile mirror in any scenario”: a compactly encoded, structured cooperative-game problem could be worth studying. But making that case would require adding the computational problem and its representation; neither is present in this paper.
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.