acceptodds
Under review as a conference paper at ICLR 2027

Learning Unanimously Acceptable Lotteries from Noisy Approval Queries

Abstract

Randomization can make collective agreement possible even when no deterministic choice satisfies every agent. We study how to find a unanimously acceptable lottery using only noisy binary approval queries, when agents have unknown utilities and acceptance thresholds. Our model allows feedback to become uninformative near acceptance thresholds, making agreement at these boundaries difficult to resolve. We develop algorithms for exact consensus under finite precision and for a robust formulation that allows either answer on borderline instances while preserving unanimous acceptance guarantees. Complementary lower bounds establish the optimal dependence on precision and margin parameters, up to logarithmic factors. We also distinguish finding one acceptable lottery from learning conservative approximations to every agent’s acceptance set. Learning sets that exclude rejected lotteries and retain all lotteries with sufficient margin requires quadratically many queries in the number of alternatives, even when a common lottery with substantial margin is supplied. Checking a proposed lottery with sufficient margin, by comparison, has a query cost independent of that number. We exploit this distinction to develop learning-augmented algorithms that save queries when a predicted lottery is useful while preserving worst-case guarantees for arbitrary predictions. Finally, we establish when exact decisions remain possible without known noise parameters and show how knowledge of the response rule can further reduce query complexity.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
preference elicitation, AI alignment, lotteries, collective decision-making

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_URRTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

A decision-maker is making a choice between a set of options. There are agents with hidden preferences, who the decision-maker aims to satisfy by making a randomized, rather than deterministic, choice -- a lottery -- over the options to satisfy all the agents. Application: deploying an ML model subject to a variety of constraints -- accuracy, harm limit, expected review cost. You want to satisfy all these requirements separately (i.e., there is no tradeoff allowed between requirements). Deploying a randomized mixture over policies (i.e., models) can satisfy all the requirements even when no individual policy can. The decision-maker proposes such mixtures and receives noisy binary feedback from each agent based on their hidden preferences. The research question is: what is the query complexity of consensus under different noise models.

Setting: n agents, m alternatives. Each agent has an unknown utility and a threshold of this utility under which they are willing to accept or reject the proposed lottery. Two noise models for the noisy queries: uniform noise and near-threshold noise (noisier as margin to the threshold of proposed lottery decreases).

The results include an upper bound for the query complexity (based on repeating the noiseless algorithm many times and applying a concentration bound) and upper and lower bounds for exact consensus and robust (a lottery is returned if it is at least rho improving than the threshold for each agent) consensus in the near-threshold noise models.

Critical strengths

The research question -- understanding the query complexity of reaching consensus when in this model of proposing lotteries with binary feedback -- is interesting. The model is general, allowing for arbitrary utilities, and the results are strong, for achieving exact and rho robust consensus under the various noise models.

Critical weaknesses

A critical weakness is clarity. Broadly, Sections 1 and 2 are written well and clearly communicates the ideas. There are a few exceptions - e.g., the text immediately following the math of Definition 2.4. For example, doesn’t the first implication of Def 2.4 directly say that a larger margin gives a larger response mean, contradicting the final sentence of the paragraph? However, the main technical sections - Sections 3-6 are written with confusing exposition that poorly conveys ideas and intuition. I don't believe the draft is suitable for acceptance without substantial revision to the text.

Questions for authors

Is there any intuition or explanation for the parameter ranges under which the bounds in Table 1 hold? If so, either including this discussion explicitly, or a pointer to this discussion, in the caption of Table 1 would be nice. It's seems like these conditions are fairly restrictive but it's not clear exactly where they come from.

Reviewer_7scyOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper extends prior work of Choo et all in ICML which studied finding the set of one agent's acceptable queries using finite precision responses. This paper extends this in several ways. 1) it looks at noisy responses. 2) it looks at more than one agent and consensus among them, 3) it goes beyond "finite precision", 4) it looks at a measure of robustness by turning it into a promise problem.

Critical strengths

Strengths: The papers exposition is reasonably clear; it makes real (though incremental) progress on a previous model. (See paper summary)

The steps it makes are reasonable and solid next steps that build on the current literature.

Critical weaknesses

Weaknesss: The biggest weakness is motivation. The claimed application in the introduction is strained at best. Lotteries are nearly never used in practice. Finding a compelling application seems to be a higher order priority than a learning problem based on a specific model.

I think that the model is mostly reasonable, but this is not enough for a couple reasons. First, the model of noise is not compelling. Agents might be (in real life definitely are) irrational. Will they really be happy with a lottery approved that they explicitly said was not okay? Your mechanism may well return this if they answer enough related questions the right way. Also, the repeated queries aspect is just completely unbelievable. You simply cannot ask people that same thing over and over and over and over again and expect to average out the results.

