Answer: —
Theorem 16 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe expected median distortion of Uncovered Set Min-Cover is at most $ 4$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite alternative set \(M\), a rational distribution \(\mu\) over complete rankings \(\mathcal{S}(M)\), and fixed tie-breaking, form the majority graph \(E_\mu\), compute its uncovered set \(S_\mu\), and compute a lottery \(p\) minimizing \(p_{\max}\) subject to \(p_Z\ge0\), \(\sum_{Z\in S_\mu}p_Z=1\), and \(\sum_{(Y,Z)\in E_\mu}p_Z\le p_{\max}\) for every \(Y\in S_\mu\). Determine the worst-case value of \(\sum_{A\in M}p_A\operatorname{med}_\lambda(A)/\min_{B\in M}\operatorname{med}_\lambda(B)\) over all metric population measures \(\lambda\) whose ranking push-forward is \(\mu\), and whether the factor \(4\) guarantee is tight.
Let \(M\) be finite and let \(\mu\) be a rational probability distribution on the complete rankings of \(M\). Direct \(Y\to Z\) when \(\mu\{r:Y\succ_r Z\}>1/2\), resolving equality using a fixed total order; let \(S_\mu\) be the alternatives reaching every alternative in at most two directed steps.
Choose the lexicographically first optimum \(p\) of \(\min p_{\max}\) subject to \(p_Z\ge0\), \(\sum_{Z\in S_\mu}p_Z=1\), and \(\sum_{Z\in S_\mu:(Y,Z)\in E_\mu}p_Z\le p_{\max}\) for each \(Y\in S_\mu\), with \(p_A=0\) outside \(S_\mu\).
A metric population is a probability measure \(\lambda\) on a metric space containing \(M\); its induced ranking orders alternatives by nondecreasing distance, with ties resolved by the fixed order. Require this ranking push-forward to equal \(\mu\), and define \(\operatorname{med}_\lambda(A)=\inf\{t:\lambda(\{x:d(x,A)\le t\})\ge1/2\}\). Let \(D_\mu(p)\) be the supremum of \(\frac{\sum_{A\in M}p_A\operatorname{med}_\lambda(A)}{\min_{B\in M}\operatorname{med}_\lambda(B)}\) over such \(\lambda\).
Target: Is the rational-threshold problem of deciding \(D_\mu(p)\le q\) in \(\mathrm{P}\), or is it NP-hard?
Is \(\sup_\mu D_\mu(p)=4\)?
Known discrete results: for finite voter profiles, this LP-based rule is computable in polynomial time and has expected median distortion at most \(4\). Every randomized rule has worst-case median distortion at least \(3\) in the discrete model.
The proposed universal bound is false under the stated median and majority-tie conventions: a fixed rational distribution on two rankings has unbounded distortion, even using only populations with strictly positive optimal median.
I also determine the distortion completely for two alternatives. The complexity question for an unrestricted number of alternatives remains open here.
There is a minor definitional issue: the displayed ratio is undefined when its denominator is zero. Below, suprema are taken over populations with positive denominator. The unboundedness construction uses only such populations, so any extension that includes their ratios remains unbounded.
Let \(M=\{A,B\}\), naming the alternatives so that the fixed order resolves a majority tie in favor of \(A\). Fix the rational ranking distribution
\(\mu(A\succ B)=\mu(B\succ A)=\tfrac12.\)
The directed tournament has the single edge \(A\to B\). Consequently, \(S_\mu=\{A\}\): \(A\) reaches both alternatives, whereas \(B\) cannot reach \(A\). The normalization constraint therefore forces \(p_A=1\) and \(p_B=0\). There is no ambiguity from lexicographic optimization.
For each \(0<\varepsilon<1\), use the real line with its usual distance. Place the alternatives at \(B=0\) and \(A=2\), and define
\(\lambda_\varepsilon=\tfrac12\delta_\varepsilon+\tfrac12\delta_3,\)
where \(\delta_x\) denotes unit probability mass at \(x\). The distances are:
| Population point | Mass | Distance to \(A\) | Distance to \(B\) | Ranking |
|---|---|---|---|---|
| \(\varepsilon\) | \(\tfrac12\) | \(2-\varepsilon\) | \(\varepsilon\) | \(B\succ A\) |
| \(3\) | \(\tfrac12\) | \(1\) | \(3\) | \(A\succ B\) |
Both rankings are strict, and the ranking push-forward is exactly the fixed distribution \(\mu\).
For two equally weighted atoms, the specified lower median is the smaller of the two distances: below that distance the ball has mass zero, and at that distance it has mass at least \(\tfrac12\). Thus
\(\operatorname{med}_{\lambda_\varepsilon}(A)=1,\qquad \operatorname{med}_{\lambda_\varepsilon}(B)=\varepsilon.\)
The distortion ratio is therefore
\(\displaystyle \frac{\sum_Cp_C\operatorname{med}_{\lambda_\varepsilon}(C)}{\min_C\operatorname{med}_{\lambda_\varepsilon}(C)}=\frac1\varepsilon.\)
For every finite positive \(K\), choosing \(0<\varepsilon<\min\{1,1/K\}\) makes this ratio exceed \(K\). Hence this single rational instance satisfies \(D_\mu(p)=+\infty\). In particular,
\(\displaystyle \sup_\mu D_\mu(p)=+\infty,\)
rather than \(4\).
This construction already consists of two equally weighted voters. Thus the stated finite-profile bound cannot apply unchanged to the simultaneous use of this lower median and this majority-tie convention. The published bound for Uncovered Set Min-Cover does not justify transferring the guarantee without reconciling those conventions. [Anshelevich–Postl, Theorem 13](https://www.ijcai.org/Proceedings/16/Papers/014.pdf)
Let \(W\) be the winner of the unique tournament edge and \(L\) the other alternative. As above, the rule necessarily selects \(W\) with probability one. Set
\(\alpha=\mu\{r:W\succ_r L\}.\)
By the definition of the edge, \(\tfrac12\le\alpha\le1\).
Proposition. Over populations with positive optimal median, the distortion is \(+\infty\) when \(\alpha=\tfrac12\), is \(3\) when \(\tfrac12<\alpha<1\), and is \(1\) when \(\alpha=1\).
The tie case was proved above. The remaining cases follow below.
Consider any admissible population with \(\alpha>\tfrac12\). Write \(b=\operatorname{med}_\lambda(L)\).
First, \(b\) is finite and the closed ball \(C=\{x:d(x,L)\le b\}\) has mass at least \(\tfrac12\). Finiteness follows because balls of integer radius increase to the entire metric space. For attainment, the definition of the infimum implies that every ball of radius \(b+1/n\) has mass at least \(\tfrac12\); continuity of a probability measure from above gives \(\lambda(C)\ge\tfrac12\).
Let \(H\) be the set of points whose induced ranking places \(W\) above \(L\). Then \(\lambda(H)=\alpha>\tfrac12\), and
\(\lambda(H\cap C)\ge\lambda(H)+\lambda(C)-1>0.\)
Choose \(x\in H\cap C\). Ranking consistency implies \(d(x,W)\le d(x,L)\), including when the ranking is determined by a distance tie. The triangle inequality yields
\(d(W,L)\le d(W,x)+d(x,L)\le2d(x,L)\le2b.\)
For every \(y\in C\), another application of the triangle inequality gives
\(d(y,W)\le d(y,L)+d(L,W)\le b+2b=3b.\)
Since \(C\) has mass at least \(\tfrac12\), it follows that \(\operatorname{med}_\lambda(W)\le3b\).
If \(W\) has the smaller median, the distortion is \(1\). Otherwise its distortion is \(\operatorname{med}_\lambda(W)/b\le3\). This proves the upper bound.
Fix \(\tfrac12<\alpha<1\) and put \(\beta=1-\alpha\), so \(0<\beta<\tfrac12\).
On the real line, place \(L=0\) and \(W=2\). For \(0<\eta<1\), use the population
\(\lambda_\eta=\beta\delta_{-1}+(\tfrac12-\beta)\delta_{1+\eta}+\tfrac12\delta_6.\)
The distances and rankings are:
| Population point | Mass | Distance to \(W\) | Distance to \(L\) | Ranking |
|---|---|---|---|---|
| \(-1\) | \(\beta\) | \(3\) | \(1\) | \(L\succ W\) |
| \(1+\eta\) | \(\tfrac12-\beta\) | \(1-\eta\) | \(1+\eta\) | \(W\succ L\) |
| \(6\) | \(\tfrac12\) | \(4\) | \(6\) | \(W\succ L\) |
The mass preferring \(W\) is \(1-\beta=\alpha\), so this realizes exactly the prescribed two-ranking distribution.
For \(L\), cumulative mass is \(\beta<\tfrac12\) at distance \(1\), and first reaches \(\tfrac12\) at distance \(1+\eta\). For \(W\), cumulative mass is \(\tfrac12-\beta<\tfrac12\) at distance \(1-\eta\), and first reaches \(\tfrac12\) at distance \(3\). Therefore
\(\operatorname{med}_{\lambda_\eta}(L)=1+\eta,\qquad \operatorname{med}_{\lambda_\eta}(W)=3.\)
The ratio is \(3/(1+\eta)\), which tends to \(3\) as \(\eta\) tends to zero. Together with the upper bound, this proves that the supremum is exactly \(3\).
If \(\alpha=1\), ranking consistency gives \(d(x,W)\le d(x,L)\) almost surely. Consequently, for every radius \(t\), the mass within distance \(t\) of \(W\) is at least the mass within distance \(t\) of \(L\). Taking the defining infima gives
\(\operatorname{med}_\lambda(W)\le\operatorname{med}_\lambda(L).\)
Thus selecting \(W\) has ratio exactly \(1\) whenever the denominator is positive. Such admissible populations exist—for example, a single voter strictly closer to \(W\), at positive distance from both alternatives. This completes the classification.
The classification supplies a polynomial-time threshold test when there are exactly two alternatives: compute \(\alpha\), distinguish the three cases, and compare the corresponding value with the rational threshold.
It does not establish a polynomial-time algorithm or NP-hardness for an unrestricted number of alternatives. Unbounded instances alone establish neither complexity conclusion.
⟨structured verdict parsed — rendered above⟩
The output is correct as a partial result. Its unboundedness example and complete two-alternative classification are rigorous under the explicitly adopted positive-denominator convention. It does not settle the general complexity question. No false mathematical step was found.
The original ratio is undefined for admissible populations whose optimal median is zero. The prover explicitly restricts its analysis to populations with positive optimal median.
This is a legitimate, clearly disclosed restriction, but it does not itself define the original expression on all admissible populations. Consequently, the asserted values of \(D_\mu(p)\) must be read under that restriction.
The counterexample’s substantive conclusion is unaffected: its denominators are strictly positive, so any definition retaining these ratios has no finite universal upper bound.
Issue — minor, definitional: Reusing \(D_\mu(p)\) for the restricted supremum can obscure the distinction from the original undefined expression. The minimum clarification is to label every exact-value claim as referring to the positive-denominator supremum. No additional mathematics is needed.
Every step checks out.
This proves unboundedness for a single fixed rational input distribution, rather than merely for a sequence of different distributions.
It also correctly demonstrates that the quoted finite-profile guarantee cannot simultaneously hold under the exact conventions in the task: the construction is already a two-voter profile.
The cited [Anshelevich–Postl Theorem 13](https://www.ijcai.org/Proceedings/16/Papers/014.pdf) does state the expected median distortion bound for Uncovered Set Min-Cover. The prover does not apply that theorem to establish its result; its warning that conventions require reconciliation is justified by the explicit counterexample. No missing theorem application undermines the construction.
The argument is valid for arbitrary admissible probability populations, including populations with atoms.
The strict inequality \(\alpha>1/2\) is used exactly where needed. The argument does not incorrectly extend to the majority-tie case.
All parameters, masses, rankings, and median calculations are correct.
For \(1/2<\alpha<1\), the parameter \(\beta=1-\alpha\) satisfies \(0<\beta<1/2\). Thus all three masses are positive and sum to \(1\).
The mass preferring \(W\) is
\((1/2-\beta)+1/2=\alpha\), as required.
For \(L\), the increasing distance order is \(1,1+\eta,6\). Cumulative mass first reaches \(1/2\) at \(1+\eta\).
For \(W\), the increasing distance order is \(1-\eta,3,4\). Cumulative mass first reaches \(1/2\) at \(3\).
Therefore the ratio is \(3/(1+\eta)\), with positive denominator, and approaches \(3\). Approaching the value suffices to establish the claimed supremum; attainment is unnecessary.
The almost-sure distance inequality implies the asserted comparison of ball probabilities for every radius. Taking the median infima consequently gives
\(\operatorname{med}_\lambda(W)\le\operatorname{med}_\lambda(L)\).
Since the rule selects \(W\), the ratio is exactly \(1\) whenever the denominator is positive. The stated single-voter example also establishes that the admissible class being optimized over is nonempty.
No gap appears in this case.
The two-alternative threshold test follows from the classification. Under an explicit binary rational representation, comparing \(\alpha\) with \(1/2\) and \(1\), and comparing the resulting finite value with the threshold, takes polynomial time. An infinite value exceeds every rational threshold.
However, this does not classify the problem for an unrestricted number of alternatives. The prover expressly acknowledges this limitation.
Issue — major, incomplete assignment: Neither a general polynomial-time algorithm nor a hardness result is established. This is missing work, not an error in the proved restricted results. Resolving it requires a general complexity argument under a specified input representation and denominator convention; clarification alone cannot supply that argument.
The appropriate overall adjudication is partial, consistent with the prover’s own claim. The universal bound is disproved under the disclosed convention, and the two-alternative classification stands.
⟨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.