| paper | d4-conf-ijcai-2015-0646 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 3.1 is a named computational result, but its Banzhaf value averages marginal contributions over uniformly random coalitions. The proposed LP computes a one-sided derivative at the single mean coalition; even a one-type market with unit-valued slots shows these quantities can differ in the high-multiplicity limit. A fluctuation-aware limit could be a worthwhile question, but it is not the concrete mirror stated here.
fails bit b-changes — the continuum limit changes the question
The attempted candidate targets only Theorem 3.1's Banzhaf hardness; it does not cover Theorem 3.2 or the paper's algorithmic results.
My lead is a continuous analogue of Banzhaf computation, anchored on Theorem 3.1, proved in this paper. It states that computing the Banzhaf value in allocation games is #P-hard under Turing reductions, even when every good has the same value. The reduction makes that value encode how many subsets of agents can or cannot match all the goods. That is a strong anchor for continuization: the hardness is explicitly about counting discrete coalitions, which is the part a mass model could remove.
Consider a large placement market with many applicants and standardized indivisible slots. An applicant’s type \(t\) is their complete set of acceptable slots; slots are grouped into classes \(h\) with common value \(v_h\), supply \(\sigma_h\) per applicant, and a specified set of compatible types. The population has type masses \(\mu_t\), with \(\sum_t\mu_t=1\). A plausible regime is a very large annual cohort with millions of applicants but only dozens or hundreds of distinct eligibility and acceptability profiles. The slots scale with the cohort. Thus \(\sigma_h\) is a per-capita supply, not an outcome made divisible: each actual applicant still receives at most one whole slot.
For coalition masses \(x_t\), let \(W(x)\) be the maximum total value obtainable by assigning them slots from the full market inventory. In aggregate form, this is the matching LP maximizing \(\sum_{t,h} v_h y_{th}\), subject to \(\sum_h y_{th}\le x_t\), \(\sum_t y_{th}\le\sigma_h\), \(y_{th}\ge0\), and \(y_{th}=0\) for incompatible pairs. Fractional \(y_{th}\) records how much mass of a type receives a slot class; it does not give any individual a fractional slot. On integer replicas of the market, the bipartite matching formulation is integral.
The continuous problem is Mass-Banzhaf for Allocation Games. Given rational type masses, per-capita slot supplies, values and compatibilities, compute, for each type \(t\), its infinitesimal marginal contribution at a uniformly random coalition of the other agents:
\[ B_t(\mu,\sigma) = \lim_{\epsilon\downarrow0} \frac{W(\mu/2+\epsilon e_t)-W(\mu/2)}{\epsilon}. \]
The solution is the vector of these rational per-type values. This is the mass counterpart of normalized Banzhaf value: a uniformly chosen subset contains about half of each type, and the added agent has vanishing population mass. The mirror therefore asks whether the paper’s #P-hard coalition-counting problem becomes tractable when the coalition is represented by its type masses.
Here the continuous question appears tractable. The matching LP’s dual gives \(W(x)\) as a minimum over feasible prices \((\alpha,\beta)\) of \(\sum_t x_t\alpha_t+\sum_h\sigma_h\beta_h\). At \(x=\mu/2\), \(B_t\) is the minimum \(\alpha_t\) over the optimal dual solutions. Computing the optimum and then minimizing that coordinate over its optimal face takes polynomially many rational LP operations. The predicted class is A, tractable. It would be a substantive positive result: the finite theorem’s hardness comes from counting subsets, while the mass question asks for one marginal price in an aggregate matching problem.
The authors should recognize this as their problem in a continuous regime. The coalition’s worth is still the maximum value of an allocation, and the output still measures an agent’s contribution to that worth. What changes is the granularity: the representative agent is infinitesimal, and the half-coalition is a mass vector. This covers the Banzhaf hardness result, not the paper’s Shapley theorem or its bounded-treewidth algorithms. It also raises natural follow-ups: prove convergence from finite replica Banzhaf values, characterize what happens at nondifferentiable points of \(W\), and ask whether the continuous problem remains polynomial when the allocation model adds type-dependent values or costs.
The weakest point is the bridge at those nondifferentiable points. The directional derivative is a precise continuum definition, but finite random coalitions can fluctuate around a kink, so their expected marginal value need not converge to this one-sided derivative without a tie or regularity analysis. That limits the claim that this is the unique high-multiplicity limit. It does not make the mass question artificial: it remains a well-defined allocation-game value, and away from kinks it has the direct replica interpretation.
Theorem 3.1 is the strongest anchor, but the proposed LP does not compute the high-multiplicity limit of the Banzhaf value at every society. Its reduction counts whether a randomly chosen coalition can match all goods; the hardness comes from subsets of agents with arbitrary neighborhoods. Those agents can all have distinct complete types, so the reduction itself does not exhibit the moderate-support regime that would make the population continuous.
More seriously, replacing a random coalition by its mean mass can give the wrong answer. Take one type of unit-valued agents, all compatible with the same goods, with supply \(n/2\) for even \(n\). The continuous worth is \(W(x)=\min\{x,1/2\}\). The proposed right derivative at the half-population coalition is zero. But a uniformly random coalition of the other \(n-1\) agents has a \(\operatorname{Binomial}(n-1,1/2)\) size. The focal agent’s marginal contribution is one exactly when that coalition has fewer than \(n/2\) members, which happens with probability \(1/2\). Thus the normalized Banzhaf value is \(1/2\), not zero, even as \(n\) grows. This is a basic capacity kink, not an exotic allocation scenario. At such points, fluctuations of coalition mass vanish while their effect on the marginal contribution does not.
There are two plausible repairs, and each weakens the claimed result. Keep the derivative and the output is LP sensitivity for a stipulated mass coalition, not the Banzhaf value the theorem computes. Or preserve Banzhaf by averaging marginal contributions over the limiting fluctuations around half mass. That is a different, fluctuation-sensitive problem; its answer is not generally obtained by one LP and can depend on how those fluctuations meet the allocation value’s piecewise-linear regions. This repair may itself be worth studying, but the paper’s hardness result does not show that its computation becomes tractable.
So the case against this anchor is that the offered mirror trades away the defining random-coalition statistic, while the more faithful limit loses the simple LP argument. I cannot honestly make the universal negative airtight: repeated-profile placement markets are plausible, and a rigorously defined fluctuation limit could be a worthwhile continuous computational question. Theorem 3.1 is therefore not defeated as a possible mirror; the proponent’s specific tractability claim is what the evidence fails to establish.
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.