| paper | d4-conf-sagt-2020-0010 |
| 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 in \(\tau,L\). Every valid instance converges, with eventual equality \(p_t^{(N)}=w_t/\bar w\) for every sufficiently large admissible \(N\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.1
Given rational type masses \(\mu_t>0\) summing to \(1\), positive integer weights \(w_t\), and a rational quota fraction \(\theta\in(0,1)\), let \(\bar w=\sum_t\mu_t w_t\). For sufficiently large population sizes \(N\) such that \(N\mu_t\) and \(N\theta\bar w\) are integers, form the weighted voting game with \(N\mu_t\) voters of type \(t\), each of weight \(w_t\), and quota \(N\theta\bar w\). Let \(x_t^{(N)}\) be the common per-voter nucleolus payoff for type \(t\), and set \(p_t^{(N)}=N x_t^{(N)}\). Determine whether \(p^{(N)}\) converges over these admissible \(N\); if it does, compute its limit.
The society has voter types indexed by weight, with mass \(\mu_t\) for type \(t\). A coalition is represented by a mass vector \(z\) with \(0\le z_t\le\mu_t\), and its limiting worth is \(1\) when \(\sum_t w_t z_t\ge\theta\bar w\), and \(0\) otherwise. The output is the limiting per-type payoff density \(p\), defined through the finite games’ nucleoli so their coalition multiplicities are retained.
The mirror covers the weighted-voting nucleolus result, whose minimum-excess dynamic program has size \(O(nT)\). It leaves the general dynamic-programming framework, the linear-subspace avoidance hardness result, and the bounded-treewidth \(b\)-matching application aside.
The strongest population mirror is the paper’s weighted-voting application. The constituency is a large federation or membership organization with many voters but only a few voting weights: a type is a voter’s weight and any other feature the game uses, and \(\mu_t\) is that type’s share of the electorate. Identical voters are genuinely interchangeable. A coalition is described by its mass vector \(z\), and its limiting worth is \(1\) if its weighted mass reaches the quota, and \(0\) otherwise.
My anchor is Theorem 5.1, which says that the nucleolus of a weighted voting game can be computed in pseudopolynomial time. The paper derives this result using a minimum-excess dynamic program of size \(O(nT)\); it is a result proved there as an application of the framework, though the algorithmic result is credited to Pashkovich and the cited hardness result to Elkind et al. [The paper](https://arxiv.org/abs/2005.10853)
Here is the continuous question I would hand to a prover: Asymptotic Weighted-Voting Nucleolus. The input is a rational mass vector \(\mu\in\mathbb{Q}_{>0}^{\tau}\), with \(\sum_t\mu_t=1\); integer weights \(w_t>0\); and a rational quota fraction \(\theta\in(0,1)\). Write \(\bar w=\sum_t\mu_t w_t\), and take population sizes \(N\) for which every \(N\mu_t\) and \(N\theta\bar w\) is integral. At size \(N\), form the weighted voting game with \(N\mu_t\) voters of type \(t\), each of weight \(w_t\), and quota \(N\theta\bar w\). Let \(x_t^{(N)}\) be the per-voter nucleolus payoff for type \(t\), and set \(p_t^{(N)}=N x_t^{(N)}\). The problem is to determine whether \(p^{(N)}\) converges as \(N\) grows through those sizes, and, if so, compute its limit \(p\).
The continuous society in this instance has type masses \(\mu\); a coalition has mass \(z\in\prod_t[0,\mu_t]\) and wins exactly when \(\sum_t w_tz_t\geq\theta\bar w\). The output \(p_t\) is the limiting payoff density, with \(\sum_t\mu_t p_t=1\). Crucially, the target is defined by the finite games’ nucleoli: their lexicographic treatment of coalition excesses is preserved through the limit, rather than replaced with an arbitrary measure over a continuum of coalitions.
I expect Class A for fixed support size \(\tau\). The coalition mass profiles lie in a fixed-dimensional box split by a single quota threshold, which suggests that the pseudopolynomial dependence on the electorate size can give way to an algorithm in \(\tau\) and the rational input length. Further questions are whether convergence always holds, whether the limit can be computed in polynomial time for fixed \(\tau\), and whether it agrees with a directly defined type-mass nucleolus.
The weakest point is that Theorem 5.1 does not establish either convergence or a support-size algorithm. The finite lexicographic objective depends on how many coalitions realize each excess; a mass vector alone does not record those multiplicities. Defining the question by the exact finite-population limit keeps it faithful to the paper, but makes proving that the limit exists part of the problem. This mirror covers the weighted-voting result, not the paper’s full dynamic-programming framework or its bounded-treewidth \(b\)-matching application. The paper’s named hardness result, Lemma 2, concerns generic linear-subspace avoidance; its path-based hardness does not provide a comparable population mirror for weighted voting.
The weighted-voting result is the proponent’s strongest anchor. Large federations with many members in a few voting-weight classes are a plausible high-multiplicity setting; grouping members by weight does not distort the game. I can’t dismiss the mirror on grounds of identity, multiplicity, or the theorem’s being known already.
The real difficulty is that the nucleolus ranks the *multiset* of coalition excesses. For a type-count profile \(k\), that excess occurs \(\prod_t \binom{N\mu_t}{k_t}\) times. A continuous mass profile \(z\) records which compositions are possible, but not how many coalitions realize each one. There is no obvious canonical lexicographic ranking of excesses over the uncountable box of mass profiles. A measure on that box would introduce a choice: Lebesgue measure and the limit of uniformly sampled finite coalitions behave differently, and either can discount rare coalitions that still determine the finite nucleolus. A max-min formulation captures the least-core stage, but does not by itself define the later lexicographic refinements.
The proposed limit of finite nucleoli is the strongest repair: it preserves the exact multiplicities and asks for an output indexed by the limiting type masses. That is a well-posed high-multiplicity asymptotic question. My case against is that it gets its objective from an unbounded sequence of discrete games, rather than from a canonical nucleolus of the continuous society; the latter would need a new definition and a dictionary to the finite sequence. That weakens the claim that this is already a continuous computational mirror. It does not defeat the mirror outright, though: the limit question itself could be valuable ChoCo work, and the brief explicitly treats such a dictionary as a programme deliverable. I don’t see an honest objection that rules out every worthwhile version of this anchor.
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.