| paper | d4-conf-ijcai-2020-0254 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: \(\rho=29/32\); fractional coalition membership does not change the worst-case approximation ratio. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given \(m\) candidates, a finite-support society of approval types \(S\subseteq C\) with rational masses \(\mu_S\), and a fractional coalition \(z_S\in[0,\mu_S]\) of mass \(q=\sum_S z_S\), where \(q\ge \ell/m\) and the coalition unanimously agrees on the placement of at least \(\ell\) candidates, what is PRR's exact worst-case ratio of expected average satisfaction to \(\ell\)? In particular, does this ratio equal \(29/32\) over all such societies and coalitions?
Use approval types \(S\subseteq C\) with masses \(\mu_S\), and include each candidate \(c\) independently with probability \(p_c=\sum_{S:c\in S}\mu_S\). For a coalition \(z\), measure expected average satisfaction as \(\mathbb{E}_{W\sim\mathrm{PRR}}[q^{-1}\sum_S z_S\sum_{c\in C}\mathbf{1}\{\mathbf{1}[c\in S]=\mathbf{1}[c\in W]\}]\); the proposed sharp bound is \(29/32\) times \(\ell\).
Every rational mass society can be scaled to a finite profile, and PRR depends only on aggregate approval shares, so this mirror adds no distinct complexity boundary; the proponent acknowledges the lack of a complexity landscape but does not address that exact equivalence.
fatal: False
The mirror covers Theorem 5's PRR guarantee and Theorem 6's tightness witness; it leaves Theorems 1–4, the deterministic-rule comparisons, and the JR/PJR/EJR results aside.
The cleanest positive mirror is the paper’s variable-winner ballot-measure setting. Imagine a large electorate voting on \(m\) yes/no measures, with millions of voters but only \(\tau\) distinct approval patterns. A type is one complete pattern \(S\subseteq C\); its mass \(\mu_S\) is the fraction of voters with that pattern. The winning committee remains a subset \(W\subseteq C\), with no fixed size. Thus the population is continuous while the ballot outcomes remain exactly as in the paper.
For a coalition, let \(z_S\in[0,\mu_S]\) be the mass taken from each type and \(q=\sum_S z_S\). It is \(\ell\)-large when \(q\ge \ell/m\), and \(\ell\)-cohesive when there are at least \(\ell\) candidates on whose placement all its mass agrees. Its average satisfaction under a lottery \(\Pi\) over committees is
\[ \mathbb E_{W\sim\Pi}\left[ \frac{1}{q}\sum_S z_S\sum_{c\in C} \mathbf{1}\!\left\{\mathbf{1}[c\in S]=\mathbf{1}[c\in W]\right\} \right]. \]
Allowing fractional \(z_S\) is the natural high-multiplicity version of selecting a coalition from a type: members of a type are indistinguishable for the preferences and utility this problem uses.
My lead anchor is Theorem 5, proved in this paper: the Proportional Random Rule (PRR), which independently includes candidate \(c\) with probability equal to the fraction of voters who approve \(c\), guarantees expected \(29/32\)-AS for every \(m\). Its continuous mirror is: given \(m\) and a finite support of approval types with binary-rational masses summing to one, produce a lottery over committees such that every \(\ell\)-large, \(\ell\)-cohesive fractional coalition has expected average satisfaction at least \((29/32)\ell\). The continuous PRR sets
\[ p_c=\sum_{S:\,c\in S}\mu_S \]
and includes each \(c\) independently with probability \(p_c\). The lottery has a compact description using \(m\) probabilities, computable with \(O(m\tau)\) rational additions. The paper’s proof carries over by replacing voter counts with masses; its inequalities also allow fractional coalition selections. I expect this mirror in Class A: there is an explicit, efficient rule and a proportionality guarantee, rather than a hard optimization problem to solve.
A second, closely related anchor is Theorem 6, also proved here: PRR cannot guarantee \((29/32+\varepsilon)\)-AS for any \(\varepsilon>0\). The continuous question is to determine PRR’s sharp universal factor—the infimum of expected coalition satisfaction divided by \(\ell\), over all \(m\), societies, and eligible coalitions. The answer is exactly \(29/32\). The paper’s witness becomes a three-type society with \(m=3\): masses \(5/12\), \(3/12\), and \(4/12\) have approval sets \(C\), \(\{c_1,c_2\}\), and \(\varnothing\), respectively. The first two types form a coalition of mass \(2/3\), which is \(2\)-large and \(2\)-cohesive. PRR gives expected average satisfaction \(29/16=(29/32)\cdot 2\) for it. This is a sharpness result for this rule, not a bound on every randomized rule. The continuous result follows from the same proof and the same rational-mass witness.
The match to the authors’ problem is strong: it keeps their ballot interpretation, variable committee size, agreement-based utility, coalition definitions, and PRR rule. It does not rely on calling the random committee outcome a continuous population. The proposed mirror changes the electorate into a distribution over complete ballot types.
The scope is deliberately narrow: these mirrors cover PRR’s guarantee and its tightness, not the paper’s full comparison of PAV, seq-Phragmén, Rule X, and representation axioms. They also do not establish the kind of complexity classification ChoCo chiefly seeks. The paper has no named result showing an optimization problem is in P, NP-hard, FPT, or similar; its closest computational anchors are approximation guarantees for a rule. That is the weakest point: PRR itself is simple to compute, and the paper’s substantive results concern proportionality, not a new computational-complexity landscape. A natural further question is whether any randomized rule can beat \(29/32\) on continuous societies, and whether an optimal such rule can be computed efficiently.
The strongest objection is that neither anchor is a computational result of the kind ChoCo is set up to chart. Theorem 5 proves a proportionality guarantee for a specified randomized rule; Theorem 6 proves that this rule’s guarantee is tight. Neither studies the complexity of finding a winner, changing an election, or optimizing an intervention. PRR itself requires only summing approval shares and sampling independent outcomes. With support size \(\tau\), its marginals take \(O(m\tau)\) rational additions to compute. There is no pricing problem, difficult search, or complexity boundary for continuization to expose.
That objection survives the better version of Theorem 5’s mirror. A society of ballot types with rational masses is a natural high-multiplicity electorate, and the theorem’s proof appears to extend to fractional coalitions. But the resulting question is whether the same rule satisfies the same guarantee on that representation. Every such rational society can also be written as a finite profile by scaling the masses to voter counts. The extension may be a clean formal dictionary, but for this theorem it does not create a new computational task: the rule and its guarantee already depend on aggregate approval shares.
Theorem 6 has the same problem. Its three-type witness is already an ordinary finite profile, and the continuous version preserves it exactly. The result says something sharp about PRR’s proportionality, but it supplies no lower bound on an algorithm or computational problem.
A stronger proposal would optimize over all lotteries, seeking the best worst-case satisfaction guarantee for each society or over all societies. That is a coherent research question, and it is close to the paper’s open question about whether a randomized rule can beat \(29/32\). But it changes the object from analyzing PRR to designing proportionality guarantees. In this programme, that is an axiomatic rule-design question, not a computational mirror of one of the paper’s results. If ChoCo chose to include computational optimization of randomized rules, this could be worth pursuing; it does not rescue these anchors under the stated scope.
There is no convincing objection to the population model itself: large electorates over a small support of approval patterns are plausible, and mass is meaningful here. The negative case is therefore limited to scope and computational substance. The proposed mirrors are mathematically sensible, but their contribution would be a restatement of a rule guarantee and its tight example over mass inputs, not a new complexity landscape.
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.