Learning Unanimously Acceptable Lotteries via Queries
This work addresses the problem of ensuring AI systems are acceptable to all stakeholders in high-stakes deployments, offering query-efficient algorithms that reduce the burden of eliciting individual constraints.
The paper studies the problem of finding a lottery over a finite set of options that is acceptable to all stakeholders, using only binary accept/reject feedback. It provides deterministic and randomized algorithms that either find such a lottery or certify infeasibility, with query complexity that can be significantly lower than full elicitation, and shows that linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable in the worst case.
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.