Research
Learning Unanimously Acceptable Lotteries via Queries
arXiv:2604.17505v1 Announce Type: cross Abstract: Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomizati
arXiv:2604.17505v1 Announce Type: cross Abstract: 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.
Related
- Choose Your Battles: Distributed Learning Over Multiple Tug of War Games
- High Probability Guarantees for Random Reshuffling
- Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains
- Tight Bounds for Learning Polyhedra with a Margin
Source: arXiv cs.LG | 2026-04-21