Learning Unanimously Acceptable Lotteries via Queries

• URL: http://arxiv.org/abs/2604.17505v1
• Date: Sun, 19 Apr 2026 15:51:59 GMT
• Title: Learning Unanimously Acceptable Lotteries via Queries
• Abstract summary: We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback.<n>We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility.<n>We develop learning-augmented algorithms that exploit natural forms of advice.
• Score: 17.857261852690346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.

Related papers

• How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings? [58.740078141879984]
  Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on.<n>Recent work in causality-based domain generalization has shown how shared causal structure can induce invariant predictors.<n>In this paper, we study when full or partial causal knowledge can provably improve supervised domain adaptation.
  arXiv  Detail & Related papers  (2026-06-10T21:07:49Z)
• Smooth Partial Lotteries for Stable Randomized Selection [61.86327960322782]
  Many organizations have adopted partial lotteries, which randomize selection based on evaluation scores.<n>Existing lottery designs are inherently unstable, as a small change to a single candidate's score can cause large shifts in selection probabilities.<n>We propose smoothness as a design principle for partial lotteries, formalizing it as a Lipschitz condition on the mapping from review scores over candidates to selection probabilities.
  arXiv  Detail & Related papers  (2026-05-19T16:22:51Z)
• Consistency of Selection Strategies for Fraud Detection [0.0]
  We study how insurers can chose which claims to investigate for fraud.<n>We argue that this can lead to inconsistent learning and propose a randomized alternative.
  arXiv  Detail & Related papers  (2025-09-23T07:33:33Z)
• Improved Regret Bounds for Online Fair Division with Bandit Learning [0.0]
  We study online fair division when there are a finite number of item types and the player values for the items are drawn randomly from distributions with unknown means.<n>In this setting, a sequence of indivisible items arrives according to a random online process, and each item must be allocated to a single player.<n>We show that it is possible to with high probability guarantee proportionality constraint satisfaction and achieve $tildeO(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2025-01-13T02:48:58Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• High-Dimensional Prediction for Sequential Decision Making [9.684829814477526]
  We study the problem of making predictions of an adversarially chosen high-dimensional state that are unbiased subject to an arbitrary collection of conditioning events. We give efficient algorithms for solving this problem, as well as a number of applications that stem from choosing an appropriate set of conditioning events.
  arXiv  Detail & Related papers  (2023-10-26T17:59:32Z)
• High-Probability Risk Bounds via Sequential Predictors [20.741036493022442]
  We show that online to batch conversions applied to general online learning algorithms can bypass regret bounds. We obtain nearly optimal high-probability risk bounds for several classical statistical estimation problems. Our analysis relies on the fact that many online learning algorithms are improper, as they are not restricted to use predictors from a given reference class.
  arXiv  Detail & Related papers  (2023-08-15T06:19:31Z)
• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  A fundamental problem in robust learning is asymmetry: a learner needs to correctly classify every one of exponentially-many perturbations that an adversary might make to a test-time natural example. In contrast, the attacker only needs to find one successful perturbation. We introduce a novel multi-group setting and introduce a novel multi-robust learning problem.
  arXiv  Detail & Related papers  (2023-03-15T21:30:14Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Root-finding Approaches for Computing Conformal Prediction Set [18.405645120971496]
  Conformal prediction constructs a confidence region for an unobserved response of a feature vector based on previous identically distributed and exchangeable observations. We exploit the fact that, emphoften, conformal prediction sets are intervals whose boundaries can be efficiently approximated by classical root-finding software.
  arXiv  Detail & Related papers  (2021-04-14T06:41:12Z)
• Batched Neural Bandits [107.5072688105936]
  BatchNeuralUCB combines neural networks with optimism to address the exploration-exploitation tradeoff. We prove that BatchNeuralUCB achieves the same regret as the fully sequential version while reducing the number of policy updates considerably.
  arXiv  Detail & Related papers  (2021-02-25T17:36:44Z)
• Adaptive Combinatorial Allocation [77.86290991564829]
  We consider settings where an allocation has to be chosen repeatedly, returns are unknown but can be learned, and decisions are subject to constraints. Our model covers two-sided and one-sided matching, even with complex constraints.
  arXiv  Detail & Related papers  (2020-11-04T15:02:59Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.