- 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.