betaFeedback

WorksComputer Science

Learning Lotteries with Minimal Stakeholder Violations from Membership Queries

Abstract

An AI developer often has several candidate versions of a system and can deploy a mixture of them, sending each request to a randomly chosen version, as in A/B testing. Each stakeholder (e.g., a safety team, a regulator, or a customer with private test data) accepts a mixture exactly when its expected performance (e.g., its rate of harmful replies) meets the stakeholder's own standard, which the developer can learn only by asking whether a proposed mixture is acceptable. We model this as choosing a lottery over mm alternatives for nn agents, each of whom accepts exactly the lotteries in an unknown halfspace and answers such binary membership queries. While Choo et al. (ICML 2026) sought a lottery that every agent accepts, none may exist when, say, safety and helpfulness requirements conflict, so we minimize the number of rejecting agents. We show that this problem is APX-hard even when all halfspaces are known and all utilities are 00 or 11. We then give exact algorithms that run in polynomial time when mm is constant, and in quasi-polynomial time when, for a constant ηη, some optimal lottery has no accepting agent within ηη of its threshold. When only some agents can be queried, optimizing over a uniform sample of agents gives additive and relative guarantees for the whole population, with a sample size that does not depend on nn, and a linear program gives a polynomial-time method for any mm. On the other hand, for m≥3m\ge 3, a deterministic algorithm that queries only KK distinct agents cannot guarantee fewer than n−Kn-K extra rejections, and this is achievable; in other words, it can guarantee nothing for the agents it does not ask. Small synthetic experiments indicate that our worst-case bounds are conservative on random instances.

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 mm 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 mm. For larger mm, 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) 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≥mk \ge m agents are sampled uniformly at random and their halfspaces are recovered, then, with probability at least 1−δ1-\delta, any lottery that minimizes the number of rejecting sampled agents has at most OPT+O(nmlog⁡(ek/m)+log⁡(1/δ)k)\mathrm{OPT} + O\left(n\sqrt{\frac{m\log(ek/m)+\log(1/\delta)}{k}}\right) violations, where OPT is the minimum number of violations (Theorem 5.1). Put another way, for an error that is a given fraction of nn, the number of agents to ask does not depend on nn: a developer with a million customers need not ask more of them than one with a thousand. If OPT≥ρn\mathrm{OPT} \ge\rho n, then O((mlog⁡(1/ρ)+log⁡(1/δ))/(ζ2ρ))O((m\log(1/\rho)+\log(1/\delta))/(\zeta^2\rho)) samples give a (1+ζ)(1+\zeta)-approximation (Theorem 5.2).

A polynomial-time linear program for any number of alternatives. For large mm, 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}, its output has at most (1+1/η)(1+1/\eta) times as many violations as x\mathbf{x}, plus the number of agents who accept xx 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) (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≥3m \ge3, it cannot: every deterministic algorithm that queries only KK distinct agents may leave n−Kn-K more agents unsatisfied than the optimum, however many queries it spends on them (Theorem 6.1), and optimizing over a fixed set of KK 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−Kn-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).

WorkDomainInformationObjectiveGuarantees
MAX-FS and MIN-ULR [6, 7, 12, 8]Rd\mathbb{R}^{d}, general linear systemsExplicitMaximize satisfied, or minimize unsatisfied, constraintsNP-hardness, approximation algorithms, inapproximability
MAX-FS with 0/1 coefficients [36]Real variablesExplicitMaximize satisfied constraintsApproximation algorithms and hardness
LP with violations [57, 31]Rd\mathbb{R}^{d}, dd fixedExplicitBest linear objective when a given number of constraints may be violatedExact algorithms in fixed dimension
MAX-FS with additive slack [30]SimplexExplicitMaximize constraints satisfied up to an additive slackQuasi-polynomial algorithm; lower bound under ETH
Chance-constrained and scenario optimization [28, 29, 53, 63]Convex or general setsSamples of random constraintsOptimize a cost subject to a small violation probabilitySample sizes for feasibility of sampled solutions
Unanimous lotteries [33]SimplexMembership queriesA lottery accepted by all agents, or report that none existsQuery upper and lower bounds; NP-hardness of maximizing accepting agents
Violation distances [70]SimplexMembership queriesMinimize a power mean of the distances to violated agents’ acceptance boundariesWhen queries determine these distances; exact and sampling-based algorithms; lower bound for deterministic algorithms
This paperSimplexMembership queries (explicit in § 3–§ 4)Minimize the number of rejecting agentsAPX-hardness; exact and parameterized algorithms; sampling guarantees; LP; exact deterministic value n−Kn-K

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 2log⁡1−cn2^{\log^{1-c} n} for any constant c>0c > 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 nn agents have been recovered, at a cost of nn 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≥2m \ge2 be the number of alternatives and n≥1n \ge1 the number of agents. For an integer z≥1z \ge1, write [z]:={1,…,z}[z] := \{1,\ldots,z\}. Let N:=[n]N := [n] be the set of agents and S:={s1,…,sm}S := \{s_1,\ldots,s_m\} the set of alternatives. A lottery is a probability vector x=(x1,…,xm)∈Δ(S):={x∈R≥0m:∑j=1mxj=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\}, where xjx_j is the probability of sjs_j; the pure lottery on sjs_j is the standard basis vector ej\mathbf{e}_j. We write ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle for the standard inner product on Rm\mathbb{R}^{m}, and log⁡\log for the natural logarithm.

