pipette
ESEspañol

Learning Lotteries with Minimal Stakeholder Violations from Membership Queries

Nicholas Teh, Paul W. Goldberg

Preprint

In the authors' words

An AI developer often has several candidate versions of a system and can deploy a mixture of them, sending each request to a randomly chosen version, as in A/B testing. Each stakeholder (e.g., a safety team, a regulator, or a customer with private test data) accepts a mixture exactly when its expected performance (e.g., its rate of harmful replies) meets the stakeholder's own standard, which the developer can learn only by asking whether a proposed mixture is acceptable. We model this as choosing a lottery over alternatives for agents, each of whom accepts exactly the lotteries in an unknown halfspace and answers such binary membership queries. While Choo et al. (ICML 2026) sought a lottery that every agent accepts, none may exist when, say, safety and helpfulness requirements conflict, so we minimize the number of rejecting agents. We show that this problem is APX-hard even when all halfspaces are known and all utilities are or . We then give exact algorithms that run in polynomial time when is constant, and in quasi-polynomial time when, for a constant , some optimal lottery has no accepting agent within of its threshold. When only some agents can be queried, optimizing over a uniform sample of agents gives additive and relative guarantees for the whole population, with a sample size that does not depend on , and a linear program gives a polynomial-time method for any . On the other hand, for , a deterministic algorithm that queries only distinct agents cannot guarantee fewer than extra rejections, and this is achievable; in other words, it can guarantee nothing for the agents it does not ask. Small synthetic experiments indicate that our worst-case bounds are conservative on random instances.

Main resultLimitation the authors admit

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 31 pages, full version of paper at NeurIPS 2026