Learning Unanimously Acceptable Lotteries via Queries

Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.

When an AI system is ready to be deployed, it often has to pass several approval checks, e.g., safety teams, compliance reviewers, domain experts, and affected communities may each have a minimum standard. Sometimes no single deployment option satisfies everyone, but a randomized mix of option (such as routing most users to one model and some to a safer fallback) might. This paper studies how to find such a mix while asking stakeholders only simple yes/no questions, e.g., "Is this proposed mix acceptable to you?" We design algorithms that either find a mix that everyone approves or prove that the available options cannot satisfy all stakeholders at once. The algorithms avoid learning everyone’s full preferences; they ask for detailed information only from stakeholders whose constraints actually matter, and can use imperfect predictions to reduce the number of questions further. We also prove limits showing that some questioning is unavoidable. These results help clarify the information cost of conservative AI deployment decisions, where the goal is not to maximize average satisfaction but to ensure that every required safety or governance bar is met.