| paper | d4-conf-atal-2022-0231 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5.10
Given integers \(t,w\) with \(\lceil(t+1)/2\rceil\leq w\leq t\), optimize over societies \(\mu\in\Delta(\{0,1\}^t)\). Let \(M_j(\mu)=\max\{\mu(v_j=0),\mu(v_j=1)\}\), and let \(A_\mu(p)\) be the topics on which proposal \(p\) agrees with the topic-wise majority. Subject to every \(p\) with \(|A_\mu(p)|\geq w\) having \(\mu(\{v:d_H(v,p)\leq\lfloor t/2\rfloor\})<1/2\), determine the supremum of \(\frac{1}{t}\sum_{j=1}^t M_j(\mu)\) and provide an \(\varepsilon\)-optimal society for any \(\varepsilon>0\).
Use topic-wise majority values to orient the coordinates, then symmetrize over topic permutations. Let \(x_\ell\) be the mass on types with exactly \(\ell\) majority-aligned coordinates, distributed uniformly among those types. The resulting LP maximizes \(\frac{1}{t}\sum_{\ell=0}^t\ell x_\ell\), subject to \(\sum_{\ell=0}^t x_\ell=1\) and \(\sum_{\ell=0}^t s_{k,\ell}x_\ell<\frac{1}{2}\binom{t}{k}\) for each \(k=w,\ldots,t\), where \(s_{k,\ell}\) is the number of \(k\)-proposals supported by an \(\ell\)-type.
The mirror covers Theorem 5.10 and the LP-based numerical bounds in Section 5.2; it does not claim to cover the other results, including Theorem 5.5.
The strongest positive case is the extremal computation in Section 5.2, where the object being optimized is already the electorate’s normalized distribution over opinion types.
My anchor is Theorem 5.10, proved in this paper. It says that \(m a_t(w)\)—the maximum average topic majority among voter matrices \(V\) with \(m d_V<w\)—is given by the optimum of the paper’s LP. In that LP, \(v'_\ell\) is the fraction of \(\ell\)-voters and \(s_{k,\ell}\) is the number of \(k\)-proposals supported by one \(\ell\)-voter. It maximizes \(\frac{1}{t}\sum_{\ell=0}^t \ell v'_\ell\), subject to \(\sum_{\ell=0}^t s_{k,\ell}v'_\ell < \frac{1}{2}\binom{t}{k}\) for every \(k=w,\ldots,t\), and \(\sum_{\ell=0}^t v'_\ell=1\). The paper computes this LP to obtain numerical bounds.
Here is the continuous question I would hand to a prover: Continuous Majority-Threshold Extremum. An instance is integers \(t\) and \(w\), with \(\lceil(t+1)/2\rceil\leq w\leq t\). A type is a complete binary opinion vector \(v\in\{0,1\}^t\), and a society is a distribution \(\mu\) over those types. For a proposal \(p\in\{0,1\}^t\), let \(S_\mu(p)=\mu\{v:d_H(v,p)\leq\lfloor t/2\rfloor\}\), its supporting mass. Relabel each topic so that \(1\) is a majority opinion. Among societies for which every proposal with at least \(w\) majority decisions has \(S_\mu(p)<1/2\), compute the supremum of the average topic majority, \(\frac{1}{t}\sum_{j=1}^t\max\{\mu(v_j=1),\mu(v_j=0)\}\). A solution is that value and, for any requested \(\varepsilon>0\), an \(\varepsilon\)-optimal society. Using a supremum accommodates cases where the best value is approached at the strict support boundary.
The connection to Theorem 5.10 is direct. A discrete electorate maps to \(\mu_v=n_v/n\); conversely, rational masses can be realized by replicating voters. The theorem’s symmetry argument compresses the continuous variables: let \(x_\ell\) be the mass of types with exactly \(\ell\) ones, spread uniformly across those types. The resulting LP has \(t+1\) variables and constraints indexed by \(k=w,\ldots,t\), and its objective is \(\frac{1}{t}\sum_\ell \ell x_\ell\). This is the paper’s computation interpreted as an optimization over voter-type mass. The paper has therefore established the discrete-to-continuous identity underlying this mirror.
The regime is a large association, party membership, or other population deliberating over a fixed or modest agenda of independent binary issues. Each person’s complete ballot is their type; mass means their share of the membership. With \(t\) fixed or modest, there are at most \(2^t\) types, so a very large electorate can have many agents per type. This fits the paper’s approval-ballot and party-platform settings, and keeps the outcome itself binary.
I expect this mirror to be Class A: the symmetry-reduced formulation has polynomially many variables and constraints in \(t\), with binomial coefficients of polynomial bit length. The further question it raises is whether the same compression yields exact worst-case representativeness ratios for general \(t\), rather than just the bounds the paper derives from \(m a_t(w)\). This case covers Theorem 5.10 and the LP-based bounds that use it; it does not claim to mirror every result in the paper.
The weakest point is also the source of the mirror’s credibility: the paper already performs almost exactly this continuous computation using normalized voter fractions. This is a strong, explicit discrete-to-continuous result, but it leaves little new computational landscape for this particular problem. The paper provides no hardness anchor, so the positive case is about a well-founded continuous formulation and its tractability, rather than discrete hardness dissolving in a continuum.
The strongest negative case is that the proposed threshold mirror is already computed in the paper’s own mass variables. Theorem 5.10 reduces the extremum to an LP with \(t+1\) variables; its \(v'_\ell\) are the masses of voter types with \(\ell\) yes-opinions. Symmetry handles the full \(2^t\)-type space, and the paper uses this LP to obtain its numerical bounds. So asking for that extremum over a continuous society adds little computational work.
That does not defeat the anchor under ChoCo’s rules: the paper’s reduction from finite electorates to an LP over masses is itself a discrete-to-continuous identity, and such an identity is a legitimate result. Nor does it rule out a stronger mirror. For a large association with a fixed or modest agenda, one could give the society as ballot-type masses and ask for the most representative proposal with at least half the mass supporting it. Theorem 5.10 optimizes over societies; it does not solve that given-society problem. The number of topics may drive its complexity, but agenda-driven hardness is still a useful result for the programme.
The exact worst-case representativeness ratio is closer to the paper’s existing analysis: it already ranges over voter matrices of arbitrary size and gives bounds via the mass LP. For fixed \(t\), the society is a point in a finite-dimensional simplex, and rational electorates approximate mass distributions; after handling boundary and tie conventions, this leaves little room for a distinct extremal question. That is an argument for low marginal value, not for no worthwhile mirror.
So I cannot honestly defeat the anchor or support the universal negative. The paper has already done much of the natural extremal continuization, but a computational question about a given high-multiplicity society remains plausible.
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.