Metraipolis › archive › dc_f627227da286
Learning Lotteries with Minimal Stakeholder Violations from Membership Queries — arXiv:2610.37828
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.37828
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T06:11:06.220Z
- SHA-256 of the archived text
eb4031ee7133b54462130caaad8bd9f7ddcd01714f4ab674b228bfbb99fcabce- Stable URL of this page
https://metraipolis.com/documento/dc_f627227da286
How to cite
Learning Lotteries with Minimal Stakeholder Violations from Membership Queries — arXiv:2610.37828 — arXiv (en), https://arxiv.org/abs/2610.37828 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f627227da286 (Metraipolis archive dc_f627227da286, sha256 eb4031ee7133b54462130caaad8bd9f7ddcd01714f4ab674b228bfbb99fcabce)
BibTeX
@misc{dcf627227da286,
title = {Learning Lotteries with Minimal Stakeholder Violations from Membership Queries — arXiv:2610.37828},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.37828},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f627227da286; sha256 eb4031ee7133b54462130caaad8bd9f7ddcd01714f4ab674b228bfbb99fcabce},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.37828. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $m$ alternatives for $n$ 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 $0$ or $1$. We then give exact algorithms that run in polynomial time when $m$ is constant, and in quasi-polynomial time when, for a constant $\eta$, some optimal lottery has no accepting agent within $\eta$ 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 $n$, and a linear program gives a polynomial-time method for any $m$. On the other hand, for $m\ge 3$, a deterministic algorithm that queries only $K$ distinct agents cannot guarantee fewer than $n-K$ 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. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno). Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2610.37828 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-31T06:07:08.598Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).