| paper | d4-journals-ai-2020-0098 |
| 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: For each supplied family, the exact guarantees are \(\Gamma_g=\min_{W,V\in\mathcal K}\lambda_g(W,V)\), with \(\lambda_g\) given by the rational linear programs above. Both guarantees are rational and attained, and the ratio-threshold answer is yes exactly when \(q\geq\Gamma_g\). The sharp unrestricted representation guarantee is \(k/(2k-1)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a candidate set \(C\), committee size \(k\), finite support \(\mathcal T\subseteq 2^C\), welfare choice \(g\in\{u,r\}\), and rational threshold \(q\), does there exist a rational distribution \(\mu\) supported on \(\mathcal T\) and a size-\(k\) PAV-winning committee \(W\) such that \(g_\mu(W)/\max_{|W'|=k}g_\mu(W')\le q\), where \(u_\mu(W)=\sum_{A\in\mathcal T}\mu_A|A\cap W|\) and \(r_\mu(W)=\sum_{A\in\mathcal T}\mu_A\mathbf 1[A\cap W\ne\varnothing]\), with the denominator positive?
Approval sets \(A\subseteq C\) are voter types with binary-rational masses \(\mu_A\) summing to \(1\). PAV chooses a size-\(k\) committee maximizing \(\sum_A\mu_A H(|A\cap W|)\); the witness objective is its utilitarian or representation welfare ratio against the best size-\(k\) committee.
The mirror covers Theorem 2’s PAV utilitarian and representation guarantees; it leaves the other rules’ guarantees, experiments, and axiomatic results aside.
There is no numbered complexity result in the supplied paper to anchor a mirror to. Theorems 1–9 give welfare guarantees; the numbered propositions concern guarantees, proportionality, or Pareto efficiency. The NP-hardness claims for PAV, Monroe, CC, and leximin-Phragmén appear in prose with citations, not as a numbered result. So none qualifies under the requested anchor rule.
The closest foothold for a positive case is Theorem 2, proved in this paper. It states that PAV’s utilitarian guarantee lies between \(1/(2+\sqrt{k})\) and \(2/\sqrt{k}\), and its representation guarantee lies between \(1/2\) and \(1/2+1/(4k-2)\). This is a worst-case approximation result, not a complexity classification, so it cannot serve as a compliant anchor. Still, it gives a natural continuous analogue of the paper’s welfare analysis.
Call the candidate set \(C\), and let each voter type be an approval set \(A\subseteq C\). A society is a binary-rational distribution \(\mu\) over a finite support \(\mathcal T\subseteq 2^C\). For a size-\(k\) committee \(W\), define utilitarian welfare as \(u_\mu(W)=\sum_A\mu_A|A\cap W|\), and representation as \(r_\mu(W)=\sum_A\mu_A\mathbf 1[A\cap W\ne\varnothing]\). PAV selects committees maximizing \(\sum_A\mu_A H(|A\cap W|)\).
A precise question suggested by Theorem 2 is PAV-Welfare-Witness\(_\infty\): given \(C,k,\mathcal T\), a threshold \(q\), and a choice of utilitarian or representation welfare, is there a rational distribution \(\mu\) supported on \(\mathcal T\) and a PAV-winning committee \(W\) whose welfare ratio against the optimum size-\(k\) committee is at most \(q\)? A yes-solution is \(\mu\) and \(W\); the unrestricted-support version searches over all approval types. Its regime could be a large city choosing \(k\) hospital sites: many residents, relatively few recurring approval patterns, and a discrete committee of sites. The type captures every preference detail this analysis uses; mass is the fraction of residents of that type.
This is a credible population mirror of the paper’s PAV welfare question. Multiplying all masses by a common denominator recovers an ordinary finite profile, and normalizing any finite profile gives rational masses; the welfare ratios are unchanged. Thus the unrestricted continuous guarantee should inherit the paper’s bounds exactly. The continuous question is well posed, and the high-multiplicity setting is natural. But this scale-invariance also exposes the weakness: the transfer is immediate, and Theorem 2 supplies no complexity classification for the witness problem. I would expect the *guarantee values* to transfer from the discrete setting; the complexity of computing or certifying them as a function of \(m,\tau,L\) remains a separate question. Further questions include how the worst-case guarantee changes when support size \(\tau\) is bounded, and whether small-support societies already witness the paper’s bounds. The mirror covers PAV’s worst-case guarantees, not the paper’s experiments, axiomatic results, or every rule it studies.
There is no eligible computational result to anchor a mirror to. Theorem 2 bounds PAV’s utilitarian and representation guarantees; it says nothing about the complexity of computing a winner or an intervention. The paper makes that distinction itself: it analyzes how existing rules perform and explicitly says it is not seeking approximation algorithms. Its other numbered results are also guarantee or axiom results. The proponent acknowledges this, so the proposed anchor does not meet the stated requirement.
The PAV-Welfare-Witness\(_\infty\) question does not repair that gap. It turns the paper’s worst-case guarantee into a threshold search over bad profiles. For rational masses, multiplying by a common denominator gives a high-multiplicity profile; PAV winners stay the same, and AV and CC scores scale together, leaving both ratios unchanged. That is a sensible representation of a large population, but it makes the proposed question a computational study of the guarantee’s witnesses—something the paper does not undertake—rather than a continuous version of a computational result in the paper. Restricting the support size could make a new research question, but it would add a parameter to this extremal search; it would not supply the missing anchor.
The strongest alternative is to ask for PAV winner determination on a rational distribution over approval types, perhaps parameterized by support size. A population with repeated approval patterns is plausible, and the paper cites PAV’s known NP-hardness. That could be a worthwhile high-multiplicity project in its own right. But it is imported from the paper’s background, not a numbered result this paper establishes, and it does not mirror Theorem 2.
So the negative case is strongest on scope: this paper’s contribution is quantitative evaluation of rules, not computational analysis of a problem over a society. It is weaker as a universal claim. The population model is natural, and an adjacent PAV-computation project may merit attention; the paper’s named results simply do not give a sound anchor for it.
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.