Paper deep dive
Improving Randomized Metric Distortion to 2.3282
Nisarg Shah
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/1/2026, 6:33:15 AM
Summary
This paper improves the upper bound on the metric distortion of randomized voting rules from 2.5 to 2.3282. The authors introduce a 'random-size stable lottery' (RSL_D), a generalization of stable k-lotteries where the number of draws is a random variable D. By mixing this new lottery type with Integrated Veto, they achieve a lower worst-case ratio between the expected social cost and the optimal cost. The proof utilizes infinite-dimensional conic linear programming duality and exact rational verification.
Entities (10)
Relation Signals (7)
Nisarg Shah → authored → Improving Randomized Metric Distortion to 2.3282
confidence 99% · Nisarg Shah Affiliation: University of Toronto... Improving Randomized Metric Distortion to 2.3282
Integrated Veto → combinedwith → Random-Size Stable Lottery
confidence 95% · By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most 11641/5000=2.3282.
Random-Size Stable Lottery → improves → Metric Distortion
confidence 95% · By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most 11641/5000=2.3282.
Charikar et al. → establishedbound → 2.753
confidence 90% · Charikar, Ramakrishnan, Wang, and Wu [JACM 2024] prove an upper bound of 2.753
Frank → establishedbound → 25%
confidence 90% · Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to 2.5
Ye → establishedbound → 25%
confidence 90% · Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to 2.5
Maximal Lottery → generalizedby → Random-Size Stable Lottery
confidence 90% · When D=1 deterministically, this reduces to the stable 1-lottery... the case k=1 is precisely a maximal lottery.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In metric social choice, each voter ranks a set of $m$ candidates by her distance to them in an unknown metric space. The cost of a candidate is its average distance to the voters. A randomized voting rule must use only the rankings to choose a lottery over candidates. Its distortion is the worst-case ratio between the expected cost under the lottery it returns and the cost of the best candidate. Charikar, Ramakrishnan, Wang, and Wu [JACM 2024] prove an upper bound of $2.753$, establishing a constant separation from deterministic rules, for which the best achievable distortion is $3$. Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to $2.5$, using an equal mixture of maximal lottery and Integrated Veto. The existing arguments do not yield a better bound with any mixture of these rules. We break this barrier with a new ingredient, a random-size stable lottery. Let $D$ be a random variable over the domain of positive integers. A random-size stable lottery $\mathrm{RSL}_D$ guarantees that the probability of a random voter preferring any fixed candidate $c$ to her favorite of $D$ i.i.d. draws from $\mathrm{RSL}_D$ is at most $\mathbb{E}[1/(D+1)]$, where the probability also averages over $D$. When $D=k$ deterministically, this reduces to the stable $k$-lottery of Charikar, Ramakrishnan, Tan, and Wang [EC 2025]; the case $k=1$ is precisely a maximal lottery. Their minimax argument for a fixed $k$ easily generalizes to a random $D$. Our main contribution is to show how stability with respect to a random $D$ can be used to bound distortion. By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most $11641/5000=2.3282$. The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification via the Bernstein basis.
Tags
Links
- Source: https://arxiv.org/abs/2608.29308v1
- Canonical: https://arxiv.org/abs/2608.29308v1
Trouble viewing inline? Open PDF directly →
Full Text
124,927 characters extracted from source content.
Expand or collapse full text
Improving Randomized Metric Distortion to 2.32822.3282 Nisarg Shah Affiliation: University of Toronto Email: nisarg@cs.toronto.edu Abstract In metric social choice, each voter ranks a set of m candidates by her distance to them in an unknown metric space. The cost of a candidate is its average distance to the voters. A randomized voting rule must use only the rankings to choose a lottery over candidates. Its distortion is the worst-case ratio between the expected cost under the lottery it returns and the cost of the best candidate. [11] prove an upper bound of 2.7532.753, establishing a constant separation from deterministic rules, for which the best achievable distortion is 33. Independently, [19] and [41] improve the bound to 2.52.5, using an equal mixture of maximal lottery, a Nash equilibrium of the zero-sum game in which a random voter compares two candidates, and Integrated Veto, an adaptation of a well-established rule, in which every voter continuously vetoes her current least-preferred candidate. The existing arguments do not yield a better bound with any mixture of these rules. We break this barrier with a new ingredient, a random-size stable lottery. Let D be a random variable over the domain of positive integers. A random-size stable lottery RSLDRSL_D guarantees that the probability of a random voter preferring any fixed candidate c to her favorite of D i.i.d. draws from RSLDRSL_D is at most [1/(D+1)] [1/(D+1)], where the probability also averages over D. When D=1D=1 deterministically, this is precisely a maximal lottery. More generally, when D=kD=k deterministically, this reduces to the stable k-lottery of [10], which they prove exists for every fixed positive integer k. Their minimax argument for a fixed k easily generalizes to a random D. Our main contribution is to show how stability with respect to a random D can be used to bound distortion. Specifically, by mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most 11641/5000=2.328211641/5000=2.3282. The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification via nonnegativity testing of polynomials using the Bernstein basis. All the proofs in this document were obtained using GPT-5.6-Sol with guidance from the author. The author verified the proofs for correctness, and significantly expanded on the exposition and simplified arguments, with the aid of GPT-5.6-Sol and Claude Opus 5. Contents 1 Introduction 1.1 Our Results 1.2 Technical Overview 1.3 Related Work 2 Preliminaries 2.1 Analysis via Candidate Sets 2.2 Integrated Veto and Maximal Lotteries 3 Random-Size Stable Lotteries 4 From Random-Size Stability to Loss Ratio 4.1 Abstracting the Profile Into an Infinite-Dimensional LP 4.2 Simplified Primal 4.3 Bounding Loss via Dual 5 A Rule with Distortion at Most 2.32822.3282 6 Discussion References A Further Properties of Random-Size Stable Lotteries A.1 Why separately chosen stable lotteries cannot simply be mixed A.2 Computing a random-size stable lottery A.3 A calculation with cumulative distributions A.4 Several draws from another lottery A.5 Approximating by a lottery with small support A.6 An extension to signed coefficients B Exact Verification and Numerical Discovery of the Distortion Bound B.1 Construction of Dual B.2 Exact Dual Families and Candidate Bounds B.3 Exact Polynomials for Dual Feasibility B.4 Polynomial Verification and Proof of B.5 Discretized Programs Used in the Search B.6 Numerical Search and Rationalization B.7 Reproducing the Computer-Assisted Checks 1 Introduction Social choice theory studies how to choose one of several alternative decisions (candidates) by aggregating the conflicting preferences of multiple parties (voters). The norm is to elicit ranked preferences from voters over the candidates because exact utilities or costs are often difficult for voters to identify and report. Consequently, much of the centuries-old literature has sought voting rules that satisfy qualitative axioms defined on this ordinal data. However, no single axiom has been convincing on its own and seeking multiple axioms together has often led to impossibility results rather than a choice of the “optimal voting rule” [4, 21, 39]. The rise of approximation algorithms in computer science has offered a new perspective: even when voters report ordinal preferences, one can aim to optimize welfare defined on the underlying numerical utilities or costs, with success measured by distortion—the approximation ratio between the achieved welfare and the optimum in the worst case over the unknown preference intensities. This has reignited the search for optimal voting rules, well-defined in this distortion framework. Specifically, in the metric social choice model [2], n voters and m candidates are points in the same underlying metric space. A voter’s distance to a candidate is her cost for that candidate, and she ranks candidates from smallest to largest distance. The social cost of a candidate is its average distance to the voters. A deterministic (resp., randomized) voting rule must choose a candidate (resp., a lottery over candidates) based only on the rankings, and its distortion is the ratio of the (expected) social cost of its choice to the smallest social cost of any candidate, in the worst case over all metrics consistent with the observed rankings. [22] prove that the best distortion achievable by deterministic rules is 33. To see why deterministic rules cannot do any better and why randomization may help, consider a simple example with two voters (1,21,2) and two candidates (a,ba,b). Voter 11 prefers a to b while voter 22 prefers b to a. Let the underlying metric have distance d and Δ:=d(a,b) :=d(a,b). Only two consistent possibilities are (provably) of interest: • either voter 11 is located at a and voter 22 is located at the midpoint of a and b, which makes the social costs of a and b equal to Δ/4 /4 and 3Δ/43 /4, respectively, • or voter 11 is located at the midpoint and voter 22 is located at b, which makes the social costs of a and b equal to 3Δ/43 /4 and Δ/4 /4, respectively. aabbv1v_1v2v_2Δ (a)=Δ/4,SC(b)=3Δ/4SC(a)= /4, 8.19447ptSC(b)=3 /4aabbv1v_1v2v_2Δ (a)=3Δ/4,SC(b)=Δ/4SC(a)=3 /4, 8.19447ptSC(b)= /4 Figure 1: Two metrics consistent with the reported rankings, which shows a lower bound of 33 for deterministic rules and 22 for randomized rules. Thus, as Figure 1 makes visible, either candidate can be optimal while the other is 33 times worse, making 33 a barrier that deterministic rules cannot cross. However, choosing between a and b uniformly at random achieves an expected social cost of Δ/2 /2, which is only 22 times the minimum possible cost and that is the best possible distortion on this instance. It was even conjectured that 22 may be the optimal metric distortion of randomized rules, but [37, 12] disprove it by establishing a lower bound strictly greater than 22, converging to approximately 2.11262.1126 as m→∞m→∞. On the upper-bound side, [11] prove a distortion guarantee of 2.7532.753 by combining maximal lottery (MLML), the Nash equilibrium of a natural zero-sum game dating back to the 1960s [30, 7], and RaDiUS, a novel rule they design. Their work, which received the SODA 2024 Best Paper Award, establishes that randomized rules can in fact achieve a constant distortion strictly lower than the best guarantee of 33 for deterministic rules. Independently, [19] and [41] improve this to 2.52.5 with a rule of striking simplicity: the equal mixture of a maximal lottery and Integrated Veto (IVIV), an algorithmic procedure in which every voter continuously vetoes her current least-preferred surviving candidate. This still leaves a fundamental question open: What is the smallest distortion that a randomized voting rule can achieve using only voters’ preference rankings? 1.1 Our Results The main result of our work improves the upper bound, closing about 44%44\% of the gap between the upper bound of 2.52.5 and the lower bound of 2.11262.1126 left by prior work. Theorem 1. There exists a randomized voting rule with metric distortion at most 11641/5000=2.3282 116415000=2.3282. To accomplish this, we consider a generalization of maximal lotteries to stable k-lotteries (SLkSL_k) by [10], who use them to design so-called tournament voting rules with low metric distortion; stable 11-lotteries are precisely maximal lotteries. We design a further generalization of this to random-size stable lotteries: given a random variable D, RSLDRSL_D effectively provides the guarantee of SLkSL_k but with k drawn from D. Yet, we show that RSLDRSL_D cannot be obtained by simply mixing SLkSL_k for different values of k; we prove its existence for any D directly via a minimax argument similar to what [10] used for SLkSL_k, and give a multiplicative-weights approximation algorithm with an explicit running time when D has finite support. The main technical contribution of our work is to connect the guarantee provided by RSLDRSL_D to metric distortion via a much more intricate analysis than that of [10] for SLkSL_k. This allows us to conduct a computer-assisted search for a suitable distribution D⋆D , which, when mixed with Integrated Veto, yields the desired distortion bound. While we were not able to analytically derive the optimal distribution, we were able to extract rational coefficients—probabilities under D⋆D and mixture weights—which exactly yield the rational distortion bound in Theorem 1. Table 1 shows our bound in the context of lower and upper bounds from prior work. Upper bounds 33 optimal deterministic rule [22] 2.7532.753 a mixture of maximal lottery and RaDiUS [11] 2.52.5 the equal mixture of maximal lottery and Integrated Veto [19, 41] 2.32822.3282 a mixture of random-size stable lottery and Integrated Veto this paper Lower bounds 2.06312.0631 an example with m=7m=7 [37] 2.11262.1126 a construction for any m⩾3m 3, bound on the left as m→∞m→∞ [12] Table 1: Randomized metric distortion bounds from our work and prior work. 1.2 Technical Overview The 2.52.5 barrier. The distortion bound of 2.52.5 proved independently by [19] and [41] uses the equal mixture of Integrated Veto (IVIV) and maximal lottery (MLML). The analysis is organized around two quantities. Let C denote the candidate set, let I be any nonempty proper subset of C, and let P be a lottery. Informally, q(I)q(I) measures how far I is from containing a candidate that almost every voter ranks above every candidate outside I. The loss ℓ(P,I) (P,I) measures how much probability P assigns outside I, charging an outside candidate in proportion to the voters who rank every member of I above it. These quantities are defined formally in Section 2.1. The following implication of [11], in the form stated by [19], lets us work entirely with rankings. 0012 120.66410.664111000.50.50.66410.66410.750.7511Previous barrier of 3/43/4q=q(I)q=q(I)upper bound on ℓ(P,I)/q(I) (P,I)/q(I)IVIVMLML(IV+ML)/2(IV+ML)/2RSLD⋆RSL_D P⋆P Figure 2: Established upper bounds on the loss ratio ℓ(P,I)/q(I) (P,I)/q(I) as a function of q(I)q(I). The curves are bounds, not exact losses. Under these bounds, reweighting IVIV and MLML cannot cross the horizontal threshold 3/43/4. Our rule mixes IVIV with RSLD⋆RSL_D so that their increasing and decreasing bounds cancel at 0.66410.6641, yielding distortion 2.32822.3282 through Proposition 1. Proposition 1 ([11, 19]). Let κ⩾0κ 0. If a lottery P satisfies ℓ(P,I)⩽κq(I) (P,I) κ\,q(I) for every nonempty proper I⊊CI C, then dist(P)⩽1+2κdist(P) 1+2κ. Thus, it suffices to bound the ratio ℓ(P,I)/q(I) (P,I)/q(I) for every set with q(I)>0q(I)>0; when q(I)=0q(I)=0, the required loss is zero. The prior analysis gives ℓ(IV,I)q(I)⩽q(I)andℓ(ML,I)q(I)⩽min1,12q(I). (IV,I)q(I) q(I) (ML,I)q(I) \1, 12q(I) \. Figure 2 shows these upper bounds. Their equal mixture reaches 3/43/4 at both q=1/2q=1/2 and q=1q=1, and shifting weight toward either rule raises one of these two values. Thus the existing arguments do not yield a better bound with any mixture of these rules. [41] proves a stronger obstruction: even if the mixture is chosen from the profile and the veto component uses arbitrary, possibly adaptive, time weights along the Simultaneous Plurality Veto trajectory, some profile still forces distortion at least 5/25/2. Random-size stable lotteries. Our new ingredient starts from stable k-lotteries (SLkSL_k) [10], which generalize maximal lotteries and satisfy Prv[c≻v(SLk)k]⩽1k+1for every c∈C. _v[c _v(SL_k)^k] 1k+1 every c∈ C. Here (SLk)k(SL_k)^k consists of k independent draws from SLkSL_k, v is a uniformly random voter, and the probability also includes the draws and the prescribed tie-breaking. The case k=1k=1 is precisely a maximal lottery. We let the number of draws itself be random. For a positive-integer-valued random variable D, a random-size stable lottery RSLDRSL_D satisfies DPrv[c≻v(RSLD)D]⩽[1D+1]for every c∈C. _D _v[c _v(RSL_D)^D] [ 1D+1 ] every c∈ C. When D=kD=k deterministically, this recovers SLkSL_k. Crucially, one lottery must be chosen before D is realized: independently choosing an SLkSL_k for each k and then mixing those lotteries does not work because repeated draws from the mixture create uncontrolled cross terms. A convex minimax argument nevertheless proves that RSLDRSL_D exists for every D. The definition and proof appear in Section 3; an approximation algorithm is deferred to Appendix A. Why a random number of draws helps. Fix a voter and a reference candidate, and suppose that RSLDRSL_D places mass t on candidates strictly below that candidate and no mass on the candidate itself. The probability that the reference candidate beats all D draws is ϕ(t):=[tD]=∑d⩾1Pr[D=d]td.φ(t):= [t^D]= _d 1 [D=d]\,t^d. It is tempting to use the same formula without the zero-mass assumption, but this is incorrect because draws equal to the reference candidate create ties. Under the random-label tie-breaking defined in Section 3, if b is the mass strictly below the reference candidate and z is the mass on it, then conditioning on its label s∈[0,1]s∈[0,1] gives the corrected probability ∫01ϕ(b+sz)s _0^1φ(b+sz) \!ds. Thus the tie-breaking is an essential part of the comparison rule and of the convexity argument establishing existence. This is where the distribution of D enters the proof. For a candidate set I, random-size stability can be applied both to the candidate in I that is usually ranked above everything outside I and, on average, to the candidates receiving probability from RSLDRSL_D. Together, these two applications constrain how much loss RSLDRSL_D can place outside I. The constraints involve ϕ(t)φ(t) at the voter-level values of t, so they retain the entire shape of ϕφ, not only the scalar [1/(D+1)]=∫01ϕ(t)dt [1/(D+1)]= _0^1φ(t) \!dt. This extra freedom is exactly what the figure exploits. The distribution D⋆D , supported on 11, 1212, and 1313, gives a linearly decreasing upper bound on ℓ(RSLD⋆,I)/q(I) (RSL_D ,I)/q(I). Integrated Veto gives the linearly increasing upper bound q(I)q(I). Mixing the two cancels these slopes and keeps the loss ratio at most 0.66410.6641 for every I. Proposition 1 then gives distortion at most 1+2(0.6641)=2.32821+2(0.6641)=2.3282. 1.3 Related Work Metric distortion. The metric model was introduced by [3, 2], who proved a lower bound of 33 for every deterministic rule and an upper bound of 55 for the Copeland rule. [24] showed that Ranked Pairs can have distortion at least 55 and, more broadly, that even randomization cannot take tournament rules below distortion 33. [35] reduced the upper bound to 2+5≈4.2362+ 5≈ 4.236 using generalized uncovered sets and proposed a candidate-selection condition whose universal existence would imply distortion 33; [26] subsequently developed an LP-duality framework that unified these analyses and led to closely related sufficient conditions. [22] finally matched the lower bound with Plurality Matching, settling the optimal deterministic distortion at 33. Subsequent work made this guarantee considerably more transparent. Plurality Veto initializes each candidate’s score at its plurality share and has voters, in an arbitrary order, veto their least-preferred candidate with positive score until one candidate survives [28]. Simultaneous Plurality Veto removes the dependence on voter order by letting all voters veto continuously and simultaneously, while preserving distortion 33 [29]. Integrated Veto, introduced independently by [19] and [41] (under the name Veto Lottery in the latter), turns this deterministic process into a lottery by assigning each candidate probability equal to twice the area under its score trajectory. Thus, the Integrated Veto component of our rule descends directly from the sequence of deterministic rules that attained the optimal distortion of 33. Utilitarian distortion. In the utilitarian model initiated by [36], voters again report only rankings, but the hidden cardinal values are otherwise unrestricted and the objective is to maximize their sum. Here normalization is essential: rankings are unchanged if one rescales each voter’s utilities independently, so rank data alone provide no way to place different voters’ utilities on a common scale. The standard unit-sum model normalizes each voter’s utilities to sum to one, giving every voter equal weight while retaining the relative intensity of her preferences. Metric distortion needs no analogous normalization because a common underlying metric already places all voters’ costs on the same scale. Under unit-sum utilities, the optimal deterministic distortion is Θ(m2) (m^2) [9, 8]; [6] proved an Ω(m) ( m) lower bound for randomized rules, and [14] matched it with an O(m)O( m) rule, closing the randomized case asymptotically as well. Although the metric and utilitarian models are each motivated by the same loss of cardinal information, rules optimized for one can perform poorly in the other. [23] nevertheless design deterministic and randomized rules that simultaneously achieve near-optimal guarantees in both models, establishing best-of-both-worlds distortion. Information–distortion tradeoffs. Full rankings are only one point on a broader elicitation spectrum. At one end, top-t ballots ask each voter to rank only her t favorite candidates; work under both utilitarian and metric objectives quantifies what can still be guaranteed as this reported prefix shrinks [27, 5]. At the other end, a value query asks a voter for her exact utility for one candidate in addition to her ranking. A few such queries can sharply reduce utilitarian distortion [1]; for any constant λ, [15] achieve O(minn,m1/λ)O( \n,m \^1/λ) distortion using λ value queries per voter, matching the known dependence on m when n=Ω(m)n= (m). More generally, one can optimize the elicitation format itself subject only to a bit budget. [32, 33] characterize this communication–distortion frontier up to logarithmic factors: achieving utilitarian distortion d requires Θ~(m/d) (m/d) bits per voter with deterministic elicitation and Θ~(m/d3) (m/d^3) bits with randomized elicitation. Hence, the format of the elicited information can matter as much as its quantity: a carefully designed short message may yield lower distortion than a substantially longer ranked ballot. 2 Preliminaries Let C be a finite set of m candidates and V a finite set of n voters. For a positive integer r, write [r]=1,…,r[r]= \1,…,r \. Each voter v∈Vv∈ V reports a strict ranking ≻v _v of C, and the profile is the collection σ=(≻v)v∈Vσ=( _v)_v∈ V. Unless stated otherwise, v is drawn uniformly at random from V in every expectation or probability carrying the subscript v. A metric instance places the voters and candidates in a common metric space with distance d.11 1 Distinct points are allowed to be at distance zero, so technically this is a pseudometric. It is consistent with σ if every voter’s ranking agrees with her distances, that is, a≻vba _vb implies d(v,a)⩽d(v,b)d(v,a) d(v,b) for all v∈Vv∈ V and a,b∈Ca,b∈ C. The social cost of a candidate c and the expected social cost of a lottery P∈Δ(C)P∈ (C), the set of probability distributions on C, are SCd(c)=v[d(v,c)]andSCd(P)=c∼P[SCd(c)].SC_d(c)= _v[d(v,c)] _d(P)= _c P[SC_d(c)]. Definition 1 (Distortion). For a profile σ and a lottery P, define distσ(P)=supd consistent with σSCd(P)minc∈CSCd(c),dist_σ(P)= _d consistent with σ SC_d(P) _c∈ CSC_d(c), with the usual conventions 0/0=10/0=1 and z/0=+∞z/0=+∞ for z>0z>0. We drop the subscript when the profile is fixed. A randomized social choice rule ℛR maps each profile σ to a lottery, and its distortion is supσdistσ(ℛ(σ)) _σdist_σ(R(σ)). We write Drand(m)D_rand(m) for the smallest distortion achievable with m candidates and supmDrand(m) _mD_rand(m) for the unrestricted optimum. Note that the rule is unaware of the underlying consistent metric. 2.1 Analysis via Candidate Sets Analyzing the worst case over the vast space of metrics consistent with the reported rankings is cumbersome. [11] simplify the analysis by showing that it suffices to reason about a set of inequalities involving only the reported rankings. We use the following reformulation of their approach, made explicit by [19]. For a nonempty proper subset of candidates I⊊CI C, let J:=C∖IJ:=C I and define q(I) q(I) =mini∈IPrv[j≻vi for some j∈J], = _i∈ I _v[j _vi for some j∈ J], (2.1) ℓ(P,I) (P,I) =∑j∈JP(j)Prv[i≻vj for every i∈I]. = _j∈ JP(j) _v[i _vj for every i∈ I]. (2.2) We will sometimes refer to a candidate z∈Iz∈ I attaining the minimum in Equation 2.1. The meanings of these two quantities are simple. Some candidate z∈Iz∈ I is ranked above every candidate outside I by 1−q(I)1-q(I) fraction of voters. When q(I)q(I) is very small, almost all voters rank z above every candidate outside I. If a lottery P were to then place significant probability mass outside I, z could lead to P having high distortion. Hence, the loss ℓ(P,I) (P,I) charges any probability that P places outside I, but probability placed on j∉Ij∉ I is charged only on voters who rank all members of I above j. It turns out that keeping ℓ(P,I) (P,I) small whenever q(I)q(I) is small is a guaranteed route to achieving low distortion. See 1 [19] finds a lottery which achieves κ=3/4κ= 34. Our goal is to find a lottery with κ<3/4κ<3/4 — more precisely, κ=0.6641κ=0.6641, which yields the desired distortion bound of 2.32822.3282. Let us understand these quantities better through an example. Example 1 (Understanding q(I)q(I), ℓ(P,I) (P,I), and κ). Let C=a,b,cC= \a,b,c \ and |V|=20|V|=20, with the preference profile shown on the right. Take I=a,bI= \a,b \, so J=cJ= \c \. Candidate a fails to beat c for a 3/53/5 fraction of the voters, whereas candidate b fails to beat c for a 1/41/4 fraction of the voters. Hence q(I)=min35,14=14,z=b.q(I)= \ 35, 14 \= 14, z=b. #Voters Ranking 88 a≻b≻ca b c 77 b≻c≻ab c a 55 c≻a≻bc a b Only the first group of voters ranks both a and b above c, so ℓ(P,I)=25P(c) (P,I)= 25P(c) for every lottery P. A rule can therefore satisfy ℓ(P,I)⩽κq(I) (P,I) κ q(I) for this particular I only by keeping P(c)P(c) at most 5κ/85κ/8. To yield the desired distortion bound, however, it must satisfy the inequality for I=a,b,c,b,c,a,cI= \a \, \b \, \c \, \b,c \, \a,c \ as well. We revisit this example in Example 2. 2.2 Integrated Veto and Maximal Lotteries We combine two kinds of lotteries. The first follows the progression described in Section 1.3: Integrated Veto was introduced independently by [19] and [41]; the latter calls it Veto Lottery. It runs the Simultaneous Plurality Veto process of [29]. Each candidate starts with a score equal to the fraction of voters ranking it first. While positive scores remain, every voter continuously decreases, at rate 1/n1/n, the score of her least-preferred candidate among those with positive score. Integrated Veto gives each candidate probability equal to twice the area under its score trajectory. The factor of two and the fact that these probabilities sum to one have the same two-line explanation. The scores start summing to one and, as long as any candidate is active, the total decreases at rate exactly one, so the total score is 1−t1-t at time t, until it reaches zero at time t=1t=1. The area under the total-score curve is therefore the area of a triangle with legs 11 and 11, namely 1/21/2, and doubling turns areas into probabilities. Example 2 (Integrated Veto on the profile of Example 1). Take the profile of Example 1. The initial scores are the plurality shares (25,720,14)( 25, 720, 14) for (a,b,c)(a,b,c). Initially the first group vetoes c, the second vetoes a, and the third vetoes b, so the three scores fall at rates of 720 720, 14 14, and 25 25, respectively. Candidate c is exhausted at t=58t= 58; at that moment the first group joins the third in vetoing b, whose score then falls at a rate of 25+14=1320 25+ 14= 1320. Candidate b is exhausted at t=1213t= 1213, after which all voters veto a, which is exhausted at t=1t=1. Figure 3 plots the three trajectories. Doubling the areas gives IV(a)=2965,IV(b)=8272080,IV(c)=532,IV(a)= 2965, (b)= 8272080, (c)= 532, which sum to one. For the set I=a,bI= \a,b \ of Example 1, the loss is ℓ(IV,I)=25⋅532=116=q(I)2 (IV,I)= 25· 532= 116=q(I)^2. [19] more generally proves ℓ(IV,I)⩽q(I)2 (IV,I) q(I)^2, stated in Lemma 1 below, which holds with equality in this example. ttscore0058 581213 12131114 14720 72025 25aabbcc Figure 3: Integrated Veto score trajectories for Example 2. Each candidate’s probability is twice the area under its trajectory. The three areas sum to 1/21/2 because the total score is 1−t1-t throughout, which is also why the factor of two is the right normalization. A trajectory changes slope only when some candidate is exhausted and the voters who were vetoing it switch to their next-least-preferred active candidate. The second lottery is a maximal lottery, which is a Nash equilibrium of the following two-player zero-sum game. Each player chooses a lottery over candidates. Nature draws one candidate from each lottery and one random voter. The voter awards a point to the player whose candidate she prefers; identical draws split the point equally. The game is symmetric, so its value is 1/21/2, and a maximin strategy is a maximal lottery. We write MLML for an arbitrary maximal lottery. According to [7], this rule was first considered by [30], but it is so fundamental that it has been rediscovered repeatedly [17, 31, 18, 16, 38]. The following bounds are the ingredients of the previous 5/25/2 result. Lemma 1 ([19]). For every nonempty proper I⊊CI C, with q=q(I)q=q(I), ℓ(IV,I)⩽q2andℓ(ML,I)⩽minq,1/2. (IV,I) q^2 (ML,I) \q,1/2 \. Dividing by q and averaging the two bounds shows that the loss ratio ℓ((IV+ML)/2,I)/q ((IV+ML)/2,I)/q is at most 1+q2 1+q2 for q⩽1/2q 1/2 and at most q2+14q q2+ 14q for q⩾1/2q 1/2. Both expressions are at most 3/43/4, so Proposition 1 gives distortion at most 5/25/2. As noted in Section 1.2, Proposition 1 does not yield a better bound even under any unequal mixture of IVIV and MLML; [41] explicitly proves that a much larger family of rules in fact has distortion no better than 5/25/2. 3 Random-Size Stable Lotteries We now formally define our key novel ingredient: random-size stable lotteries. We prove their existence by extending the minimax argument of [10] from a fixed number of draws k to a random number of draws D. In Appendix A, we show that this also yields a standard multiplicative-weights algorithm to compute such lotteries approximately and establish other properties of interest that we will not use in our work. Comparing multisets. First, we need to lift each voter’s comparison of individual candidates to a comparison between multisets of candidates. Fix a voter v and two nonempty multisets S and T. It is natural to compare S and T by the candidates that v ranks highest in them. If these candidates are distinct, v’s ranking determines the comparison; the only ambiguity arises when the same candidate is highest-ranked in both multisets, possibly with different multiplicities. To resolve this ambiguity, we use the random-label tie-breaking scheme of [10]: give every duplicate an independent label drawn uniformly from [0,1][0,1], and let v compare duplicates by their labels. Thus, if voter v’s highest-ranked candidate in S∪TS∪ T has multiplicity r in S and s in T, then Pr[S≻vT]=r/(r+s) [S _vT]=r/(r+s). By choosing S or T to be singleton, this also yields comparisons between individual candidates and multisets. For a lottery P, a positive integer d, and a positive-integer-valued random variable D, we will be interested in the multisets PdP^d and PDP^D obtained by taking d and D independent draws from P, respectively. The random sample size. For a random number of draws D, let ϕ(t)=[tD]=∑d⩾1Pr[D=d]tdφ(t)= [t^D]= _d 1 [D=d]\,t^d be the probability-generating function of D. Note that ϕφ is increasing and convex on [0,1][0,1], with ϕ(0)=0φ(0)=0, ϕ(1)=1φ(1)=1, and ∫01ϕ(t)t=[1/(D+1)] _0^1φ(t) \!dt= [1/(D+1)]. Fix a voter v. If a lottery P places mass t on candidates that v ranks strictly below a candidate c and P(c)=0P(c)=0, then Pr[c≻vPD]=∑d⩾1Pr[D=d]⋅Pr[c≻vPd]=∑d⩾1Pr[D=d]⋅td=ϕ(t). [c _vP^D]= _d 1 [D=d]· [c _vP^d]= _d 1 [D=d]· t^d=φ(t). Without the assumption P(c)=0P(c)=0, this simple formula is incorrect because a draw equal to c ties the challenger. Let b be the P-mass strictly below c and let z=P(c)z=P(c). Conditional on the challenger copy of c receiving label s∈[0,1]s∈[0,1], a single draw from P loses to it with probability b+szb+sz. Random-label tie-breaking therefore gives the corrected formula Pr[c≻vPD]=∫01ϕ(b+sz)ds. [c _vP^D]= _0^1φ(b+sz) \!ds. When z=0z=0, this reduces to ϕ(b)φ(b). Definition 2 (Random-size stable lottery). We write RSLDRSL_D for an arbitrary lottery that is random-size stable for D, meaning that, for every challenger lottery A, DPrv[A≻v(RSLD)D]⩽[1D+1]. _D _v[A _v(RSL_D)^D] [ 1D+1 ]. Here, A=A1A=A^1 denotes a single random sample from A. When D=1D=1 deterministically, Definition 2 is precisely a maximal lottery; when D=kD=k deterministically, it is a stable k-lottery defined by [10]. [13, 25] define a related notion of stable lotteries over committees, which are more restrictive in that the committee does not necessarily come from independent draws from the same lottery, but more general in other dimensions, as discussed in Appendix A. DPrv[A≻v(RSLD)D] _D _v[A _v(RSL_D)^D] is linear in A, so it is enough to consider a single challenger candidate when maximizing or minimizing it. Because the comparison, with random-label tie-breaking, is designed to yield exactly one probabilistic winner, the equation in Definition 2 is also equivalent to DPrv[(RSLD)D≻vA]⩾1−[1D+1]. _D _v[(RSL_D)^D _vA] 1- [ 1D+1 ]. Theorem 2 (Existence of random-size stable lotteries). For every finite preference profile and every distribution of a positive-integer-valued random variable D, there exists a random-size stable lottery RSLDRSL_D such that DPrv[c≻v(RSLD)D]⩽[1D+1]for every c∈C. _D _v[c _v(RSL_D)^D] [ 1D+1 ] every c∈ C. (3.1) No smaller right-hand side works for every profile. Every candidate in the support of RSLDRSL_D satisfies the displayed inequality with equality. Proof. For this proof, abbreviate pD=[1/(D+1)]p_D= [1/(D+1)]. For a challenger lottery A and a lottery P, define F(A,P)=DPrv[A≻vPD].F(A,P)= _D _v[A _vP^D]. The function is linear in A. To see that it is continuous and convex in P, first take A to be a fixed candidate c and fix a voter. Let b be the P-mass strictly below c and let z=P(c)z=P(c). Conditional on the challenger copy of c having label s∈[0,1]s∈[0,1], this voter contributes ϕ(b+sz)φ(b+sz). Both b and z are linear in P, while ϕφ is continuous and convex; integrating over s, the voter, and A preserves these properties. The convex minimax theorem therefore gives minPmaxAF(A,P)=maxAminPF(A,P). _P _AF(A,P)= _A _PF(A,P). For every lottery P, exchangeability among d+1d+1 independent labeled draws gives Prv[P≻vPd]=1/(d+1) _v[P _vP^d]=1/(d+1), and hence F(P,P)=pDF(P,P)=p_D. Choosing P=AP=A shows that the right-hand side of the minimax equality is at most pDp_D, while maxAF(A,P)⩾F(P,P)=pD _AF(A,P) F(P,P)=p_D for every P. The minimax value is therefore exactly pDp_D. Because F is linear in A, an optimal P, denoted RSLDRSL_D, satisfies Equation 3.1 for every candidate. Finally, pD=F(RSLD,RSLD)=∑c∈CRSLD(c)DPrv[c≻v(RSLD)D].p_D=F(RSL_D,RSL_D)= _c∈ CRSL_D(c)\, _D _v[c _v(RSL_D)^D]. Every term in this weighted average is at most pDp_D, so equality holds for every candidate in the support. The same identity shows that no smaller universal right-hand side is possible. ∎ The cases of deterministic D recover maximal lotteries and stable k-lotteries directly. Random-size existence cannot instead be obtained by averaging separately chosen stable k-lotteries: independent draws from that average contain cross terms not controlled by fixed-size stability. Section A.1 gives a two-candidate example. The same convexity argument also gives a standard multiplicative-weights algorithm for approximating RSLDRSL_D; the precise guarantee and proof appear in Proposition 2. An exact identity for reversing which side receives the D draws, together with the nonnegative convexity term it produces, is given in Lemma 7. Its outside-mass consequence is incorporated into the profile-independent loss optimization below. 4 From Random-Size Stability to Loss Ratio To use Proposition 1, we would like to upper bound the loss ℓ(RSLD,I) (RSL_D,I) of a random-size stable lottery RSLDRSL_D in terms of only D and q(I)q(I), abstracting away any other relevant information from the full profile. The three lemmas in this section successively simplify this problem. 4.1 Abstracting the Profile Into an Infinite-Dimensional LP The first lemma, Lemma 2, is one of the most significant technical results enabling our approach. It condenses the worst-case over all profiles into an optimization program over a scalar x and two probability measures η and ξ, establishing the necessary link between random-size stability and the loss ℓ(RSLD,I) (RSL_D,I). Later, Lemma 3 applies a useful transformation to this program and Lemma 4 paves a pathway for upper bounding its optimal objective value. Lemma 2. Fix a positive-integer-valued random variable D. Write ϕD(t)=[tD] _D(t)= [t^D] and pD=[1D+1]p_D= [ 1D+1]. For q∈[0,1]q∈[0,1], define gD(q)=supx,η,ξ g_D(q)= _x,η,ξ x((1−q)∫[0,1]2b0dη(b0,y)+q∫[0,1]b1dξ(b1)) x ((1-q) _[0,1]^2b_0 \!dη(b_0,y)+q _[0,1]b_1 \!dξ(b_1) ) subject to to (1−q)∫[0,1]2ϕD(x+(1−x)y)dη(b0,y)+q∫[0,1]ϕD(xb1)dξ(b1)⩽pD,(C1) aligned &(1-q) _[0,1]^2 _D(x+(1-x)y) \!dη(b_0,y)+q _[0,1] _D(xb_1) \!dξ(b_1) p_D, (C1) aligned (1−q)∫[0,1]2(∫0yϕD((1−x)u+xb0)du+∫y1ϕD((1−x)u+x)du)dη(b0,y)+q∫[0,1](∫01ϕD((1−x)u+xb1)du)dξ(b1)⩽pD,(C2) aligned &(1-q) _[0,1]^2 ( _0^y _D((1-x)u+xb_0) \!du+ _y^1 _D((1-x)u+x) \!du ) \!dη(b_0,y)\\ & +q _[0,1] ( _0^1 _D((1-x)u+xb_1) \!du ) \!dξ(b_1) p_D, (C2) aligned x((1−q)∫[0,1]2b0dη(b0,y)+q∫[0,1]b1dξ(b1))⩽(1−pD)x,(C3) aligned &x ((1-q) _[0,1]^2b_0 \!dη(b_0,y)+q _[0,1]b_1 \!dξ(b_1) ) (1-p_D)x, (C3) aligned η([0,1]2)=1,ξ([0,1])=1,x∈[0,1],η,ξ⩾0. η([0,1]^2)=1, ξ([0,1])=1, x∈[0,1], η,ξ 0. Note that η and ξ range over nonnegative finite Borel measures on [0,1]2[0,1]^2 and [0,1][0,1], respectively. Then, for every profile, every random-size stable lottery RSLDRSL_D, and every nonempty proper I⊊CI C, ℓ(RSLD,I)⩽gD(q(I)). (RSL_D,I) g_D(q(I)). We acknowledge that the statement of this lemma may be jarring for a reader at this point in the paper as the complicated optimization program has no prior foundation. So, before diving into a rigorous proof, let us provide some insights on the high-level approach and where some of these terms come from. Some subtleties are omitted in this exposition, but discussed in the rigorous proof that follows. Insights behind Lemma 2. Fix a nonempty proper I⊊CI C, put J=C∖IJ=C I, and choose z∈Iz∈ I attaining the minimum in the definition of q(I)q(I). Recall that ℓ(RSLD,I)=∑j∈JRSLD(j)⋅Prv[i≻vj for every i∈I]. (RSL_D,I)= _j∈ JRSL_D(j)· _v[i _vj for every i∈ I]. To separate the ingredients of this expression, write RSLD=(1−x)PI+xPJRSL_D=(1-x)P_I+xP_J, where x is its probability mass on J, and PI,PJP_I,P_J are RSLDRSL_D restricted (and renormalized) on I,JI,J, respectively. Let V0=v∈V:z≻vj for every j∈JV_0= \v∈ V:z _vj for every j∈ J \ and V1=V∖V0V_1=V V_0. By the definition of q(I)q(I), V0V_0 contains a 1−q(I)1-q(I) fraction of the voters. For s∈0,1s∈ \0,1 \ and v∈Vsv∈ V_s, let bs(v)b_s(v) be the PJP_J-mass on candidates that v ranks below every member of I. For v∈V0v∈ V_0, let y(v)y(v) be the PIP_I-mass on candidates ranked below z by v. Let η be the joint distribution of (b0(v),y(v))(b_0(v),y(v)) with v drawn uniformly from V0V_0, and let ξ be the distribution of b1(v)b_1(v) with v drawn uniformly from V1V_1. Then, the loss decomposes as ℓ(RSLD,I)=x((1−q(I))∫[0,1]2b0dη(b0,y)+q(I)∫[0,1]b1dξ(b1)). (RSL_D,I)=x ((1-q(I)) _[0,1]^2b_0 \!dη(b_0,y)+q(I) _[0,1]b_1 \!dξ(b_1) ). Notice that this matches the objective of the optimization program in Lemma 2. The proof then identifies three necessary constraints that random-size stability imposes on x, η, and ξ: (C1) comes from challenging RSLDRSL_D with z, (C2) from challenging it with PIP_I, and (C3) from reversing the latter comparison. We then forget the originating profile and maximize the displayed loss expression over all possible choices of x,η,ξx,η,ξ that satisfy (C1)–(C3). While some possible choices may not arise from any profile, this supremum upper bounds the loss on any feasible profile. The next two lemmas convert this profile-independent optimization into the pointwise scalar inequalities used in the proof of our main bound. Proof of Lemma 2. Fix a nonempty proper set I⊊CI C, put J=C∖IJ=C I and q=q(I)q=q(I), and choose z∈Iz∈ I attaining the minimum in Equation 2.1. Define V0=v∈V:z≻vj for every j∈JandV1=V∖V0.V_0= \v∈ V:z _vj for every j∈ J \ V_1=V V_0. By the definition of q(I)q(I), |V0|/|V|=1−q |V_0||V|=1-q. Let x=RSLD(J)x=RSL_D(J). If x=0x=0, then the loss is zero. Moreover, taking η and ξ to be point masses at (0,0)(0,0) and 00, respectively, is feasible in the definition of gD(q)g_D(q): the left-hand sides of (C1) and (C3) are zero, while that of (C2) is ∫01ϕD(u)u=pD _0^1 _D(u) \!du=p_D. Hence, suppose x>0x>0. Write PJ=RSLD|JP_J=RSL_D J for the conditional lottery outside I. When x<1x<1, write PI=RSLD|IP_I=RSL_D I; when x=1x=1, let PIP_I be any lottery supported on I. Encoding the loss. For s∈0,1s∈ \0,1 \ and each voter v∈Vsv∈ V_s, define bs(v)=∑j∈JPJ(j)⋅i≻vj for every i∈I.b_s(v)= _j∈ JP_J(j)·1 \i _vj for every i∈ I \. Thus bs(v)b_s(v) is the fraction of the outside conditional lottery that this voter ranks below every member of I. For each v∈V0v∈ V_0, give z an independent random label and let y(v)y(v) be the fraction of PIP_I lying below this labeled copy of z. Let η have the joint law of (b0(v),y(v))(b_0(v),y(v)) when v is drawn uniformly from V0V_0, including the randomness of the label, and let ξ have the law of b1(v)b_1(v) when v is drawn uniformly from V1V_1. If either set is empty, choose the corresponding measure arbitrarily. Since RSLD(j)=xPJ(j)RSL_D(j)=xP_J(j) for every j∈Jj∈ J, Equation 2.2 gives ℓ(RSLD,I) (RSL_D,I) =x∑j∈JPJ(j)⋅Prv[i≻vj for every i∈I] =x _j∈ JP_J(j)· _v[i _vj for every i∈ I] =xv[∑j∈JPJ(j)⋅i≻vj for every i∈I] =x _v [ _j∈ JP_J(j)·1 \i _vj for every i∈ I \ ] =x((1−q)∫[0,1]2b0dη(b0,y)+q∫[0,1]b1dξ(b1)). =x ((1-q) _[0,1]^2b_0 \!dη(b_0,y)+q _[0,1]b_1 \!dξ(b_1) ). The final equality is the law of total expectation over the partition V0V_0 and V1V_1. It remains to show that x,η,ξx,η,ξ satisfy (C1)–(C3). Deriving (C1) by applying stability to z. For v∈V0v∈ V_0, the lottery RSLDRSL_D places mass at least x+(1−x)y(v)x+(1-x)y(v) below the labeled copy of z; for v∈V1v∈ V_1, it places mass at least xb1(v)xb_1(v) below it. Since ϕD(t) _D(t) is the probability that all D draws fall within a mass of t, monotonicity of ϕD _D and random-size stability for z give (1−q)∫[0,1]2ϕD(x+(1−x)y)dη(b0,y)+q∫[0,1]ϕD(xb1)dξ(b1)⩽DPrv[z≻v(RSLD)D]⩽pD.(1-q) _[0,1]^2 _D(x+(1-x)y) \!dη(b_0,y)+q _[0,1] _D(xb_1) \!dξ(b_1) _D _v[z _v(RSL_D)^D] p_D. This proves (C1). Deriving (C2) by averaging stability over the inside lottery. Conditional on a voter v, draw an independently labeled candidate from PIP_I, and let Uv∈[0,1]U_v∈[0,1] be its labeled percentile within PIP_I, measured from worst to best in v’s ranking. Conditional on v, random labeling makes UvU_v uniform on [0,1][0,1] and independent of the label used to define y(v)y(v) for v∈V0v∈ V_0. For a realization Uv=uU_v=u and v∈Vsv∈ V_s, the challenger beats at least the (1−x)u(1-x)u mass of PIP_I below it and the xbs(v)xb_s(v) mass of PJP_J lying below every member of I. For v∈V0v∈ V_0, if u>y(v)u>y(v), it also lies above z and hence above all of PJP_J, so it beats mass at least (1−x)u+x(1-x)u+x. Averaging the resulting lower bound on the probability that all D draws lie below this candidate gives (1−q)∫[0,1]2(∫0yϕD((1−x)u+xb0)u+∫y1ϕD((1−x)u+x)u)dη(b0,y) (1-q) _[0,1]^2 ( _0^y _D((1-x)u+xb_0) \!du+ _y^1 _D((1-x)u+x) \!du ) \!dη(b_0,y) +q∫[0,1](∫01ϕD((1−x)u+xb1)du)dξ(b1)⩽DPrv[PI≻v(RSLD)D]⩽pD. +q _[0,1] ( _0^1 _D((1-x)u+xb_1) \!du ) \!dξ(b_1) _D _v[P_I _v(RSL_D)^D] p_D. This proves (C2). Deriving (C3) using the reverse comparison identity. Random-size stability with challenger lottery PIP_I gives DPrv[PI≻v(RSLD)D]⩽pD _D _v[P_I _v(RSL_D)^D] p_D, so Lemma 7 gives DPrv[PID≻vRSLD]⩽1−pD _D _v[P_I^D _vRSL_D] 1-p_D. Decomposing the one draw from RSLD=(1−x)PI+xPJRSL_D=(1-x)P_I+xP_J and using exchangeability gives DPrv[PID≻vRSLD]=(1−x)(1−pD)+xDPrv[PID≻vPJ]. _D _v[P_I^D _vRSL_D]=(1-x)(1-p_D)+x\, _D _v[P_I^D _vP_J]. Whenever every member of I beats j∈Jj∈ J, every nonempty multiset drawn from PIP_I beats j. Therefore, DPrv[PID≻vPJ] _D _v[P_I^D _vP_J] ⩾∑j∈JPJ(j)⋅Prv[i≻vj for every i∈I] _j∈ JP_J(j)· _v[i _vj for every i∈ I] =(1−q)∫[0,1]2b0dη(b0,y)+q∫[0,1]b1dξ(b1) =(1-q) _[0,1]^2b_0 \!dη(b_0,y)+q _[0,1]b_1 \!dξ(b_1) =ℓ(RSLD,I)x. = (RSL_D,I)x. Combining the last two equations gives ℓ(RSLD,I)⩽(1−pD)x (RSL_D,I) (1-p_D)x, which is precisely (C3). Thus every profile produces a feasible triple (x,η,ξ)(x,η,ξ) whose objective equals its loss. Since the definition of gD(q)g_D(q) takes the supremum over all such x and all probability measures η and ξ, including choices that need not arise from a profile, it upper bounds the loss and proves the lemma. ∎ 4.2 Simplified Primal Note that the program in Lemma 2 is not jointly linear in x, η, and ξ: its objective multiplies x by linear functionals of η and ξ, and its constraints depend nonlinearly on x through ϕD _D. To obtain a linear program, we fix x and search over x separately. When D, q, and x are fixed, the objective and constraints are linear in the decision measures η and ξ.22 2 For any fixed function h and scalars α,βα,β, ∫Sh(t)d(αη1+βη2)(t)=α∫Sh(t)dη1(t)+β∫Sh(t)dη2(t). _Sh(t) \!d(α _1+β _2)(t)=α _Sh(t) \!d _1(t)+β _Sh(t) \!d _2(t). Thus the integral is linear in the measures regardless of the form of h. For a reader unfamiliar with programs involving measures, the finite-support analogue is ∑z=110hzηz _z=1^10h_z _z, which is linear in the probability masses η1,…,η10 _1,…, _10 even if the coefficients hzh_z come from a nonlinear function. (C3) directly bounds the objective by (1−pD)x(1-p_D)x. Hence, instead of keeping (C3) in the program, we remove it—this can only increase the optimal objective value and hence keep it a valid upper bound on gD(q)g_D(q)—and instead constrain gD(q)g_D(q) directly using the upper bound provided by (C3). To succinctly write the resulting LP, we define some additional notation. For fixed D, abbreviate f(t)=ϕD(t),p=pD=∫01f(t)t,r=1−x.f(t)= _D(t), p=p_D= _0^1f(t) \!dt, r=1-x. For x>0x>0, define Kx K_x =∫01f(ru)u,Wx(y)=f(x+ry),wx(b1)=f(xb1), = _0^1f(ru) \!du, W_x(y)=f(x+ry), w_x(b_1)=f(xb_1), (4.1) Gx(b0,y) G_x(b_0,y) =∫0yf(ru+xb0)u+∫y1f(ru+x)u−Kxx, = _0^yf(ru+xb_0) \!du+ _y^1f(ru+x) \!du-K_xx, Fx(b1) F_x(b_1) =∫01f(ru+xb1)u−Kxx,Rx=p−Kxx. = _0^1f(ru+xb_1) \!du-K_xx, R_x= p-K_xx. (4.2) For any optimization program P, we will write val() (P) to denote its optimal objective value. Lemma 3. For fixed D, q∈[0,1]q∈[0,1], and x∈(0,1]x∈(0,1], let η and ξ range over probability measures on [0,1]2[0,1]^2 and [0,1][0,1], respectively, and consider Primal(D,q,x)(D,q,x) supη,ξ⩾0 _η,ξ 0 (1−q)∫[0,1]2b0dη(b0,y)+q∫[0,1]b1dξ(b1) (1-q) _[0,1]^2b_0 \!dη(b_0,y)+q _[0,1]b_1 \!dξ(b_1) subject to to (1−q)∫[0,1]2Wx(y)dη(b0,y)+q∫[0,1]wx(b1)dξ(b1) (1-q) _[0,1]^2W_x(y) \!dη(b_0,y)+q _[0,1]w_x(b_1) \!dξ(b_1) ⩽p, p, (1−q)∫[0,1]2Gx(b0,y)dη(b0,y)+q∫[0,1]Fx(b1)dξ(b1) (1-q) _[0,1]^2G_x(b_0,y) \!dη(b_0,y)+q _[0,1]F_x(b_1) \!dξ(b_1) ⩽Rx. R_x. Then gD(q)⩽max0,supx∈(0,1]:Primal(D,q,x) is feasibleminxval(Primal(D,q,x)),(1−p)x.g_D(q) \0,\ _ subarraycx∈(0,1]:\\ Primal(D,q,x) is feasible subarray \x ( Primal(D,q,x)),(1-p)x \ \. (4.3) Proof. The first constraint of Primal(D,q,x) Primal(D,q,x) is exactly (C1). In (C2), the function integrated against η is Kx+xGxK_x+xG_x, and the function integrated against ξ is Kx+xFxK_x+xF_x. Since both measures have mass one and (1−q)+q=1(1-q)+q=1, subtracting the common term KxK_x from (C2) and dividing by x gives the second constraint of Primal(D,q,x) Primal(D,q,x). Dividing the objective in Lemma 2 by x gives the objective of Primal(D,q,x) Primal(D,q,x). We leave (C3) outside Primal because it already gives the independent upper bound (1−p)x(1-p)x on the original, unnormalized objective. Consequently, every feasible choice in Lemma 2 with x>0x>0 has objective at most minxval(Primal(D,q,x)),(1−p)x. \x ( Primal(D,q,x)),(1-p)x \. Taking the supremum over the feasible values of x proves Equation 4.3. At x=0x=0, the original objective is zero, which accounts for the first term in the maximum. Note that optimizing over all measures thus constrained provides only an upper bound; we do not claim that every pair of measures feasible for Primal comes from a preference profile. ∎ 4.3 Bounding Loss via Dual The last step removes the distribution-valued variables by taking the dual of Primal; since Primal involves measures η and ξ over [0,1]2[0,1]^2 and [0,1][0,1], respectively, as variables, this requires using duality theory of generalized moment problems [40]. The dual has only four scalar variables, but infinitely many constraints: one for each (b0,y)∈[0,1]2(b_0,y)∈[0,1]^2 and one constraint for each b1∈[0,1]b_1∈[0,1]. Hence, the dual is a semi-infinite linear program. Lemma 4. For fixed D, q∈[0,1]q∈[0,1], and x∈(0,1]x∈(0,1], the dual of Primal(D,q,x) Primal(D,q,x) is Dual(D,q,x)(D,q,x) infλ,μ⩾0u,v∈ℝ _ subarraycλ,μ 0\\ u,v subarray λp+μRx+(1−q)u+qv λ p+μ R_x+(1-q)u+qv subject to to u+λWx(y)+μGx(b0,y) u+λ W_x(y)+μ G_x(b_0,y) ⩾b0 b_0 for every (b0,y)∈[0,1]2, every (b_0,y)∈[0,1]^2, v+λwx(b1)+μFx(b1) v+λ w_x(b_1)+μ F_x(b_1) ⩾b1 b_1 for every b1∈[0,1]. every b_1∈[0,1]. Every feasible solution (λ,μ,u,v)(λ,μ,u,v) of Dual(D,q,x) Dual(D,q,x), whether optimal or not, satisfies val(Primal(D,q,x))⩽λp+μRx+(1−q)u+qv. ( Primal(D,q,x)) λ p+μ R_x+(1-q)u+qv. (4.4) Consequently, given T:[0,1]→[0,∞)T:[0,1]→[0,∞), in order to prove that gD(q)⩽T(q)g_D(q) T(q) for all q∈[0,1]q∈[0,1], it suffices to prove that for each q∈[0,1]q∈[0,1] and x∈(0,1]x∈(0,1], at least one of the following holds. 1. Primal(D,q,x) Primal(D,q,x) is infeasible. 2. (1−p)x⩽T(q)(1-p)x T(q). 3. Dual(D,q,x) Dual(D,q,x) has a feasible solution (λ,μ,u,v)(λ,μ,u,v) with x(λp+μRx+(1−q)u+qv)⩽T(q)x (λ p+μ R_x+(1-q)u+qv ) T(q). Proof. Since all objective and constraint functions are continuous, Primal(D,q,x) Primal(D,q,x) is a so-called generalized moment problem, and its dual is precisely the semi-infinite linear program provided in the lemma. For an interested reader, Section B.1 derives the displayed dual via the Lagrangian. Moreover, whenever Primal(D,q,x) Primal(D,q,x) is feasible, generalized-moment duality [40, Corollary 3.1] gives val(Primal(D,q,x))=val(Dual(D,q,x)) ( Primal(D,q,x))= ( Dual(D,q,x)). The strong duality (equality of optimal values) requires checking a number of conditions on the program, but is stronger than what we need. We only need weak duality (which follows directly from first principles, as explained in Section B.1): the objective value of Dual(D,q,x) Dual(D,q,x) at every feasible solution (λ,μ,u,v)(λ,μ,u,v) is at least val(Primal(D,q,x)) ( Primal(D,q,x)), which proves Equation 4.4. Combining this inequality with Equation 4.3 proves the final claim: for each feasible x>0x>0, the minimum in Equation 4.3 is at most T(q)T(q) by one of the two stated alternatives, while x=0x=0 contributes zero. ∎ 5 A Rule with Distortion at Most 2.32822.3282 By Lemma 4, it is enough to exhibit (a) a draw distribution D and a target T(q)T(q), and (b) for every (q,x)∈[0,1]2(q,x)∈[0,1]^2, which of its three conditions are met, and in case of the third condition, via which dual feasible solution (λ,μ,u,v)(λ,μ,u,v). Table 2: Rule and target for Lemma 5 Let D⋆D be supported on 1,12,13 \1,12,13 \ with Pr[D⋆=1]=423239106,Pr[D⋆=12]=471105106,Pr[D⋆=13]=105656106. [D =1]= 42323910^6, 18.49988pt [D =12]= 47110510^6, 18.49988pt [D =13]= 10565610^6. Its probability-generating function and stability threshold are ϕD⋆(t)=423239t+471105t12+105656t13106,pD⋆=∫01ϕD⋆(t)t=46483747182000000. _D (t)= 423239t+471105t^12+105656t^1310^6, 18.49988ptp_D = _0^1 _D (t) \!dt= 46483747182000000. Put a=3320542059,b=794142059,T(q)=q(a−bq).a= 3320542059, 18.49988ptb= 794142059, 18.49988ptT(q)=q(a-bq). Section 5 provides (a). For (b), Section B.2 in Section B.2 gives 4949 parametric dual tuples j=(λj,μj,uj,vj)z_j=( _j, _j,u_j,v_j) for j∈[49]j∈[49], and Section B.2 in Section B.2 lists the 5050 candidate bounds obtained from the (C3) bound and these 4949 tuples. Section B.3 proves that each dual tuple is feasible on its stated range of x, while Section B.4 proves that at least one eligible candidate bound applies at every relevant (q,x)(q,x). The case x=0x=0 is immediate, while Section B.2 proves primal infeasibility at x=1x=1 for q<1−pD⋆q<1-p_D . Verifying a dual solution requires plugging the dual solution, a function of x, into the objective and constraints of Dual(D⋆,q,x) Dual(D ,q,x) and verifying throughout its stated domain that (a) all the constraints are met and (b) the objective is upper bounded by T(q)T(q). Both parts reduce to verifying that a number of polynomials in one or two variables are nonnegative over their respective domains. This is verified using exact rational arithmetic by the algorithm of [20], which rewrites the polynomials in their so-called Bernstein bases and uses the derived Bernstein coefficients to establish nonnegativity throughout the desired domain. To verify that at least one of the 5050 candidate bounds applies at every relevant point, we apply the algorithm of [20] to the resulting disjunction of polynomial inequalities.33 3 [20] describe the subdivision test for one polynomial. We apply the same test to every eligible polynomial on each subdivision and accept that subdivision when any one test succeeds. When no single candidate can be verified throughout the current domain, the algorithm automatically subdivides the domain and repeats the test on the resulting subdivisions. This process is not guaranteed to terminate because nonnegative Bernstein coefficients are sufficient but not necessary for polynomial nonnegativity. However, whenever it terminates, the resulting subdivisions cover the entire domain and at least one required inequality holds throughout each subdivision, so the verification is sound. It terminates in our case using exact rational arithmetic. The verification code is available via our GitHub repository44 4 https://github.com/nisarg89/metric-distortion and instructions for running it as well as the expected output are listed in Section B.7. This verification concludes in the following lemma, for which a complete proof is provided in Section B.4. Lemma 5. Let D⋆D , a, and b be as specified in Section 5. Then, gD⋆(q)⩽q(a−bq)g_D (q) q(a-bq) for all q∈[0,1]q∈[0,1]. Consequently, for every profile and every random-size stable lottery RSLD⋆RSL_D , we have ℓ(RSLD⋆,I)⩽q(I)⋅(a−b⋅q(I)) (RSL_D ,I) q(I)· (a-b· q(I) ) for every nonempty proper I⊊CI C. We are now ready for our main result. See 1 Proof. Consider the rule P⋆=794150000IV+4205950000RSLD⋆,P = 794150000IV+ 4205950000RSL_D , and fix a nonempty proper I⊊CI C. Write q=q(I)q=q(I). By Lemmas 1 and 5 and the linearity of ℓ(P,I) (P,I) in P, ℓ(P⋆,I)⩽794150000q2+4205950000q(3320542059−794142059q)=664110000q. (P ,I) 794150000q^2+ 4205950000q ( 3320542059- 794142059q )= 664110000q. (5.1) Therefore, Proposition 1 gives dist(P⋆)⩽1+2⋅664110000=116415000=2.3282dist(P ) 1+2· 664110000= 116415000=2.3282. ∎ Equation 5.1 shows why we sought a loss upper bound of the form T(q)=q(a−bq)T(q)=q(a-bq). This is so that the loss ratio is upper bounded as ℓ(RSLD⋆,I)/q(I)⩽a−bq(I) (RSL_D ,I)/q(I) a-bq(I), a linearly decreasing function of q. When mixed appropriately with the linearly increasing upper bound of ℓ(IV,I)/q(I)⩽q(I) (IV,I)/q(I) q(I) for IVIV (Lemma 1), the variation cancels out, giving us the constant upper bound of ab+1=664110000 ab+1= 664110000 on κ and allowing us to apply Proposition 1. Figure 2 shows the upper bounds on the loss ratios of IVIV (linearly increasing), RSLD⋆RSL_D (linearly decreasing), and the mixture P⋆P (constant at 664110000 664110000). A note on the search process. While the search process used to identify the candidate solutions presented in Sections 5 and B.2 is irrelevant from the perspective of proving the claimed distortion bound, let us describe its stages at a high level to provide some intuition; Sections B.5 and B.6 describe the full process, and Section B.7 provides instructions for an interested reader to execute our code and perform an independent search. • First, for fixed (D,q,x)(D,q,x), we aim to solve Dual(D,q,x) Dual(D,q,x) via constraint-generation: we start by solving it with only finitely many constraints imposed at some E⊂[0,1]2E⊂[0,1]^2 and E1⊂[0,1]E_1⊂[0,1]; call a separation oracle on the returned solution to check if a constraint corresponding to some (b0,y)∈[0,1]2(b_0,y)∈[0,1]^2 or b1∈[0,1]b_1∈[0,1] is violated and add a violated constraint to E or E1E_1, respectively; and repeat until the separation oracle fails to find a violated dual constraint. This process is plugged inside a broader grid-search over (q,x)∈[0,1]2(q,x)∈[0,1]^2 for each fixed D, and that in turn inside an ad hoc search over D in the probability simplex with support S⊂[60]S⊂[60] of size |S|⩽4|S| 4. • Note that this search is by no means exact. The use of ϕφ in the Dual coefficients makes the separation oracle nonlinear; SciPy’s differential_evolution heuristic is used to implement it, which may fail to find a violated constraint even when one exists. Hence, exact feasibility of any candidate dual feasible solution identified must be verified separately using rational arithmetic. The same issue applies to the numerical LP solver HiGHS from SciPy we use to solve Dual on a finite set of constraints corresponding to (E,E1)(E,E_1), which may return a solution that may turn out to be infeasible under an exact feasibility check. Finally, an upper bound gD(q)⩽T(q)g_D(q) T(q) requires taking the supremum over x∈[0,1]x∈[0,1] and must hold for all q∈[0,1]q∈[0,1], whereas we use only a grid over (q,x)∈[0,1]2(q,x)∈[0,1]^2. • Nonetheless, the grid search produces a candidate (D⋆,a,b)(D ,a,b) with the lowest identified a/(1+b)a/(1+b), listed in Section 5, for which we have evidence to believe that gD⋆(q)⩽q(a−bq)g_D (q) q(a-bq) for all q∈[0,1]q∈[0,1] may hold. To certify this, based on the candidate dual solutions found at the grid points, it also identified which constraints are tight in different regions and used that to analytically derive and rationalize the 4949 parametrized dual solutions as functions of x listed in Section B.2. As we described above, subsequent exact verification was successful on these candidates identified by the search. 6 Discussion Room for improvement. We see four avenues to improve the bound with differing prospects. • Numerical certification. The numerical search estimated a bound of approximately 2.328182.32818, compared with the certified bound of 2.32822.3282. Hence, more precise rationalization and stronger numerical certification may have little to no room for improvement. • The draw distribution. Even when we searched over draw distributions with support size 44, the best we could find placed positive masses only on 11, 1212, and 1313. Our search suggests that the optimal distribution seems to converge to bimodality with modes at 11 and p for some positive real number p, with mass placed on p discretized by placing appropriate masses on ⌊p⌋ p and ⌈p⌉ p ; if this is true, it would suggest that the optimal distribution has support structure very similar to that of our D∗D^* and looking for alternative draw distributions may only yield modest improvement. • The analysis. Replacing the affine loss envelope by a tighter one may help, but we are more optimistic about a joint analysis of IVIV and RSLD⋆RSL_D that does not simply take a convex combination of their separate worst-case bounds, or about retaining more of the constraints imposed by the profile in our initial optimization program in Lemma 2. Even more fundamentally, our entire analysis hinges on optimizing κ to then apply Proposition 1, but this result itself is only a sufficient condition, not necessary. • The rule. We genuinely do not know whether a mixture of IVIV, MLML, and one or several random-size stable lotteries RSLD1,RSLD2,…RSL_D_1,RSL_D_2,… might already reach optimal distortion (the lower bound sits at 2.1126…2.1126…), or whether closing the gap may require a fundamentally new rule. For m⩾4m 4 candidates, determining the optimal randomized metric distortion remains open, including whether its limit as m→∞m→∞ equals the asymptotic lower bound 2.1126…2.1126… of [12]. A fascinating experience working with GPT-5.6-Sol. The bound of 2.32822.3282 emerged through a rapid series of improvements. • When we provided the work of [19], together with detailed instructions on how to effectively make improvements on open problems, GPT-5.6-Sol autonomously identified an appropriate ingredient to add—stable 22-lottery SL2SL_2 [10]—and achieved a bound of 2.49242.4924 using a mixture of (IV+ML)/2(IV+ML)/2 and SL2SL_2. • Then, it explored placing unequal weights on IVIV and MLML, which reduced the bound to 2.46622.4662. • When we asked it to find a further improvement, GPT-5.6-Sol autonomously came up with the idea of using a lottery P for which 12Prv[c≻vP]+12Prv[c≻vP2]⩽512 12 _v[c _vP]+ 12 _v[c _vP^2] 512, proved its existence using a minimax argument, and reduced the bound to 2.422.42 by mixing it with IVIV and MLML. • At this point, we generalized its proposed lottery into the random-size stable lottery RSLDRSL_D presented in this work and asked it to systematically search over the space of D. • This led to a rapid series of autonomous improvements, which culminated in the 2.32822.3282 bound presented in this work. We have not manually verified all these intermediate results, only the final bound and its corresponding mathematical claims presented in this work. Watching this sequence unfold over the short span of 2 days was both a fascinating experience and thought-provoking regarding the nature of research and implications for science in an era in which such rapid autonomous discoveries are possible. AI Disclosure All the mathematical proofs were derived by OpenAI Codex (GPT-5.6-Sol at Max effort) based on research directions, literature connections, proof and search strategies, and inspirations supplied by the author. The author has verified all mathematical details, presented simplified arguments and detailed expositions, often with the aid of GPT-5.6-Sol and Claude Opus 5, and retains full responsibility for all the content and any errors. Acknowledgments This work was supported by an NSERC Discovery Grant and an NSERC-CSE Research Communities Grant. Researchers funded through the NSERC-CSE Research Communities Grants do not represent the Communications Security Establishment Canada or the Government of Canada. Any research, opinions or positions they produce as part of this initiative do not represent the official views of the Government of Canada. References [1] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris (2021) Peeking behind the ordinal curtain: improving distortion via cardinal queries. Artificial Intelligence 296, p. 103488. Cited by: §1.3. [2] E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron (2018) Approximating optimal social choice under metric preferences. Artificial Intelligence 264, p. 27–51. Cited by: §1.3, §1. [3] E. Anshelevich, O. Bhardwaj, and J. Postl (2015) Approximating optimal social choice under metric preferences. In proc29thaaai, p. 777–783. Cited by: §1.3. [4] K. J. Arrow (1951) Social choice and individual values. Wiley. Cited by: §1. [5] A. Borodin, D. Halpern, M. Latifian, and N. Shah (2022) Distortion in voting with top-t preferences. In proc31stijcai, p. 116–122. Cited by: §1.3. [6] C. Boutilier, I. Caragiannis, S. Haber, T. Lu, A. D. Procaccia, and O. Sheffet (2015) Optimal social choice functions: a utilitarian view. Artificial Intelligence 227, p. 190–213. Cited by: §1.3. [7] F. Brandt (2017) Rolling the dice: recent results in probabilistic social choice. In Trends in Computational Social Choice, p. 3–26. Cited by: §1, §2.2. [8] I. Caragiannis, S. Nath, A. D. Procaccia, and N. Shah (2017) Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research 58, p. 123–152. Cited by: §1.3. [9] I. Caragiannis and A. D. Procaccia (2011) Voting almost maximizes social welfare despite limited communication. Artificial Intelligence 175 (9–10), p. 1655–1671. Cited by: §1.3. [10] M. Charikar, P. Ramakrishnan, Z. Tan, and K. Wang (2025) Metric distortion for tournament voting and beyond. In proc26thec, p. 790–818. Cited by: §1.1, §1.2, §3, §3, §3, 1st item, Abstract. [11] M. Charikar, P. Ramakrishnan, K. Wang, and H. Wu (2024) Breaking the metric voting distortion barrier. Journal of the ACM 71 (6), p. 42:1–42:33. Cited by: §1.2, Table 1, §1, §2.1, Proposition 1, Abstract. [12] M. Charikar and P. Ramakrishnan (2022) Metric distortion bounds for randomized social choice. In proc33rdsoda, p. 2986–3004. Cited by: Table 1, §1, §6. [13] Y. Cheng, Z. Jiang, K. Munagala, and K. Wang (2020) Group fairness in committee selection. ACM Transactions on Economics and Computation 8 (4), p. 23:1–23:18. Cited by: Appendix A, §3. [14] S. Ebadian, A. Kahng, D. Peters, and N. Shah (2024) Optimized distortion and proportional fairness in voting. ACM Transactions on Economics and Computation 12 (1), p. 3:1–3:39. Cited by: §1.3. [15] S. Ebadian and N. Shah (2025) Every bit helps: achieving the optimal distortion with a few queries. In proc39thaaai, p. 13788–13795. Cited by: §1.3. [16] D. S. Felsenthal and M. Machover (1992) After two centuries, should Condorcet’s voting procedure be implemented?. Behavioral Science 37 (4), p. 250–274. Cited by: §2.2. [17] P. C. Fishburn (1984) Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies 51 (4), p. 683–692. Cited by: §2.2. [18] D. C. Fisher and J. Ryan (1995) Tournament games and positive tournaments. Journal of Graph Theory 19 (2), p. 217–236. Cited by: §2.2. [19] F. Frank (2026) An improved bound for the randomized metric distortion problem. Note: arXiv:2608.17863 Cited by: §1.2, §1.3, Table 1, §1, §2.1, §2.1, §2.2, 1st item, Example 2, Lemma 1, Proposition 1, Abstract. [20] J. Garloff (1993) The Bernstein algorithm. Interval Computations (2), p. 154–168. Cited by: §B.4, §5, §5, footnote 3. [21] A. Gibbard (1973) Manipulation of voting schemes: a general result. Econometrica 41 (4), p. 587–601. Cited by: §1. [22] V. Gkatzelis, D. Halpern, and N. Shah (2020) Resolving the optimal metric distortion conjecture. In proc61stfocs, p. 1427–1438. Cited by: §1.3, Table 1, §1. [23] V. Gkatzelis, M. Latifian, and N. Shah (2023) Best of both distortion worlds. In proc24thec, p. 738–758. Cited by: §1.3. [24] A. Goel, A. K. Krishnaswamy, and K. Munagala (2017) Metric distortion of social choice rules: lower bounds and fairness properties. In proc18thec, p. 287–304. Cited by: §1.3. [25] Z. Jiang, K. Munagala, and K. Wang (2020) Approximately stable committee selection. In proc52ndstoc, p. 463–472. Cited by: Appendix A, §3. [26] D. Kempe (2020) An analysis framework for metric voting based on LP duality. In proc34thaaai, p. 2079–2086. Cited by: §1.3. [27] D. Kempe (2020) Communication, distortion, and randomness in metric voting. In proc34thaaai, p. 2087–2094. Cited by: §1.3. [28] F. E. Kizilkaya and D. Kempe (2022) Plurality veto: a simple voting rule achieving optimal metric distortion. In proc31stijcai, p. 349–355. Cited by: §1.3. [29] F. E. Kizilkaya and D. Kempe (2023) Generalized veto core and a practical voting rule with optimal metric distortion. In proc24thec, p. 913–936. Cited by: §1.3, §2.2. [30] G. Kreweras (1965) Aggregation of preference orderings. In Mathematics and Social Sciences I, p. 73–79. Cited by: §1, §2.2. [31] G. Laffond, J. Laslier, and M. Le Breton (1993) The bipartisan set of a tournament game. Games and Economic Behavior 5 (1), p. 182–201. Cited by: §2.2. [32] D. Mandal, A. D. Procaccia, N. Shah, and D. P. Woodruff (2019) Efficient and thrifty voting by any means necessary. In proc33rdneurips, p. 7178–7189. Cited by: §1.3. [33] D. Mandal, N. Shah, and D. P. Woodruff (2020) Optimal communication–distortion tradeoff in voting. In proc21stec, p. 795–813. Cited by: §1.3. [34] P. Massart (1990) The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. The Annals of Probability 18 (3), p. 1269–1283. Cited by: §A.5. [35] K. Munagala and K. Wang (2019) Improved metric distortion for deterministic social choice rules. In proc20thec, p. 245–262. Cited by: §1.3. [36] A. D. Procaccia and J. S. Rosenschein (2006) The distortion of cardinal preferences in voting. In proc10thcia, p. 317–331. Cited by: §1.3. [37] H. Pulyassary and C. Swamy (2021) On the randomized metric distortion conjecture. Note: arXiv:2111.08698 Cited by: Table 1, §1. [38] R. L. Rivest and E. Shen (2010) An optimal single-winner preferential voting system based on game theory. In proc3rdcomsoc, p. 399–410. Cited by: §2.2. [39] M. A. Satterthwaite (1975) Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory 10 (2), p. 187–217. Cited by: §1. [40] A. Shapiro (2001) On duality theory of conic linear problems. In Semi-Infinite Programming: Recent Advances, p. 135–165. Cited by: §B.1, §4.3, §4.3. [41] Q. Ye (2026) Half veto, half maximal lottery, five-halves distortion. Note: arXiv:2608.21202 Cited by: §1.2, §1.2, §1.3, Table 1, §1, §2.2, §2.2, Abstract. Appendix Appendix A Further Properties of Random-Size Stable Lotteries This appendix records further consequences of random-size stability. It relates the definition to deterministic challenger committees, comparisons using other numbers of samples, and lotteries with small support. These consequences do not subsume stable lotteries over committees [13, 25]: here every committee consists of independent draws from one lottery and a voter compares committees by their favorite members, whereas that literature permits correlated committee lotteries and more general committee preferences. A.1 Why separately chosen stable lotteries cannot simply be mixed Suppose masses 3/53/5 and 2/52/5 of the voters rank a≻ba b and b≻ab a, respectively. The lottery P1=δaP_1= _a is stable for one draw, while P2=(4/5)δa+(1/5)δbP_2=(4/5) _a+(1/5) _b is stable for two draws because Prv[a≻vP22] _v[a _vP_2^2] =35∫01(15+45s)2s+25∫01(45s)2s=13, = 35 _0^1 ( 15+ 45s )^2 \!ds+ 25 _0^1 ( 45s )^2 \!ds= 13, Prv[b≻vP22] _v[b _vP_2^2] =35∫01(15s)2s+25∫01(45+15s)2s=13. = 35 _0^1 ( 15s )^2 \!ds+ 25 _0^1 ( 45+ 15s )^2 \!ds= 13. If D is uniform on 1,2 \1,2 \, their average P=(P1+P2)/2P=(P_1+P_2)/2 satisfies Prv[a≻vP]=51100,Prv[a≻vP2]=33100, _v[a _vP]= 51100, _v[a _vP^2]= 33100, and hence DPrv[a≻vPD]=21/50>5/12=[1/(D+1)] _D _v[a _vP^D]=21/50>5/12= [1/(D+1)]. The cross terms created by drawing repeatedly from P are not controlled by the separate guarantees for P1P_1 and P2P_2. Selecting PDP_D after observing D would satisfy a different averaged statement, not the requirement that one base lottery be chosen before D. A.2 Computing a random-size stable lottery Proposition 2. Suppose D has finite support of size s, whose largest value is dmaxd_ , and let m=|C|⩾2m=|C| 2. For every positive integer N, one can compute a lottery P¯ P satisfying maxc∈CDPrv[c≻vP¯D]⩽[1D+1]+logm2N. _c∈ C _D _v[c _v P^D] [ 1D+1 ]+ m2N. In the real-arithmetic model, the algorithm uses O(Nnmslog(dmax+1))O(Nnms (d_ +1)) arithmetic operations and exponential evaluations. Thus additive error at most ε is obtained in O(nmslog(dmax+1)log(m)/ε2)O(nms (d_ +1) (m)/ ^2) time. Proof. Start with the uniform lottery P1P_1 and set η=8log(m)/Nη= 8 (m)/N. At iteration t, put gt,c=DPrv[c≻vPtD]g_t,c= _D _v[c _vP_t^D] and update Pt+1(c)=Pt(c)exp(ηgt,c)∑b∈CPt(b)exp(ηgt,b).P_t+1(c)= P_t(c) (η g_t,c) _b∈ CP_t(b) (η g_t,b). The standard exponential-weights calculation for numbers in [0,1][0,1] gives maxc∈C1N∑t=1Ngt,c⩽1N∑t=1N∑c∈CPt(c)gt,c+logmηN+η8. _c∈ C 1N _t=1^Ng_t,c 1N _t=1^N _c∈ CP_t(c)g_t,c+ mη N+ η8. The exchangeability identity proved inside Theorem 2 makes the inner sum [1/(D+1)] [1/(D+1)] at every iteration. With the chosen η, the last two terms sum to log(m)/(2N) (m)/(2N). Finally, let P¯=N−1∑t=1NPt P=N^-1 _t=1^NP_t. The convexity established in the same proof gives DPrv[c≻vP¯D]⩽N−1∑tDPrv[c≻vPtD] _D _v[c _v P^D] N^-1 _t _D _v[c _vP_t^D] for every c. It remains to account for the running time. For a voter v and candidate c, let bv,cb_v,c be the PtP_t-mass strictly below c. Because every Pt(c)P_t(c) is positive, integrating over the label of the challenger copy gives gt,c=1n∑v∈V∑d∈supp(D)Pr[D=d](bv,c+Pt(c))d+1−bv,cd+1(d+1)Pt(c).g_t,c= 1n _v∈ V _d (D) [D=d]\, (b_v,c+P_t(c))^d+1-b_v,c^d+1(d+1)P_t(c). For each voter, all values bv,cb_v,c are obtained in one scan of her ranking. Repeated squaring then evaluates the displayed powers in O(nmslog(dmax+1))O(nms (d_ +1)) arithmetic operations per iteration; the multiplicative-weights update costs another O(m)O(m) operations and exponential evaluations. This proves the claimed total. ∎ For an infinite-support distribution, the same iteration guarantee holds provided that the required expectations can be evaluated to sufficient precision, but the running time then depends on the cost of those evaluations. For a deterministic nonempty committee A⊆CA C, the event A≻v(RSLD)DA _v(RSL_D)^D means that voter v’s favorite labeled member of A beats her favorite of the D independent draws. Proposition 3. Every nonempty committee A⊆CA C satisfies DPrv[A≻v(RSLD)D]⩽min1,|A|[1D+1]. _D _v[A _v(RSL_D)^D] \1,|A| [ 1D+1 ] \. Moreover, minP∈Δ(C)max∅≠A⊆CDPrv[A≻vPD]|A|=[1D+1]. _P∈ (C) _ ≠ A C _D _v[A _vP^D]|A|= [ 1D+1 ]. Proof. The event that A defeats (RSLD)D(RSL_D)^D is the union, over c∈Ac∈ A, of the event that the labeled copy of c defeats (RSLD)D(RSL_D)^D. The union bound and Equation 3.1 give the first inequality. For any lottery P, the exchangeability identity in the proof of Theorem 2 gives some candidate c with DPrv[c≻vPD]⩾[1/(D+1)] _D _v[c _vP^D] [1/(D+1)], which proves the matching lower bound for the normalized maximum. ∎ Fix a committee A, expose the voter and the labeled copies in A, and let T∈[0,1]T∈[0,1] be the probability that one draw from RSLDRSL_D lies below the voter’s favorite labeled member of A. Then Prv[A≻v(RSLD)r]=[Tr] _v[A _v(RSL_D)^r]= [T^r] and DPrv[A≻v(RSLD)D]=[ϕ(T)] _D _v[A _v(RSL_D)^D]= [φ(T)]. Because D is positive-integer-valued, ϕφ is continuous and strictly increasing from 00 to 11 on [0,1][0,1], so its inverse ϕ−1:[0,1]→[0,1]φ^-1:[0,1]→[0,1] is well-defined. Lemma 6. Let sA=min1,|A|[1/(D+1)]s_A= \1,|A| [1/(D+1)] \. For an integer r⩾1r 1, define hr,ϕ(u)=(ϕ−1(u))rh_r,φ(u)=(φ^-1(u))^r, and let cavhr,ϕcavh_r,φ be the smallest concave function on [0,1][0,1] lying above hr,ϕh_r,φ. Then Prv[A≻v(RSLD)r]⩽(cavhr,ϕ)(sA). _v[A _v(RSL_D)^r] (cavh_r,φ)(s_A). If D=dD=d deterministically, this bound is sAr/ds_A^r/d for r⩽dr d and sAs_A for r⩾dr d. Proof. By Proposition 3, [ϕ(T)]⩽sA [φ(T)] s_A. The function cavhr,ϕcavh_r,φ is nondecreasing, since it is at most the constant concave upper bound 11 and equals 11 at the right endpoint. Because Tr=hr,ϕ(ϕ(T))T^r=h_r,φ(φ(T)), the definition of the concave upper bound and Jensen’s inequality give [Tr]⩽[(cavhr,ϕ)(ϕ(T))]⩽(cavhr,ϕ)([ϕ(T)])⩽(cavhr,ϕ)(sA). [T^r] [(cavh_r,φ)(φ(T))] (cavh_r,φ)( [φ(T)]) (cavh_r,φ)(s_A). For ϕ(t)=tdφ(t)=t^d, the function ur/du^r/d is concave when r⩽dr d; when r⩾dr d, its smallest concave upper bound on [0,1][0,1] is the line u. ∎ Let B be a lottery, let R be an independent positive integer, and write ψ(t)=[tR]ψ(t)= [t^R]. Theorem 3. Every random-size stable lottery satisfies Prv[BR≻v(RSLD)D]⩽1−ψ(1−[1D+1]). _v[B^R _v(RSL_D)^D] 1-ψ (1- [ 1D+1 ] ). For deterministic R=rR=r, the bound becomes 1−(1−[1/(D+1)])r1-(1- [1/(D+1)])^r. Finally, random-size stable lotteries can be approximated in support, although the resulting additive error is too coarse for the main distortion proof. Let d¯=[D]=ϕ′(1) d= [D]=φ (1). Proposition 4. For every integer s⩾1s 1, there is a lottery P P supported on at most s candidates such that DPrv[c≻vP^D]⩽[1D+1]+d¯π2sfor every c∈C. _D _v[c _v P^D] [ 1D+1 ]+ d π2s every c∈ C. We now prove the last two statements and then record an extension to signed coefficients. The signed extension is mathematically useful but does not describe a random value of D unless the coefficients are nonnegative and sum to one. A.3 A calculation with cumulative distributions Draw a uniformly random voter v and order labeled candidates from worst to best according to v. For lotteries A and P, let FA,vF_A,v and FP,vF_P,v be their cumulative distribution functions in this order. Draw a labeled outcome ω from A and put U=FP,v(ω),Y=FA,v(ω).U=F_P,v(ω), Y=F_A,v(ω). Conditional on v, Y is uniform on [0,1][0,1]. For every integer d⩾1d 1, Prv[A≻vPd]=[Ud],Prv[Ad≻vP]=d[UYd−1]. _v[A _vP^d]= [U^d], _v[A^d _vP]=d [UY^d-1]. (A.1) The first identity conditions on the draw from A. For the second, the best of d independent A-draws has density dFA,vd−1dFA,vdF_A,v^d-1 \!dF_A,v. Summing Equation A.1 over the distribution of D gives the formulas used in Lemma 7: DPrv[A≻vPD]=[ϕ(U)],DPrv[AD≻vP]=[Uϕ′(Y)]. _D _v[A _vP^D]= [φ(U)], _D _v[A^D _vP]= [Uφ (Y)]. Lemma 7. For finitely supported D, define ϕ(u,v)=ϕ(u)−ϕ(v)−ϕ′(v)(u−v).D_φ(u,v)=φ(u)-φ(v)-φ (v)(u-v). Then DPrv[AD≻vP]=DPrv[A≻vPD]+1−2[1D+1]−[ϕ(U,Y)]. _D _v[A^D _vP]= _D _v[A _vP^D]+1-2 [ 1D+1 ]- [D_φ(U,Y)]. Consequently, DPrv[A≻vPD]⩽[1/(D+1)] _D _v[A _vP^D] [1/(D+1)] implies DPrv[AD≻vP]⩽1−[1/(D+1)] _D _v[A^D _vP] 1- [1/(D+1)]. The probability inequality extends to arbitrary D by truncation. Proof. Convexity gives ϕ⩾0D_φ 0, and rearranging its definition gives Uϕ′(Y)=ϕ(U)−ϕ(U,Y)+Yϕ′(Y)−ϕ(Y).Uφ (Y)=φ(U)-D_φ(U,Y)+Yφ (Y)-φ(Y). Because Y is uniform conditional on every voter, [Yϕ′(Y)−ϕ(Y)]=∫01(tϕ′(t)−ϕ(t))dt=1−2∫01ϕ(t)dt=1−2[1D+1]. [Yφ (Y)-φ(Y)]= _0^1(tφ (t)-φ(t)) \!dt=1-2 _0^1φ(t) \!dt=1-2 [ 1D+1 ]. Substitution into the two preceding cumulative-distribution formulas proves the identity, and discarding the nonnegative term proves the consequence. Equality holds when A=PA=P by exchangeability. ∎ A.4 Several draws from another lottery For this proof, abbreviate pD=[1/(D+1)]p_D= [1/(D+1)]. Draw a labeled ω from B. The best of R draws from B has density ψ′(FB,v(ω))ψ (F_B,v(ω)) with respect to a draw from B. Conditional on this best draw, all D draws from RSLDRSL_D lie below it with probability ϕ(FRSLD,v(ω))φ(F_RSL_D,v(ω)). With U=FRSLD,v(ω)U=F_RSL_D,v(ω) and Y=FB,v(ω)Y=F_B,v(ω), therefore, Prv[BR≻v(RSLD)D]=[ϕ(U)ψ′(Y)]. _v[B^R _v(RSL_D)^D]= [φ(U)ψ (Y)]. (A.2) By linearity of Equation 3.1 in the candidate drawn from B, [ϕ(U)]=DPrv[B≻v(RSLD)D]⩽pD. [φ(U)]= _D _v[B _v(RSL_D)^D] p_D. Also 0⩽ϕ(U)⩽10 φ(U) 1, and Y is uniform on [0,1][0,1]. The function ψ′ψ is nondecreasing. We claim that for every random pair (Z,Y)(Z,Y) with 0⩽Z⩽10 Z 1, Z⩽pD Z p_D, and uniform marginal Y, [Zψ′(Y)]⩽∫1−pD1ψ′(t)dt. [Zψ (Y)] _1-p_D^1ψ (t) \!dt. (A.3) To prove this directly, put λ=ψ′(1−pD)λ=ψ (1-p_D). Pointwise, Z(ψ′(Y)−λ)⩽(ψ′(Y)−λ)+.Z(ψ (Y)-λ) (ψ (Y)-λ)_+. Taking expectations and using Z⩽pD Z p_D gives [Zψ′(Y)]⩽λpD+∫01(ψ′(t)−λ)+dt=∫1−pD1ψ′(t)dt, [Zψ (Y)] λ p_D+ _0^1(ψ (t)-λ)_+ \!dt= _1-p_D^1ψ (t) \!dt, where a flat portion at the threshold does not affect the equality. Applying Equation A.3 to Z=ϕ(U)Z=φ(U) in Equation A.2 yields Prv[BR≻v(RSLD)D]⩽∫1−pD1ψ′(t)dt=1−ψ(1−pD). _v[B^R _v(RSL_D)^D] _1-p_D^1ψ (t) \!dt=1-ψ(1-p_D). For deterministic R=rR=r, substitute ψ(t)=trψ(t)=t^r. A.5 Approximating by a lottery with small support Draw s candidates independently from RSLDRSL_D, and let P P be their empirical distribution. Fix a voter. Place the candidates in this voter’s order and linearly interpolate across the interval corresponding to each candidate; this interpolation is exactly the proportional label convention. Let F and F F be the resulting cumulative distribution functions for RSLDRSL_D and P P. The sharp Dvoretzky–Kiefer–Wolfowitz inequality [34] gives Pr[supt|F^(t)−F(t)|>ε]⩽2e−2sε2. [ _t| F(t)-F(t)|> ] 2e^-2s ^2. Integrating the tail bound gives [supt|F^(t)−F(t)|]⩽∫0∞2e−2sε2ε=π2s. [ _t| F(t)-F(t)| ] _0^∞2e^-2s ^2 \!d = π2s. (A.4) The same sampled candidates are used for every voter; Equation A.4 is applied separately and then averaged over voters. Because ϕ′(t)⩽ϕ′(1)=d¯φ (t) φ (1)= d on [0,1][0,1], the function ϕφ is d¯ d-Lipschitz. For any pure candidate c, the probability that c defeats the empirical committee differs from the corresponding probability under RSLDRSL_D by at most d¯supt|F^(t)−F(t)| d _t| F(t)-F(t)| for that voter. Therefore P^[maxc∈C(DPrv[c≻vP^D]−DPrv[c≻v(RSLD)D])]⩽d¯π2s. _ P [ _c∈ C ( _D _v[c _v P^D]- _D _v[c _v(RSL_D)^D] ) ] d π2s. The maximum causes no factor depending on |C||C|: for each voter, the same uniform error in the cumulative distributions controls every candidate position. Since DPrv[c≻v(RSLD)D]⩽[1/(D+1)] _D _v[c _v(RSL_D)^D] [1/(D+1)] for every c, some realization of the sample satisfies DPrv[c≻vP^D]⩽[1D+1]+d¯π2s _D _v[c _v P^D] [ 1D+1 ]+ d π2s simultaneously for all candidates. Its empirical distribution has support at most s. A.6 An extension to signed coefficients Theorem 4. Let (ad)d⩾1(a_d)_d 1 be an absolutely summable sequence of real numbers, define f(t)=∑d⩾1adtd,f(t)= _d 1a_dt^d, and let pf=∫01f(t)tp_f= _0^1f(t) \!dt. Every finite profile admits a lottery P such that ∑d⩾1adPrv[c≻vPd]⩽∫01f(t)dt _d 1a_d _v[c _vP^d] _0^1f(t) \!dt for every candidate c. The threshold is exact: for every lottery P, the maximum of the left-hand side over candidates is at least ∫01f(t)t _0^1f(t) \!dt. Proof. Within this proof, write Gc(P)G_c(P) for the left-hand side. Since pf=∑d⩾1ad/(d+1)p_f= _d 1a_d/(d+1), absolute summability gives uniform convergence of the defining series on [0,1][0,1], hence continuity of every GcG_c. The exchangeability argument in the proof of Theorem 2 is linear in the coefficients and gives ∑cP(c)Gc(P)=pf. _cP(c)G_c(P)=p_f. For a lottery P, let M(P)=argmaxc∈CGc(P)M(P)= *arg\,max_c∈ CG_c(P), and let B(P)B(P) be the set of lotteries supported on M(P)M(P). Each B(P)B(P) is nonempty, convex, and compact. Continuity of the functions GcG_c implies that the correspondence B has a closed graph. Kakutani’s fixed-point theorem therefore gives a lottery P with P∈B(P)P∈ B(P). Every candidate in the support of this lottery maximizes Gc(P)G_c(P), so the displayed identity gives maxcGc(P)=∑cP(c)Gc(P)=pf. _cG_c(P)= _cP(c)G_c(P)=p_f. For every lottery, the maximum of the numbers Gc(P)G_c(P) is at least their P-weighted average pfp_f, which proves the converse. ∎ Signed coefficients do not define probabilities and need not make the weighted comparison function convex in P, so the minimax proof of Theorem 2 does not apply. They also do not imply the union bound or the consequence of Lemma 7 used in Proposition 3. We use nonnegative coefficients summing to one everywhere in the distortion results. Appendix B Exact Verification and Numerical Discovery of the Distortion Bound This appendix first gives the construction of Dual omitted from the main body, states the 4949 exact dual families, and then proves Lemma 5 from these data and the rule and target in Section 5. It gives a uniform, labeled description of every polynomial inequality checked by the program, explains the exact method used to prove those inequalities on continuous domains, and verifies that at least one of the candidate bounds applies at every relevant (q,x)(q,x). Only afterward do we describe how finite restrictions of Primal and Dual suggested the support and masses of D⋆D , the target coefficients a and b, and the three constructions that produce the dual families. The search is numerical evidence; the proof uses the original programs from Lemmas 3 and 4 and exact rational arithmetic. B.1 Construction of Dual Fix D, q, and x as in Lemma 4. Give the two moment constraints of Primal nonnegative multipliers λ and μ, while retaining the requirements η∈Δ([0,1]2)η∈ ([0,1]^2) and ξ∈Δ([0,1])ξ∈ ([0,1]). The resulting Lagrangian is ℒ(η,ξ,λ,μ)= (η,ξ;λ,μ)=\; λp+μRx λ p+μ R_x +(1−q)∫[0,1]2(b0−λWx(y)−μGx(b0,y))dη(b0,y) +(1-q) _[0,1]^2 (b_0-λ W_x(y)-μ G_x(b_0,y) ) \!dη(b_0,y) +q∫[0,1](b1−λwx(b1)−μFx(b1))dξ(b1). +q _[0,1] (b_1-λ w_x(b_1)-μ F_x(b_1) ) \!dξ(b_1). For every continuous function h on a compact set S, supν∈Δ(S)∫Shν=maxs∈Sh(s), _ν∈ (S) _Sh \!dν= _s∈ Sh(s), because an average cannot exceed the pointwise maximum and a point mass at a maximizer attains it. Thus, for fixed λ and μ, maximizing the Lagrangian over η and ξ replaces its two integrals by the corresponding pointwise maxima. Introducing u and v as upper bounds on these maxima gives u u ⩾b0−λWx(y)−μGx(b0,y) b_0-λ W_x(y)-μ G_x(b_0,y) for every (b0,y)∈[0,1]2, every (b_0,y)∈[0,1]^2, v v ⩾b1−λwx(b1)−μFx(b1) b_1-λ w_x(b_1)-μ F_x(b_1) for every b1∈[0,1]. every b_1∈[0,1]. Minimizing λp+μRx+(1−q)u+qvλ p+μ R_x+(1-q)u+qv subject to these inequalities and λ,μ⩾0λ,μ 0 is exactly Dual. Equivalently, the pair (η,ξ)(η,ξ) can be represented by one measure on the compact disjoint union [0,1]2⊔[0,1][0,1]^2 [0,1], with moment constraints fixing the mass of each component. The objective and all moment functions are continuous, so generalized-moment duality implies that the primal and dual optimal values coincide whenever Primal is feasible [40, Corollary 3.1]. Weak duality, which is all that Lemma 4 uses, also follows immediately by integrating the two pointwise dual inequalities against η and ξ and applying the two moment constraints of Primal. B.2 Exact Dual Families and Candidate Bounds Throughout this subsection and the two verification subsections that follow, set f=ϕD⋆f= _D , p=pD⋆p=p_D , and r=1−xr=1-x; all the functions from Equations 4.1 and 4.2 use this f. Table 3: The 4949 dual families Dual families 1 and 2. Put Ax=Gx(1,0)A_x=G_x(1,0), y1=80529/100000y_1=80529/100000, and y2=1y_2=1. For 0<x<10<x<1 and each j∈1,2j∈ \1,2 \, let j=(λj,μj,uj,vj)z_j=( _j, _j,u_j,v_j), where Δj(x)=(f(x)−Wx(yj))∂yGx(0,yj)−(Ax−Gx(0,yj))Wx′(yj) _j(x)= (f(x)-W_x(y_j) ) _yG_x(0,y_j)- (A_x-G_x(0,y_j) )W_x (y_j) and λj=∂yGx(0,yj)Δj(x),μj=−Wx′(yj)Δj(x),uj=−λjWx(yj)−μjGx(0,yj),vj=0. _j= _yG_x(0,y_j) _j(x), 18.49988pt _j=- W_x (y_j) _j(x), 18.49988ptu_j=- _jW_x(y_j)- _jG_x(0,y_j), 18.49988ptv_j=0. Dual family 3. Let Ψ(s)=∫0sf(t)t (s)= _0^sf(t) \!dt and Lx=p−Ψ(x)−Ψ(r)−xf(r)L_x=p- (x)- (r)-xf(r). For 0<x<10<x<1, let 3=(λ3,μ3,u3,v3)z_3=( _3, _3,u_3,v_3), where λ3=Lxxf(r)(1−f(x)),μ3=rf(r),u3=−λ3,v3=0. _3= L_xxf(r)(1-f(x)), 18.49988pt _3= rf(r), 18.49988ptu_3=- _3, 18.49988ptv_3=0. Dual families 4–49. For each j∈4,5,…,49j∈ \4,5,…,49 \, put τj=(j+11)/100 _j=(j+11)/100, Sj(x)=λ3xf′(xτj)+μ3Fx′(τj)S_j(x)= _3xf (x _j)+ _3F_x ( _j), and θj(x)=1/Sj(x) _j(x)=1/S_j(x). For 0<x<10<x<1, let j=(λj,μj,uj,vj)z_j=( _j, _j,u_j,v_j), where λj _j =θjλ3, = _j _3, μj _j =θjμ3, = _j _3, uj u_j =(1−θj)+θju3, =(1- _j)+ _ju_3, vj v_j =τj−λjf(xτj)−μjFx(τj). = _j- _jf(x _j)- _jF_x( _j). At x=1x=1, define j=(λj,μj,uj,vj)z_j=( _j, _j,u_j,v_j) by its continuous limit, where λj=1f′(τj),μj=0,uj=1−1f′(τj),vj=τj−f(τj)f′(τj). _j= 1f ( _j), 18.49988pt _j=0, 18.49988ptu_j=1- 1f ( _j), 18.49988ptv_j= _j- f( _j)f ( _j). Table 4: Candidate bounds for the exact verification For any dual tuple =(λ,μ,u,v)z=(λ,μ,u,v), write U(q,x,)=x(λp+μRx+(1−q)u+qv).U(q,x;z)=x (λ p+μ R_x+(1-q)u+qv ). The verification considers the following 5050 candidate bounds. A dual bound may be used only on the stated range of x, on which Section B.3 proves that its tuple is feasible for Dual. Candidate Required bound Eligible x (C3) (1−p)x⩽T(q)(1-p)x T(q) [0,1][0,1] 1z_1 U(q,x,1)⩽T(q)U(q,x;z_1) T(q) (0,1)(0,1) 2z_2 U(q,x,2)⩽T(q)U(q,x;z_2) T(q) [1/5,1)[1/5,1) 3z_3 U(q,x,3)⩽T(q)U(q,x;z_3) T(q) (0,1)(0,1) jz_j, 4⩽j⩽494 j 49 U(q,x,j)⩽T(q)U(q,x;z_j) T(q) (0,1](0,1] Primal infeasibility and endpoints. At x=0x=0, the unnormalized loss is zero. At x=1x=1, the first constraint of Primal(D⋆,q,1) Primal(D ,q,1) has left-hand side at least 1−q1-q. Consequently, this primal is infeasible whenever q<1−p=135516253182000000.q<1-p= 135516253182000000. It therefore remains to verify that at least one candidate in Section B.2 applies for every (q,x)∈[0,1]×(0,1)(q,x)∈[0,1]×(0,1) and for x=1x=1 when q∈[1−p,1]q∈[1-p,1]. On the latter boundary, only the (C3) bound and the tuples 4,…,49z_4,…,z_49 are needed; the displayed limits in Section B.2 define those tuples at x=1x=1. B.3 Exact Polynomials for Dual Feasibility If f(t)=∑dadtdf(t)= _da_dt^d, the binomial theorem rewrites the normalized functions from Equation 4.2 as the following polynomials: Fx(b1) F_x(b_1) =∑dad∑k=1d(dk)xk−1rd−kd−k+1b1k, = _da_d _k=1^d dk x^k-1r^d-kd-k+1b_1^k, (B.1) Gx(b0,y) G_x(b_0,y) =∑dad∑k=1d(dk)xk−1rd−kd−k+1(b0kyd−k+1+1−yd−k+1), = _da_d _k=1^d dk x^k-1r^d-kd-k+1 (b_0^ky^d-k+1+1-y^d-k+1 ), (B.2) Rx R_x =∑dadd+1∑j=0d−1rj. = _d a_dd+1 _j=0^d-1r^j. (B.3) These identities agree with Equation 4.2 for x>0x>0 and give their continuous extensions at x=0x=0. They also show directly that every expression used below is a rational function with rational coefficients. We use one uniform convention to describe the polynomials checked by the program without expanding their large integer coefficients. Let R be any rational expression below and let X be its stated domain. After substituting f and Equations B.1, B.2 and B.3, write R=N/QR=N/Q in lowest terms with coprime integer polynomials and choose the common sign so that Q is positive on the relative interior of X. We write num(R)=Nnum_X(R)=N; multiplying N and Q by the same positive integer does not change any sign claim. Whenever an exact factor is displayed beneath num(R)num_X(R), polynomial division by that factor is exact. This convention gives a short but complete implicit specification of every polynomial. Dual families 1 and 2. Let x¯1=0 x_1=0 and x¯2=1/5 x_2=1/5, and define j=[x¯j,1]×[0,1]X_j=[ x_j,1]×[0,1] in the variables (x,y)(x,y). For j∈1,2j∈ \1,2 \, let Δj _j and jz_j be as in Section B.2. Put Ij,0(x,y) I_j,0(x,y) =uj+λjWx(y)+μjGx(0,y), =u_j+ _jW_x(y)+ _jG_x(0,y), Ij,1(x,y) I_j,1(x,y) =Ij,0(x,y)+μjf(ry)r−1. =I_j,0(x,y)+ _j f(ry)r-1. The six polynomial families used for these tuples are H1,jfeas(x) H^feas_1,j(x) =−Δj(x)x(1−x)2, =- _j(x)x(1-x)^2, H2,jfeas(x) H^feas_2,j(x) =−∂yGx(0,yj), =- _yG_x(0,y_j), H3,jfeas(x) H^feas_3,j(x) =Wx′(yj), =W_x (y_j), H4,jfeas(x) H^feas_4,j(x) =num[x¯j,1](λja1x+μjf(r)r−1), =num_[ x_j,1] ( _ja_1x+ _j f(r)r-1 ), H5,jfeas(x,y) H^feas_5,j(x,y) =numj(Ij,0)(y−yj)2, = num_X_j(I_j,0)(y-y_j)^2, H6,jfeas(x,y) H^feas_6,j(x,y) =numj(Ij,1)y, = num_X_j(I_j,1)y, where a1=423239/106a_1=423239/10^6. The factors x(1−x)2x(1-x)^2, (y−yj)2(y-y_j)^2, and y divide the corresponding numerators exactly. The program proves H1,jfeas>0H^feas_1,j>0 on the relative interior of its interval and proves Hi,jfeas⩾0H^feas_i,j 0 on the stated domain for i=2,…,6i=2,…,6. These signs imply that λj,μj⩾0 _j, _j 0. To verify the first pointwise dual inequality, convexity of Gx(⋅,y)G_x(·,y) gives, for r>0r>0, Gx(b0,y)⩾Gx(0,y)+b0f(ry)r.G_x(b_0,y) G_x(0,y)+b_0 f(ry)r. (B.4) The resulting lower bound is affine in b0b_0, and the signs of H5,jfeasH^feas_5,j and H6,jfeasH^feas_6,j verify its values at b0=0b_0=0 and b0=1b_0=1. For the second pointwise inequality, the difference vj+λjf(xb1)+μjFx(b1)−b1v_j+ _jf(xb_1)+ _jF_x(b_1)-b_1 is convex in b1b_1, vanishes at b1=0b_1=0, and has nonnegative derivative there by H4,jfeas⩾0H^feas_4,j 0. Hence both pointwise inequalities hold throughout the domains on which these tuples are used. Dual family 3. Recall Ψ(s)=∫0sf(t)t (s)= _0^sf(t) \!dt and Lx=p−Ψ(x)−Ψ(r)−xf(r)L_x=p- (x)- (r)-xf(r). Define I3,0(x,y) I_3,0(x,y) =μ3Gx(0,y)−λ3(1−Wx(y)), = _3G_x(0,y)- _3(1-W_x(y)), I3,1(x,y) I_3,1(x,y) =I3,0(x,y)+μ3f(ry)r−1. =I_3,0(x,y)+ _3 f(ry)r-1. The three polynomials are H1,3feas(x)=Lxx(1−x),H2,3feas(x,y)=num[0,1]2(I3,0)1−y,H3,3feas(x,y)=num[0,1]2(I3,1)y(1−y).H^feas_1,3(x)= L_xx(1-x), H^feas_2,3(x,y)= num_[0,1]^2(I_3,0)1-y, H^feas_3,3(x,y)= num_[0,1]^2(I_3,1)y(1-y). All displayed divisions are exact. The program proves H1,3feas⩾0H^feas_1,3 0 on [0,1][0,1] and H2,3feas,H3,3feas⩾0H^feas_2,3,H^feas_3,3 0 on [0,1]2[0,1]^2. Thus λ3⩾0 _3 0 and μ3>0 _3>0, and Equation B.4 again reduces the first pointwise inequality to the two endpoint checks. The second pointwise difference is convex, vanishes at b1=0b_1=0, and has nonnegative derivative there because μ3f(r)/r=1 _3f(r)/r=1 and λ3⩾0 _3 0. Hence this tuple is feasible for every 0<x<10<x<1. Dual families 4–49. For j∈4,5,…,49j∈ \4,5,…,49 \, define Zj(x)=Lxf′(xτj)+(1−f(x))(f(r+xτj)−f(xτj)).Z_j(x)=L_xf (x _j)+(1-f(x)) (f(r+x _j)-f(x _j) ). The two polynomial families are H1,jfeas(x)=Zj(x)1−x,H2,jfeas(x)=Zj(x)−(1−f(x))f(1−x)x(1−x).H^feas_1,j(x)= Z_j(x)1-x, H^feas_2,j(x)= Z_j(x)-(1-f(x))f(1-x)x(1-x). The divisions are exact, and the program proves H1,jfeas>0H^feas_1,j>0 and H2,jfeas⩾0H^feas_2,j 0 on [0,1][0,1] for every j∈4,5,…,49j∈ \4,5,…,49 \. These signs imply Sj(x)⩾1S_j(x) 1, so 0<θj(x)⩽10< _j(x) 1. The first pointwise inequality for jz_j is therefore a convex combination of the inequality 1⩾b01 b_0 and the first inequality for 3z_3. The second pointwise difference is convex in b1b_1, equals zero at b1=τjb_1= _j, and has derivative θjSj−1=0 _jS_j-1=0 there. It is consequently nonnegative on [0,1][0,1]. At x=1x=1, the limiting tuple in Section B.2 is feasible because its first inequality is 1⩾b01 b_0 and its second is the tangent-line inequality for the convex polynomial f. B.4 Polynomial Verification and Proof of Lemma 5 We now describe the exact outer polynomials and the method used to prove that at least one of the candidate bounds in Section B.2 applies at every relevant (q,x)(q,x). Recall that U(q,x,)U(q,x;z) is the unnormalized objective of a dual tuple z. Define the following polynomial gaps: H0out(q,x) H^out_0(q,x) =T(q)−(1−p)x, =T(q)-(1-p)x, Hjout(q,x) H^out_j(q,x) =−Δj(x)x(T(q)−U(q,x,j)) =- _j(x)x (T(q)-U(q,x;z_j) ) for j∈1,2, j∈ \1,2 \, H3out(q,x) H^out_3(q,x) =f(1−x)(1−f(x))(T(q)−U(q,x,3)), =f(1-x)(1-f(x)) (T(q)-U(q,x;z_3) ), Hjout(q,x) H^out_j(q,x) =Zj(x)1−x(T(q)−U(q,x,j)) = Z_j(x)1-x (T(q)-U(q,x;z_j) ) for j∈4,5,…,49. j∈ \4,5,…,49 \. After substitution, every right-hand side is a polynomial in (q,x)(q,x) with rational coefficients; the factors shown are precisely positive common denominators on the relative interiors where the corresponding tuples are used, and the divisions by x and 1−x1-x are exact polynomial divisions. Thus nonnegativity of an outer polynomial proves that its associated upper bound is at most T(q)T(q). We use the algorithm of [20] to prove polynomial nonnegativity on rational boxes. Map a box [q0,q1]×[x0,x1][q_0,q_1]×[x_0,x_1] affinely to (s,t)∈[0,1]2(s,t)∈[0,1]^2. If H has bidegree at most (m,n)(m,n), write it in the tensor-product Bernstein basis as H(s,t)=∑i=0m∑j=0ncij(mi)si(1−s)m−i(nj)tj(1−t)n−j.H(s,t)= _i=0^m _j=0^nc_ij mis^i(1-s)^m-i njt^j(1-t)^n-j. Every basis function is nonnegative, and their sum is one. Therefore H(s,t)H(s,t) is a convex combination of the coefficients cijc_ij and mini,jcij⩽H(s,t)⩽maxi,jcij. _i,jc_ij H(s,t) _i,jc_ij. In particular, nonnegative coefficients prove H⩾0H 0 throughout the box. The program computes these coefficients using exact rational arithmetic. For a finite disjunction of polynomial inequalities, we apply the same Garloff test to every eligible polynomial on each current rational box. If one candidate has only nonnegative coefficients, that inequality holds throughout the box, which becomes an accepted subdivision. If no candidate succeeds, the program divides the box at rational midpoints and repeats the test on the resulting boxes. This procedure is not guaranteed to terminate: the Bernstein-coefficient test is sufficient but not necessary, and a true pointwise disjunction need not initially have one member that holds throughout a large box. Whenever the procedure does terminate, however, the accepted subdivisions form a finite cover and give a sound proof of the disjunction. It terminates for the polynomials considered here, and no floating-point arithmetic enters any check. Specifically, for every (q,x)∈[0,1]×(0,1)(q,x)∈[0,1]×(0,1), the program verifies the disjunction H0out(q,x) H^out_0(q,x) ⩾0∨H1out(q,x)⩾0∨(x⩾15∧H2out(q,x)⩾0)∨⋁j=349Hjout(q,x)⩾0. 0 H^out_1(q,x) 0 (x 15\ \ H^out_2(q,x) 0 ) _j=3^49H^out_j(q,x) 0. For x=1x=1 and q∈[1−p,1]q∈[1-p,1], it verifies H0out(q,1)⩾0∨⋁j=449Hjout(q,1)⩾0.H^out_0(q,1) 0 _j=4^49H^out_j(q,1) 0. The condition x⩾1/5x 1/5 in the first disjunction is a precondition for using 2z_2, not another candidate bound: a subdivision may be accepted using H2outH^out_2 only if it lies entirely in x⩾1/5x 1/5. At q=0q=0, the target is T(0)=0T(0)=0, and the program never divides by q. Proof of Lemma 5. Fix q∈[0,1]q∈[0,1] and an x∈[0,1]x∈[0,1] for which Primal(D⋆,q,x) Primal(D ,q,x) is feasible. If x=0x=0, the unnormalized loss is zero and hence at most T(q)T(q), so suppose x>0x>0. If x=1x=1, primal feasibility implies q⩾1−pq 1-p by the argument following Section B.2. Thus one of the two verified disjunctions applies. If H0out(q,x)⩾0H^out_0(q,x) 0, then (1−p)x⩽T(q)(1-p)x T(q). Otherwise, one of the eligible outer polynomials is nonnegative, and its associated dual tuple jz_j is feasible by Section B.3 and satisfies U(q,x,j)⩽T(q)U(q,x;z_j) T(q). Hence the sufficient condition in Lemma 4 holds, and gD⋆(q)⩽T(q)=q(3320542059−794142059q)g_D (q) T(q)=q ( 3320542059- 794142059q ) for every q∈[0,1]q∈[0,1]. The loss bound follows from Lemma 2. ∎ B.5 Discretized Programs Used in the Search The exact programs in Lemmas 3 and 4 are not finite LPs. For the numerical search, fix arbitrary nonempty finite sets E⊆[0,1]2E [0,1]^2 and E1⊆[0,1]E_1 [0,1], and restrict η and ξ to these sets. The resulting discretized primal is maxη,ξ⩾0 _η,ξ 0 (1−q)∑(b0,y)∈Eb0η(b0,y)+q∑b1∈E1b1ξ(b1) (1-q) _(b_0,y)∈ Eb_0η(b_0,y)+q _b_1∈ E_1b_1ξ(b_1) subject to to (1−q)∑(b0,y)∈EWx(y)η(b0,y)+q∑b1∈E1wx(b1)ξ(b1) (1-q) _(b_0,y)∈ EW_x(y)η(b_0,y)+q _b_1∈ E_1w_x(b_1)ξ(b_1) ⩽p, p, (1−q)∑(b0,y)∈EGx(b0,y)η(b0,y)+q∑b1∈E1Fx(b1)ξ(b1) (1-q) _(b_0,y)∈ EG_x(b_0,y)η(b_0,y)+q _b_1∈ E_1F_x(b_1)ξ(b_1) ⩽Rx, R_x, ∑(b0,y)∈Eη(b0,y)=1,∑b1∈E1ξ(b1)=1. _(b_0,y)∈ Eη(b_0,y)=1, _b_1∈ E_1ξ(b_1)=1. Here η(b0,y)η(b_0,y) and ξ(b1)ξ(b_1) are probability masses, not densities. Its ordinary finite LP dual is minλ,μ⩾0u,v∈ℝ _ subarraycλ,μ 0\\ u,v subarray λp+μRx+(1−q)u+qv λ p+μ R_x+(1-q)u+qv subject to to u+λWx(y)+μGx(b0,y) u+λ W_x(y)+μ G_x(b_0,y) ⩾b0 b_0 for every (b0,y)∈E, every (b_0,y)∈ E, v+λwx(b1)+μFx(b1) v+λ w_x(b_1)+μ F_x(b_1) ⩾b1 b_1 for every b1∈E1. every b_1∈ E_1. Thus the dual of the discretized primal is precisely what results from imposing the exact dual inequalities only on the finite sets. Finite LP duality equates the two discretized values. Restricting the measures can only decrease the primal optimum, while omitting pointwise dual constraints can only decrease the dual optimum; therefore this common value generally underestimates the exact value. A tuple returned by the discretized dual does not upper bound the original program unless its inequalities are subsequently proved for every (b0,y)∈[0,1]2(b_0,y)∈[0,1]^2 and every b1∈[0,1]b_1∈[0,1]. B.6 Numerical Search and Rationalization None of the calculations in this subsection is used in the proof of Lemma 5. They explain only how we found the exact data later verified in Section B.4. Fixed (D,q,x)(D,q,x). Start with finite sets E and E1E_1, solve the discretized dual, and let (λ,μ,u,v)(λ,μ,u,v) be the returned tuple. We then numerically search for the largest violation of each of its two types of constraint: δ0 _0 =max(b0,y)∈[0,1]2b0−u−λWx(y)−μGx(b0,y), = _(b_0,y)∈[0,1]^2 \b_0-u-λ W_x(y)-μ G_x(b_0,y) \, δ1 _1 =maxb1∈[0,1]b1−v−λwx(b1)−μFx(b1). = _b_1∈[0,1] \b_1-v-λ w_x(b_1)-μ F_x(b_1) \. When the numerical search finds a positive value, we add a corresponding point to E or E1E_1 and solve the finite dual again. This is dual constraint generation; from the discretized primal viewpoint, the same step adds a possible point at which a measure may place mass. The two maximizations are nonlinear optimization problems, and the implementation uses SciPy’s differential_evolution. Failure of this heuristic to find a violation is not a proof of dual feasibility. Numerical LP tolerances can also leave a returned tuple slightly infeasible. By contrast, a genuinely feasible but suboptimal solution of the minimization dual would be completely safe: it would merely give a weaker upper bound. Finite sets of q and x. The preceding computation was repeated on finite sets of q- and x-values. Let L^D(q,x) L_D(q,x) denote the numerical objective value returned for a searched pair. For each searched q, we formed g^D(q)=maxx in the search setminxL^D(q,x),(1−p)x. g_D(q)= _x in the search set \x L_D(q,x),(1-p)x \. This is an estimate, not an upper bound on gD(q)g_D(q). A second finite LP chose weights α,β,γ⩾0α,β,γ 0 on Integrated Veto, maximal lottery, and the random-size stable lottery by solving minα,β,γ,Ccut _α,β,γ,C_cut Ccut C_cut subject to to αqi2+βminqi,1/2+γg^D(qi) α q_i^2+β \q_i,1/2 \+γ g_D(q_i) ⩽Ccutqi C_cutq_i for every searched qi, every searched q_i, α+β+γ=1,α,β,γ,Ccut⩾0. α+β+γ=1, α,β,γ,C_cut 0. The implementation also included the analytically derived endpoint constraints β+γΛD⩽Ccutβ+γ _D C_cut and α+β/2+γρD⩽Ccutα+β/2+γ _D C_cut, where ΛD _D is the numerically evaluated q↓0q 0 limit and ρD _D solves f(ρD)=pf( _D)=p. The best candidate found had β=0β=0. In that case, the remaining constraints have the form g^D(qi)⩽qi(Ccutγ−αγqi), g_D(q_i) q_i ( C_cutγ- αγq_i ), which suggests a=Ccut/γa=C_cut/γ and b=α/γb=α/γ. The draw distribution and target. For a selected finite support S of positive integer degrees, we wrote f(t)=∑d∈Sadtdf(t)= _d∈ Sa_dt^d, parameterized the masses ad>0a_d>0 by unconstrained log ratios followed by normalization, and optimized those real parameters using differential_evolution. Thus the degrees were selected discretely, but the probability masses were optimized continuously; there was no grid over the probability simplex. The search tested many supports containing degree 11, including supports of three and four degrees, perturbed promising supports by adding or moving mass to other degrees, and reoptimized the outer LP. It also constructed sparse feasible measures for the discretized primal. Such measures give lower bounds on the true loss and can expose an erroneously low value caused by a violated dual constraint; they never prove an upper bound. The search was not exhaustive and does not prove that D⋆D is optimal among draw distributions. From numerical dual solutions to explicit tuples. At each searched pair (q,x)(q,x), the finite dual returned numerical values of (λ,μ,u,v)(λ,μ,u,v) and indicated which pointwise inequalities were nearly tight. In the small-q regime, the observed pattern was that the first pointwise inequality was tight at (b0,y)=(0,y∘)(b_0,y)=(0,y_ ) and (1,0)(1,0) and stationary in y at (0,y∘)(0,y_ ), while v=0v=0. For fixed x and y∘y_ , these conditions are u+λWx(y∘)+μGx(0,y∘) u+λ W_x(y_ )+μ G_x(0,y_ ) =0, =0, λWx′(y∘)+μ∂yGx(0,y∘) λ W_x (y_ )+μ _yG_x(0,y_ ) =0, =0, u+λf(x)+μAx u+λ f(x)+μ A_x =1. =1. Solving these three linear equations with y∘=80529/100000y_ =80529/100000 and y∘=1y_ =1 gives 1z_1 and 2z_2, respectively. The first rational value was suggested by the numerical active point, which was approximately 0.80529050.8052905. Near the middle numerical peak, the active pattern instead suggested that the first pointwise inequality should be tight at (0,1)(0,1), tangent in b0b_0 there, and tight at (1,0)(1,0), again with v=0v=0. Since Wx(1)=1W_x(1)=1, Gx(0,1)=0G_x(0,1)=0, and ∂b0Gx(0,1)=f(r)/r _b_0G_x(0,1)=f(r)/r, these conditions are u+λ=0,μf(r)r=1,u+λf(x)+μAx=1,v=0.u+λ=0, μ f(r)r=1, u+λ f(x)+μ A_x=1, v=0. Their solution is 3z_3; in particular, μ3=r/f(r) _3=r/f(r) and λ3=(μ3Ax−1)/(1−f(x)) _3=( _3A_x-1)/(1-f(x)), which is algebraically identical to the formula using LxL_x in Section B.2. For larger q, the numerical dual solutions placed the active complementary-state constraint at an interior point b1=tb_1=t. To retain feasibility of the first pointwise inequality, we mixed the first three coordinates of 3z_3 with the trivially feasible triple (0,0,1)(0,0,1): (λ,μ,u)=θ(λ3,μ3,u3)+(1−θ)(0,0,1).(λ,μ,u)=θ( _3, _3,u_3)+(1-θ)(0,0,1). We then imposed equality and zero derivative in the second pointwise inequality at b1=tb_1=t. Equality determines v=t−λf(xt)−μFx(t)v=t-λ f(xt)-μ F_x(t), while the derivative condition determines the mixing weight. Numerical solutions suggested a moving interior value of t, so we retained the rational values t=15/100,16/100,…,60/100t=15/100,16/100,…,60/100; these give 4,5,…,49z_4,z_5,…,z_49, respectively. Only the exact coverage proof in Section B.4, not this numerical pattern, establishes that these tuples suffice. Rationalization. The best numerical candidate used f(t)≈0.42323858t+0.47110490t12+0.10565652t13f(t)≈ 0.42323858t+0.47110490t^12+0.10565652t^13 and an Integrated Veto weight of approximately 0.15881980.1588198. We replaced the probabilities, mixture weight, active value y1y_1, and tangency points by the rational values in Sections 5 and B.2. The outer LP relation a=Ccut/γa=C_cut/γ and b=α/γb=α/γ then gives the displayed rational target. These replacements change both the rule and the proposed dual curves: numerical proximity transfers no guarantee. The proof in Section B.4 therefore verifies the rational data independently over all states and all (q,x)∈[0,1]2(q,x)∈[0,1]^2. B.7 Reproducing the Computer-Assisted Checks The GitHub repository cited above contains a README, the exact verifier, the checked-in rational candidate, and the numerical search code. The verifier uses only the Python standard library and reconstructs every polynomial in Sections B.3 and B.4 using exact rational arithmetic. From the repository root, either runpython3 verify_distortion.py python3 verify_distortion.py candidate.json The first command uses the built-in candidate, while the second supplies the same checked-in data explicitly. Either command produces exactlyAll polynomial nonnegativity checks passed. Any failed check stops the program. Successful completion verifies dual feasibility on the stated domains and that an eligible bound applies at every relevant (q,x)∈[0,1]2(q,x)∈[0,1]^2, establishing the computer-assisted claim in Lemma 5. To rerun the numerical discovery process, install requirements.txt and run python3 search_distortion.py; its floating-point output becomes part of the proof only after exact verification of the rationalized candidate.