Learning Lotteries with Minimal Stakeholder Violations from Membership Queries

1 Introduction

• When safety, helpfulness, and regulatory thresholds conflict, no mixture may satisfy everyone, motivating MIN-VIOL’s objective of minimizing rejecting agents.A strict version and a lenient version can jointly meet two standards, while adding a stricter regulator’s cap makes all three requirements incompatible.Source: §1 · pp. 1–2
• Stakeholders reveal only yes-or-no answers to proposed lotteries, and the cost of each answer can restrict queries to a subset of agents.A customer may withhold private test data, while an answer may require an evaluation run or human review.Source: §1 · p. 2

1.1 Our Results

• MIN-VIOL is APX-hard even with full information and binary utilities, ruling out a PTAS unless P = NP.The result strengthens prior NP-hardness for maximizing the number of accepting agents [Choo et al., 2026b].Source: §1.1 · p. 2
• With constant m, MIN-VIOL is exactly solvable in polynomial time; with a constant margin η at an optimum, it is solvable in quasi-polynomial time.The latter condition requires that no accepting agent at an optimal lottery lies within η of its threshold.Source: §1.1 · p. 2
• Uniformly sampling agents gives additive and relative population guarantees with sample sizes independent of n for a fixed error target.A linear program also gives a polynomial-time method for any m, with a stronger guarantee when few agents are barely satisfied.Source: §1.1 · pp. 2–3
• Without random sampling, for m ≥3, querying K distinct agents can leave n −K more rejections than optimal, and this worst-case bound is achievable.Small synthetic experiments found fewer than 10 extra rejections on average when sampling 120 of 500 agents; the n −K worst case arose only in the lower-bound construction.Source: §1.1 · p. 3

1.2 Related Work

• Related work studies unanimity queries [Choo et al., 2026b], full-information constraint optimization, and preference aggregation; this paper instead minimizes rejections from accept/reject feedback.Its lottery problem is a restricted maximum feasible subsystem, with hidden constraints distinguishing it from settings where preferences or constraints are inputs.Source: §1.2 · p. 3

2 Preliminaries

• A lottery is a probability vector over m alternatives, and its coordinates specify the probability assigned to each alternative.The pure lottery on alternative s_j is the standard basis vector e_j.Source: §2 · p. 4
• Each agent accepts lotteries whose expected utility meets a threshold, making its acceptable set a halfspace of the probability simplex.Utilities and thresholds are normalized; degenerate agents, who accept all or no lotteries, are excluded.Source: §2 · p. 4
• A membership query gives one agent a proposed lottery and returns only whether that agent accepts it; it reveals no utility or threshold.The text assumes a known grid for normalized utility-threshold pairs only when stating explicit query budgets or certain running times.Source: §2 · p. 4
• MIN-VIOL minimizes the number of agents rejecting a lottery, and an optimum exists.A mixed lottery can outperform every pure lottery: in the example, one mixture is rejected by one agent, while every pure lottery is rejected by at least two.Source: §2 · p. 4
• Expected quantities such as access, service, safety, or loss combine linearly when an alternative is selected at random.The paper identifies this as the standard cardinal baseline in random assignment and probabilistic social choice [Hylland and Zeckhauser, 1979, Brandt, 2017].Source: §2 · p. 4

• MIN-VIOL is APX-hard even with binary utilities, and has no PTAS unless P = NP.The result applies when all normalized agent pairs are known.Source: §3 · p. 5
• The reduction maps each cubic-graph vertex to an alternative and each edge to q² agents, linking violated-agent counts to vertex-cover size.A vertex cover yields a lottery with exactly its size in violations, while an α-approximation for MIN-VIOL gives an α-approximation for MINIMUM VERTEX COVER on cubic graphs.Source: §3 · p. 5
• An extra alternative absorbs unassigned probability, making vertex-cover lotteries feasible and ensuring the pure extra-alternative lottery violates only the q vertex agents.This construction makes violating an edge agent never worthwhile.Source: §3 · p. 5
• The theorem rules out a PTAS, but not every constant-factor approximation or an additive guarantee matching the sampling results.It concerns multiplicative approximation with full information; the paper leaves stronger inapproximability for lottery instances open.Source: §3 · p. 5

