Paper deep dive
Learning Unanimously Acceptable Lotteries via Queries
Davin Choo, Paul W. Goldberg, Nicholas Teh
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 4/27/2026, 8:04:44 AM
Summary
The paper investigates the problem of finding a 'unanimously acceptable lottery' in high-stakes AI deployments where multiple stakeholders impose different minimum acceptability thresholds. The authors study a query-based model where an algorithm proposes randomized distributions (lotteries) over a finite set of alternatives and receives binary (accept/reject) feedback. The research provides deterministic and randomized algorithms to either find a lottery that satisfies all stakeholders or certify that no such lottery exists. Key contributions include the development of the 'LearnHyperplane' subroutine for single-agent elicitation, the analysis of query complexity (showing linear dependence on the number of stakeholders and logarithmic dependence on precision), and the introduction of learning-augmented algorithms that use advice (like predicted binding stakeholders or promising lotteries) to improve efficiency while maintaining worst-case guarantees.
Entities (9)
Relation Signals (7)
Stakeholder → imposes → Acceptability Threshold
confidence 100% · each stakeholder evaluates candidate deployments through their own scalar yardstick... together with a personal acceptability threshold
Paul W. Goldberg → isaffiliatedwith → University of Oxford
confidence 100% · Paul W. Goldberg University of Oxford, UK
Davin Choo → isaffiliatedwith → Harvard University
confidence 100% · Davin Choo Harvard University, USA
Lottery → isevaluatedby → Stakeholder
confidence 100% · each stakeholder evaluates candidate deployments through their own scalar yardstick
Lottery → isevaluatedby → Stakeholder
confidence 100% · the algorithm proposes lotteries and receives only binary accept/reject feedback.
LearnHyperplane → recovers → Acceptability Halfspace
confidence 100% · Algorithm 1 (LearnHyperplane) learns an explicit halfspace description of agent i’s acceptable set.
LearnHyperplane → recovers → Acceptability Halfspace
confidence 100% · LearnHyperplane(i) that recovers an agent’s acceptability halfspace on the simplex
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2604.17505v1
- Canonical: https://arxiv.org/abs/2604.17505v1
Trouble viewing inline? Open PDF directly →
Full Text
204,519 characters extracted from source content.
Expand or collapse full text
Learning Unanimously Acceptable Lotteries via Queries Davin Choo Harvard University, USA Paul W. Goldberg University of Oxford, UK Nicholas Teh University of Oxford, UK 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. 1 Introduction In high-stakes AI deployments, before release, systems are checked against a collection of requirements: internal safety review, policy and compliance constraints, domain expert criteria, and often structured human evaluation (Gebru et al., 2021; Government of Canada, 2020; Mitchell et al., 2019; Raji et al., 2020; US Department of Commerce, 2023; UK Department for Science, Innovation and Technology, 2024). In many settings, these requirements act as gates rather than soft preferences: failure on a single critical check is enough to block deployment (Anthropic, 2025; European Parliament and Council of the European Union, 2024; OpenAI, 2025). This kind of decision process is conservative by design: it is meant to ensure that no required standard is violated, even when different teams (or affected stakeholders) focus on different risks (Government of Canada, 2020; US Department of Commerce, 2023). A second, often overlooked aspect is that a deployment choice determines a distribution of outcomes rather than a single outcome (Sutton and Barto, 2018). Even a fixed model run under a fixed policy produces variable behavior due to environmental uncertainty and stochastic execution (Ovadia et al., 2019; Quiñonero-Candela et al., 2008). Crucially, considering distributions (lotteries) rather than deterministic choices convexifies the feasible space. In many governance settings, no single monolithic model configuration may satisfy every stakeholder’s constraints simultaneously. However, a randomized mixture (e.g., routing 90% of traffic to a high-performance but high-risk model and 10% to a highly robust fallback) may satisfy the aggregate risk thresholds of all parties. Modern deployments frequently include such explicit mixing mechanisms (e.g., routing, fallback modes) (Amazon Web Services, 2023). From a governance perspective, the problem therefore becomes selecting a distribution over options that clears all safety bars. In such settings, it is natural that different stakeholders impose different minimum standards. This can often be understood in practice as operational risk thresholds reflecting different risk appetites (US Department of Commerce, 2023). A compliance group may insist on a hard constraint; a safety team may require a baseline level of robustness; an impacted population may care about guarantees that do not align with average-case performance. We formalize this by letting each stakeholder evaluate candidate deployments through their own scalar yardstick (which one can read as a utility, a safety score, or an inverted risk score), together with a personal acceptability threshold that encodes their minimum bar. Crucially, these standards are typically assessed through coarse feedback (Government of Canada, 2020, 2025). Approval processes do not ask each stakeholder to provide a complete utility function over all possible outcomes. They ask whether a proposed deployment is acceptable. It is also common that acceptability is judged relative to a reference point: the current system in production, a previously approved policy, or a conservative baseline. This view provides a simple interpretation of a stakeholder’s “minimum bar”: approval means the proposal meets or exceeds what would otherwise be deployed, according to that stakeholder’s criterion. Our work studies the resulting feasibility problem: given a menu of candidate deployments and stakeholders who respond only with accept/reject judgments, can we find a deployment choice that everyone approves (i.e., a unanimously acceptable choice), or certify that no such choice exists? A certificate of infeasibility is meaningful here: it says the current menu is inadequate to satisfy all thresholds simultaneously, so the correct response is to modify the design space (e.g., add mitigations or introduce safer operating modes) rather than to search longer for a nonexistent compromise (Anthropic, 2025; European Parliament and Council of the European Union, 2024; OpenAI, 2025; US Department of Commerce, 2023). Our focus is the information cost of reaching such a conservative decision. We work in a query-based model in which the algorithm proposes candidate randomized deployment choices and observes only yes/no acceptability feedback from stakeholders. The goal is to minimize the number of such queries needed to either produce a universally approved choice or correctly conclude infeasibility. 1.1 Our Results We study the following query feasibility problem. There are n agents and m alternatives. The algorithm proposes lotteries ∈Δ(S)x∈ (S) and may query any agent i with a query Query(i,)∈True,FalseQuery(i,x)∈\ True, False\ indicating whether ⟨i,⟩≥τi _i,x ≥ _i, where (i,τi)(u_i, _i) are unknown to the algorithm. The goal is to either (i) output a unanimously acceptable lottery ∈⋂i=1nix∈ _i=1^nA_i, or (i) correctly certify infeasibility. Single agent elicitation. We give an exact procedure LearnHyperplane(i)LearnHyperplane(i) that recovers an agent’s acceptability halfspace on the simplex using only accept/reject queries using (mlog(1/ε))O(m (1/ )) membership queries and returns either AcceptAll, RejectAll, or a linear inequality equivalent to ⟨i,⟩≥τi _i,x ≥ _i for all ∈Δ(S)x∈ (S) (Lemmas 3.1 and 3.2). Deterministic multi-agent algorithm. Building on LearnHyperplaneLearnHyperplane, we give an adaptive deterministic algorithm that learns an agent’s constraint only when it is violated by the current candidate lottery. It always outputs a unanimously acceptable lottery when one exists, and otherwise outputs Null, using (n2+nmlog(1/ε))O (n^2+nm (1/ ) ) queries in the worst case (Theorem 3.3). Randomization reduces hyperplane learning. We adapt a Clarkson-style sampling/reweighting approach for low-dimensional linear programming to our query model. The resulting randomized algorithm is always correct and uses [(nmlogn+minn,m3logn⋅mlog(1/ε))]E[O(nm n+ \n,\,m^3 n\· m (1/ ))] queries (Theorem 3.4). In particular, when n≫m3logn m^3 n, it learns only a vanishing fraction of agents’ constraints in expectation, while preserving correctness. Lower bounds. We show that any (deterministic or randomized) algorithm that is always correct must make Ω((n−minn,m)+(minn,m−1)log(1/ε)) ((n- \n,m\)+( \n,m\-1) (1/ )) queries in the worst case, even for binary utilities (Theorem 4.1). Additionally, even for a single agent (n=1n=1), Ω(m) (m) queries are necessary in the worst case (Theorem 4.2). These bounds explain the unavoidable linear dependence on n and logarithmic dependence on 1/ε1/ . Learning-augmented elicitation. Finally, we give learning-augmented variants 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. With a predicted permutation σ σ over agents, the deterministic algorithm uses ((n+mlog(1/ε))R(σ^))O((n+m (1/ ))\,R( σ)) queries, where R(σ^)R( σ) is the number of record agents encountered under that order (Theorem 5.1). For the randomized algorithm, we bias the initial sampling weights toward earlier agents in σ σ and obtain an expected query complexity of (nmμ+minn,m3μ⋅mlog(1/ε))O(nmμ+ \n,m^3μ\· m (1/ )), where μ=logE(σ^)+loglognμ= E( σ)+ n and E(σ^)E( σ) is the smallest prefix length that contains a valid witness set (Theorem 5.2). Additionally, given a predicted lottery x, we warm-start the single agent turning point searches inside LearnHyperplaneLearnHyperplane, reducing the cost of learning an agent’s halfspace to (m+mlog(1+δmax,i(^)/ε2))O(m+m \! (1+ _ ,i( x)/ ^2 )) queries (Theorem 5.3), while preserving worst-case bounds when the prediction is poor. We provide accompanying lower bounds on the minimum number of queries required even in the presence of each of these predictions. 1.2 Related Work Preference elicitation and query learning. Our setup is closely related to preference elicitation, which studies how to ask as few questions as possible to make a decision without fully learning preferences (e.g., in auctions or voting). A classic connection between elicitation and computational learning is that elicitation can be viewed as querying multiple “concepts” with the goal of producing an optimal example rather than reconstructing each concept (Blum et al., 2004). Subsequent work develops a variety of query types and policies for eliciting complex preferences and utilities (e.g., Boutilier, 2002; Conen and Sandholm, 2001). Our model aligns in this spirit: our goal is not to recover (i,τi)(u_i, _i), but to find any lottery satisfying all agents’ constraints. The technical distinction is that we study a structured continuous decision space (the simplex over m alternatives) with binary accept/reject queries about lotteries, and we provide worst-case query bounds with explicit dependence on the required numerical precision ε . Query learning of halfspaces and geometric concepts. At a geometric level, each agent induces a halfspace over the (m−1)(m-1)-simplex via an acceptability constraint ⟨i,⟩≥τi _i,x ≥ _i. Our single-agent subroutine that recovers an agent’s acceptability boundary is related to classical query learning of geometric concepts, including exact learning on discretized domains and membership-query learning of polytopes where the precision of query points is treated as a resource (Angluin, 1988; Bshouty et al., 1998a, b; Goldberg and Kwek, 2000). The key difference is the learning objective and the multi-agent structure: most prior work targets identifying an unknown concept for a single oracle, whereas we have n distinct (unknown) halfspaces and only need to find one point in their intersection (or prove emptiness). This distinction is what enables algorithms that learn only a small subset of “constraining” agents’ hyperplanes in the worst case, rather than learning all n constraints, at least in expectation. Learning-augmented algorithms. Learning-augmented algorithms (also called algorithms with predictions/advice) aim to exploit imperfect predictions without sacrificing worst-case guarantees, typically establishing consistency (good predictions help), robustness (bad predictions do not hurt asymptotically), and often smoothness (graceful degradation with prediction error) (e.g., Lykouris and Vassilvitskii, 2021; Kumar et al., 2018; Rohatgi, 2020). We adapt this framework to elicitation for unanimous acceptability by considering predictions natural to governance pipelines—an ordering of “most constraining” agents, or a good candidate lottery—and analyzing how these predictions reduce the number of expensive hyperplane learning steps. Compared to the dominant learning-augmented literature (which is largely online/metric/optimization focused), our setting highlights a different prediction target: advice about which constraints will be active (or which candidate point is near the feasible region) in a feasibility with queries problem. 2 Model and Preliminaries For any positive integer z, denote [z]:=1,…,z[z]:=\1,…,z\. Let N=[n]N=[n] be the set of n agents,111These are the stakeholders as mentioned in the introduction. and S=s1,…,smS=\s_1,…,s_m\ be the set of m alternatives. A lottery over S is a probability vector =(x1,…,xm)∈Δ(S)x=(x_1,…,x_m)∈ (S), where Δ(S):=∈ℝ≥0m:∑j=1mxj=1 (S):=\x _≥ 0^m: _j=1^mx_j=1\ is the (m−1)(m-1)-simplex. Let je_j denote the pure lottery placing unit mass on sjs_j. Each agent i∈Ni∈ N has an (unknown) utility (or value) ui(sj)∈[0,1]u_i(s_j)∈[0,1] for each alternative sj∈Ss_j∈ S,222We can also denote an agent’s utility vector as iu_i, where the j-th entry is ui(sj)u_i(s_j). and an (unknown) threshold τi∈(0,1] _i∈(0,1].333We assume without loss of generality that no agent has threshold 0, otherwise they can trivially be ignored. The expected utility of lottery x for agent i is Ui()=∑j=1mxjui(sj)U_i(x)= _j=1^mx_j\,u_i(s_j). Agent i accepts x if and only if Ui()≥τiU_i(x)≥ _i. Define the acceptable region/set i:=∈Δ(S):⟨i,⟩≥τiA_i:=\x∈ (S): _i,x ≥ _i\, i.e., the intersection of the simplex with a halfspace. A lottery is unanimously acceptable if and only if ∈⋂i∈Nix∈ _i∈ NA_i. Expected utility and acceptability thresholds. Given we are analyzing the output as lotteries over alternatives, we need a principled way to evaluate randomization. The standard modeling choice is the von Neumann-Morgenstern expected utility framework: under mild rationality axioms on preferences over lotteries, an agent’s lottery preferences admit a cardinal utility representation that is linear in probabilities, i.e., the agent behaves as if maximizing expected utility (von Neumann and Morgenstern, 1944). This assumption is very common in algorithmic decision-making. For instance, Markov decision processes and reinforcement learning typically define the objective as maximizing expected cumulative reward/return under a (possibly stochastic) policy (Puterman, 1994; Sutton and Barto, 2018). In game theory, agents evaluate mixed strategies via expected utilities, and equilibrium notions (best responses, Nash equilibria) are defined in terms of expected payoffs (Nash, 1950; Osborne and Rubinstein, 1994). We further adopt an agent-specific acceptability threshold τi _i and declare a lottery x acceptable to agent i if and only if Ui()≥τiU_i(x)≥ _i. Thresholds capture a common “minimum standard” view of decision-making (Simon, 1955), and they match the way safety, compliance, and stakeholder constraints are modeled in modern ML/AI: one often maximizes expected performance subject to inequality constraints (e.g., constrained MDPs/safe or constrained RL), rather than folding all desiderata into a single scalar reward (Altman, 1999; García and Fernández, 2015). In multi-agent mechanism design, analogous inequalities appear as individual rationality (or participation) constraints requiring each agent’s expected utility to exceed an outside option (Myerson, 1981; Nisan et al., 2007). In our setting, τi _i plays exactly this role of a personalized minimum bar, so unanimity corresponds to satisfying all agents’ constraints without requiring interpersonal utility comparisons. Example 2.1. Let m=2m=2. Suppose agent 11 has 1=(1,0),τ1=0.6u_1=(1,0), _1=0.6, so i=∈Δ(S):x1≥0.6A_i=\x∈ (S):x_1≥ 0.6\. Suppose agent 22 has 2=(0,1),τ2=0.6u_2=(0,1), _2=0.6, so 2=∈Δ(S):x2≥0.6=∈Δ(S):x1≤0.4A_2=\x∈ (S):x_2≥ 0.6\=\x∈ (S):x_1≤ 0.4. Then 1∩2=∅A_1 _2= , and no unanimously acceptable lottery exists. Query model. The algorithm does not observe (i,τi)(u_i, _i). It may issue membership queries of the form Query(i,)Query(i,x) where i∈Ni∈ N and ∈Δ(S)x∈ (S). The oracle returns True if and only if ∈ix _i, and False otherwise. The query complexity is the number of oracle calls. Problem (Unanimous Acceptability via Queries) Given n,mn,m, and query access to agents, output either: (i) a lottery ∈Δ(S)x∈ (S) such that Ui()≥τiU_i(x)≥ _i for all i∈Ni∈ N, or (i) Null, certifying that ⋂i∈Ni=∅ _i∈ NA_i= . Deterministic algorithms must be correct on all instances. Our randomized algorithms are always correct; randomness only affects the number of queries. We analyze the expected number of queries they use. Remark 2.2. A natural relaxation to the unanimity objective is to maximize the number of accepting agents. However, we can show that even with an unlimited query budget (i.e., to obtain explicit access to (i,τi)(u_i, _i)), this optimization problem is NP-hard (see Appendix B.3 for a discussion). We now illustrate the setting with a short, concrete example. Example 2.3. Fix m=3m=3 alternatives S=s1,s2,s3S=\s_1,s_2,s_3\ and ε=0.1 =0.1. Consider three agents with utilities and thresholds: iui(s1)ui(s2)ui(s3)τi11.00.60.20.620.21.00.50.730.20.21.00.3 array[]c|c|ci&u_i(s_1)&u_i(s_2)&u_i(s_3)& _i\\ 1&1.0&0.6&0.2&0.6\\ 2&0.2&1.0&0.5&0.7\\ 3&0.2&0.2&1.0&0.3 array For a lottery =(x1,x2,x3)∈Δ(S)x=(x_1,x_2,x_3)∈ (S), the acceptability sets i=∈Δ(S):⟨i,⟩≥τiA_i=\x∈ (S): _i,x ≥ _i\ are following halfspaces intersected with the simplex: 1A_1 (x1+0.6x2+0.2x3≥0.6x_1+0.6x_2+0.2x_3≥ 0.6); 2A_2 (0.2x1+x2+0.5x3≥0.70.2x_1+x_2+0.5x_3≥ 0.7); 3A_3 (0.2x1+0.2x2+x3≥0.30.2x_1+0.2x_2+x_3≥ 0.3). Observe that no pure lottery is unanimously acceptable (e.g., 1e_1 is rejected by agent 22, 2e_2 by agent 33, and 3e_3 by agent 11), but the lottery ∗=(0.25,0.60,0.15)x^*=(0.25,0.60,0.15) is unanimously acceptable since U1(∗)=0.64≥0.6U_1(x^*)=0.64≥ 0.6, U2(∗)=0.725≥0.7U_2(x^*)=0.725≥ 0.7, and U3(∗)=0.32≥0.3U_3(x^*)=0.32≥ 0.3. Figure 1 visualizes the three halfspaces and their intersection. 3e_32e_21e_1∗x^*1A_12A_23A_3⋂i=13i _i=1^3A_i Figure 1: Example 2.3 (m=3m=3): halfspace acceptability regions 1,2,3A_1,A_2,A_3 on the probability simplex. The vertices 1,2,3e_1,e_2,e_3 are pure lotteries, arrows indicate the acceptable side of each constraint, and ∗x^* is a feasible lottery in ⋂i=13i _i=1^3A_i (gray). Finite precision. Fix ε∈(0,1/2] ∈(0,1/2] with 1/ε∈ℤ>01/ _>0. We assume ε -quantized parameters: ui(sj)∈0,ε,2ε,…,1u_i(s_j)∈\0, ,2 ,…,1\ and τi∈ε,2ε,…,1 _i∈\ ,2 ,…,1\. This is necessary for finite-query exactness and can be viewed as Θ(ε) ( )-robust unanimity (Appendix B.1 and B.2). For some counting-based lower bounds we additionally assume m≤(1/ε)1−δm≤(1/ )^1-δ for a fixed constant δ∈(0,1]δ∈(0,1] (see Appendix B.1 for more details). 3 Algorithms for Learning Unanimously Acceptable Lotteries We begin by investigating elicitation algorithms that can give us an upper bound on the worst-case number of queries needed to either find a unanimously acceptable lottery, or certify that none exists. We first focus on how we can (efficiently) elicit the acceptable region for a single agent. For a fixed agent i, acceptability is a single linear inequality: Ui()=⟨i,⟩≥τiU_i(x)= _i,x ≥ _i. Thus, the acceptable region is exactly a halfspace intersected with the simplex Δ(S) (S). Our goal is to recover an equivalent (normalized) halfspace description using as few membership queries Query(i,)Query(i,x) as possible. Algorithm 1 (LearnHyperplaneLearnHyperplane) learns an explicit halfspace description of agent i’s acceptable set. It begins by querying the vertices 1,…,me_1,…,e_m to partition indices into LaccL^acc and LrejL^rej. If Lrej=∅L^rej= (resp., Lacc=∅L^acc= ), then the agent accepts (resp., rejects) every lottery and we return AcceptAll (resp., RejectAll). Otherwise, fix any rejected index r∈Lrejr∈ L^rej. For any edge between a rejected vertex ke_k and an accepted vertex k′e_k , consider the edge lotteries k,k′,α:=(1−α)k+αk′x_k,k ,α:=(1-α)e_k+ _k for α∈[0,1]α∈[0,1]. Along such an edge, Ui(k,k′,α)U_i(x_k,k ,α) is affine and strictly increasing in α, so the accept/reject behavior changes exactly once. We call αi;k,k′∗:=infα∈[0,1]:Query(i,k,k′,α)=True∈(0,1]α^*_i;k,k \;:=\; \α∈[0,1]:Query(i,x_k,k ,α)= True\∈(0,1] the turning point on edge (k,k′)(e_k,e_k ); equivalently, it is the smallest α that is accepted, and (since the boundary is the equality ⟨ui,x⟩=τi u_i,x = _i) it satisfies Ui(k,k′,αi;k,k′∗)=τiU_i(x_k,k ,α^*_i;k,k )= _i. Algorithm 1 LearnHyperplane(i)LearnHyperplane(i) 1:Agent i∈Ni∈ N 2:AcceptAll, RejectAll, or a vector i∈ℝmc_i ^m whose induced halfspace ∈Δ(S):⟨i,⟩≥1\x∈ (S): _i,x ≥ 1\ coincides with agent i’s acceptable region on Δ(S) (S). 3:Query all pure lotteries 1,…,me_1,…,e_m and let Lacc:=j:j∈[m],Query(i,j)=TrueL^acc:=\j:j∈[m],Query(i,e_j)= True\, Lrej:=[m]∖LaccL^rej:=[m] L^acc. 4:if Lrej=∅L^rej= then return AcceptAll 5:else if Lacc=∅L^acc= then return RejectAll 6:end if 7:Choose any r∈Lrejr∈ L^rej. 8:For distinct k,k′∈[m]k,k ∈[m] and α∈[0,1]α∈[0,1], define k,k′,α:=αk′+(1−α)kx_k,k ,α:= _k +(1-α)e_k. 9:for each j∈Laccj∈ L^acc do 10: Find turning point αr,j←ExactThreshold(i,r,j) _r,j (i,r,j) on edge (r,j)(e_r,e_j) (i.e., αr,j=αi;r,j∗ _r,j=α^*_i;r,j). 11:end for 12:if αr,j=1 _r,j=1 for all j∈Laccj∈ L^acc then 13: Construct i∈ℝmc_i ^m by setting ci,j=1c_i,j=1 for j∈Laccj∈ L^acc 14: and ci,k=0c_i,k=0 for k∈Lrejk∈ L^rej. 15: return cic_i 16:end if 17:Choose any a∈Lacca∈ L^acc such that αr,a<1 _r,a<1. 18:for each k∈Lrej∖rk∈ L^rej \r\ do 19: Find turning point αk,a←ExactThreshold(i,k,a) _k,a (i,k,a) on edge (k,a)(e_k,e_a) (i.e., αk,a=αi;k,a∗ _k,a=α^*_i;k,a) 20:end for 21:Construct i=(ci,1,…,ci,m)c_i=(c_i,1,…,c_i,m) as follows: 22: Set ci,r=0c_i,r=0. 23: For each j∈Laccj∈ L^acc, set ci,j=1/αr,jc_i,j=1/ _r,j. 24: For each k∈Lrej∖rk∈ L^rej \r\, set ci,k=1−αk,aci,a1−αk,ac_i,k= 1- _k,a\,c_i,a1- _k,a. 25:return ic_i LearnHyperplaneLearnHyperplane recovers m−1m-1 turning points on selected simplex edges (via ExactThresholdExactThreshold): first on each edge (r,j)(e_r,e_j) for j∈Laccj∈ L^acc, and then (if needed) on edges (k,a)(e_k,e_a) from the remaining rejected vertices to a fixed accepted a with αi;r,a∗<1α^*_i;r,a<1. In the (m−1)(m-1)-dimensional affine hull of Δ(S) (S), these m−1m-1 edge intersections determine the boundary hyperplane up to scaling; the algorithm normalizes to produce a vector ic_i such that for all ∈Δ(S)x∈ (S), ⟨i,⟩≥1 _i,x ≥ 1 if and only if agent i accepts x. The subroutine ExactThresholdExactThreshold is a one-dimensional search along an edge and uses (log(1/ε))O( (1/ )) queries per turning point (Appendix C.1). We also provide a geometric intuition of the algorithm in Appendix C.2. Formalizing this idea, we present LearnHyperplaneLearnHyperplane, which elicits the supporting hyperplane of a single agent’s acceptable region as described above, and by using only (mlog(1/ε))O(m (1/ )) queries. We now establish two key properties of LearnHyperplaneLearnHyperplane. The first concerns query complexity: we show that the algorithm identifies all necessary threshold points using only (log(1/ε))O( (1/ )) queries. Lemma 3.1 formalizes this bound. Lemma 3.1. Algorithm 1 makes (mlog(1/ε))O(m (1/ )) queries. Our next step is to show that the resulting vector exactly encodes the boundary of the agent’s acceptable region. Lemma 3.2. Fix an agent i∈Ni∈ N. Algorithm 1 returns one of the following: (i) AcceptAll, in which case Ui()≥τiU_i(x)≥ _i for all ∈Δ(S)x∈ (S); (i) RejectAll, in which case Ui()<τiU_i(x)< _i for all ∈Δ(S)x∈ (S); or (i) a vector i∈ℝmc_i ^m such that for all ∈Δ(S)x∈ (S), ⟨i,⟩≥1 _i,x ≥ 1 if and only if Ui()≥τiU_i(x)≥ _i. In case (i), the induced halfspace ∈Δ(S):⟨i,⟩≥1\x∈ (S): _i,x ≥ 1\ coincides with agent i’s acceptable set. These two lemmas show that an agent’s acceptance region can be elicited and represented as a single linear constraint. This reduces the multi-agent elicitation problem to determining whether the intersection of the learned halfspaces is nonempty. Intersecting the learned halfspaces across agents and solving a feasibility linear program (LP) allows us to find a unanimously acceptable lottery or certify that none exists (without requiring further queries). A simple baseline is to run LearnHyperplane(i)LearnHyperplane(i) for every agent i∈Ni∈ N and then solve the resulting feasibility LP. This full elicitation strategy makes (nmlog(1/ε))O(nm (1/ )) queries. However, aside from the trivial early termination case where some agent rejects all lotteries, it always learns all n hyperplanes, so its best-case query complexity on feasible instances is still Θ(nmlog(1/ε)) (nm (1/ )). In many instances this is unnecessarily pessimistic. Intuitively, feasibility (and the particular lottery we end up returning) might be “certified” by only a small subset of constraints, so learning the remaining agents’ hyperplanes provides no additional benefit. This motivates an adaptive deterministic algorithm (Algorithm 2) that pays for hyperplane elicitation only when it is forced by an observed violation. Fix a deterministic tie-breaking rule: define Select(C)Select(C) to return the lexicographically maximum feasible lottery x among all ∈Δ(S)x∈ (S) satisfying ⟨,⟩≥1 ,x ≥ 1 for all ∈Cc∈ C, and return Null if infeasible.444Equivalently, SelectSelect can be implemented by solving a sequence of LPs that maximize x1x_1, then x2x_2, etc., over the feasible region. This means it can be implemented in polymomial time. Our focus is the number of membership queries, so we treat this offline computation cost as secondary. Intuitively, Algorithm 2 maintains a set C of learned acceptability halfspaces and proposes a candidate ←Select(C)x (C). It then queries the remaining (unlearned) agents. If every unlearned agent accepts x, then x is unanimously acceptable (all previously learned agents accept x by construction). Otherwise, upon encountering the first unlearned agent i that rejects x, the algorithm invokes LearnHyperplane(i)LearnHyperplane(i) to elicit i’s acceptability halfspace, adds the resulting constraint to C, and immediately restarts with a new candidate lottery. The algorithm reports infeasibility either when Select(C)=NullSelect(C)= Null or when LearnHyperplane(i)LearnHyperplane(i) returns RejectAll. Our result is as follows. Algorithm 2 Deterministic algorithm that returns a unanimously acceptable lottery if one exists, or Null otherwise 1:Set of agents N=1,…,nN=\1,…,n\ and set of alternatives S=s1,…,smS=\s_1,…,s_m\ 2:Lottery =(x1,…,xm)∈Δ(S)x=(x_1,…,x_m)∈ (S) such that Ui()≥τiU_i(x)≥ _i for all i∈Ni∈ N, or Null 3:C←∅C← ⊳ learned hyperplane constraints 4:N′←N ← N ⊳ agents whose hyperplanes not learned 5:while True do 6: ←Select(C)x (C) 7: if =Nullx= Null then return Null 8: end if 9: j←Nonej← None ⊳ keep track of the first violator 10: for i=1,…,ni=1,…,n do 11: if i∉N′i∉ N then continue 12: else if Query(i,)=FalseQuery(i,x)= False then 13: j←ij← i; break ⊳ violator 14: end if 15: end for 16: if j=Nonej= None then return x 17: end if 18: ←LearnHyperplane(j)c (j); N′←N′∖jN ← N \j\ 19: if =RejectAllc= RejectAll then return Null 20: else C←C∪C← C∪\c\ 21: end if 22:end while 23:return x Theorem 3.3. Algorithm 2 returns a unanimously acceptable lottery when one exists, and outputs Null otherwise, using (n2+nmlog(1/ε))O (n^2+nm (1/ ) ) queries. Note that the extra n2n^2 term arises solely from verification queries in the worst case: each time a new hyperplane is learned, the new candidate ←Select(C)x (C) must be checked against the remaining unlearned agents. Note that if the number of agents on which Algorithm 2 calls LearnHyperplaneLearnHyperplane on is small, then we can avoid learning most agents’ halfspaces and can be substantially cheaper than full elicitation. A natural follow-up question is whether one can do better than eliciting the hyperplane of every agent. In many governance deployments, m (the menu size) is modest while n (stakeholders) can be very large. In such settings, algorithms that avoid learning all n halfspaces are attractive, motivating the randomized approach below. Specifically, show that randomization (via Algorithm 3, details in Appendix C.6) gives an improvement on the expected number of hyperplane learning we have to do. As with any randomized guarantee, the worst case over the internal randomness can still be as large as n; our improvement is in expectation. Theorem 3.4. There exists a randomized algorithm that returns a unanimously acceptable lottery when one exists, and outputs Null otherwise, using (nmlogn+minn,m3logn⋅mlog(1/ε))O (nm n+ \n,\,m^3 n\· m (1/ ) ) queries in expectation. Proof idea (informal).. Our algorithm adapts the Clarkson (1995) low-dimensional LP sampling approach to our model: each round samples a small (weight-biased) set of agents, learns only their halfspaces, solves the sampled LP to get a candidate lottery x, then verifies x against all agents and multiplicatively upweights the violators. The geometric reason this works is that in dimension m−1m-1 there is always a small set of (m)O(m) agents that certifies feasibility/infeasibility (and pins down the tie-broken optimum when feasible); any failed verification must violate at least one witness agent, so repeated up-weighting quickly forces the sample to include all witnesses, after which verification certifies correctness. The novel consideration here is our oracle strength: we do not get violated constraints for free from a separation oracle, so we must explicitly elicit (and cache) sampled agents’ constraints via LearnHyperplaneLearnHyperplane. ∎ Thus, the randomized algorithm reduces the number of expensive hyperplane learning occurrences to (minn,m3logn)O( \n,m^3 n\) in expectation, at the cost of (mlogn)O(m n) global verification rounds. Intuitively, if n≫m3logn m^3 n, then the expected number of queries is (nmlogn+m4(logn)log(1/ε))O(nm n+m^4( n) (1/ )); whereas if n≤m3logn≤ m^3 n, the second term becomes (nmlog(1/ε))O(nm (1/ )). We also remark that finding explicit infeasibility witnesses comes at no additional query cost (see Appendix C.7), which may be useful in governance/audit applications. 4 Lower Bounds on Query Complexity The previous section establishes query-efficient algorithms for either finding a unanimously acceptable lottery or certifying infeasibility under membership-query access. We now ask how far one can improve these bounds in the worst case. Our lower bounds apply to both deterministic and randomized algorithms, and they already hold under binary utilities (ui(sj)∈0,1u_i(s_j)∈\0,1\). Theorem 4.1. Any (deterministic or randomized) algorithm that, on every instance, outputs a unanimously acceptable lottery when one exists (and correctly reports infeasibility otherwise), has a worst-case (expected) number of queries of Ω((n−minn,m)+(minn,m−1)log(1/ε)) ((n- \n,m\)+( \n,m\-1) (1/ ) ). Relative to Section 3, our algorithms have the correct qualitative dependence on ε (via the Θ(log(1/ε)) ( (1/ )) threshold search cost). The remaining gaps are in how many times agents must be re-queried during verification. Algorithm 2 has an (n2)O(n^2) verification overhead in the worst case, while Algorithm 3 reduces the number of verification rounds to (mlogn)O(m n) in expectation (and thus (nmlogn)O(nm n) verification queries). When m is modest, this brings the dependence on n close to the Ω(n) (n) lower bound up to logarithmic factors, while simultaneously ensuring that only a small number of agents’ halfspaces must be explicitly learned in expectation. The next theorem isolates an orthogonal difficulty: even with a single agent, no algorithm can hope to achieve a polylogarithmic dependence on m in our model. Theorem 4.2. Fix any m≥2m≥ 2. Even for n=1n=1, any correct algorithm must make Ω(m) (m) queries in the worst case. 5 Learning-Augmented Algorithms The algorithms in Section 3 are designed for the worst case: they assume the algorithm has no prior information about which agents are likely to be constraining, or where a unanimously acceptable lottery might lie. In many applications, this is overly pessimistic. In particular, governance and safety evaluation pipelines often come with side information—historical data about which checks tend to bind, preliminary offline evaluations, domain expertise, or even heuristic rankings produced by other systems. While such advice can be imperfect, it can nevertheless capture meaningful structure that an elicitation algorithm can exploit to reduce the number of expensive stakeholder queries. Learning-augmented algorithms (also called algorithms with advice/predictions) provide a framework for leveraging such information without sacrificing worst-case guarantees. The algorithm receives a prediction about some aspect of the instance, but must remain correct even if the prediction is arbitrarily wrong. We seek three standard properties: consistency (perfect advice results in fewer queries), robustness (arbitrarily bad advice does not worsen the asymptotic worst-case guarantees), and smoothness (performance degrades gradually as a function of a prediction quality parameter). In our setting, advice is especially natural because the dominant query cost arises from learning agents’ halfspaces: each call to LearnHyperplaneLearnHyperplane costs (mlog(1/ε))O(m (1/ )) queries. Thus, even coarse predictions that reduce (i) the number of agents whose hyperplanes must be elicited, or (i) the time until the algorithm queries the set of “constraining” agents, can translate into substantial query savings. We consider two forms of predictions: permutation predictions, which provide an ordering of agents intended to place more constraining agents early, and lottery predictions, which provide a candidate lottery believed to be promising.555These two prediction types are illustrative rather than exhaustive; they simply demonstrate that natural, coarse advice can reduce query complexity while preserving worst‑case guarantees. 5.1 Permutation Predictions A natural and common kind of advice in practice is a ranking of stakeholders by “likely constraining”; for example, based on past deployment reviews or on preliminary screening. Algorithm 2 scans agents to find the first violator of the current candidate lottery; if a violator is found, the algorithm pays the full cost of eliciting that agent’s halfspace. This suggests that a good scan order can substantially reduce the number of costly elicitation steps. Let σ be any permutation of the agents N. Define Algorithm 2[σ][σ] to be Algorithm 2 with the only change that, in each iteration, the algorithm scans unlearned agents in the order σ(1),…,σ(n)σ(1),…,σ(n) (instead of 1,…,n1,…,n). Let H(σ)⊆NH(σ) N denote the set of agents on which LearnHyperplaneLearnHyperplane is invoked during the execution of Algorithm 2[σ][σ], and define R(σ):=|H(σ)|R(σ):=|H(σ)|.666If R(σ)=0R(σ)=0, then the very first candidate lottery (computed from an empty constraint set) is already unanimously acceptable, and the algorithm terminates after only the n verification queries. Thus, we assume R(σ)≥1R(σ)≥ 1 for notational simplicity. We call R(σ)R(σ) the number of record agents under order σ: it is exactly the number of times the algorithm is forced to pay for hyperplane elicitation. Smaller R(σ)R(σ) corresponds to better advice. A permutation predictor outputs an ordering σ σ intended to place “more constraining” agents early. Importantly, there need not be a uniquely most constraining agent: which constraints become active depends on the sequence of candidate lotteries produced by SelectSelect. We therefore interpret “constraining” in an operational sense: an agent is constraining for order σ if it is ever encountered as a violator before its halfspace is learned. The most direct use of a predicted permutation σ σ is to run Algorithm 2 with the agent order σ σ in the for loop on Line 10 (which we denote as Algorithm 2[σ^][ σ]). We treat R(σ^)R( σ) as the prediction quality parameter. Theorem 5.1. Let σ σ be a predicted permutation of the agents. Then Algorithm 2[σ^][ σ] outputs a unanimously acceptable lottery if one exists, and Null otherwise, using ((n+mlog(1/ε))R(σ^))O ((n+m (1/ ))\,R( σ) ) queries. When advice is perfect (i.e., R(σ^)=1R( σ)=1), the algorithm of theorem 5.1 uses only (n+mlog(1/ε))O(n+m (1/ )) queries; note that Ω(n+m) (n+m) queries are necessary from section 4. Meanwhile, even with arbitrarily bad advice, the query complexity never exceeds the advice-free worst-case guarantee of algorithm 2 since R(σ^)≤nR( σ)≤ n for any permutation. Finally, the linear dependence on R(σ^)R( σ) gives us a smooth performance degradation as prediction quality worsens. Permutation advice can also improve the randomized algorithm (Algorithm 3), which repeatedly samples agents according to a weight vector, solves the sampled subproblem, and multiplicatively upweights violators. In the advice-free analysis, the expected number of iterations scales as (mlogn)O(m n) because the algorithm must (in effect) discover a small witness set among n agents. A predicted order allows us to bias sampling toward agents that appear early, reducing the effective logn n dependence when a witness set is contained in a short prefix of σ σ. Let rankσ^(i)∈1,…,nrank_ σ(i)∈\1,…,n\ denote the position of agent i in σ σ. Recall from the analysis of Algorithm 3 that correctness can be certified by a small witness set: in the feasible case, there is a basis of size at most m−1m-1 that determines the final (tie-breaking) solution; in the infeasible case, there is a Helly witness of size at most m, i.e., a set B with ⋂i∈Bi=∅ _i∈ BA_i= . Let W denote the family of valid witness sets used in the analysis (bases in the feasible case, Helly witnesses in the infeasible case) and define the prefix witness parameter E(σ^):=minB∈maxi∈Brankσ^(i)E( σ):= _B ~ _i∈ Brank_ σ(i), i.e., E(σ^)E( σ) is the smallest k such that the first k agents of σ σ contains some B∈B . We define Algorithm 3[σ^][ σ] as Algorithm 3 with an advice-biased initialization of the sampling weights: set the initial integer weight of agent i to wi(1):=⌈n/rankσ^(i)⌉w_i^(1):= n/rank_ σ(i) , and then run the same sampling and multiplicative updating procedure as in Algorithm 3. Theorem 5.2. Let σ σ be a predicted permutation of the agents. Then Algorithm 3[σ^][ σ] outputs a unanimously acceptable lottery if one exists, and Null otherwise, using (nmμ+minn,m3μ⋅mlog(1/ε))O(nmμ+ \n,m^3μ\· m (1/ )) queries in expectation, where μ=logE(σ^)+loglognμ= E( σ)+ n. The above result recovers the advice-free bound (up to constants) when the advice is arbitrary: since E(σ^)≤nE( σ)≤ n always, we have μ=(logn)μ=O( n). When the advice is perfect, the dependence on logn n in the advice-free analysis is replaced by logE(σ^)+loglogn E( σ)+ n. The bound is monotone in E(σ^)E( σ), giving us smooth degradation as the prediction worsens. We complement Theorems 5.1 and 5.2 by proving, in Appendix E.3, that even when the predicted permutation is perfect, any algorithm that must remain correct for arbitrary advice still requires Ω((n−minn,m)+(minn,m−1)log(1/ε)) ((n- \n,m\)+( \n,m\-1) (1/ )) queries, as in the setting without advice. 5.2 Lottery Predictions A second natural form of advice is a lottery prediction: the predictor provides a candidate lottery ^∈Δ(S) x∈ (S) that is believed to be informative for the instance.777For example, x may come from offline evaluation, a heuristic search procedure, or a previous deployment cycle. The algorithm must remain correct even if x is arbitrary. The most direct use of x is to verify it once: query each agent i∈Ni∈ N on x. If Query(i,^)=TrueQuery(i, x)= True for all i, then x is unanimously acceptable and the algorithm can terminate after exactly n membership queries. When x is not unanimously acceptable, we can still leverage it to reduce the query cost of learning an individual agent’s acceptability halfspace. Recall that LearnHyperplane(i)LearnHyperplane(i) (Algorithm 1) identifies agent i’s boundary by locating m−1m-1 turning points along simplex edges, using ExactThresholdExactThreshold (Appendix C.1). Each such call performs a global bisection on an interval of length 11, costing Θ(log(1/ε)) ( (1/ )) queries. Lottery advice provides a natural warm start for these one-dimensional searches. For distinct k,k′∈[m]k,k ∈[m], recall the edge lotteries k,k′,α:=αek′+(1−α)ekx_k,k ,α:=α e_k +(1-α)e_k for all α∈[0,1]α∈[0,1]. Given any ∈Δ(S)x∈ (S), define the pairwise projection coordinate α^k,k′() α_k,k (x), which takes on a value of xk′/(xk+xk′)x_k /(x_k+x_k ) if xk+xk′>0x_k+x_k >0, and 1/21/2 otherwise (xk+xk′=0x_k+x_k =0). Equivalently, α^k,k′() α_k,k (x) is the unique α∈[0,1]α∈[0,1] such that the edge lottery k,k′,αx_k,k ,α has the same relative mass on k,k′\e_k,e_k \ as x after renormalizing away the other m−2m-2 coordinates. Fix an agent i∈Ni∈ N and an ordered pair (k,k′)(k,k ) with Query(i,k)=FalseQuery(i,e_k)= False and Query(i,k′)=TrueQuery(i,e_k )= True. As argued in Section 3, there is a unique turning point αi;k,k′∗:=infα∈[0,1]:Query(i,xk,k′,α)=True∈(0,1]α^*_i;k,k := \α∈[0,1]:Query(i,x_k,k ,α)= True\∈(0,1]. Then, given a prediction x, define the (edge) turning point projection error δi;k,k′(x^):=|α^k,k′(x^)−αi;k,k′∗| _i;k,k ( x):=| α_k,k ( x)-α^*_i;k,k |. We illustrate the defined quantities with Figure 2. k′e_k ke_kαi;k,k′∗ _i;k,k ^*α^k,k′(^) α_k,k ( x)δi;k,k′(^) _i;k,k ( x) Figure 2: Each point on this line segment is a lottery. The red (resp., green) region indicates the set of rejected (resp., accepted) lotteries along this edge. A lottery prediction induces a projected turning point which can be used as a warm start α^k,k′(^) α_k,k ( x) to find the turning point αi;k,k′∗α^*_i;k,k faster. Let ℰiE_i denote the set of ordered pairs (k,k′)(k,k ) on which LearnHyperplaneLearnHyperplane invokes ExactThresholdExactThreshold when run on agent i (i.e., the set of simplex edges whose turning points are actually queried); note that |ℰi|≤m−1|E_i|≤ m-1. Define the per-agent prediction error δimax(^):=max(k,k′)∈ℰiδi;k,k′(^) _i ( x):= _(k,k ) _i\ _i;k,k ( x). We now define LearnHyperplane[^]LearnHyperplane[ x] to be LearnHyperplaneLearnHyperplane with a modification that every call to ExactThreshold(i,k,k′)ExactThreshold(i,k,k ) is replaced by a warm-started routine ExactThresholdPred(i,k,k′,α^k,k′(^))ExactThresholdPred(i,k,k , α_k,k ( x)) (Algorithm 4 in Appendix E.4). Theorem 5.3. Fix an agent i∈Ni∈ N and a predicted lottery ^∈Δ(S) x∈ (S). Then LearnHyperplane[^](i)LearnHyperplane[ x](i) returns one of the following: (i) AcceptAll, (i) RejectAll, or (i) a vector ic_i whose induced halfspace coincides with agent i’s acceptable set on Δ(S) (S)). Moreover, it has a query complexity of (m+mlog(1+δimax(^)/ε2))O(m+m (1+ _i ( x)/ ^2)). The above result gives a learning-augmented bound for the subroutine that learns a single agent’s acceptable halfspace. It is robust: for any prediction x, the query complexity is never worse (up to constants) than the baseline (mlog(1/ε))O(m (1/ )) bound. It is also consistent under perfect edge information: if δi;k,k′(x^)=0 _i;k,k ( x)=0 for all (k,k′)∈Ei(k,k )∈ E_i, then each warm-started threshold search uses only (1)O(1) additional queries (no logarithmic factor), so the subroutine runs in (m)O(m) queries total (including the m pure lottery queries). More generally, the overhead above m scales as ∑(k,k′)∈ℰilog(1+δi;k,k′(^)/ε2) _(k,k ) _i (1+ _i;k,k ( x)/ ^2), giving us a smooth degradation with prediction error. Then, Algorithms 2 and 3 can incorporate lottery advice by first verifying x (early termination if unanimously accepted), and otherwise replacing every call to LearnHyperplaneLearnHyperplane by LearnHyperplane[^]LearnHyperplane[ x]. This preserves correctness, and simply replaces the per-agent elicitation cost (mlog(1/ε))O(m (1/ )) by the refined bound in Theorem 5.3.888Note that we do not require any relation between x and feasibility; we only exploit whatever pairwise information it encodes. Next, we show that the logarithmic dependence on the turning point projection error in Theorem 5.3 is necessary, even when m=2m=2, with the following lower bound. Proposition 5.4. Fix δ∈[ε2,1]δ∈[ ^2,1], and define M:=min⌊1/(2ε)⌋,⌊δ/ε2⌋+1M:= \ 1/(2 ) ,\ δ/ ^2 +1\. There exist n=m=2n=m=2, a lottery prediction ^∈Δ(S) x∈ (S), and a family of instances ℐtt=0M−1\I_t\_t=0^M-1 such that each ℐtI_t has a unique unanimously acceptable lottery t∗=1,2,αtx_t^*=x_1,2, _t, and for every t the turning point projection error for agent 22 on edge (1,2)(e_1,e_2) in instance ℐtI_t satisfies δ2;1,2(x^)=|αb1,2(x^)−αt|≤δ _2;1,2( x)=| _b1,2( x)- _t|≤δ. For this fixed x, any correct query algorithm must make Ω(log(1+δ/ε2)) ( (1+δ/ ^2 )) queries in the worst case (over the choice of t), in expectation for randomized algorithms. 6 Conclusion and Future Work We study the feasibility problem underlying conservative deployment gates: using only accept/reject feedback to proposed lotteries, the goal is to find a unanimously acceptable lottery or certify infeasibility. We give query-efficient deterministic, randomized, and learning-augmented elicitation algorithms that exploit the halfspace geometry of acceptability on the simplex. Complementary lower bounds show unavoidable linear dependence on the number of stakeholders and Θ(log(1/ε)) ( (1/ )) dependence on the target precision (and Ω(m) (m) even for a single stakeholder). In many governance settings, stakeholder judgments may be noisy, context-dependent, or costly to elicit at high precision. Extending our guarantees to stochastic or approximate oracles is an important future direction. Acknowledgments This work was supported by the Advanced Research + Invention Agency (ARIA). References Airiau et al. [2023] Stéphane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger, Jérôme Lang, and Dominik Peters. Portioning using ordinal preferences: Fairness and efficiency. Artificial Intelligence, 314:103809, 2023. Altman [1999] Eitan Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999. Amaldi and Kann [1995] Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147(1):181–210, 1995. Amazon Web Services [2023] Amazon Web Services. Mlops deployment best practices for real-time inference model serving endpoints with amazon sagemaker, 2023. URL https://aws.amazon.com/blogs/machine-learning/mlops-deployment-best-practices-for-real-time-inference-model-serving-endpoints-with-amazon-sagemaker/. Angluin [1988] Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1988. Anthropic [2025] Anthropic. Anthropic Responsible Scaling Policy (version 2.2), 2025. URL https://w-cdn.anthropic.com/872c653b2d0501d6ab44cf87f43e1dc4853e4d37.pdf. Bai et al. [2022] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional AI: Harmlessness from AI feedback. arXiv preprint arXiv:2212.08073, 2022. Blum et al. [2004] Avrim Blum, Jeffrey Jackson, Tuomas Sandholm, and Martin Zinkevich. Preference elicitation and query learning. Journal of Machine Learning Research, 5:649–667, 2004. Boutilier [2002] Craig Boutilier. A pomdp formulation of preference elicitation problems. In Proceedings of the 18th AAAI Conference on Artificial Intelligence (AAAI), pages 239–246, 2002. Bshouty et al. [1998a] Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, and H. David Mathias. Exact learning of discretized geometric concepts. SIAM Journal on Computing, 28(2):674–699, 1998a. Bshouty et al. [1998b] Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, and Hisao Tamaki. Noise-tolerant distribution-free learning of general geometric concepts. Journal of the ACM, 45(5):863–890, 1998b. Caragiannis et al. [2024] Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas. Truthful aggregation of budget proposals with proportionality guarantees. Artificial Intelligence, 335:104178, 2024. Chen et al. [2025] Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, and Tianqi Yang. Halfspaces are hard to test with relative error. arXiv preprint arXiv:2511.06171, 2025. Clarkson [1995] Kenneth L. Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM, 42(2):488–499, 1995. Conen and Sandholm [2001] Wolfram Conen and Tuomas Sandholm. Preference elicitation in combinatorial auctions. In Proceedings of the 3rd ACM Conference on Electronic Commerce (EC), pages 256–259, 2001. Conitzer et al. [2024] Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H. Holliday, Bob M. Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, Emanuel Tewolde, and William S. Zwicker. Position: Social choice should guide ai alignment in dealing with diverse human feedback. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. Danzer et al. [1963] Ludwig Danzer, Branko Grünbaum, and Victor Klee. Helly’s theorem and its relatives. In Proceedings of Symposia in Pure Mathematics, volume 7, pages 101–180, 1963. Elkind et al. [2026] Edith Elkind, Matthias Greger, Patrick Lederer, Warut Suksompong, and Nicholas Teh. Settling the score: Portioning with cardinal preferences. Artificial Intelligence, 352:104487, 2026. European Parliament and Council of the European Union [2024] European Parliament and Council of the European Union. Regulation (eu) 2024/1689 of the European Parliament and of the Council (Artificial Intelligence Act), 2024. URL https://eur-lex.europa.eu/eli/reg/2024/1689/oj/eng. Freeman and Schmidt-Kraepelin [2024] Rupert Freeman and Ulrike Schmidt-Kraepelin. Project-fair and truthful mechanisms for budget aggregation. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9704–9712, 2024. Freeman et al. [2021] Rupert Freeman, David Pennock, Dominik Peters, and Jennifer Wortman Vaughan. Truthful aggregation of budget proposals. Journal of Economic Theory, 193:105234, 2021. García and Fernández [2015] Javier García and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16:1437–1480, 2015. Gebru et al. [2021] Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé I, and Kate Crawford. Datasheets for datasets. Communications of the ACM, 64(12):86–92, 2021. Goldberg and Cossío [2021] Paul W. Goldberg and Francisco J. Marmolejo Cossío. Learning convex partitions and computing game-theoretic equilibria from best-response queries. ACM Transactions on Economics and Computation, 9(1):3:1–3:36, 2021. Goldberg and Kwek [2000] Paul W. Goldberg and Stephen Kwek. The precision of query points as a resource for learning convex polytopes with membership queries. In Proceedings of the 13th Annual Conference on Computational Learning Theory (COLT), pages 225–235, 2000. Government of Canada [2020] Government of Canada. Algorithmic Impact Assessment tool, 2020. URL https://w.canada.ca/en/government/system/digital-government/digital-government-innovations/responsible-use-ai/algorithmic-impact-assessment.html. Government of Canada [2025] Government of Canada. Guide to peer review of automated decision systems, 2025. URL https://w.canada.ca/en/government/system/digital-government/digital-government-innovations/responsible-use-ai/guide-peer-review-automated-decision-systems.html. Helly [1923] Eduard Helly. Über mengen konvexer körper mit gemeinschaftlichen punkten. Jahresbericht der Deutschen Mathematiker-Vereinigung, 32:175–176, 1923. Kumar et al. [2018] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via ML predictions. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 9684–9693, 2018. Lykouris and Vassilvitskii [2021] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4), 2021. Matoušek et al. [1996] Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4–5):498–516, 1996. Mitchell et al. [2019] Margaret Mitchell, Simone Wu, Andrew Zaldivar, Parker Barnes, Lucy Vasserman, Ben Hutchinson, Elena Spitzer, Inioluwa Deborah Raji, and Timnit Gebru. Model cards for model reporting. In Proceedings of the 4th ACM Conference on Fairness, Accountability, and Transparency (FAccT), pages 220–229, 2019. Myerson [1981] Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58–73, 1981. Nash [1950] John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48–49, 1950. Nisan et al. [2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007. OpenAI [2025] OpenAI. OpenAI Preparedness Framework (version 2), 2025. URL https://cdn.openai.com/pdf/18a02b5d-6b67-4cec-ab64-68cdfbddebcd/preparedness-framework-v2.pdf. Osborne and Rubinstein [1994] Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. MIT Press, 1994. Ouyang et al. [2022] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Procreedings of the 36th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 27730–27744, 2022. Ovadia et al. [2019] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua V. Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 14003–14014, 2019. Puterman [1994] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. John Wiley & Sons, 1994. Quiñonero-Candela et al. [2008] Joaquin Quiñonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence, editors. Dataset Shift in Machine Learning. The MIT Press, 2008. Raji et al. [2020] Inioluwa Deborah Raji, Andrew Smart, Rebecca N. White, Margaret Mitchell, Timnit Gebru, Ben Hutchinson, Jamila Smith-Loud, Daniel Theron, and Parker Barnes. Closing the AI accountability gap: defining an end-to-end framework for internal algorithmic auditing. In Proceedings of the 3rd ACM Conference on Fairness, Accountability, and Transparency (FAccT), pages 33–44, 2020. Rohatgi [2020] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1834–1845, 2020. Seidel [1991] Raimund Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6:423–434, 1991. Sharir and Welzl [1992] Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems. In Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 567–579, 1992. Simon [1955] Herbert A. Simon. A behavioral model of rational choice. The Quarterly Journal of Economics, 69(1):99–118, 1955. Sorensen et al. [2024] Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell Gordon, Niloofar Mireshghallah, Christopher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, Tim Althoff, and Yejin Choi. Position: A roadmap to pluralistic alignment. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. Suksompong and Teh [2026] Warut Suksompong and Nicholas Teh. Voting in divisible settings: A survey. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 39789–39796, 2026. Sutton and Barto [2018] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2 edition, 2018. UK Department for Science, Innovation and Technology [2024] UK Department for Science, Innovation and Technology. Introduction to AI assurance, 2024. URL https://w.gov.uk/government/publications/introduction-to-ai-assurance. US Department of Commerce [2023] US Department of Commerce. Artificial Intelligence Risk Management Framework (ai rmf 1.0), 2023. URL https://nvlpubs.nist.gov/nistpubs/ai/nist.ai.100-1.pdf. von Neumann and Morgenstern [1944] John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944. Yao [1977] Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), pages 222–227, 1977. Appendix A Additional Related Work Pluralistic alignment and aggregation of diverse feedback. A growing body of alignment work emphasizes that advanced AI systems must serve users and stakeholders with diverse values, and that aggregating feedback is not merely an engineering detail but a normative and algorithmic problem. Position papers argue explicitly for importing tools from social choice into modern alignment pipelines, e.g., when human feedback diverges across raters or populations [Conitzer et al., 2024, Sorensen et al., 2024]. In practice, alignment procedures such as reinforcement learning from human feedback and related approaches elicit human judgments over candidate outputs and use them to shape model behavior [Ouyang et al., 2022, Bai et al., 2022]. Our work is complementary in focus: rather than proposing a new aggregation rule or training method, we study the query complexity of reaching a conservative “deployment gate” style guarantee in which every stakeholder’s acceptability threshold is met. This viewpoint captures settings where decisions must satisfy all relevant constraints (e.g., safety, compliance, or governance checks) and where feedback collection is costly, motivating algorithms that obtain just enough information to either (i) output a unanimously acceptable lottery, or (i) certify infeasibility. Lotteries. Lotteries are standard in decision theory and game theory [von Neumann and Morgenstern, 1944, Nash, 1950, Osborne and Rubinstein, 1994]. Our use of lotteries is purely algorithmic: randomization enlarges the feasible set under linear (expected utility) acceptability constraints, but we do not study equilibrium selection or welfare optimality. From a mechanism design perspective, acceptability thresholds can be viewed as an individual participation or safety constraint, but we deliberately abstract away strategic reporting and incentive issues [Myerson, 1981, Nisan et al., 2007]; our focus is the information cost (queries) required to find a unanimously feasible decision in the presence of unknown constraints. Constrained decision-making and safe reinforcement learning. Constrained MDPs and safe RL study decision-making under constraints, including feasibility and optimization of expected returns subject to safety constraints [Puterman, 1994, Altman, 1999, García and Fernández, 2015, Sutton and Barto, 2018]. These works typically assume access to trajectories/samples and an explicit constraint specification (or a simulator), whereas our model isolates a different bottleneck: the cost of eliciting whether candidate (randomized) decisions satisfy each stakeholder’s acceptability constraint. Our results therefore complement, rather than replace, the safe RL literature: they provide query-efficient methods for the approval/constraint checking component that can appear in governance loops. Query models in game theory. A separate query-based line of work studies computing equilibria or best-response structure when payoffs are not explicitly given (e.g., via payoff queries or best-response queries). For example, Goldberg and Cossío [2021] study learning the partition of a mixed-strategy simplex induced by best responses, enabling equilibrium computation from such queries. Our oracle is strictly weaker (binary accept/reject rather than payoffs or best responses) and our goal is feasibility rather than equilibrium. Low-dimensional linear programming. Once constraints are explicit (i.e., agents’ preferences are fully known), unanimous acceptability reduces to feasibility of a low-dimensional linear program over the simplex. Classical convexity results such as Helly’s theorem and its refinements imply that feasibility (or infeasibility) can be certified by a small witness set of constraints (of size (m)O(m)) [Helly, 1923, Danzer et al., 1963, Sharir and Welzl, 1992]. Randomized algorithms for low-dimensional linear programming (e.g., randomized incremental and sampling/reweighting methods) exploit precisely this structure [Seidel, 1991, Clarkson, 1995, Matoušek et al., 1996]. Our randomized elicitation algorithm is inspired by this line of work, but under a strictly weaker oracle model: we do not receive violated constraints (separating hyperplanes) for free, and instead must learn an agent’s halfspace using accept/reject queries on lotteries. Our contribution is to show how this structure can still be leveraged in our query-limited setting, giving us an improved query complexity and accompanying lower bounds. Property testing/lower bounds for halfspaces. Lower bounds for learning or testing halfspaces in various oracle models provide useful context for our ε -precision assumption and for understanding which tasks inherently require many queries. For example, Chen et al. [2025] prove lower bounds for testing halfspaces under a relative-error criterion in a property testing model. While their model is different from ours, it reinforces that seemingly modest changes in feedback/oracle access can qualitatively change the complexity of halfspace-related tasks. Maximum feasible subsystems. Relaxing unanimity to maximize the number (or weight) of satisfied constraints connects to the maximum feasible subsystem problem, which is NP-hard and hard to approximate in general [Amaldi and Kann, 1995]. Our paper shows that even under strong structural restrictions induced by lotteries over a simplex, optimizing the number of satisfied agents remains NP-hard, motivating unanimity as a clean baseline where the computational challenge lies primarily in elicitation rather than offline optimization. Portioning and budget aggregation. Our model is also related to the portioning/budget aggregation literature, which studies how to aggregate opinions about how a divisible public resource (e.g., money or time) should be split across alternatives [Freeman et al., 2021, Airiau et al., 2023, Elkind et al., 2026]. We refer the reader to the recent survey by Suksompong and Teh [2026] for a comprehensive overview of works in this area. At a geometric level, both settings choose a point in a simplex. The differences are semantic, informational, and objective-based: in portioning, the fractional vector is the implemented allocation itself and agents typically report richer information (e.g., ideal budget proposals, cardinal allocations, or ordinal rankings), with work focusing on truthfulness, proportionality, Pareto efficiency, or project fairness of aggregation rules [Freeman et al., 2021, Freeman and Schmidt-Kraepelin, 2024, Caragiannis et al., 2024, Elkind et al., 2026]. In contrast, our simplex point is a lottery over alternatives, acceptability is evaluated via expected utility against agent-specific thresholds, and we focus on the query complexity of finding any unanimously acceptable lottery or certifying infeasibility, rather than selecting a normatively optimal aggregate allocation. Appendix B Omitted Content from Section 2 B.1 Necessity of finite precision We will explain why a finite-precision assumption is necessary to obtain finite query algorithms for exact unanimity. In the main body of the paper, we enforce this by assuming each ui(sj)u_i(s_j) and τi _i is an integer multiple of ε , which implies that the relevant boundary/threshold locations are rationals with bounded denominators. Proposition B.1 (Necessity of finite precision). If agent utilities and thresholds are allowed to be arbitrary real numbers in [0,1][0,1] (with no finite-precision restriction), then there is no algorithm that, using finitely many membership queries, always outputs a unanimously acceptable lottery when one exists (and correctly outputs Null otherwise). This holds even for n=m=2n=m=2. Proof. Consider m=2m=2 alternatives S=s1,s2S=\s_1,s_2\. Any lottery can be identified with a single scalar α∈[0,1]α∈[0,1], meaning α=(α,1−α)x_α=(α,1-α). For each t∈(0,1)t∈(0,1), define an instance ℐtI_t with two agents as follows: • Agent 1 has u1(s1)=1u_1(s_1)=1, u1(s2)=0u_1(s_2)=0, and threshold τ1=t _1=t. Then U1(α)=αU_1(x_α)=α, so agent 11 accepts exactly the interval [t,1][t,1]. • Agent 2 has u2(s1)=0u_2(s_1)=0, u2(s2)=1u_2(s_2)=1, and threshold τ2=1−t _2=1-t. Then U2(α)=1−αU_2(x_α)=1-α, so agent 22 accepts exactly the interval [0,t][0,t]. Hence, the unanimously acceptable set in ℐtI_t is exactly the singleton t\x_t\. Now consider any (deterministic) algorithm A that is correct on every instance and that makes finitely many queries on every instance. Run A on the family ℐt:t∈(0,1)\I_t:t∈(0,1)\. Each membership query made by A returns a single bit, so every execution produces a finite transcript over 0,1\0,1\; therefore, across all t, the set of possible transcripts is countable, and consequently the set of possible outputs of A is also countable. However, correctness requires that on input ℐtI_t, the algorithm outputs exactly tx_t (it cannot output Null, since ℐtI_t is feasible), and the map t↦xtt x_t is injective over the uncountable set (0,1)(0,1). This is impossible if A has only countably many possible outputs. Therefore no such finite-query algorithm exists. The same impossibility immediately applies to any randomized algorithm that is required to be correct with probability 11: fixing the internal randomness gives us a deterministic algorithm, to which the above argument applies. ∎ B.2 Finite precision as ε -robust unanimity Although our main model treats the ε -precision values as the ground truth, it is often useful to interpret the same assumption as capturing limited measurement/communication precision: agents may only be able to report utilities and thresholds up to granularity ε . Fix any underlying “continuous” instance with real-valued parameters u¯i(sj)∈[0,1] u_i(s_j)∈[0,1] and τ¯i∈(0,1] τ_i∈(0,1]. Let ui(sj)u_i(s_j) and τi _i be ε -quantized versions satisfying maxj∈[m]|ui(sj)−u¯i(sj)|≤εand|τi−τ¯i|,≤εfor all i∈N. _j∈[m]|u_i(s_j)- u_i(s_j)|≤ | _i- τ_i|,≤ all i∈ N. Write U¯i()=∑j=1mxju¯i(sj) U_i(x)= _j=1^mx_j u_i(s_j) and Ui()=∑jxjui(sj)U_i(x)= _jx_ju_i(s_j). Then, we have the following result. Lemma B.2. For any agent i and any lottery ∈Δ(S)x∈ (S), |Ui()−U¯i()|≤ε|U_i(x)- U_i(x)|≤ . Consequently, for any lottery ∈Δ(S)x∈ (S): (∀i∈N,U¯i()≥τ¯i+2ε)⟹(∀i∈N,Ui()≥τi)⟹(∀i∈N,U¯i()≥τ¯i−2ε). (∀ i∈ N,\ U_i(x)≥ τ_i+2 ) (∀ i∈ N,\ U_i(x)≥ _i ) (∀ i∈ N,\ U_i(x)≥ τ_i-2 ). Proof. Since x is a probability vector, |Ui()−U¯i()|=|∑j=1mxj(ui(sj)−u¯i(sj))|≤∑j=1mxj|ui(sj)−u¯i(sj)|≤ε.|U_i(x)- U_i(x)|= | _j=1^mx_j (u_i(s_j)- u_i(s_j) ) |≤ _j=1^mx_j\,|u_i(s_j)- u_i(s_j)|≤ . For the forward implication, if U¯i()≥τ¯i+2ε U_i(x)≥ τ_i+2 then Ui()≥U¯i()−ε≥τ¯i+ε≥τiU_i(x)≥ U_i(x)- ≥ τ_i+ ≥ _i. For the backward implication, if Ui()≥τiU_i(x)≥ _i then U¯i()≥Ui()−ε≥τi−ε≥τ¯i−2ε U_i(x)≥ U_i(x)- ≥ _i- ≥ τ_i-2 . ∎ Interpretation. Lemma B.2 shows that ε -precision on the agent parameters induces an Θ(ε) ( )-robust notion of unanimity: it rules out instances where feasibility relies on knife-edge comparisons that are unstable under perturbations of size (ε)O( ) in the reported utilities/thresholds. In particular, if there exists a lottery that clears every agent’s true threshold by a margin 2ε2 , then it remains unanimously acceptable after ε -quantization; and any unanimously acceptable lottery in the quantized instance is within 2ε2 of being acceptable in the underlying continuous instance. Additional remarks on the ε -precision model. Our algorithmic upper bounds in Section 3 do not rely on any further relationship between m and ε . For some information-theoretic lower bounds, we assume m≤(1/ε)1−δm≤(1/ )^1-δ for a fixed constant δ∈(0,1]δ∈(0,1] (in particular, m≤1/εm≤ 1/ ), which avoids a degenerate setting where the positive ε -grid on the simplex is tiny and the resulting counting bounds become vacuous. Unless otherwise stated, we work throughout in the ε -precision model above. In particular, all constraints have rational coefficients, and whenever ⋂i∈Ni≠∅ _i∈ NA_i≠ it contains a lottery with rational coordinates. Thus, we may restrict all oracle queries and algorithm outputs to rational lotteries; for readability we write ∈Δ(S)x∈ (S) and suppress the qualifier ∈Δ(S)∩ℚmx∈ (S) ^m. B.3 Beyond Unanimity: Computational Intractability of Partial Acceptance Objectives Our main goal in this paper is feasibility under a conservative consent constraint: either find a lottery that every agent deems acceptable, or certify that no such lottery exists. A natural relaxation is to ask for a lottery that is acceptable to as many agents as possible. Formally, define the (acceptability) welfare of a lottery x as W():=|i∈N:Ui()≥τi|W(x):=|\i∈ N:U_i(x)≥ _i\|. Then, the optimization problem (denote as Max-Accept-Lottery) would ask: find a lottery ∈Δ(S)x∈ (S) maximizing W()W(x); whereas the decision variant (denote as k-Accept-Lottery) would ask: given an integer k∈ℤ+k _+, decide whether there exists ∈Δ(S)x∈ (S) such that W()≥kW(x)≥ k. At a high level, k-Accept-Lottery resembles the maximum feasible subsystem problem (Max-FS), which asks to satisfy as many linear inequalities as possible and is NP-hard [Amaldi and Kann, 1995]. Indeed, writing each agent’s acceptability condition as a linear constraint ⟨i,⟩≥τi _i,x ≥ _i and adding the simplex constraints x1,…,xm≥0x_1,…,x_m≥ 0 and ∑j=1mxj=1 _j=1^mx_j=1, k-Accept-Lottery can be seen as a structured subclass of Max-FS. Thus, Max-FS hardness results do not immediately apply under our strong structural restrictions (nonnegative coefficients, a shared normalization constraint, etc.). The following theorem shows that the problem remains NP-hard even in this special case. Theorem B.3. k-Accept-Lottery is NP-hard, even when ui(sj)∈0,1u_i(s_j)∈\0,1\ for every i∈Ni∈ N and j∈[m]j∈[m]. Proof. We reduce from the classical NP-complete problem Clique. An instance of Clique is given by an undirected graph G=(V,E)G=(V,E) and an integer κ≥2κ≥ 2; it is a yes-instance if G contains a clique of size κ≥2κ≥ 2, and a no-instance otherwise. Given an instance (G,κ)(G,κ) of Clique with |V|=m|V|=m and |E|=M|E|=M, we construct an instance of k-Accept-Lottery with m alternative and a polynomial number of agents. Create one alternative per vertex, i.e., S=sv:v∈VS=\s_v:v∈ V\, where |S|=m|S|=m. Let R:=m+M+1R:=m+M+1. Note that R is polynomial in the size of G. Define three agent types; all utilities are in 0,1\0,1\: • Type A: “Upper bound” agents. For each vertex v∈Vv∈ V, create R identical agents av,1,…,av,Ra_v,1,…,a_v,R. For every agent i∈NAi∈ N_A, let ui(sv)=0 and ui(sw)=1 for all w≠v,u_i(s_v)=0 and u_i(s_w)=1 for all w≠ v, and threshold τi=1−1/κ _i=1-1/κ. Then, for any lottery x, Ui()=∑w≠vxw=1−xvU_i(x)= _w≠ vx_w=1-x_v, and thus Ui()≥τi⇔1−xv≥1−1/κ⇔xv≤1/κ.U_i(x)≥ _i 1-x_v≥ 1-1/κ x_v≤ 1/κ. Intuitively, every Type A agent created from vertex v only accepts a lottery if the probability mass placed on v is at most 1/κ1/κ. • Type B: “Lower bound” agents. For each vertex v∈Vv∈ V, create one agent. For every agent i∈NBi∈ N_B, let ui(sv)=1 and ui(sw)=0 for all w≠v,u_i(s_v)=1 and u_i(s_w)=0 for all w≠ v, and threshold τi=1/κ _i=1/κ. Then, for any lottery x, Ui()=xvU_i(x)=x_v, and thus Ui()≥τi⇔xv≥1/κ.U_i(x)≥ _i x_v≥ 1/κ. Intuitively, every Type B agent created from vertex v only accepts a lottery if the probability mass placed on v is at least 1/κ1/κ. • Type C: Edge agents. For each edge u,v∈E\u,v\∈ E, create one agent. For every agent i∈NCi∈ N_C created from edge u,v\u,v\, let ui(su)=ui(sv)=1 and ui(sw)=0 for all w∉u,v,u_i(s_u)=u_i(s_v)=1 and u_i(s_w)=0 for all w∉\u,v\, and threshold τi=2/κ _i=2/κ. Then, for any lottery x, Ui()=xu+xvU_i(x)=x_u+x_v, and thus Ui()≥τi⇔xu+xv≥2/κ.U_i(x)≥ _i x_u+x_v≥ 2/κ. Now, the total number of agents is n=|NA|+|NB|+|NC|=Rm+m+Mn=|N_A|+|N_B|+|N_C|=Rm+m+M, which is polynomial in m+Mm+M. Now, set k:=Rm+κ+(κ2)k:=Rm+κ+ κ2. We claim that (G,κ)(G,κ) is a yes-instance of Clique if and only if the constructed instance has a lottery ∈Δ(S)x∈ (S) with W()≥kW(x)≥ k. (⇒)( ) Assume G contains a clique C⊆VC V with |C|=κ|C|=κ. Define the lottery x as follows: xv=1/κif v∈C,0otherwise.x_v= cases1/κ&if v∈ C,\\ 0&otherwise. cases Now, all Type A agents will accept x: For every vertex v, we have xv≤1/κx_v≤ 1/κ, so each of the R agents corresponding to each vertex v will accept x. Hence, we have RmRm accepting agents from Type A. Exactly κ Type B agents will accept x: For v∈Cv∈ C, xv=1/κx_v=1/κ, so any agent corresponding to a vertex in C will accept; whereas for v∉Cv∉ C, xv=0x_v=0, so any agent corresponding to a vertex not in C will reject. Thus, there is exactly κ accepting agents from Type B. Exactly (κ2) κ2 Type C agents will accept x: For any edge u,v\u,v\ with u,v∈Cu,v∈ C, we have xu+xv=2/κx_u+x_v=2/κ, so an agent corresponding to the edge u,v\u,v\ will accept. Since C is a clique, it has all (κ2) κ2 edges, so at least (κ2) κ2 Type C agents that accept. Thus, W()≥Rm+κ+(κ2)=k.W(x)≥ Rm+κ+ κ2=k. (⇐)( ) Assume there exists a lottery ∈Δ(S)x∈ (S) such that W()≥kW(x)≥ k. We prove three claims. Claim 1: xv≤1/κx_v≤ 1/κ for every vertex v∈Vv∈ V. Suppose for a contradiction that for some vertex v, xv>1/κx_v>1/κ. Then every one of the R Type A agents associated with v rejects x (since they accept x if and only if xv≤1/κx_v≤ 1/κ). Thus, we lost at least R acceptances from Type A agents. Even if all other agents (from Type B and Type C) accepted, then W() W(x) ≤R(m−1)+m+M ≤ R(m-1)+m+M =Rm−R+m+M =Rm-R+m+M =Rm−(m+M+1)+m+M =Rm-(m+M+1)+m+M =Rm−1 =Rm-1 <Rm+κ+(κ2)=k, <Rm+κ+ κ2=k, giving us a contradiction. Thus, xv≤1/κx_v≤ 1/κ for all v∈Vv∈ V. Claim 2: At most κ Type B agents accept, and their corresponding vertices have probability mass exactly 1/κ1/κ. Let T:=v∈V:xv≥1/κT:=\v∈ V:x_v≥ 1/κ\ be the set of vertices whose Type B agents accept x. Now, we know from Claim 1 that xv≤1/κx_v≤ 1/κ and together with xv≥1/κx_v≥ 1/κ imply that xv=1/κx_v=1/κ for all v∈Tv∈ T. Then, 1=∑v∈Vxv≥∑v∈Txv=|T|⋅1κ,1= _v∈ Vx_v≥ _v∈ Tx_v=|T|· 1κ, giving us |T|≤κ|T|≤κ. However, since W()≥kW(x)≥ k and by Claim 1, all RmRm Type A agents accept, thus, among Types B and C agents combined, we must have at least W()−Rm=k−Rm=κ+(κ2)W(x)-Rm=k-Rm=κ+ κ2 agents that accept x. Claim 3: A Type C agent with corresponding edge u,v\u,v\ can accept x only if both u,v∈Tu,v∈ T. Note that in order for such an agent to accept x, we must have that xu+xv≥2/κx_u+x_v≥ 2/κ, by definition. Then, since xu≤1/κx_u≤ 1/κ and xv≤1/κx_v≤ 1/κ, we must necessarily have that xu=xv=1/κx_u=x_v=1/κ. Thus, u,v∈Tu,v∈ T. Therefore, the number of Type C agents that accept x is exactly the number of edges of G with both endpoints in T. For any undirected simple graph with |T||T| vertices, the number of edges is at most (|T|2) |T|2. Thus, the total number of agents which are Types B or C that accept x is at most |T|+(|T|2)|T|+ |T|2. However, we established earlier that we need at least κ+(κ2)κ+ κ2 agents among Types B and C to accept x, so |T|+(|T|2)≥κ+(κ2).|T|+ |T|2≥κ+ κ2. (1) Now, let f(y):=y+(y2)=y+y(y−1)2=y(y+1)2.f(y):=y+ y2=y+ y(y-1)2= y(y+1)2. Then, for any integer y≥0y≥ 0, it is clear that f(y)f(y) is strictly increasing. Then, since |T|≤κ|T|≤κ (as established in the proof of Claim 2), we have that f(|T|)≤f(κ)f(|T|)≤ f(κ). Combining this with (1) which gives us f(κ)≤f(|T|)f(κ)≤ f(|T|), we get that f(κ)≤f(|T|)≤f(κ),f(κ)≤ f(|T|)≤ f(κ), essentially giving us f(κ)=f(|T|)⟹κ+(κ2)=|T|+(|T|2).f(κ)=f(|T|) κ+ κ2=|T|+ |T|2. (2) By the strictly increasing property of f, we get that |T|=κ|T|=κ. Combining this with (2), we get that (|T|2)=(κ2) |T|2= κ2. Since |T|=κ|T|=κ, exactly κ Type B agents accept x (namely, those corresponding to vertices in T). Moreover, because W()≥kW(x)≥ k and all RmRm Type A agents accept by Claim 1, we need at least κ+(κ2)κ+ κ2 acceptances coming from Types B and C combined. Hence, at least (κ2) κ2 Type C agents must accept x. On the other hand, by Claim 3, a Type C agent can accept x only if its corresponding edge has both endpoints in T. There is one Type C agent per edge, and among |T|=κ|T|=κ vertices there are at most (|T|2)=(κ2) |T|2= κ2 such edges. Therefore, at most (κ2) κ2 Type C agents can accept x. Combining the two bounds, we conclude that exactly (κ2) κ2 Type C agents accept x, which implies that every unordered pair of distinct vertices in T forms an edge in G. Thus, the induced subgraph on T is complete, i.e., T is a clique of size κ in G. ∎ This hardness result complements our earlier conceptual motivation for unanimity. For unanimity, once each agent’s acceptability halfspace is learned, the remaining task is simply to test feasibility (and select a witness) via linear programming, so the central bottleneck is elicitation via queries. In contrast, moving beyond unanimity to objectives based on maximizing W()W(x) introduces computational intractability even when the full instance (i,τi)i∈N(u_i, _i)_i∈ N is given explicitly. For this reason, we treat unanimity as a clean baseline for conservative, safety-oriented collective decision making, and we leave approximation or structure-exploiting relaxations beyond unanimity to future work. Appendix C Omitted Proofs from Section 3 C.1 ExactThresholdExactThreshold Subroutine We first establish some preliminaries. Fix an agent i∈Ni∈ N and indices k,k′∈[m]k,k ∈[m] such that Query(i,k)=FalseQuery(i,e_k)= False and Query(i,k′)=TrueQuery(i,e_k )= True. Recall the edge lotteries k,k′,α:=αk′+(1−α)k,α∈[0,1].x_k,k ,α:= _k +(1-α)e_k, α∈[0,1]. Along this edge, Ui(k,k′,α)=(1−α)ui(sk)+αui(sk′)=ui(sk)+α(ui(sk′)−ui(sk)).U_i(x_k,k ,α)=(1-α)u_i(s_k)+α u_i(s_k )=u_i(s_k)+α(u_i(s_k )-u_i(s_k)). Since Query(i,k)=FalseQuery(i,e_k)= False implies ui(sk)<τiu_i(s_k)< _i and Query(i,k′)=TrueQuery(i,e_k )= True implies τi≤ui(sk′) _i≤ u_i(s_k ), we have that ui(sk′)−ui(sk)>0u_i(s_k )-u_i(s_k)>0, so Ui(xk,k′,α)U_i(x_k,k ,α) is strictly increasing in α. Thus, there is a unique α∗:=infα∈[0,1]:Query(i,xk,k′,α)=True∈(0,1]α^*:= \α∈[0,1]:Query(i,x_k,k ,α)= True\∈(0,1] such that Query(i,xk,k′,α)=TrueQuery(i,x_k,k ,α)= True if and only if α≥α∗α≥α^*. Solving Ui(xk,k′,α∗)=τiU_i(x_k,k ,α^*)= _i gives α∗=τi−ui(sk)ui(sk′)−ui(sk).α^*= _i-u_i(s_k)u_i(s_k )-u_i(s_k). (3) Under ε -precision, let ui(sk)=aεu_i(s_k)=a , ui(sk′)=bεu_i(s_k )=b , and τi=tε _i=t for integers a,b,ta,b,t. Then b−a∈1,2,…,1/εb-a∈\1,2,…,1/ \ and t−a∈1,2,…,b−at-a∈\1,2,…,b-a\, so (3) equals (t−a)/(b−a)(t-a)/(b-a) and therefore can be written in lowest terms as p/qp/q with 1≤q≤b−a≤1/ε.1≤ q≤ b-a≤ 1/ . (4) Let Q:=1/ε∈ℤ>0Q:=1/ _>0. Any two distinct rationals p/q≠p′/q′p/q≠ p /q with 1≤q,q′≤Q1≤ q,q ≤ Q satisfy |pq−p′q′|=|pq′−p′q|qq′≥1qq′≥1Q2=ε2. | pq- p q |= |pq -p q|q ≥ 1q ≥ 1Q^2= ^2. Consequently, any interval of length <ε2/2< ^2/2 contains at most one rational number whose reduced denominator is at most Q. We now introduce the ExactThresholdExactThreshold subroutine. ExactThreshold(i,k,k′)ExactThreshold(i,k,k ) The subroutine uses membership queries only in the bisection phase. 1. Initialize ℓ←0 ← 0 and u←1u← 1. Note that Query(i,xk,k′,ℓ)=Query(i,ek)=FalseQuery(i,x_k,k , )=Query(i,e_k)= False and Query(i,xk,k′,u)=Query(i,ek′)=TrueQuery(i,x_k,k ,u)=Query(i,e_k )= True. 2. While u−ℓ≥ε2/2u- ≥ ^2/2: (a) Let m←(ℓ+u)/2m←( +u)/2 and query Query(i,xk,k′,m)Query(i,x_k,k ,m). (b) If the answer is True, set u←mu← m; otherwise set ℓ←m ← m. Throughout the loop, the invariant Query(i,xk,k′,ℓ)=FalseQuery(i,x_k,k , )= False and Query(i,xk,k′,u)=TrueQuery(i,x_k,k ,u)= True is maintained, and therefore ℓ<α∗≤u <α^*≤ u. 3. Let Q:=1/εQ:=1/ . By (4), α∗α^* has reduced denominator at most Q, and by the loop condition we have u−ℓ<ε2/2u- < ^2/2. Therefore α∗α^* is the unique rational in [ℓ,u][ ,u] with reduced denominator at most Q. Recover this unique rational and return it as α∗α^*. One concrete reconstruction routine (using no membership queries) is: iterate q=1,2,…,Qq=1,2,…,Q, set p:=⌈qℓ⌉p:= q , and return the first fraction p/qp/q satisfying p/q≤up/q≤ u. Uniqueness implies the returned value equals α∗α^*. We now prove correctness. Note that the monotonicity of α↦Query(i,xk,k′,α)α (i,x_k,k ,α) implies the bisection loop maintains ℓ<α∗≤u <α^*≤ u. On termination, u−ℓ<ε2/2u- < ^2/2, so by the uniqueness argument above there is exactly one rational in [ℓ,u][ ,u] with reduced denominator ≤Q=1/ε≤ Q=1/ , namely α∗α^* itself. Hence the reconstruction step returns α∗α^* exactly. Finally, we prove the query complexity. Starting from an interval of length 11, each bisection query halves the bracket width. Thus the loop performs at most ⌈log(2/ε2)⌉=(log(1/ε)) (2/ ^2 ) =O( (1/ )) queries, and the reconstruction phase uses none. We conclude with a short remark. Why does ε2 ^2 appear in our turning point searches? Under ε -precision, each utility ui(sj)u_i(s_j) and threshold τi _i is an integer multiple of ε . Along any simplex edge between two pure lotteries, an agent’s acceptance boundary occurs at a turning point α∗α^* that is a rational number with reduced denominator at most 1/ε1/ . Any two distinct rationals with denominators at most 1/ε1/ differ by at least ε2 ^2. Consequently, once we bracket α∗α^* into an interval of length <ε2/2< ^2/2 using membership queries, α∗α^* becomes the unique candidate rational in the bracket and can be recovered exactly via rational reconstruction. This is the origin of the (log(1/ε))O( (1/ )) query cost per one-dimensional threshold search. C.2 Geometric Intuition for LearnHyperplaneLearnHyperplane Recovering an agent’s halfspace on the simplex relies on the convexity of linear acceptance regions. Along any edge connecting a rejected vertex ke_k to an accepted vertex k′e_k , there exists exactly one “turning point” where the agent’s utility crosses their threshold τi _i. By finding these turning points on m−1m-1 edges incident to a specific vertex, we identify m−1m-1 points that lie strictly on the hyperplane boundary :⟨i,⟩=τi\x: _i,x = _i\. These points uniquely define the hyperplane (and thus the normal vector ic_i) in the (m−1)(m-1)-dimensional affine hull of the simplex. Algorithm 1 implements this efficiently using binary search to locate these turning points. C.3 Proof of Lemma 3.1 The algorithm begins by querying each pure lottery je_j for j∈[m]j∈[m], making exactly m queries. Each call to ExactThresholdExactThreshold performs bisection for (log(1/ε))O( (1/ )) steps (to obtain an interval of width <ε2/2< ^2/2), followed by rational reconstruction (which uses no queries). Since Algorithm 1 calls ExactThresholdExactThreshold at most m−1m-1 times, the total number of queries is m+((m−1)log(1/ε))=(mlog(1/ε))m+O((m-1) (1/ ))=O(m (1/ )). C.4 Proof of Lemma 3.2 Fix an agent i∈Ni∈ N. Algorithm 1 first queries all pure lotteries and partitions the alternatives as Lacc:=j∈[m]:Ui(j)≥τi=j∈[m]:ui(sj)≥τi,Lrej:=[m]∖Lacc=j∈[m]:ui(sj)<τi.L^acc:=\j∈[m]:U_i(e_j)≥ _i\=\j∈[m]:u_i(s_j)≥ _i\, L^rej:=[m] L^acc=\j∈[m]:u_i(s_j)< _i\. If Lrej=∅L^rej= (i.e., Algorithm 1 returns AcceptAll), then ui(sj)≥τiu_i(s_j)≥ _i for all j∈[m]j∈[m], and for every ∈Δ(S)x∈ (S), Ui()=∑j=1mxjui(sj)≥∑j=1mxjτi=τi,U_i(x)= _j=1^mx_ju_i(s_j)≥ _j=1^mx_j _i= _i, and agent i accepts every lottery, as claimed. If Lacc=∅L^acc= (i.e., Algorithm 1 returns RejectAll), then ui(sj)<τiu_i(s_j)< _i for all j∈[m]j∈[m], and for every ∈Δ(S)x∈ (S), Ui()=∑j=1mxjui(sj)<∑j=1mxjτi=τi,U_i(x)= _j=1^mx_ju_i(s_j)< _j=1^mx_j _i= _i, and agent i rejects every lottery, as claimed. In the remainder of this proof, we assume that Lacc≠∅L^acc≠ and Lrej≠∅L^rej≠ . Then, Algorithm 1 chooses some r∈Lrejr∈ L^rej, so ui(sr)<τiu_i(s_r)< _i. For distinct k,k′∈[m]k,k ∈[m] and α∈[0,1]α∈[0,1], recall the definition xk,k′,α:=αek′+(1−α)ekx_k,k ,α:=α e_k +(1-α)e_k. In particular, for j∈Laccj∈ L^acc, Ui(xr,j,α)=αui(sj)+(1−α)ui(sr)=ui(sr)+α(ui(sj)−ui(sr)).U_i(x_r,j,α)=α u_i(s_j)+(1-α)u_i(s_r)=u_i(s_r)+α(u_i(s_j)-u_i(s_r)). Since ui(sj)≥τi>ui(sr)u_i(s_j)≥ _i>u_i(s_r), we have ui(sj)−ui(sr)>0u_i(s_j)-u_i(s_r)>0, so Ui(xr,j,α)U_i(x_r,j,α) is strictly increasing in α and there is a unique αr,j∈(0,1] _r,j∈(0,1] such that Ui(xr,j,αr,j)=τiU_i(x_r,j, _r,j)= _i. Solving the equality gives αr,j(ui(sj)−ui(sr))=τi−ui(sr)⟹1αr,j=ui(sj)−ui(sr)τi−ui(sr). _r,j(u_i(s_j)-u_i(s_r))= _i-u_i(s_r) 1 _r,j= u_i(s_j)-u_i(s_r) _i-u_i(s_r). (5) Algorithm 1 sets ci,r=0c_i,r=0 and, for every j∈Laccj∈ L^acc, sets ci,j=1/αr,jc_i,j=1/ _r,j. We split our analysis into two cases. Case 1. Suppose αr,j=1 _r,j=1 for all j∈Laccj∈ L^acc (Line 12 of Algorithm 1). Then by (5), we have ui(sj)=τiu_i(s_j)= _i for all j∈Laccj∈ L^acc. Since ui(sk)<τiu_i(s_k)< _i for all k∈Lrejk∈ L^rej, a lottery ∈Δ(S)x∈ (S) satisfies Ui()≥τiU_i(x)≥ _i if and only if it assigns zero probability to rejected alternatives: indeed, Ui()=∑j∈Laccxjτi+∑k∈Lrejxkui(sk)≤∑j∈Laccxjτi+∑k∈Lrejxkτi=τi,U_i(x)= _j∈ L^accx_j _i+ _k∈ L^rejx_ku_i(s_k)≤ _j∈ L^accx_j _i+ _k∈ L^rejx_k _i= _i, with strict inequality whenever xk>0x_k>0 for some k∈Lrejk∈ L^rej (because then ui(sk)<τiu_i(s_k)< _i contributes strictly less). If xk=0x_k=0 for all k∈Lrejk∈ L^rej, then Ui()=∑j∈Laccxjτi=τiU_i(x)= _j∈ L^accx_j _i= _i. Thus the acceptable set is ∈Δ(S):xk=0 for all k∈Lrej\x∈ (S):x_k=0 for all k∈ L^rej\. In this case, Algorithm 1 returns the vector ic_i defined by ci,j=1c_i,j=1 for j∈Laccj∈ L^acc and ci,k=0c_i,k=0 for k∈Lrejk∈ L^rej. Since ∑j∈Laccxj≤∑j=1mxj=1 _j∈ L^accx_j≤ _j=1^mx_j=1, this implies ∑j∈Laccxj=1 _j∈ L^accx_j=1, and thus ∑k∈Lrejxk=0 _k∈ L^rejx_k=0, so xk=0x_k=0 for all k∈Lrejk∈ L^rej For ∈Δ(S)x∈ (S), we have ⟨i,⟩=∑j∈Laccxj _i,x = _j∈ L^accx_j, so ⟨i,⟩≥1⇔∑j∈Laccxj≥1⇔xk=0 for all k∈Lrej, _i,x ≥ 1 _j∈ L^accx_j≥ 1 x_k=0 for all k∈ L^rej, which is exactly the acceptable set. Case 2. There exists some a∈Lacca∈ L^acc with αr,a<1 _r,a<1 (Line 17), which implies ui(sa)>τiu_i(s_a)> _i by (5). For each k∈Lrej∖rk∈ L^rej \r\, Algorithm 1 computes the unique αk,a∈(0,1) _k,a∈(0,1) satisfying Ui(xk,a,αk,a)=τiU_i(x_k,a, _k,a)= _i, i.e., τi=αk,aui(sa)+(1−αk,a)ui(sk), _i= _k,au_i(s_a)+(1- _k,a)u_i(s_k), which is unique because Ui(k,a,0)=ui(sk)<τiU_i(x_k,a,0)=u_i(s_k)< _i and Ui(k,a,1)=ui(sa)>τiU_i(x_k,a,1)=u_i(s_a)> _i. Algorithm 1 sets ci,a=1/αr,ac_i,a=1/ _r,a and then defines for each k∈Lrej∖rk∈ L^rej \r\: ci,k:=1−αk,aci,a1−αk,a.c_i,k:= 1- _k,ac_i,a1- _k,a. We now show that in this case, ci,j=ui(sj)−ui(sr)τi−ui(sr)for all j∈[m].c_i,j= u_i(s_j)-u_i(s_r) _i-u_i(s_r) all j∈[m]. (6) For j∈Laccj∈ L^acc, (6) holds by (5), since Algorithm sets ci,j=1/αr,jc_i,j=1/ _r,j. Also ci,r=0=(ui(sr)−ui(sr))/(τi−ui(sr))c_i,r=0=(u_i(s_r)-u_i(s_r))/( _i-u_i(s_r)), so (6) holds for j=rj=r. Fix k∈Lrej∖rk∈ L^rej \r\. From τi=αk,aui(sa)+(1−αk,a)ui(sk) _i= _k,au_i(s_a)+(1- _k,a)u_i(s_k), we have ui(sk)=τi−αk,aui(sa)1−αk,a,u_i(s_k)= _i- _k,au_i(s_a)1- _k,a, and hence ui(sk)−ui(sr)τi−ui(sr)=11−αk,a⋅τi−ui(sr)−αk,a(ui(sa)−ui(sr))τi−ui(sr)=1−αk,a⋅ui(sa)−ui(sr)τi−ui(sr)1−αk,a. u_i(s_k)-u_i(s_r) _i-u_i(s_r)= 11- _k,a· _i-u_i(s_r)- _k,a(u_i(s_a)-u_i(s_r)) _i-u_i(s_r)= 1- _k,a· u_i(s_a)-u_i(s_r) _i-u_i(s_r)1- _k,a. But by (5) applied to a, we have ci,a=1/αr,a=(ui(sa)−ui(sr))/(τi−ui(sr))c_i,a=1/ _r,a=(u_i(s_a)-u_i(s_r))/( _i-u_i(s_r)), so the last expression equals 1−αk,aci,a1−αk,a=ci,k, 1- _k,ac_i,a1- _k,a=c_i,k, proving (6) for k and thus for all j∈[m]j∈[m]. Finally, for any lottery ∈Δ(S)x∈ (S), using (6) we have ⟨i,⟩≥1⇔∑j=1mui(sj)−ui(sr)τi−ui(sr)xj≥1⇔∑j=1m(ui(sj)−ui(sr))xj≥τi−ui(sr). _i,x ≥ 1 _j=1^m u_i(s_j)-u_i(s_r) _i-u_i(s_r)x_j≥ 1 _j=1^m(u_i(s_j)-u_i(s_r))x_j≥ _i-u_i(s_r). Since ∑j=1mxj=1 _j=1^mx_j=1, the left-hand side equals ∑j=1mui(sj)xj−ui(sr)∑j=1mxj=Ui()−ui(sr) _j=1^mu_i(s_j)x_j-u_i(s_r) _j=1^mx_j=U_i(x)-u_i(s_r), so the inequality is equivalent to Ui()−ui(sr)≥τi−ui(sr)U_i(x)-u_i(s_r)≥ _i-u_i(s_r), i.e., Ui()≥τiU_i(x)≥ _i. This proves that whenever Algorithm 1 returns a vector ic_i, it satisfies ⟨i,⟩≥1⇔Ui()≥τi _i,x ≥ 1 U_i(x)≥ _i for all ∈Δ(S)x∈ (S), as desired. C.5 Proof of Theorem 3.3 We first prove correctness. Let F(C):=∈Δ(S):⟨,⟩≥1 for all ∈CF(C):=\x∈ (S): ,x ≥ 1 for all c∈ C\ be the feasible set determined by the constraints in C. By definition, Select(C)Select(C) returns Null if and only if F(C)=∅F(C)= , and otherwise returns a unique lottery ∈F(C)x∈ F(C). Also, by Lemma 3.2, if ic_i is the vector returned by LearnHyperplaneLearnHyperplane (in the non-RejectAll case), then for every ∈Δ(S)x∈ (S), ⟨i,⟩≥1⇔Ui()≥τi. _i,x ≥ 1 U_i(x)≥ _i. (7) Now, at every iteration of the while loop (Line 5), immediately after the assignment ←Select(C)x (C) (Line 6), the following invariant holds: For every agent i∈N∖N′i∈ N N , C contains the constraint ic_i learned for agent i, and the current candidate x satisfies Ui()≥τiU_i(x)≥ _i. To see this, observe that if i∈N∖N′i∈ N N , then i was previously selected as a violator, and removed from N′N . In that iteration, either • LearnHyperplane(i)=RejectAllLearnHyperplane(i)= RejectAll, in which case the algorithm terminates immediately (so the invariant is only relevant before termination), or • LearnHyperplane(i)=iLearnHyperplane(i)=c_i, then the algorithm adds the returned vector ic_i to C. In later iterations, ←Select(C)∈F(C)x (C)∈ F(C), so in particular, ⟨i,⟩≥1 _i,x ≥ 1. By (7), this implies Ui()≥τiU_i(x)≥ _i. Note that LearnHyperplane(i)≠AcceptAllLearnHyperplane(i)≠ AcceptAll, because we only call LearnHyperplane(i)LearnHyperplane(i) after observing Query(i,)=FalseQuery(i,x)= False. If an agent accepted all pure lotteries, linearity would imply they accept all lotteries, so they could not be a violator. Next, we prove that if Algorithm 2 returns a lottery, it is unanimously acceptable. Suppose the algorithm returns some x (Line 16). This occurs only if there is no violator, which means that for every unlearned agent i∈N′i∈ N , we observed Query(i,)=TrueQuery(i,x)= True, i.e., Ui()≥τiU_i(x)≥ _i. For any learned agent i∈N∖N′i∈ N N , the invariant implies Ui()≥τiU_i(x)≥ _i. Consequently, we get that Ui()≥τiU_i(x)≥ _i for all i∈Ni∈ N, and x is unanimously acceptable. Next, we prove that if Algorithm 2 returns Null, then no unanimously acceptable lottery exists. There are two ways the algorithm returns Null: 1. Select(C)Select(C) returns Null (Line 7). Then F(C)=∅F(C)= . Suppose for a contradiction that there exists a lottery ∗∈Δ(S)x^*∈ (S) such that Ui(∗)≥τiU_i(x^*)≥ _i for all i∈Ni∈ N. In particular, for every learned agent i∈N∖N′i∈ N N , we have Ui(∗)≥τiU_i(x^*)≥ _i. By (7), this implies ⟨i,∗⟩≥1 _i,x^* ≥ 1 for each i∈Cc_i∈ C. Thus, ∗∈F(C)x^*∈ F(C), contradicting F(C)=∅F(C)= . Thus, no unanimously acceptable lottery exists. 2. LearnHyperplane(i)LearnHyperplane(i) returns RejectAll (Line 19). By definition of LearnHyperplaneLearnHyperplane, this means that agent i rejects every pure lottery. By linearity of expected utility, if Ui(j)<τiU_i(e_j)< _i for all j∈[m]j∈[m], then for every ∈Δ(S)x∈ (S), Ui()=∑j=1mxjUi(j)<∑j=1mxjτi=τi,U_i(x)= _j=1^mx_jU_i(e_j)< _j=1^mx_j _i= _i, and agent i rejects every lottery. Thus, unanimity is impossible and returning Null is correct. Finally, we show that Algorithm 2 terminates. In each iteration of the while loop, either the algorithm returns, or it finds a violator i∈N′i∈ N , and then removes i from N′N . Since N′⊆N N and agents are removed at most once, this can happen at most n times. Thus, the algorithm terminates after at most n+1n+1 iterations. Next, we prove the query complexity by providing an upper bound on the number of queries made by Algorithm 2. Let γ be the number of times the algorithm calls LearnHyperplaneLearnHyperplane. Clearly γ≤nγ≤ n. By Lemma 3.1, each call to LearnHyperplaneLearnHyperplane makes (mlog(1/ε))O(m (1/ )) queries. Therefore, all invocations of LearnHyperplaneLearnHyperplane together contribute (nmlog(1/ε))O(nm (1/ )) queries. Next, we count the number of “verification” queries. In an iteration where the unlearned set has size |N′|=k|N |=k, the for loop queries each agent in N′N at most once, so it makes at most k direct queries. Each time a violator is found and learned, |N′||N | decreases by 11. Thus, in the worst case (violator being last each time), the total number of “verification” queries is at most n+(n−1)+⋯+1=n(n+1)2=(n2).n+(n-1)+…+1= n(n+1)2=O(n^2). Thus, the total number of queries made by Algorithm 2 is (n2+nmlog(1/ε))O (n^2+nm (1/ ) ). C.6 Proof of Theorem 3.4 Note that we can assume n≥2n≥ 2 and m≥2m≥ 2, otherwise the problem is trivial. For integer weights w1,…,wn≥1w_1,…,w_n≥ 1, let Nmulti(w)N_multi(w) denote the multiset containing exactly wiw_i labeled copies of each agent i, and so |Nmulti(w)|=∑i=1nwi|N_multi(w)|= _i=1^nw_i. Let WeightedSample(w,r′)WeightedSample(w,r ) return a uniformly random subset Nrand⊆Nmulti(w)N_rand N_multi(w) of size r′r (i.e., |Nrand|=r′|N_rand|=r ) drawn without replacement. Write supp(Nrand)⊆Nsupp(N_rand) N for the set of distinct agents appearing in NrandN_rand. Our algorithm (Algorithm 3) is as follows. For each agent i, let i⊆Δ(S)A_i (S) denote the agent’s acceptable region (halfspace). By Lemma 3.2, either i=Δ(S)A_i= (S) (AcceptAll), or i=∅A_i= (RejectAll), or i=∈Δ(S):⟨i,⟩≥1A_i=\x∈ (S): _i,x ≥ 1\ for the vector ic_i returned by LearnHyperplane(i)LearnHyperplane(i). Then, for any subset of agents N′⊆N N, define the feasible region P(N′):⋂i∈N′i.P(N ): _i∈ N A_i. If P(N′)≠∅P(N )≠ , define N′x_N to be the unique lexicographically maximum point in P(N′)P(N ) (i.e., the output of SelectSelect under the deterministic lexicographic tie-breaking rule from Section 3); otherwise define xN′:=Nullx_N := Null. When no agent in N′N is of type RejectAll (i.e., when i≠∅A_i≠ for all i∈N′i∈ N ), this coincides with N′=Select(i:i∈N′,i≠Δ(S))x_N =Select(\c_i:i∈ N ,A_i≠ (S)\), since AcceptAll agents contribute no constraint. Define the basis for a subset of agents N′⊆N N (where P(N′)≠∅P(N )≠ ) as a minimal subset B⊆N′B N such that P(B)≠∅P(B)≠ and B=N′x_B=x_N . For weight vector w=(w1,…,wn)∈ℤ≥1nw=(w_1,…,w_n) _≥ 1^n and N′⊆N N, write w(N′):=∑i∈N′wiw(N ):= _i∈ N w_i and W:=w(N)W:=w(N). Algorithm 3 Randomized algorithm that returns a unanimously acceptable lottery if one exists, or Null otherwise 1:Set of agents N, and set of alternatives S=s1,…,smS=\s_1,…,s_m\ 2:Lottery =(x1,…,xm)∈Δ(S)x=(x_1,…,x_m)∈ (S) such that Ui()≥τiU_i(x)≥ _i for all i∈Ni∈ N; or Null 3:r←16(m−1)2r← 16(m-1)^2 ⊳ sample size 4:Initialize wi←1,i←False, and i←Nonew_i← 1,\ known_i← False, and c_i← None for all i∈Ni∈ N 5:while True do 6: W←∑i=1nwiW← _i=1^nw_i 7: r′←minr,Wr ← \r,\,W\ ⊳ if W<rW<r we sample the whole multiset 8: Nrand←WeightedSample(w,r′)N_rand (w,r ) ⊳ Nrand⊆Nmulti(w)N_rand N_multi(w), |Nrand|=r′|N_rand|=r 9: for all i∈supp(Nrand)i (N_rand) do 10: if i=Falseknown_i= False then 11: ←LearnHyperplane(i)c (i) 12: if =RejectAllc= RejectAll then return Null 13: else if c=AcceptAllc= AcceptAll then i←Trueknown_i← True and i←Nonec_i← None 14: else knowni←Trueknown_i← True and i←c_i 15: end if 16: end if 17: end for 18: CNrand←i:i∈supp(Nrand)∧i≠NoneC_N_rand←\c_i:i (N_rand)\ \ c_i≠ None\ 19: ←Select(CNrand)x (C_N_rand) 20: if =Nullx= Null then return Null 21: end if 22: Compute the set V:=i∈N:Query(i,)=FalseV:=\i∈ N:Query(i,x)= False\ ⊳ identifying violating agents 23: if V=∅V= then return x 24: end if 25: for all i∈Vi∈ V do 26: wi←2wiw_i← 2w_i ⊳ multiplicative weights update on violators 27: end for 28:end while We begin by proving correctness. If Algorithm 3 returns • x (Line 23), then every agent accepts x (i.e., the set of violating agents V is empty), so x is unanimously acceptable. • Null, then either: – some call to LearnHyperplaneLearnHyperplane returns RejectAll (Line 12), in which case that agent rejects every lottery in Δ(S) (S) and finding a unanimously acceptable lottery is impossible; or – Select(CNrand)Select(C_N_rand) returns Null (Line 20), meaning P(supp(Nrand))=∅P(supp(N_rand))= . Since P(N)⊆P(supp(Nrand))P(N) P(supp(N_rand)), emptiness of P(supp(Nrand))P(supp(N_rand)) implies P(N)=∅P(N)= (note that P(N′)=∩i∈N′iP(N )= _i∈ N A_i with i⊆Δ(S))A_i (S)), i.e., no unanimously acceptable lottery exists. Hence returning Null is correct. Next, we will prove the expected query complexity using a series of intermediate lemmas. We first make use of a lemma from Matoušek et al. [1996, Lemma 1(i)], which highlights a standard property of d-dimensional linear programming: under lexicographic (deterministic) selection, every feasible bounded instance has a basis of size at most d. Since our feasible region lies in the affine hull of dimension d=m−1d=m-1, the claim follows (note that P(N′)⊆Δ(S)P(N ) (S) is always bounded). Lemma C.1. For any subset of agents N′⊆N N, if P(N′)≠∅P(N )≠ , then N′N has a basis B⊆N′B N with |B|≤m−1|B|≤ m-1. This lemma essentially tells us that there exists a “small” set of agents whose constraints determine the final chosen lottery x. This “smallness” is what gives us the (mlogn)O(m n) dependence later. Next, we prove the following weighted sampling lemma. Intuitively, in each iteration, Algorithm 3 sample r′r elements from the multiset Nmulti(w)N_multi(w) (given a weight vector w=(w1,…,wn)w=(w_1,…,w_n)) and solves the LP for the sampled distinct agents supp(Nrand)supp(N_rand) constraints (if an agent i has not been “learned” yet, then run LearnHyperplane(i)LearnHyperplane(i) and store ic_i), getting a lottery supp(Nrand)x_supp(N_rand), which is the unique lexicographically maximum feasible lottery for the sampled constraints (i.e., the output of SelectSelect on the sampled constraint set). The algorithm then verifies this against every agent by querying every agent on this candidate supp(Nrand)x_supp(N_rand). Let V be the agents who reject supp(Nrand)x_supp(N_rand). This lemma gives us an upper bound on the expected total weight of the violators w(V)w(V) after solving the sampled “subproblem” in each iteration. In particular, we will show that the expected total weight of violators for any iteration is [w(V)]≤m⋅Wr′+1E[w(V)]≤ m· Wr +1. Now, we can think of these weights as a sampling distribution (i.e., agent i is more likely to be included in the next sampled subproblem/iteration when wi(t)w_i^(t) is large), and as a penalty counter (if agent i rejects our proposed x, we double wi(t)w_i^(t) for the next iteration). Thus, if the expected total weight of violators is small, then doubling of violator’s weight would flesh them out faster, and provide us some progress towards identifying “more constraining” agents/likely violators faster. Lemma C.2. Let V:=∅V:= if supp(Nrand)=Nullx_supp(N_rand)= Null; and V:=i∈N:supp(Nrand)∉iV:=\i∈ N:x_supp(N_rand) _i\ otherwise. Then [w(V)]≤m⋅Wr′+1.E[w(V)]≤ m· Wr +1. In particular, if r′=min16(m−1)2,Wr = \16(m-1)^2,W\, then if W≤rW≤ r, then r′=Wr =W and the sample contains all agents, so w(V)=0w(V)=0. If W>rW>r, then [w(V)]≤W8(m−1).E[w(V)]≤ W8(m-1). Proof. Each element i∈Nmulti(w)i∈ N_multi(w) is a copy of some agent i^∈N i∈ N. For any Nrand⊆Nmulti(w)N_rand N_multi(w), define Nrand:=supp(Nrand)x_N_rand:=x_supp(N_rand) and π:Nmulti(w)→Nπ:N_multi(w)→ N. Then, define the violator copy set Vcopy(Nrand):=i∈Nmulti(w)∖Nrand:Nrand≠Null and Nrand∉π(i).V_copy(N_rand):=\i∈ N_multi(w) N_rand:x_N_rand≠ Null\ and x_N_rand _π(i)\. Intuitively, agents that have been sampled would have had their constraints learned and thus would not be a violator. Thus, it makes sense that violators only make up the agents that have not been learned (and in particular not sampled in this iteration). If Nrand=Nullx_N_rand= Null then Vcopy(Nrand)=∅V_copy(N_rand)= by definition. If Nrand≠Nullx_N_rand≠ Null and an agent i violates Nrandx_N_rand, then no copy of i can be in NrandN_rand (otherwise i∈supp(Nrand)i (N_rand) and Nrand∈ix_N_rand _i). Thus, all wiw_i copies of i is contained in Nmulti(w)∖NrandN_multi(w) N_rand and also Vcopy(Nrand)V_copy(N_rand). This means that |Vcopy(Nrand)|=w(V),|V_copy(N_rand)|=w(V), (8) i.e., every violating agent contributes all its copies, and no violating agent can appear in NrandN_rand. For any subset Q⊆Nmulti(w)Q N_multi(w), with |Q|=(r′+1)|Q|=(r +1), define its extreme elements X(Q):=i∈Q:i∈Vcopy(Q∖i).X(Q):=\i∈ Q:i∈ V_copy(Q \i\)\. Then, we will show that the number of extreme elements is no more than m: |X(Q)|≤m.|X(Q)|≤ m. (9) We split our analysis into two cases. We first provide an intuition of the proof for the two cases. When P(supp(Q))≠∅P(supp(Q))≠ , then an extreme element corresponds to an agent i i such that removing i i changes the unique optimum and causes i i to be violated. We prove that such an i i must lie in every basis of supp(Q)supp(Q). Since there exists some basis of size ≤m−1≤ m-1, there can be at most m−1m-1 such agents. Also, X(Q)X(Q) cannot contain two copies of the same agent (because then removing one copy would not remove that agent from the support). Thus, |X(Q)|≤m−1|X(Q)|≤ m-1. In the case where P(supp(Q))=∅P(supp(Q))= , then an extreme point corresponds to an agent i i such that removing i makes the subproblem feasible (since Q∖iQ \i\ is feasible by definition of a violator). If removing i i restores feasibility (i.e., makes the intersection nonempty), then any infeasible subcollection must include i (because every subset of a feasible family is feasible). Then we apply Helly’s theorem in dimension m−1m-1: since the family on supp(Nrand)supp(N_rand) is infeasible, there exists an infeasible subfamily of size ≤m≤ m; taking a minimal one gives a “minimal infeasible” set B with |B|≤m|B|≤ m. Every “essential” agent i i (whose removal restores feasibility) must be in all minimal infeasible sets, in particular this one B. Thus, there are at most m such agents. Again there is at most one copy per agent in X(Q)X(Q), so |X(Q)|≤m|X(Q)|≤ m. We prove it formally as follows. Case 1: P(supp(Q))≠∅P(supp(Q))≠ (feasible). Let i∈X(Q)i∈ X(Q) (and i i be the corresponding agent in N). Then Q∖iQ \i\ is such that supp(Q)∖i^=Q∖ix_supp(Q) \ i\=x_Q \i\ exists and violates i i. We claim i i must belong to every basis of supp(Q)supp(Q). Indeed, suppose (for contradiction) there is a basis B⊆supp(Q)B (Q) with i^∉B i∉ B. Then B⊆supp(Q)∖i^B (Q) \ i\ and B=supp(Q)x_B=x_supp(Q). However, supp(Q)∖i^x_supp(Q) \ i\ is feasible for B and (since supp(Q)∖i^x_supp(Q) \ i\ violates i i) we have supp(Q)∖i^≠supp(Q)x_supp(Q) \ i\ _supp(Q). Since supp(Q)x_supp(Q) is feasible for P(supp(Q)∖bi)P(supp(Q) \b_i\) and supp(Q)∖bix_supp(Q) \b_i\ is the lexicographically maximum point in P(supp(Q)∖bi)P(supp(Q) \b_i\), we have that supp(Q)∖bix_supp(Q) \b_i\ is lexicographically at least supp(Q)x_supp(Q). Moreover, supp(Q)∖bi≠supp(Q)x_supp(Q) \b_i\ _supp(Q) because supp(Q)∖bix_supp(Q) \b_i\ violates bib_i while supp(Q)x_supp(Q) satisfies bib_i. Hence supp(Q)∖bix_supp(Q) \b_i\ is lexicographically larger than supp(Q)x_supp(Q). This contradicts the fact that B=supp(Q)x_B=x_supp(Q) is the lexicographically maximum point in P(B)P(B), because supp(Q)∖bix_supp(Q) \b_i\ is feasible for B. Hence i i is in every basis of supp(Q)supp(Q). By Lemma C.1, supp(Q)supp(Q) has some basis of size at most m−1m-1, so there can be at most m−1m-1 such distinct agents i i. Moreover, X(Q)X(Q) contains at most one copy per agent (if Q contained two copies of i i, removing one would still leave i^∈supp(Q∖i) i (Q \i\), so i could not be a violator). Thus |X(Q)|≤m−1|X(Q)|≤ m-1 in this case. Case 2: P(supp(Q))=∅P(supp(Q))= (infeasible). Let i∈X(Q)i∈ X(Q) (and i i be the corresponding agent in N). Then by definition Q∖iQ \i\ is feasible, hence P(supp(Q)∖i^)≠∅P(supp(Q) \ i\)≠ . Therefore, every infeasible subset of supp(Q)supp(Q) must contain i i (otherwise it would remain infeasible inside supp(Q)∖i^supp(Q) \ i\), so i i belongs to every minimal infeasible subset of supp(Q)supp(Q). By Helly’s theorem [Danzer et al., 1963], in the (m−1)(m-1)-dimensional affine hull, we can choose a minimal infeasible subset B⊆supp(Q)B (Q) with |B|≤m|B|≤ m. Since every i i with P(supp(Q)∖i^)≠∅P(supp(Q) \ i\)≠ must lie in every minimal infeasible subset, we have i^∈B i∈ B. Thus there are at most m such distinct agents, and again at most one copy per agent can lie in X(Q)X(Q). Hence |X(Q)|≤m|X(Q)|≤ m. This proves (9). Finally, we count pairs (Nrand,i)(N_rand,i) such that |Nrand|=r′|N_rand|=r and i∈Vcopy(Nrand)i∈ V_copy(N_rand). On one hand, the count equals ∑Nrand:|Nrand|=r′|Vcopy(Nrand)| _N_rand:|N_rand|=r |V_copy(N_rand)|. On the other hand, mapping (Nrand,i)↦Q:=Nrand∪i(N_rand,i) Q:=N_rand∪\i\ gives a bijection to pairs (Q,i)(Q,i) with |Q|=r′+1|Q|=r +1 and i∈X(Q)i∈ X(Q). Therefore, ∑Nrand:|Nrand|=r′|Vcopy(Nrand)|=∑Q:|Q|=r′+1|X(Q)|≤m(Wr′+1), _N_rand:|N_rand|=r |V_copy(N_rand)|= _Q:|Q|=r +1|X(Q)|≤ m Wr +1, where the rightmost inequality follows from the fact that there are (Wr′+1) Wr +1 possible such subsets Q. Then, dividing both sides by (Wr′) Wr and using the fact that (Wr′+1)/(Wr′)=(W−r′)/(r′+1) Wr +1/ Wr =(W-r )/(r +1), we get [|Vcopy(Nrand)|]≤m⋅W−r′r′+1.E[|V_copy(N_rand)|]≤ m· W-r r +1. Finally, from (8), we know that |Vcopy(Nrand)|=w(V)|V_copy(N_rand)|=w(V). Substituting this into the inequality above gives us [w(V)]≤m⋅W−r′r′+1≤m⋅Wr′+1,E[w(V)]≤ m· W-r r +1≤ m· Wr +1, as desired. Then, since Algorithm 3 uses a sample size of r=16(m−1)2r=16(m-1)^2, for m≥2m≥ 2, we get that m⋅Wr′+1≤m⋅W16(m−1)2+1≤W8(m−1),m· Wr +1≤ m· W16(m-1)^2+1≤ W8(m-1), as desired. ∎ The remainder of the proof can broken down into four steps: 1. Construct a small “witness set” B∗B^* of agents of size ≤m≤ m that can “explain” feasibility or infeasibility. 2. Formalize the random process so we can reason about expectations cleanly. 3. Define a potential function Φt _t and prove it has positive expected drift until termination, thus giving us [T]=(mlogn)E[T]=O(m n), where T is the number of iterations of the while loop. 4. Convert the iteration bound into the final expected query bound. Step 1: Constructing the witness set B∗B^*. Next, we construct the witness set B∗⊆NB^* N. Intuitively, this is a set of agents of size at most m that “explains” feasibility (or infeasibility). Intuitively in feasible instances, agents in B∗B^* should be sufficient to “pin down” the final (unanimously acceptable lottery) Nx_N; or in infeasible instances, it already certifies infeasibility. Fix a set B∗⊆NB^* N as follows: • If P(N)≠∅P(N)≠ (feasible instance), let B∗B^* be any basis of N; by Lemma C.1, |B∗|≤m−1|B^*|≤ m-1. • If P(N)=∅P(N)= (infeasible instance), by Helly’s theorem [Danzer et al., 1963] there exists a B∗⊆NB^* N with |B∗|≤m|B^*|≤ m such that P(B∗)=∅P(B^*)= . Let b:=|B∗|≤mb:=|B^*|≤ m. Now, algorithmically, each iteration of the while loop (Line 5) samples some constraints from the subset of agents N′⊆N N and computes N′x_N (Line 8). If N′x_N is not unanimously acceptable, then we can define a violator set V(N′):=i∈N:N′∉iV(N ):=\i∈ N:x_N _i\. Then the following lemma proves that if there is a violation, at least one violator must lie in B∗B^*. This lemma is the key that links our weight doubling update to progress (which we will see with the defined potential function later). Lemma C.3. For any N′⊆N N with N′≠Nullx_N ≠ Null, if V(N′)≠∅V(N )≠ then V(N′)∩B∗≠∅V(N )∩ B^*≠ . Proof. If P(N)=∅P(N)= (and consequently P(B∗)=∅P(B^*)= ), then for any lottery ∈Δ(S)x∈ (S), there exists an agent i∈B∗i∈ B^* with ∉ix _i, so in particular V(N′)∩B∗≠∅V(N )∩ B^*≠ . Thus, we assume that P(N)≠∅P(N)≠ and B∗B^* is a basis of N. Let ∗:=N=B∗x^*:=x_N=x_B^* be the unique tie-broken optimum for the full instance. Suppose for contradiction that N′x_N violates some agent, but none of those violators are in B∗B^*, i.e., V(N′)∩B∗=∅V(N )∩ B^*= but V(N′)≠∅V(N )≠ . This means that N′x_N satisfies every constraint in B∗B^*, i.e., N′∈P(B∗)x_N ∈ P(B^*). Since ∗x^* is the unique lexicographically maximum point in P(B∗)P(B^*) and N′∈P(B∗)x_N ∈ P(B^*), it follows that N′x_N is not lexicographically larger than ∗x^*. On the other hand, ∗x^* is feasible for P(N′)P(N ) (because it satisfies all constraints in N and N′⊆N N), and N′x_N is the lexicographically maximum point in P(N′)P(N ), so N′x_N is lexicographically at least ∗x^*. Therefore, N′=∗x_N =x^*. However, ∗x^* is feasible for all agents, so it cannot have violators, i.e., V(N′)≠∅V(N )≠ , which is a contradiction. ∎ Thus, any violating candidate lottery must violate at least one agent in the witness set B∗B^*. Step 2: Defining the random process. Note that all randomness in Algorithm 3 comes from the calls to WeightedSampleWeightedSample. Let T be the (random) index of the iteration in which the algorithm terminates (i.e., returns x or Null). For t≥1t≥ 1, let: • w(t)=(w1(t),…,wn(t))∈ℤ≥1nw^(t)=(w_1^(t),…,w_n^(t)) ^n_≥ 1 be the weight vector at the start of iteration t, and W(t):=∑i=1nwi(t)W^(t):= _i=1^nw^(t)_i. • r(t):=minr,W(t)r^(t):= \r,W^(t)\ and Nrand(t)⊆Nmulti(w(t))N_rand^(t) N_multi(w^(t)) be the random sample of size r(t)r^(t). • Let t:=supp(Nrand(t))x_t:=x_supp(N_rand^(t)). If t=Nullx_t= Null, then the algorithm terminates at iteration t. Otherwise let V(t):=V(supp(Nrand(t)))=i∈N:t∉iV^(t):=V(supp(N_rand^(t)))=\i∈ N:x_t _i\ and define the violator weight (i.e., total weight of violators at iteration t) as ω(t):=∑i∈Vtwi(t)if t≠Null,0if t=Null.ω^(t)\ :=\ cases _i∈ V_tw_i^(t)&if x_t≠ Null,\\ 0&if x_t= Null. cases If t<Tt<T, then necessarily t≠Nullx_t≠ Null and V(t)≠∅V^(t)≠ . Define the filtration ℱtt≥0\F_t\_t≥ 0 by letting ℱ0F_0 be trivial and ℱt:=σ(Nrand(1),…,Nrand(t))F_t:=σ(N_rand^(1),…,N_rand^(t)) for each t≥1t≥ 1.999Here, σ(⋅)σ(·) denotes σ-algebra generated by the input. Intuitively, ℱtF_t is the history of samples Nrand(1),…,Nrand(t)N_rand^(1),…,N_rand^(t) up to time t. Later on, when we condition on ℱt−1F_t-1, it means we freeze everything that happened in rounds 1,…,t−11,…,t-1, and (the random sample in) round t is the only remaining randomness. Let (Nrand(1),…,Nrand(t))(N_rand^(1),…,N_rand^(t)) be the sample history. Then, conditioned on (Nrand(1),…,Nrand(t))(N_rand^(1),…,N_rand^(t)), the algorithm’s state (and in particular w(t+1)w^(t+1) and W(t+1)W^(t+1)) is fixed, because all other steps are deterministic. To see this, given the sample history up to t, we know (i) which agents were sampled, (i) which constraints were learned, (i) which tx_t was computed (since SelectSelect is deterministic under the fixed lexicographic tie-breaking rule) and (iv) which agents are violators, and thus their new weight vector. Furthermore, T is a stopping time with respect to this filtration (because whether the algorithm has terminated by the end of iteration t is determined by (Nrand(1),…,Nrand(t))(N_rand^(1),…,N_rand^(t))). Intuitively, this means that we can tell whether we have stopped by time t using only information revealed up to time t; we don’t need future samples. We require this because later on, we will have condition expectation terms multiplied by an indicator for whether the algorithm has stopped. In order to correctly pull that indicator outside the conditional expectation, we need this fact (or in other words, this indicator must be measurable with respect to the σ-field we condition on). Step 3: A drift bound for the potential function and [T]E[T]. The key idea is that we want to upper bound [T]E[T], the expected number of iterations. To do so, we will define a potential Φt∈[0,1] _t∈[0,1] for round t, show that before termination, logΦt _t increases by at least a constant in expectation each round, and since logΦt≤0 _t≤ 0 always, and we start from a negative value, we can only have about (mlogn)O(m n) rounds. Fix the witness set B∗⊆NB^* N constructed in Step 1, and recall that b:=|B∗|≤mb:=|B^*|≤ m. Define the potential at the start of iteration t by Φt:=∏i∈B∗wi(t)(W(t))b. _t:= _i∈ B^*w^(t)_i(W^(t))^b. Intuitively, the numerator ∏i∈B∗wi(t) _i∈ B^*w^(t)_i tracks how big the witnesses weights are (multiplicatively); whereas the denominator (W(t))b(W^(t))^b normalizes by the overall scale of weights (since all weights might grow). Raising W to the power of b ensures the potential is always at most 11. Thus, note that 0<Φt≤10< _t≤ 1 for all t, and initially Φ1=n−b _1=n^-b since wi(1)=1w^(1)_i=1 and W(1)=nW^(1)=n. For t<Tt<T, the iteration is nonterminal, so t≠Nullx_t≠ Null and the violator set V(t):=i∈N:t∉iV^(t):=\i∈ N:x_t _i\ is nonempty. Recall that the total violator weight is ω(t):=∑i∈V(t)wi(t)ω^(t):= _i∈ V^(t)w^(t)_i. Lemma C.4. Assume m≥2m≥ 2 and Algorithm 3 uses r=16(m−1)2r=16(m-1)^2. There exists an absolute constant c0>0c_0>0 (e.g., c0=log2−14c_0= 2- 14) such that for every t≥1t≥ 1, [(logΦt+1−logΦt) 1[t<T]|ℱt−1]≥c0⋅[t<T].E [( _t+1- _t)\,1[t<T]\, |\,F_t-1 ]≥ c_0·1[t<T]. Proof. On the event t<T\t<T\ we have V(t)≠∅V^(t)≠ and xt≠Nullx_t≠ Null. By Lemma C.3, V(t)∩B∗≠∅V^(t)∩ B^*≠ , so at least one weight in B∗B^* doubles in iteration t. Hence ∏i∈B∗wi(t+1)≥2∏i∈B∗wi(t) _i∈ B^*w^(t+1)_i≥ 2 _i∈ B^*w^(t)_i. Also the total weight updates as W(t+1)=W(t)+ω(t)W^(t+1)=W^(t)+ω^(t). Therefore, on t<T\t<T\, Φt+1≥Φt⋅2(1+ω(t)/W(t))b, _t+1\;≥\; _t· 2 (1+ω^(t)/W^(t) )^b, and so logΦt+1−logΦt≥log2−blog(1+ω(t)W(t)). _t+1- _t\;≥\; 2-b (1+ ω^(t)W^(t) ). Condition on ℱt−1F_t-1, so w(t)w^(t) and W(t)W^(t) are fixed. Lemma C.2 (with r=16(m−1)2r=16(m-1)^2 and r(t)=minr,W(t)r^(t)= \r,W^(t)\) gives [ω(t)∣ℱt−1]≤W(t)/(8(m−1))E[ω^(t) _t-1]≤ W^(t)/(8(m-1)) for m≥2m≥ 2. Since log(1+u) (1+u) is concave, [log(1+ω(t)W(t))|ℱt−1]≤log(1+[ω(t)∣ℱt−1]W(t))≤log(1+18(m−1)).E [ (1+ ω^(t)W^(t) ) |F_t-1 ]≤ (1+ E[ω^(t) _t-1]W^(t) )≤ (1+ 18(m-1) ). Using b≤mb≤ m and log(1+u)≤u (1+u)≤ u, blog(1+18(m−1))≤m⋅18(m−1)≤14.b (1+ 18(m-1) )≤ m· 18(m-1)≤ 14. Thus [(logΦt+1−logΦt)[t<T]|ℱt−1]≥(log2−14)[t<T],E [( _t+1- _t)1[t<T] |F_t-1 ]≥ ( 2- 14 )1[t<T], so we may take c0=log2−14>0c_0= 2- 14>0. ∎ Lemma C.5. [T]=(mlogn)E[T]=O(m n). Proof. Fix K≥1K≥ 1 and let TK:=minT,KT_K:= \T,K\. Telescoping gives logΦTK−logΦ1=∑t=1K−1(logΦt+1−logΦt)[t<T]. _T_K- _1= _t=1^K-1( _t+1- _t)1[t<T]. Take expectations and apply the drift lemma: [logΦTK]−logΦ1≥c0[minT−1,K−1].E[ _T_K]- _1\;≥\;c_0\,E[ \T-1,K-1\]. Since ΦTK≤1 _T_K≤ 1, we have [logΦTK]≤0E[ _T_K]≤ 0. Therefore [minT−1,K−1]≤log(1/Φ1)c0.E[ \T-1,K-1\]\;≤\; (1/ _1)c_0. Letting K→∞K→∞ and using Φ1=n−b _1=n^-b gives [T]≤1+blognc0=(mlogn),E[T]≤ 1+ b nc_0=O(m n), since b≤mb≤ m and c0c_0 is an absolute constant. ∎ Step 4: Expected number of LearnHyperplaneLearnHyperplane calls and query complexity. Finally, we prove the expected number of LearnHyperplaneLearnHyperplane calls and conclude with the query complexity of Algorithm 3. Each iteration samples r(t)≤r^(t)≤ r copies, hence at most r distinct agents appear in supp(Nrand(t))supp(N_rand^(t)). Since each agent’s hyperplane is learned at most once, the total number of distinct LearnHyperplaneLearnHyperplane calls is at most L≤minn,rTL≤ \n,rT\. Since the function y↦minn,ryy \n,ry\ is concave, taking expectations and using Jensen’s inequality, we get [L]≤minn,r[T]=(minn,m3logn)E[L]≤ \n,\,r\,E[T]\=O( \n,\ m^3 n\), where the equality is using Lemma C.5 and r=Θ((m−1)2)r= ((m-1)^2). Finally, in any iteration that reaches Line 22, the verification step queries all n agents once; thus each iteration uses at most n verification queries, and the total verification cost is at most nTnT queries. Each call to LearnHyperplaneLearnHyperplane makes (mlog(1/ε))O(m (1/ )) queries, by Lemma 3.1. Thus the total expected query complexity is (n[T])+(mlog(1/ε)⋅[L])=(nmlogn+minn,m3logn⋅mlog(1/ε)),O (n\,E[T] )+O (m (1/ )·E[L] )=O(nm n+ \n,m^3 n\· m (1/ )), as desired. C.7 Remark on finding infeasibility witness set When our algorithms output Null, they can also output an explicit infeasibility witness: a subset of agents B⊆NB N such that ⋂i∈Bi=∅ _i∈ BA_i= . This can be done without any additional membership queries. If LearnHyperplane(i)LearnHyperplane(i) returns RejectAll, we may take B=iB=\i\. Otherwise, Null is returned only when SelectSelect is infeasible on a set of already learned halfspaces; since these constraints are explicit, Helly’s theorem [Helly, 1923] implies there exists an infeasible subcollection of size at most m in the (m−1)(m\!-\!1)-dimensional affine hull. Such a witness subset can be extracted offline (e.g., via a standard LP routine) and returned alongside Null. Appendix D Omitted Proofs from Section 4 D.1 Proof of Theorem 4.1 We prove the lower bound for deterministic algorithms first, and then extend it to randomized algorithms. Any deterministic query algorithm can be represented as a (possibly infinite) binary decision tree T. Each internal node is labeled by a query Query(i,)Query(i,x), where i∈Ni∈ N and ∈Δ(S)x∈ (S). The two outgoing edges correspond to the oracle answers True and False. Each leaf is labeled either by an output lottery ∗∈Δ(S)x^*∈ (S) or by Null. For an instance ℐI, let QT(ℐ)Q_T(I) denote the number of queries made on ℐI, i.e., the depth of the root-to-leaf path followed by T on ℐI. The worst-case query complexity of T is supℐQT(ℐ) _IQ_T(I). We call T correct if on every instance ℐI it outputs a unanimously acceptable lottery when one exists, and outputs Null otherwise. Then, we have the following lemma. Lemma D.1. Let T be any correct decision tree. Fix any feasible instance ℐI (i.e., there exists ∈Δ(S)x∈ (S) such that Ui()≥τiU_i(x)≥ _i for all i∈Ni∈ N). Then along the (unique) root-to-leaf path traversed by T on ℐI, every agent i∈Ni∈ N is queried at least once. In particular, QT(ℐ)≥nQ_T(I)≥ n. Proof. Let P be the root-to-leaf path followed by T on ℐI. Since ℐI is feasible and T is correct, the reached leaf is labeled by some lottery ∗x^* (not Null). Suppose for contradiction that there exists an agent j∈Nj∈ N that is never queried along P. Construct a new instance ℐ′I by changing only agent j as follows: set uj′(s)=0u _j(s)=0 for all s∈Ss∈ S and set τj′=ετ _j= . Then for every lottery ∈Δ(S)x∈ (S), we have Uj′()=0<τj′U _j(x)=0<τ _j, so agent j rejects every query. All other agents are unchanged, so every query made along P (which never involves j) receives the same answer on ℐ′I as on ℐI. Therefore T follows the same path P on ℐ′I and outputs the same ∗x^*. However, ℐ′I is infeasible (agent j rejects all lotteries), so correctness requires output Null, a contradiction. Thus, every agent must be queried at least once along P. ∎ Next, we introduce a grid family of lotteries. Since 1/ε∈ℤ+1/ _+ by our finite-precision assumption, define the ε -grid on the simplex by Δε(S):=x∈Δ(S):xj∈0,ε,2ε,…,1∀j∈[m],andΔε+(S):=x∈Δε(S):xj≥ε∀j∈[m]. _ (S):= \x∈ (S):x_j∈\0, ,2 ,…,1\\ ∀ j∈[m] \, _ ^+(S):=\x∈ _ (S):x_j≥ \ ∀ j∈[m]\. We only use these sets to define a hard family; the algorithm itself may query arbitrary rational lotteries. Lemma D.2. Fix m≥2m≥ 2 and ε>0 >0 such that 1/ε≥m1/ ≥ m. For each =(x1,…,xm)∈Δε+(S)x=(x_1,…,x_m)∈ _ ^+(S), define an instance ℐI_x with m agents as follows: for each agent i∈[m]i∈[m], ui(si)=1,ui(sj)=0(j≠i), and τi=xi.u_i(s_i)=1, u_i(s_j)=0\ \ (j≠ i), and _i=x_i. Then the set of unanimously acceptable lotteries in ℐI_x is exactly the singleton \x\. Moreover, any correct deterministic decision tree has depth at least Ω((m−1)log(1/ε)) ((m-1) (1/ )) on some instance ℐI_x. Proof. For any lottery ′=(x1′,…,xm′)∈Δ(S)x =(x _1,…,x _m)∈ (S) and any i∈[m]i∈[m], the utility is Ui(′)=xi′U_i(x )=x _i. Thus agent i accepts ′x if and only if xi′≥τi=xix _i≥ _i=x_i. First, x is unanimously acceptable since xi=τix_i= _i for all i. Now take any unanimously acceptable ′x . Then xi′≥xix _i≥ x_i for all i∈[m]i∈[m]. Let δi:=xi′−xi≥0 _i:=x _i-x_i≥ 0. Because both x and ′x lie in the simplex, ∑i=1mδi=∑i=1mxi′−∑i=1mxi=1−1=0, _i=1^m _i= _i=1^mx _i- _i=1^mx_i=1-1=0, so δi=0 _i=0 for all i, i.e., ′=x =x. Hence the unanimously acceptable set is \x\. Therefore, for distinct ,′∈Δε+(S)x,x ∈ _ ^+(S), a correct algorithm must output different lotteries on ℐI_x and ℐx′I_x . In a decision tree, the output at a leaf is fixed, so ℐI_x and ℐx′I_x must reach different leaves. Hence any correct tree has at least |Δε+(S)|| _ ^+(S)| leaves. We now lower bound |Δε+(S)|| _ ^+(S)|. Writing xi=kiεx_i=k_i with integers ki≥1k_i≥ 1, the constraint ∑i=1mxi=1 _i=1^mx_i=1 becomes ∑i=1mki=1/ε _i=1^mk_i=1/ . The number of positive integer solutions is |Δε+(S)|=(1/ε−1m−1)| _ ^+(S)|= 1/ -1m-1. A binary tree of depth d has at most 2d2^d leaves, so d≥log|Δε+(S)|d≥ | _ ^+(S)|. Finally, using the standard inequality (ab)≥(a/b)b ab≥(a/b)^b for a≥b≥1a≥ b≥ 1, with a=1/ε−1a=1/ -1 and b=m−1b=m-1, we get log|Δε+(S)|=log(1/ε−1m−1)≥(m−1)log(1/ε−1m−1)≥(m−1)log(1εm). | _ ^+(S)|= 1/ -1m-1≥(m-1) ( 1/ -1m-1 )≥(m-1) ( 1 m ). Then, since m≤(1/ε)1−δm≤(1/ )^1-δ for some fixed δ∈(0,1]δ∈(0,1] (by our assumption in the preliminaries), we have 1εm≥(1/ε)δ 1 m≥(1/ )^δ, hence log(1/(εm))≥δlog(1/ε) (1/( m))≥δ (1/ ). Thus log|Δε+(S)|=Ω((m−1)log(1/ε)) | _ ^+(S)|= ((m-1) (1/ )), proving the lemma. ∎ We now prove the stated lower bound (our main result) for deterministic algorithms, by splitting into two cases. Case 1: n≥mn≥ m. For each ∈Δε+(S)x∈ _ ^+(S), define an instance ℐ~ I_x with n agents as follows. Agents 1,…,m1,…,m are defined exactly as in Lemma D.2. The remaining n−mn-m agents are dummy agents that accept every lottery: for each i∈m+1,…,ni∈\m+1,…,n\ set ui(sj)=1 for all j∈[m]andτi=1.u_i(s_j)=1 for all j∈[m] _i=1. Then Ui(′)=1U_i(x )=1 for every lottery ′x , so these agents always answer True. The unanimously acceptable set of ℐ~ I_x is still \x\, since the dummy agents impose no constraint and the first m agents force uniqueness by Lemma D.2. Let T be any correct decision tree and consider its behavior on the family of instances ℱ:=ℐ~:∈Δε+(S)F:=\ I_x:x∈ _ ^+(S)\. By Lemma D.1, on every feasible instance ℐ~ I_x, the path followed by T queries each of the n agents at least once. In particular, on each ℐ~ I_x it makes at least n−mn-m queries to the dummy agents. Now prune T by deleting every internal node that queries a dummy agent and contracting to its True child (which is the only possible answer on ℱF). Call the pruned tree T′T . For each instance ℐ~∈ℱ I_x , the pruned execution path in T′T ends at a leaf labeled by x (the same output), so distinct x still reach distinct leaves of T′T . Thus, T′T has at least |Δε+(S)|| _ ^+(S)| leaves, implying that some ℐ~ I_x satisfies QT′(ℐ~)≥log|Δε+(S)|Q_T ( I_x)≥ | _ ^+(S)|. For that same instance, QT(ℐ~)≥(n−m)+QT′(ℐ~)≥(n−m)+log|Δε+(S)|.Q_T( I_x)\ ≥\ (n-m)+Q_T ( I_x)\ ≥\ (n-m)+ | _ ^+(S)|. By Lemma D.2, log|Δε+(S)|=Ω((m−1)log(1/ε)) | _ ^+(S)|= ((m-1) (1/ )), so supℐQT(ℐ)≥Ω((n−m)+(m−1)log(1/ε)). _IQ_T(I)≥ ((n-m)+(m-1) (1/ ) ). Case 2: n<mn<m. Consider lotteries supported on the first n alternatives: Δn+(S):=∈Δ(S):xi∈ε,2ε,…,1 for all i≤n,xi≥ε for all i≤n, and xn+1=⋯=xm=0. _n^+(S):= \x∈ (S):x_i∈\ ,2 ,…,1\ for all i≤ n,\ x_i≥ for all i≤ n, and x_n+1=·s=x_m=0 \. For each x∈Δn+(S)x∈ _n^+(S) define an instance ℐ I_x with n agents, where each agent i∈[n]i∈[n] has ui(si)=1,ui(sj)=0(j≠i), and τi=xi.u_i(s_i)=1, u_i(s_j)=0\ (j≠ i), and _i=x_i. We claim the unanimously acceptable set of ℐ I_x is \x\. Indeed, if a lottery ′x is unanimously acceptable, then for each agent i≤ni≤ n we have Ui(′)=xi′≥τi=xiU_i(x )=x _i≥ _i=x_i. For j>nj>n, xj=0x_j=0 and xj′≥0x _j≥ 0, so xj′≥xjx _j≥ x_j as well. Thus, ′≥x coordinate-wise, but since ,′∈Δ(S)x,x ∈ (S) we must have ∑j(xj′−xj)=0 _j(x _j-x_j)=0, forcing ′=x =x. Therefore any correct decision tree must have at least |Δn+(S)|| _n^+(S)| leaves over the family ℐ^:∈Δn+(S)\ I_x:x∈ _n^+(S)\, and consequently, some instance requires at least log|Δn+(S)| | _n^+(S)| queries. Moreover, |Δn+(S)|=(1/ε−1n−1)| _n^+(S)|= 1/ -1n-1, and under the assumption that n<m≤(1/ε)1−δn<m≤(1/ )^1-δ we obtain log|Δn+(S)|=Ω((n−1)log(1/ε)) | _n^+(S)|= ((n-1) (1/ )). This gives us supℐQT(ℐ)≥Ω((n−1)log(1/ε)). _IQ_T(I)≥ ((n-1) (1/ ) ). Combining the two cases gives us the deterministic lower bound supℐQT(ℐ)≥Ω((n−minn,m)+(minn,m−1)log(1/ε)), _IQ_T(I)≥ ((n- \n,m\)+( \n,m\-1) (1/ ) ), Now, we detail the extension of this lower bound to randomized algorithms. We interpret the query complexity of a randomized algorithm as worst-case expected number of queries (and the algorithm must be correct on every instance for every realization of its internal randomness). Formally, a randomized algorithm R is a distribution over deterministic decision trees. Let TσT_σ denote the deterministic tree obtained by fixing the random seed σ. Define the expected query complexity of R on instance ℐI as QR(ℐ):=σ[QTσ(ℐ)],Q_R(I):=E_σ [Q_T_σ(I) ], and its worst-case expected query complexity as supℐQR(ℐ) _IQ_R(I). We use Yao’s minimax principle [Yao, 1977] in the following form. Lemma D.3. For any distribution μ over instances, infRsupℐQR(ℐ)≥minTℐ∼μ[QT(ℐ)], _R\ _I\ Q_R(I)≥ _TE_I μ [Q_T(I) ], where the minimum ranges over correct deterministic decision trees T, and the infimum ranges over correct randomized algorithms R (distributions over correct deterministic trees). Proof. Fix μ and a randomized algorithm R (a distribution over correct deterministic trees). Then supℐQR(ℐ)≥ℐ∼μ[QR(ℐ)]=ℐ∼μσ[QTσ(ℐ)]=σℐ∼μ[QTσ(ℐ)]≥infTℐ∼μ[QT(ℐ)]. _IQ_R(I) _I μ[Q_R(I)]=E_I μE_σ[Q_T_σ(I)]=E_σE_I μ[Q_T_σ(I)]≥ _TE_I μ[Q_T(I)]. Taking infR _R on the left-hand side gives us the claim. ∎ We also use a standard average-depth bound. Lemma D.4. Let T be a binary decision tree. For any leaf ℓ of T, let depth(ℓ)depth( ) denote the number of internal nodes on the path from the root to ℓ . Let L be any finite set of leaves of T, and let ℓ∼Unif(L) (L) be a uniformly random leaf in L. Then [depth(ℓ)]≥log|L|E[depth( )]≥ |L|. Proof. By Kraft’s inequality, ∑ℓ∈L2−depth(ℓ)≤1 _ ∈ L2^-depth( )≤ 1. Let D:=depth(ℓ)D:=depth( ). Since the function f(y)=2−yf(y)=2^-y is convex, Jensen’s inequality gives us 2−[D]=f([D])≤[f(D)]=[2−D].2^-E[D]=f(E[D]) [f(D)]=E[2^-D]. Because ℓ is uniform on L, [2−D]=1|L|∑ℓ∈L2−depth(ℓ)≤1|L|E[2^-D]= 1|L| _ ∈ L2^-depth( )≤ 1|L|. Taking log of both sides gives us [D]≥log|L|E[D]≥ |L|. ∎ Now choose μ to be the uniform distribution over the hard family from the relevant deterministic case: • If n≥mn≥ m, let μ be uniform over ℱ=ℐ~:∈Δε+(S)F=\ I_x:x∈ _ ^+(S)\. • If n<mn<m, let μ be uniform over ℐ^:∈Δn+(S)\ I_x:x∈ _n^+(S)\. Lemma D.5. For every correct deterministic decision tree T, ℐ∼μ[QT(ℐ)]≥(n−m)+log|Δε+(S)|,if n≥m,log|Δn+(S)|,if n<m.E_I μ[Q_T(I)]≥ cases(n-m)+ | _ ^+(S)|,&if n≥ m,\\ | _n^+(S)|,&if n<m. cases Proof. We prove the two cases. Case n≥mn≥ m. Fix a correct deterministic tree T. For any ℐ=ℐ~∈ℱI= I_x , Lemma D.1 implies that the execution path on ℐI queries each of the n agents at least once, hence makes at least n−mn-m queries to the dummy agents. Prune T into T′T by contracting dummy-agent query nodes to their True child, exactly as in the deterministic proof. For each ℐ∈ℱI we have QT(ℐ)≥(n−m)+QT′(ℐ)Q_T(I)≥(n-m)+Q_T (I). Moreover, since each ℐ=ℐ~I= I_x has a unique correct output x, the map ℐ↦I (reached leaf of T′T ) is injective over ℱF, and its image is a set L of size |Δε+(S)|| _ ^+(S)|. Because μ is uniform over ℱF, the induced distribution on L is uniform. Applying Lemma D.4 to T′T gives us ℐ∼μ[QT′(ℐ)]≥log|Δε+(S)|E_I μ[Q_T (I)]≥ | _ ^+(S)|. Therefore, I∼μ[QT(I)]≥(n−m)+log|Δε+(S)|.E_I μ[Q_T(I)]≥(n-m)+ | _ ^+(S)|. Case n<mn<m. The same injectivity argument applies (no pruning needed): distinct x induce distinct leaves, and μ is uniform on that family, so Lemma D.4 gives ℐ∼μ[QT(I)]≥log|Δn+(S)|E_I μ[Q_T(I)]≥ | _n^+(S)|. ∎ Finally, by Lemma D.3 and Lemma D.5, infRsupℐQR(ℐ)≥(n−m)+log|Δε+(S)|,if n≥m,log|Δn+(S)|,if n<m. _R _IQ_R(I)≥ cases(n-m)+ | _ ^+(S)|,&if n≥ m,\\ | _n^+(S)|,&if n<m. cases Using Lemma D.2 (and the same binomial counting bound with m replaced by n in the second case), we have log|Δε+(S)|=Ω((m−1)log(1/ε)) | _ ^+(S)|= ((m-1) (1/ )) and log|Δn+(S)|=Ω((n−1)log(1/ε)) | _n^+(S)|= ((n-1) (1/ )). Therefore every correct randomized algorithm satisfies supℐQR(ℐ)≥Ω((n−minn,m)+(minn,m−1)log(1/ε)), _IQ_R(I)≥ ((n- \n,m\)+( \n,m\-1) (1/ ) ), completing the proof for randomized algorithms as well. D.2 Proof of Theorem 4.2 Consider the single-agent case n=1n=1. For each j∈[m]j∈[m], define a feasible instance ℐjI_j by setting τ1=1,u1(sj)=1,u1(sk)=0for all k∈[m]∖j. _1=1, u_1(s_j)=1, u_1(s_k)=0\ \ for all k∈[m] \j\. Also define an infeasible instance ℐ0I_0 by τ1=1,u1(sk)=0for all k∈[m]. _1=1, u_1(s_k)=0\ \ for all k∈[m]. We first characterize the oracle on these instances. Fix any lottery ∈Δ(S)x∈ (S). On ℐjI_j, we have U1()=⟨1,⟩=xj,U_1(x)= _1,x =x_j, and therefore Query(1,)=True⇔xj≥1⇔=j,Query(1,x)= True x_j≥ 1 =e_j, where the last equivalence uses that ∈Δ(S)x∈ (S) implies xj≤1x_j≤ 1 with equality if and only if =jx=e_j. Thus, ℐjI_j is feasible and the acceptable set is exactly j\e_j\. On ℐ0I_0, we have U1()=0<τ1=1U_1(x)=0< _1=1 for every ∈Δ(S)x∈ (S), so Query(1,)=FalseQuery(1,x)= False for every query and the instance is infeasible. Next, we show the lower bound on deterministic algorithms. Let ℱF be any deterministic algorithm that is correct on every instance. Run ℱF on ℐ0I_0. Since ℐ0I_0 rejects every lottery, every query made by ℱF is answered False, and (by correctness) ℱF must eventually halt and output Null. Let q0q_0 be the number of queries ℱF makes on this run, and let J:=j∈[m]:ℱ queried the pure lottery j at least once among its first q0 queries.J:=\j∈[m]:$ F$ queried the pure lottery $e_j$ at least once among its first $q_0$ queries\. If |J|<m|J|<m, choose some j∗∈[m]∖Jj^*∈[m] J. Consider running ℱF on the feasible instance ℐj∗I_j^*. By our characterization, ℐj∗I_j^* answers True only on the single query j∗e_j^*, and by the choice of j∗j^*, ℱF does not query j∗e_j^* among its first q0q_0 queries. Therefore, the first q0q_0 oracle answers received by ℱF on ℐj∗I_j^* are also all False. Since ℱF is deterministic, it follows that ℱF receives exactly the same query/answer history on ℐ0I_0 and on ℐj∗I_j^*, and hence produces the same output on both instances. Now, we show that this is impossible: correctness requires output Null on ℐ0I_0, but requires output j∗e_j^* on ℐj∗I_j^* because j∗e_j^* is the only acceptable lottery there. Thus we must have |J|=m|J|=m, meaning that ℱF queries every pure lottery 1,…,me_1,…,e_m before it can correctly output Null on ℐ0I_0. In particular, q0≥mq_0≥ m, so the worst-case query complexity of any correct deterministic algorithm is at least m. Finally, we prove the lower bound for any randomized algorithm. Let ℛR be any randomized algorithm in our model (as mentioned in Section 2, such a randomized algorithm is always correct for every realization of internal randomness). Fix any realization of its internal randomness; this gives us a deterministic algorithm that is still correct on every instance. Applying the deterministic lower bound above to this deterministic instantiation shows it makes at least m queries on ℐ0I_0. Since this holds for every realization, ℛR makes at least m queries on ℐ0I_0 in expectation as well. Therefore every correct randomized algorithm has worst-case expected query complexity at least m. Appendix E Omitted Proofs from Section 5 E.1 Proof of Theorem 5.1 We prove the statement for an arbitrary permutation σ; instantiating with σ=σ^σ= σ gives us the result. Fix any permutation σ of N, and consider Algorithm 2[σ]. Recall the definition of record agents: for any permutation σ, let R(σ)R(σ) be the number of agents on which LearnHyperplaneLearnHyperplane is invoked on during the run of Algorithm 2[σ]. Correctness follows from Theorem 3.3, whose proof does not rely on the specific fixed scan order 1,2,…,n1,2,…,n, only on the facts that (i) in each iteration of the while loop (Line 5 of Algorithm 2) the algorithm proposes a candidate ←Select(C)x (C), (i) it checks unlearned agents one-by-one until either finding a violator or exhausting the scan, and (i) upon finding a violator it elicits that agent’s halfspace and adds it to C (or returns Null if LearnHyperplaneLearnHyperplane returns RejectAll). These properties remain true under any fixed permutation order σ. Hence Algorithm 2[σ]2[σ] outputs a unanimously acceptable lottery when one exists and outputs Null otherwise. Thus, we focus on proving its query complexity, bounding the number of queries made by Algorithm 2[σ][σ]. By Lemma 3.1, each call to LearnHyperplaneLearnHyperplane makes (mlog(1/ε))O(m (1/ )) queries. Since Algorithm 2[σ][σ] calls LearnHyperplaneLearnHyperplane exactly for the R(σ)R(σ) agents, the total number of elicitation queries is (R(σ)mlog(1/ε))O(R(σ)\,m (1/ )) Consider one iteration of the outer while loop of Algorithm 2[σ][σ] (Line 5). After computing ←Select(C)x (C), the algorithm queries agents in the order σ(1),…,σ(n)σ(1),…,σ(n), skipping learned agents (those not in N′N ), and stops either when it finds the first violator j with Query(j,)=FalseQuery(j,x)= False, or when it finishes the scan and returns x. In a single such iteration, each agent is queried at most once, so each iteration uses at most n membership queries for verification. Let γ be the number of while iterations executed. Every such iteration (except possibly the last) ends by learning at least one new violating agent (and hence invoking LearnHyperplaneLearnHyperplane at least once), and each agent can be learned at most once because it is removed from N′N immediately after being learned. Therefore, γ≤R(σ)+1γ≤ R(σ)+1, and the total number of verification queries is at most nγ≤n(R(σ)+1).nγ≤ n(R(σ)+1). The total number of membership queries made by Algorithm 2[σ][σ] is therefore (R(σ)mlog(1/ε))+n(R(σ)+1)=((n+mlog(1/ε))(R(σ)+1)).O(R(σ)\,m (1/ ))+n(R(σ)+1)=O((n+m (1/ ))(R(σ)+1)). Since we assumed R(σ)≥1R(σ)≥ 1, then R(σ)+1≤2R(σ)R(σ)+1≤ 2R(σ), and so the query complexity is simply ((n+mlog(1/ε))R(σ)).O((n+m (1/ ))\,R(σ)). If R(σ)=0R(σ)=0, the algorithm makes a single verification scan and uses at most n queries, which is consistent with the (R(σ)+1)(R(σ)+1) bound. E.2 Proof of Theorem 5.2 We prove the statement for an arbitrary permutation σ; instantiating it with σ=σ^σ= σ gives us the result. Fix any permutation σ of N, and consider Algorithm 3[σ][σ]. Recall that Algorithm 3[σ][σ] is equivalent to running Algorithm 3, except that it initializes the weights as wi(1):=⌈nrankσ(i)⌉for all i∈N,w_i^(1):= nrank_σ(i) all i∈ N, and then runs the same sampling and multiplicative updating procedure as in Algorithm 3. Correctness follows from Algorithm 3, whose proof does not rely on how weights are initialized, only on: (i) correctness of LearnHyperplaneLearnHyperplane, (i) the fact that returning x when no violators exist is unanimously acceptable, and (i) the fact that returning Null on RejectAll or on infeasible sampled constraints is correct. Thus, we focus on proving its query complexity. In the proof of Theorem 3.4 (Step 1), a witness set B⊆NB N is: • if the instance is feasible (P(N)≠∅P(N)≠ ): any basis B of N, with |B|≤m−1|B|≤ m-1; • if infeasible (P(N)=∅P(N)= ): any Helly witness B with |B|≤m|B|≤ m and P(B)=∅P(B)= . Witness parameter. Let W be the family of valid witness sets used in the analysis of Algorithm 3: W consists of bases when P(N)≠∅P(N)≠ and Helly witnesses when P(N)=∅P(N)= . Define the prefix-witness parameter K:=E(σ):=minB∈Wmaxi∈Brankσ(i),K:=E(σ):= _B∈ W _i∈ Brank_σ(i), i.e., there exists some witness set contained in the first K positions of σ. Fix a witness set B∗∈WB^*∈ W achieving this minimum, and let b:=|B∗|≤mb:=|B^*|≤ m. Potential and drift. Let w(t)w^(t) be the weight vector at iteration t, W(t):=∑i=1nwi(t)W^(t):= _i=1^nw_i^(t), and define the potential Φt:=∏i∈B∗wi(t)(W(t))b. _t:= _i∈ B^*w_i^(t)(W(t))^b. As in Lemma C.4 in the proof of Theorem 3.4, on every nonterminal iteration t<Tt<T, Lemma C.3 implies the violator set intersects B∗B^*, hence the numerator multiplies by at least 22, while the denominator increases by a factor (1+ω(t)/W(t))b(1+ω^(t)/W^(t))^b. Using Lemma C.2 (with r=16(m−1)2r=16(m-1)^2) to bound E[ω(t)∣ℱt−1]E[ω^(t) _t-1] and concavity of log , we obtain a constant c0>0c_0>0 (e.g. c0=log2−1/4c_0= 2-1/4) such that [(logΦt+1−logΦt)[t<T]∣ℱt−1]≥c0[t<T].E [( _t+1- _t)1[t<T] _t-1 ]\;≥\;c_01[t<T]. Bounding [T]E[T]. For M≥1M≥ 1, let T(M):=minT,MT^(M):= \T,M\. Telescoping and the drift bound gives us [minT−1,M−1]≤log(1/Φ1)c0.E[ \T-1,M-1\]≤ (1/ _1)c_0. Letting M→∞M→∞ (monotone convergence) gives us [T]≤1+log(1/Φ1)c0=(log(1/Φ1)).E[T]≤ 1+ (1/ _1)c_0=O( (1/ _1)). Bounding Φ1 _1 with predictions. Under the initialization inferred from our predicted permutation, W(1)=∑k=1n⌈nk⌉≤∑k=1n(nk+1)=n(∑k=1n1k+1).W^(1)= _k=1^n nk ≤ _k=1^n ( nk+1 )=n ( _k=1^n 1k+1 ). Moreover, every i∈B∗i∈ B^* has rankσ(i)≤Krank_σ(i)≤ K, thus wi(1)=⌈nrankσ(i)⌉≥nK⟹∏i∈B∗wi(1)≥(n/K)b.w_i^(1)= nrank_σ(i) ≥ nK _i∈ B^*w_i^(1)≥(n/K)^b. Therefore, Φ1≥(n/K)b(n(∑k=1n1k+1))b=1((∑k=1n1k+1)K)b, _1≥ (n/K)^b(n( _k=1^n 1k+1))^b= 1(( _k=1^n 1k+1)K)^b, so log(1/Φ1)≤blog((∑k=1n1k+1)K)≤mlog((logn)K). (1/ _1)≤ b ( ( _k=1^n 1k+1 )K )≤ m (O( n)K ). Query complexity. Each iteration uses at most n membership queries in the verification step, so verification costs (n[T])O(nE[T]). Let L be the number of distinct agents whose hyperplanes are learned. Each iteration samples at most r=(m2)r=O(m^2) agents, and each agent is learned at most once, so L≤minn,rTL≤ \n,rT\ and by concavity [L]≤minn,r[T]=(minn,m3log(Klogn)).E[L]≤ \n,rE[T]\=O( \n,m^3 (K n )\). Each learned hyperplane costs (mlog(1/ε))O(m (1/ )) queries (by Lemma 3.1), giving total expected queries (nmlog(Klogn))+mlog(1/ε)⋅minn,m3log(Klogn).O (nm (K n))+m (1/ )· \n,m^3 (K n\ ). Substituting E(σ)=KE(σ)=K and setting μ=log(Klogn)=log(E(σ)logn)=logE(σ)+loglognμ= (K n)= (E(σ) n)= E(σ)+ n, we get (nmμ+minn,m3μ⋅mlog(1/ε)),O (nmμ+ \n,m^3μ\· m (1/ ) ), as desired. E.3 Lower Bound with Permutation Predictions Proposition E.1. Fix any n,mn,m. Then, any (deterministic or randomized) algorithm) that is correct for every instance ℐI and permutation prediction σ σ (i.e., outputs a unanimously acceptable lottery whenever one exists and Null otherwise) has a worst-case (expected) number of queries is Ω((n−minn,m)+(minn,m−1)log(1/ε)) ((n- \n,m\)+( \n,m\-1) (1/ )). Proof. Fix n,mn,m. Let A be any deterministic (or randomized) algorithm that is correct for every pair (ℐ,σ^)(I, σ) where ℐI is an instance of the problem and σ σ is an arbitrary permutation of N (i.e., A outputs a unanimously acceptable lottery whenever one exists and outputs Null otherwise). We will prove our result by showing, for each case n≥mn≥ m and n<mn<m, a hard family of feasible instances together with a fixed permutation advice σ σ whose prefix witness parameter is small. Since A must be correct for every permutation advice, lower bounding its query complexity under this specific σ σ is without loss of generality. We first show the following lemma. Lemma E.2. Fix any permutation advice σ σ. Let T be any correct deterministic decision tree for the problem under advice σ σ (i.e., T outputs a unanimously acceptable lottery on every feasible instance and outputs Null on every infeasible instance, when run with input (ℐ,σ^)(I, σ)). Then on every feasible instance ℐI, along the root-to-leaf path followed by T on input (ℐ,σ^)(I, σ), every agent i∈Ni∈ N is queried at least once. In particular, T makes at least n membership queries on ℐI. Proof. Let P be the root-to-leaf path followed by T on input (ℐ,σ^)(I, σ). Because ℐI is feasible and T is correct, the reached leaf is labeled by some lottery ∗∈Δ(S)x^*∈ (S) (not Null). Suppose for contradiction that some agent j∈Nj∈ N is never queried along P. Construct a new instance ℐ′I by changing only agent j as follows: set uj′(s)=0u _j(s)=0 for all s∈Ss∈ S and set τj′=ετ _j= . Then Uj′()=0<τj′U _j(x)=0<τ _j for every lottery ∈Δ(S)x∈ (S), so agent j rejects every query and ℐ′I is infeasible. However, since j is never queried along P, every query asked along P receives the same answer on (ℐ′,σ^)(I , σ) as on (ℐ,σ^)(I, σ), and so T follows the same path P and outputs the same non-Null lottery ∗x^*. This contradicts correctness on (ℐ′,σ^)(I , σ), which would require output Null. ∎ We split our analysis into two cases. Case 1: n≥mn≥ m. Let Δ+(S) ^+(S) denote the positive ε -grid on the simplex, i.e., Δ+(S):=∈Δ(S):xj∈ε,2ε,…,1 for all j∈[m]. ^+(S):=\x∈ (S):x_j∈\ ,2 ,…,1\ for all j∈[m]\. Note that under ε -precision and m≤(1/ε)1−δ≤1/εm≤(1/ )^1-δ≤ 1/ , this set is nonempty. For each =(x1,…,xm)∈Δ+(S)x=(x_1,…,x_m)∈ ^+(S) define an instance ℐI_x with n agents as follows: • For each i∈[m]i∈[m], set ui(si)=1u_i(s_i)=1, ui(sj)=0u_i(s_j)=0 for all j≠ij≠ i, and set τi=xi _i=x_i. • For each dummy agent i∈m+1,…,ni∈\m+1,…,n\, set ui(sj)=1u_i(s_j)=1 for all j∈[m]j∈[m] and τi=1 _i=1 (so i accepts every lottery). Fix the permutation advice σ σ so that agents 1,…,m1,…,m occupy the first m positions (e.g. σ^(k)=k σ(k)=k for all k∈[n]k∈[n]). Since all nontrivial constraints are contained in agents 1,…,m1,…,m, there exists a witness set contained in the first m positions; thus E(σ^)≤mE( σ)≤ m. Moreover, since each dummy agent has i=Δ(S)A_i= (S), no minimal witness set (basis) can include a dummy agent, so some valid witness set lies entirely in 1,…,m\1,…,m\. We claim that the unanimously acceptable set of ℐI_x is the singleton \x\. Indeed, for any lottery ∈Δ(S)y∈ (S) and any i∈[m]i∈[m], we have Ui()=yiU_i(y)=y_i. Thus agent i accepts y if and only if yi≥τi=xiy_i≥ _i=x_i. If y is unanimously acceptable, then yi≥xiy_i≥ x_i for all i∈[m]i∈[m]. Let di:=yi−xi≥0d_i:=y_i-x_i≥ 0. Because ,∈Δ(S)x,y∈ (S), we have ∑i=1mdi=∑i=1myi−∑i=1mxi=1−1=0 _i=1^md_i= _i=1^my_i- _i=1^mx_i=1-1=0, forcing di=0d_i=0 for all i, i.e., =y=x. Now, fix any correct deterministic decision tree T and consider its behavior on the family ℱ:=ℐ:∈Δ+(S)F:=\I_x:x∈ ^+(S)\ with the advice fixed to σ σ. By Lemma E.2, on each feasible instance ℐI_x the execution path queries every agent at least once. In particular, it makes at least n−mn-m queries to dummy agents. Over the family ℱF, every dummy-agent query is answered True. Prune T into a tree T′T by contracting every internal node that queries a dummy agent to its True child. Then for every ∈Δ+(S)x∈ ^+(S), QT(ℐ,σ^)≥(n−m)+QT′(ℐ,σ^).Q_T(I_x, σ)≥(n-m)+Q_T (I_x, σ). By uniqueness, the correct output on ℐI_x is exactly x. Therefore distinct ≠′x must reach distinct leaves of T′T (a leaf has a fixed output label), so T′T has at least |Δ+(S)|| ^+(S)| leaves. Hence supQT′(ℐ,σ^)≥log|Δ+(S)| _xQ_T (I_x, σ)≥ | ^+(S)|, and thus for some x, QT(ℐ,σ^)≥(n−m)+log|Δ+(S)|.Q_T(I_x, σ)≥(n-m)+ | ^+(S)|. Let xi=kiεx_i=k_i with integers ki≥1k_i≥ 1. The simplex constraint ∑i=1mxi=1 _i=1^mx_i=1 becomes ∑i=1mki=1/ε _i=1^mk_i=1/ . Thus, |Δ+(S)|| ^+(S)| is the number of positive integer solutions to this equation, namely |Δ+(S)|=(1/ε−1m−1).| ^+(S)|= 1/ -1m-1. Using (ab)≥(a/b)b ab≥(a/b)^b for a≥b≥1a≥ b≥ 1 with a=1/ε−1a=1/ -1 and b=m−1b=m-1 gives us log|Δ+(S)|≥(m−1)log(1/ε−1m−1)≥(m−1)log(1εm). | ^+(S)|≥(m-1) ( 1/ -1m-1 )≥(m-1) ( 1 m ). By the standing growth condition m≤(1/ε)1−δm≤(1/ )^1-δ, we have 1/(εm)≥(1/ε)δ1/( m)≥(1/ )^δ and hence log|Δ+(S)|=Ω((m−1)log(1/ε)). | ^+(S)|= ((m-1) (1/ )). Combining, for n≥mn≥ m we obtain sup∈Δ+(S)QT(ℐ,σ^)≥Ω((n−m)+(m−1)log(1/ε)). _x∈ ^+(S)Q_T(I_x, σ)≥ ((n-m)+(m-1) (1/ )). Case 2: n<mn<m. Define the positive ε -grid supported on the first n alternatives: Δn+(S):=x∈Δ(S):xi∈ε,2ε,…,1 for all i≤n,xn+1=⋯=xm=0. ^+_n(S):=\x∈ (S):x_i∈\ ,2 ,…,1\ for all i≤ n,x_n+1=·s=x_m=0\. For each ∈Δn+(S)x∈ ^+_n(S) define an instance ℐI_x with n agents: for each i∈[n]i∈[n], set ui(si)=1u_i(s_i)=1, ui(sj)=0u_i(s_j)=0 for j≠ij≠ i, and τi=xi _i=x_i. Fix any permutation advice σ σ (e.g. identity); trivially E(σ^)≤nE( σ)≤ n. The same coordinate-wise argument shows that ℐI_x has a unique unanimously acceptable lottery x. Thus, any correct deterministic decision tree under advice σ σ must have at least |Δn+(S)|| ^+_n(S)| leaves over this family, so some instance forces at least log|Δn+(S)| | ^+_n(S)| queries. Counting as above gives us |Δn+(S)|=(1/ε−1n−1)| ^+_n(S)|= 1/ -1n-1, so log|Δn+(S)|=Ω((n−1)log(1/ε)) | ^+_n(S)|= ((n-1) (1/ )), using again that n<m≤(1/ε)1−δn<m≤(1/ )^1-δ. Combining the two cases gives us the deterministic lower bound supℐQT(ℐ,σ^)≥Ω((n−minn,m)+(minn,m−1)log(1/ε)). _IQ_T(I, σ)≥ ((n- \n,m\)+( \n,m\-1) (1/ )). We interpret a randomized algorithm as a distribution over correct deterministic decision trees. For a (random seed-indexed) deterministic tree TωT_ω, define Q(ℐ,σ^):=ω[QTω(ℐ,σ^)]Q_A(I, σ):=E_ω[Q_T_ω(I, σ)]. We use two standard facts. Lemma E.3 (Yao’s minimax principle). For any distribution μ over instances, infsupℐQ(ℐ,σ^)≥minTℐ∼μ[QT(ℐ,σ^)], _A _IQ_A(I, σ)≥ _T\ E_I μ [Q_T(I, σ) ], where the infimum ranges over correct randomized algorithms A and the minimum ranges over correct deterministic trees T. Proof. Fix μ and a randomized algorithm A (a distribution over deterministic trees). Then supℐQ(ℐ,σ^)≥ℐ∼μ[Q(ℐ,σ^)]=ℐ∼μT∼[QT(ℐ,σ^)]=T∼ℐ∼μ[QT(ℐ,σ^)]≥minTℐ∼μ[QT(ℐ,σ^)]. _IQ_A(I, σ) _I μ [Q_A(I, σ) ]=E_I μE_T [Q_T(I, σ) ]=E_T E_I μ [Q_T(I, σ) ]≥ _TE_I μ [Q_T(I, σ) ]. Taking inf _A on the left-hand side proves the claim. ∎ Lemma E.4 (Average depth bound). Let T be a binary decision tree and let L be any finite set of leaves of T. If ℓ is drawn uniformly from L, then [depth(ℓ)]≥log|L|E[depth( )]≥ |L|. Proof. By Kraft’s inequality, ∑ℓ∈L2−depth(ℓ)≤1 _ ∈ L2^-depth( )≤ 1. Let D:=depth(ℓ)D:=depth( ) where ℓ∼Unif(L) (L). Then [2−D]=1|L|∑ℓ∈L2−depth(ℓ)≤1|L|.E[2^-D]= 1|L| _ ∈ L2^-depth( )≤ 1|L|. Since 2−x2^-x is convex, Jensen’s inequality gives 2−[D]≤[2−D]≤1/|L|2^-E[D] [2^-D]≤ 1/|L|, hence [D]≥log|L|E[D]≥ |L|. ∎ Now choose μ to be uniform over the corresponding hard family: ℐ:x∈Δ+(S)\I_x:x∈ ^+(S)\ when n≥mn≥ m, and ℐ:x∈Δn+(S)\I_x:x∈ ^+_n(S)\ when n<mn<m. Fix any correct deterministic tree T. In each case, the correct output is unique for every instance in the support of μ. Therefore distinct instances in the support must reach distinct output leaves of the (possibly pruned) tree, so the set L of leaves reached under μ has size |L|=|Δ||L|=| |. Because μ is uniform on instances, the induced distribution on L is uniform. By Lemma E.4, ℐ∼μ[QT(ℐ,σ^)]≥log|L|=log|Δ|,E_I μ[Q_T(I, σ)]≥ |L|= | |, and in the n≥mn≥ m case the pruning argument contributes the additive (n−m)(n-m) term exactly as above. Thus the same asymptotic lower bound holds for minTℐ∼μ[QT(ℐ,σ^)] _TE_I μ[Q_T(I, σ)], and Lemma E.3 implies the same lower bound for infsupℐQ(ℐ,σ^) _A _IQ_A(I, σ). Equivalently, every correct randomized algorithm has worst-case expected query complexity Ω((n−minn,m)+(minn,m−1)log(1/ε)), ((n- \n,m\)+( \n,m\-1) (1/ ) ), even under an permutation advice σ σ with E(σ^)≤minn,mE( σ)≤ \n,m\. ∎ E.4 Proof of Theorem 5.3 We first define the warm-started threshold routine used by LearnHyperplane[^]LearnHyperplane[ x]. Algorithm 4 ExactThresholdPred(i,k,k′,α^)ExactThresholdPred(i,k,k , α) Input: agent i∈Ni∈ N, indices k,k′∈[m]k,k ∈[m] with Query(i,ek)=FalseQuery(i,e_k)= False, Query(i,ek′)=TrueQuery(i,e_k )= True, and a warm start α^∈[0,1] α∈[0,1]. Output: the exact turning point αi;k,k′∗∈(0,1]α^*_i;k,k ∈(0,1] with Query(i,xk,k′,α)=TrueQuery(i,x_k,k ,α)= True iff α≥αi;k,k′∗α≥α^*_i;k,k . 1:←ε2/2step← ^2/2. 2:b←Query(i,xk,k′,α^)b (i,x_k,k , α). 3:if b=Trueb= True then ⊳ α^≥αi;k,k′∗ α≥α^*_i;k,k 4: ←α^upper← α. 5: while −>0upper-step>0 and Query(i,xk,k′,−)=TrueQuery(i,x_k,k ,upper-step)= True do 6: ←−upper -step; ←2×step← 2×step. 7: end while 8: ←max0,−lower← \0,upper-step\. 9:else⊳ α^<αi;k,k′∗ α<α^*_i;k,k 10: ←α^lower← α. 11: while +<1lower+step<1 and Query(i,xk,k′,+)=FalseQuery(i,x_k,k ,lower+step)= False do 12: ←+lower +step; ←2×step← 2×step. 13: end while 14: ←min1,+upper← \1,lower+step\. 15:end if 16:Perform bisection on [,][lower,upper] until −<ε2/2upper-lower< ^2/2, maintaining Query(i,k,k′,)=FalseQuery(i,x_k,k ,lower)= False and Query(i,k,k′,)=TrueQuery(i,x_k,k ,upper)= True. 17:Apply the same rational reconstruction step as ExactThresholdExactThreshold (Appendix C.1) to recover αi;k,k′∗α^*_i;k,k uniquely from [,][lower,upper], and return it. Then, we prove the following lemma. Lemma E.5. Fix i,k,k′i,k,k as in Algorithm 4, and let α∗:=αi;k,k′∗α^*:=α^*_i;k,k . For any warm start α^∈[0,1] α∈[0,1], ExactThresholdPredExactThresholdPred returns α∗α^* exactly. Moreover, it has a query complexity of (1+log(1+|α^−α∗|ε2)).O (1+ (1+ | α-α^*| ^2 ) ). Proof. Correctness follows from monotonicity of Query(i,k,k′,α)Query(i,x_k,k ,α) on α and the same denominator/uniqueness argument used for ExactThresholdExactThreshold in Appendix C.1: α∗α^* is a rational with reduced denominator at most 1/ε1/ , so any bracket of width <ε2/2< ^2/2 contains at most one such rational, and rational reconstruction returns α∗α^* uniquely. It remains to show that the algorithm maintains a valid bracket and to bound its length and query complexity. Let d:=|α^−α∗|d:=| α-α^*|. If b=Trueb= True, then α^≥α∗ α≥α^* and the algorithm decreases upper in steps of size step that double geometrically until either (i) the next candidate point falls below 0 or (i) the query at −upper-step flips to False. In either case, by construction Query(i,k,k′,)=TrueQuery(i,x_k,k ,upper)= True and Query(i,k,k′,)=FalseQuery(i,x_k,k ,lower)= False, and monotonicity implies α∗∈(,]α^*∈(lower,upper]. The case b=Falseb= False is symmetric (searching to the right), giving us a bracket Query(i,k,k′,)=FalseQuery(i,x_k,k ,lower)= False, Query(i,k,k′,)=TrueQuery(i,x_k,k ,upper)= True, and α∗∈(,]α^*∈(lower,upper]. Next, we derive the bracket width after the exponential phase. Consider the case b=Trueb= True (the other case is identical). Let 0:=ε2/2step_0:= ^2/2 be the initial step size and suppose the while loop performs t≥0t≥ 0 successful iterations (i.e., the queried point remains accepting). Then the step size at the end of the exponential phase is t=2t×0step_t=2^t×step_0, and α^−=0(1+2+⋯+2t−1)=(2t−1)×0. α-upper=step_0(1+2+·s+2^t-1)=(2^t-1)×step_0. Since upper remains accepting throughout, we have ≥α∗upper≥α^*, and thus d=α^−α∗≥α^−=(2t−1)×0d= α-α^*≥ α-upper=(2^t-1)×step_0. Rearranging gives 2t×0≤d+02^t×step_0≤ d+step_0, i.e., t≤d+ε2/2.step_t≤ d+ ^2/2. At termination of the exponential phase, the algorithm sets =max0,−tlower= \0,upper-step_t\, so the resulting bracket has width at most tstep_t (and at most upper if clipped at 0). Thus, the bracket width after the exponential phase is at most d+ε2/2d+ ^2/2. Now, we prove the query complexity. The exponential phase uses one query to evaluate b plus one query per loop test, and the loop doubles step each successful iteration until step reaches the scale of d (or until clipped at an endpoint). Thus the number of queries in the exponential phase is (1+log(1+dε2)).O (1+ (1+ d ^2 ) ). After this phase, the bracket width is at most d+ε2/2d+ ^2/2. The bisection phase reduces the width to <ε2/2< ^2/2, requiring (log(d+ε2/2ε2/2))=(log(1+dε2))O ( ( d+ ^2/2 ^2/2 ) )=O ( (1+ d ^2 ) ) additional membership queries. Rational reconstruction uses no membership queries. Summing the phases proves the lemma. ∎ Now, fix an agent i∈Ni∈ N and a prediction ^∈Δ(S) x∈ (S). Note that LearnHyperplane[^](i)LearnHyperplane[ x](i) is identical to LearnHyperplane(i)LearnHyperplane(i) except that every invocation of ExactThreshold(i,k,k′)ExactThreshold(i,k,k ) is replaced by ExactThresholdPred(i,k,k′,α^k,k′(^))ExactThresholdPred(i,k,k , α_k,k ( x)), where α^k,k′(^) α_k,k ( x) is the pairwise projection coordinate defined in Section 5.2. All other steps (including the construction of ic_i from the recovered turning points) are unchanged. We first show correctness. LearnHyperplane(i)LearnHyperplane(i)’s correctness (Lemma 3.2) relies only on the fact that each threshold routine returns the exact turning point αi;k,k′∗α^*_i;k,k on the queried edge. By Lemma E.5, ExactThresholdPredExactThresholdPred returns the same turning point as ExactThresholdExactThreshold for every queried edge. Therefore LearnHyperplane[^](i)LearnHyperplane[ x](i), computes the same values αi;k,k′∗α^*_i;k,k and returns exactly the same output (AcceptAll, RejectAll, or an equivalent halfspace vector ic_i) as LearnHyperplane(i)LearnHyperplane(i). Next, we prove the query complexity. Moreover, as in LearnHyperplaneLearnHyperplane, LearnHyperplane[^]LearnHyperplane[ x] first queries all m pure lotteries 1,…,me_1,…,e_m once. If it returns AcceptAll or RejectAll at this stage, the query complexity is exactly m. Otherwise, it invokes the threshold routine on at most |ℰi|≤m−1|E_i|≤ m-1 simplex edges. For each (k,k′)∈ℰi(k,k ) _i, the warm start used is α^k,k′(^) α_k,k ( x), so the distance to the true turning point is precisely δi;k,k′(^) _i;k,k ( x). Lemma E.5 therefore implies that the number of queries used on edge (k,k′)(k,k ) is (1+log(1+δi;k,k′(^)/ε2))O (1+ (1+ _i;k,k ( x)/ ^2 ) ). Summing over (k,k′)∈ℰi(k,k ) _i and adding the m pure-lottery queries gives us (m+∑(k,k′)∈ℰilog(1+δi;k,k′(^)ε2)).O (m+ _(k,k ) _i (1+ _i;k,k ( x) ^2 ) ). Finally, since |ℰi|≤m−1|E_i|≤ m-1 and δi;k,k′(^)≤δimax(^) _i;k,k ( x)≤ _i ( x) for every (k,k′)∈ℰi(k,k ) _i, we obtain the simplified bound (m+mlog(1+δimax(^)ε2)),O (m+m (1+ _i ( x) ^2 ) ), completing the proof. E.5 Lottery Predictions: Why violator count (of the lottery prediction) is not a useful error model A tempting way to quantify the quality of a predicted lottery ^∈Δ(S) x∈ (S) is by its violator count |V(^)|whereV(^):=i∈N:Query(i,^)=False.|V( x)| V( x):=\i∈ N:Query(i, x)= False\. While this quantity is relevant for the trivial “verify and stop” use of the lottery advice, it is generally a weak error model for learning-augmented elicitation because it evaluates advice at a single point and discards the geometric information that determines how many queries are required to learn constraints. In particular, |V(^)||V( x)| does not distinguish between (i) a prediction that lies deep inside many agents’ acceptable regions and (i) a prediction that is accepted by many agents but sits arbitrarily close to their acceptance boundaries. In case (i), even if |V(^)||V( x)| is small, a subsequent candidate lottery produced by an elicitation algorithm (e.g., Algorithm 2 or Algorithm 3) after learning a new constraint and recomputing ←Select(C)x (C)) can move by a small amount that flips many previously accepting agents into rejecting. As a result, the total number of encountered violators (and hence the number of costly hyperplane learning steps) can still be large despite a small violator count at x. In contrast, the dominant cost inside LearnHyperplaneLearnHyperplane is a collection of one-dimensional searches along simplex edges k,k′,αx_k,k ,α, whose difficulty is governed by the corresponding turning points αi;k,k′∗α^*_i;k,k . Therefore, the algorithmically relevant prediction quality is inherently local to the edge: the only useful information that a full lottery x provides for queries restricted to the edge (the convex hull of ke_k and k′e_k : convk,k′conv\e_k,e_k \) is its pairwise projection coordinate α^k,k′(^) α_k,k ( x), and the right notion of prediction error is the turning point projection error δi;k,k′(^):=|α^k,k′(^)−αi;k,k′∗|. _i;k,k ( x):= | α_k,k ( x)-α^*_i;k,k |. This quantity directly controls how quickly a warm-started threshold search can bracket αi;k,k′∗α^*_i;k,k before the final bisection/reconstruction phase, giving us the smooth bounds in Theorem 5.3. E.6 Proof of Proposition 5.4 Let Q:=1/ε∈ℤ>0Q:=1/ _>0. If Q<4Q<4, then δ/ε2≤1/ε2=Q2≤9δ/ ^2≤ 1/ ^2=Q^2≤ 9, so log(1+δ/ε2)=(1) (1+δ/ ^2)=O(1). On the other hand, on any feasible instance every correct algorithm must query each agent at least once (the proof of Lemma D.1 applies with the advice x held fixed), so it makes at least n=2n=2 queries. Thus the claimed Ω(log(1+δ/ε2)) ( (1+δ/ ^2)) lower bound holds after adjusting constants. Henceforth, we assume Q≥4Q≥ 4. Define M:=min⌊Q/2⌋,⌊δQ2⌋+1M:= \ Q/2 , δ Q^2 +1\. Since δ≥ε2δ≥ ^2, we have δQ2≥1δ Q^2≥ 1, hence ⌊δQ2⌋+1≥2 δ Q^2 +1≥ 2; also ⌊Q/2⌋≥2 Q/2 ≥ 2 because Q≥4Q≥ 4. Therefore M≥2M≥ 2. For each t∈0,1,…,M−1t∈\0,1,…,M-1\, set qt:=Q−tandαt:=1qt∈(0,1).q_t:=Q-t _t\;:=\; 1q_t∈(0,1). Note 1≤qt≤Q1≤ q_t≤ Q, so qtε∈0,ε,2ε,…,1q_t ∈\0, ,2 ,…,1\ and αt _t is a rational with reduced denominator qt≤Qq_t≤ Q. Define the prediction coordinate as the midpoint α^:=12(α0+αM−1)and^:=1,2,α^∈Δ(S). α:= 12 ( _0+ _M-1 ) x:=x_1,2, α∈ (S). We claim that for every t∈0,…,M−1t∈\0,…,M-1\, |αt−α^|≤δ.| _t- α|≤δ. (10) Indeed, αt _t is increasing in t, so |αt−α^|≤αM−1−α02=12(1Q−(M−1)−1Q)=M−12Q(Q−(M−1)).| _t- α|≤ _M-1- _02= 12 ( 1Q-(M-1)- 1Q )= M-12Q(Q-(M-1)). Because M≤⌊Q/2⌋M≤ Q/2 , we have Q−(M−1)≥Q/2Q-(M-1)≥ Q/2, thus |αt−α^|≤M−1Q2.| _t- α|≤ M-1Q^2. Finally, since M−1≤⌊δQ2⌋≤δQ2M-1≤ δ Q^2 ≤δ Q^2 (because M−1=min⌊Q/2⌋−1,⌊δQ2⌋M-1= \ Q/2 -1, δ Q^2 \), we obtain |αt−α^|≤δ| _t- α|≤δ, proving (10). For each t∈0,…,M−1t∈\0,…,M-1\, define an instance ℐtI_t with n=2n=2 agents and m=2m=2 alternatives S=s1,s2S=\s_1,s_2\ as follows: • Agent 22 has u2(s1)=0u_2(s_1)=0, u2(s2)=qtεu_2(s_2)=q_t , and τ2=ε _2= . • Agent 11 has u1(s1)=qtεu_1(s_1)=q_t , u1(s2)=0u_1(s_2)=0, and τ1=(qt−1)ε _1=(q_t-1) . All utilities and thresholds are integer multiples of ε in [0,1][0,1], and τ1>0 _1>0 since qt≥Q−(M−1)≥Q/2≥2q_t≥ Q-(M-1)≥ Q/2≥ 2. For any α∈[0,1]α∈[0,1], write 1,2,α=(1−α)1+α2x_1,2,α=(1-α)e_1+ _2. Then U2(1,2,α)=α⋅qtε,soU2(1,2,α)≥τ2⇔α≥1qt=αt,U_2(x_1,2,α)=α· q_t , U_2(x_1,2,α)≥ _2 α≥ 1q_t= _t, and U1(1,2,α)=(1−α)⋅qtε,soU1(1,2,α)≥τ1⇔α≤1qt=αt.U_1(x_1,2,α)=(1-α)· q_t , U_1(x_1,2,α)≥ _1 α≤ 1q_t= _t. Thus, the unanimously acceptable set in ℐtI_t is exactly the singleton 1,2,αt\x_1,2, _t\; denote this unique feasible lottery by t∗x_t^*. Moreover, in each ℐtI_t we have Query(2,1)=FalseQuery(2,e_1)= False and Query(2,2)=TrueQuery(2,e_2)= True, so the turning point for agent 22 on the edge (1,2)(e_1,e_2) is α2;1,2∗=αtα^*_2;1,2= _t (by the definition in Section 5.2). Since m=2m=2, the pairwise projection coordinate satisfies αb1,2(^)=x^2=α _b1,2( x)= x_2= α, and thus, δ2;1,2(^)=|αb1,2(^)−α2;1,2∗|=|α^−αt|≤δ, _2;1,2( x)=| _b1,2( x)-α^*_2;1,2|=| α- _t|≤δ, where α2;1,2∗=αtα^*_2;1,2= _t in instance ℐtI_t. Now, fix any correct deterministic decision tree T, and let QT(ℐ)Q_T(I) be the number of queries made by T on instance ℐI (with the fixed advice x). Each ℐtI_t is feasible and has the unique correct output t∗=1,2,αtx_t^*=x_1,2, _t, and these outputs are distinct over t. Therefore the instances ℐ0,…,ℐM−1I_0,…,I_M-1 reach M distinct leaves of T. Let μ be the uniform distribution over ℐ0,…,ℐM−1\I_0,…,I_M-1\; since the mapping ℐt↦I_t reached leaf is injective, the induced distribution over these M leaves is uniform. By the average-depth bound (Lemma D.4), I∼μ[QT(ℐ)]≥logM.E_I μ [Q_T(I) ]\;≥\; M. (11) In particular, maxtQT(ℐt)≥logM _tQ_T(I_t)≥ M. Now consider randomized algorithms. Apply Lemma D.3 to the distribution μ above. Since (11) shows that ℐ∼μ[QT(ℐ)]≥logME_I μ[Q_T(I)]≥ M for every correct deterministic decision tree T, Lemma D.3 gives us infsupℐQ(ℐ)≥logM, _A _IQ_A(I)≥ M, where the infimum ranges over correct randomized algorithms. In particular, every correct randomized algorithm A satisfies supℐQ(ℐ)≥logM _IQ_A(I)≥ M. Let λ:=δQ2=δ/ε2≥1λ:=δ Q^2=δ/ ^2≥ 1. Recall M=min⌊Q/2⌋,⌊λ⌋+1M= \ Q/2 ,\ λ +1\. If M=⌊λ⌋+1M= λ +1, then M≥2M≥ 2 and M≥λM≥λ, so M≥max2,λM≥ \2,λ\. For λ∈[1,2)λ∈[1,2) we have logM≥log2≥(log2/log3)log(1+λ) M≥ 2≥( 2/ 3)\, (1+λ), while for λ≥2λ≥ 2, logM≥logλ≥12log(1+λ), M≥ λ≥ 12 (1+λ), since log(1+λ)≤log(2λ)=log2+logλ≤2logλ (1+λ)≤ (2λ)= 2+ λ≤ 2 λ. Thus in this case logM=Ω(log(1+λ)) M= ( (1+λ)). If M=⌊Q/2⌋M= Q/2 , then M≥Q/4M≥ Q/4 (since Q≥4Q≥ 4), so logM=Ω(logQ) M= ( Q). Moreover λ≤Q2λ≤ Q^2 (as δ≤1δ≤ 1) implies log(1+λ)≤log(1+Q2)=O(logQ) (1+λ)≤ (1+Q^2)=O( Q), and hence again logM=Ω(log(1+λ)) M= ( (1+λ)). Therefore logM=Ω(log(1+λ))=Ω(log(1+δ/ε2)) M= ( (1+λ))= ( (1+δ/ ^2)).