Answer: Every admissible output has distortion at most \(5\), and an admissible rational coupling is computable in time polynomial in \(m,\tau,L\). The sharp uniform distortion among deterministic group-oblivious ordinal rules is \(5\). Exact profile-dependent ratios are given by the LP-family characterization proved above; with two alternatives they are \(1+2/p\) for \(1/2\le p<1\), and \(1\) for \(p=1\).
Theorem 4.3 — class: algorithmic
Given a finite alternative set \(A\) and a rational mass vector \(\bar\mu\) over rankings, compute an alternative \(x\) and a fractional domination coupling \(z\) with row and column marginals \(\bar\mu\), supported on pairs where ranking \(r\) ranks \(x\) at least as highly as the top alternative of ranking \(s\). Determine and certify the worst-case \(\operatorname{MaxAvg}\) distortion of this group-oblivious rule over all hidden finite type distributions with ranking marginal \(\bar\mu\), and whether a ratio of \(5\) is tight under the chosen group-multiplicity regime.
Let \(A\) contain \(m\ge2\) alternatives. A society is given by its support: a list \(R\) of \(\tau\) strict rankings with positive binary-rational masses \(\bar\mu_r\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the input bit length.
An admissible output is \(x\in A\) and a nonnegative rational coupling \(z\) satisfying \(\sum_s z_{rs}=\bar\mu_r\), \(\sum_r z_{rs}=\bar\mu_s\), and \(z_{rs}=0\) unless \(x\succeq_r\operatorname{top}(s)\), where \(\succeq_r\) means earlier in ranking \(r\), or equal.
A hidden realization has finitely many types \(t\), each with positive rational mass \(p_t\), ranking \(r_t\in R\), location \(v_t\) in a common metric space containing \(A\), and group label \(g_t\). Require \(\sum_{t:r_t=r}p_t=\bar\mu_r\) and \(a\succ_{r_t}b\Rightarrow d(v_t,a)\le d(v_t,b)\); equal distances may be ordered arbitrarily. Locations may coincide.
Allow any finite number \(k\ge2\) of hidden groups, each with positive mass, with no lower bound on group masses. The same ranking may occur at different locations and in different groups.
Define \(C_I(a)=\operatorname{MaxAvg}_I(a)=\max_g\frac{\sum_{t:g_t=g}p_t d(v_t,a)}{\sum_{t:g_t=g}p_t}\) and \(D_x(\bar\mu)=\sup_I C_I(x)/\min_{a\in A}C_I(a)\), over compatible hidden realizations; use \(0/0=1\) and a positive numerator divided by zero as \(+\infty\). A deterministic rule \(M\) sees only \((A,\bar\mu)\), fixes all selection ties deterministically, and has distortion \(\sup_{A,\bar\mu}D_{M(A,\bar\mu)}(\bar\mu)\).
What are the profile-dependent worst-case ratios \(D_x(\bar\mu)\) for admissible outputs, and the sharp uniform distortion guarantee for rules returning them?
Can an admissible \((x,z)\) be computed in time polynomial in \(m,\tau,L\) with distortion at most \(5\), and is \(5\) optimal among all deterministic group-oblivious ordinal rules under this group regime?
For finite agents, domination-perfect-matching rules have MaxAvg distortion at most \(5\), and every deterministic group-oblivious ordinal rule has distortion at least \(5-\varepsilon\) for every \(\varepsilon>0\), even with two alternatives and equal-sized groups. [Source](https://link.springer.com/article/10.1007/s10458-026-09742-y)
For arbitrary voter and candidate weights, FractionalVeto constructs a fractional domination matching; this addresses weighted winner existence, rather than the hidden-group MaxAvg distortion question. [Source](https://arxiv.org/html/2206.07098v2)
No result settling the specified continuous distortion question was located.
Every admissible output satisfies \(D_x(\bar\mu)\le 5\). An admissible rational coupling can be computed in time polynomial in \(m,\tau,L\), and \(5\) is optimal among all deterministic group-oblivious ordinal rules in the stated regime.
The profile-dependent ratios need not equal \(5\). Below is an exact characterization by a one-parameter family of linear programs. In particular, with two alternatives, if \(p\) is the mass preferring an admissible winner \(x\), then
\( \displaystyle D_x(\bar\mu)= \begin{cases} 1+2/p,&\frac12\le p<1,\\ 1,&p=1. \end{cases} \)
All statements below use the permitted convention that equal distances may be ordered arbitrarily.
Define the top-choice mass of candidate \(c\) by
\( \displaystyle q_c=\sum_{s:\operatorname{top}(s)=c}\bar\mu_s. \)
The weighted ranking-matching lemma states that, for arbitrary voter and candidate probability weights, some candidate \(x\) admits a fractional matching supported on edges \(x\succeq_r c\), with the prescribed voter and candidate marginals. This is the existence result established constructively by FractionalVeto. [PluralityVeto, Section 4](https://arxiv.org/html/2206.07098v2)
Apply it with voter set \(R\), voter weights \(\bar\mu_r\), candidate set \(A\), and candidate weights \(q_c\). These are nonnegative probability weights, as required. Thus some \(x\) admits numbers \(f_{rc}\) satisfying
\( \displaystyle \sum_c f_{rc}=\bar\mu_r,\qquad \sum_r f_{rc}=q_c,\qquad f_{rc}=0\ \text{unless }x\succeq_r c. \)
For every \(s\), the quantity \(q_{\operatorname{top}(s)}\) is positive because \(\bar\mu_s>0\). Set
\( \displaystyle z_{rs} =f_{r,\operatorname{top}(s)} \frac{\bar\mu_s}{q_{\operatorname{top}(s)}}. \)
Summing over rankings with the same top choice gives \(\sum_s z_{rs}=\bar\mu_r\). Summing over \(r\) gives \(\sum_r z_{rs}=\bar\mu_s\). Its support also has the required domination property. Hence an admissible output exists.
To compute one, test candidates in a fixed deterministic order. For each \(x\), construct a flow network with:
A flow of value \(1\) is precisely an admissible coupling. Existence guarantees that some test succeeds.
There are \(m\) networks, each with \(O(\tau)\) vertices and \(O(\tau^2)\) arcs. Multiplying capacities by the product of the input denominators gives integer capacities whose bit lengths are \(O(L)\). A polynomial-time maximum-flow algorithm therefore yields a rational coupling in time polynomial in \(m,\tau,L\). No expansion into individual voters or enumeration of unsupported rankings is needed.
Fix an admissible \((x,z)\) and a compatible hidden realization \(I\). Define the overall average cost
\( \displaystyle B_I(a)=\sum_t p_t d(v_t,a). \)
Because this is a mass-weighted average of the group averages,
\( \displaystyle B_I(a)\le C_I(a). \)
For each supported ranking, define its conditional average distance vector
\( \displaystyle h_r(b)= \frac{1}{\bar\mu_r}\sum_{t:r_t=r}p_t d(v_t,b). \)
Whenever \(z_{rs}>0\), admissibility and ordinal consistency imply
\( \displaystyle h_r(x)\le h_r(\operatorname{top}(s)),\qquad h_s(\operatorname{top}(s))\le h_s(a). \)
The triangle inequality, averaged within the relevant rankings, consequently gives
\( \displaystyle d(x,a) \le h_r(a)+h_r(x) \le 2h_r(a)+d(a,\operatorname{top}(s)) \le 2h_r(a)+2h_s(a). \)
Multiply by \(z_{rs}\) and sum. Both marginals of \(z\) are \(\bar\mu\), so
\( \displaystyle d(x,a)\le 4\sum_r\bar\mu_r h_r(a)=4B_I(a). \)
For every group, its average distance to \(x\) is at most its average distance to \(a\), plus \(d(x,a)\). Therefore
\( \displaystyle C_I(x)\le C_I(a)+d(x,a) \le C_I(a)+4B_I(a) \le 5C_I(a). \)
This holds for every alternative \(a\). If the optimal cost is zero, it also forces \(C_I(x)=0\), giving ratio \(1\) under the specified convention. Otherwise, divide by the optimal cost. Thus \(D_x(\bar\mu)\le 5\).
The following formula eliminates the unknown number of groups, types, and metric-space points.
Let \(\delta=(\delta_{bc})_{b,c\in A}\) be a candidate pseudometric: it is symmetric and nonnegative, has zero diagonal, and satisfies every triangle inequality.
For ranking \(r\), let \(K_r(\delta)\) consist of vectors \(h\in\mathbb R_{\ge0}^{A}\) satisfying, for all candidates \(b,c\),
\( \displaystyle |h(b)-h(c)|\le\delta_{bc}\le h(b)+h(c), \)
and
\( \displaystyle b\succ_r c\ \Longrightarrow\ h(b)\le h(c). \)
These are linear inequalities when the absolute-value inequality is written as two inequalities.
They are exactly the conditions needed to extend the candidate pseudometric by a point with candidate distances \(h\) and ranking \(r\). To verify sufficiency, connect the new point to each candidate \(b\) by an edge of length \(h(b)\), retaining the candidate edges of lengths \(\delta_{bc}\), and take shortest-path distances. The sum inequalities prevent shortcuts between candidates through the new point; the difference inequalities prevent shortcuts in its prescribed distances.
The same construction works simultaneously for any finite collection of such vectors. Identifying points at zero distance yields a metric space. When candidate distances are positive, the alternatives remain distinct.
Fix \(a\in A\), \(r,s\in R\), and \(\theta\in[0,1]\). Define \(V_{x,a}^{r,s}(\theta)\) as the supremum of the linear-program objective
\( \displaystyle \theta u(x)+(1-\theta)v(x), \)
with variables \(\delta\), vectors \(h_t\) for \(t\in R\), and vectors \(u,v\), subject to
\( \displaystyle h_t\in K_t(\delta)\quad(t\in R),\qquad u\in K_r(\delta),\qquad v\in K_s(\delta), \)
and
\( \displaystyle \sum_{t\in R}\bar\mu_t h_t(a)\le1,\qquad \theta u(a)+(1-\theta)v(a)\le1. \)
For fixed \(\theta\), this is an LP with \(O(m^2+\tau m)\) variables and \(O(m^3+\tau m^2)\) constraints.
The exact answer for every admissible \(x\) is
\( \displaystyle \boxed{ D_x(\bar\mu)= \max_{\substack{a\in A\\r,s\in R}} \ \sup_{\theta\in[0,1]}V_{x,a}^{r,s}(\theta). } \)
Thus general profiles admit an exact finite optimization characterization. Polynomial-time evaluation of this formula is not asserted; polynomial-time construction of an admissible output was proved separately.
Consider a realization with positive optimal cost. Choose an optimal alternative \(a\), and scale all distances so that \(C_I(a)=1\). Choose a group attaining \(C_I(x)\).
The overall conditional ranking vectors \(h_t\) belong to \(K_t(\delta)\), and
\( \displaystyle \sum_t\bar\mu_t h_t(a)=B_I(a)\le1. \)
Within the selected group, average the distance vectors separately for each ranking present. Denote these vectors by \(u_t\), and their conditional masses by \(\lambda_t\). Averaging preserves every inequality defining \(K_t(\delta)\). Moreover,
\( \displaystyle \sum_t\lambda_t=1,\qquad \sum_t\lambda_t u_t(a)\le1,\qquad \sum_t\lambda_t u_t(x)=C_I(x). \)
Hold these distance vectors fixed and maximize \(\sum_t\lambda_t u_t(x)\) over the simplex, subject to \(\sum_t\lambda_t u_t(a)\le1\). An optimum exists because the feasible set is nonempty and compact.
An extreme optimum has at most two positive coordinates. Indeed, with at least three positive coordinates, there is a nonzero perturbation \(w\), supported on them, satisfying both \(\sum_t w_t=0\) and \(\sum_t w_tu_t(a)=0\). Sufficiently small perturbations in both directions remain feasible, contradicting extremality.
Consequently, some rankings \(r,s\) and mixing weight \(\theta\) produce a feasible LP point whose objective is at least \(C_I(x)\), the normalized distortion.
Realizations with zero optimal cost have distortion \(1\) by Section 2. Every LP has value at least \(1\), witnessed by \(\delta_{bc}=0\) and all distance coordinates equal to \(1\). This covers the zero-cost case as well.
First consider feasible data with rational coordinates, rational \(\theta\), and positive distances between distinct alternatives. Write
\( \displaystyle T=\theta u(x)+(1-\theta)v(x),\quad M=\theta u(a)+(1-\theta)v(a),\quad B=\sum_t\bar\mu_t h_t(a). \)
Thus \(M\le1\) and \(B\le1\). Define the ranking distribution
\( \displaystyle q_t=\theta\mathbf1_{t=r}+(1-\theta)\mathbf1_{t=s}. \)
For sufficiently small positive rational \(\varepsilon\), construct two groups:
The extension construction supplies a common metric space. The total mass of every ranking is exactly \(\bar\mu_t\), and all type masses are positive rationals.
The first group has average costs \(M\) at \(a\) and \(T\) at \(x\). The second group’s average cost at \(a\) is
\( \displaystyle \frac{B-\varepsilon\sum_tq_t h_t(a)}{1-\varepsilon} \longrightarrow B. \)
Hence \(C_I(a)\longrightarrow\max\{M,B\}\le1\), while \(C_I(x)\ge T\). Comparing with \(a\), the supremum of the actual distortion is therefore at least \(T\).
It remains to justify allowing real data and candidate pseudometrics in the LP. For any feasible point and \(\eta>0\), replace
\( \displaystyle \delta_{bc}\ \text{by }\delta_{bc}+2\eta\quad(b\ne c), \)
and add \(\eta\) to every distance coordinate. All extension and ranking inequalities remain valid. Dividing all distances by \(1+\eta\) restores both budget inequalities. Distinct candidates now have positive distances, and the objective becomes \((T+\eta)/(1+\eta)\), which tends to \(T\).
Rational points are dense in the joint distance cone: its defining inequalities have rational coefficients, and approximation within the rational linear span of the minimal face preserves them. Approximate these distance data and \(\theta\) by rational values. If either budget slightly exceeds \(1\), divide all distances by the maximum of \(1\) and the two budget values. This factor tends to \(1\), so the objective converges.
Thus rational, genuine-metric instances approach every feasible LP value. This proves the reverse inequality and the exact formula.
In particular, the supremum can be approached with two groups and at most \(\tau+2\) types.
Let \(A=\{x,a\}\), and let \(p\) be the mass ranking \(x\) above \(a\).
A row ranking \(a\) above \(x\) can send mass only to columns whose top choice is \(x\). Its total mass is \(1-p\), whereas those columns have capacity \(p\). Therefore admissibility requires \(1-p\le p\).
Conversely, when \(1/2\le p<1\), the coupling, with rows and columns ordered by \(x\)-first and \(a\)-first rankings, is
\( \displaystyle z= \begin{pmatrix} 2p-1&1-p\\ 1-p&0 \end{pmatrix}. \)
It has the required marginals and support. For \(p=1\), the sole supported ranking couples to itself. Thus \(x\) is admissible exactly when \(p\ge1/2\).
Put \(\Delta=d(x,a)\). Every voter ranking \(x\) above \(a\) satisfies
\( \displaystyle \Delta\le d(v,x)+d(v,a)\le2d(v,a). \)
Consequently,
\( \displaystyle C_I(a)\ge B_I(a)\ge\frac{p\Delta}{2}. \)
Together with \(C_I(x)\le C_I(a)+\Delta\), this bounds the distortion by \(1+2/p\).
Suppose \(p<1\). Choose rational \(0<\varepsilon<1-p\), and put
\( \displaystyle t=\frac{p}{2(1-\varepsilon)}. \)
On the real line, place \(x\) at \(0\) and \(a\) at \(1\). Use two groups:
The midpoint ranking is compatible because its two distances are equal. Both groups have average cost \(t\) at \(a\). Their average costs at \(x\) are respectively \(1+t\) and \(1-t\). Therefore
\( \displaystyle \frac{C_I(x)}{\min_b C_I(b)} =\frac{1+t}{t} =1+\frac{2(1-\varepsilon)}p. \)
Letting positive rational \(\varepsilon\) tend to zero proves \(D_x=1+2/p\).
If \(p=1\), every voter satisfies \(d(v,x)\le d(v,a)\). This inequality holds within every group, so \(x\) always minimizes the objective and \(D_x=1\).
Consider the fixed two-alternative profile with mass \(1/2\) on each ranking. Whatever a deterministic ordinal rule selects, name its selected alternative \(x\). The preceding construction applies with \(p=1/2\), giving ratios
\( \displaystyle 5-4\varepsilon \)
for arbitrarily small positive rational \(\varepsilon\). Thus every deterministic group-oblivious ordinal rule has uniform distortion at least \(5\), whether or not it returns admissible outputs.
Section 2 proves the matching upper bound for every rule returning admissible outputs, and Section 1 provides such a polynomial-time rule. Therefore the sharp uniform guarantee is exactly \(5\).
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the stated task. I found no false step, major gap, or minor issue requiring correction. The polynomial-time construction, distortion upper bound, exact LP characterization, two-alternative formula, and sharp uniform lower bound all withstand verification.
The cited ranking-matching result has the required scope: for a finite ranked election and arbitrary nonnegative voter and candidate probability weights, some candidate admits a nonnegative fractional matching with those marginals, supported on the stated weak-domination edges. This agrees with Section 4, particularly Theorem 2, of the [cited FractionalVeto source](https://arxiv.org/html/2206.07098v2).
Its hypotheses are satisfied here. The support \(R\) is finite, every ranking is strict, the voter weights \(\bar\mu_r\) form a probability distribution, and the top-choice weights \(q_c\) are nonnegative and sum to \(1\). Candidates with \(q_c=0\) are permitted by the theorem.
The conversion from \(f\) to \(z\) is valid. Each denominator \(q_{\operatorname{top}(s)}\) is positive because it includes \(\bar\mu_s>0\). Grouping columns by their top choice verifies the row marginals; summing over rows verifies the column marginals. Nonnegativity and the required support restriction are inherited from the fractional matching.
The flow formulation is exact. Total source capacity and total sink capacity are both \(1\), so a flow of value \(1\) saturates every prescribed marginal. Conversely, an admissible coupling supplies such a flow.
The complexity estimate is sound. There are \(m\) candidate tests, each with \(O(\tau)\) vertices and \(O(\tau^2)\) arcs. The product of the input denominators has bit length \(O(L)\); scaling therefore produces integer capacities of polynomial bit length. A polynomial-time maximum-flow algorithm yields a rational coupling of polynomial encoding length. The argument does not expand the profile into individual voters.
The identity expressing \(B_I(a)\) as the mass-weighted average of group averages is valid because group masses are positive and sum to \(1\). Thus \(B_I(a)\le C_I(a)\).
Conditional vectors \(h_r\) are well-defined because every supported ranking has positive mass. Averaging ordinal consistency gives both inequalities asserted when \(z_{rs}>0\).
Every step in the distance chain is justified:
Multiplication by \(z_{rs}\) and summation are legitimate because all terms are nonnegative and the coupling has total mass \(1\). Its two marginals give exactly the constant \(4\).
The groupwise triangle inequality then establishes \(C_I(x)\le5C_I(a)\) for every candidate \(a\). If an optimal cost is zero, this inequality forces the selected candidate’s cost to be zero as well. The prescribed convention therefore gives ratio \(1\), rather than an undefined expression or infinite ratio.
This proves the upper bound for every compatible finite hidden realization, regardless of group sizes, repeated rankings, or coincident locations.
The candidate pseudometric conditions and the inequalities defining \(K_r(\delta)\) are necessary for candidate-distance vectors. They also survive conditional averaging.
The shortest-path construction establishes sufficiency. The sum inequalities prevent an excursion through an added point from shortening a candidate-to-candidate distance. The difference inequalities prevent a route through another candidate from shortening a prescribed point-to-candidate distance.
The simultaneous extension assertion is valid: the same restrictions apply to every added point, so introducing several points creates no additional shortcut violating the prescribed distances. Taking the quotient by zero distance produces a metric. Positive distances between distinct candidates ensure that alternatives remain distinct in that quotient.
For fixed \(\theta\), every constraint and the objective are linear. The variable and constraint counts are correct, including the candidate triangle inequalities and the extension inequalities for every ranking vector.
Normalization by a positive optimal cost is legitimate. The overall conditional ranking vectors satisfy the first budget because \(B_I(a)\le C_I(a)=1\). Conditional vectors within the selected group satisfy the extension and ranking restrictions by averaging.
The optimization over group-ranking proportions has a nonempty compact feasible polytope. Its linear objective attains an optimum at an extreme point.
The perturbation argument correctly excludes three or more positive coordinates: two homogeneous linear equations on at least three supported coordinates have a nonzero solution, and sufficiently small perturbations in both directions preserve nonnegativity, total mass, and the comparator-cost constraint. Thus an extreme optimum uses at most two rankings.
This establishes the forward inequality without assuming that the group’s original ranking proportions have small support. A single supported ranking is accommodated by an endpoint mixing weight. The zero-optimum case is also covered because each LP has the stated feasible witness of objective \(1\).
For rational feasible data and rational \(\theta\), the two-group construction preserves every ranking marginal exactly. A sufficiently small positive rational \(\varepsilon\) makes every residual mass \(\bar\mu_t-\varepsilon q_t\) positive. Both groups have positive mass, and zero-mass types are explicitly omitted.
The extension construction supplies compatible locations in one common metric space. The displayed second-group comparator cost is correct: its numerator subtracts precisely the mass removed from the baseline ranking points, and its denominator is \(1-\varepsilon\).
Consequently, the comparator cost tends to \(\max\{M,B\}\le1\), while the selected candidate’s cost is at least \(T\). Comparing against \(a\) is sufficient because the actual minimum candidate cost cannot exceed \(C_I(a)\). The limiting argument establishes a supremum bound; it does not incorrectly assert attainment.
The pseudometric perturbation is valid. Adding \(2\eta\) to off-diagonal candidate distances preserves candidate triangle inequalities. Adding \(\eta\) to every point-distance coordinate preserves the difference, sum, nonnegativity, and ranking inequalities. Each budget increases by exactly \(\eta\), so scaling by \(1+\eta\) restores feasibility. The transformed objective is correctly computed as \((T+\eta)/(1+\eta)\).
The rational approximation argument is sufficient. The joint distance cone is defined by rational linear inequalities, and approximation within the rational span of the minimal face preserves feasibility when sufficiently close. Approximating \(\theta\) within its interval preserves nonnegative mixing weights. The final common rescaling handles any small budget excess and tends to \(1\).
Thus the LP family does not introduce unattainable distortion values through irrational mixing weights or coincident candidates. The exact characterization follows, as does the approximation claim using two groups and at most \(\tau+2\) types.
The admissibility necessity follows from the capacity available to rows ranking \(a\) above \(x\). The displayed coupling is nonnegative precisely in the asserted range, has the correct marginals, and satisfies domination. The separate treatment of \(p=1\) correctly handles the absent second ranking.
The comparator-cost lower bound \(C_I(a)\ge p\Delta/2\) follows from ordinal consistency and the triangle inequality. Combined with \(C_I(x)\le C_I(a)+\Delta\), it bounds the ratio whenever \(a\) is optimal; when \(x\) is optimal, the ratio is \(1\).
The lower-bound construction satisfies all mass and ranking requirements. The restriction \(\varepsilon<1-p\) ensures that both types in the second group have positive mass. The midpoint ranking is explicitly permitted by the tie convention.
Rechecking the group averages gives exactly \(t\) at \(a\), and respectively \(1+t\) and \(1-t\) at \(x\). Therefore \(a\) is optimal, the denominator is positive, and the displayed ratio is correct. Taking rational \(\varepsilon\) to zero establishes the stated supremum. The unanimous case \(p=1\) is correctly proved separately.
At the fixed balanced two-alternative profile, either deterministic selection has supporting mass \(p=1/2\). The construction therefore gives ratios \(5-4\varepsilon\) approaching \(5\), while leaving the observed profile fixed. This proves the lower bound for every deterministic group-oblivious ordinal rule, including rules whose outputs need not be admissible.
Together with the upper bound and construction, this establishes the sharp uniform guarantee and the requested polynomial-time selection result. The prover explicitly leaves polynomial-time evaluation of the exact profile-dependent LP-family supremum unasserted; that limitation does not undermine the algorithmic claim requested in the task.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.