Learning Unanimously Acceptable Lotteries from Noisy Approval Queries

Randomization can make collective agreement possible even when no deterministic choice satisfies every agent. We study how to find a unanimously acceptable lottery using only noisy binary approval queries, when agents have unknown utilities and acceptance thresholds. Our model allows feedback to become uninformative near acceptance thresholds, making agreement at these boundaries difficult to resolve. We develop algorithms for exact consensus under finite precision and for a robust formulation that allows either answer on borderline instances while preserving unanimous acceptance guarantees. Complementary lower bounds establish the optimal dependence on precision and margin parameters, up to logarithmic factors. We also distinguish finding one acceptable lottery from learning conservative approximations to every agent’s acceptance set. Learning sets that exclude rejected lotteries and retain all lotteries with sufficient margin requires quadratically many queries in the number of alternatives, even when a common lottery with substantial margin is supplied. Checking a proposed lottery with sufficient margin, by comparison, has a query cost independent of that number. We exploit this distinction to develop learning-augmented algorithms that save queries when a predicted lottery is useful while preserving worst-case guarantees for arbitrary predictions. Finally, we establish when exact decisions remain possible without known noise parameters and show how knowledge of the response rule can further reduce query complexity.