# Learning Unanimously Acceptable Lotteries via Queries

arXiv: https://arxiv.org/abs/2604.17505 · HTML: https://mlsanity.com/paper/2604.17505/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 47 references that are in the map.
- First posted on arXiv 19 Apr 2026.

## Builds on (most cited first, 16 of 16)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Datasheets for Datasets](https://mlsanity.com/paper/1803.09010/) (2018)
- [Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift](https://mlsanity.com/paper/1906.02530/) (2019)
- [Model Cards for Model Reporting](https://mlsanity.com/paper/1810.03993/) (2018)
- [Closing the AI Accountability Gap: Defining an End-to-End Framework for Internal Algorithmic Auditing](https://mlsanity.com/paper/2001.00973/) (2020)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback](https://mlsanity.com/paper/2404.10271/) (2024)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Truthful Aggregation of Budget Proposals](https://mlsanity.com/paper/1905.00457/) (2019)
- [Settling the Score: Portioning with Cardinal Preferences](https://mlsanity.com/paper/2307.15586/) (2023)
- [Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries](https://mlsanity.com/paper/1807.06170/) (2018)
- [Truthful Aggregation of Budget Proposals with Proportionality Guarantees](https://mlsanity.com/paper/2203.09971/) (2022)
- [Project-Fair and Truthful Mechanisms for Budget Aggregation](https://mlsanity.com/paper/2309.02613/) (2023)
- [Halfspaces are hard to test with relative error](https://mlsanity.com/paper/2511.06171/) (2025)

## Built on by (most cited first, 1 of 1)

- [Efficient Ensemble Selection from Binary and Pairwise Feedback](https://mlsanity.com/paper/2605.09588/) (2026)

## Abstract (arXiv)

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.