Agents. Agent i∈Ni \in N accepts exactly the lotteries in its acceptable set Ai={x∈Δ(S):⟨ui,x⟩≥τi}A_i = \{\mathbf{x} \in\Delta(S) : \langle\mathbf{u}_i,\mathbf{x}\rangle\ge\tau_i\}, where ui∈[0,1]m\mathbf{u}_i \in[0,1]^m gives agent ii’s utility ui(sj)u_i(s_j) for each alternative and τi\tau_i is its threshold. We write Ui(x):=⟨ui,x⟩U_i(\mathbf{x}) := \langle\mathbf{u}_i,\mathbf{x}\rangle for the expected utility. Thus AiA_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., ∅≠Ai⊊Δ(S)\varnothing\ne A_i \subsetneq\Delta(S). Membership queries reveal AiA_i but not the pair (ui,τi)(\mathbf{u}_i,\tau_i): since ⟨1,x⟩=1\langle\mathbf{1},\mathbf{x}\rangle= 1 on Δ(S)\Delta(S), the pair (λui+μ1,λτi+μ)(\lambda\mathbf{u}_i + \mu\mathbf{1},\lambda\tau_i+\mu) gives the same set AiA_i for every λ>0\lambda> 0 and μ∈R\mu\in\mathbb{R}. Margins Ui(x)−τiU_i(\mathbf{x})-\tau_i are therefore meaningful only after fixing a normalization. If AiA_i has nonempty relative interior in Δ(S)\Delta(S), we use the unique pair with min⁡jui(sj)=0\min_j u_i(s_j)=0 and max⁡jui(sj)=1\max_j u_i(s_j)=1. Otherwise, AiA_i consists of the lotteries that put all probability on some nonempty proper subset of alternatives, and we let ui\mathbf{u}_i be the indicator vector of that subset and τi=1\tau_i=1 (Lemma B.1). From now on, (ui,τi)(\mathbf{u}_i,\tau_i) denotes this normalized pair; thus ui∈[0,1]m\mathbf{u}_i \in[0,1]^m and τi∈(0,1]\tau_i \in(0,1].

Membership queries. A query (i,x)∈N×Δ(S)(i,\mathbf{x}) \in N \times\Delta(S) returns Query⁡(i,x)=1\operatorname{Query}(i,\mathbf{x}) = 1 if agent ii accepts x\mathbf{x} and 00 otherwise; no utility or threshold is observed. We write QQ for the total number of queries and KK 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: ui(sj)∈{ε,2ε,…,1}u_i(s_j) \in\{\varepsilon,2\varepsilon,\ldots,1\} and τi∈{ε,2ε,…,1}\tau_i \in\{\varepsilon,2\varepsilon,\ldots,1\}, where ε∈(0,1/2]\varepsilon\in(0,1/2] and 1/ε1/\varepsilon is an integer. The lottery is not discretized: the decision maker may propose any point of Δ(S)\Delta(S). Under this convention, the halfspace recovery routine of Choo et al. [2026b] finds an agent’s normalized pair with Tε=O(mlog⁡(1/ε))T_\varepsilon= O(m\log(1/\varepsilon)) queries; we call this recovering the agent. Appendix § 11.§ 2 explains why some such assumption is needed for exact recovery.