4.1 A Constant Number of Alternatives

• For constant m, enumerating simplex vertices gives an exact algorithm running in O(m^(3+nm)), polynomial in n for each fixed m.Its exponent grows with m, so it is XP rather than FPT in m.Source: §4.1 · p. 6

4.2 Few Alternatives Under a Margin Condition

• If an optimal lottery has no accepting agent within margin η of its threshold, an optimal lottery uses at most ⌈log(2n)/(2η²)⌉ alternatives.Sampling alternatives and applying Hoeffding's inequality ensures all agents' expected utilities fall by at most η; only agents accepted within margin η can become violated.Source: §4.2 · p. 6
• For every integer s ≥ 1, a lottery minimizing viol among those using at most s alternatives is computable in time (m(n + s))^O(s); the paper also gives viol(bx) ≤ OPT + |Bη(x*)| for every optimal lottery x*.The lottery bx is optimal if Bη(x*) = ∅ for some optimal lottery x*.Source: §4.2 · p. 6

4.3 Few Violations

• When the allowed violation count v is small, at most m^v · poly(n, m) LP feasibility checks decide feasibility and return a lottery, making the problem FPT in (v, m).The algorithm branches on agents from a small infeasible subfamily, found using Helly's theorem.Source: §4.3 · p. 7
• Parameterizing by v alone is W[2]-hard, even with binary utilities, unless FPT = W[2].The hardness reduction is from HITTING SET.Source: §4.3 · p. 7
• For m = 2, MIN-VIOL reduces to finding a point contained in the largest number of intervals, solvable in O(n log n) time.Source: §4.3 · p. 7

5 Limited Queries: Learning from Sampled Agents

• With k ≥ m uniformly sampled agents, every sample-minimizing lottery has at most OPT + 8n√((m log(2ek/m) + log(8/δ))/k) violations with probability at least 1 − δ.The guarantee assumes exact minimization on the sample; the sampled rejection sets have VC dimension at most m.Source: §5 · pp. 7–8
• When OPT ≥ ρn, the sample-minimizing lottery has at most (1 + ζ)OPT violations with probability at least 1 − δ, for k ≥ C(m log(1/ρ) + log(1/δ))/(ζ²ρ).The relative guarantee follows from a relative-error bound; exact sample minimization is available when m is constant.Source: §5 · p. 8

5.1 A Polynomial-Time LP for Arbitrary m

• For arbitrary m, the LP minimizes a convex penalty that is zero for acceptance with margin η, one at the boundary, and greater than one for rejection.The penalty is linearized over sampled agents; repeated copies can be merged with weights.Source: §5.1 · p. 8
• With probability at least 1 − δ, the LP lottery's violations are bounded by (1 + 1/η)viol(x) + |Bη(x)| + (Cn/η)√((log m + log(1/δ))/k), for every lottery x.The guarantee is strongest when a good lottery has few violations and few agents accepted within margin η of their thresholds.Source: §5.1 · p. 8
• Using all agents removes the sampling term, but the factor 1 + 1/η remains because penalties for violated agents are uncapped; capping them would make the objective nonconvex.Source: §5.1 · p. 8
• Exact sample minimization avoids the LP's margin penalty when affordable, while the LP runs in polynomial time for every m without a margin condition and has a sampling term growing with log m.Source: §5.1 · p. 8

