| paper | d4-conf-atal-2013-0118 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 13
statement extracted from the paper’s text layer
Given an atomless unit-mass population of one complete type and a nonnegative rational piecewise-linear worth function \(W:[0,1]\to\mathbb{Q}_{\ge 0}\) with \(W(0)=0\), a coalition \(A\) has worth \(W(|A|)\). Choose a nonnegative tax schedule \(q\) with \(q(1)=0\) and \(q(x)\le W(x)\), and a nonnegative payoff density \(p\) with \(\int_I p(i)\,di=W(1)\), such that \(\int_A p(i)\,di\ge W(|A|)-q(|A|)\) for every measurable \(A\); compute a stable schedule minimizing \(\int_0^1 q(x)\,dx\).
An atomless anonymous TU game with coalition worth \(W(x)\) at mass \(x\), a tax schedule over coalition masses, a payoff density, core stability for every measurable coalition, and total tax measured across mass levels.
The mirror covers Theorem 13’s optimal-tax policy for anonymous games. It leaves the paper’s general taxation results, multi-type games, and its other characterizations untouched.
The strongest mirror is the paper’s anonymous-game result, Theorem 13. It is proved in this paper, not cited from elsewhere: for an \(n\)-agent anonymous game with \(v(S)=f(|S|)\), taxing each coalition of size \(s\) by
\[
t_S=\max\left\{0,\ f(s)-\frac{s}{n}f(n)\right\}
\]
is an optimal taxation policy. The tax is zero for the grand coalition. The theorem gives an explicit policy for the paper’s objective of minimizing total tax across coalitions.
Here is the continuous problem I would hand to a prover. Call it Anonymous Continuum Coalition Taxation. An instance is an atomless population \(I=[0,1]\), all of one complete type, and a nonnegative rational piecewise-linear worth function \(W:[0,1]\to\mathbb{Q}_{\ge0}\), with \(W(0)=0\). A measurable coalition \(A\subseteq I\) has worth \(W(|A|)\), where \(|A|\) is its population mass. Choose a tax schedule \(q:[0,1]\to\mathbb{R}_{\ge0}\), with \(q(1)=0\) and \(q(x)\le W(x)\). The taxed worth of \(A\) is \(W(|A|)-q(|A|)\). A solution must also give a nonnegative payoff density \(p\) such that
\[
\int_I p(i)\,di=W(1)
\quad\text{and}\quad
\int_A p(i)\,di\ge W(|A|)-q(|A|)
\]
for every measurable coalition \(A\). Among stable schedules, minimize \(J(q)=\int_0^1q(x)\,dx\), the aggregate tax across coalition mass levels.
The answer is
\[
q^*(x)=\max\{0,\ W(x)-xW(1)\},
\qquad p(i)=W(1).
\]
This is not just an appealing guess based on symmetry. For any stable schedule, write \(U(x)=W(x)-q(x)\). Since every coalition of mass \(x\) must be protected, \(U(x)\) cannot exceed the payoff received by every such coalition. Averaged over coalitions of mass \(x\), their payoff is \(xW(1)\), so \(U(x)\le xW(1)\). Also \(U(x)\le W(x)\). The constant density \(p=W(1)\) attains both bounds at once. Thus \(q^*\) is pointwise minimal among stable schedules, and consequently minimizes the integral objective—and any other nonnegative weighting of mass levels.
The high-multiplicity regime is a large cooperative of interchangeable micro-producers, such as standardized storage units whose coalition’s revenue depends on its aggregate capacity, not the identities of its members. Their shared type includes the relevant capacity, costs, and contract terms. With \(n\) such agents, take \(v_n(S)=nW(|S|/n)\). Applying Theorem 13 and dividing its tax by \(n\) gives exactly \(q^*(x)\) at each grid point \(x=s/n\). The continuous question extends that policy from those discrete coalition sizes to every mass level. Here the population is the continuous object; the worth function and payoff allocation remain the cooperative-game ingredients.
For a piecewise-linear \(W\), this is a tractable, Class A mirror: the formula gives the schedule directly, and its explicit piecewise-linear representation requires only polynomially many rational operations in the number of input segments and their bit length. The result covers Theorem 13’s anonymous optimal-taxation finding. It does not claim a complexity result for the paper’s general taxation problem.
The weakest point is the tax aggregate. The paper sums over the finite set of coalitions, while the continuum model integrates over mass levels; an atomless population has no corresponding counting measure on its coalitions. This is a real modeling choice. The case survives it because Theorem 13’s policy is pointwise minimal: the same schedule is optimal regardless of how coalition mass levels receive nonnegative weight. I would not extend that robustness claim to a multi-type game, where different payoff densities can trade off taxes across coalition compositions.
That extension is a natural next question: with finitely many complete types, represent society by type masses, coalition worth by a function of its composition vector, and payoffs by type-specific densities. Then ask for a stable tax schedule minimizing tax over coalition compositions, and determine when the resulting optimization is tractable. The paper’s anonymous result is a clean one-type anchor for that broader computational programme.
The strongest objection to the proposed mirror is fidelity to the paper’s objective, not whether an atomless population is sensible. A cooperative of interchangeable storage units is a plausible high-multiplicity setting, and one type is allowed by the programme. I would not argue that this scenario fails the population test.
Theorem 13 gives an optimization result, though not a complexity classification: for anonymous games it identifies the optimal tax directly. The proposed continuum problem inherits that answer almost verbatim. For any stable schedule and payoff density \(p\), averaging \(\int_A p\) over all coalitions \(A\) of mass \(x\) gives \(xW(1)\). Thus \(W(x)-q(x)\le xW(1)\); dominance also gives \(W(x)-q(x)\le W(x)\). The constant density \(p=W(1)\) meets both bounds, yielding \(q(x)=\max\{0,W(x)-xW(1)\}\). This is the finite theorem’s symmetry argument lifted to a continuum, rather than a new computational question.
There is also a mismatch in what gets aggregated. The paper’s objective sums tax over coalitions, so in an anonymous \(n\)-agent game it weights size \(s\) by \(\binom ns\). With the proposed scaling \(v_n(S)=nW(|S|/n)\), total tax is \(n\sum_s\binom ns q(s/n)\), whereas the proposed objective is \(\int_0^1q(x)\,dx\). Under uniform sampling of coalitions, the naturally normalized finite objective concentrates at mass \(1/2\); a different coalition-formation process can concentrate it elsewhere. The proponent is right that pointwise minimality preserves the same optimal schedule under any nonnegative weighting. That saves the policy claim, but it also means the integral objective adds no content to this one-type result and does not capture the paper’s aggregate-tax criterion.
A multi-type extension could pose a richer question: worth depends on a coalition’s type-composition vector, and payoffs are type-specific. But it needs an encoded worth function and a measure over coalition compositions. The finite paper’s sum over coalitions induces composition weights that concentrate around a typical composition; an unweighted integral over composition vectors chooses a different objective. Picking a smooth measure may define a worthwhile new optimization problem, but Theorem 13 does not determine that choice or supply a result for the resulting model.
So the negative case is strongest against treating the offered one-type continuation as a meaningful new computational contribution: it changes the aggregate objective and then recovers the paper’s formula by a direct averaging argument. It does not establish the universal claim that no worthwhile mirror exists. The microproducer scenario is coherent, and a carefully specified multi-type model could be worth studying on its own. On the material here, an airtight “no scenario” verdict would overstate the case.
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.