- 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 agents and alternatives. A lottery is a distribution over the alternatives. Each agent has a utility for each alternative , and an acceptance threshold . The utility of agent 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 . 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 . 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 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.?