• An adversary can answer as if queried agents accept exactly lotteries with x3 = ··· = xm = 0, then choose a profile where all unqueried agents reject the algorithm's output.In that profile, every agent accepts the same pure lottery e1 or e2, so OPT = 0.Source: §6 · p. 9
• For m ≥ 3, any deterministic algorithm querying at most K distinct agents has worst-case additive gap exactly n − K.The matching upper bound comes from minimizing violations over a fixed set of K agents; the lower bound holds regardless of how many queries are spent on them or how adaptively they are chosen.Source: §6 · p. 9
• After partial queries, counting agents who reject under every versus some consistent profile bounds each lottery's violations and the unknown optimum.Choosing the lottery that minimizes the upper count gives an additive gap no larger than the difference between the optimum bounds; each unqueried agent adds one to that difference.Source: §6 · p. 9

7 Synthetic Experiments

• 120-agent exact minimization was within 2% of the optimum on average, and each fourfold increase in sample size reduced mean extra rejection rate by about 3.9–5.9×.The reduction was faster than the factor of 2 suggested by Theorem 5.1’s 1/k rate.Source: §7 · pp. 9–10, Table 1 · p. 10
• With K = 100 queried agents, uniform sampling produced mean additive gaps of 8.46 and 7.99 agents, versus the worst-case n − K = 400.Across tested K values, mean gaps were about 0.6%–19% of n − K; the lower-bound construction reached n − K for every tested K.Source: §7 · p. 10
• For η = 0.05, the margin-based method beat exact minimization on 120 samples in the separated setting, but more than doubled extra rejections in the near-threshold setting.The near-threshold setting had every agent accepting the planted lottery within the 0.05 margin.Source: §7 · p. 10
• With n = 1000, m = 500, and η = 0.15, sampling 169 alternatives caused no new rejections in 480 trials when all agents accepted the starting lottery with margin at least η.When 20% accepted with margin below η, the mean new rejection rate was 1.19% and the 95th percentile was 1.70%, versus a theorem allowance of 20%.Source: §7 · p. 10

8 Conclusion

• The paper studies minimizing rejecting agents: the problem is APX-hard, admits exact algorithms under additional structure, has population guarantees from uniform samples, and has a tight deterministic guarantee based on queried-agent count for m ≥ 3.The deterministic worst-case bound is determined by the number of distinct agents queried.Source: §8 · p. 10
• The halfspace model covers thresholds on expected quantities but not variance-dependent, ambiguity-sensitive, or nonlinearly probability-weighted acceptability; several algorithms rely directly on linearity.Theorem 5.1 extends to other rejection-set models with bounded VC dimension, whereas Theorems 4.1, 4.2, and 5.3 do not automatically extend to general convex acceptable sets.Source: §8 · p. 10

A Additional Related Work

• Related work differs in objective and information: distance-based violation measures distinguish severity, while this paper counts rejections and asks binary acceptability queries rather than eliciting utilities or comparisons.The distance-based power mean is convex once relevant boundaries are known; the rejection-count problem is APX-hard even with full information.Source: A Additional Related Work · pp. 15–16

B.1 On the linear acceptability assumption

• Acceptable sets are assumed to be halfspaces, but agents need not report numerical utilities; the decision maker sees only accept/reject answers to proposed lotteries.The hidden set is defined by expected score meeting an agent-specific threshold.Source: §B.1 · p. 17

B.2 Normalization and finite precision

• Normalization gives a unique normalized utility-threshold pair for acceptable sets with nonempty relative interior, while boundary-only sets are simplices over a unique subset of alternatives.A finite grid is used for explicit query budgets and running times, not to discretize the output lottery.Source: §B.2 · p. 18

C Proof of Theorem 3.1

• The reduction from cubic-graph minimum vertex cover preserves approximation: every constructed lottery yields a vertex cover no larger than its violation count, and the optimum violation count equals the graph’s minimum cover size.Consequently, a PTAS for MIN-VIOL would give a PTAS for cubic-graph vertex cover, so MIN-VIOL is APX-hard even with binary utilities.Source: C Proof of Theorem 3.1 · p. 19

D.1 Proof of Theorem 4.1

