Introduction
Training a language model to refuse harmful requests also makes it refuse some harmless ones [14 , 66 ] , and the parties affected by a deployment weigh these two errors differently. Consider a chatbot with a strict version, which gives a harmful reply to 0.2% of risky prompts but refuses 12% of harmless requests, and a lenient version, with rates of 1% and 2%. The developer need not commit to one version: it can route each conversation to a randomly chosen version, which is routine in A/B testing and staged releases [51 ] . If two thirds of conversations go to the strict version, linearity of expectation gives rates of about 0.47% and 8.7%. This mixture meets both a safety team’s limit of 0.5% on harmful replies and a hospital’s limit of 9% on refusals, although neither version meets both limits on its own. Suppose that a regulator also caps harmful replies at 0.3%. Then at least 87.5% of conversations must go to the strict version, whereas the hospital accepts at most 70%; no mixture meets all three requirements, and the developer has to choose whose requirement goes unmet.
We model such decisions with a standard framework from probabilistic social choice and random assignment [25 , 49 ] . A decision maker chooses a lottery over a finite set of alternatives (here, model versions), and each agent (here, a stakeholder) accepts it and only if the expected score of the lottery is at least the agent’s threshold; the lotteries that an agent accepts therefore form a halfspace of the probability simplex. For requirements on average rates—of harmful replies, of refusals, or of errors on a customer’s own test set—this linear model is exact, because a mixture’s rate equals the sum, over versions, of the routing probability times that version’s rate. The same model also describes applications ranging from content moderation [44 , 45 ] to school or housing allocation [1 , 27 ] to the division of a budget among public projects [69 ] .
The decision maker, however, knows neither the scores nor the thresholds. A customer will not reveal its private test data, and a regulator’s standard may be available only as legal text [38 ] . What a stakeholder can do is look at a concrete proposal and answer yes or no; following Angluin [1988], we call such a question (“is this lottery acceptable to you?”) a membership query . Answering it demands far less of a stakeholder than reporting full utilities [24 , 26 ] , yet a single answer can cost an evaluation run or a human review, so a decision maker facing thousands of stakeholders can consult only some of them.
This query model was introduced by Choo et al. [ [33 ] , who sought unanimity : a lottery that every agent accepts, or a report that there is none. Unanimity fits settings in which every requirement is mandatory, but it offers little guidance when requirements conflict. As the example shows, a single demanding agent can rule out every lottery, and learning that no lottery is unanimously acceptable does not tell the developer what to deploy (keeping the old version is one of the alternatives, not a way out of the choice). This paper addresses the following question: when the requirements cannot all be met, how can a decision maker who asks few membership queries find a lottery that as few agents as possible reject? We call the problem of minimizing the number of rejecting agents MIN-VIOL.
One could instead measure how severely each agent is violated, as Teh and Goldberg [ [70 ] do in the same query model by minimizing a power mean of the distances from the lottery to the violated agents’ acceptance boundaries (Appendix § 10 compares the two objectives). We count rejecting agents because, for safety, a small aggregate violation can hide many agents who each fall just below their thresholds. This choice has a computational cost. Unanimity is a linear feasibility problem, whereas MIN-VIOL asks for a point of the simplex satisfying as many linear inequalities as possible, which is hard in general (§ 1.2 ).
Our Results
Our main results concern what can be promised to the stakeholders who are not asked.
Even with full information, the problem is hard. MIN-VIOL is APX-hard even when all utilities are 0 or 1 (Theorem 3.1 ), so it has no polynomial-time approximation scheme unless P = NP; this strengthens the NP-hardness shown by Choo et al. [ [33 ] . In other words, even a developer who knows every requirement cannot, in general, get arbitrarily close to the best lottery efficiently.
Exact algorithms under additional structure. When the number m m m of alternatives is constant (say, a handful of model versions), MIN-VIOL can be solved exactly in polynomial time (Theorem 4.1 ), by an algorithm that is XP rather than FPT in m m m . For larger m m m , if some optimal lottery leaves no accepting agent within a margin η \eta η of its threshold, then some optimal lottery uses only O ( log n / η 2 ) O(\log n/\eta^2) O ( log n / η 2 ) alternatives (Theorem 4.2 , via a sampling argument of Castiglioni et al. [ [30 ] ), and searching over such lotteries finds one in quasi-polynomial time for constant η \eta η (Corollary 4.4). Finally, when few violations are allowed, Helly’s theorem gives an algorithm that is FPT in the numbers of alternatives and violations together, whereas the number of violations alone gives W[2]-hardness (§ 4.3 ).
Learning from a random sample of agents. If k ≥ m k \ge m k ≥ m agents are sampled uniformly at random and their halfspaces are recovered, then, with probability at least 1 − δ 1-\delta 1 − δ , any lottery that minimizes the number of rejecting sampled agents has at most O P T + O ( n m log ( e k / m ) + log ( 1 / δ ) k ) \mathrm{OPT} + O\left(n\sqrt{\frac{m\log(ek/m)+\log(1/\delta)}{k}}\right) OPT + O ( n k m l o g ( e k / m ) + l o g ( 1/ δ ) ) violations, where OPT is the minimum number of violations (Theorem 5.1 ). Put another way, for an error that is a given fraction of n n n , the number of agents to ask does not depend on n n n : a developer with a million customers need not ask more of them than one with a thousand. If O P T ≥ ρ n \mathrm{OPT} \ge\rho n OPT ≥ ρ n , then O ( ( m log ( 1 / ρ ) + log ( 1 / δ ) ) / ( ζ 2 ρ ) ) O((m\log(1/\rho)+\log(1/\delta))/(\zeta^2\rho)) O (( m log ( 1/ ρ ) + log ( 1/ δ )) / ( ζ 2 ρ )) samples give a ( 1 + ζ ) (1+\zeta) ( 1 + ζ ) -approximation (Theorem 5.2 ).
A polynomial-time linear program for any number of alternatives. For large m m m , we solve a linear program that penalizes agents who reject the lottery or accept it with margin less than η \eta η . With high probability, for every lottery x \mathbf{x} x , its output has at most ( 1 + 1 / η ) (1+1/\eta) ( 1 + 1/ η ) times as many violations as x \mathbf{x} x , plus the number of agents who accept x x x with margin less than η \eta η , plus O ( n η log m + log ( 1 / δ ) k ) O\left(\frac{n}{\eta}\sqrt{\frac{\log m+\log(1/\delta)}{k}}\right) O ( η n k l o g m + l o g ( 1/ δ ) ) (Theorem 5.3). The guarantee is strong when few agents are barely satisfied.
Without random sampling, unasked agents get no guarantee. Can clever, adaptive questioning of a fixed set of agents replace random sampling? For m ≥ 3 m \ge3 m ≥ 3 , it cannot: every deterministic algorithm that queries only K K K distinct agents may leave n − K n-K n − K more agents unsatisfied than the optimum, however many queries it spends on them (Theorem 6.1), and optimizing over a fixed set of K K K queried agents matches this bound (Theorem 6.2). In other words, a deterministic decision maker can promise nothing to the agents it does not ask. For AI deployment, this means that a developer who always consults the same internal teams or large customers has, in the worst case, no guarantee for anyone else; choosing at random whom to ask is what makes the sampling guarantees possible.
Synthetic experiments. On random instances, our bounds are conservative: with 500 agents, the lottery learned from a random sample of 120 had, on average, fewer than 10 more rejecting agents than the optimum, and the n − K n-K n − K worst case arose only for our lower-bound construction (Section 7).
Related Work
We discuss the closest work here; Appendix § 10 covers further areas (see Table 2 ).
Table 2. Comparison with the closest work. “Explicit” means that all constraints are given as input.
Learning lotteries from membership queries. Choo et al. [ [33 ] bounded the number of membership queries needed to find a lottery that every agent accepts, or to conclude that there is none, and showed that maximizing the number of accepting agents is NP-hard even with binary utilities [33 Theorem B.3 of the extended version] . We use their routine for recovering one agent’s halfspace as a black box, but our objective is different.
Maximum feasible subsystem. With full information, MIN-VIOL asks for a point of the simplex satisfying as many of the agents’ linear inequalities as possible. It is therefore a restricted case of the maximum feasible subsystem (MAX-FS) problem, or of its complement, the minimum unsatisfied linear relation (MIN-ULR) problem. For general systems of linear inequalities without mandatory constraints, MAX-FS can be approximated within a factor 2 but has no PTAS unless P = NP [6 ] , while MIN-ULR is much harder: it cannot be approximated within 2 log 1 − c n 2^{\log^{1-c} n} 2 l o g 1 − c n for any constant c > 0 c > 0 c > 0 unless NP ⊆ \subseteq ⊆ QP [12 , 7 ] ; see also Amaldi et al. [ [8 ] and, for 0/1 coefficients, Elbassioni et al. [ [36 ] . Hardness for general systems does not by itself give hardness for lottery instances, in which the variables form a probability vector, the simplex equation must hold, and, with binary utilities, each agent requires enough probability on a fixed subset of alternatives. Theorem 3.1 gives a reduction that stays within these instances. Conversely, a full-information method that treats the simplex constraints as mandatory can be used once all n n n agents have been recovered, at a cost of n n n times the per-agent recovery cost; our limited-query results ask what can be guaranteed with fewer queries. Castiglioni et al. [2023] study a relaxation of MAX-FS over the simplex in which each constraint may be violated by a small additive slack. Theorem 4.2 uses their sampling argument, and § 4.2 compares the two.
AI alignment with diverse stakeholders. Conitzer et al. [2024] and Sorensen et al. [2024] argued that aligning AI systems with people whose values differ calls for tools from social choice; this line of work mostly concerns training, whereas we study which mixture of trained versions to deploy. In a similar vein, Neoh et al. [2026b] selected a small committee of AI systems from binary or pairwise feedback using few queries. Randomized classifiers in fair classification meet known constraints on group-level rates [2 ] ; our constraints are hidden and need not all be met.
Probabilistic social choice and portioning. Randomization is widely used to aggregate preferences, break ties, allocate resources, or satisfy fairness and efficiency criteria [25 , 22 , 27 ] (Hylland and Zeckhauser 1979; Abdulkarıoğlu and Sönmez 2003). A lottery can also be viewed as a division of a divisible resource, such as money or time, among the alternatives; aggregating preferences into such a division is known as portioning or budget aggregation [13 , 42 , 41 , 37 ] (Bogomolnaja et al. 2005; Arieli et al. 2023), and we refer to the survey by Suksompong and Teh [2026] for an overview of voting in such divisible settings. This literature takes preferences, proposed divisions, priorities, or constraints as input, whereas our decision maker observes only accept/reject answers about proposed lotteries.
Learning-augmented algorithms. Learning-augmented algorithms use possibly erroneous predictions to circumvent worst-case limits such as Theorem 6.1 [58 ] , for instance in mechanism design [3 ] , online fair division [17 , 62 ] , and voting [21 ] (Appendix § 10 ); Choo et al. [2026b] used such advice to find a unanimously acceptable lottery with fewer queries.
Preliminaries
Let m ≥ 2 m \ge2 m ≥ 2 be the number of alternatives and n ≥ 1 n \ge1 n ≥ 1 the number of agents. For an integer z ≥ 1 z \ge1 z ≥ 1 , write [ z ] : = { 1 , … , z } [z] := \{1,\ldots,z\} [ z ] := { 1 , … , z } . Let N : = [ n ] N := [n] N := [ n ] be the set of agents and S : = { s 1 , … , s m } S := \{s_1,\ldots,s_m\} S := { s 1 , … , s m } the set of alternatives. A lottery is a probability vector x = ( x 1 , … , x m ) ∈ Δ ( S ) : = { x ∈ R ≥ 0 m : ∑ j = 1 m x j = 1 } \mathbf{x} = (x_1,\ldots,x_m) \in\Delta(S) := \{\mathbf{x} \in\mathbb{R}_{\ge0}^{m} : \sum_{j=1}^{m} x_j = 1\} x = ( x 1 , … , x m ) ∈ Δ ( S ) := { x ∈ R ≥ 0 m : ∑ j = 1 m x j = 1 } , where x j x_j x j is the probability of s j s_j s j ; the pure lottery on s j s_j s j is the standard basis vector e j \mathbf{e}_j e j . We write ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ for the standard inner product on R m \mathbb{R}^{m} R m , and log \log log for the natural logarithm.
Agents. Agent i ∈ N i \in N i ∈ N accepts exactly the lotteries in its acceptable set A i = { x ∈ Δ ( S ) : ⟨ u i , x ⟩ ≥ τ i } A_i = \{\mathbf{x} \in\Delta(S) : \langle\mathbf{u}_i,\mathbf{x}\rangle\ge\tau_i\} A i = { x ∈ Δ ( S ) : ⟨ u i , x ⟩ ≥ τ i } , where u i ∈ [ 0 , 1 ] m \mathbf{u}_i \in[0,1]^m u i ∈ [ 0 , 1 ] m gives agent i i i ’s utility u i ( s j ) u_i(s_j) u i ( s j ) for each alternative and τ i \tau_i τ i is its threshold. We write U i ( x ) : = ⟨ u i , x ⟩ U_i(\mathbf{x}) := \langle\mathbf{u}_i,\mathbf{x}\rangle U i ( x ) := ⟨ u i , x ⟩ for the expected utility. Thus A i A_i A i is the part of the simplex on one side of a hyperplane (Figure 1a). We exclude degenerate agents: every agent accepts at least one lottery and rejects at least one, i.e., ∅ ≠ A i ⊊ Δ ( S ) \varnothing\ne A_i \subsetneq\Delta(S) ∅ = A i ⊊ Δ ( S ) . Membership queries reveal A i A_i A i but not the pair ( u i , τ i ) (\mathbf{u}_i,\tau_i) ( u i , τ i ) : since ⟨ 1 , x ⟩ = 1 \langle\mathbf{1},\mathbf{x}\rangle= 1 ⟨ 1 , x ⟩ = 1 on Δ ( S ) \Delta(S) Δ ( S ) , the pair ( λ u i + μ 1 , λ τ i + μ ) (\lambda\mathbf{u}_i + \mu\mathbf{1},\lambda\tau_i+\mu) ( λ u i + μ 1 , λ τ i + μ ) gives the same set A i A_i A i for every λ > 0 \lambda> 0 λ > 0 and μ ∈ R \mu\in\mathbb{R} μ ∈ R . Margins U i ( x ) − τ i U_i(\mathbf{x})-\tau_i U i ( x ) − τ i are therefore meaningful only after fixing a normalization. If A i A_i A i has nonempty relative interior in Δ ( S ) \Delta(S) Δ ( S ) , we use the unique pair with min j u i ( s j ) = 0 \min_j u_i(s_j)=0 min j u i ( s j ) = 0 and max j u i ( s j ) = 1 \max_j u_i(s_j)=1 max j u i ( s j ) = 1 . Otherwise, A i A_i A i consists of the lotteries that put all probability on some nonempty proper subset of alternatives, and we let u i \mathbf{u}_i u i be the indicator vector of that subset and τ i = 1 \tau_i=1 τ i = 1 (Lemma B.1 ). From now on, ( u i , τ i ) (\mathbf{u}_i,\tau_i) ( u i , τ i ) denotes this normalized pair ; thus u i ∈ [ 0 , 1 ] m \mathbf{u}_i \in[0,1]^m u i ∈ [ 0 , 1 ] m and τ i ∈ ( 0 , 1 ] \tau_i \in(0,1] τ i ∈ ( 0 , 1 ] .
Membership queries. A query ( i , x ) ∈ N × Δ ( S ) (i,\mathbf{x}) \in N \times\Delta(S) ( i , x ) ∈ N × Δ ( S ) returns Query ( i , x ) = 1 \operatorname{Query}(i,\mathbf{x}) = 1 Query ( i , x ) = 1 if agent i i i accepts x \mathbf{x} x and 0 0 0 otherwise; no utility or threshold is observed. We write Q Q Q for the total number of queries and K K K for the number of distinct agents queried.
Finite-grid convention. All geometric and statistical results allow arbitrary real-valued normalized pairs. Only when we state an explicit query budget, or a running time that depends on recovered agents, do we assume that the normalized pair lies on a known grid: u i ( s j ) ∈ { ε , 2 ε , … , 1 } u_i(s_j) \in\{\varepsilon,2\varepsilon,\ldots,1\} u i ( s j ) ∈ { ε , 2 ε , … , 1 } and τ i ∈ { ε , 2 ε , … , 1 } \tau_i \in\{\varepsilon,2\varepsilon,\ldots,1\} τ i ∈ { ε , 2 ε , … , 1 } , where ε ∈ ( 0 , 1 / 2 ] \varepsilon\in(0,1/2] ε ∈ ( 0 , 1/2 ] and 1 / ε 1/\varepsilon 1/ ε is an integer. The lottery is not discretized: the decision maker may propose any point of Δ ( S ) \Delta(S) Δ ( S ) . Under this convention, the halfspace recovery routine of Choo et al. [2026b] finds an agent’s normalized pair with T ε = O ( m log ( 1 / ε ) ) T_\varepsilon= O(m\log(1/\varepsilon)) T ε = O ( m log ( 1/ ε )) queries; we call this recovering the agent. Appendix § 11 .§ 2 explains why some such assumption is needed for exact recovery.
Objective. The violation count of a lottery x \mathbf{x} x is viol ( x ) : = ∣ { i ∈ N : U i ( x ) < τ i } ∣ \operatorname{viol}(\mathbf{x}) := |\{i \in N : U_i(\mathbf{x}) < \tau_i\}| viol ( x ) := ∣ { i ∈ N : U i ( x ) < τ i } ∣ , the number of agents who reject x \mathbf{x} x . The problem MIN-VIOL asks for a lottery minimizing viol, and OPT : = min x ∈ Δ ( S ) viol ( x ) \operatorname{OPT} := \min_{\mathbf{x}\in\Delta(S)} \operatorname{viol}(\mathbf{x}) OPT := min x ∈ Δ ( S ) viol ( x ) . The minimum is attained: the set of lotteries with at most a given number of violations is a finite union of intersections of the closed sets A i A_i A i , hence closed in the compact set Δ ( S ) \Delta(S) Δ ( S ) . The same holds for any finite set or multiset of agents. The following example shows that mixed lotteries can be strictly better than pure ones.
Example 2.1. Let m ≥ 4 m \ge4 m ≥ 4 and n = 4 n=4 n = 4 , and let agents 1 1 1 , 2 2 2 , 3 3 3 , and 4 4 4 accept x \mathbf{x} x if and only if x 1 + x 2 ≥ 3 / 5 x_1+x_2 \ge3/5 x 1 + x 2 ≥ 3/5 , x_1+x__3 \ge3/5 , x 2 + x 3 ≥ 3 / 5 x_2+x_3 \ge3/5 x 2 + x 3 ≥ 3/5 , and x 4 ≥ 3 / 10 x_4 \ge3/10 x 4 ≥ 3/10 , respectively; all utilities are 0 0 0 or 1 1 1 . If agents 1 1 1 , 2 2 2 , and 3 3 3 accept x \mathbf{x} x , adding their conditions gives x 1 + x 2 + x 3 ≥ 9 / 10 x_1+x_2+x_3 \ge9/10 x 1 + x 2 + x 3 ≥ 9/10 , so x 4 ≤ 1 / 10 x_4 \le1/10 x 4 ≤ 1/10 and agent 4 4 4 rejects x \mathbf{x} x . Hence no lottery is accepted by every agent. The lottery x ∗ = ( 1 / 3 , 1 / 3 , 1 / 3 , 0 , … , 0 ) \mathbf{x}^*=(1/3,1/3,1/3,0,\ldots,0) x ∗ = ( 1/3 , 1/3 , 1/3 , 0 , … , 0 ) is rejected only by agent 4 4 4 , so OPT = 1 \operatorname{OPT}=1 OPT = 1 , whereas every pure lottery is rejected by at least two agents. The three agents who accept x ∗ \mathbf{x}^* x ∗ do so with margin 2 / 3 − 3 / 5 = 1 / 15 2/3-3/5=1/15 2/3 − 3/5 = 1/15 .
Interpreting linear acceptability. U i ( x ) U_i(\mathbf{x}) U i ( x ) is the expected value, under the lottery, of a quantity attached to each alternative: an expected von Neumann–Morgenstern utility [73 , 40 ] , or an average outcome such as access probability, service level, safety, or the negative of a loss. By the law of total expectation, such averages combine linearly when an alternative is drawn at random. This linear threshold model is the standard cardinal baseline in random assignment and probabilistic social choice [49 , 25 ] , and, as with linear classifiers in statistical learning [72 , 11 ] [67 ] , it gives the hidden acceptable sets a finite-dimensional structure that can be learned. Appendix B.1 and § 8 discuss its limits.
Hardness of Approximating Min-Viol
Before asking what can be learned from limited queries, we study the full-information problem, in which all normalized pairs ( u i , τ i ) (u_i,\tau_i) ( u i , τ i ) are given.
Theorem 3.1. Given all normalized pairs ( u i , τ i ) i ∈ N (u_i,\tau_i)_{i\in N} ( u i , τ i ) i ∈ N , MIN-VIOL is APX-hard. In particular, unless P = N P P = NP P = N P , it admits no polynomial-time approximation scheme (PTAS). This remains true even when all utilities are binary, i.e., u i ( s j ) ∈ { 0 , 1 } u_i(s_j) \in\{0,1\} u i ( s j ) ∈ { 0 , 1 } for each i ∈ N i \in N i ∈ N and j ∈ [ m ] j \in[m] j ∈ [ m ] .
Proof idea. We give an approximation-preserving reduction from MINIMUM VERTEX COVER on cubic graphs, which is APX-hard [5 ] . For a cubic graph on q q q vertices, there is one alternative for each vertex and one extra alternative that receives the probability not placed on vertices. The vertex agent of vertex j j j has utility 1 only on alternative j j j and threshold 1 / q 1/q 1/ q , so it accepts if and only if x j ≥ 1 / q x_j \ge1/q x j ≥ 1/ q . For each edge { j , j ′ } \{j,j'\} { j , j ′ } , there are q 2 q^2 q 2 identical edge agents with utility 0 on alternatives j j j and j ′ j' j ′ , utility 1 elsewhere, and threshold 1 − 1 / q 1 - 1/q 1 − 1/ q , so they accept if and only if x j + x j ′ ≤ 1 / q x_j + x_{j'} \le1/q x j + x j ′ ≤ 1/ q . A lottery that violates an edge agent violates all q 2 q^2 q 2 copies, more than the q q q violations of the pure lottery on the extra alternative. From any lottery x x x we obtain a vertex cover of size at most viol ( x ) \operatorname{viol}(x) viol ( x ) : all vertices if some edge agent rejects x x x , and otherwise the vertices j j j with x j < 1 / q x_j < 1/q x j < 1/ q , which cover every edge because no edge has both endpoints with probability at least 1 / q 1/q 1/ q (that would give x j + x j ′ ≥ 2 / q x_j + x_{j'} \ge2/q x j + x j ′ ≥ 2/ q ). Conversely, a vertex cover C C C gives a lottery with exactly ∣ C ∣ |C| ∣ C ∣ violations (probability 1 / q 1/q 1/ q on each vertex outside C C C ). Hence an α \alpha α -approximation for MIN-VIOL gives an α \alpha α -approximation for MINIMUM VERTEX COVER on cubic graphs. The full proof is in Appendix C.
Comparison with hardness proofs for general systems. The hardness results of Amaldi and Kann [1995] concern linear systems with arbitrary coefficients and unconstrained variables. In our reduction, every graph constraint must instead be an acceptance condition with 0/1 utilities over lotteries: the edge condition x j + x j ′ ≤ 1 / q x_j + x_{j'} \le1/q x j + x j ′ ≤ 1/ q is written as 1 − x j − x j ′ ≥ 1 − 1 / q 1 - x_j - x_{j'} \ge1 - 1/q 1 − x j − x j ′ ≥ 1 − 1/ q , the probability of all alternatives other than j j j and j ′ j' j ′ . The extra alternative absorbs the probability not placed on vertices, so that every vertex query gives a valid lottery and the pure lottery on the extra alternative violates only the q q q vertex agents; this is what makes violating an edge agent never worthwhile.
What the theorem does not show. Theorem 3.1 rules out a PTAS but not every constant-factor approximation. Much stronger inapproximability is known for MIN-ULR on general linear systems [12 , 7 ] ; we do not know whether it holds for lottery instances. The theorem also concerns multiplicative approximation with full information, so it is not a lower bound matching the additive sampling guarantees of § 5 .
Exact Algorithms Under Full Information
Theorem 3.1 shows that exact optimization needs additional structure. We consider three kinds: a constant number of alternatives (Section 4.1), a margin condition under which few alternatives suffice (Section 4.2), and a small number of violations (Section 4.3).
A Constant Number of Alternatives
Fix the set of agents that a lottery must satisfy. The lotteries satisfying them form a polytope, and an optimal lottery can be taken to be a vertex of it. Each vertex is the unique solution of the simplex equation together with m − 1 m-1 m − 1 tight constraints, each of the form x j = 0 x_j=0 x j = 0 or U i ( x ) = τ i U_i(x)=\tau_i U i ( x ) = τ i . Enumerating all such linear systems and keeping the best solution gives the following result (proof in Appendix D.1). It is closely related to exact algorithms for linear programming with a given number of violated constraints in fixed dimension [57 , 31 ] , which can also be applied here; we include it because it is simple and has an explicit running time.
Theorem 4.1. Given all normalized pairs ( u i , τ i ) i ∈ N (u_i,\tau_i)_{i\in N} ( u i , τ i ) i ∈ N , there is a deterministic algorithm that returns a lottery minimizing viol in time O ( ( n + m m − 1 ) ( m 3 + n m ) ) O\left(\binom{n+m}{m-1}(m^3+nm)\right) O ( ( m − 1 n + m ) ( m 3 + nm ) ) . This is polynomial for every constant number m m m of alternatives. Since the exponent of n n n grows with m m m , this is an XP algorithm in the parameter m m m , not an FPT one; in particular, the decision version (is OPT at most a given number?) is in XP when parameterized by m m m .
Few Alternatives Under a Margin Condition
A lottery uses alternative s j s_j s j if x j > 0 x_j>0 x j > 0 . We now show that a lottery using many alternatives can be replaced by one using few. For η > 0 \eta>0 η > 0 and a lottery x x x , let B η ( x ) : = { i ∈ N : τ i ≤ U i ( x ) < τ i + η } B_\eta(x):=\{i\in N:\tau_i\le U_i(x)<\tau_i+\eta\} B η ( x ) := { i ∈ N : τ i ≤ U i ( x ) < τ i + η } be the set of agents who accept x x x with margin less than η \eta η (in the normalization of Section 2; see Figure 1a), and let s η : = ⌈ log ( 2 n ) 2 η 2 ⌉ s_\eta:=\left\lceil\frac{\log(2n)}{2\eta^2}\right\rceil s η := ⌈ 2 η 2 l o g ( 2 n ) ⌉ .
Theorem 4.2. For every lottery x x x and every η > 0 \eta>0 η > 0 , there is a lottery x ~ \tilde{x} x ~ that uses at most s η s_\eta s η alternatives and satisfies U i ( x ~ ) ≥ U i ( x ) − η U_i(\tilde{x})\ge U_i(x)-\eta U i ( x ~ ) ≥ U i ( x ) − η for all i ∈ N i\in N i ∈ N . Consequently, viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ \operatorname{viol}(\tilde{x})\le\operatorname{viol}(x)+|B_\eta(x)| viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ . In particular, if some optimal lottery x ∗ x^* x ∗ has B η ( x ∗ ) = ∅ B_\eta(x^*)=\varnothing B η ( x ∗ ) = ∅ , then some optimal lottery uses at most s η s_\eta s η alternatives.
Proof idea and relation to Castiglioni et al. [2023]. Draw s η s_\eta s η alternatives independently from x x x and let x ~ \tilde{x} x ~ be their empirical distribution. For each agent, U i ( x ~ ) U_i(\tilde{x}) U i ( x ~ ) is an average of s η s_\eta s η independent values in [ 0 , 1 ] [0,1] [ 0 , 1 ] with mean U i ( x ) U_i(x) U i ( x ) , so Hoeffding’s inequality and a union bound over the n n n agents show that, with probability at least 1 / 2 1/2 1/2 , U i ( x ~ ) ≥ U i ( x ) − η U_i(\tilde{x})\ge U_i(x)-\eta U i ( x ~ ) ≥ U i ( x ) − η for every agent. This sampling step is the argument that Castiglioni et al. [2023] use for their relaxation of MAX-FS over the simplex, and we do not claim it as new. Their guarantee is for the relaxed problem, which counts a constraint as satisfied if it is violated by at most an additive slack. Theorem 4.2 instead counts violations at the original thresholds: an agent who accepts x x x with margin at least η \eta η still accepts x ~ \tilde{x} x ~ , so the only agents who can become violated are those in B η ( x ) B_\eta(x) B η ( x ) . The full proof is in Appendix D.2.
Proposition 4.3. For every integer s ≥ 1 s\ge1 s ≥ 1 , a lottery minimizing viol among all lotteries that use at most s s s alternatives can be computed in time ( m ( n + s ) ) O ( s ) (m(n+s))^{O(s)} ( m ( n + s ) ) O ( s ) .
For each set of at most s s s alternatives, the algorithm applies Theorem 4.1 to the lotteries that use only those alternatives (proof in Appendix D.3). Combining it with Theorem 4.2 gives the following (proof in Appendix D.4).
Corollary 4.4. For every η > 0 \eta>0 η > 0 , running the algorithm of Proposition 4.3 with s = s η s=s_\eta s = s η takes time ( m ( n + s η ) ) O ( s η ) (m(n+s_\eta))^{O(s_\eta)} ( m ( n + s η ) ) O ( s η ) and returns a lottery x ~ \tilde{x} x ~ with viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ \operatorname{viol}(\tilde{x})\le\operatorname{viol}(x)+|B_\eta(x)| viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ for every lottery x x x . In particular, viol ( x ~ ) ≤ OPT + ∣ B η ( x ∗ ) ∣ \operatorname{viol}(\tilde{x})\le\operatorname{OPT}+|B_\eta(x^*)| viol ( x ~ ) ≤ OPT + ∣ B η ( x ∗ ) ∣ for every optimal lottery x ∗ x^* x ∗ , and x ~ \tilde{x} x ~ is optimal if B η ( x ∗ ) = ∅ B_\eta(x^*)=\varnothing B η ( x ∗ ) = ∅ for some optimal x ∗ x^* x ∗ .
The running time is not polynomial. For constant η \eta η , it is ( m n ) O ( log n ) (mn)^{O(\log n)} ( mn ) O ( l o g n ) , which is quasi-polynomial, and it grows quickly as η \eta η decreases. The lottery x ~ \tilde{x} x ~ in the proof of Theorem 4.2 has all probabilities equal to multiples of 1 / s η 1/s_\eta 1/ s η . Hence the guarantee of Corollary 4.4 is also obtained by the enumeration of Castiglioni et al. [2023], if each of the ( m + s η − 1 s η ) \binom{m+s_\eta-1}{s_\eta} ( s η m + s η − 1 ) such lotteries is scored by its exact violation count, in time O ( ( m + s η − 1 s η ) n m ) O\left(\binom{m+s_\eta-1}{s_\eta}nm\right) O ( ( s η m + s η − 1 ) nm ) . Proposition 4.3 returns the best lottery among all that use at most s η s_\eta s η alternatives, which is never worse, at a higher running time. Castiglioni et al. [ [30 ] also show that, under the Exponential Time Hypothesis, their relaxed problem requires quasi-polynomial time.
Few Violations
The running time of Theorem 4.1 is polynomial for constant m m m , but its exponent grows with m m m . When few violations are allowed, the exponential dependence can be limited to m m m and the number of violations together (proof in Appendix § 14 .§ 2 ).
Theorem 4.5. Given all normalized pairs ( u i , τ i ) i ∈ N (u_i,\tau_i)_{i\in N} ( u i , τ i ) i ∈ N and an integer v ∈ { 0 , … , n } v \in\{0,\ldots,n\} v ∈ { 0 , … , n } , there is a deterministic algorithm that decides whether some lottery has at most v v v violations and, if so, returns one, using at most m v ⋅ poly ( n , m ) m^v \cdot\operatorname{poly}(n,m) m v ⋅ poly ( n , m ) LP feasibility checks over Δ ( S ) \Delta(S) Δ ( S ) . Hence, when the utilities and thresholds are given explicitly, this problem is fixed-parameter tractable when parameterized by ( v , m ) (v,m) ( v , m ) .
Proof idea. If the acceptable sets of the remaining agents have a common point, an LP finds it. Otherwise, by Helly’s theorem [47 ] in the ( m − 1 ) (m-1) ( m − 1 ) -dimensional affine hull of the simplex, at most m m m of these sets already have no common point. Such a subfamily can be found with at most n n n LP feasibility checks, by removing agents one at a time as long as the remaining sets still have no common point. A lottery with at most v v v violations must violate one of these at most m m m agents, so the algorithm branches on which of them to drop; the recursion has depth at most v v v and at most m m m branches per step. This is in the spirit of algorithms for optimization with few violated constraints [57 ] .
The parameter cannot be reduced to the number of violations alone (proof in Appendix § 14 .§ 3 ). □
Theorem 4.6. Given all normalized pairs ( u i , τ i ) i ∈ N (u_i,\tau_i)_{i\in N} ( u i , τ i ) i ∈ N and an integer v v v , deciding whether some lottery has at most v v v violations is W[2]-hard when parameterized by v v v alone, even when all utilities are 0 or 1. Hence, unless FPT = W[2], there is no algorithm with running time f ( v ) ⋅ poly ( n , m ) f(v)\cdot\operatorname{poly}(n,m) f ( v ) ⋅ poly ( n , m ) for any function f f f .
Proof idea. We reduce from HITTING SET: given a family of subsets of [ q ] [q] [ q ] and an integer v v v , is there a set of at most v v v elements that meets every member of the family? As in the proof of Theorem 3.1 , there is one alternative for each element and one extra alternative. The agent of element j j j accepts if and only if x j ≥ 1 / q x_j \ge1/q x j ≥ 1/ q . For each set F F F in the family, v + 1 v+1 v + 1 identical agents accept if and only if ∑ j ∈ F x j ≤ ( ∣ F ∣ − 1 ) / q \sum_{j\in F}x_j \le(|F|-1)/q ∑ j ∈ F x j ≤ ( ∣ F ∣ − 1 ) / q , which is an acceptance condition with 0/1 utilities. A lottery with at most v v v violations cannot violate these v + 1 v+1 v + 1 copies, so every set F F F contains an element j j j with x j < 1 / q x_j < 1/q x j < 1/ q ; these elements form a hitting set whose size is the number of violations. Conversely, a hitting set C C C gives a lottery with exactly ∣ C ∣ |C| ∣ C ∣ violations (probability 1 / q 1/q 1/ q on each element outside C C C ).
Finally, when m = 2 m=2 m = 2 , the simplex is a segment and each acceptable set is an interval, so MIN-VIOL reduces to finding a point contained in the largest number of intervals, which takes O ( n log n ) O(n\log n) O ( n log n ) time by sorting the endpoints (Proposition E.1 ). □
Limited Queries: Learning from Sampled Agents
The previous sections studied the full-information problem, in which every agent’s constraint is known. We now ask what can be guaranteed when far fewer than n n n agents are queried. In this section, k k k agents i 1 , … , i k i_1,\ldots,i_k i 1 , … , i k are sampled independently and uniformly from N N N (with replacement), and the acceptable sets of the sampled agents are recovered; § 6 drops the sampling assumption. The results are statistical statements about uniform sampling. Each sampled agent costs at most T ε T_\varepsilon T ε queries, so a budget of Q Q Q queries allows ⌊ Q / T ε ⌋ \lfloor Q/T_\varepsilon\rfloor ⌊ Q / T ε ⌋ samples; Appendix § 16 states the resulting guarantees together with running times.
Theorem 5.1. Fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and k ≥ m k \ge m k ≥ m . With probability at least 1 − δ 1-\delta 1 − δ , every lottery x ^ \hat{x} x ^ that minimizes the number of sampled agents who reject it (counting repeated samples with multiplicity) satisfies viol ( x ^ ) ≤ OPT + 8 n m log ( 2 e k / m ) + log ( 8 / δ ) / k \operatorname{viol}(\hat{x}) \le\operatorname{OPT}+8n\sqrt{m\log(2ek/m)+\log(8/\delta)}/k viol ( x ^ ) ≤ OPT + 8 n m log ( 2 e k / m ) + log ( 8/ δ ) / k .
Proof idea. Agent i i i rejects x x x if and only if ⟨ u i − τ i 1 , x ⟩ < 0 \langle u_i-\tau_i\mathbf{1},x\rangle<0 ⟨ u i − τ i 1 , x ⟩ < 0 , so the set of agents rejecting x x x is cut out by a halfspace through the origin of R m \mathbb{R}^m R m . The family of these sets therefore has VC dimension at most m m m , and the standard VC inequality gives uniform convergence of the sampled rejection rate to the population rate. The argument is standard; what is specific to lotteries is the bound m m m on the VC dimension. The proof is in Appendix F.1.
The same sampling procedure also gives a relative guarantee when OPT is not too small. The proof replaces the VC inequality with the relative-error bound of Li et al. [2001], which bounds the difference between the sampled and true rejection rates by a small multiple of their sum plus ρ \rho ρ (Appendix F.2).
Theorem 5.2. There is an absolute constant C > 0 C > 0 C > 0 such that the following holds. Fix δ , ρ ∈ ( 0 , 1 / 2 ) \delta, \rho\in(0, 1/2) δ , ρ ∈ ( 0 , 1/2 ) and ζ ∈ ( 0 , 1 ] \zeta\in(0, 1] ζ ∈ ( 0 , 1 ] , and let k ≥ C ( m log ( 1 / ρ ) + log ( 1 / δ ) ) / ( ζ 2 ρ ) k \ge C(m \log(1/\rho) + \log(1/\delta))/(\zeta^2\rho) k ≥ C ( m log ( 1/ ρ ) + log ( 1/ δ )) / ( ζ 2 ρ ) . With probability at least 1 − δ 1-\delta 1 − δ , every lottery x ^ \hat{\mathbf{x}} x ^ as in Theorem 5.1 satisfies viol ( x ^ ) ≤ ( 1 + ζ / 2 ) O P T + ( ζ / 2 ) ρ n \operatorname{viol}(\hat{\mathbf{x}}) \le(1+\zeta/2)\mathrm{OPT}+(\zeta/2)\rho n viol ( x ^ ) ≤ ( 1 + ζ /2 ) OPT + ( ζ /2 ) ρ n . In particular, if O P T ≥ ρ n \mathrm{OPT} \ge\rho n OPT ≥ ρ n , then viol ( x ^ ) ≤ ( 1 + ζ ) O P T \operatorname{viol}(\hat{\mathbf{x}}) \le(1+\zeta)\mathrm{OPT} viol ( x ^ ) ≤ ( 1 + ζ ) OPT .
Theorems 5.1 and 5.2 concern how well a sample represents the population, assuming exact minimization on the sample, which Theorem 4.1 provides when m m m is constant. Section 5.1 handles arbitrary m m m .
A Polynomial-Time LP for Arbitrary m m m
When m m m is part of the input, exact minimization on the sample is an instance of MIN-VIOL, which is APX-hard (Theorem 3.1). We therefore replace each violation by a convex penalty. For a margin parameter η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] , agent i i i is charged max { 0 , ( τ i + η − U i ( x ) ) / η } \max\{0,(\tau_i+\eta-U_i(\mathbf{x}))/\eta\} max { 0 , ( τ i + η − U i ( x )) / η } : this is 0 if i i i accepts x \mathbf{x} x with margin at least η \eta η , 1 on the acceptance boundary, and more than 1 if i i i rejects x \mathbf{x} x . Minimizing the average penalty over the sample is the linear program
minimize 1 k ∑ t = 1 k z t subject to z t ≥ 1 η ( τ i t + η − ⟨ u i t , x ⟩ ) and z t ≥ 0 for all t ∈ [ k ] , x ∈ Δ ( S ) . (1) \begin{aligned}
\text{minimize}\quad& \frac{1}{k}\sum_{t=1}^{k}z_t\\
\text{subject to}\quad& z_t \ge\frac{1}{\eta}(\tau_{i_t}+\eta-\langle\mathbf{u}_{i_t},\mathbf{x}\rangle)\ \text{ and }\ z_t \ge0\quad\text{for all }t\in[k],\ \mathbf{x}\in\Delta(S). \tag*{(1)}
\end{aligned} minimize subject to k 1 t = 1 ∑ k z t z t ≥ η 1 ( τ i t + η − ⟨ u i t , x ⟩) and z t ≥ 0 for all t ∈ [ k ] , x ∈ Δ ( S ) . (1)
Repeated copies of a sampled agent can be merged into one constraint with the corresponding weight in the objective.
Theorem 5.3. There is an absolute constant C > 0 C > 0 C > 0 such that the following holds. Fix an integer k ≥ 1 k \ge1 k ≥ 1 , δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] , and let x ^ η \hat{\mathbf{x}}_\eta x ^ η be the x \mathbf{x} x -part of any optimal solution of the linear program (1). With probability at least 1 − δ 1-\delta 1 − δ , viol ( x ^ η ) ≤ ( 1 + 1 / η ) viol ( x ) + ∣ B η ( x ) ∣ + ( C n / η ) ( log m + log ( 1 / δ ) ) / k \operatorname{viol}(\hat{\mathbf{x}}_\eta) \le(1+1/\eta)\operatorname{viol}(\mathbf{x})+|B_\eta(\mathbf{x})|+(Cn/\eta)\sqrt{(\log m+\log(1/\delta))/k} viol ( x ^ η ) ≤ ( 1 + 1/ η ) viol ( x ) + ∣ B η ( x ) ∣ + ( C n / η ) ( log m + log ( 1/ δ )) / k for every lottery x \mathbf{x} x .
Proof idea. The penalty is at least the violation indicator. For a fixed lottery x \mathbf{x} x , it is at most 1 + 1 / η 1+1/\eta 1 + 1/ η for an agent rejecting x \mathbf{x} x , at most 1 for an agent in B η ( x ) B_\eta(\mathbf{x}) B η ( x ) , and 0 for every other agent, so the population average penalty of x \mathbf{x} x is at most ( ( 1 + 1 / η ) viol ( x ) + ∣ B η ( x ) ∣ ) / n ((1+1/\eta)\operatorname{viol}(\mathbf{x})+|B_\eta(\mathbf{x})|)/n (( 1 + 1/ η ) viol ( x ) + ∣ B η ( x ) ∣ ) / n . The penalty is a ( 1 / η ) (1/\eta) ( 1/ η ) -Lipschitz function of U i ( x ) − τ i U_i(\mathbf{x})-\tau_i U i ( x ) − τ i , which is a convex combination of the m m m functions i ↦ u i ( s j ) − τ i i\mapsto u_i(s_j)-\tau_i i ↦ u i ( s j ) − τ i ; standard Rademacher complexity bounds Bartlett and Mendelson, [18 ] then give uniform convergence at rate ( 1 / η ) log m / k (1/\eta)\sqrt{\log m/k} ( 1/ η ) log m / k . The proof is in Appendix F.3.
The bound is useful when some lottery has few violations and few agents accepted with margin less than η \eta η . If B η ( x ∗ ) = ∅ B_\eta(\mathbf{x}^*)=\varnothing B η ( x ∗ ) = ∅ for an optimal lottery x ∗ \mathbf{x}^* x ∗ , the bound is ( 1 + 1 / η ) O P T (1+1/\eta)\mathrm{OPT} ( 1 + 1/ η ) OPT plus the sampling error; if some lottery is accepted by every agent with margin at least η \eta η , only the sampling error remains. For instance, in Example 2.1, O P T = 1 \mathrm{OPT}=1 OPT = 1 and the optimal lottery x ∗ \mathbf{x}^* x ∗ given there has B 1 / 15 ( x ∗ ) = ∅ B_{1/15}(\mathbf{x}^*)=\varnothing B 1/15 ( x ∗ ) = ∅ .
Full information. If the LP is run on all n n n agents, each once, instead of on a sample, the sampling term disappears: viol ( x ^ η ) ≤ ( 1 + 1 / η ) viol ( x ) + ∣ B η ( x ) ∣ \operatorname{viol}(\hat{\mathbf{x}}_\eta)\le(1+1/\eta)\operatorname{viol}(\mathbf{x})+|B_\eta(\mathbf{x})| viol ( x ^ η ) ≤ ( 1 + 1/ η ) viol ( x ) + ∣ B η ( x ) ∣ for every lottery x \mathbf{x} x . The factor 1 + 1 / η 1+1/\eta 1 + 1/ η comes from the penalty of violated agents, not from sampling. Capping the penalty at 1 would remove this factor, but the capped penalty is not convex, so minimizing it is no longer a linear program.
Which method to use. Exact minimization on the sample, combined with Theorem 5.1, avoids the factor 1 + 1 / η 1+1/\eta 1 + 1/ η and the term ∣ B η ( x ) ∣ |B_\eta(\mathbf{x})| ∣ B η ( x ) ∣ of Theorem 5.3, and is preferable when it is affordable: when m m m is a small constant, when m = 2 m=2 m = 2 (Proposition E.1), or when m m m and the optimal number of violations on the sample are both small (Theorem 4.5). Running Corollary 4.4 on the sample takes quasi-polynomial time and is exact only under its margin condition. The LP runs in polynomial time for every m m m and every sample, without any margin condition, and its sampling term grows with log m \log m log m rather than m m m .
The Deterministic Worst Case
We now drop the sampling assumption. A profile I = ( ( u i , τ i ) ) i ∈ N \mathcal{I} = ((u_i, \tau_i))_{i \in\mathbb{N}} I = (( u i , τ i ) ) i ∈ N lists all normalized pairs; we write viol I ( x ) \operatorname{viol}_{\mathcal{I}}(x) viol I ( x ) and OPT ( I ) \operatorname{OPT}(\mathcal{I}) OPT ( I ) for the violation count and its minimum under I \mathcal{I} I . For a deterministic algorithm A \mathcal{A} A , let A ( I ) \mathcal{A}(\mathcal{I}) A ( I ) be the lottery it returns when its queries are answered according to I \mathcal{I} I ; its additive gap on I \mathcal{I} I is viol I ( A ( I ) ) − OPT ( I ) \operatorname{viol}_{\mathcal{I}}(\mathcal{A}(\mathcal{I})) - \operatorname{OPT}(\mathcal{I}) viol I ( A ( I )) − OPT ( I ) .
An algorithm that recovers a fixed set M M M of K K K agents and returns a lottery x M x_M x M minimizing the number of violated agents in M M M has additive gap at most n − K n-K n − K on every profile. Indeed, if x ∗ x^* x ∗ is optimal for I \mathcal{I} I , then x M x_M x M violates at most as many agents of M M M as x ∗ x^* x ∗ does, and at most n − K n-K n − K agents outside M M M , so viol I ( x M ) ≤ OPT ( I ) + n − K \operatorname{viol}_{\mathcal{I}}(x_M) \le\operatorname{OPT}(\mathcal{I}) + n-K viol I ( x M ) ≤ OPT ( I ) + n − K . The question is whether adaptive queries, possibly many to the same agents, can do better. For m ≥ 3 m \ge3 m ≥ 3 they cannot.
Theorem 6.1. Fix m ≥ 3 m \ge3 m ≥ 3 and a deterministic algorithm A \mathcal{A} A . Run A \mathcal{A} A with every query ( i , x ) (i,x) ( i , x ) answered “accept” if and only if x 3 = ⋯ = x m = 0 x_3 = \cdots= x_m = 0 x 3 = ⋯ = x m = 0 , and let M M M be the set of agents it queries and x ^ \hat{x} x ^ its output. Then there is a profile I \mathcal{I} I with binary utilities and all thresholds equal to 1 1 1 such that A \mathcal{A} A , run on I \mathcal{I} I , receives the same answers and therefore returns x ^ \hat{x} x ^ , every agent outside M M M rejects x ^ \hat{x} x ^ , and all agents accept the same pure lottery e 1 e_1 e 1 or e 2 e_2 e 2 . Hence viol I ( x ^ ) ≥ n − ∣ M ∣ \operatorname{viol}_{\mathcal{I}}(\hat{x}) \ge n - |M| viol I ( x ^ ) ≥ n − ∣ M ∣ and OPT ( I ) = 0 \operatorname{OPT}(\mathcal{I}) = 0 OPT ( I ) = 0 .
Proof idea. Give every agent in M M M the utility vector ( 1 , 1 , 0 , … , 0 ) (1,1,0,\ldots,0) ( 1 , 1 , 0 , … , 0 ) and threshold 1 1 1 : such an agent accepts exactly the lotteries with x 3 = ⋯ = x m = 0 x_3 = \cdots= x_m = 0 x 3 = ⋯ = x m = 0 , which reproduces every answer. Give every agent outside M M M the utility vector e 1 e_1 e 1 if x ^ ≠ e 1 \hat{x} \ne e_1 x ^ = e 1 and e 2 e_2 e 2 if x ^ = e 1 \hat{x} = e_1 x ^ = e 1 , with threshold $1. Such an agent accepts only that pure lottery, so it rejects x ^ \hat{x} x ^ , while that pure lottery is accepted by every agent (Figure 1 b). The answer rule needs a third alternative so that the queried agents reject some lotteries, as nondegeneracy requires, while accepting both e 1 e_1 e 1 and e 2 e_2 e 2 . The proof is in Appendix § 17 .§ 1 .
Figure 1. Lotteries over three alternatives drawn as points of a triangle with corners e 1 e_1 e 1 , e 2 e_2 e 2 , e 3 e_3 e 3 . (a) An agent’s acceptable set A i A_i A i (shaded) is the part of the triangle on one side of a line; the darker strip contains the lotteries that the agent accepts with margin less than η \eta η . (b) The profile in the proof of Theorem 6.1 when x ^ ≠ e 1 \hat{x} \ne e_1 x ^ = e 1 : every queried agent accepts exactly the lotteries on the bottom edge, and every unqueried agent accepts only e 1 e_1 e 1 . All unqueried agents reject x ^ \hat{x} x ^ , but every agent accepts e 1 e_1 e 1 .
Theorem 6.2. Assume that each queried agent can be recovered with finitely many membership queries, as under the finite-grid convention, and let m ≥ 3 m \ge3 m ≥ 3 . For K ∈ { 0 , … , n } K \in\{0,\ldots,n\} K ∈ { 0 , … , n } , let C K \mathcal{C}_K C K be the class of deterministic algorithms that query at most K K K distinct agents on every profile. Then inf A ∈ C K sup I ( viol I ( A ( I ) ) − OPT ( I ) ) = n − K \inf_{\mathcal{A} \in\mathcal{C}_K} \sup_{\mathcal{I}}(\operatorname{viol}_{\mathcal{I}}(\mathcal{A}(\mathcal{I}))-\operatorname{OPT}(\mathcal{I})) = n-K inf A ∈ C K sup I ( viol I ( A ( I )) − OPT ( I )) = n − K , where the supremum is over all profiles satisfying the model assumptions.
The upper bound is the argument above, and the lower bound follows from Theorem 6.1 (proof in Appendix § 17 .§ 2 ); Teh and Goldberg [ [70 ] prove an analogous lower bound for their distance-based objective. In the sampling model of Section 5, queried agents carry information about unqueried ones. In the worst case they carry none: for m ≥ 3 m \ge3 m ≥ 3 , the best guarantee depends only on how many distinct agents are queried, not on how many queries are spent on them or how adaptively they are chosen.
Bounds after a partial query history. The answers observed so far restrict each agent’s normalized pair to the pairs consistent with them. For a lottery x x x , counting the agents who reject x x x under every consistent pair, and those who reject it under some consistent pair, gives lower and upper bounds on its violation count that hold for every consistent profile; minimizing both over lotteries gives lower and upper bounds on the unknown optimum. The lottery that minimizes the upper count has additive gap at most the difference between the two bounds on the optimum. This difference can only shrink as more answers arrive, and every unqueried agent adds one to it, which is the effect behind Theorem 6.1 . Appendix I proves these facts and gives the exact worst-case additive gap of any fixed lottery after the observed answers.
Synthetic Experiments
We ran small synthetic experiments to see how conservative the worst-case bounds are on random instances; Appendix J gives the setup in full. We generated 20 populations with n = 500 n = 500 n = 500 agents and m = 3 m = 3 m = 3 alternatives in each of two settings. In both, 15% of agents reject a planted lottery and 85% accept it, with margin at least 0.05 in the separated setting and less than 0.05 in the near-threshold setting. Since m = 3 m = 3 m = 3 , we computed OPT exactly with the vertex enumeration of Theorem 4.1 , and checked it against a mixed-integer program on 280 instances, which agreed in every case. For each population and sample size, we drew 6 independent samples. Table 1 reports the results.
Table 1. Mean extra rejection rate ( viol ( x ^ ) − OPT ) / n (\operatorname{viol}(\hat{x})-\operatorname{OPT})/n ( viol ( x ^ ) − OPT ) / n in percent, with 95th percentiles in parentheses.
Findings. (i) Exact minimization on 120 sampled agents is within 2% of the optimum on average, far below the explicit bound of Theorem 5.1 , which exceeds n n n at these sample sizes. Each fourfold increase in k k k reduced the mean extra rejection rate by a factor between about 3.9 and 5.9, faster than the factor 2 2 2 suggested by the 1 / k 1/\sqrt{k} 1/ k rate of Theorem 5.1 . (ii) As the trade-off in η \eta η of Theorem 5.3 suggests, η = 0.05 \eta= 0.05 η = 0.05 was better than η = 0.02 \eta= 0.02 η = 0.02 in the separated setting, and on 120 samples even better than exact minimization, but more than doubled the extra rejection rate in the near-threshold setting, where B 0.05 ( x ) B_{0.05}(\mathbf{x}) B 0.05 ( x ) contains every agent who accepts the planted lottery x \mathbf{x} x . (iii) Querying K = 100 K = 100 K = 100 agents chosen uniformly at random and optimizing over them gave mean additive gaps of 8.46 and 7.99 agents, against the worst-case value n − K = 400 n - K = 400 n − K = 400 ; across the tested values of K K K , the mean gap was between about 0.6% and 19% of n − K n - K n − K . The construction of Theorem 6.1 reached a gap of exactly n − K n - K n − K for every tested K ∈ { 10 , 25 , 50 , 100 , 200 , 400 } K \in\{10, 25, 50, 100, 200, 400\} K ∈ { 10 , 25 , 50 , 100 , 200 , 400 } , so the worst case can occur, but in our experiments only for a specially chosen profile. (iv) With n = 1000 n = 1000 n = 1000 , m = 500 m = 500 m = 500 , and η = 0.15 \eta= 0.15 η = 0.15 , Theorem 4.2 gives s η = 169 s_{\eta} = 169 s η = 169 . When every agent accepted the starting lottery with margin at least η \eta η , sampling 169 alternatives as in its proof never created a new rejection in 480 trials, and sampling only 50 created none in 471 of them. When 20% of agents accepted it with margin less than η \eta η , the mean new rejection rate with 169 alternatives was 1.19% (95th percentile 1.70%), whereas the theorem allows up to 20%.
Conclusion
We studied how to choose a lottery that as few agents as possible reject, in the membership query model of Choo et al. [ [33 ] . The problem is APX-hard even with full information, but it can be solved exactly under additional structure; under uniform sampling, a small number of queried agents gives guarantees for the whole population, and without sampling, for m ≥ 3 m \ge3 m ≥ 3 , the number of distinct queried agents alone determines the worst-case guarantee of deterministic algorithms.
Limitations and extensions. The halfspace model covers thresholds on expected access, safety, service, or loss, but not acceptability that depends on variance, ambiguity, or nonlinear probability weighting (Appendix § 11 .§ 1 ). Theorem 5.1 needs only a bound on the VC dimension of the rejection sets: if another acceptance model gives VC dimension d d d , the same proof applies with d d d in place of m m m . Theorems 4.1 , 4.2 , and 5.3 use linearity through linear boundaries, expected utility as an average over alternatives, and a piecewise-linear penalty, respectively; they do not extend automatically to general convex acceptable sets. The lower bound of Theorem 6.1 does extend, since halfspaces are a special case of convex sets.
Our results assume noiseless answers. Suppose instead that each answer is flipped with probability p < 1 / 2 p < 1/2 p < 1/2 , independently across queries, including repeated ones. Repeating a query r r r times and taking the majority answer, breaking ties arbitrarily, is wrong with probability at most exp ( − r ( 1 − 2 p ) 2 / 2 ) \exp(-r(1 - 2p)^2/2) exp ( − r ( 1 − 2 p ) 2 /2 ) by Hoeffding’s inequality. If the noiseless procedure makes at most Q ≥ 1 Q \ge1 Q ≥ 1 queries, then, for δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , choosing r = ⌈ 2 log ( Q / δ ) / ( 1 − 2 p ) 2 ⌉ r = \lceil2\log(Q/\delta)/(1 - 2p)^2\rceil r = ⌈ 2 log ( Q / δ ) / ( 1 − 2 p ) 2 ⌉ and stopping after at most Q r Qr Q r simulated queries makes every majority answer correct with probability at least 1 − δ 1 - \delta 1 − δ . All noiseless guarantees therefore continue to hold, with the probability that they hold reduced by at most δ \delta δ and with at most r Q rQ r Q queries in total. Persistent or adversarial errors, or preferences that change between queries, require a different model.
Acknowledgments and Disclosure of Funding
This work was funded by the Advanced Research + Invention Agency (ARIA) under the ASPAI project. PWG is also supported by EPSRC Grants EP/X040461/1 and EP/X038548/1.
Additional Related Work
Table 2 compares the works closest to ours. The general objective of satisfying as many linear inequalities as possible is classical; what the table separates is the set over which one optimizes, what information about the constraints is available, and what kind of guarantee is proved.
Aggregated violation distances. Teh and Goldberg [ [70 ] study the same query model with a different objective. Rather than counting the agents who reject a lottery, they measure how severely each agent is violated: after normalizing each agent’s acceptance boundary so that distances are comparable across agents, they take the Euclidean distance from the lottery to the boundary of each violated agent, measured in the affine hull of the simplex, and minimize a power mean of these distances. They characterize when membership queries determine these distances, show that the optimum can then be found exactly, give sampling-based guarantees under a limited query budget, and prove that a deterministic algorithm that leaves some agents unqueried can incur a loss that grows with the fraction of such agents, in parallel with Theorem 6.1 . The two objectives are complementary. A distance-based objective distinguishes a slight violation from a severe one, but a small aggregate distance can still leave many agents slightly below their thresholds; the violation count treats every rejection as equally serious, which suits requirements that are either met or not. Computationally, the power mean of distances is convex once the relevant boundaries are known, whereas minimizing the violation count is APX-hard even with full information (Theorem 3.1 ).
Linear programming with violations. In fixed dimension, Matoušek [1995] and Chan [2005] study linear programs in which a given number of constraints may be violated, and give exact algorithms whose running time is polynomial in the number of constraints for fixed dimension. Their constraints are explicit and their objective is a linear function. These algorithms are closest in spirit to our full-information results for small m m m (Theorem 4.1 and Appendix § 14 ), which concern the violation count over the simplex; our main questions, however, concern what can be learned from membership queries.
Robust fitting and maximum consensus. The violation objective also resembles maximum-consensus and robust-fitting formulations, in which one seeks a model consistent with as many constraints or data points as possible [39 ] . These problems share the view that incompatible constraints should be discarded rather than averaged. However, robust fitting usually concerns parametric models fitted to observed data, with constraints or residuals available numerically. In our setting, the unknown constraints are agents’ acceptable halfspaces of the simplex, and the decision maker observes only binary answers to lotteries that it proposes. Our deterministic lower bound is therefore not a standard robust-estimation lower bound.
Preference elicitation, utility elicitation, and active querying. Our membership query model is motivated by preference and utility elicitation, where full utilities are costly, sensitive, or cognitively difficult to obtain [24 , 26 ] . Much of this work uses value queries, comparison queries, bound queries, or minimax-regret criteria to choose good decisions under utility uncertainty. We differ in both the query and the objective. A query in our model asks whether a concrete lottery is acceptable, not for a utility value, a pairwise comparison, or a bound on a parameter. The goal is not to optimize expected utility or regret for a single partially known utility function, but to minimize the number of agents below their individual thresholds. Recovering sampled agents is one step of our algorithms, but what they output is a lottery with a guarantee for the whole population, not a utility model for every agent.
Membership query learning, active learning, and preference-based learning. Membership queries are classical in computational learning theory [Angluin, 1988], and active learning studies how adaptively chosen queries can reduce label complexity [46 ] . Preference-based learning and dueling bandits instead infer rewards or rankings from comparisons [20 ] . Our problem is neither concept learning in the usual sense nor online preference optimization. Each agent has a hidden halfspace of the simplex, but the output is a single lottery that is evaluated on all agents, not a classifier that predicts future labels. This matters for the deterministic lower bound: repeated queries to the same agents may reveal their halfspaces, but they give no information about unqueried agents.
Statistical learning, convex penalties, and chance constraints. The sampling results can be viewed as a generalization problem: each lottery x x x defines a binary loss on agents, equal to 1 if the agent rejects x x x and 0 otherwise. The linear acceptability assumption then plays the role of a linear threshold hypothesis class in supervised learning: it limits the possible rejection sets enough for uniform convergence from finitely many sampled agents, without claiming that every acceptability rule is linear [72 , 11 , 67 ] . The LP replaces the discontinuous violation indicator with a one-sided penalty that is an upper bound on it. Convex upper bounds on discontinuous binary losses are classical [19 ] , and our analysis uses the behavior of Rademacher complexity under convex hulls and Lipschitz maps [18 ] . What is specific to lotteries is that the penalty controls the true violation count through the set B η ( x ) B_{\eta}(x) B η ( x ) of accepted agents with small margin. Chance-constrained and scenario optimization seek decisions that violate a random constraint with small probability [28 , 29 , 53 , 63 ] . Our population is finite and accessed through queries rather than given by a distribution, and our deterministic results show that, without a sampling assumption, worst-case guarantees depend only on the number of distinct agents queried.
Learning-augmented algorithms. Theorem 6.1 shows that, without random sampling, nothing can be guaranteed for the agents who are not asked. Learning-augmented algorithms circumvent worst-case limits of this kind in a different way: they receive predictions that may be erroneous, and aim for guarantees that improve with the accuracy of the predictions while remaining reasonable when the predictions are poor [54 , 64 , 58 ] . This approach has been applied to mechanism design [74 , 15 , 3 ] , online fair division [Banerjee et al., 2022, 2023, Choo et al., 2026a, Cohen et al., 2026, Huang and Teh, 2026, Neoh et al., 2026a, Neoh and Teh, 2026a,b, Teh et al., 2026], and voting [21 ] . In particular, Choo et al. [ [33 ] used advice, such as a promising lottery or the agents whose requirements are likely to be binding, to find a unanimously acceptable lottery with fewer queries. Our guarantees rely on random sampling rather than on predictions, and combining the two is an interesting direction for future work.
Omitted Material from Section 2
On the linear acceptability assumption
Formally, the model assumes that each agent’s acceptable set is a halfspace of the simplex: A i = { x ∈ Δ ( S ) : ⟨ u i , x ⟩ ≥ τ i } A_i = \{x \in\Delta(S) : \langle u_i, x\rangle\ge\tau_i\} A i = { x ∈ Δ ( S ) : ⟨ u i , x ⟩ ≥ τ i } . This is an assumption about the shape of the hidden acceptable sets, not an assumption that agents report numerical utilities. The decision maker observes neither u i u_i u i nor τ i \tau_i τ i ; it only observes whether proposed lotteries are acceptable. Our information model is therefore weaker than elicitation models that query utility values, comparisons, bounds, or regret-relevant parameters [24 , 26 ] .
Risk attitudes. The assumption does not require risk neutrality over final outcomes. Suppose alternative s j s_j s j induces, for agent i i i , a distribution P i j P_{ij} P ij over consequences, and the agent evaluates consequences with a von Neumann–Morgenstern utility function v i v_i v i [73 , 40 ] . Under the standard expected utility treatment of compound lotteries [10 ] , if the decision maker first draws j ∼ x j \sim x j ∼ x and then deploys s j s_j s j , the agent’s expected utility is ∑ j = 1 m x j E c ∼ P i j [ v i ( c ) ] \sum_{j=1}^{m} x_j \mathbb{E}_{c\sim P_{ij}}[v_i(c)] ∑ j = 1 m x j E c ∼ P ij [ v i ( c )] , so the expected consequence utilities, normalized as in Section 2, give exactly U i ( x ) = ⟨ u i , x ⟩ U_i(x) = \langle u_i, x\rangle U i ( x ) = ⟨ u i , x ⟩ . Risk attitudes over consequences are part of v i v_i v i ; for example, if consequences are monetary, a concave v i v_i v i represents risk aversion. The linearity is only in the decision maker’s random choice among finitely many alternatives.
Scores. In many platform, allocation, and public policy settings, the alternatives are deterministic rules, and the lottery describes randomized deployment across cohorts, applicants, time periods, or cases. If agent i i i ’s requirement concerns an average quantity, oriented so that larger is better, such as expected access probability, service level, safety, compliance, or the negative of an expected loss, then the value of a mixture is exactly the convex combination of the values of its components. Here u i ( s j ) u_i(s_j) u i ( s j ) is not a psychological utility but a score of alternative s j s_j s j , and τ i \tau_i τ i is the minimum acceptable score. For example, if u i ( s j ) = 1 u_i(s_j) = 1 u i ( s j ) = 1 for safe alternatives and 0 0 0 for unsafe ones, the requirement that an unsafe alternative is chosen with probability at most 1 / 10 1/10 1/10 is ⟨ u i , x ⟩ ≥ 9 / 10 \langle u_i, x\rangle\ge9/10 ⟨ u i , x ⟩ ≥ 9/10 . This expected score model is the standard cardinal baseline for evaluating lotteries in random assignment and probabilistic social choice [49 , 25 ] , although that literature also studies ordinal preferences and other ways of comparing lotteries.
A learning-theoretic view. Each lottery x x x defines a rejection region { ( u , τ ) : ⟨ u , x ⟩ < τ } \{(u,\tau) : \langle u,x\rangle< \tau\} {( u , τ ) : ⟨ u , x ⟩ < τ } in the space of agent types. These regions form a finite-dimensional family of linear threshold regions, analogous to linear classifiers in statistical learning [72 , 11 , 67 ] , which is what makes uniform convergence from sampled agents possible. Richer acceptability models give different families of regions and require different sample complexity, query complexity, and optimization analyses.
Scope. The model does not capture agents whose acceptability depends on variance, nonlinear probability weighting, ambiguity about the randomization, regret, or other departures from expected utility [56 , 50 , 65 , 55 , 43 ] , nor requirements on the distribution of realized outcomes that cannot be written as a linear threshold. For example, an agent who trades off the mean and variance of realized outcomes generally has a nonlinear acceptable set. Section 8 explains which of our results extend beyond halfspaces. The linear model is nevertheless not trivial: by Theorem 3.1 , minimizing violations is APX-hard even with full information and binary utilities, so the difficulty does not come from complicated utilities or nonlinear behavior.
Normalization and finite precision
As noted in Section 2, membership queries identify an acceptable set A i A_i A i , not a pair ( u i , τ i ) (u_i,\tau_i) ( u i , τ i ) , so margins U i ( x ) − τ i U_i(x)-\tau_i U i ( x ) − τ i are meaningful only after fixing a normalization. The normalization of Section 2 is justified by the following elementary fact.
Lemma B.1. Let A ⊊ Δ ( S ) A\subsetneq\Delta(S) A ⊊ Δ ( S ) be nonempty and suppose A = { x ∈ Δ ( S ) : ⟨ v , x ⟩ ≥ θ } A=\{x\in\Delta(S):\langle v,x\rangle\ge\theta\} A = { x ∈ Δ ( S ) : ⟨ v , x ⟩ ≥ θ } for some nonconstant v ∈ [ 0 , 1 ] m v\in[0,1]^m v ∈ [ 0 , 1 ] m and some θ ∈ R \theta\in\mathbb{R} θ ∈ R . Then exactly one of the following holds.
(i) A A A has nonempty relative interior in Δ ( S ) \Delta(S) Δ ( S ) . In this case there is a unique pair ( u , τ ) (u,\tau) ( u , τ ) with A = { x ∈ Δ ( S ) : ⟨ u , x ⟩ ≥ τ } A=\{x\in\Delta(S):\langle u,x\rangle\ge\tau\} A = { x ∈ Δ ( S ) : ⟨ u , x ⟩ ≥ τ } , min j ∈ [ m ] u ( s j ) = 0 \min_{j\in[m]}u(s_j)=0 min j ∈ [ m ] u ( s j ) = 0 , and max j ∈ [ m ] u ( s j ) = 1 \max_{j\in[m]}u(s_j)=1 max j ∈ [ m ] u ( s j ) = 1 .
(ii) A A A has empty relative interior in Δ ( S ) \Delta(S) Δ ( S ) . In this case A = Δ ( T ) : = { x ∈ Δ ( S ) : x j = 0 for all j ∉ T } A=\Delta(T):=\{x\in\Delta(S):x_j=0\text{ for all }j\notin T\} A = Δ ( T ) := { x ∈ Δ ( S ) : x j = 0 for all j ∈ / T } for a unique nonempty proper subset T ⊊ [ m ] T\subsetneq[m] T ⊊ [ m ] , and A A A is also given by u ( s j ) = 1 { j ∈ T } u(s_j)=1\{j\in T\} u ( s j ) = 1 { j ∈ T } and τ = 1 \tau=1 τ = 1 .
In both cases, the normalized pair gives exactly the same accept/reject answers as the original pair.
Proof. Let v min : = min j v ( s j ) v_{\min}:=\min_j v(s_j) v m i n := min j v ( s j ) and v max : = max j v ( s j ) v_{\max}:=\max_j v(s_j) v m a x := max j v ( s j ) . Since A A A is nonempty and not all of Δ ( S ) \Delta(S) Δ ( S ) , we have v min < θ ≤ v max v_{\min}<\theta\le v_{\max} v m i n < θ ≤ v m a x .
If θ = v max \theta=v_{\max} θ = v m a x , then a lottery is accepted if and only if it puts all probability on alternatives attaining the maximum score, so A = Δ ( T ) A=\Delta(T) A = Δ ( T ) with T : = { j ∈ [ m ] : v ( s j ) = v max } T:=\{j\in[m]:v(s_j)=v_{\max}\} T := { j ∈ [ m ] : v ( s j ) = v m a x } . Since v v v is nonconstant, T T T is a nonempty proper subset of [ m ] [m] [ m ] , so A A A has empty relative interior. Moreover, T T T is determined by A A A , as it is the set of j j j with e j ∈ A e_j\in A e j ∈ A , and the indicator pair in (ii) gives exactly the set A A A .
Suppose now that θ < v max \theta<v_{\max} θ < v m a x . Then A A A contains all lotteries close enough to a pure lottery e j e_j e j with v ( s j ) = v max v(s_j)=v_{\max} v ( s j ) = v m a x , so it has nonempty relative interior. Let ( u ′ , τ ′ ) (u',\tau') ( u ′ , τ ′ ) be any pair with A = { x ∈ Δ ( S ) : ⟨ u ′ , x ⟩ ≥ τ ′ } A=\{x\in\Delta(S):\langle u',x\rangle\ge\tau'\} A = { x ∈ Δ ( S ) : ⟨ u ′ , x ⟩ ≥ τ ′ } , and consider the affine functions f ( x ) : = ⟨ v , x ⟩ − θ f(x):=\langle v,x\rangle-\theta f ( x ) := ⟨ v , x ⟩ − θ and f ′ ( x ) : = ⟨ u ′ , x ⟩ − τ ′ f'(x):=\langle u',x\rangle-\tau' f ′ ( x ) := ⟨ u ′ , x ⟩ − τ ′ on the affine hull of Δ ( S ) \Delta(S) Δ ( S ) . Since f f f is positive near a pure lottery e j e_j e j with v ( s j ) = v max v(s_j)=v_{\max} v ( s j ) = v m a x and negative near one with v ( s j ) = v min v(s_j)=v_{\min} v ( s j ) = v m i n , it vanishes at some point p p p in the relative interior of Δ ( S ) \Delta(S) Δ ( S ) . Near p p p , both { f ≥ 0 } \{f\ge0\} { f ≥ 0 } and { f ′ ≥ 0 } \{f'\ge0\} { f ′ ≥ 0 } coincide with A A A ; hence f ′ f' f ′ is not constant, the zero sets of f f f and f ′ f' f ′ agree near p p p and therefore coincide, and both functions are nonnegative on the same side. Thus f ′ = λ f f'=\lambda f f ′ = λ f on the affine hull for some λ > 0 \lambda>0 λ > 0 , and since ⟨ 1 , x ⟩ = 1 \langle\mathbf{1},x\rangle=1 ⟨ 1 , x ⟩ = 1 there, we have u ′ = λ v + μ 1 u'=\lambda v+\mu\mathbf{1} u ′ = λ v + μ 1 and τ ′ = λ θ + μ \tau'=\lambda\theta+\mu τ ′ = λ θ + μ for some μ ∈ R \mu\in\mathbb{R} μ ∈ R . The conditions min j u ′ ( s j ) = 0 \min_j u'(s_j)=0 min j u ′ ( s j ) = 0 and max j u ′ ( s j ) = 1 \max_j u'(s_j)=1 max j u ′ ( s j ) = 1 hold exactly when λ = 1 / ( v max − v min ) \lambda=1/(v_{\max}-v_{\min}) λ = 1/ ( v m a x − v m i n ) and μ = − λ v min \mu=-\lambda v_{\min} μ = − λ v m i n and hold exactly when λ = 1 / ( v max − v min ) \lambda=1/(v_{\max}-v_{\min}) λ = 1/ ( v m a x − v m i n ) and μ = − λ v min \mu=-\lambda v_{\min} μ = − λ v m i n ; and conversely, with these values, the pair ( λ v + μ 1 , λ θ + μ ) (\lambda v+\mu\mathbf{1},\lambda\theta+\mu) ( λ v + μ 1 , λ θ + μ ) gives A A A and satisfies both conditions. Hence the normalized pair exists and is unique.
The finite-grid convention of Section 2 is used only for explicit query budgets and running times; the geometric, statistical, and lower-bound results hold for arbitrary real-valued normalized pairs unless they explicitly invoke it. There are two reasons to make it explicit. First, exact recovery of real-valued coefficients from finitely many binary answers is impossible without a finite description or a tolerance. This already happens when m = 2 m=2 m = 2 : if an agent accepts λ e 1 + ( 1 − λ ) e 2 \lambda e_1+(1-\lambda)e_2 λ e 1 + ( 1 − λ ) e 2 if and only if λ ≥ a \lambda\ge a λ ≥ a , a query at λ \lambda λ returns only whether λ ≥ a \lambda\ge a λ ≥ a . There are only countably many finite binary answer sequences, while a a a ranges over a continuum. Second, the grid gives every recovered pair a finite description, so the algorithms that use recovered agents have well-defined running times. We use the per-agent bound T ε = O ( m log ( 1 / ε ) ) T_\varepsilon=\mathcal{O}(m\log(1/\varepsilon)) T ε = O ( m log ( 1/ ε )) of Choo et al. [2026b] as a black box. The convention does not discretize the lottery: the output may be any point of Δ ( S ) \Delta(S) Δ ( S ) .
Proof of Theorem 3.1
We give a polynomial-time approximation-preserving reduction from MINIMUM VERTEX COVER on cubic graphs, which is APX-hard [5 ] . The idea is that vertex agents ask for probability at least 1 / q 1/q 1/ q on their vertex, while many copies of each edge agent forbid this much probability on both endpoints of an edge; the vertices that do not receive probability 1 / q 1/q 1/ q then form a vertex cover.
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a cubic graph with vertices V = { v 1 , … , v q } V=\{v_1,\ldots,v_q\} V = { v 1 , … , v q } . Set m : = q + 1 m:=q+1 m := q + 1 , where s j s_j s j corresponds to v j v_j v j for j ∈ [ q ] j\in[q] j ∈ [ q ] and s m s_m s m is an extra alternative. Create q q q vertex agents a 1 , … , a q a_1,\ldots,a_q a 1 , … , a q and, for each edge e ∈ E e \in E e ∈ E , q 2 q^2 q 2 copies b e , 1 , … , b e , q 2 b_{e,1},\ldots,b_{e,q^2} b e , 1 , … , b e , q 2 of an edge agent. Then n = q + q 2 ∣ E ∣ = O ( q 3 ) n=q+q^2|E|=O(q^3) n = q + q 2 ∣ E ∣ = O ( q 3 ) , since ∣ E ∣ = 3 q / 2 |E|=3q/2 ∣ E ∣ = 3 q /2 . The utilities and thresholds are as follows.
For each j ∈ [ q ] j \in[q] j ∈ [ q ] , the vertex agent a j a_j a j has threshold 1 / q 1/q 1/ q , utility 1 1 1 on s j s_j s j , and utility 0 0 0 on every other alternative. Thus U a j ( x ) = x j U_{a_j}(\mathbf{x})=x_j U a j ( x ) = x j , and a j a_j a j accepts x \mathbf{x} x if and only if x j ≥ 1 / q x_j \ge1/q x j ≥ 1/ q .
For each edge e = { v j , v j ′ } ∈ E e=\{v_j,v_{j'}\}\in E e = { v j , v j ′ } ∈ E , every copy b e , r b_{e,r} b e , r has threshold 1 − 1 / q 1-1/q 1 − 1/ q , utility 0 0 0 on s j s_j s j and s j ′ s_{j'} s j ′ , and utility 1 1 1 on every other alternative. Thus U b e , r ( x ) = 1 − x j − x j ′ U_{b_{e,r}}(\mathbf{x})=1-x_j-x_{j'} U b e , r ( x ) = 1 − x j − x j ′ , and b e , r b_{e,r} b e , r accepts x \mathbf{x} x if and only if x j + x j ′ ≤ 1 / q x_j+x_{j'}\le1/q x j + x j ′ ≤ 1/ q .
Every utility vector lies in { 0 , 1 } m \{0,1\}^m { 0 , 1 } m and takes both values 0 0 0 and 1 1 1 , and every threshold lies in ( 0 , 1 ) (0,1) ( 0 , 1 ) (a cubic graph has q ≥ 4 q\ge4 q ≥ 4 vertices), so all pairs are normalized. Every agent is nondegenerate: a j a_j a j accepts e j \mathbf{e}_j e j and rejects e m \mathbf{e}_m e m , while each edge agent of e e e accepts e m \mathbf{e}_m e m and rejects the pure lotteries on the endpoints of e e e . Let vc ( G ) \operatorname{vc}(G) vc ( G ) be the minimum size of a vertex cover of G G G . We show that OPT = vc ( G ) \operatorname{OPT}=\operatorname{vc}(G) OPT = vc ( G ) for the constructed instance and that every lottery can be turned into a vertex cover of size at most its violation count.
OPT ≤ vc ( G ) \operatorname{OPT}\le\operatorname{vc}(G) OPT ≤ vc ( G ) . Let C ⊆ V C\subseteq V C ⊆ V be a vertex cover, and define x C ∈ Δ ( S ) \mathbf{x}^C\in\Delta(S) x C ∈ Δ ( S ) by x j C = 1 / q x_j^C=1/q x j C = 1/ q if v j ∉ C v_j\notin C v j ∈ / C , x j C = 0 x_j^C=0 x j C = 0 if v j ∈ C v_j\in C v j ∈ C , and x m C : = 1 − ( q − ∣ C ∣ ) / q = ∣ C ∣ / q x_m^C:=1-(q-|C|)/q=|C|/q x m C := 1 − ( q − ∣ C ∣ ) / q = ∣ C ∣/ q . For every edge, at most one endpoint lies outside C C C , so the probabilities of its endpoints sum to at most 1 / q 1/q 1/ q and all its edge agents accept x C \mathbf{x}^C x C . The vertex agent a j a_j a j accepts x C \mathbf{x}^C x C if and only if v j ∉ C v_j\notin C v j ∈ / C . Therefore viol ( x C ) = ∣ C ∣ \operatorname{viol}(\mathbf{x}^C)=|C| viol ( x C ) = ∣ C ∣ , and minimizing over C C C gives OPT ≤ vc ( G ) \operatorname{OPT}\le\operatorname{vc}(G) OPT ≤ vc ( G ) .
From lotteries to vertex covers. Given a lottery x \mathbf{x} x , let C ( x ) : = V C(\mathbf{x}):=V C ( x ) := V if x j + x j ′ > 1 / q x_j+x_{j'}>1/q x j + x j ′ > 1/ q for some edge { v j , v j ′ } ∈ E \{v_j,v_{j'}\}\in E { v j , v j ′ } ∈ E , and C ( x ) : = { v j ∈ V : x j < 1 / q } C(\mathbf{x}):=\{v_j\in V:x_j<1/q\} C ( x ) := { v j ∈ V : x j < 1/ q } otherwise; C ( x ) C(\mathbf{x}) C ( x ) can be computed in polynomial time. In the first case, x \mathbf{x} x violates all q 2 q^2 q 2 copies of some edge agent, so ∣ C ( x ) ∣ = q ≤ q 2 ≤ viol ( x ) |C(\mathbf{x})|=q\le q^2\le\operatorname{viol}(\mathbf{x}) ∣ C ( x ) ∣ = q ≤ q 2 ≤ viol ( x ) , and C ( x ) = V C(\mathbf{x})=V C ( x ) = V is a vertex cover. In the second case, no edge has both endpoints with probability at least 1 / q 1/q 1/ q , since that would give x j + x j ′ ≥ 2 / q x_j+x_{j'}\ge2/q x j + x j ′ ≥ 2/ q . Hence C ( x ) C(\mathbf{x}) C ( x ) is a vertex cover. No edge agent is violated, and the violated vertex agents are exactly those of the vertices in C ( x ) C(\mathbf{x}) C ( x ) , so ∣ C ( x ) ∣ = viol ( x ) |C(\mathbf{x})|=\operatorname{viol}(\mathbf{x}) ∣ C ( x ) ∣ = viol ( x ) . In both cases, C ( x ) C(\mathbf{x}) C ( x ) is a vertex cover with ∣ C ( x ) ∣ ≤ viol ( x ) |C(\mathbf{x})|\le\operatorname{viol}(\mathbf{x}) ∣ C ( x ) ∣ ≤ viol ( x ) . In particular, vc ( G ) ≤ OPT \operatorname{vc}(G)\le\operatorname{OPT} vc ( G ) ≤ OPT , so OPT = vc ( G ) \operatorname{OPT}=\operatorname{vc}(G) OPT = vc ( G ) .
Approximation preservation. If x \mathbf{x} x is an α \alpha α -approximate solution of the constructed instance, then ∣ C ( x ) ∣ ≤ viol ( x ) ≤ α ⋅ OPT = α ⋅ vc ( G ) |C(\mathbf{x})|\le\operatorname{viol}(\mathbf{x})\le\alpha\cdot\operatorname{OPT}=\alpha\cdot\operatorname{vc}(G) ∣ C ( x ) ∣ ≤ viol ( x ) ≤ α ⋅ OPT = α ⋅ vc ( G ) , so C ( x ) C(\mathbf{x}) C ( x ) is an α \alpha α -approximate vertex cover of G G G . Hence a PTAS for MIN-VIOL would give a PTAS for MINIMUM VERTEX COVER on cubic graphs, which does not exist unless P = N P \mathrm{P}=\mathrm{NP} P = NP . Therefore MIN-VIOL is APX-hard, even with binary utilities.
Omitted Proofs from Section 4
Proof of Theorem 4.1
The idea is that some optimal lottery is a vertex of the polytope of lotteries accepted by the agents that it satisfies, and every such vertex is the unique solution of a system of m m m linear equations; enumerating these systems therefore finds an optimal lottery. For any N ′ ⊆ N N'\subseteq N N ′ ⊆ N , let P ( N ′ ) : = { x ∈ Δ ( S ) : ⟨ u i , x ⟩ ≥ τ i for all i ∈ N ′ } = ⋂ i ∈ N ′ A i P(N'):=\{\mathbf{x}\in\Delta(S):\langle\mathbf{u}_i,\mathbf{x}\rangle\ge\tau_i\text{ for all }i\in N'\}=\bigcap_{i\in N'}A_i P ( N ′ ) := { x ∈ Δ ( S ) : ⟨ u i , x ⟩ ≥ τ i for all i ∈ N ′ } = ⋂ i ∈ N ′ A i , with the convention P ( ∅ ) = Δ ( S ) P(\varnothing)=\Delta(S) P ( ∅ ) = Δ ( S ) . We first prove two lemmas.
Lemma D.1. Let x ∗ ∈ arg min x ∈ Δ ( S ) viol ( x ) \mathbf{x}^*\in\arg\min_{\mathbf{x}\in\Delta(S)}\operatorname{viol}(\mathbf{x}) x ∗ ∈ arg min x ∈ Δ ( S ) viol ( x ) and N ∗ : = { i ∈ N : x ∗ ∈ A i } N^*:=\{i\in N:\mathbf{x}^*\in A_i\} N ∗ := { i ∈ N : x ∗ ∈ A i } . Then there exists an extreme point x ˉ \bar{\mathbf{x}} x ˉ of P ( N ∗ ) P(N^*) P ( N ∗ ) such that viol ( x ˉ ) = viol ( x ∗ ) \operatorname{viol}(\bar{\mathbf{x}})=\operatorname{viol}(\mathbf{x}^*) viol ( x ˉ ) = viol ( x ∗ ) .
Proof. Since x ∗ ∈ P ( N ∗ ) \mathbf{x}^*\in P(N^*) x ∗ ∈ P ( N ∗ ) , the set P ( N ∗ ) P(N^*) P ( N ∗ ) is nonempty. By the definition of A i A_i A i , P ( N ∗ ) = Δ ( S ) ∩ ⋂ i ∈ N ∗ { x ∈ R m : ⟨ u i , x ⟩ ≥ τ i } P(N^*)=\Delta(S)\cap\bigcap_{i\in N^*}\{\mathbf{x}\in\mathbb{R}^m:\langle\mathbf{u}_i,\mathbf{x}\rangle\ge\tau_i\} P ( N ∗ ) = Δ ( S ) ∩ ⋂ i ∈ N ∗ { x ∈ R m : ⟨ u i , x ⟩ ≥ τ i } , so P ( N ∗ ) P(N^*) P ( N ∗ ) is a compact polytope. Thus, P ( N ∗ ) P(N^*) P ( N ∗ ) has at least one extreme point; fix any extreme point x ˉ ∈ P ( N ∗ ) \bar{\mathbf{x}}\in P(N^*) x ˉ ∈ P ( N ∗ ) . By definition of P ( N ∗ ) P(N^*) P ( N ∗ ) , we have ⟨ u i , x ˉ ⟩ ≥ τ i \langle\mathbf{u}_i,\bar{\mathbf{x}}\rangle\ge\tau_i ⟨ u i , x ˉ ⟩ ≥ τ i for every i ∈ N ∗ i\in N^* i ∈ N ∗ , so x ˉ \bar{\mathbf{x}} x ˉ violates at most the agents in N ∖ N ∗ N\setminus N^* N ∖ N ∗ . Therefore, viol ( x ˉ ) ≤ ∣ N ∖ N ∗ ∣ = viol ( x ∗ ) \operatorname{viol}(\bar{\mathbf{x}})\le|N\setminus N^*|=\operatorname{viol}(\mathbf{x}^*) viol ( x ˉ ) ≤ ∣ N ∖ N ∗ ∣ = viol ( x ∗ ) . Since x ∗ \mathbf{x}^* x ∗ is optimal, equality must hold and x ˉ \bar{\mathbf{x}} x ˉ is also optimal. □ \square □
Lemma D.2. Let N ′ ⊆ N N'\subseteq N N ′ ⊆ N and let x \mathbf{x} x be an extreme point of P ( N ′ ) P(N') P ( N ′ ) . Then there exist subsets J ⊆ [ m ] J\subseteq[m] J ⊆ [ m ] and N 0 ′ ⊆ N ′ N'_0\subseteq N' N 0 ′ ⊆ N ′ with ∣ J ∣ + ∣ N 0 ′ ∣ = m − 1 |J|+|N'_0|=m-1 ∣ J ∣ + ∣ N 0 ′ ∣ = m − 1 such that x \mathbf{x} x is the unique solution to the linear system ∑ j = 1 m z j = 1 \sum_{j=1}^{m}z_j=1 ∑ j = 1 m z j = 1 , z j = 0 z_j=0 z j = 0 for all j ∈ J j\in J j ∈ J , and ⟨ u i , z ⟩ = τ i \langle\mathbf{u}_i,\mathbf{z}\rangle=\tau_i ⟨ u i , z ⟩ = τ i for all i ∈ N 0 ′ i\in N'_0 i ∈ N 0 ′ .
Algorithm 1 Returns a lottery with the minimum number of violations.
Input: The normalized pairs $(u_i,\tau_i)_{i\in N}$.
Output: A lottery $\hat{x}$ minimizing viol.
1: $\hat{x}\leftarrow e_1$
2: for each pair $(J,N_0)$ with $J\subseteq [m]$, $N_0\subseteq N$, and $|J|+|N_0|=m-1$ do
3: if $\mathcal{L}(J,N_0)$ has a unique solution $x$, $x\in\Delta(S)$, and $\operatorname{viol}(x)<\operatorname{viol}(\hat{x})$ then
4: $\hat{x}\leftarrow x$
5: end if
6: end for
7: return $\hat{x}$
Proof. Let L : = { d ∈ R m : ∑ j = 1 m d j = 0 } L:=\{d\in\mathbb{R}^{m}:\sum_{j=1}^{m}d_j=0\} L := { d ∈ R m : ∑ j = 1 m d j = 0 } be the translation space of the affine hull of Δ ( S ) \Delta(S) Δ ( S ) , where dim ( L ) = m − 1 \dim(L)=m-1 dim ( L ) = m − 1 .
Let T 0 : = { j ∈ [ m ] : x j = 0 } T_0:=\{j\in[m]:x_j=0\} T 0 := { j ∈ [ m ] : x j = 0 } and T 1 : = { i ∈ N ′ : ⟨ u i , x ⟩ = τ i } T_1:=\{i\in N':\langle u_i,x\rangle=\tau_i\} T 1 := { i ∈ N ′ : ⟨ u i , x ⟩ = τ i } be the sets of tight nonnegativity constraints and tight agent constraints at x x x , respectively. Consider the family F : = { d ↦ d j : j ∈ T 0 } ∪ { d ↦ ⟨ u i , d ⟩ : i ∈ T 1 } \mathcal{F}:=\{d\mapsto d_j:j\in T_0\}\cup\{d\mapsto\langle u_i,d\rangle:i\in T_1\} F := { d ↦ d j : j ∈ T 0 } ∪ { d ↦ ⟨ u i , d ⟩ : i ∈ T 1 } of linear functionals on L L L .
We claim that F \mathcal{F} F spans L ∗ L^* L ∗ . Indeed, suppose not. Then there exists a nonzero d ∈ L d\in L d ∈ L such that d j = 0 d_j=0 d j = 0 for all j ∈ T 0 j\in T_0 j ∈ T 0 and ⟨ u i , d ⟩ = 0 \langle u_i,d\rangle=0 ⟨ u i , d ⟩ = 0 for all i ∈ T 1 i\in T_1 i ∈ T 1 .
For each j ∉ T 0 j\notin T_0 j ∈ / T 0 , we have x j > 0 x_j>0 x j > 0 ; and for each i ∈ N ′ ∖ T 1 i\in N'\setminus T_1 i ∈ N ′ ∖ T 1 , we have ⟨ u i , x ⟩ > τ i \langle u_i,x\rangle>\tau_i ⟨ u i , x ⟩ > τ i . Since there are only finitely many such indices, there exists α 0 > 0 \alpha_0>0 α 0 > 0 such that, for every ∣ α ∣ ≤ α 0 |\alpha|\leq\alpha_0 ∣ α ∣ ≤ α 0 , we have x j + α d j ≥ 0 x_j+\alpha d_j\geq0 x j + α d j ≥ 0 for all j ∉ T 0 j\notin T_0 j ∈ / T 0 and ⟨ u i , x + α d ⟩ ≥ τ i \langle u_i,x+\alpha d\rangle\geq\tau_i ⟨ u i , x + α d ⟩ ≥ τ i for all i ∈ N ′ ∖ T 1 i\in N'\setminus T_1 i ∈ N ′ ∖ T 1 . For j ∈ T 0 j\in T_0 j ∈ T 0 , we have x j + α d j = 0 x_j+\alpha d_j=0 x j + α d j = 0 . For i ∈ T 1 i\in T_1 i ∈ T 1 , we have ⟨ u i , x + α d ⟩ = ⟨ u i , x ⟩ + α ⟨ u i , d ⟩ = τ i \langle u_i,x+\alpha d\rangle=\langle u_i,x\rangle+\alpha\langle u_i,d\rangle=\tau_i ⟨ u i , x + α d ⟩ = ⟨ u i , x ⟩ + α ⟨ u i , d ⟩ = τ i . Also, ∑ j = 1 m ( x j + α d j ) = 1 \sum_{j=1}^{m}(x_j+\alpha d_j)=1 ∑ j = 1 m ( x j + α d j ) = 1 because d ∈ L d\in L d ∈ L . Thus, x + α d ∈ P ( N ′ ) x+\alpha d\in P(N') x + α d ∈ P ( N ′ ) for every ∣ α ∣ ≤ α 0 |\alpha|\leq\alpha_0 ∣ α ∣ ≤ α 0 . Since d ≠ 0 d\neq0 d = 0 , this gives us a nontrivial line segment in P ( N ′ ) P(N') P ( N ′ ) through x x x , contradicting the fact that x x x is an extreme point. Therefore F \mathcal{F} F spans L ∗ L^* L ∗ . Choose from F \mathcal{F} F a basis { d ↦ d j : j ∈ J } ∪ { d ↦ ⟨ u i , d ⟩ : i ∈ N 0 ′ } \{d\mapsto d_j:j\in J\}\cup\{d\mapsto\langle u_i,d\rangle:i\in N'_0\} { d ↦ d j : j ∈ J } ∪ { d ↦ ⟨ u i , d ⟩ : i ∈ N 0 ′ } of L ∗ L^* L ∗ , where J ⊆ T 0 J\subseteq T_0 J ⊆ T 0 , N 0 ′ ⊆ T 1 N'_0\subseteq T_1 N 0 ′ ⊆ T 1 , and ∣ J ∣ + ∣ N 0 ′ ∣ = m − 1 |J|+|N'_0|=m-1 ∣ J ∣ + ∣ N 0 ′ ∣ = m − 1 .
We now show that x x x is the unique solution to the system ∑ j = 1 m z j = 1 \sum_{j=1}^{m}z_j=1 ∑ j = 1 m z j = 1 , z j = 0 z_j=0 z j = 0 for all j ∈ J j\in J j ∈ J , and ⟨ u i , z ⟩ = τ i \langle u_i,z\rangle=\tau_i ⟨ u i , z ⟩ = τ i for all i ∈ N 0 ′ i\in N'_0 i ∈ N 0 ′ . Clearly x x x satisfies this system. Conversely, if z z z is any solution, then d : = z − x ∈ L d:=z-x\in L d := z − x ∈ L , d j = 0 d_j=0 d j = 0 for all j ∈ J j\in J j ∈ J , and ⟨ u i , d ⟩ = 0 \langle u_i,d\rangle=0 ⟨ u i , d ⟩ = 0 for all i ∈ N 0 ′ i\in N'_0 i ∈ N 0 ′ . Since the chosen functionals form a basis of L ∗ L^* L ∗ , this forces d = 0 d=0 d = 0 , and thus z = x z=x z = x . Therefore, x x x is the unique solution.
Now, for each pair ( J , N 0 ) (J,N_0) ( J , N 0 ) with J ⊆ [ m ] J\subseteq[m] J ⊆ [ m ] , N 0 ⊆ N N_0\subseteq N N 0 ⊆ N , and ∣ J ∣ + ∣ N 0 ∣ = m − 1 |J|+|N_0|=m-1 ∣ J ∣ + ∣ N 0 ∣ = m − 1 , let L ( J , N 0 ) \mathcal{L}(J,N_0) L ( J , N 0 ) denote the linear system ∑ j = 1 m x j = 1 \sum_{j=1}^{m}x_j=1 ∑ j = 1 m x j = 1 , x j = 0 x_j=0 x j = 0 for all j ∈ J j\in J j ∈ J , and ⟨ u i , x ⟩ = τ i \langle u_i,x\rangle=\tau_i ⟨ u i , x ⟩ = τ i for all i ∈ N 0 i\in N_0 i ∈ N 0 . Lemma D.2 shows that every extreme point of every polytope P ( N ′ ) P(N') P ( N ′ ) is the unique solution of L ( J , N 0 ) \mathcal{L}(J,N_0) L ( J , N 0 ) for some such pair ( J , N 0 ) (J,N_0) ( J , N 0 ) . This motivates the following algorithm (Algorithm 1).
We first prove correctness. Let x ∗ x^* x ∗ be an optimal lottery and N ∗ : = { i ∈ N : x ∗ ∈ A i } N^*:=\{i\in N:x^*\in A_i\} N ∗ := { i ∈ N : x ∗ ∈ A i } . By Lemma D.1, some extreme point x ˉ \bar{x} x ˉ of P ( N ∗ ) P(N^*) P ( N ∗ ) is also optimal, and by Lemma D.2, x ˉ \bar{x} x ˉ is the unique solution of L ( J , N 0 ) \mathcal{L}(J,N_0) L ( J , N 0 ) for some J ⊆ [ m ] J\subseteq[m] J ⊆ [ m ] and N 0 ⊆ N ∗ N_0\subseteq N^* N 0 ⊆ N ∗ with ∣ J ∣ + ∣ N 0 ∣ = m − 1 |J|+|N_0|=m-1 ∣ J ∣ + ∣ N 0 ∣ = m − 1 . When Algorithm 1 considers this pair, it finds x ˉ ∈ Δ ( S ) \bar{x}\in\Delta(S) x ˉ ∈ Δ ( S ) , so the returned lottery satisfies viol ( x ^ ) ≤ viol ( x ˉ ) = O P T \operatorname{viol}(\hat{x})\leq\operatorname{viol}(\bar{x})=\mathrm{OPT} viol ( x ^ ) ≤ viol ( x ˉ ) = OPT ; that is, it is optimal.
Next, we prove the running time of Algorithm 1. For each t ∈ { 0 , … , m − 1 } t\in\{0,\ldots,m-1\} t ∈ { 0 , … , m − 1 } , the number of pairs ( J , N 0 ) (J,N_0) ( J , N 0 ) with ∣ N 0 ∣ = t |N_0|=t ∣ N 0 ∣ = t and ∣ J ∣ = m − 1 − t |J|=m-1-t ∣ J ∣ = m − 1 − t is ( n t ) ( m m − 1 − t ) \binom{n}{t}\binom{m}{m-1-t} ( t n ) ( m − 1 − t m ) , so, by Vandermonde’s identity, the total number of pairs is ∑ t = 0 m − 1 ( n t ) ( m m − 1 − t ) = ( n + m m − 1 ) \sum_{t=0}^{m-1}\binom{n}{t}\binom{m}{m-1-t}=\binom{n+m}{m-1} ∑ t = 0 m − 1 ( t n ) ( m − 1 − t m ) = ( m − 1 n + m ) . For each pair, the system L ( J , N 0 ) \mathcal{L}(J,N_0) L ( J , N 0 ) has exactly m m m equations in m m m unknowns, so testing consistency and uniqueness and solving it can be done in O ( m 3 ) O(m^3) O ( m 3 ) time by Gaussian elimination. Evaluating viol ( x ) \operatorname{viol}(x) viol ( x ) requires computing ⟨ u i , x ⟩ \langle u_i,x\rangle ⟨ u i , x ⟩ for all i ∈ N i\in N i ∈ N , which takes O ( n m ) O(nm) O ( nm ) time. Thus, the total running time is O ( ( n + m m − 1 ) ( m 3 + n m ) ) O\left(\binom{n+m}{m-1}(m^3+nm)\right) O ( ( m − 1 n + m ) ( m 3 + nm ) ) .
Finally, the decision version (is OPT at most a given number?) is solved by running Algorithm 1 and comparing the violation count of the returned lottery with that number. Since ( n + m m − 1 ) ≤ ( n + m ) m − 1 \binom{n+m}{m-1}\leq(n+m)^{m-1} ( m − 1 n + m ) ≤ ( n + m ) m − 1 , the running time is polynomial for every constant m m m , and the decision problem is in XP when parameterized by m m m .
Proof of Theorem 4.2
The sampling step below is the argument of Castiglioni et al. [ [30 ] for their relaxation of MAX-FS over the simplex; we include it for completeness. Draw J 1 , … , J s η J_1,\ldots,J_{s_\eta} J 1 , … , J s η independently from x x x , i.e., Pr [ J t = j ] = x j \Pr[J_t=j]=x_j Pr [ J t = j ] = x j for all j ∈ [ m ] j\in[m] j ∈ [ m ] and t ∈ [ s η ] t\in[s_\eta] t ∈ [ s η ] , and let x ~ : = 1 s η ∑ t = 1 s η e J t \tilde{x}:=\frac{1}{s_\eta}\sum_{t=1}^{s_\eta}e_{J_t} x ~ := s η 1 ∑ t = 1 s η e J t be their empirical distribution. Then x ~ ∈ Δ ( S ) \tilde{x}\in\Delta(S) x ~ ∈ Δ ( S ) , and it uses at most s η s_\eta s η alternatives. For a fixed agent i i i , the values u i ( s J 1 ) , … , u i ( s J s η ) u_i(s_{J_1}),\ldots,u_i(s_{J_{s_\eta}}) u i ( s J 1 ) , … , u i ( s J s η ) are independent, lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and have mean ∑ j = 1 m x j u i ( s j ) = U i ( x ) \sum_{j=1}^{m}x_ju_i(s_j)=U_i(x) ∑ j = 1 m x j u i ( s j ) = U i ( x ) , and U i ( x ~ ) U_i(\tilde{x}) U i ( x ~ ) is their average. Hoeffding’s inequality gives Pr [ U i ( x ~ ) < U i ( x ) − η ] ≤ e − 2 s η η 2 \Pr[U_i(\tilde{x})<U_i(x)-\eta]\le e^{-2s_\eta\eta^2} Pr [ U i ( x ~ ) < U i ( x ) − η ] ≤ e − 2 s η η 2 . By a union bound and the definition of s η s_\eta s η , Pr [ ∃ i ∈ N : U i ( x ~ ) < U i ( x ) − η ] ≤ n e − 2 s η η 2 ≤ n e − log ( 2 n ) = 1 / 2 \Pr[\exists i\in N:U_i(\tilde{x})<U_i(x)-\eta]\le ne^{-2s_\eta\eta^2}\le ne^{-\log(2n)}=1/2 Pr [ ∃ i ∈ N : U i ( x ~ ) < U i ( x ) − η ] ≤ n e − 2 s η η 2 ≤ n e − l o g ( 2 n ) = 1/2 . Hence some realization of x ~ \tilde{x} x ~ satisfies U i ( x ~ ) ≥ U i ( x ) − η U_i(\tilde{x})\ge U_i(x)-\eta U i ( x ~ ) ≥ U i ( x ) − η for all i ∈ N i\in N i ∈ N ; fix it.
We now bound the number of violations of x ~ \tilde{x} x ~ . If agent i i i rejects x ~ \tilde{x} x ~ , then U i ( x ) < τ i + η U_i(x)<\tau_i+\eta U i ( x ) < τ i + η , since otherwise U i ( x ~ ) ≥ U i ( x ) − η ≥ τ i U_i(\tilde{x})\ge U_i(x)-\eta\ge\tau_i U i ( x ~ ) ≥ U i ( x ) − η ≥ τ i ; that is, agent i i i either rejects x x x or belongs to B η ( x ) B_\eta(x) B η ( x ) . Therefore viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ \operatorname{viol}(\tilde{x})\le\operatorname{viol}(x)+|B_\eta(x)| viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ . If x ∗ x^* x ∗ is optimal and B η ( x ∗ ) = ∅ B_\eta(x^*)=\varnothing B η ( x ∗ ) = ∅ , applying this with x = x ∗ x=x^* x = x ∗ gives viol ( x ~ ) ≤ OPT \operatorname{viol}(\tilde{x})\le\operatorname{OPT} viol ( x ~ ) ≤ OPT , so x ~ \tilde{x} x ~ is an optimal lottery that uses at most s η s_\eta s η alternatives.
Proof of Proposition 4.3
For T ⊆ [ m ] T\subseteq[m] T ⊆ [ m ] , recall from Lemma B.1 that Δ ( T ) \Delta(T) Δ ( T ) is the set of lotteries that use only alternatives in T T T . Every lottery that uses at most s s s alternatives lies in Δ ( T ) \Delta(T) Δ ( T ) for T = { j ∈ [ m ] : x j > 0 } T=\{j\in[m]:x_j>0\} T = { j ∈ [ m ] : x j > 0 } , so it suffices to minimize viol \operatorname{viol} viol over Δ ( T ) \Delta(T) Δ ( T ) for each T T T with 1 ≤ t : = ∣ T ∣ ≤ min { s , m } 1\le t:=|T|\le\min\{s,m\} 1 ≤ t := ∣ T ∣ ≤ min { s , m } and keep the best solution.
Fix such a set T T T . If t = 1 t=1 t = 1 , then Δ ( T ) \Delta(T) Δ ( T ) consists of a single pure lottery, whose violation count can be computed in O ( n ) O(n) O ( n ) time. Now suppose t ≥ 2 t\ge2 t ≥ 2 . On Δ ( T ) \Delta(T) Δ ( T ) , agent i i i accepts x x x if and only if ∑ j ∈ T u i ( s j ) x j ≥ τ i \sum_{j\in T}u_i(s_j)x_j\ge\tau_i ∑ j ∈ T u i ( s j ) x j ≥ τ i , so minimizing viol \operatorname{viol} viol over Δ ( T ) \Delta(T) Δ ( T ) is the same problem with the t t t alternatives in T T T . Some agents may accept or reject every lottery in Δ ( T ) \Delta(T) Δ ( T ) , but the proof of Theorem 4.1 uses only the simplex constraints, compactness, and the linear acceptance inequalities, so it applies with m m m replaced by t t t . Hence an optimizer over Δ ( T ) \Delta(T) Δ ( T ) can be computed in time O ( ( t t − 1 ) 3 + n t ) O\left(\binom{t}{t-1}^{3}+nt\right) O ( ( t − 1 t ) 3 + n t ) , which also covers the case t = 1 t=1 t = 1 . There are ( m t ) \binom{m}{t} ( t m ) sets T T T of size t t t , and for each t ≤ s t\le s t ≤ s we have ( m t ) ≤ m t \binom{m}{t}\le m^t ( t m ) ≤ m t , ( n + s t − 1 ) ≤ ( n + s ) t − 1 \binom{n+s}{t-1}\le(n+s)^{t-1} ( t − 1 n + s ) ≤ ( n + s ) t − 1 , and t 3 + n t ≤ 2 ( n + s ) 3 t^3+nt\le2(n+s)^3 t 3 + n t ≤ 2 ( n + s ) 3 ; hence all sets of size t t t together take time O ( m t ( n + s ) t + 2 ) O(m^t(n+s)^{t+2}) O ( m t ( n + s ) t + 2 ) . Summing over the at most s s s values of t t t gives total time O ( s m s ( n + s ) s + 2 ) O(s\,m^s(n+s)^{s+2}) O ( s m s ( n + s ) s + 2 ) , which is ( m ( n + s ) ) O ( s ) (m(n+s))^{O(s)} ( m ( n + s ) ) O ( s ) . The best lottery found over all such T T T minimizes viol \operatorname{viol} viol among all lotteries that use at most s s s alternatives.
Proof of Corollary 4.4
The running time is that of Proposition 4.3 with s = s η s=s_\eta s = s η . Let x ^ \hat{x} x ^ be the returned lottery and let x x x be any lottery. By Theorem 4.2, some lottery x ~ \tilde{x} x ~ that uses at most s η s_\eta s η alternatives satisfies viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ \operatorname{viol}(\tilde{x})\le\operatorname{viol}(x)+|B_\eta(x)| viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ . Since x ^ \hat{x} x ^ minimizes viol \operatorname{viol} viol among all such lotteries, viol ( x ^ ) ≤ viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ \operatorname{viol}(\hat{x})\le\operatorname{viol}(\tilde{x})\le\operatorname{viol}(x)+|B_\eta(x)| viol ( x ^ ) ≤ viol ( x ~ ) ≤ viol ( x ) + ∣ B η ( x ) ∣ . Taking x x x to be an optimal lottery x ∗ x^* x ∗ gives viol ( x ^ ) ≤ OPT + ∣ B η ( x ∗ ) ∣ \operatorname{viol}(\hat{x})\le\operatorname{OPT}+|B_\eta(x^*)| viol ( x ^ ) ≤ OPT + ∣ B η ( x ∗ ) ∣ , which equals OPT \operatorname{OPT} OPT if B η ( x ∗ ) = ∅ B_\eta(x^*)=\varnothing B η ( x ∗ ) = ∅ .
Omitted Material from Section 4.3
This appendix proves the algorithm for m = 2 m=2 m = 2 mentioned in Section 4.3, and Theorems 4.5 and 4.6.
Exact optimization on a line segment: m = 2 m=2 m = 2
Proposition E.1. When m = 2 m=2 m = 2 , there is a deterministic algorithm that, given all normalized pairs ( u i , τ i ) i ∈ N (u_i,\tau_i)_{i\in N} ( u i , τ i ) i ∈ N , returns a lottery minimizing viol \operatorname{viol} viol in time O ( n log n ) O(n\log n) O ( n log n ) .
Proof. Since m = 2 m=2 m = 2 , every lottery can be written uniquely as x λ : = ( λ , 1 − λ ) x_\lambda:=(\lambda,1-\lambda) x λ := ( λ , 1 − λ ) with λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] . With two alternatives, the normalization of Section 2 gives u i = ( 1 , 0 ) u_i=(1,0) u i = ( 1 , 0 ) or u i = ( 0 , 1 ) u_i=(0,1) u i = ( 0 , 1 ) for every agent i i i . Hence the set A i : = { λ ∈ [ 0 , 1 ] : x λ ∈ A i } A_i:=\{\lambda\in[0,1]:x_\lambda\in A_i\} A i := { λ ∈ [ 0 , 1 ] : x λ ∈ A i } is the interval [ ℓ i , r i ] [\ell_i,r_i] [ ℓ i , r i ] , where ( ℓ i , r i ) = ( τ i , 1 ) (\ell_i,r_i)=(\tau_i,1) ( ℓ i , r i ) = ( τ i , 1 ) if u i = ( 1 , 0 ) u_i=(1,0) u i = ( 1 , 0 ) and ( ℓ i , r i ) = ( 0 , 1 − τ i ) (\ell_i,r_i)=(0,1-\tau_i) ( ℓ i , r i ) = ( 0 , 1 − τ i ) if u i = ( 0 , 1 ) u_i=(0,1) u i = ( 0 , 1 ) . Since n − viol ( x λ ) = ∣ { i ∈ N : λ ∈ A i } ∣ n-\operatorname{viol}(x_\lambda)=|\{i\in N:\lambda\in A_i\}| n − viol ( x λ ) = ∣ { i ∈ N : λ ∈ A i } ∣ for every λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , it suffices to find a point of [ 0 , 1 ] [0,1] [ 0 , 1 ] contained in the largest number of these intervals, which Algorithm 2 does by sorting the endpoints.
:::
Algorithm 2 Returns a lottery with the minimum number of violations when $m = 2$.
Input: The normalized pairs $(u_i,\tau_i)_{i\in N}$, with $S = \{s_1,s_2\}$.
Output: A lottery $x^*$ minimizing viol.
1: for $i = 1,\ldots,n$ do
2: if $u_i = (1,0)$ then
3: Set $(\ell_i,r_i) \leftarrow (\tau_i,1)$
4: else
5: Set $(\ell_i,r_i) \leftarrow (0,1-\tau_i)$
6: end if
7: end for
8: Form the list of tagged endpoints $(\ell_i,\mathrm{L})$ and $(r_i,\mathrm{R})$ for every $i \in N$, together with $(0,\mathrm{sent})$ and $(1,\mathrm{sent})$
9: Sort this list by coordinate and scan it once to obtain the distinct coordinates $\lambda_1 < \cdots < \lambda_d$ and, for each $j \in [d]$, the counts $L_j := |\{i \in N : \ell_i = \lambda_j\}|$ and $R_j := |\{i \in N : r_i = \lambda_j\}|$
10: $c \leftarrow 0$, $c_{\max} \leftarrow -1$, $\lambda^* \leftarrow 0$
11: for $j = 1,\ldots,d$ do
12: $c \leftarrow c + L_j$
13: if $c > c_{\max}$ then
14: $c_{\max} \leftarrow c$
15: $\lambda^* \leftarrow \lambda_j$
16: end if
17: $c \leftarrow c - R_j$
18: end for
19: return $x^* := (\lambda^*,1-\lambda^*)$
We now prove correctness. Let λ 1 < ⋯ < λ d \lambda_1 < \cdots< \lambda_d λ 1 < ⋯ < λ d and L j L_j L j , R j R_j R j be the quantities produced by Algorithm 2. We claim that, for each j ∈ [ d ] j \in[d] j ∈ [ d ] , immediately before the update c ← c + L j c \leftarrow c + L_j c ← c + L j , the value of c c c is ∣ { i ∈ N : ℓ i < λ j ≤ r i } ∣ |\{i \in N : \ell_i < \lambda_j \le r_i\}| ∣ { i ∈ N : ℓ i < λ j ≤ r i } ∣ . This is true for j = 1 j = 1 j = 1 because λ 1 = 0 \lambda_1 = 0 λ 1 = 0 (by the sentinels), initially c = 0 c = 0 c = 0 , and no interval satisfies ℓ i < 0 \ell_i < 0 ℓ i < 0 . If the claim holds at the start of iteration j j j , then after the update c ← c + L j c \leftarrow c + L_j c ← c + L j we have c = ∣ { i ∈ N : ℓ i ≤ λ j ≤ r i } ∣ = ∣ { i ∈ N : λ j ∈ Λ i } ∣ c = |\{i \in N : \ell_i \le\lambda_j \le r_i\}| = |\{i \in N : \lambda_j \in\Lambda_i\}| c = ∣ { i ∈ N : ℓ i ≤ λ j ≤ r i } ∣ = ∣ { i ∈ N : λ j ∈ Λ i } ∣ . Thus, the algorithm evaluates the overlap number at λ j \lambda_j λ j . After this evaluation, the update c ← c − R j c \leftarrow c - R_j c ← c − R j removes exactly the intervals with r i = λ j r_i = \lambda_j r i = λ j , so the resulting value of c c c is ∣ { i ∈ N : ℓ i ≤ λ j < r i } ∣ |\{i \in N : \ell_i \le\lambda_j < r_i\}| ∣ { i ∈ N : ℓ i ≤ λ j < r i } ∣ . For j < d j < d j < d , since there is no endpoint in ( λ j , λ j + 1 ) (\lambda_j,\lambda_{j+1}) ( λ j , λ j + 1 ) , this equals ∣ { i ∈ N : ℓ i < λ j + 1 ≤ r i } ∣ |\{i \in N : \ell_i < \lambda_{j+1} \le r_i\}| ∣ { i ∈ N : ℓ i < λ j + 1 ≤ r i } ∣ , which is precisely the invariant at the start of iteration j + 1 j+1 j + 1 .
Now, let λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] . If λ = λ j \lambda= \lambda_j λ = λ j for some j ∈ [ d ] j \in[d] j ∈ [ d ] , its overlap number is explicitly evaluated by the algorithm. Otherwise, λ ∈ ( λ j , λ j + 1 ) \lambda\in(\lambda_j,\lambda_{j+1}) λ ∈ ( λ j , λ j + 1 ) for some consecutive coordinates λ j < λ j + 1 \lambda_j < \lambda_{j+1} λ j < λ j + 1 . Since no interval endpoint lies in ( λ j , λ j + 1 ) (\lambda_j,\lambda_{j+1}) ( λ j , λ j + 1 ) , the set { i ∈ N : λ ∈ Λ i } \{i \in N : \lambda\in\Lambda_i\} { i ∈ N : λ ∈ Λ i } is independent of the choice of λ \lambda λ inside this open interval. Moreover, if λ ∈ Λ i = [ ℓ i , r i ] \lambda\in\Lambda_i = [\ell_i,r_i] λ ∈ Λ i = [ ℓ i , r i ] , then ℓ i ∉ ( λ j , λ j + 1 ) \ell_i \notin(\lambda_j,\lambda_{j+1}) ℓ i ∈ / ( λ j , λ j + 1 ) and r i ∉ ( λ j , λ j + 1 ) r_i \notin(\lambda_j,\lambda_{j+1}) r i ∈ / ( λ j , λ j + 1 ) , while ℓ i ≤ λ ≤ r i \ell_i \le\lambda\le r_i ℓ i ≤ λ ≤ r i . Hence ℓ i ≤ λ j \ell_i \le\lambda_j ℓ i ≤ λ j and r i ≥ λ j + 1 r_i \ge\lambda_{j+1} r i ≥ λ j + 1 , so λ j ∈ Λ i \lambda_j \in\Lambda_i λ j ∈ Λ i . Therefore, ∣ { i ∈ N : λ ∈ Λ i } ∣ ≤ ∣ { i ∈ N : λ j ∈ Λ i } ∣ |\{i \in N : \lambda\in\Lambda_i\}| \le|\{i \in N : \lambda_j \in\Lambda_i\}| ∣ { i ∈ N : λ ∈ Λ i } ∣ ≤ ∣ { i ∈ N : λ j ∈ Λ i } ∣ . So a maximum overlap point can always be chosen among λ 1 , … , λ d \lambda_1,\ldots,\lambda_d λ 1 , … , λ d , and the algorithm returns some λ ∗ ∈ [ 0 , 1 ] \lambda^* \in[0,1] λ ∗ ∈ [ 0 , 1 ] maximizing ∣ { i ∈ N : λ ∈ Λ i } ∣ |\{i \in N : \lambda\in\Lambda_i\}| ∣ { i ∈ N : λ ∈ Λ i } ∣ .
Using n − viol ( x λ ) = ∣ { i ∈ N : λ ∈ Λ i } ∣ n - \operatorname{viol}(x_\lambda) = |\{i \in N : \lambda\in\Lambda_i\}| n − viol ( x λ ) = ∣ { i ∈ N : λ ∈ Λ i } ∣ , we conclude that x ∗ : = x λ ∗ ∈ arg min x ∈ Δ ( S ) viol ( x ) x^* := x_{\lambda^*} \in\arg\min_{x\in\Delta(S)} \operatorname{viol}(x) x ∗ := x λ ∗ ∈ arg min x ∈ Δ ( S ) viol ( x ) .
Finally, computing all values ℓ i , r i \ell_i,r_i ℓ i , r i takes O ( n ) O(n) O ( n ) time, sorting the 2 n + 2 2n+2 2 n + 2 tagged endpoints takes O ( n log n ) O(n\log n) O ( n log n ) time, the scan that forms ( λ j , L j , R j ) j = 1 d (\lambda_j,L_j,R_j)_{j=1}^d ( λ j , L j , R j ) j = 1 d is linear, and the final sweep is linear. Therefore, the total running time is O ( n log n ) O(n\log n) O ( n log n ) .
Proof of Theorem 4.5
Proof. We first show that an infeasible family of acceptable sets contains an infeasible subfamily of at most m m m sets, and that such a subfamily can be found with few LP feasibility checks. We then show that branching on which agent of this subfamily to drop decides the problem. Throughout, we use the convention ⋂ i ∈ ∅ A i = Δ ( S ) \bigcap_{i\in\varnothing} A_i = \Delta(S) ⋂ i ∈ ∅ A i = Δ ( S ) .
Lemma E.2. Let N ′ ⊆ N N' \subseteq N N ′ ⊆ N . If ⋂ i ∈ N ′ A i = ∅ \bigcap_{i\in N'} A_i = \varnothing ⋂ i ∈ N ′ A i = ∅ , then there exists W ⊆ N ′ W \subseteq N' W ⊆ N ′ with ∣ W ∣ ≤ m |W| \le m ∣ W ∣ ≤ m such that ⋂ i ∈ W A i = ∅ \bigcap_{i\in W} A_i = \varnothing ⋂ i ∈ W A i = ∅ .
Algorithm 3 HellyBranch($N'$, $v$) (deletes up to $v$ agents from $N'$)
Input: Index set $N' \subseteq N$, integer $v \ge 0$.
Output: Either NO, or a lottery $\mathbf{x} \in \Delta(S)$ such that there exists $V \subseteq N'$ with $|V| \le v$ and $\mathbf{x} \in \bigcap_{i\in N'\setminus V} A_i$.
1: if $\bigcap_{i\in N'} A_i \ne \varnothing$ then
2: return any $\mathbf{x} \in \bigcap_{i\in N'} A_i$ (found by LP feasibility)
3: end if
4: if $v = 0$ then
5: return NO
6: end if
7: Compute $W \subseteq N'$ with $|W| \le m$ and $\bigcap_{i\in W} A_i = \varnothing$ (Lemma E.3)
8: for each $i \in W$ do
9: $\mathbf{x} \leftarrow$ HellyBranch($N' \setminus \{i\}$, $v - 1$)
10: if $\mathbf{x} \ne$ NO then
11: return $\mathbf{x}$
12: end if
13: end for
14: return NO
Proof. Each A i A_i A i is a convex subset of the affine hull of Δ ( S ) \Delta(S) Δ ( S ) , which has dimension m − 1 m-1 m − 1 . By Helly’s theorem [47 ] in dimension m − 1 m-1 m − 1 , if a finite family of convex subsets of that affine hull has empty intersection, then some subfamily of size at most ( m − 1 ) + 1 = m (m-1)+1=m ( m − 1 ) + 1 = m already has empty intersection. Applying this to { A i } i ∈ N ′ \{A_i\}_{i\in N'} { A i } i ∈ N ′ proves the claim.
Lemma E.3. There is a deterministic procedure that, given N ′ ⊆ N N' \subseteq N N ′ ⊆ N with ⋂ i ∈ N ′ A i = ∅ \bigcap_{i\in N'} A_i = \varnothing ⋂ i ∈ N ′ A i = ∅ , returns W ⊆ N ′ W \subseteq N' W ⊆ N ′ such that ∣ W ∣ ≤ m |W| \le m ∣ W ∣ ≤ m and ⋂ i ∈ W A i = ∅ \bigcap_{i\in W} A_i = \varnothing ⋂ i ∈ W A i = ∅ using at most ∣ N ′ ∣ |N'| ∣ N ′ ∣ feasibility checks of linear programs over Δ ( S ) \Delta(S) Δ ( S ) .
Proof. Initialize W ← N ′ W \leftarrow N' W ← N ′ , and fix an arbitrary ordering i 1 , … , i ∣ N ′ ∣ i_1,\ldots,i_{|N'|} i 1 , … , i ∣ N ′ ∣ of the elements of N ′ N' N ′ . For t = 1 , … , ∣ N ′ ∣ t=1,\ldots,|N'| t = 1 , … , ∣ N ′ ∣ , if ⋂ ℓ ∈ W ∖ { i t } A ℓ = ∅ \bigcap_{\ell\in W\setminus\{i_t\}} A_\ell= \varnothing ⋂ ℓ ∈ W ∖ { i t } A ℓ = ∅ , then set W ← W ∖ { i t } W \leftarrow W \setminus\{i_t\} W ← W ∖ { i t } .
This procedure performs at most ∣ N ′ ∣ |N'| ∣ N ′ ∣ feasibility checks, one for each i t i_t i t . Moreover, throughout the procedure we maintain ⋂ ℓ ∈ W A ℓ = ∅ \bigcap_{\ell\in W} A_\ell= \varnothing ⋂ ℓ ∈ W A ℓ = ∅ , because we delete i t i_t i t only when the remaining family is still infeasible.
We claim that the final set W W W is inclusion-minimal infeasible. Indeed, fix any i t i_t i t that remains in the final set W W W . When i t i_t i t was processed, it was not deleted, so at that moment the current set, say W ′ W' W ′ , satisfied ⋂ ℓ ∈ W ′ ∖ { i t } A ℓ ≠ ∅ \bigcap_{\ell\in W'\setminus\{i_t\}} A_\ell\ne\varnothing ⋂ ℓ ∈ W ′ ∖ { i t } A ℓ = ∅ . Afterwards the algorithm only deletes more agents, so W ∖ { i t } ⊆ W ′ ∖ { i t } W \setminus\{i_t\} \subseteq W' \setminus\{i_t\} W ∖ { i t } ⊆ W ′ ∖ { i t } . Feasibility is preserved when constraints are removed, and thus ⋂ ℓ ∈ W ∖ { i t } A ℓ ≠ ∅ \bigcap_{\ell\in W\setminus\{i_t\}} A_\ell\ne\varnothing ⋂ ℓ ∈ W ∖ { i t } A ℓ = ∅ . Therefore, W W W is inclusion-minimal infeasible.
By Lemma E.2, every infeasible family contains an infeasible subfamily of size at most m m m . If ∣ W ∣ > m |W| > m ∣ W ∣ > m , then applying Lemma E.2 to the family { A i } i ∈ W \{A_i\}_{i\in W} { A i } i ∈ W would give us a proper infeasible subfamily of W W W , contradicting the inclusion-minimality of W W W . Therefore ∣ W ∣ ≤ m |W| \le m ∣ W ∣ ≤ m .
We run Algorithm 3 on input ( N , v ) (N,v) ( N , v ) .
We prove the following stronger recursive claim: for every N ′ ⊆ N N' \subseteq N N ′ ⊆ N and every integer r ≥ 0 r \ge0 r ≥ 0 , the call HellyBranch( N ′ , r ) (N',r) ( N ′ , r ) returns NO if and only if there is no set V ⊆ N ′ V \subseteq N' V ⊆ N ′ with ∣ V ∣ ≤ r |V| \le r ∣ V ∣ ≤ r such that ⋂ i ∈ N ′ ∖ V A i ≠ ∅ \bigcap_{i\in N'\setminus V} A_i \ne\varnothing ⋂ i ∈ N ′ ∖ V A i = ∅ . Moreover, whenever HellyBranch( N ′ , r ) (N',r) ( N ′ , r ) returns a lottery x \mathbf{x} x , there exists such a set V ⊆ N ′ V \subseteq N' V ⊆ N ′ with x ∈ ⋂ i ∈ N ′ ∖ V A i \mathbf{x} \in\bigcap_{i\in N'\setminus V} A_i x ∈ ⋂ i ∈ N ′ ∖ V A i . We prove the claim by induction on r r r .
If r = 0 r=0 r = 0 , then the algorithm returns a lottery exactly when ⋂ i ∈ N ′ A i ≠ ∅ \bigcap_{i\in N'} A_i \ne\varnothing ⋂ i ∈ N ′ A i = ∅ (Line 1), and otherwise returns NO (Lines 4–5). This is precisely the claim with V = ∅ V=\varnothing V = ∅ .
Now let r ≥ 1 r \ge1 r ≥ 1 and assume the claim holds for r − 1 r-1 r − 1 . If ⋂ i ∈ N ′ A i ≠ ∅ \bigcap_{i\in N'} A_i \ne\varnothing ⋂ i ∈ N ′ A i = ∅ , then Line 2 returns some x ∈ ⋂ i ∈ N ′ A i \mathbf{x} \in\bigcap_{i\in N'} A_i x ∈ ⋂ i ∈ N ′ A i , so the claim holds with V = ∅ V=\varnothing V = ∅ . Suppose instead that ⋂ i ∈ N ′ A i = ∅ \bigcap_{i\in N'} A_i = \varnothing ⋂ i ∈ N ′ A i = ∅ . By Lemma E.3, the algorithm computes a set W ⊆ N ′ W \subseteq N' W ⊆ N ′ such that ∣ W ∣ ≤ m |W| \le m ∣ W ∣ ≤ m and ⋂ i ∈ W A i = ∅ \bigcap_{i\in W} A_i = \varnothing ⋂ i ∈ W A i = ∅ .
If, for some i ∈ W i \in W i ∈ W , the recursive call HellyBranch( N ′ ∖ { i } , r − 1 ) (N' \setminus\{i\}, r - 1) ( N ′ ∖ { i } , r − 1 ) returns a lottery x x x , then by the induction hypothesis there exists V ′ ⊆ N ′ ∖ { i } V' \subseteq N' \setminus\{i\} V ′ ⊆ N ′ ∖ { i } with ∣ V ′ ∣ ≤ r − 1 |V'| \le r - 1 ∣ V ′ ∣ ≤ r − 1 such that x ∈ ⋂ t ∈ N ′ ∖ ( V ′ ∪ { i } ) A t x \in\bigcap_{t\in N'\setminus(V'\cup\{i\})} A_t x ∈ ⋂ t ∈ N ′ ∖ ( V ′ ∪ { i }) A t . Thus, the current call returns a valid lottery with deleted set V : = V ′ ∪ { i } V := V' \cup\{i\} V := V ′ ∪ { i } , and ∣ V ∣ ≤ r |V| \le r ∣ V ∣ ≤ r .
Conversely, suppose there exists V ∗ ⊆ N ′ V^* \subseteq N' V ∗ ⊆ N ′ with ∣ V ∗ ∣ ≤ r |V^*| \le r ∣ V ∗ ∣ ≤ r such that ⋂ i ∈ N ′ ∖ V ∗ A i ≠ ∅ \bigcap_{i\in N'\setminus V^*} A_i \ne\varnothing ⋂ i ∈ N ′ ∖ V ∗ A i = ∅ . Since ⋂ i ∈ W A i = ∅ \bigcap_{i\in W} A_i = \varnothing ⋂ i ∈ W A i = ∅ , we must have V ∗ ∩ W ≠ ∅ V^* \cap W \ne\varnothing V ∗ ∩ W = ∅ ; otherwise W ⊆ N ′ ∖ V ∗ W \subseteq N' \setminus V^* W ⊆ N ′ ∖ V ∗ , which would imply ⋂ i ∈ N ′ ∖ V ∗ A i ⊆ ⋂ i ∈ W A i = ∅ \bigcap_{i\in N'\setminus V^*} A_i \subseteq\bigcap_{i\in W} A_i = \varnothing ⋂ i ∈ N ′ ∖ V ∗ A i ⊆ ⋂ i ∈ W A i = ∅ , a contradiction. Fix any i ∗ ∈ V ∗ ∩ W i^* \in V^* \cap W i ∗ ∈ V ∗ ∩ W . Then V ∗ ∖ { i ∗ } ⊆ N ′ ∖ { i ∗ } V^* \setminus\{i^*\} \subseteq N' \setminus\{i^*\} V ∗ ∖ { i ∗ } ⊆ N ′ ∖ { i ∗ } and ∣ V ∗ ∖ { i ∗ } ∣ ≤ r − 1 |V^* \setminus\{i^*\}| \le r-1 ∣ V ∗ ∖ { i ∗ } ∣ ≤ r − 1 , and deleting V ∗ ∖ { i ∗ } V^* \setminus\{i^*\} V ∗ ∖ { i ∗ } from N ′ ∖ { i ∗ } N' \setminus\{i^*\} N ′ ∖ { i ∗ } leaves exactly N ′ ∖ V ∗ N' \setminus V^* N ′ ∖ V ∗ , whose acceptable sets have a common point. By the induction hypothesis, the recursive call on ( N ′ ∖ { i ∗ } , r − 1 ) (N' \setminus\{i^*\}, r - 1) ( N ′ ∖ { i ∗ } , r − 1 ) returns a lottery, and since the algorithm tries every i ∈ W i \in W i ∈ W , the current call also returns a lottery. This proves the recursive claim. Applying it to the top-level call ( N , v ) (N, v) ( N , v ) , we obtain the desired correctness.
If there exists a lottery x ∈ Δ ( S ) x \in\Delta(S) x ∈ Δ ( S ) with viol ( x ) ≤ v \operatorname{viol}(x) \le v viol ( x ) ≤ v , define V : = { i ∈ N : ⟨ u i , x ⟩ < τ i } V := \{i \in N : \langle u_i, x\rangle< \tau_i\} V := { i ∈ N : ⟨ u i , x ⟩ < τ i } . By the definition of A i A_i A i , we have ∣ V ∣ = viol ( x ) ≤ v |V| = \operatorname{viol}(x) \le v ∣ V ∣ = viol ( x ) ≤ v and x ∈ ⋂ i ∈ N ∖ V A i x \in\bigcap_{i\in N\setminus V} A_i x ∈ ⋂ i ∈ N ∖ V A i . Thus, by the recursive claim, HellyBranch( N , v ) (N, v) ( N , v ) does not return NO.
Conversely, if HellyBranch( N , v ) (N, v) ( N , v ) returns a lottery x x x , then by the recursive claim there exists V ⊆ N V \subseteq N V ⊆ N with ∣ V ∣ ≤ v |V| \le v ∣ V ∣ ≤ v such that x ∈ ⋂ i ∈ N ∖ V A i x \in\bigcap_{i\in N\setminus V} A_i x ∈ ⋂ i ∈ N ∖ V A i . Therefore, every violated agent lies in V V V , and so viol ( x ) ≤ ∣ V ∣ ≤ v \operatorname{viol}(x) \le|V| \le v viol ( x ) ≤ ∣ V ∣ ≤ v . Thus Algorithm 3 returns NO if and only if there is no lottery x ∈ Δ ( S ) x \in\Delta(S) x ∈ Δ ( S ) with viol ( x ) ≤ v \operatorname{viol}(x) \le v viol ( x ) ≤ v , and whenever it returns a lottery, that lottery has at most v v v violations.
For the running time, each internal node has at most m m m children and the recursion depth is at most v v v , so the recursion tree has at most 1 + m + ⋯ + m v = O ( m v ) 1 + m + \cdots+ m^v = O(m^v) 1 + m + ⋯ + m v = O ( m v ) nodes. At each node, Line 1 solves one LP feasibility problem over Δ ( S ) \Delta(S) Δ ( S ) ; if the current family is infeasible and r > 0 r > 0 r > 0 , Lemma E.3 performs at most ∣ N ′ ∣ ≤ n |N'| \le n ∣ N ′ ∣ ≤ n additional LP feasibility checks. Each such LP has m m m variables and at most m + ∣ N ′ ∣ + 1 ≤ m + n + 1 m + |N'| + 1 \le m + n + 1 m + ∣ N ′ ∣ + 1 ≤ m + n + 1 linear constraints. Thus the algorithm performs O ( m v n ) O(m^v n) O ( m v n ) LP feasibility checks, each of which takes polynomial time, so the problem is fixed-parameter tractable when parameterized by ( v , m ) (v, m) ( v , m ) .
Proof of Theorem 4.6
Proof. We give a parameterized reduction from HITTING SET. Let ( q , F , v ) (q, \mathcal{F}, v) ( q , F , v ) be an instance, where F = { F 1 , … , F t } \mathcal{F} = \{F_1, \ldots, F_t\} F = { F 1 , … , F t } is a family of subsets of [ q ] [q] [ q ] , and the question is whether there exists a set C ⊆ [ q ] C \subseteq[q] C ⊆ [ q ] with ∣ C ∣ ≤ v |C| \le v ∣ C ∣ ≤ v such that C ∩ F ℓ ≠ ∅ C \cap F_\ell\ne\varnothing C ∩ F ℓ = ∅ for every ℓ ∈ { 1 , … , t } \ell\in\{1, \ldots, t\} ℓ ∈ { 1 , … , t } .
We may assume that q ≥ 1 q \ge1 q ≥ 1 , that every F ℓ F_\ell F ℓ is nonempty, and that v ≤ q v \le q v ≤ q : if some F ℓ F_\ell F ℓ is empty, the instance is a no-instance, and otherwise, if q = 0 q = 0 q = 0 or v > q v > q v > q , it is a yes-instance (take C = [ q ] C = [q] C = [ q ] ); in these cases we output a fixed no-instance or yes-instance of MIN-VIOL with parameter 0.
From ( q , F , v ) (q, \mathcal{F}, v) ( q , F , v ) , construct an instance of MIN-VIOL as follows. Let the set of alternatives be S = { s 1 , … , s q , s q + 1 } S = \{s_1, \ldots, s_q, s_{q+1}\} S = { s 1 , … , s q , s q + 1 } , where s q + 1 s_{q+1} s q + 1 is an extra alternative.
For each j ∈ [ q ] j \in[q] j ∈ [ q ] , create an element agent a j a_j a j with threshold τ a j = 1 / q \tau_{a_j} = 1/q τ a j = 1/ q and utility vector u a j ( s j ) = 1 u_{a_j}(s_j) = 1 u a j ( s j ) = 1 , u a j ( s ℓ ) = 0 u_{a_j}(s_\ell) = 0 u a j ( s ℓ ) = 0 for every ℓ ≠ j \ell\ne j ℓ = j . For any lottery x = ( x 1 , … , x q + 1 ) ∈ Δ ( S ) x = (x_1, \ldots, x_{q+1}) \in\Delta(S) x = ( x 1 , … , x q + 1 ) ∈ Δ ( S ) , we have U a j ( x ) = x j U_{a_j}(x) = x_j U a j ( x ) = x j . Thus, agent a j a_j a j accepts x x x if and only if x j ≥ 1 / q x_j \ge1/q x j ≥ 1/ q .
Next, for each set F ℓ ∈ F F_\ell\in\mathcal{F} F ℓ ∈ F and each copy index r ∈ { 1 , … , v + 1 } r \in\{1, \ldots, v+1\} r ∈ { 1 , … , v + 1 } , create a set agent b ℓ , r b_{\ell,r} b ℓ , r with threshold τ b ℓ , r = 1 − ( ∣ F ℓ ∣ − 1 ) / q \tau_{b_{\ell,r}} = 1 - (|F_\ell| - 1)/q τ b ℓ , r = 1 − ( ∣ F ℓ ∣ − 1 ) / q and utilities u b ℓ , r ( s j ) = 0 u_{b_{\ell,r}}(s_j) = 0 u b ℓ , r ( s j ) = 0 for j ∈ F ℓ j \in F_\ell j ∈ F ℓ and u b ℓ , r ( s j ) = 1 u_{b_{\ell,r}}(s_j) = 1 u b ℓ , r ( s j ) = 1 for j ∈ [ q ] ∖ F ℓ j \in[q] \setminus F_\ell j ∈ [ q ] ∖ F ℓ . In particular, u b ℓ , r ( s q + 1 ) = 1 u_{b_{\ell,r}}(s_{q+1}) = 1 u b ℓ , r ( s q + 1 ) = 1 . Therefore, for every x ∈ Δ ( S ) x \in\Delta(S) x ∈ Δ ( S ) , U b ℓ , r ( x ) = ∑ j ∉ F ℓ x j = 1 − ∑ j ∈ F ℓ x j U_{b_{\ell,r}}(x) = \sum_{j\notin F_\ell} x_j = 1 - \sum_{j\in F_\ell} x_j U b ℓ , r ( x ) = ∑ j ∈ / F ℓ x j = 1 − ∑ j ∈ F ℓ x j . Thus b ℓ , r b_{\ell,r} b ℓ , r accepts x x x if and only if 1 − ∑ j ∈ F ℓ x j ≥ 1 − ( ∣ F ℓ ∣ − 1 ) / q 1 - \sum_{j\in F_\ell} x_j \ge1 - (|F_\ell| - 1)/q 1 − ∑ j ∈ F ℓ x j ≥ 1 − ( ∣ F ℓ ∣ − 1 ) / q , that is, if and only if ∑ j ∈ F ℓ x j ≤ ( ∣ F ℓ ∣ − 1 ) / q \sum_{j\in F_\ell} x_j \le(|F_\ell| - 1)/q ∑ j ∈ F ℓ x j ≤ ( ∣ F ℓ ∣ − 1 ) / q .
All utilities in the construction are binary, and all pairs are normalized: every utility vector takes both values 0 and 1, and every threshold lies in ( 0 , 1 ] (0,1] ( 0 , 1 ] . When the threshold is 1, the utility vector is precisely the indicator vector specified in case (ii) of Lemma B.1. Moreover, the constructed profile satisfies the nondegeneracy assumption: each element agent a j a_j a j accepts e j e_j e j and rejects e q + 1 e_{q+1} e q + 1 , and, since F ℓ ≠ ∅ F_\ell\ne\varnothing F ℓ = ∅ implies τ b ℓ , r = ( q − ∣ F ℓ ∣ + 1 ) / q ∈ ( 0 , 1 ] \tau_{b_{\ell,r}} = (q - |F_\ell| + 1)/q \in(0,1] τ b ℓ , r = ( q − ∣ F ℓ ∣ + 1 ) / q ∈ ( 0 , 1 ] , each set agent b ℓ , r b_{\ell,r} b ℓ , r accepts e q + 1 e_{q+1} e q + 1 and rejects every e j e_j e j with j ∈ F ℓ j \in F_\ell j ∈ F ℓ . We now prove correctness. Assume first that the HITTING SET instance is a yes-instance, and let C ⊆ [ q ] C \subseteq[q] C ⊆ [ q ] be a hitting set with ∣ C ∣ ≤ v |C| \le v ∣ C ∣ ≤ v . Define a lottery x C ∈ Δ ( S ) x^C \in\Delta(S) x C ∈ Δ ( S ) by x j C = 0 x^C_j = 0 x j C = 0 for j ∈ C j \in C j ∈ C , x j C = 1 / q x^C_j = 1/q x j C = 1/ q for j ∈ [ q ] ∖ C j \in[q] \setminus C j ∈ [ q ] ∖ C , and x q + 1 C = 1 − ∑ j = 1 q x j C = ∣ C ∣ / q x^C_{q+1} = 1-\sum_{j=1}^q x^C_j = |C|/q x q + 1 C = 1 − ∑ j = 1 q x j C = ∣ C ∣/ q . For every j ∈ [ q ] j \in[q] j ∈ [ q ] , the element agent a j a_j a j is violated if and only if j ∈ C j \in C j ∈ C , since U a j ( x C ) = x j C U_{a_j}(x^C) = x^C_j U a j ( x C ) = x j C and τ a j = 1 / q \tau_{a_j} = 1/q τ a j = 1/ q . Thus, exactly ∣ C ∣ |C| ∣ C ∣ element agents are violated.
Now fix any ℓ ∈ { 1 , … , t } \ell\in\{1,\ldots,t\} ℓ ∈ { 1 , … , t } . Since C C C is a hitting set, C ∩ F ℓ ≠ ∅ C \cap F_\ell\ne\emptyset C ∩ F ℓ = ∅ , so at most ∣ F ℓ ∣ − 1 |F_\ell|-1 ∣ F ℓ ∣ − 1 elements of F ℓ F_\ell F ℓ belong to [ q ] ∖ C [q] \setminus C [ q ] ∖ C . Since x j C = 1 / q x^C_j = 1/q x j C = 1/ q for j ∈ [ q ] ∖ C j \in[q] \setminus C j ∈ [ q ] ∖ C and x j C = 0 x^C_j = 0 x j C = 0 for j ∈ C j \in C j ∈ C , it follows that ∑ j ∈ F ℓ x j C ≤ ( ∣ F ℓ ∣ − 1 ) / q \sum_{j\in F_\ell} x^C_j \le(|F_\ell|-1)/q ∑ j ∈ F ℓ x j C ≤ ( ∣ F ℓ ∣ − 1 ) / q . Hence every copy b ℓ , r b_{\ell,r} b ℓ , r accepts x C x^C x C . Thus no set agent is violated. Therefore, viol ( x C ) = ∣ C ∣ ≤ v \operatorname{viol}(x^C) = |C| \le v viol ( x C ) = ∣ C ∣ ≤ v , so the constructed MIN-VIOL instance is a yes-instance.
Conversely, suppose there exists a lottery x ∈ Δ ( S ) x \in\Delta(S) x ∈ Δ ( S ) such that viol ( x ) ≤ v \operatorname{viol}(x) \le v viol ( x ) ≤ v . We first show that x x x violates no set agent. Indeed, if x x x violated some b ℓ , r b_{\ell,r} b ℓ , r , then it would violate all v + 1 v+1 v + 1 identical copies b ℓ , 1 , … , b ℓ , v + 1 b_{\ell,1},\ldots,b_{\ell,v+1} b ℓ , 1 , … , b ℓ , v + 1 , which would imply viol ( x ) ≥ v + 1 \operatorname{viol}(x) \ge v+1 viol ( x ) ≥ v + 1 , contradicting viol ( x ) ≤ v \operatorname{viol}(x) \le v viol ( x ) ≤ v .
Thus, every set agent accepts x x x , and so for every ℓ ∈ { 1 , … , t } \ell\in\{1,\ldots,t\} ℓ ∈ { 1 , … , t } we have ∑ j ∈ F ℓ x j ≤ ( ∣ F ℓ ∣ − 1 ) / q \sum_{j\in F_\ell} x_j \le(|F_\ell|-1)/q ∑ j ∈ F ℓ x j ≤ ( ∣ F ℓ ∣ − 1 ) / q . Define C ( x ) : = { j ∈ [ q ] : x j < 1 / q } C(x) := \{j \in[q] : x_j < 1/q\} C ( x ) := { j ∈ [ q ] : x j < 1/ q } . We claim that C ( x ) C(x) C ( x ) is a hitting set. Suppose not. Then there exists some ℓ ∈ { 1 , … , t } \ell\in\{1,\ldots,t\} ℓ ∈ { 1 , … , t } such that C ( x ) ∩ F ℓ = ∅ C(x)\cap F_\ell= \emptyset C ( x ) ∩ F ℓ = ∅ . Thus, x j ≥ 1 / q x_j \ge1/q x j ≥ 1/ q for every j ∈ F ℓ j \in F_\ell j ∈ F ℓ , and therefore ∑ j ∈ F ℓ x j ≥ ∣ F ℓ ∣ / q > ( ∣ F ℓ ∣ − 1 ) / q \sum_{j\in F_\ell} x_j \ge|F_\ell|/q > (|F_\ell|-1)/q ∑ j ∈ F ℓ x j ≥ ∣ F ℓ ∣/ q > ( ∣ F ℓ ∣ − 1 ) / q , contradicting the acceptance of the set agents associated with F ℓ F_\ell F ℓ . Thus C ( x ) C(x) C ( x ) intersects every set F ℓ F_\ell F ℓ , so it is a hitting set.
Finally, an element agent a j a_j a j is violated if and only if x j < 1 / q x_j < 1/q x j < 1/ q , that is, if and only if j ∈ C ( x ) j \in C(x) j ∈ C ( x ) . Since no set agent is violated, it follows that ∣ C ( x ) ∣ = viol ( x ) ≤ v |C(x)| = \operatorname{viol}(x) \le v ∣ C ( x ) ∣ = viol ( x ) ≤ v . So C ( x ) C(x) C ( x ) is a hitting set of size at most v v v .
We have shown that in the case q ≥ 1 q \ge1 q ≥ 1 , every F ℓ ≠ ∅ F_\ell\ne\emptyset F ℓ = ∅ , and v ≤ q v \le q v ≤ q , the instance ( q , F , v ) (q,\mathcal{F},v) ( q , F , v ) is a yes-instance of HITTING SET if and only if the constructed MIN-VIOL instance is a yes-instance. In this branch the construction uses q + 1 q+1 q + 1 alternatives and q + t ( v + 1 ) q+t(v+1) q + t ( v + 1 ) agents, and since v ≤ q v \le q v ≤ q , its size is polynomial in the size of ( q , F , v ) (q,\mathcal{F},v) ( q , F , v ) . The output parameter is v v v , or 0 in the trivial cases above. Therefore this is a parameterized reduction from HITTING SET parameterized by v v v to the decision version of MIN-VIOL. Since HITTING SET is W[2]-hard parameterized by v v v , the latter problem is also W[2]-hard when parameterized by v v v alone.
The same hardness immediately carries over to the search version: any algorithm that returns a lottery x x x with viol ( x ) ≤ v \operatorname{viol}(x) \le v viol ( x ) ≤ v whenever one exists also decides the decision problem.
Omitted Proofs from Section 5
Throughout this appendix, i 1 , … , i k i_1,\ldots,i_k i 1 , … , i k are sampled independently from Unif ( N ) \operatorname{Unif}(\mathbb{N}) Unif ( N ) . For a lottery x x x , let R x : = { i ∈ N : x ∉ A i } R_x := \{i \in N : x \notin A_i\} R x := { i ∈ N : x ∈ / A i } be the set of agents who reject x x x , let r ( x ) : = ∣ R x ∣ / n = viol ( x ) / n r(x) := |R_x|/n = \operatorname{viol}(x)/n r ( x ) := ∣ R x ∣/ n = viol ( x ) / n , and let r ^ ( x ) : = 1 k ∑ t = 1 k 1 { i t ∈ R x } \hat r(x) := \frac{1}{k}\sum_{t=1}^k \mathbf{1}\{i_t \in R_x\} r ^ ( x ) := k 1 ∑ t = 1 k 1 { i t ∈ R x } be the fraction of sampled agents who reject x x x , counted with multiplicity. The lotteries x ^ \hat x x ^ in Theorems 5.1 and 5.2 are exactly the minimizers of r ^ \hat r r ^ . Both r r r and r ^ \hat r r ^ take finitely many values, so all minima below are attained.
Proof of Theorem 5.1
Since ∑ j = 1 m x j = 1 \sum_{j=1}^m x_j = 1 ∑ j = 1 m x j = 1 for every lottery, we have i ∈ R x i \in R_x i ∈ R x if and only if ⟨ u i , x ⟩ < τ i \langle u_i,x\rangle< \tau_i ⟨ u i , x ⟩ < τ i , that is, if and only if ∑ j = 1 m ( u i ( s j ) − τ i ) x j < 0 \sum_{j=1}^m (u_i(s_j)-\tau_i)x_j < 0 ∑ j = 1 m ( u i ( s j ) − τ i ) x j < 0 . If we identify agent i i i with the point ( u i ( s 1 ) − τ i , … , u i ( s m ) − τ i ) ∈ R m (u_i(s_1)-\tau_i,\ldots,u_i(s_m)-\tau_i) \in\mathbb{R}^m ( u i ( s 1 ) − τ i , … , u i ( s m ) − τ i ) ∈ R m , then R x R_x R x is the set of agents whose points lie in the open halfspace { y ∈ R m : ⟨ y , x ⟩ < 0 } \{y \in\mathbb{R}^m : \langle y,x\rangle< 0\} { y ∈ R m : ⟨ y , x ⟩ < 0 } . Hence the family { R x : x ∈ Δ ( S ) } \{R_x : x \in\Delta(S)\} { R x : x ∈ Δ ( S )} is induced on N N N by a subfamily of the open halfspaces of R m \mathbb{R}^m R m whose boundaries pass through the origin, and its VC dimension is at most m m m . Since r ( x ) = Pr i ∼ Unif ( N ) [ i ∈ R x ] r(x) = \Pr_{i\sim\operatorname{Unif}(N)}[i \in R_x] r ( x ) = Pr i ∼ Unif ( N ) [ i ∈ R x ] , the VC inequality [72 , 11 ] together with Sauer’s lemma (using k ≥ m k \ge m k ≥ m ) gives, with probability at least 1 − δ 1-\delta 1 − δ , sup x ∈ Δ ( S ) ∣ r ^ ( x ) − r ( x ) ∣ ≤ 2 2 ( m log ( 2 e k / m ) + log ( 4 / δ ) ) / k ≤ α \sup_{x\in\Delta(S)} |\hat r(x)-r(x)| \le2\sqrt{2(m\log(2ek/m)+\log(4/\delta))/k} \le\alpha sup x ∈ Δ ( S ) ∣ r ^ ( x ) − r ( x ) ∣ ≤ 2 2 ( m log ( 2 e k / m ) + log ( 4/ δ )) / k ≤ α , where α : = 4 ( m log ( 2 e k / m ) + log ( 8 / δ ) ) / k \alpha:= 4\sqrt{(m\log(2ek/m)+\log(8/\delta))/k} α := 4 ( m log ( 2 e k / m ) + log ( 8/ δ )) / k . On this event, if x ∗ x^* x ∗ minimizes r r r and x ^ \hat x x ^ minimizes r ^ \hat r r ^ , then r ( x ^ ) ≤ r ^ ( x ^ ) + α ≤ r ^ ( x ∗ ) + α ≤ r ( x ∗ ) + 2 α r(\hat x) \le\hat r(\hat x)+\alpha\le\hat r(x^*)+\alpha\le r(x^*)+2\alpha r ( x ^ ) ≤ r ^ ( x ^ ) + α ≤ r ^ ( x ∗ ) + α ≤ r ( x ∗ ) + 2 α . Multiplying by n n n gives viol ( x ^ ) ≤ OPT + 2 α n \operatorname{viol}(\hat x) \le\operatorname{OPT}+2\alpha n viol ( x ^ ) ≤ OPT + 2 α n , which is the claim.
Proof of Theorem 5.2
The proof follows that of Theorem 5.1, with the VC inequality replaced by a bound on the relative error, which is much smaller for lotteries rejected by few agents. By the proof of Theorem 5.1, the family { R x : x ∈ Δ ( S ) } \{R_x : x \in\Delta(S)\} { R x : x ∈ Δ ( S )} has VC dimension at most m m m . Let β : = ζ / 20 \beta:= \zeta/20 β := ζ /20 . By the relative-error bound of Li et al. [2001, Theorem 5], applied with parameter ρ \rho ρ and accuracy β \beta β , there is an absolute constant C C C such that, if k ≥ C ( m log ( 1 / ρ ) + log ( 1 / δ ) ) / ( ζ 2 ρ ) k \ge C(m \log(1/\rho) + \log(1/\delta))/(\zeta^2\rho) k ≥ C ( m log ( 1/ ρ ) + log ( 1/ δ )) / ( ζ 2 ρ ) , then with probability at least 1 − δ 1-\delta 1 − δ , ∣ r ^ ( x ) − r ( x ) ∣ ≤ β ( r ^ ( x ) + r ( x ) + ρ ) |\widehat{r}(x)-r(x)| \le\beta(\widehat{r}(x)+r(x)+\rho) ∣ r ( x ) − r ( x ) ∣ ≤ β ( r ( x ) + r ( x ) + ρ ) for all x ∈ Δ ( S ) x \in\Delta(S) x ∈ Δ ( S ) . Fix this event. Rearranging the two directions of this inequality gives ( 1 − β ) r ( x ) ≤ ( 1 + β ) r ^ ( x ) + β ρ (1-\beta)r(x) \le(1+\beta)\widehat{r}(x)+\beta\rho ( 1 − β ) r ( x ) ≤ ( 1 + β ) r ( x ) + β ρ and ( 1 − β ) r ^ ( x ) ≤ ( 1 + β ) r ( x ) + β ρ (1-\beta)\widehat{r}(x) \le(1+\beta)r(x)+\beta\rho ( 1 − β ) r ( x ) ≤ ( 1 + β ) r ( x ) + β ρ for every lottery x x x . Let x ∗ x^* x ∗ minimize r r r , so that r ( x ∗ ) = O P T / n r(x^*) = \mathrm{OPT}/n r ( x ∗ ) = OPT / n . Since x ^ \widehat{x} x minimizes r ^ \widehat{r} r ,
( 1 − β ) r ( x ^ ) ≤ ( 1 + β ) r ^ ( x ^ ) + β ρ ≤ ( 1 + β ) r ^ ( x ∗ ) + β ρ ≤ ( 1 + β ) 2 1 − β r ( x ∗ ) + 1 + β 1 − β β ρ + β ρ , (1-\beta)r(\widehat{x}) \le(1+\beta)\widehat{r}(\widehat{x})+\beta\rho\le(1+\beta)\widehat{r}(x^*)+\beta\rho\le\frac{(1+\beta)^2}{1-\beta}r(x^*)+\frac{1+\beta}{1-\beta}\beta\rho+\beta\rho, ( 1 − β ) r ( x ) ≤ ( 1 + β ) r ( x ) + β ρ ≤ ( 1 + β ) r ( x ∗ ) + β ρ ≤ 1 − β ( 1 + β ) 2 r ( x ∗ ) + 1 − β 1 + β β ρ + β ρ ,
and dividing by 1 − β 1-\beta 1 − β gives r ( x ^ ) ≤ ( ( 1 + β ) / ( 1 − β ) ) 2 r ( x ∗ ) + 2 β ρ / ( 1 − β ) 2 r(\widehat{x}) \le((1+\beta)/(1-\beta))^2r(x^*)+2\beta\rho/(1-\beta)^2 r ( x ) ≤ (( 1 + β ) / ( 1 − β ) ) 2 r ( x ∗ ) + 2 β ρ / ( 1 − β ) 2 . For 0 < β ≤ 1 / 20 0<\beta\le1/20 0 < β ≤ 1/20 , we have ( ( 1 + β ) / ( 1 − β ) ) 2 ≤ 1 + 10 β ((1+\beta)/(1-\beta))^2\le1+10\beta (( 1 + β ) / ( 1 − β ) ) 2 ≤ 1 + 10 β (the left-hand side is convex in β \beta β , equals 1 1 1 at β = 0 \beta=0 β = 0 , and is below 1.23 1.23 1.23 at β = 1 / 20 \beta=1/20 β = 1/20 ) and, since ( 1 − β ) 2 ≥ 9 / 10 (1-\beta)^2\ge9/10 ( 1 − β ) 2 ≥ 9/10 , 2 β / ( 1 − β ) 2 ≤ 10 β 2\beta/(1-\beta)^2\le10\beta 2 β / ( 1 − β ) 2 ≤ 10 β . Since 10 β = ζ / 2 10\beta=\zeta/2 10 β = ζ /2 , multiplying by n n n gives viol ( x ^ ) ≤ ( 1 + ζ / 2 ) O P T + ( ζ / 2 ) ρ n \operatorname{viol}(\widehat{x})\le(1+\zeta/2)\mathrm{OPT}+(\zeta/2)\rho n viol ( x ) ≤ ( 1 + ζ /2 ) OPT + ( ζ /2 ) ρ n . If O P T ≥ ρ n \mathrm{OPT}\ge\rho n OPT ≥ ρ n , then ( ζ / 2 ) ρ n ≤ ( ζ / 2 ) O P T (\zeta/2)\rho n\le(\zeta/2)\mathrm{OPT} ( ζ /2 ) ρ n ≤ ( ζ /2 ) OPT , so viol ( x ^ ) ≤ ( 1 + ζ ) O P T \operatorname{viol}(\widehat{x})\le(1+\zeta)\mathrm{OPT} viol ( x ) ≤ ( 1 + ζ ) OPT .
Proof of Theorem 5.3
We show that the LP penalty is an upper bound on the violation indicator (Lemma F.1), that its sample average is uniformly close to its population average (Lemma F.2), and that its population average for any lottery x x x is at most ( ( 1 + 1 / η ) viol ( x ) + ∣ B η ( x ) ∣ ) / n ((1+1/\eta)\operatorname{viol}(x)+|B_\eta(x)|)/n (( 1 + 1/ η ) viol ( x ) + ∣ B η ( x ) ∣ ) / n . For an agent i i i and a lottery x x x , let ℓ ( i , x ) : = max { 0 , ( τ i + η − U i ( x ) ) / η } \ell(i,x):=\max\{0,(\tau_i+\eta-U_i(x))/\eta\} ℓ ( i , x ) := max { 0 , ( τ i + η − U i ( x )) / η } be the penalty of Section 5.1, and let L ^ ( x ) : = 1 k ∑ t = 1 k ℓ ( i t , x ) \widehat{L}(x):=\frac{1}{k}\sum_{t=1}^k\ell(i_t,x) L ( x ) := k 1 ∑ t = 1 k ℓ ( i t , x ) and L ( x ) : = 1 n ∑ i ∈ N ℓ ( i , x ) L(x):=\frac{1}{n}\sum_{i\in N}\ell(i,x) L ( x ) := n 1 ∑ i ∈ N ℓ ( i , x ) be its sample and population averages.
Lemma F.1. For every agent i i i and lottery x x x , 1 { U i ( x ) < τ i } ≤ ℓ ( i , x ) \mathbf{1}\{U_i(x)<\tau_i\}\le\ell(i,x) 1 { U i ( x ) < τ i } ≤ ℓ ( i , x ) . Moreover, the optimal value of (1) is min x ∈ Δ ( S ) L ^ ( x ) \min_{x\in\Delta(S)}\widehat{L}(x) min x ∈ Δ ( S ) L ( x ) , and the x x x -part of every optimal solution of (1) minimizes L ^ \widehat{L} L .
Proof. If U i ( x ) ≥ τ i U_i(x)\ge\tau_i U i ( x ) ≥ τ i , the indicator is 0 ≤ ℓ ( i , x ) 0\le\ell(i,x) 0 ≤ ℓ ( i , x ) . If U i ( x ) < τ i U_i(x)<\tau_i U i ( x ) < τ i , then τ i + η − U i ( x ) > η \tau_i+\eta-U_i(x)>\eta τ i + η − U i ( x ) > η , so ℓ ( i , x ) > 1 \ell(i,x)>1 ℓ ( i , x ) > 1 . For a fixed x x x , the smallest feasible value of z t z_t z t in (1) is ℓ ( i t , x ) \ell(i_t,x) ℓ ( i t , x ) , so the smallest objective value with this x x x is L ^ ( x ) \widehat{L}(x) L ( x ) . Hence the optimal value of (1) is min x L ^ ( x ) \min_x\widehat{L}(x) min x L ( x ) , and if ( x , z 1 , … , z k ) (x,z_1,\ldots,z_k) ( x , z 1 , … , z k ) is optimal, then L ^ ( x ) ≤ 1 k ∑ t z t = min x ′ L ^ ( x ′ ) \widehat{L}(x)\le\frac{1}{k}\sum_t z_t=\min_{x'}\widehat{L}(x') L ( x ) ≤ k 1 ∑ t z t = min x ′ L ( x ′ ) .
Lemma F.2. There is an absolute constant C > 0 C>0 C > 0 such that, for every integer k ≥ 1 k\ge1 k ≥ 1 , δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] , with probability at least 1 − δ 1-\delta 1 − δ ,
sup x ∈ Δ ( S ) ∣ L ^ ( x ) − L ( x ) ∣ ≤ ( C / η ) ( log m + log ( 1 / δ ) ) / k . \sup_{x\in\Delta(S)}|\widehat{L}(x)-L(x)|\le(C/\eta)\sqrt{(\log m+\log(1/\delta))/k}. x ∈ Δ ( S ) sup ∣ L ( x ) − L ( x ) ∣ ≤ ( C / η ) ( log m + log ( 1/ δ )) / k .
Proof. We use the empirical Rademacher complexity of a class H \mathcal{H} H of functions on N N N , namely R ^ ( H ) : = E σ [ sup g ∈ H 1 k ∑ t = 1 k σ t g ( i t ) ] \widehat{\mathfrak{R}}(\mathcal{H}):=\mathbb{E}_{\sigma}\left[\sup_{g\in\mathcal{H}}\frac{1}{k}\sum_{t=1}^k\sigma_tg(i_t)\right] R ( H ) := E σ [ sup g ∈ H k 1 ∑ t = 1 k σ t g ( i t ) ] , where σ 1 , … , σ k \sigma_1,\ldots,\sigma_k σ 1 , … , σ k are independent and uniform on { − 1 , 1 } \{-1,1\} { − 1 , 1 } , together with the standard facts about it in Shalev-Shwartz and Ben-David [ [67 ] .
For each lottery x x x , define f x ( i ) : = U i ( x ) − τ i f_x(i):=U_i(x)-\tau_i f x ( i ) := U i ( x ) − τ i , and for each alternative s j s_j s j , define h j ( i ) : = u i ( s j ) − τ i h_j(i):=u_i(s_j)-\tau_i h j ( i ) := u i ( s j ) − τ i . Since x j ≥ 0 x_j\ge0 x j ≥ 0 and ∑ j = 1 m x j = 1 \sum_{j=1}^m x_j=1 ∑ j = 1 m x j = 1 , we have f x = ∑ j = 1 m x j h j f_x=\sum_{j=1}^m x_jh_j f x = ∑ j = 1 m x j h j , so the class F : = { f x : x ∈ Δ ( S ) } \mathcal{F}:=\{f_x:x\in\Delta(S)\} F := { f x : x ∈ Δ ( S )} is the convex hull of h 1 , … , h m h_1,\ldots,h_m h 1 , … , h m . Taking the convex hull does not change the Rademacher complexity, and since each h j h_j h j takes values in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , Massart’s lemma gives R ^ ( F ) = R ^ ( { h 1 , … , h m } ) ≤ 2 ( 2 log m ) / k \widehat{\mathfrak{R}}(\mathcal{F})=\widehat{\mathfrak{R}}(\{h_1,\ldots,h_m\})\le2\sqrt{(2\log m)/k} R ( F ) = R ({ h 1 , … , h m }) ≤ 2 ( 2 log m ) / k .
Let ψ ( z ) : = max { 0 , 1 − z / η } − 1 \psi(z):=\max\{0,1-z/\eta\}-1 ψ ( z ) := max { 0 , 1 − z / η } − 1 , so that ℓ ( i , x ) = 1 + ψ ( f x ( i ) ) \ell(i,x)=1+\psi(f_x(i)) ℓ ( i , x ) = 1 + ψ ( f x ( i )) , and let G : = { ψ ∘ f x : x ∈ Δ ( S ) } \mathcal{G}:=\{\psi\circ f_x:x\in\Delta(S)\} G := { ψ ∘ f x : x ∈ Δ ( S )} . Since ψ \psi ψ is ( 1 / η ) (1/\eta) ( 1/ η ) -Lipschitz, the contraction lemma gives R ^ ( G ) ≤ R ^ ( F ) / η \widehat{\mathfrak{R}}(\mathcal{G})\le\widehat{\mathfrak{R}}(\mathcal{F})/\eta R ( G ) ≤ R ( F ) / η . Moreover, f x ( i ) ∈ [ − 1 , 1 ] f_x(i)\in[-1,1] f x ( i ) ∈ [ − 1 , 1 ] because U i ( x ) ∈ [ 0 , 1 ] U_i(x)\in[0,1] U i ( x ) ∈ [ 0 , 1 ] and τ i ∈ ( 0 , 1 ] \tau_i\in(0,1] τ i ∈ ( 0 , 1 ] , so every function in G \mathcal{G} G takes values in [ − 1 , 1 / η ] ⊆ [ − 1 / η , 1 / η ] [-1,1/\eta]\subseteq[-1/\eta,1/\eta] [ − 1 , 1/ η ] ⊆ [ − 1/ η , 1/ η ] . The uniform convergence bound in terms of R ^ \widehat{\mathfrak{R}} R Shalev-Shwartz and Ben-David, [67 ] , applied to G \mathcal{G} G and to − G -\mathcal{G} − G (which has the same Rademacher complexity, since σ \sigma σ is symmetric), each with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 , shows that with probability at least 1 − δ 1-\delta 1 − δ ,
sup g ∈ G ∣ 1 k ∑ t = 1 k g ( i t ) − 1 n ∑ i ∈ N g ( i ) ∣ ≤ 2 R ^ ( G ) + 4 η 2 log ( 8 / δ ) k ≤ 4 η 2 log m k + 4 η 2 log ( 8 / δ ) k . \sup_{g\in\mathcal{G}}\left|\frac{1}{k}\sum_{t=1}^k g(i_t)-\frac{1}{n}\sum_{i\in N}g(i)\right|
\le2\widehat{\mathfrak{R}}(\mathcal{G})+\frac{4}{\eta}\sqrt{\frac{2\log(8/\delta)}{k}}
\le\frac{4}{\eta}\sqrt{\frac{2\log m}{k}}+\frac{4}{\eta}\sqrt{\frac{2\log(8/\delta)}{k}}. g ∈ G sup k 1 t = 1 ∑ k g ( i t ) − n 1 i ∈ N ∑ g ( i ) ≤ 2 R ( G ) + η 4 k 2 log ( 8/ δ ) ≤ η 4 k 2 log m + η 4 k 2 log ( 8/ δ ) .
Since the constant 1 in ℓ ( i , x ) = 1 + ψ ( f x ( i ) ) \ell(i, x) = 1 + \psi(f_{\mathbf{x}}(i)) ℓ ( i , x ) = 1 + ψ ( f x ( i )) cancels, the left-hand side equals sup x ∈ Δ ( S ) ∣ L ^ ( x ) − L ( x ) ∣ \sup_{\mathbf{x}\in\Delta(S)}|\widehat{L}(\mathbf{x}) - L(\mathbf{x})| sup x ∈ Δ ( S ) ∣ L ( x ) − L ( x ) ∣ . Finally, log ( 8 / δ ) ≤ 3 log m + log ( 1 / δ ) \log(8/\delta) \le3\log m + \log(1/\delta) log ( 8/ δ ) ≤ 3 log m + log ( 1/ δ ) because m ≥ 2 m \ge2 m ≥ 2 , which gives the lemma.
Let κ : = ( C / η ) ( log m + log ( 1 / δ ) ) / k \kappa:= (C/\eta)\sqrt{(\log m + \log(1/\delta))/k} κ := ( C / η ) ( log m + log ( 1/ δ )) / k be the bound of Lemma F.2, and fix the event of that lemma. We use three bounds. First, by Lemma F.1, viol ( x ^ η ) ≤ n L ( x ^ η ) \operatorname{viol}(\widehat{x}_{\eta}) \le nL(\widehat{x}_{\eta}) viol ( x η ) ≤ n L ( x η ) . Second, since x ^ η \widehat{x}_{\eta} x η minimizes L ^ \widehat{L} L (Lemma F.1), every lottery x \mathbf{x} x satisfies L ( x ^ η ) ≤ L ^ ( x ^ η ) + κ ≤ L ^ ( x ) + κ ≤ L ( x ) + 2 κ L(\widehat{x}_{\eta}) \le\widehat{L}(\widehat{x}_{\eta}) + \kappa\le\widehat{L}(\mathbf{x}) + \kappa\le L(\mathbf{x}) + 2\kappa L ( x η ) ≤ L ( x η ) + κ ≤ L ( x ) + κ ≤ L ( x ) + 2 κ . Third, we bound n L ( x ) nL(\mathbf{x}) n L ( x ) for a fixed lottery x \mathbf{x} x . If U i ( x ) ≥ τ i + η U_i(\mathbf{x}) \ge\tau_i + \eta U i ( x ) ≥ τ i + η , then ℓ ( i , x ) = 0 \ell(i, \mathbf{x}) = 0 ℓ ( i , x ) = 0 . If i ∈ B η ( x ) i \in B_\eta(\mathbf{x}) i ∈ B η ( x ) , then 0 < ℓ ( i , x ) ≤ 1 0 < \ell(i, \mathbf{x}) \le1 0 < ℓ ( i , x ) ≤ 1 . If U i ( x ) < τ i U_i(\mathbf{x}) < \tau_i U i ( x ) < τ i , then ℓ ( i , x ) = ( τ i + η − U i ( x ) ) / η ≤ ( 1 + η ) / η = 1 + 1 / η \ell(i, \mathbf{x}) = (\tau_i + \eta- U_i(\mathbf{x}))/\eta\le(1+\eta)/\eta= 1 + 1/\eta ℓ ( i , x ) = ( τ i + η − U i ( x )) / η ≤ ( 1 + η ) / η = 1 + 1/ η , because τ i ≤ 1 \tau_i \le1 τ i ≤ 1 and U i ( x ) ≥ 0 U_i(\mathbf{x}) \ge0 U i ( x ) ≥ 0 . Therefore n L ( x ) ≤ ( 1 + 1 / η ) viol ( x ) + ∣ B η ( x ) ∣ nL(\mathbf{x}) \le(1 + 1/\eta)\operatorname{viol}(\mathbf{x}) + |B_\eta(\mathbf{x})| n L ( x ) ≤ ( 1 + 1/ η ) viol ( x ) + ∣ B η ( x ) ∣ . Combining the three bounds gives viol ( x ^ η ) ≤ n L ( x ) + 2 κ n ≤ ( 1 + 1 / η ) viol ( x ) + ∣ B η ( x ) ∣ + 2 κ n \operatorname{viol}(\widehat{x}_{\eta}) \le nL(\mathbf{x}) + 2\kappa n \le(1 + 1/\eta)\operatorname{viol}(\mathbf{x}) + |B_\eta(\mathbf{x})| + 2\kappa n viol ( x η ) ≤ n L ( x ) + 2 κn ≤ ( 1 + 1/ η ) viol ( x ) + ∣ B η ( x ) ∣ + 2 κn for every lottery x \mathbf{x} x , which is the claim of Theorem 5.3 with constant 2 C 2C 2 C . If the LP is run on all n n n agents, each once, then L ^ = L \widehat{L} = L L = L , and the same argument with κ = 0 \kappa= 0 κ = 0 gives the full-information bound stated in § 5.1 .
Converting Sample Sizes into Query Budgets
Suppose each agent can be recovered with at most T ε = O ( m log ( 1 / ε ) ) T_\varepsilon= O(m\log(1/\varepsilon)) T ε = O ( m log ( 1/ ε )) queries, as under the finite-grid convention. With a budget of Q Q Q queries, sample k : = ⌊ Q / T ε ⌋ k := \lfloor Q/T_\varepsilon\rfloor k := ⌊ Q / T ε ⌋ agents independently from Unif ( N ) \operatorname{Unif}(N) Unif ( N ) and recover only the distinct sampled agents. This uses at most k T ε ≤ Q kT_\varepsilon\le Q k T ε ≤ Q queries, and the sampled agents, with their multiplicities, then define the problem on the sample exactly.
Proposition G.1. Assume the finite-grid convention and that m m m is a constant. Fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , let k : = ⌊ Q / T ε ⌋ ≥ m k := \lfloor Q/T_\varepsilon\rfloor\ge m k := ⌊ Q / T ε ⌋ ≥ m , sample and recover agents as above, and minimize the number of rejecting sampled agents exactly with the algorithm of Theorem 4.1 . This uses at most Q Q Q queries, the optimization takes time polynomial in k k k , and with probability at least 1 − δ 1-\delta 1 − δ the returned lottery satisfies the bound of Theorem 5.1 . If, in addition, δ \delta δ , ρ \rho ρ , ζ \zeta ζ , and k k k satisfy the conditions of Theorem 5.2 and OPT ≥ ρ n \operatorname{OPT} \ge\rho n OPT ≥ ρ n , then with probability at least 1 − δ 1-\delta 1 − δ the returned lottery has at most ( 1 + ζ ) OPT (1+\zeta)\operatorname{OPT} ( 1 + ζ ) OPT violations.
Proof. The query count was shown above. The sampled agents, counted with multiplicity, form a profile of k k k agents, and Theorem 4.1 minimizes the number of violations on it exactly in time polynomial in k k k for constant m m m ; for m = 2 m=2 m = 2 , Proposition E.1 takes time O ( k log k ) O(k\log k) O ( k log k ) . The guarantees then follow from Theorems 5.1 and 5.2 .
Proposition G.2. Assume the finite-grid convention. Fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] , let k : = ⌊ Q / T ε ⌋ ≥ 1 k := \lfloor Q/T_\varepsilon\rfloor\ge1 k := ⌊ Q / T ε ⌋ ≥ 1 , sample and recover agents as above, and solve the linear program (1) . This uses at most Q Q Q queries, the optimization takes time polynomial in k k k and m m m , and with probability at least 1 − δ 1-\delta 1 − δ the returned lottery satisfies the bound of Theorem 5.3 .
Proof. The query count was shown above. Once the sampled agents are recovered, (1) is a linear program with m + k m+k m + k variables and O ( m + k ) O(m+k) O ( m + k ) constraints, which can be solved in polynomial time. The guarantee follows from Theorem 5.3 .
Omitted Proofs from Section 6
Proof of Theorem 6.1
The idea is to choose utilities that reproduce every answer the algorithm received, while making every unqueried agent accept only a pure lottery other than x \mathbf{x} x . Consider the run of A \mathcal{A} A in which every query ( i , x ) (i,\mathbf{x}) ( i , x ) is answered “accept” if and only if x 3 = ⋯ = x m = 0 x_3 = \cdots= x_m = 0 x 3 = ⋯ = x m = 0 , with queried set M M M and output x ^ \widehat{\mathbf{x}} x . For each queried agent i ∈ M i \in M i ∈ M , set u i = ( 1 , 1 , 0 , … , 0 ) \mathbf{u}_i = (1,1,0,\ldots,0) u i = ( 1 , 1 , 0 , … , 0 ) and τ i = 1 \tau_i = 1 τ i = 1 . Then A i = { x ∈ Δ ( S ) : x 1 + x 2 ≥ 1 } = { x ∈ Δ ( S ) : x 3 = ⋯ = x m = 0 } A_i = \{\mathbf{x} \in\Delta(S): x_1 + x_2 \ge1\} = \{\mathbf{x} \in\Delta(S): x_3 = \cdots= x_m = 0\} A i = { x ∈ Δ ( S ) : x 1 + x 2 ≥ 1 } = { x ∈ Δ ( S ) : x 3 = ⋯ = x m = 0 } , so these agents give exactly the answers of the run above. For each unqueried agent i ∈ N ∖ M i \in N \setminus M i ∈ N ∖ M , set τ i = 1 \tau_i = 1 τ i = 1 and u i = z \mathbf{u}_i = \mathbf{z} u i = z , where z : = e 1 \mathbf{z} := \mathbf{e}_1 z := e 1 if x ^ ≠ e 1 \widehat{\mathbf{x}} \ne\mathbf{e}_1 x = e 1 and z : = e 2 \mathbf{z} := \mathbf{e}_2 z := e 2 if x ^ = e 1 \widehat{\mathbf{x}} = \mathbf{e}_1 x = e 1 . Let I = { ( u i , τ i ) } i ∈ N I = \{(\mathbf{u}_i,\tau_i)\}_{i\in N} I = {( u i , τ i ) } i ∈ N . Every unqueried agent accepts exactly one lottery, the pure lottery z \mathbf{z} z , so it rejects x ^ \widehat{\mathbf{x}} x . All agents are nondegenerate: queried agents accept exactly the lotteries ( λ , 1 − λ , 0 , … , 0 ) (\lambda,1-\lambda,0,\ldots,0) ( λ , 1 − λ , 0 , … , 0 ) with λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] and reject e 3 \mathbf{e}_3 e 3 , which exists because m ≥ 3 m \ge3 m ≥ 3 , while each unqueried agent accepts only z \mathbf{z} z . All pairs are indicator vectors of proper subsets of alternatives with threshold 1, so they are normalized.
We claim that running A \mathcal{A} A on I \mathcal{I} I produces the same query history as the original run. We show by induction on t t t that the first t t t query–answer pairs agree, for every t t t up to the number of queries in the original run. The case t = 0 t=0 t = 0 is trivial. If the first t t t pairs agree, then, because A \mathcal{A} A is deterministic, its ( t + 1 ) (t+1) ( t + 1 ) -st query is the same in both runs, so the queried agent belongs to M M M . For agents in M M M , the answers under I \mathcal{I} I agree with the answer rule of the original run, so the ( t + 1 ) (t+1) ( t + 1 ) -st answer is also the same. Hence the entire query history is the same, and since A \mathcal{A} A is deterministic, it returns x ^ \hat{x} x ^ on I \mathcal{I} I .
Every agent in N ∖ M N \setminus M N ∖ M rejects x ^ \hat{x} x ^ , so viol I ( x ^ ) ≥ n − ∣ M ∣ \operatorname{viol}_{\mathcal{I}}(\hat{x}) \ge n-|M| viol I ( x ^ ) ≥ n − ∣ M ∣ . Every queried agent accepts z ∈ { e 1 , e 2 } z \in\{e_1,e_2\} z ∈ { e 1 , e 2 } , and every unqueried agent accepts z z z by construction, so viol I ( z ) = 0 \operatorname{viol}_{\mathcal{I}}(z)=0 viol I ( z ) = 0 and OPT ( I ) = 0 \operatorname{OPT}(\mathcal{I})=0 OPT ( I ) = 0 .
Proof of Theorem 6.2
Upper bound. Fix M ⊆ N M \subseteq N M ⊆ N with ∣ M ∣ = K |M|=K ∣ M ∣ = K . Consider the deterministic algorithm that queries only agents in M M M , recovers each of them, and returns a lottery x M x_M x M minimizing the number of violated agents in M M M , chosen by a fixed tie-breaking rule. This algorithm belongs to C K C_K C K . For any profile I \mathcal{I} I , let x ∗ x^* x ∗ be optimal for I \mathcal{I} I . Then x M x_M x M violates at most as many agents of M M M as x ∗ x^* x ∗ does, and at most n − K n-K n − K agents outside M M M , so viol I ( x M ) ≤ viol I ( x ∗ ) + ( n − K ) = OPT ( I ) + ( n − K ) \operatorname{viol}_{\mathcal{I}}(x_M) \le\operatorname{viol}_{\mathcal{I}}(x^*)+(n-K)=\operatorname{OPT}(\mathcal{I})+(n-K) viol I ( x M ) ≤ viol I ( x ∗ ) + ( n − K ) = OPT ( I ) + ( n − K ) . Hence inf A ∈ C K sup I ( viol I ( A ( I ) ) − OPT ( I ) ) ≤ n − K \inf_{\mathcal{A}\in C_K}\sup_{\mathcal{I}}(\operatorname{viol}_{\mathcal{I}}(\mathcal{A}(\mathcal{I}))-\operatorname{OPT}(\mathcal{I})) \le n-K inf A ∈ C K sup I ( viol I ( A ( I )) − OPT ( I )) ≤ n − K .
Lower bound. Fix any A ∈ C K \mathcal{A}\in C_K A ∈ C K and run it on the profile in which every agent has utility vector ( 1 , 1 , 0 , … , 0 ) (1,1,0,\ldots,0) ( 1 , 1 , 0 , … , 0 ) and threshold 1 1 1 ; its answers are exactly those of the answer rule in Theorem 6.1. Let M M M be the set of agents queried and x ^ \hat{x} x ^ the output. This profile satisfies the model assumptions, so ∣ M ∣ ≤ K |M|\le K ∣ M ∣ ≤ K . By Theorem 6.1 , there is a profile I \mathcal{I} I on which A \mathcal{A} A returns A ( I ) = x ^ \mathcal{A}(\mathcal{I})=\hat{x} A ( I ) = x ^ , every agent in N ∖ M N\setminus M N ∖ M rejects x ^ \hat{x} x ^ , and OPT ( I ) = 0 \operatorname{OPT}(\mathcal{I})=0 OPT ( I ) = 0 . Therefore viol I ( A ( I ) ) − OPT ( I ) = viol I ( x ^ ) ≥ n − ∣ M ∣ ≥ n − K \operatorname{viol}_{\mathcal{I}}(\mathcal{A}(\mathcal{I}))-\operatorname{OPT}(\mathcal{I})=\operatorname{viol}_{\mathcal{I}}(\hat{x})\ge n-|M|\ge n-K viol I ( A ( I )) − OPT ( I ) = viol I ( x ^ ) ≥ n − ∣ M ∣ ≥ n − K . The profile I \mathcal{I} I satisfies the model assumptions: it is nondegenerate by the proof of Theorem 6.1 , and since its utilities are binary and its thresholds equal 1 1 1 , it satisfies the finite-grid convention for every ε \varepsilon ε . Hence sup I ( viol I ( A ( I ) ) − OPT ( I ) ) ≥ n − K \sup_{\mathcal{I}}(\operatorname{viol}_{\mathcal{I}}(\mathcal{A}(\mathcal{I}))-\operatorname{OPT}(\mathcal{I}))\ge n-K sup I ( viol I ( A ( I )) − OPT ( I )) ≥ n − K for every A ∈ C K \mathcal{A}\in C_K A ∈ C K , which proves the claim.
Bounds After a Partial Query History
This appendix studies what can be said after an arbitrary query history, before all agents have been recovered: we bound the unknown optimum, and the worst-case loss of a chosen lottery, using only the answers observed so far.
Bounds from observed queries
Throughout this subsection, no finite-precision assumption is needed.
A partial query history is the set of accept/reject answers observed so far. We write it as a finite set h ⊆ N × Δ ( S ) × { 0 , 1 } h\subseteq N\times\Delta(S)\times\{0,1\} h ⊆ N × Δ ( S ) × { 0 , 1 } , where ( i , x , b ) ∈ h (i,x,b)\in h ( i , x , b ) ∈ h means that querying agent i i i on lottery x x x returned answer b b b . For each agent i ∈ N i\in N i ∈ N , let h i : = { ( x , b ) : ( i , x , b ) ∈ h } h_i:=\{(x,b):(i,x,b)\in h\} h i := {( x , b ) : ( i , x , b ) ∈ h } be the answers observed for agent i i i . We say that h ′ h' h ′ extends h h h if h ⊆ h ′ h\subseteq h' h ⊆ h ′ , and that h h h is consistent if there exists at least one profile satisfying our model whose answers reproduce every triple in h h h .
For each agent i i i , let Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) be the set of normalized pairs ( u , τ ) (u,\tau) ( u , τ ) , in the sense of Section 2, that agree with all observed answers, i.e., 1 { ⟨ u , x ⟩ ≥ τ } = b 1\{\langle u,x\rangle\ge\tau\}=b 1 {⟨ u , x ⟩ ≥ τ } = b for every ( x , b ) ∈ h i (x,b)\in h_i ( x , b ) ∈ h i . Thus Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) contains the pairs that remain possible for agent i i i , and h h h is consistent if and only if Θ i ( h i ) ≠ ∅ \Theta_i(h_i)\ne\varnothing Θ i ( h i ) = ∅ for every i ∈ N i\in N i ∈ N .
A profile I = ( ( u i , τ i ) ) i ∈ N \mathcal{I}=((u_i,\tau_i))_{i\in N} I = (( u i , τ i ) ) i ∈ N is consistent with h h h if ( u i , τ i ) ∈ Θ i ( h i ) (u_i,\tau_i)\in\Theta_i(h_i) ( u i , τ i ) ∈ Θ i ( h i ) for every i ∈ N i\in N i ∈ N ; we use viol I \operatorname{viol}_{\mathcal{I}} viol I and OPT ( I ) \operatorname{OPT}(\mathcal{I}) OPT ( I ) as in Section 6. The answers observed so far determine two sets of lotteries for each agent: A i ( h i ) : = { x ∈ Δ ( S ) : ⟨ u , x ⟩ ≥ τ for every ( u , τ ) ∈ Θ i ( h i ) } A_i(h_i):=\{x\in\Delta(S):\langle u,x\rangle\ge\tau\text{ for every }(u,\tau)\in\Theta_i(h_i)\} A i ( h i ) := { x ∈ Δ ( S ) : ⟨ u , x ⟩ ≥ τ for every ( u , τ ) ∈ Θ i ( h i )} and A ‾ i ( h i ) : = { x ∈ Δ ( S ) : ⟨ u , x ⟩ ≥ τ for some ( u , τ ) ∈ Θ i ( h i ) } \overline{A}_i(h_i):=\{x\in\Delta(S):\langle u,x\rangle\ge\tau\text{ for some }(u,\tau)\in\Theta_i(h_i)\} A i ( h i ) := { x ∈ Δ ( S ) : ⟨ u , x ⟩ ≥ τ for some ( u , τ ) ∈ Θ i ( h i )} . The first set contains the lotteries that agent i i i is guaranteed to accept given the observed answers, and the second contains those that agent i i i accepts under at least one consistent profile. If h h h is consistent, then Θ i ( h i ) ≠ ∅ \Theta_i(h_i)\ne\varnothing Θ i ( h i ) = ∅ , so A i ( h i ) ⊆ A ‾ i ( h i ) A_i(h_i)\subseteq\overline{A}_i(h_i) A i ( h i ) ⊆ A i ( h i ) , and if Θ i ( h i ) = { ( u i , τ i ) } \Theta_i(h_i)=\{(u_i,\tau_i)\} Θ i ( h i ) = {( u i , τ i )} , then both sets equal A i A_i A i .
For any lottery x ∈ Δ ( S ) x\in\Delta(S) x ∈ Δ ( S ) , define the lower and upper violation counts consistent with the observed answers as viol ‾ h ( x ) : = ∣ { i ∈ N : x ∉ A ‾ i ( h i ) } ∣ \underline{\operatorname{viol}}_h(x):=|\{i\in N:x\notin\overline{A}_i(h_i)\}| viol h ( x ) := ∣ { i ∈ N : x ∈ / A i ( h i )} ∣ and viol ‾ h ( x ) : = ∣ { i ∈ N : x ∉ A i ( h i ) } ∣ \overline{\operatorname{viol}}_h(x):=|\{i\in N:x\notin A_i(h_i)\}| viol h ( x ) := ∣ { i ∈ N : x ∈ / A i ( h i )} ∣ . The lower count viol ‾ h ( x ) \underline{\operatorname{viol}}_h(x) viol h ( x ) counts agents who must reject x x x under every profile still consistent with the observed answers, while the upper count viol ‾ h ( x ) \overline{\operatorname{viol}}_h(x) viol h ( x ) counts agents who could reject x x x under at least one consistent profile.
Theorem I.1. For every consistent query history h h h , every lottery x ∈ Δ ( S ) \mathbf{x} \in\Delta(S) x ∈ Δ ( S ) , and every profile I \mathcal{I} I consistent with h h h , viol ‾ h ( x ) ≤ viol I ( x ) ≤ viol ‾ h ( x ) \underline{\operatorname{viol}}_h(\mathbf{x}) \le\operatorname{viol}_{\mathcal{I}}(\mathbf{x}) \le\overline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) ≤ viol I ( x ) ≤ viol h ( x ) . Consequently, if L ( h ) : = min x ∈ Δ ( S ) viol ‾ h ( x ) L(h) := \min_{\mathbf{x}\in\Delta(S)} \underline{\operatorname{viol}}_h(\mathbf{x}) L ( h ) := min x ∈ Δ ( S ) viol h ( x ) and H ( h ) : = min x ∈ Δ ( S ) viol ‾ h ( x ) H(h) := \min_{\mathbf{x}\in\Delta(S)} \overline{\operatorname{viol}}_h(\mathbf{x}) H ( h ) := min x ∈ Δ ( S ) viol h ( x ) , then every profile I \mathcal{I} I consistent with h h h satisfies L ( h ) ≤ OPT ( I ) ≤ H ( h ) L(h) \le\operatorname{OPT}(\mathcal{I}) \le H(h) L ( h ) ≤ OPT ( I ) ≤ H ( h ) . Moreover, if x ^ h ∈ arg min x ∈ Δ ( S ) viol ‾ h ( x ) \widehat{\mathbf{x}}_h \in\arg\min_{\mathbf{x}\in\Delta(S)} \overline{\operatorname{viol}}_h(\mathbf{x}) x h ∈ arg min x ∈ Δ ( S ) viol h ( x ) , then viol I ( x ^ h ) ≤ OPT ( I ) + ( H ( h ) − L ( h ) ) \operatorname{viol}_{\mathcal{I}}(\widehat{\mathbf{x}}_h) \le\operatorname{OPT}(\mathcal{I}) + (H(h)-L(h)) viol I ( x h ) ≤ OPT ( I ) + ( H ( h ) − L ( h )) . In particular, if H ( h ) = L ( h ) H(h)=L(h) H ( h ) = L ( h ) , then x ^ h \widehat{\mathbf{x}}_h x h is optimal for every profile consistent with h h h .
Proof. Fix x ∈ Δ ( S ) \mathbf{x} \in\Delta(S) x ∈ Δ ( S ) and a profile I \mathcal{I} I consistent with h h h . For each agent i i i , we have ( u i , τ i ) ∈ Θ i ( h i ) (u_i,\tau_i) \in\Theta_i(h_i) ( u i , τ i ) ∈ Θ i ( h i ) . Therefore:
if x ∉ A ‾ i ( h i ) \mathbf{x} \notin\overline{A}_i(h_i) x ∈ / A i ( h i ) , then every pair in Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) rejects x \mathbf{x} x , so agent i i i rejects x \mathbf{x} x in profile I \mathcal{I} I ;
if x ∈ A ‾ i ( h i ) \mathbf{x} \in\underline{A}_i(h_i) x ∈ A i ( h i ) , then every pair in Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) accepts x \mathbf{x} x , so agent i i i accepts x \mathbf{x} x in profile I \mathcal{I} I .
Summing over agents gives viol ‾ h ( x ) ≤ viol I ( x ) ≤ viol ‾ h ( x ) \underline{\operatorname{viol}}_h(\mathbf{x}) \le\operatorname{viol}_{\mathcal{I}}(\mathbf{x}) \le\overline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) ≤ viol I ( x ) ≤ viol h ( x ) . Minimizing each side over x ∈ Δ ( S ) \mathbf{x} \in\Delta(S) x ∈ Δ ( S ) gives L ( h ) ≤ OPT ( I ) ≤ H ( h ) L(h) \le\operatorname{OPT}(\mathcal{I}) \le H(h) L ( h ) ≤ OPT ( I ) ≤ H ( h ) . Finally, viol I ( x ^ h ) ≤ viol ‾ h ( x ^ h ) = H ( h ) \operatorname{viol}_{\mathcal{I}}(\widehat{\mathbf{x}}_h) \le\overline{\operatorname{viol}}_h(\widehat{\mathbf{x}}_h)=H(h) viol I ( x h ) ≤ viol h ( x h ) = H ( h ) , and combining this with OPT ( I ) ≥ L ( h ) \operatorname{OPT}(\mathcal{I}) \ge L(h) OPT ( I ) ≥ L ( h ) gives viol I ( x ^ h ) − OPT ( I ) ≤ H ( h ) − L ( h ) \operatorname{viol}_{\mathcal{I}}(\widehat{\mathbf{x}}_h)-\operatorname{OPT}(\mathcal{I}) \le H(h)-L(h) viol I ( x h ) − OPT ( I ) ≤ H ( h ) − L ( h ) .
Proposition I.2. Let h ′ h' h ′ extend h h h , and assume that h ′ h' h ′ is consistent. Then, for every lottery x ∈ Δ ( S ) \mathbf{x} \in\Delta(S) x ∈ Δ ( S ) , viol ‾ h ( x ) ≤ viol ‾ h ′ ( x ) ≤ viol ‾ h ′ ( x ) ≤ viol ‾ h ( x ) \underline{\operatorname{viol}}_h(\mathbf{x}) \le\underline{\operatorname{viol}}_{h'}(\mathbf{x}) \le\overline{\operatorname{viol}}_{h'}(\mathbf{x}) \le\overline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) ≤ viol h ′ ( x ) ≤ viol h ′ ( x ) ≤ viol h ( x ) . Consequently, L ( h ) ≤ L ( h ′ ) ≤ H ( h ′ ) ≤ H ( h ) L(h) \le L(h') \le H(h') \le H(h) L ( h ) ≤ L ( h ′ ) ≤ H ( h ′ ) ≤ H ( h ) . In particular, the uncertainty gap H ( h ) − L ( h ) H(h)-L(h) H ( h ) − L ( h ) cannot increase as more queries are answered.
Proof. If h ′ h' h ′ extends h h h , then Θ i ( h i ′ ) ⊆ Θ i ( h i ) \Theta_i(h'_i) \subseteq\Theta_i(h_i) Θ i ( h i ′ ) ⊆ Θ i ( h i ) for every agent i i i . Thus, A ‾ i ( h i ) ⊆ A ‾ i ( h i ′ ) \underline{A}_i(h_i) \subseteq\underline{A}_i(h'_i) A i ( h i ) ⊆ A i ( h i ′ ) and A ‾ i ( h i ′ ) ⊆ A ‾ i ( h i ) \overline{A}_i(h'_i) \subseteq\overline{A}_i(h_i) A i ( h i ′ ) ⊆ A i ( h i ) . Therefore, for each fixed lottery x \mathbf{x} x , the set of agents for whom x \mathbf{x} x is not even possibly acceptable can only grow, while the set of agents for whom x \mathbf{x} x is guaranteed acceptable can only grow. Equivalently, viol ‾ h ( x ) \underline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) can only increase and viol ‾ h ( x ) \overline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) can only decrease. This proves the first inequality, and minimizing over x ∈ Δ ( S ) \mathbf{x} \in\Delta(S) x ∈ Δ ( S ) gives the second inequality.
A useful extreme case is an agent with no observed answers. If h i = ∅ h_i=\varnothing h i = ∅ , then Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) is the set of all normalized pairs. Thus, every lottery x ∈ Δ ( S ) \mathbf{x} \in\Delta(S) x ∈ Δ ( S ) is accepted by some pair in Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) and rejected by some (possibly different) pair in Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) : to accept x \mathbf{x} x , choose any j j j with x j > 0 x_j>0 x j > 0 and take u = e j u=e_j u = e j , τ = x j / 2 \tau=x_j/2 τ = x j /2 ; to reject x \mathbf{x} x , choose any ℓ \ell ℓ with x ℓ < 1 x_\ell<1 x ℓ < 1 (which exists because m ≥ 2 m\ge2 m ≥ 2 ) and take u = e ℓ u=e_\ell u = e ℓ , τ = ( x ℓ + 1 ) / 2 \tau=(x_\ell+1)/2 τ = ( x ℓ + 1 ) /2 . Both pairs are normalized, since their thresholds lie strictly between 0 and 1. Therefore A ‾ i ( h i ) = Δ ( S ) \overline{A}_i(h_i)=\Delta(S) A i ( h i ) = Δ ( S ) and A ‾ i ( h i ) = ∅ \underline{A}_i(h_i)=\varnothing A i ( h i ) = ∅ . So an unseen agent contributes 0 to viol ‾ h ( x ) \underline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) and 1 to viol ‾ h ( x ) \overline{\operatorname{viol}}_h(\mathbf{x}) viol h ( x ) for every lottery x \mathbf{x} x . In particular, if exactly K K K agents have nonempty histories, then viol ‾ h ( x ) − viol ‾ h ( x ) ≥ n − K \overline{\operatorname{viol}}_h(\mathbf{x})-\underline{\operatorname{viol}}_h(\mathbf{x})\ge n-K viol h ( x ) − viol h ( x ) ≥ n − K for every x ∈ Δ ( S ) \mathbf{x}\in\Delta(S) x ∈ Δ ( S ) , and thus H ( h ) − L ( h ) ≥ n − K H(h)-L(h)\ge n-K H ( h ) − L ( h ) ≥ n − K . This shows, for an arbitrary partial history, why unqueried agents drive the lower bound of Theorem 6.1.
The bound H ( h ) − L ( h ) H(h)-L(h) H ( h ) − L ( h ) for x ^ h \widehat{\mathbf{x}}_h x h can be loose. To state the exact worst-case additive gap of an arbitrary fixed lottery x \mathbf{x} x over all profiles consistent with h h h , define, for x , z ∈ Δ ( S ) \mathbf{x},\mathbf{z}\in\Delta(S) x , z ∈ Δ ( S ) ,
D h ( x , z ) : = ∑ i ∈ N max ( u , τ ) ∈ Θ i ( h i ) ( 1 { ⟨ u , x ⟩ < τ } − 1 { ⟨ u , z ⟩ < τ } ) . D_h(\mathbf{x},\mathbf{z}) := \sum_{i\in N} \max_{(u,\tau)\in\Theta_i(h_i)} \left(1\{\langle u,\mathbf{x}\rangle<\tau\}-1\{\langle u,\mathbf{z}\rangle<\tau\}\right). D h ( x , z ) := i ∈ N ∑ ( u , τ ) ∈ Θ i ( h i ) max ( 1 {⟨ u , x ⟩ < τ } − 1 {⟨ u , z ⟩ < τ } ) .
Theorem I.3. For every consistent query history h h h and every lottery x ∈ Δ ( S ) \mathbf{x}\in\Delta(S) x ∈ Δ ( S ) , the supremum of viol I ( x ) − OPT ( I ) \operatorname{viol}_{\mathcal{I}}(\mathbf{x})-\operatorname{OPT}(\mathcal{I}) viol I ( x ) − OPT ( I ) over all profiles I \mathcal{I} I consistent with h h h equals max z ∈ Δ ( S ) D h ( x , z ) \max_{\mathbf{z}\in\Delta(S)}D_h(\mathbf{x},\mathbf{z}) max z ∈ Δ ( S ) D h ( x , z ) . Consequently, the exact worst-case additive gap that any lottery can guarantee after observing h h h is min x ∈ Δ ( S ) max z ∈ Δ ( S ) D h ( x , z ) \min_{\mathbf{x}\in\Delta(S)}\max_{\mathbf{z}\in\Delta(S)}D_h(\mathbf{x},\mathbf{z}) min x ∈ Δ ( S ) max z ∈ Δ ( S ) D h ( x , z ) .
Proof. Fix x ∈ Δ ( S ) \mathbf{x}\in\Delta(S) x ∈ Δ ( S ) . For each agent i i i , the expression maximized in the i i i -th summand of D h D_h D h takes values in { − 1 , 0 , 1 } \{-1,0,1\} { − 1 , 0 , 1 } on the nonempty set Θ i ( h i ) \Theta_i(h_i) Θ i ( h i ) , so its maximum is attained; and since D h ( x , z ) D_h(\mathbf{x},\mathbf{z}) D h ( x , z ) is an integer in { − n , … , n } \{-n,\ldots,n\} { − n , … , n } , the maximum over z ∈ Δ ( S ) \mathbf{z}\in\Delta(S) z ∈ Δ ( S ) is attained as well. For the upper bound, let I \mathcal{I} I be any profile consistent with h h h , and let z I ∈ arg min z ∈ Δ ( S ) viol I ( z ) \mathbf{z}_{\mathcal{I}}\in\arg\min_{\mathbf{z}\in\Delta(S)}\operatorname{viol}_{\mathcal{I}}(\mathbf{z}) z I ∈ arg min z ∈ Δ ( S ) viol I ( z ) . Then viol I ( x ) − OPT ( I ) = viol I ( x ) − viol I ( z I ) \operatorname{viol}_{\mathcal{I}}(\mathbf{x})-\operatorname{OPT}(\mathcal{I})=\operatorname{viol}_{\mathcal{I}}(\mathbf{x})-\operatorname{viol}_{\mathcal{I}}(\mathbf{z}_{\mathcal{I}}) viol I ( x ) − OPT ( I ) = viol I ( x ) − viol I ( z I ) , which is the sum over i ∈ N i\in N i ∈ N of 1 { ⟨ u i , x ⟩ < τ i } − 1 { ⟨ u i , z I ⟩ < τ i } 1\{\langle u_i,\mathbf{x}\rangle<\tau_i\}-1\{\langle u_i,\mathbf{z}_{\mathcal{I}}\rangle<\tau_i\} 1 {⟨ u i , x ⟩ < τ i } − 1 {⟨ u i , z I ⟩ < τ i } . Since ( u i , τ i ) ∈ Θ i ( h i ) (u_i,\tau_i)\in\Theta_i(h_i) ( u i , τ i ) ∈ Θ i ( h i ) for every i i i , each summand is at most the corresponding summand in the definition of D h ( x , z I ) D_h(\mathbf{x},\mathbf{z}_{\mathcal{I}}) D h ( x , z I ) . Thus viol I ( x ) − OPT ( I ) ≤ D h ( x , z I ) ≤ max z ∈ Δ ( S ) D h ( x , z ) \operatorname{viol}_{\mathcal{I}}(\mathbf{x})-\operatorname{OPT}(\mathcal{I})\le D_h(\mathbf{x},\mathbf{z}_{\mathcal{I}})\le\max_{\mathbf{z}\in\Delta(S)}D_h(\mathbf{x},\mathbf{z}) viol I ( x ) − OPT ( I ) ≤ D h ( x , z I ) ≤ max z ∈ Δ ( S ) D h ( x , z ) , and taking the supremum over all profiles I \mathcal{I} I consistent with h h h gives one direction of the claimed equality.
For the reverse inequality, let z ∗ ∈ arg max z ∈ Δ ( S ) D h ( x , z ) \mathbf{z}^*\in\arg\max_{\mathbf{z}\in\Delta(S)}D_h(\mathbf{x},\mathbf{z}) z ∗ ∈ arg max z ∈ Δ ( S ) D h ( x , z ) . For each agent i i i , choose ( u i ∗ , τ i ∗ ) ∈ Θ i ( h i ) (u_i^*,\tau_i^*)\in\Theta_i(h_i) ( u i ∗ , τ i ∗ ) ∈ Θ i ( h i ) attaining the maximum in the i i i -th summand of D h ( x , z ∗ ) D_h(\mathbf{x},\mathbf{z}^*) D h ( x , z ∗ ) . Since the consistency constraints are separate across agents, these choices combine into a profile I ∗ : = ( ( u i ∗ , τ i ∗ ) ) i ∈ N \mathcal{I}^* := ((u_i^*, \tau_i^*))_{i \in\mathbb{N}} I ∗ := (( u i ∗ , τ i ∗ ) ) i ∈ N that is consistent with h h h . By construction, viol I ∗ ( x ) − viol I ∗ ( z ∗ ) = D h ( x , z ∗ ) \operatorname{viol}_{\mathcal{I}^*}(x) - \operatorname{viol}_{\mathcal{I}^*}(z^*) = D_h(x,z^*) viol I ∗ ( x ) − viol I ∗ ( z ∗ ) = D h ( x , z ∗ ) . Since OPT ( I ∗ ) ≤ viol I ∗ ( z ∗ ) \operatorname{OPT}(\mathcal{I}^*) \le\operatorname{viol}_{\mathcal{I}^*}(z^*) OPT ( I ∗ ) ≤ viol I ∗ ( z ∗ ) , we get viol I ∗ ( x ) − OPT ( I ∗ ) ≥ D h ( x , z ∗ ) = max z ∈ Δ ( S ) D h ( x , z ) \operatorname{viol}_{\mathcal{I}^*}(x) - \operatorname{OPT}(\mathcal{I}^*) \ge D_h(x,z^*) = \max_{z \in\Delta(S)} D_h(x,z) viol I ∗ ( x ) − OPT ( I ∗ ) ≥ D h ( x , z ∗ ) = max z ∈ Δ ( S ) D h ( x , z ) . Combining with the upper bound proves the claim.
This suggests a query rule: choose the next query so as to minimize the largest value that min x max z D h ( x , z ) \min_x \max_z D_h(x,z) min x max z D h ( x , z ) can take after the answer. Such a rule targets the MIN-VIOL objective directly, rather than learning each agent’s halfspace separately.
Details of the Synthetic Experiments
The experiments measure how far the worst-case guarantees are from the behavior of the algorithms on random instances.
Populations. For each of two settings, we generated 20 independent populations with n = 500 n = 500 n = 500 agents and m = 3 m = 3 m = 3 alternatives. In each population, the planted lottery x x x was drawn uniformly from Δ ( S ) \Delta(S) Δ ( S ) . Each agent’s utilities were 3 independent uniform values on [ 0 , 1 ] [0,1] [ 0 , 1 ] , rescaled so that the smallest is 0 and the largest is 1; this gives the normalized pair of Section 2, in which margins are measured. For 425 agents (85%), τ i \tau_i τ i is U i ( x ) U_i(x) U i ( x ) minus a margin drawn uniformly from [ 0.05 , 0.25 ] [0.05,0.25] [ 0.05 , 0.25 ] in the separated setting and from [ 0 , 0.05 ) [0,0.05) [ 0 , 0.05 ) in the near-threshold setting, so these agents accept x x x . For the other 75 agents, τ i \tau_i τ i is U i ( x ) U_i(x) U i ( x ) plus an amount drawn uniformly from [ 0.05 , 0.25 ] [0.05,0.25] [ 0.05 , 0.25 ] , so they reject x x x . An agent whose threshold fell outside ( 0 , 1 ) (0,1) ( 0 , 1 ) was drawn again. Hence B 0.05 ( x ) = ∅ B_{0.05}(x) = \varnothing B 0.05 ( x ) = ∅ in the separated setting, whereas in the near-threshold setting B 0.05 ( x ) B_{0.05}(x) B 0.05 ( x ) consists of all 425 accepting agents, and B 0.02 ( x ) B_{0.02}(x) B 0.02 ( x ) of about 169 of them on average. The planted lottery was optimal in every near-threshold population (OPT = 75 \operatorname{OPT} = 75 OPT = 75 ); in the separated setting, OPT \operatorname{OPT} OPT was between 71 and 75.
Computing the optimum. Since m = 3 m = 3 m = 3 , we computed OPT \operatorname{OPT} OPT exactly by checking all candidate lotteries formed by the edges of the simplex and the agents’ acceptance boundaries, i.e., the vertex enumeration of Theorem 4.1 . We compared this exact solver with a mixed-integer program that has one binary variable per agent, indicating whether the agent’s constraint may be violated, on all 40 populations and on all 240 samples of size k = 120 k = 120 k = 120 described below; the optimal values agreed in every case.
Sampling and exact minimization. For each population and each sample size k ∈ { 30 , 120 , 480 } k \in\{30, 120, 480\} k ∈ { 30 , 120 , 480 } , we drew 6 independent samples of k k k agents uniformly with replacement, minimized the number of rejecting sampled agents exactly, and measured the extra rejection rate ( viol ( x ^ ) − OPT ) / n (\operatorname{viol}(\hat{x}) - \operatorname{OPT})/n ( viol ( x ^ ) − OPT ) / n on all 500 agents. As in Section 5, the normalized pairs of the sampled agents are taken as recovered; we did not simulate the membership queries. Among the minimizers on the sample, vertex enumeration returns the first minimizing vertex it finds; Theorem 5.1 applies to every minimizer. Table 1 reports the mean over all populations and samples and the 95th percentile. For comparison, with m = 3 m = 3 m = 3 and k ≤ 480 k \le480 k ≤ 480 , the explicit bound of Theorem 5.1 exceeds n n n for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , whereas the observed mean extra rejection rate is below 2% from k = 120 k = 120 k = 120 on.
The LP. Theorem 5.3 contains an unspecified absolute constant, so we did not evaluate its bound numerically. Instead, we separated the error caused by the LP from the error caused by sampling: we ran the LP with η ∈ { 0.02 , 0.05 } \eta\in\{0.02, 0.05\} η ∈ { 0.02 , 0.05 } on all 500 agents and on the same samples of k = 120 k = 120 k = 120 agents used for exact minimization (Table 1). In the bound of Theorem 5.3 , a larger η \eta η reduces the factor 1 + 1 / η 1 + 1/\eta 1 + 1/ η and the sampling term but enlarges B η ( x ) B_\eta(x) B η ( x ) , and the results follow this trade-off. In the separated setting, where B 0.05 ( x ) = ∅ B_{0.05}(x) = \varnothing B 0.05 ( x ) = ∅ for the planted lottery x x x , increasing η \eta η from 0.02 to 0.05 lowered the mean extra rejection rate from 0.51% to 0.28% on all agents and from 1.96% to 0.53% on the samples, below the 1.67% of exact minimization on the same samples. This is possible because exact minimization returns a vertex, which typically lies on the boundary of some sampled agents’ acceptable sets, whereas the LP favors lotteries that the sampled agents accept with margin. In the near-threshold setting, where B 0.05 ( x ) B_{0.05}(x) B 0.05 ( x ) contains every accepting agent, increasing η \eta η raised the rate from 1.86% to 5.22% on all agents and from 3.60% to 9.20% on the samples. Thus the LP can be more accurate than exact minimization when the agents who accept a good lottery do so with a clear margin, but it loses accuracy when many of them are close to their thresholds and η \eta η is too large. The guarantee of exact minimization does not depend on margins, which is why we prefer it when it is affordable (Section 5.1).
Querying K K K agents. For each population and each K ∈ { 10 , 25 , 50 , 100 , 200 , 400 } K \in\{10, 25, 50, 100, 200, 400\} K ∈ { 10 , 25 , 50 , 100 , 200 , 400 } , we chose K K K distinct agents uniformly at random 6 times, minimized the number of violations among them exactly, and measured the additive gap among all 500 agents. For K = 100 K = 100 K = 100 , the mean gap was 8.46 agents in the separated setting and 7.99 agents in the near-threshold setting, that is, 2.11% and 2.00% of the worst-case value n − K = 400 n - K = 400 n − K = 400 . Table 3 gives all values: the mean gap was between 0.57% and 19.17% of n − K n - K n − K , and the largest gap in any single run was 202 agents, or 41% of n − K n - K n − K (with K = 10 K = 10 K = 10 ). We also implemented the profile constructed in the proof of Theorem 6.1 for the algorithm that recovers K K K fixed agents and minimizes the number of violations among them; on it, the gap was exactly n − K n - K n − K for every tested K K K .
Table 3. Mean additive gap viol ( x ^ ) − O P T \operatorname{viol}(\widehat{x}) - \mathrm{OPT} viol ( x ) − OPT of exact minimization over K K K distinct agents chosen uniformly at random, as a percentage of the worst-case value n − K n - K n − K , with n = 500 n = 500 n = 500 and m = 3 m = 3 m = 3 .
Few alternatives. With n = 1000 n = 1000 n = 1000 , m = 500 m = 500 m = 500 , and η = 0.15 \eta= 0.15 η = 0.15 , Theorem 4.2 gives s η = ⌈ log ( 2000 ) / 0.045 ⌉ = 169 s_\eta= \lceil\log(2000)/0.045\rceil= 169 s η = ⌈ log ( 2000 ) /0.045 ⌉ = 169 . In each of 480 trials, we drew a new population: each agent’s utilities were 500 independent uniform values on [ 0 , 1 ] [0, 1] [ 0 , 1 ] , rescaled as above, and the starting lottery x x x was drawn uniformly from Δ ( S ) \Delta(S) Δ ( S ) , so that it uses every alternative. Every agent accepts x x x : τ i \tau_i τ i is U i ( x ) U_i(x) U i ( x ) minus a margin drawn uniformly from [ η , η + 0.05 ] [\eta, \eta+ 0.05] [ η , η + 0.05 ] , so that B η ( x ) = ∅ B_\eta(x) = \varnothing B η ( x ) = ∅ . In a harder setting, the margins of 20% of the agents were instead drawn uniformly from [ 0 , η ) [0, \eta) [ 0 , η ) , so that ∣ B η ( x ) ∣ = 200 \lvert B_\eta(x)\rvert= 200 ∣ B η ( x )∣ = 200 . For s ∈ { 50 , 169 } s \in\{50, 169\} s ∈ { 50 , 169 } , we drew s s s alternatives independently from x x x , took their empirical distribution as in the proof of Theorem 4.2 , and counted the agents who reject it. When B η ( x ) = ∅ B_\eta(x) = \varnothing B η ( x ) = ∅ , sampling 169 alternatives created no new rejection in any trial; in fact, no agent’s expected utility dropped by more than η \eta η in any trial, whereas the proof guarantees this only with probability at least 1 / 2 1/2 1/2 . Sampling only 50 alternatives created no new rejection in 471 of the 480 trials and one new rejection in each of the others. In the harder setting, the mean new rejection rate was 1.19% with 169 alternatives (95th percentile 1.70%) and 2.19% with 50 alternatives (95th percentile 3.00%), whereas Theorem 4.2 allows up to ∣ B η ( x ) ∣ / n = 20 % \lvert B_\eta(x)\rvert/n = 20\% ∣ B η ( x )∣ / n = 20% .
Implementation and compute. We used Python 3.13 with NumPy and SciPy, both distributed under the BSD 3-Clause license, and solved the LP and the mixed-integer program with the HiGHS solver (MIT license) in SciPy. In floating point, agent i i i counts as accepting x x x if U i ( x ) ≥ τ i − 10 − 9 U_i(x) \ge\tau_i - 10^{-9} U i ( x ) ≥ τ i − 1 0 − 9 . All random draws use fixed seeds. All instances are small (n ≤ 1000 n \le1000 n ≤ 1000 and m ≤ 500 m \le500 m ≤ 500 ): on a cloud virtual machine with 2 Intel Xeon vCPUs at 2.1 GHz and 8 GB of memory, and no GPU, all experiments together take about 2 minutes, of which about 80 seconds are spent on the mixed-integer check. Source files are available at https://github.com/niceth/Learning-Lotteries-Minimal-Stakeholder-Violations.