Welfare with limited preference information An exact binary frontier and transcript certificates
Problem ID: D71-180.
Status: Unresolved; restricted results and reductions.
Target and the regime solved here
There are $n\geq1$ voters with nonnegative unit-sum utilities over $m$ alternatives. Rankings use a public deterministic tie rule. The target minimizes worst-case optimal welfare divided by the algorithm's expected welfare after at most $k$ cardinal queries per voter. The survey [survey, Section 5, Open Problems 3--4] poses broader information tradeoffs. Its reported deterministic bounds under other normalizations are not automatically sharp bounds for the randomized unit-sum problem here.
We give the exact frontier for two alternatives, including the optimal ranking-dependent lottery and a lower bound against every randomized rule. We also derive exact optimization certificates after any feasible finite transcript and a noise bound. These are restricted results with no claim of new priority. No unresolved general parameter regime is certified merely by the source's broad agenda.
Two alternatives without queries
Name the alternatives $a,b$. Suppose the observed ranking profile has $r$ voters ranking $a$ first and $s=n-r$ ranking $b$ first. Write $w=W(a)$, so $W(b)=n-w$. Since each top utility is at least $1/2$, \[
\frac r2\leq w\leq r+\frac s2.
\] Every interior point of this interval is achievable with the prescribed strict rankings; endpoints are limits when the public tie rule excludes some boundary profiles. Thus supremum distortion is unaffected by using the closed interval.
Theorem (Exact conditional and unconditional minimax distortion): For the observed counts $(r,s)$, the minimax distortion among all randomized zero-query rules is \[
D_{r,s}=1+\frac{2rs}{n^2}.
\] If $r,s>0$, an optimal rule chooses $a$ with probability \[
p_{r,s}=\frac{r(r+2s)}{r^2+4rs+s^2}.
\] For $r=0$ or $s=0$, choose the unanimously top alternative. Consequently \[
D^*(n,2,0)=1+\frac{2\lfloor n^2/4\rfloor}{n^2},
\qquad D^*(n,2,k)=1\quad(k\geq1).
\]
Proof: Fix the labeled ranking profile. Every randomized rule with no queries has some probability $p$ of choosing $a$; labels and internal random bits can only affect this number. Its expected welfare at $w$ is $pw+(1-p)(n-w)$. On each side of $w=n/2$, the ratio \[
\frac{\max\{w,n-w\}}{pw+(1-p)(n-w)}
\] is a linear-fractional function with a derivative of constant sign, whenever its denominator is positive. Its maximum over the interval therefore occurs at an endpoint or at $n/2$, where its value is one. For $r,s>0$ both endpoint denominators are positive, and their ratios are \[
L(p)=\frac{r+2s}{r+2s-2sp},\qquad
H(p)=\frac{2r+s}{s+2rp}.
\] Here $L$ increases and $H$ decreases. At $p=0$ we have $L=1<H$; at $p=1$ we have $H=1<L$. Their unique intersection minimizes their maximum. Solving $L(p)=H(p)$ gives the displayed $p_{r,s}$. Substitution gives $(r^2+4rs+s^2)/(r+s)^2=1+2rs/n^2$. Both endpoint profiles are feasible or arbitrarily approximable, so this maximum is also a lower bound for every randomized rule, not only an upper bound for the proposed lottery.
For unanimity, the top alternative weakly maximizes each individual's utility, hence welfare; choosing it gives distortion one, the unavoidable lower bound. Maximizing $rs=r(n-r)$ over integer $r$ gives $\lfloor n^2/4\rfloor$, proving the unconditional formula. Finally a single exact query to $u_i(a)$ determines $u_i(b)=1-u_i(a)$ for every voter. Welfare maximization is exact, giving distortion one for $k\geq1$. ∎
For example the balanced binary profile has distortion $3/2$, not the coarser uniform-choice bound two. With odd $n$ the exact worst constant is strictly below $3/2$. With one voter it is one, consistently with the top-choice baseline.
The sharp information remaining after a transcript
Fix any ranking profile and any realized, feasible transcript of an adaptive query rule, including its realized random seed. Let $\mathcal U_T$ be all unit-sum utility profiles consistent with that transcript. Queries are truthful exact coordinates, or intervals $|u_i(a)-y_{ia}|\leq\eta_{ia}$ under declared deterministic noise bounds. Let $P_T$ be the bounded polytope obtained from nonnegativity, unit sums, all weak ranking inequalities, and all query constraints. Assume the actual consistency set is nonempty.
Lemma (Closure and exact welfare certificates): $P_T$ is the closure of $\mathcal U_T$. For any alternatives $a,b$ and real $d\geq0$, the smallest value of $W(a)-dW(b)$ over the closure is the sum of $n$ individual linear-program minima. In particular an alternative $a$ is a welfare maximizer for every consistent utility profile if and only if all $m$ minima for $W(a)-W(b)$ are nonnegative.
Proof: The tie rule makes some ranking inequalities strict when equality would reverse the reported order. All other constraints are weak linear inequalities or equalities. Choose one genuinely consistent point $u^0\in\mathcal U_T$. For every $u\in P_T$, the convex combination $(1-t)u+t u^0$ satisfies all strict ranking inequalities for $t>0$ and all remaining constraints by convexity, so belongs to $\mathcal U_T$ and converges to $u$. Conversely the weak constraints are closed. This proves the closure assertion.
After fixing the transcript, all utility and query constraints are voter-specific. Adaptivity adds none: the fixed seed and previous answers induce the same next query on every consistent profile. Thus $P_T$ is the product of the individual feasible polytopes. The welfare difference is a sum of their linear objectives, so its minimum separates and is attained. Nonnegativity of these minima is exactly universal welfare dominance, using continuity and the closure. ∎
Theorem (Sharp randomized continuation value): Let $V_T$ be the finite vertex set of $P_T$. The largest guaranteed fraction of optimal welfare achievable by a lottery after this transcript is the optimum $t_T$ of the finite linear program \[
\begin{split}
\text{maximize }&t,\\
q_a&\geq0,\quad\sum_aq_a=1,\quad0\leq t\leq1,\\
\sum_aq_aW_u(a)&\geq tW_u(b)
\quad(u\in V_T,\ b\in[m]).
\end{split}
\] The exact conditional minimax distortion is $1/t_T$, with $1/m\leq t_T\leq1$. This is a finite characterization, without a polynomial-time claim for vertex enumeration or adaptive query design.
Proof: For fixed $q,t,b$, the difference between the two sides of the constraint is linear in $u$. It is nonnegative on the whole polytope exactly when it is nonnegative at every vertex, by convex decomposition into vertices. By Lemma
Lemma (Closure and exact welfare certificates) this is also equivalent to nonnegativity on the actual consistency set. Requiring it for each $b$ is equivalent to expected welfare at least $t\max_bW_u(b)$ uniformly. Since $\sum_bW_u(b)=n$, optimal welfare is always at least $n/m>0$. Uniform choice yields expected welfare $n/m$, while optimal welfare is at most $n$, so $t=1/m$ is feasible. The feasible $(q,t)$ set is nonempty and compact, and hence attains its maximum. Reciprocating the best positive guaranteed fraction gives the distortion formula. ∎
The constraints include correlations between different alternatives' welfare induced by each unit-sum restriction. Optimizing separately computed coordinate intervals generally loses that information and need not give the sharp lottery.
Full elicitation and bounded measurement error
Proposition (Normalization and a direct noise guarantee): With exact answers, $m-1$ coordinate queries per voter suffice for welfare-optimal choice for every $m$. With all $m$ coordinates measured with errors bounded by $\eta$, choosing an alternative of maximum reported total has additive welfare regret at most $2n\eta$. Combining this rule with uniform choice, by selecting the rule with the better proved guarantee in advance, gives distortion at most \[
\min\left\{m,\frac{1}{1-2m\eta}\right\}
\quad\text{when }2m\eta<1,
\] and the bound $m$ for all $\eta$.
Proof: The missing coordinate equals one minus the sum of the queried ones. For noisy full elicitation, let $\widehat W$ denote reported totals. Each satisfies $|\widehat W(a)-W(a)|\leq n\eta$. If $a^*$ maximizes true welfare and $\widehat a$ maximizes reported welfare, then \[
W(a^*)\leq\widehat W(a^*)+n\eta
\leq\widehat W(\widehat a)+n\eta
\leq W(\widehat a)+2n\eta.
\] Since $W(a^*)\geq n/m$, this gives $W(\widehat a)\geq(1-2m\eta)W(a^*)$ when that coefficient is positive. Uniform choice supplies the competing bound $m$ independently of noise. ∎
The binary theorem provides matching upper and lower bounds in its specified regime. The transcript program does not solve optimal adaptive elicitation for $m\geq3$, and the noise bound has no matching minimax lower bound here. Those are precise limits of this attempt; no general frontier or contemporary literature gap is claimed solved.
References
- [survey] E. Anshelevich, A. Filos-Ratsikas, N. Shah, and A. A. Voudouris (2021). Distortion in Social Choice Problems: The First 15 Years and Beyond. Section 5, "Beyond Ordinal Information," Open Problems 3--4, printed p. 9. https://arxiv.org/pdf/2103.00911.
Completion Estimate
30%