Learning Acceptable Lotteries via Queries: Minimizing Aggregated Violation Distances

Randomization is often used to compromise among fixed policies, classifiers, or interventions, but affected stakeholders may be unable or unwilling to report utilities over all alternatives. We study a weaker feedback model in which, for each proposed lottery, each stakeholder reports only whether it is acceptable. Unlike prior work focused on finding a unanimously acceptable lottery when one exists, we allow unanimity to be impossible and seek lotteries that minimize aggregate acceptability violations. We model each stakeholder's acceptable lotteries by an unknown linear threshold rule over the lottery simplex, and the learner may only ask accept/reject queries. Since binary labels do not reveal utility shortfalls, and such shortfalls are not comparable across stakeholders, we measure violation geometrically: the Euclidean distance, within the affine hull of the simplex, to the stakeholder's normalized acceptance hyperplane. These distances are aggregated using the power mean. Our results characterize exactly which boundary information can be learned from these queries. A deterministic algorithm uses $\mathcal{O}(nm\log(m/\varepsilon))$ queries to recover the normalized boundary whenever violation distances are identifiable from query answers. Otherwise, queries determine the acceptable face but not the rate at which violation grows away from it; this ambiguity is unavoidable. When no ambiguity arises, the aggregate violation objective can be optimized exactly. When it does, we optimize a convex worst-case upper bound objective based on distance to the learned acceptable set and prove an additive loss bound of $\sqrt{2}(|B|/n)^{1/p}$. We also prove structural properties of optimal lotteries, including a support-size bound of $n+1$, and give a limited-budget algorithm with additive-$\alpha$ guarantees. Synthetic experiments illustrate the resulting breadth-depth tradeoff and the effect of the power-mean parameter $p$ on violation distribution.