acceptodds
Under review as a conference paper at ICLR 2027

Query Complexity of Eliciting Consensus Lotteries with Bounded Adaptivity and Parallelism

Abstract

When a decision requires unanimous approval, limited opportunities for feedback can make elicitation costly. We study how to find a consensus lottery (i.e., a distribution over alternatives accepted by every agent) or determine that none exists, using only binary accept/reject queries. Each agent accepts a lottery when its expected utility meets an unknown threshold. We consider two interaction constraints: _bounded adaptivity_, which limits the number of feedback rounds, and _bounded parallelism_, which limits the total number of queries per round. For arbitrary numbers of agents and alternatives, we give algorithms and lower bounds that quantify the costs of learning acceptance constraints and finding consensus under these limits. We determine the optimal round and query complexities for learning one agent’s acceptable set under bounded parallelism, and develop consensus algorithms based on parallel constraint learning and selective elicitation. These methods show how consensus can be found without fully learning every agent's constraint. For two alternatives, we obtain tight bounds in several settings and demonstrate that randomization can substantially reduce the query cost of a fixed round budget and the number of rounds under bounded parallelism, even though it cannot improve the optimal total query count when rounds are unrestricted.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
query learning, lotteries, preference elicitation, adaptivity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ZADwOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the query complexity of eliciting consensus lotteries under batch-size and/or round constraints. We are given nn agents and mm alternatives. A lottery is a distribution over the mm alternatives. Each agent ii has a utility ui(j)u_i(j) for each alternative jj, and an acceptance threshold τi\tau_i. The utility of agent ii for a lottery is the expected utility over the distribution. We say that the agent accepts the lottery if its expected utility is at least its acceptance threshold τi\tau_i. Goal is to find a lottery that is accepted by all agents, or verify that no such lottery exists.

The catch is that the utilities and acceptance thresholds are unknown to the algorithm. Instead, it can only indirectly access those entities via queries. This paper studies acceptance queries that ask for a given lottery and agent whether that agent accepts that lottery. Goal is to bound the worst-case number of queries that an algorithm executes to solve the problem. While this problem has already been studied in the fully adaptive setting, the authors study batch or round constrained settings. In the former, the maximum number of parallel queries per round is constrained and goal is to minimise the number of rounds. In the latter, the number of rounds is constrained and the goal is to minimise the batch size.

As a first main result, the authors provide upper and lower bounds for the problem with a bounded number of rounds RR. Then, they consider the problem with only two alternatives. They give an asymptotically tight upper bound on the total number of queries, complementing the existing lower bound by Choo et al., 2026. Then, they show that randomisation does not help in the unconstrained setting but is indeed helpful when having two alternatives with constrained rounds or batches.

Critical strengths
  • The problem considered in the paper is interesting and well-motivated. Generalising results from the fully adaptive setting to batch- or round- constrained settings is a very natural next research step.
  • The results for two alternatives seem very meaningful. For the unconstrained setting, the question is now asymptotically solved. For constrained settings, the authors show a clear separation between randomised and deterministic algorithms.
  • Overall, the results seem non-trivial. They require the combination of many diverse tools.
Critical weaknesses
  • The significance of the bound for a constrained number of rounds RR is hard to grasp. There is no discussion on how close the bounds are and on whether there is hope for tight bounds.
  • A clear distinction from the techniques by Choo et al. would be helpful. What are the new technical steps compared to that approach?
Questions for authors
  • Can you highlight the main new ideas in your algorithms, in particular compared to the fully adaptive algorithm by Choo et al.?
Reviewer_efZWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
3
Read review
Paper summary

This paper studies consensus lottery elicitation under bounded adaptivity and parallelism. Building on Choo et al. (2026), it establishes new query and round complexity bounds, including tight results for two alternatives and separations between deterministic and randomized algorithms.

Critical strengths
  1. The paper provides several tight complexity bounds, which are strong theoretical contributions.
  2. The results are well organized, with detailed proofs and helpful examples.
Critical weaknesses
  1. The model and some proof techniques are inherited from Choo et al. (2026), and the new techniques are confined to m=2m=2. Which technical components are fundamentally new?
  2. The assumptions are somewhat strong, how do people actually apply this method in real-world scenarios?
Questions for authors

Same as weaknesses.

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

The paper studies how to find a consensus lottery. The problem relates to the feasibility of linear programming using queries on each constraint separately. The algorithm wants to find a distribution xx over mm items. Each agent ii accepts or rejects the distribution based on ⟨x,ui⟩≥τi\langle x, u_i\rangle\ge \tau_i, where uiu_i is the agent's subjective value of each item and τi\tau_i is its threshold. Choo et al. (ICML 2026) studied the fully adaptive version. This paper adds two interaction limits: at most R rounds with unlimited queries per round (Section 3), and a global cap of B queries per round (Section 4). For general m, it gives:

  • fixed-round algorithms and a lower bound for learning one agent’s halfspace;
  • tight batch-capped round and query bounds for one agent;
  • multi-agent consensus algorithms based on parallel learning and a batched version of Clarkson-style weighted sampling, together with a - batch-capped lower bound. (the same algorithm as Choo et al. did (ICML 2026) with an additional round bound.

For m=2m = 2, the problem becomes finding a point that intersects with several intervals in R\mathbb{R}. The paper gives

  • a deterministic direct-search algorithm with optimal total queries;
  • tight deterministic R-round query complexity;
  • a 3-round randomized algorithm using expected queries;
  • tight deterministic and randomized round complexities under a batch cap.
Critical strengths

Strong characterization for two item case m=2m = 2. It improve the previous work from O(nlog⁡n+log⁡n⋅log⁡(1/ε))O(n\log n+\log n\cdot\log(1/\varepsilon)) to Θ(n+log⁡(1/ε))\Theta(n+\log(1/\varepsilon)) The problem connects to max-finding which has similar complexity as Grigorieva, Elena, et al. "The communication complexity of private value single-item auctions." Operations Research Letters 34.5 (2006): 491-498.

Critical weaknesses

Weakness

  1. The general-mm results are loose and largely compositional. For multiple agents with m>2m > 2 and a fixed number of rounds, the only result is Theorem 3.4. It runs single-agent learning for all nn agents in parallel, multiplying the cost by nn, which is immediate. Under a batch cap, Theorem 4.5 is the weighted-sampling algorithm of Choo et al. (ICML 2026) with an additional round analysis.
  2. A per-agent cap, where each stakeholder answers at most bb queries per round, seems more natural. It is not clear why query batches should be synchronized across agents. I would like to see the motivation for it.
  3. A noise model could also separate this problem from generic LP feasibility. Here the noise could come from the randomness of the lottery itself: an agent might judge a lottery by the realized outcome or by samples, rather than by its exact expected utility. This could separate from standard noisy membership queries.
Questions for authors
  1. Why stop at three rounds for the randomized algorithm?
  2. For m>2m > 2, does the endpoint-test idea extend?
  3. How do the results change under a per-agent cap, under noisy answers, or under δ\delta-approximate feasibility?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.