Learning Lotteries with Minimal Stakeholder Violations from Membership Queries

Nicholas Teh; Paul W. Goldberg

cs.LGOct 27, 2026

Learning Lotteries with Minimal Stakeholder Violations from Membership Queries

Authors: Nicholas Teh, Paul W. Goldberg

Organizations: University of Oxford

Abstract

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 $η$ , 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 $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.

Figures & tables

Panel of Figure 1 — Figure 1: Lotteries over three alternatives drawn as points of a triangle with corners $\mathbf{e}_{1},\mathbf{e}_{2},\mathbf{e}_{3}$ . (a) An agent’s acceptable set $A_{i}$ (shaded) is the part of the triangle on one side of a line; the darker strip contains the lotteries that the agent accepts with margin less than $\eta$ . (b) The profile in the proof of Theorem 6.1 when $\widehat{\mathbf{x}}\neq\mathbf{e}_{1}$ : every queried agent accepts exactly the lotteries on the bottom edge, and every unqueried agent accepts only $\mathbf{e}_{1}$ . All unqueried agents reject $\widehat{\mathbf{x}}$ , but every agent accepts $\mathbf{e}_{1}$ .

Method	Agents used	Separated	Near-threshold
Exact minimization on the sample	$k=30$	$6.81$ $(19.24)$	$6.25$ $(15.81)$
Exact minimization on the sample	$k=120$	$1.67$ $(4.22)$	$1.36$ $(3.41)$
Exact minimization on the sample	$k=480$	$0.43$ $(1.40)$	$0.23$ $(0.80)$
LP ( 1 ), $\eta=0.02$	$k=120$	$1.96$ $(5.60)$	$3.60$ $(6.80)$
LP ( 1 ), $\eta=0.05$	$k=120$	$0.53$ $(1.61)$	$9.20$ $(17.82)$
LP ( 1 ), $\eta=0.02$	all $500$	$0.51$ $(1.67)$	$1.86$ $(3.80)$

Table 1: Mean extra rejection rate

(\mathrm{viol}(\widehat{\mathbf{x}})-\mathrm{OPT})/n

in percent, with

95

th percentiles in parentheses.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Work	Domain	Information	Objective	Guarantees
Max-FS and Min-ULR [ Amaldi and Kann, 1995 , Amaldi and Kann, 1998 , Arora et al., 1997 , Amaldi et al., 2003 ]	$\mathbb{R}^{d}$ , general linear systems	Explicit	Maximize satisfied, or minimize unsatisfied, constraints	NP-hardness, approximation algorithms, inapproximability
Max-FS with $0/1$ coefficients [ Elbassioni et al., 2009 ]	Real variables	Explicit	Maximize satisfied constraints	Approximation algorithms and hardness
LP with violations [ Matoušek, 1995 , Chan, 2005 ]	$\mathbb{R}^{d}$ , $d$ fixed	Explicit	Best linear objective when a given number of constraints may be violated	Exact algorithms in fixed dimension
Max-FS with additive slack [ Castiglioni et al., 2023 ]	Simplex	Explicit	Maximize constraints satisfied up to an additive slack	Quasi-polynomial algorithm; lower bound under ETH
Chance-constrained and scenario optimization [ Calafiore and Campi, 2006 , Campi and Garatti, 2008 , Luedtke and Ahmed, 2008 , Pagnoncelli et al., 2009 ]	Convex or general sets	Samples of random constraints	Optimize a cost subject to a small violation probability	Sample sizes for feasibility of sampled solutions
Unanimous lotteries [ Choo et al., 2026b ]	Simplex	Membership queries	A lottery accepted by all agents, or report that none exists	Query upper and lower bounds; NP-hardness of maximizing accepting agents

Appendix

Table 2: Comparison with the closest work. “Explicit” means that all constraints are given as input.

$K$	$10$	$25$	$50$	$100$	$200$	$400$
Separated	$13.01$	$8.62$	$3.77$	$2.11$	$1.23$	$0.58$
Near-threshold	$19.17$	$7.79$	$3.66$	$2.00$	$0.88$	$0.57$

Appendix

Table 3: Mean additive gap

\mathrm{viol}(\widehat{\mathbf{x}})-\mathrm{OPT}

of exact minimization over

K

distinct agents chosen uniformly at random, as a percentage of the worst-case value

n-K

, with

n=500

and

m=3

Multi-Party Multi-Objective Optimization

See all 12 papers

Learning Unanimously Acceptable Lotteries via Queries
Apr 19, 2026Davin Choo, Paul W. Goldberg, Nicholas TehQuery Complexity Learning-Augmented Algorithms
Harvard University, USA · University of Oxford, UK
Smooth Partial Lotteries for Stable Randomized Selection
May 19, 2026Alexander Goldberg, Giulia Fanti, Nihar B. ShahAlgorithmic Stability Algorithmic Fairness
Carnegie Mellon University
Robust AI Evaluation through Maximal Lotteries
Feb 24, 2026Hadi Khalaf, Serena L. Wang, Daniel Halpern +3LLM Evaluation Rank Aggregation
Harvard University

Apr 19, 2026J/K move · Enter open · S save

Learning Unanimously Acceptable Lotteries via Queries

Davin Choo, Paul W. Goldberg, Nicholas Teh

Harvard University, USA · University of Oxford, UK

Query Complexity Learning-Augmented Algorithms Preference Learning Preference Elicitation

Open paper AskPDF 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.

Abstract

Multi-Party Multi-Objective Optimization

Explore similar work

Learning Unanimously Acceptable Lotteries via Queries

Smooth Partial Lotteries for Stable Randomized Selection

Robust AI Evaluation through Maximal Lotteries