| paper | d4-conf-ijcai-2019-1035 |
| 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: \(O\!\left(L^4+(m+d)L^3(d+1)^2+\tau^2\right)\) bit operations suffice, and hence \(O(L^6)\) suffices under the stated encoding. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite set of types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and an explicitly represented rational polynomial \(F\) on a neighborhood of \([0,\mu]\), with \(\partial_t F(\mu/2)\ne 0\) for every \(t\), return the total preorder \(t\succeq u\) iff \(\operatorname{sgn}(\partial_t F(\mu/2))\ge \operatorname{sgn}(\partial_u F(\mu/2))\). This asks for the limiting ordinal Banzhaf ranking when each finite-population context includes each other member independently with probability \(1/2\), and coalition power is given by \(F\) of its type-mass vector.
Types are roles with population masses \(\mu\); a coalition is represented by its type-mass vector and has power \(F\) at that vector. The output is a ranking of types by the signs of the derivatives at \(\mu/2\); there is no optimization objective.
The mirror needs a smooth polynomial representation of coalition power, which narrows the paper's arbitrary ordinal orders; the proponent acknowledges that restriction but does not explain why this encoding is canonical.
fatal: False
The mirror covers the ordinal Banzhaf ranking represented in Theorem 3; it leaves Theorem 1's axioms, Theorem 2's CP-majority characterization, and other weighted-majority rules aside.
The honest positive case has a limit: the paper contains no named computational-complexity result to anchor one. Theorem 1, proved here, characterizes the ordinal Banzhaf solution on linear orders by coalitional anonymity, neutrality, and monotonicity. Theorem 2, cited from Haret et al. (2018), characterizes CP-majority for two ranked elements by equality of coalitions, neutrality, and positive responsiveness. Neither is a complexity result.
The nearest computationally relevant result is Theorem 3, proved here. It says that on a linear order over \(2^N\), the ordinal Banzhaf ranking equals the weighted-majority ranking that compares \(i\) and \(j\) across contexts \(S\in U_{ij}\), using the Banzhaf-distance weight \(\hat w^S_{ij}\). That weight counts how many of \(S\) and \(S\cup\{i,j\}\) lie between \(S\cup\{i\}\) and \(S\cup\{j\}\); the weighted comparison has the same sign as the difference between their ordinal Banzhaf scores. This is a representation result, not a claim that the ranking problem is in P or hard. I would not present it as a qualifying anchor under your rule.
A plausible continuous research question nevertheless grows from that result. Imagine a very large membership organization whose members fall into a fixed number \(\tau\) of roles, with members of each role indistinguishable for coalition power. A type is a role, and \(\mu_t\) is its fraction of the membership. A coalition is represented by its vector of type masses, and a function \(F\) gives the coalition’s strength from that vector. This is a genuine high-multiplicity regime: \(n\) members but only \(\tau\) types, with \(n\gg\tau\). The output, as in the paper, is a ranking; there is no optimization objective.
Here is a precise candidate, Limit Ordinal-Banzhaf Type Ranking. Input a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), and an explicitly represented rational polynomial \(F\) on a neighborhood of \([0,\mu]\). Assume \(\partial_tF(\mu/2)\ne0\) for every \(t\in T\). Return the total preorder on types defined by
\[
t\succeq_F u
\quad\Longleftrightarrow\quad
\operatorname{sgn}\!\left(\partial_tF(\mu/2)\right)
\ge
\operatorname{sgn}\!\left(\partial_uF(\mu/2)\right).
\]
The solution is the ranking of types by their limiting ordinal Banzhaf scores.
The link to the paper is direct but restricted. In a finite population with \(n_t=n\mu_t\) members of each type, draw a Banzhaf context by choosing each other member independently with probability \(1/2\). The selected coalition’s type-mass vector concentrates at \(\mu/2\). If its power is induced by \(F\), a member of type \(t\)’s ordinal marginal contribution is eventually the sign of \(\partial_tF(\mu/2)\), so the normalized Banzhaf score converges to that sign. For the stated explicit polynomial input, computing the ranking is tractable by evaluating the derivatives. This is a prospective Class A question, but it has no discrete hardness anchor in this paper, so no hardness-transfer claim follows.
Authors could plausibly recognize this as a high-multiplicity limit of their central question: ranking individuals by ordinal marginal contributions to coalitions. The mirror covers only that Banzhaf side, closest to Theorem 3; it does not mirror CP-majority or the axiomatic characterizations.
The weak point is substantial. Replacing an arbitrary order over all subsets by a smooth function of type masses sharply restricts the paper’s input, and the limit can collapse the ranking to just two tiers. Critical cases with \(\partial_tF(\mu/2)=0\) may need finer asymptotics, and those could recover distinctions that the limit erases. So this is a coherent continuous research question, but not evidence that this paper establishes a continuous computational-complexity landscape.
The strongest case against a mirror starts with a mismatch: this paper proves no computational complexity result. Theorem 1 is an axiomatic characterization, Theorem 2 is a prior axiomatic characterization, and Theorem 3 is an identity between two ways of computing the same ranking. None gives a running time, hardness result, or algorithm for a specified input encoding. The input is an order over all subsets of \(N\); when that order is listed explicitly, the ordinal Banzhaf scores can be counted directly in time polynomial in the list’s length. The paper therefore offers no computational landscape for ChoCo to continuize.
The proposed Limit Ordinal-Banzhaf Type Ranking is the most plausible bridge, and a large organization with many members in a few roles is a credible high-multiplicity setting. The problem is what the bridge carries across. With a smooth \(F\), the random coalition’s type-mass vector concentrates at \(\mu/2\). If every \(\partial_t F(\mu/2)\) is nonzero, a member’s normalized ordinal Banzhaf score tends to the sign of that derivative. The output has at most two tiers, and for an explicitly represented rational polynomial those signs are directly computable. That is a sensible limit observation, but it does not open a complexity question: its tractability comes from replacing the paper’s arbitrary ordinal power relation with a compact, smoothly evaluable function.
There is a better version of the mirror: retain only ordinal comparisons, and ask how the ranking behaves for coalitions described by type masses. But that version needs a representation of the power relation over a continuum of coalitions. The paper supplies none. With an explicit table of type-count profiles, the scores are again direct counts, polynomial in the table’s length. With a compact representation, the complexity depends on the added representation and its structure. The resulting problem may be worth studying, but its computational difficulty would come from new assumptions absent from the paper.
The continuum also gives Banzhaf’s uniform choice of a finite coalition a sharply concentrated limit. A faithful smooth version therefore samples essentially one coalition-mass profile, rather than averaging over a rich range of contexts. One can choose a different distribution over contexts or a different infinitesimal marginal convention, but those choices define new indices. At derivative ties, further asymptotics may distinguish types, yet those refinements depend on how the finite populations approach the limit; they do not supply a canonical complexity problem from this paper.
So the proponent’s role-based scenario survives as a plausible application, and their limit formula survives as a coherent mathematical question. What does not survive is the claim that it is a worthwhile continuous computational mirror of this paper. That conclusion is strong for ChoCo’s stated remit; the broader claim that no useful continuous variant could ever be developed is less secure. The weakness lies there: a future paper could specify a compelling succinct model of ordinal power over type-mass coalitions and study its complexity, but that would be a new computational problem, not a continuization of a result established here.
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.