Query Complexity of Eliciting Consensus Lotteries with Bounded Adaptivity and Parallelism

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.