Second, if you change the model, you get different answers. The usefulness of these results relies on the robustness of the model. It is not likely that the results will not change when the particular noise model changes, particularly with respect to repeated queries. Third, For most off the alleged applications, all that must be done is apply a martingale. There remain boundary cases to sweep up, which are technically much harder, but, in practice much less appealing because it is on these boundary cases that the exactness of the model is the most important, and, as described above, it is not an exact model.
The paper does not even lay out a conceivable future in which these algorithms would be applied. The additions on the prior work, while reasonable next steps, seem to be a bridge to nowhere.

While there is no application for the results. The theory is not very compelling either. From skimming the proof sketches, I see dense explanations, not a clear new technique that could be transported to different problems, not a new way to understand things A second weakness is the lack of any big results. Putting 4-5 smaller results on the same topic together does not make a compelling paper. It may actually slightly improve the paper to remove some of the less compelling results, and streamline the story. Currently, there is a lot going on and I got a little disoriented.

Questions for authors

Are lotteries like these used currently? Do you really think there is an application that can be specified? For example, in your intro motivation, who is making this decision (Frontier Model upper management like Mark Zuckerburg? or who would be running this algorithm) If so, what type of applied people should read this paper to apply its ideas? Or is it more that this may be useful later?

Whom do you see your audience to be (given there are so many papers out there, why would they be interested in this particular one)?

Reviewer_8BBwOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This is a quite interesting paper. The author identifies an important problem: given n agents, and m plans, how to find the lottery where almost everyone accepts that. During the whole process each agent accepts a lottery if and only if it expected utility reaches an unknown threshold, and the leaner only gets noisy yes/no answers to queries of the form “is lottery x acceptable to agent i?”. Compared to Choo et al. (2026), the paper considers a more challenging noise model where responses become less reliable near the threshold. The authors propose an algorithm based on a finite-grid assumption to avoid such unreliable queries, together with matching lower bounds. They further consider a relaxed setting with an acceptance margin and show that learning the acceptable regions requires quadratically many queries in the number of alternatives, while verifying a given lottery is much cheaper. This motivates a prediction-based algorithm that first verifies a candidate and falls back to the general method if needed. The paper is entirely theoretical, with no experimental evaluation.

Critical strengths

The author provide a relatively complete picture of what can and can not be achieved under its noise model. Most upper bounds come with lower bounds that match in the main parameters up to logarithmic factors. I particularly appreciate the characterization of cases where finite query guarantees are impossible, and the tight analysis of the grid-spacing dependence in Lemma 3.1.

Another interesting results is Theorem 4.4, showing that learning all agents' acceptable regions remains expensive even when a good lottery is provided, while verifying a given lottery is much cheaper. This motivates the prediction-based algorithm and provides a useful insight into the difference between learning and verification.

Critical weaknesses

My main concern is the limited novelty compared to Choo et al. (2026). Much of the framework, including boundary searching, reconstructing acceptance regions, and prediction-based verification, follows the previous work. The extensions to noisy responses mainly rely on relatively standard techniques such as repeated queries, majority voting, and bisection. More importantly, the main lower bound in Theorem 4.4 applies to learning all acceptance regions rather than finding a consensus lottery, which is the actual objective of the paper. The query complexity for consensus still has a gap between the linear lower bound and quadratic upper bound in the number of alternatives. Therefore, I am not fully convinced that the paper provides a sufficiently strong theoretical advancement over the previous work.

My second concern is the practical relevance of the proposed noise model. The motivating ML applications often provide numerical evaluations rather than binary acceptance responses, and it is unclear whether the assumed noise conditions accurately describe these applications. The lower bounds also rely on fairly permissive assumptions about the response distribution. As discussed in Appendix I, stronger assumptions on the response rule can significantly improve the complexity bounds.

Finally, the theoretical query complexity seems extremely expensive in practice. For example, with two-decimal precision and reliability growing linearly with the margin, the exact algorithm can require over (10^{10}) repetitions for a single comparison. Even the relaxed setting with a margin of 0.05 can require over (10^5) repetitions. Without experiments or a more realistic analysis of these costs, I find it difficult to assess the practical significance of the proposed approach.

Questions for authors

The theoretical query complexity appears extremely high even with moderate precision or margin requirements. Could the authors provide a concrete example with realistic noise parameters and estimate the actual number of queries required? In particular, how realistic is the near-threshold noise assumption for the motivating ML applications, where numerical evaluation scores may already be available?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.