References

  1. [1]Atila Abdulkadiroğlu and Tayfun Sönmez. School choice: A mechanism design approach. American Economic Review, 93(3):729–747, 2003.DOI
  2. [2]Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 60–69, 2018.arxiv.org/abs/1803.02453
  3. [3]Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning-augmented mechanism design: Leveraging predictions for facility location. Mathematics of Operations Research, 49(4):2626–2651, 2024.
  4. [5]Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theoretical Computer Science, 237(1–2):123–134, 2000.DOI
  5. [6]Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147(1–2):181–210, 1995.DOI
  6. [7]Edoardo Amaldi and Viggo Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(1–2):237–260, 1998.DOI
  7. [8]Edoardo Amaldi, Marc E. Pfetsch, and Leslie E. Trotter, Jr. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Mathematical Programming, 95:533–554, 2003.DOI
  8. [10]Francis J. Anscombe and Robert J. Aumann. A definition of subjective probability. The Annals of Mathematical Statistics, 34(1):199–205, 1963.DOI
  9. [11]Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
  10. [12]Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317–331, 1997.
  11. [13]Haris Aziz, Anna Bogomolnaia, and Hervé Moulin. Fair mixing: The case of dichotomous preferences. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 753–781, 2019.
  12. [14]Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022.arxiv.org/abs/2204.05862
  13. [15]Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS), pages 11:1–11:22, 2023.arxiv.org/abs/2209.04058
  14. [17]Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. Proportionally fair online allocation of public goods with predictions. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 20–28, 2023.arxiv.org/abs/2209.15305
  15. [18]Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, 2002.DOI
  16. [19]Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138–156, 2006.DOI
  17. [20]Viktor Bengs, Röbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22:1–108, 2021.
  18. [21]Ben Berger, Michal Feldman, Vasilis Gkatzelis, and Xizhi Tan. Learning-augmented metric distortion via (p, q)-veto core. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), page 984, 2024.
  19. [22]Anna Bogomolnaia and Hervé Moulin. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295–328, 2001.DOI
  20. [24]Craig Boutilier, Relu Patrascu, Pascal Poupart, and Dale Schuurmans. Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence, 170(8–9):686–713, 2006.DOI
  21. [25]Felix Brandt. Rolling the dice: Recent results in probabilistic social choice. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 1, pages 3–26. AI Access, 2017.
  22. [26]Darius Braziunas and Craig Boutilier. Elicitation of factored utilities. AI Magazine, 29(4):79–92, 2008.DOI
  23. [27]Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011.
  24. [28]Giuseppe C. Calafiore and Marco C. Campi. The scenario approach to robust control design. IEEE Transactions on Automatic Control, 51(5):742–753, 2006.DOI
  25. [29]Marco C. Campi and Simone Garatti. The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 19(3):1211–1230, 2008.DOI
  26. [30]Matteo Castiglioni, Andrea Celli, and Nicola Gatti. Public Bayesian persuasion: Being almost optimal and almost persuasive. Algorithmica, 85:2885–2921, 2023.arxiv.org/abs/2002.05156
  27. [31]Timothy M. Chan. Low-dimensional linear programming with violations. SIAM Journal on Computing, 34(4):879–893, 2005.
  28. [33]Davin Choo, Paul W. Goldberg, and Nicholas Teh. Learning unanimously acceptable lotteries via queries. In Proceedings of the 43rd International Conference on Machine Learning (ICML), pages 20451–20493, 2026b. Extended version available as arXiv:2604.17505.arxiv.org/abs/2604.17505
  29. [36]Khaled Elbassioni, Rajiv Raman, Saurabh Ray, and René Sitters. On the approximability of the maximum feasible subsystem problem with 0/1-coefficients. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1210–1219, 2009.
  30. [37]Edith Elkind, Matthias Greger, Patrick Lederer, Warut Suksompong, and Nicholas Teh. Settling the score: Portioning with cardinal preferences. Artificial Intelligence, 352:104487, 2026.
  31. [38]European Union. Regulation (EU) 2024/1689 laying down harmonised rules on artificial intelligence (Artificial Intelligence Act). Official Journal of the European Union, L series, 2024. 12 July 2024.
  32. [39]Martin A. Fischler and Robert C. Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24 (6):381–395, 1981.
  33. [40]Peter C. Fishburn. The Foundations of Expected Utility, volume 31 of Theory and Decision Library. D. Reidel, Dordrecht, 1982.DOI
  34. [41]Rupert Freeman and Ulrike Schmidt-Kraepelin. Project-fair and truthful mechanisms for budget aggregation. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9704–9712, 2024.
  35. [42]Rupert Freeman, David M. Pennock, Dominik Peters, and Jennifer Wortman Vaughan. Truthful aggregation of budget proposals. Journal of Economic Theory, 193:105234, 2021.
  36. [43]Itzhak Gilboa and David Schmeidler. Maxmin expected utility with non-unique prior. Journal of Mathematical Economics, 18(2):141–153, 1989. doi: 10.1016/0304-4068(89)90018-9.DOI
  37. [44]Tarleton Gillespie. Custodians of the Internet: Platforms, Content Moderation, and the Hidden Decisions That Shape Social Media. Yale University Press, 2018.
  38. [45]Robert Gorwa, Reuben Binns, and Christian Katzenbach. Algorithmic content moderation: Technical and political challenges in the automation of platform governance. Big Data & Society, 7(1), 2020.DOI
  39. [46]Steve Hanneke. Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 7(2–3):131–309, 2014.
  40. [47]Eduard Helly. Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahresbericht der Deutschen Mathematiker-Vereinigung, 32:175–176, 1923.
  41. [49]Aanund Hyland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293–314, 1979.
  42. [50]Daniel Kahneman and Amos Tversky. Prospect theory: An analysis of decision under risk. Econometrica, 47(2):263–292, 1979. doi: 10.2307/1914185.DOI
  43. [51]Ron Kohavi, Diane Tang, and Ya Xu. Trustworthy Online Controlled Experiments: A Practical Guide to A/B Testing. Cambridge University Press, 2020.
  44. [53]James Luedtke and Shabbir Ahmed. A sample approximation approach for optimization with probabilistic constraints. SIAM Journal on Optimization, 19(2):674–699, 2008.DOI
  45. [54]Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):24:1–24:25, 2021.arxiv.org/abs/1802.05399
  46. [55]Mark J. Machina. “Expected Utility” Analysis without the Independence Axiom. Econometrica, 50 (2):277–323, 1982. doi: 10.2307/1912631.DOI
  47. [56]Harry Markowitz. Portfolio selection. The Journal of Finance, 7(1):77–91, 1952. doi: 10.1111/j.1540-6261.1952.tb01525.x.DOI
  48. [57]Jiří Matoušek. On geometric optimization with few violated constraints. Discrete & Computational Geometry, 14:365–384, 1995.
  49. [58]Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 646–662. Cambridge University Press, 2021.
  50. [62]Tzeh Yuan Neoh, Nicholas Teh, Je Qin Chooi, Paul W. Goldberg, and Milind Tambe. Efficient ensemble selection from binary and pairwise feedback. arXiv:2605.09588, 2026b.arxiv.org/abs/2605.09588
  51. [63]Bernardo K. Pagnoncelli, Shabbir Ahmed, and Alexander Shapiro. Sample average approximation method for chance constrained programming: Theory and applications. Journal of Optimization Theory and Applications, 142:399–416, 2009.DOI
  52. [64]Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 9661–9670, 2018.
  53. [65]John Quiggin. A theory of anticipated utility. Journal of Economic Behavior & Organization, 3(4): 323–343, 1982. doi: 10.1016/0167-2681(82)90008-7.DOI
  54. [66]Paul Röttger, Hannah Kirk, Bertie Vidgen, Giuseppe Attanasio, Federico Bianchi, and Dirk Hovy. XSTest: A test suite for identifying exaggerated safety behaviours in large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL), pages 5377–5400, 2024.
  55. [67]Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
  56. [69]Warut Suksompong and Nicholas Teh. Voting in divisible settings: A survey. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 39789–39796, 2026.
  57. [70]Nicholas Teh and Paul W. Goldberg. Learning acceptable lotteries via queries: Minimizing aggregated violation distances. In Advances in Neural Information Processing Systems (NeurIPS), 2026. To appear.arxiv.org/abs/2604.17505
  58. [72]Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998.
  59. [73]John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.
  60. [74]Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 571–577, 2022.arxiv.org/abs/2205.11313

Paper details

vlnc:W_88mdwe8q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents