| paper | d4-conf-atal-2014-0233 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: All limits exist, and the entire vector is exactly computable in polynomial time in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type shares \(\mu_t>0\) summing to \(1\), qualities \(w_t>0\), and reliabilities \(r_t\in(0,1)\), form for each scale \(M\) a random population with independent counts \(N_t\sim\operatorname{Poisson}(M\mu_t)\). Conditional on those counts, use the paper’s reliability-extension Max-Game and its ordinary finite Shapley values \(\phi_i\). For each type \(t\), compute the high-multiplicity limit \(\lim_{M\to\infty}\mathbb{E}[\sum_{i:\,\mathrm{type}(i)=t}\phi_i]\), and determine whether these limits admit an exact polynomial-time algorithm in \(|T|\) and the input bit length.
A type distribution \(\mu\) over interchangeable workers with type-specific quality \(w_t\) and survival probability \(r_t\), replicated at scale \(M\). The output is each type’s expected total ordinary Shapley payoff, grouped within the finite Poissonized population before taking the limit as \(M\to\infty\); this boundary-layer rule gives meaning to the allocation where a bare atomless value function is flat.
For every nonzero atomless coalition, the highest-quality type present determines the value, so the coalition-value function is flat along positive-mass paths; the nonzero Shapley allocation therefore depends on a finite-ordering boundary layer that the bare distribution \(\mu\) does not specify.
fatal: False
The mirror covers Theorem 3 through type-level Shapley totals in the high-multiplicity limit. It does not cover Theorem 2’s Banzhaf index, the core and Cost of Stability results, or the sabotage results.
I would make a positive case for a narrow mirror of the paper’s payoff-index computations: fair ex-ante division in a large pool of interchangeable, failure-prone agents.
Consider a crowdsourcing platform that hires many workers to solve the same task and keeps the best successful submission. A type is a worker’s quality \(w_t\) and success probability \(r_t\), together with any other attributes the game uses. Workers of one type are interchangeable. A plausible regime is tens of thousands of workers in a few dozen or hundred quality-and-reliability groups: the population is large, while the support size \(\tau\) is moderate.
Here is the continuous model I would hand to a prover. The input is a rational type distribution \(\mu\), with \(\sum_t\mu_t=1\), a rational expected population size \(M\), and rational \(w_t>0\) and \(0<r_t<1\). Draw the number of type-\(t\) workers as an independent Poisson random variable of mean \(M\mu_t\); each worker survives independently with probability \(r_t\). A coalition is specified by recruitment intensities \(x_t\in[0,M\mu_t]\). Its value \(V(x)\) is the expected quality of its best surviving worker, with value zero if nobody survives. Ordering types by decreasing quality gives
\(V(x)=\sum_{k=1}^{\tau} w_k(1-\exp(-r_kx_k))\exp(-\sum_{j<k}r_jx_j)\).
Thus mass \(x_t\) means expected headcount of type \(t\), while \(\mu_t\) records that type’s population share.
This Poisson population gives a precise bridge to the paper’s finite game: conditional on the realized counts, it is exactly a reliability extension of a Max-Game. Poisson thinning preserves the paper’s individual survival probabilities. The continuous questions ask for type-level totals of the ordinary indices over this random population.
My lead is Poisson-Max Shapley by Type, anchored in Theorem 3, proved here. Theorem 3 says that the Shapley value can be computed in polynomial time for any reliability extension of a Max-Game. The continuous problem’s instance is \((M,\mu,(w_t,r_t)_{t=1}^{\tau})\); its requested solution is the vector of expected Shapley totals by type, \(\Phi_t=M\mu_t\int_0^1 \frac{\partial V(uM\mu)}{\partial x_t}\,du\). Randomly ordering the Poisson population gives this arrival-path formula: at position \(u\), the predecessor population has intensity \(uM\mu\). The outputs are the expected sums of the paper’s individual Shapley values, grouped by type. I expect this problem to be tractable: substituting the displayed \(V\) makes the integrand a polynomial-size sum of exponentials, whose integral has a polynomial-size exact expression.
A second, independently grounded problem is Poisson-Max Banzhaf by Type, anchored in Theorem 2, proved here. Theorem 2 says that the Banzhaf index can be computed in polynomial time for any reliability extension of a Max-Game. On the same input, return the expected sum of Banzhaf indices for each type: \(\Beta_t=M\mu_t\,\frac{\partial V(x)}{\partial x_t}\big|_{x=M\mu/2}\). Selecting each other worker independently with probability \(1/2\) thins the Poisson population to intensity \(M\mu/2\), yielding this marginal-contribution expression. As with Theorem 2, these are power-index totals; they need not sum to the grand-coalition value. I also expect this problem to be tractable by direct evaluation of the derivative.
The authors have a good reason to recognize these questions: they study redundant workforces, agent skill levels, independent failures, and fair division of the resulting value; their motivating settings include crowdsourcing. The mirror preserves the maximum-quality objective and failure model, while aggregating agents into types. The population-size distribution is an explicit co-modification that lets mass represent expected headcount. A type-level output is natural for a large standardized workforce, where a principal needs to set rewards by class.
The scope is just Theorems 2 and 3: computing Banzhaf and Shapley indices. I would not claim that this mirrors the paper’s core or sabotage results. The supplied paper has no named NP-hardness result to anchor; these are its two named polynomial-time computation results, so this case supports a continuous tractability story rather than a claim that discrete hardness dissolves.
My weakest point is the Poissonized population. The paper fixes a finite number of agents, whereas this mirror uses random counts with prescribed type intensities. Conditional on those counts, the underlying game is exactly theirs, and the requested outputs are expected totals of their indices. Still, a referee who requires a deterministic population size could ask for a separate limit or error analysis connecting fixed type quotas to this Poisson model. That is the main remaining bridge to establish.
The strongest negative argument is that both indices are built from atomic agents. Theorem 2 and Theorem 3 are genuine named computational results, and types defined by \((w,r)\) are sensible for large crowdsourcing pools. So neither the absence of an algorithmic result nor the absence of plausible multiplicity is grounds for rejecting these anchors.
In an atomless society, though, a coalition containing any positive mass of a type with \(r_t>0\) has surviving mass of that type almost surely. Its value is therefore just the highest \(w_t\) among types present, regardless of their masses or reliability rates. Banzhaf’s random half-coalition contains positive mass of every such type, and adding one infinitesimal agent changes nothing. The Poisson version preserves finite-agent effects at finite \(M\), but its aggregate Banzhaf total tends to zero as \(M\) grows: the probability that a sampled coalition lacks the relevant higher-weight types falls exponentially. Scaling the inclusion probability as \(1/M\) could avoid that collapse, but it would define a different power index.
The Shapley anchor is harder to defeat. The direct atomless value is flat along the path \(u\mu\) for every \(u>0\), so its ordinary path derivative is zero; the change in value is concentrated at the empty coalition. Yet the proponent’s type-level total has a nonzero high-multiplicity limit in plausible cases:
\[
\Phi_t(M)=\mu_t\int_0^M \frac{\partial V(z\mu)}{\partial x_t}\,dz.
\]
This captures the early arrivals in a random ordering, when only order-one agents have appeared. A fixed-size replication limit can give the same sort of class allocation. It is a coherent, author-recognizable candidate mirror; calling it “only a limit of discrete games” would be an invalid objection under the programme’s stated bridge.
My negative case therefore weakens the Banzhaf anchor, but it does not honestly dispose of the Shapley replication-limit version. Its vulnerability is that the atomless coalition game alone does not specify the allocation: a finite-agent ordering, or an equivalent boundary-layer rule, supplies essential semantics. If the authors accept the induced high-multiplicity limit, the Shapley mirror survives and the paper should be green under the stated standard. The case against a worthwhile mirror is weak.
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.