• An optimal lottery can be chosen as a vertex of the polytope satisfying its accepted agents; enumerating systems of m tight constraints and retaining the feasible candidate with fewest violations finds an optimum.The number of systems is at most (n + m)^(m−1), so the algorithm runs in polynomial time for constant m.Source: §D.1 · pp. 19–20

D.2 Proof of Theorem 4.2

• Sampling alternatives from an optimal lottery yields a lottery with at most sη alternatives whose violations are bounded by the optimum plus the number of accepted agents within η of threshold.If an optimal lottery has no such near-threshold accepting agents, the sparse lottery is also optimal.Source: §D.2 · p. 21

D.3 Proof of Proposition 4.3

• Searching over subsets of at most s alternatives and solving the restricted violation problem on each subset finds the best lottery using at most s alternatives.The resulting search takes time (m(n + s))^O(s).Source: §D.3 · p. 21

D.4 Proof of Corollary 4.4

• Searching over lotteries supported on at most sη alternatives returns a lottery with at most OPT + |Bη(x*)| violations, and is optimal when the optimal lottery has no accepting agents within η of threshold.The search runs in the time bound of Proposition 4.3 with s = sη.Source: §D.4 · p. 21

E.1 Exact optimization on a line segment: m = 2

• With two alternatives, each agent’s acceptable lotteries form an interval, so sorting interval endpoints and scanning for maximum overlap finds an optimum in O(n log n) time.The overlap count is the number of accepting agents at a lottery.Source: §E.1 · pp. 21–22

E.2 Proof of Theorem 4.5

• For a violation budget v, Helly’s theorem supplies an infeasible subset of at most m agents; branching on which agent to remove decides whether a lottery with at most v violations exists.The algorithm is fixed-parameter tractable in (v, m), using O(m^v) recursion-tree nodes and polynomial-time LP checks.Source: §E.2 · pp. 23–24

E.3 Proof of Theorem 4.6

• The constructed MIN-VIOL instance is a yes-instance exactly when the HITTING SET instance has a hitting set of size at most v, yielding W[2]-hardness parameterized by v.The reduction also carries over to the search version: returning a qualifying lottery would decide the decision problem.Source: §E.3 · p. 25

F Omitted Proofs from Section 5

• For each lottery, the proof compares its population rejection fraction with its sampled rejection fraction; the sampled optimization minimizes the latter.The proof treats sampled agents with their multiplicities.Source: F Omitted Proofs from Section 5 · p. 25

F.1 Proof of Theorem 5.1

• With probability at least 1−δ, the sampled minimizer has at most OPT + 2αn violations, where α = 4√((m log(2ek/m) + log(8/δ))/k).The proof bounds the uniform difference between sampled and population rejection fractions, then applies it to both the population optimum and sampled minimizer.Source: §F.1 · p. 25

F.2 Proof of Theorem 5.2

• If OPT ≥ ρn and k meets the stated sample-size condition, the sampled minimizer has at most (1+ζ)OPT violations with probability at least 1−δ.The proof uses a relative-error bound for lotteries rejected by few agents.Source: §F.2 · p. 26

F.3 Proof of Theorem 5.3

• The penalty ℓ(i,x) upper-bounds the indicator that agent i rejects lottery x, and minimizing the LP objective is equivalent to minimizing the sample-average penalty.The penalty is max{0, (τ_i+η−U_i(x))/η}.Source: §F.3 · p. 26
• With probability at least 1−δ, the sample and population average penalties differ uniformly by at most (C/η)√((log m + log(1/δ))/k).The proof derives this uniform bound using the Rademacher complexity of the convex hull of alternative-specific score functions.Source: §F.3 · p. 26
• For every lottery x, the returned lottery has at most (1+1/η)viol(x) + |B_η(x)| + 2κn violations, where κ is the sample-to-population error bound.If the LP uses all n agents, κ=0 and the same argument gives the full-information bound.Source: §F.3 · p. 27

G Converting Sample Sizes into Query Budgets

• With Q queries, sampling and recovering k=floor(Q/T_ε) agents supports exact sample optimization in polynomial time for constant m or an LP in polynomial time for any m, with the respective population guarantees.The sample-based procedures use at most Q queries.Source: G Converting Sample Sizes into Query… · p. 27

H.1 Proof of Theorem 6.1

• For a deterministic algorithm querying at most K agents, a consistent profile can make its output reject every unqueried agent while another lottery has zero violations.The construction preserves the algorithm's query history and yields at least n−|M| rejections on its output, where M is its queried set.Source: §H.1 · pp. 27–28

H.2 Proof of Theorem 6.2

• The worst-case excess violations for deterministic algorithms querying at most K agents is n−K: querying a fixed K-agent set and minimizing its rejections achieves the upper bound, and a constructed profile matches it.The lower-bound profile has OPT=0.Source: §H.2 · p. 28

I.1 Bounds from observed queries

• After any consistent query history, the unknown optimum lies between L(h) and H(h), and minimizing the lower violation count gives excess at most H(h)−L(h); this uncertainty gap cannot increase with more answers.An agent with no observed answers contributes a gap of one for every lottery, so K queried agents imply H(h)−L(h)≥n−K.Source: §I.1 · p. 29
• For a fixed lottery x, its exact worst-case additive gap over profiles consistent with h is max_z D_h(x,z), so minimizing that maximum gives the best guaranteed gap after the history.The paper suggests choosing the next query to reduce this objective directly.Source: §I.1 · pp. 29–30

Populations

• Each of 40 populations had n = 500 agents and m = 3 alternatives; 425 accepted the planted lottery, while 75 rejected it.There were 20 populations in each of two settings; the planted lottery was optimal in every near-threshold population, with OPT = 75, and OPT ranged from 71 to 75 in the separated setting.Source: J Details of the Synthetic Experiments · p. 30

Computing the optimum

• The exact solver and mixed-integer program agreed on optimal values for all 40 populations and all 240 samples of size k = 120.The exact solver enumerated candidate lotteries from simplex edges and agent acceptance boundaries.Source: J Details of the Synthetic Experiments · p. 30

Sampling and exact minimization

• With k = 120 sampled agents, exact minimization had a mean extra rejection rate below 2%, although the explicit bound exceeded n for every δ ∈ (0, 1).The experiment used six independent uniform-with-replacement samples per population and sample size, and measured the gap across all 500 agents.Source: J Details of the Synthetic Experiments · p. 30

The LP

• In the separated setting, increasing η from 0.02 to 0.05 lowered the LP mean extra rejection rate from 0.51% to 0.28% on all agents and from 1.96% to 0.53% on samples.In the near-threshold setting, the corresponding rates rose from 1.86% to 5.22% on all agents and from 3.60% to 9.20% on samples; exact minimization is margin-independent.Source: J Details of the Synthetic Experiments · p. 30

Querying K agents

• For K = 100 queried agents, the mean gap was 8.46 agents in the separated setting and 7.99 in the near-threshold setting, or 2.11% and 2.00% of n − K.Across runs, mean gaps ranged from 0.57% to 19.17% of n − K; the largest single-run gap was 202 agents, or 41% of n − K, at K = 10.Source: J Details of the Synthetic Experiments · p. 31, Table 3 · p. 31

Few alternatives

• With 169 sampled alternatives, no new rejection occurred in 480 trials when Bη(x) was empty; with 200 agents near thresholds, the mean new rejection rate was 1.19%.The theorem allows up to 20% in the harder setting; using 50 alternatives yielded a 2.19% mean new rejection rate there.Source: J Details of the Synthetic Experiments · p. 31

Implementation and compute

• All experiments used instances with n ≤ 1000 and m ≤ 500 and took about 2 minutes on a 2-vCPU, 8-GB cloud virtual machine.About 80 seconds were spent on the mixed-integer check.Source: J Details of the Synthetic Experiments · p. 31