Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies a setting that combines social choice and information aggregation.  As in a classic social choice problem, individuals with preferences want to choose between two options, but as in an information aggregation setting they do not have the knowledge to know exactly what their preferences are, instead having only a signal correlated with the true state of the world.  The paper introduces a “Wisdom-of-the-Crowd-Voting” Mechanism, which implements the majority wish in an (approximate) strong Bayes Nash equilibrium.
main_review: The mechanism appears novel, natural, and reasonably practical, as it asks agents only to report their ordinal utilities and beliefs about others conditional on their signal.  (In the spirit of ideas from peer prediction, I think we could even dispense with the reported belief if favor of the signal since one can be inferred directly from the other when the signal structure is known to the mechanism designer.)  The properties established for it are satisfying.

Post Author Response:
Thanks for your response.  On a few of the points raised:

Two alternatives - there is certainly plenty of work that looks at settings with two outcomes, but I still do think it is fair to call this restriction a limitation of the results in the paper.

Ex-ante/Ex-post and Finite T - It seems like there are some worthwhile things to say here, and it would be good for some of them to make it into the paper.  I will point out though, that these issues aren't obvious to me.  For example, this paper already makes "strong additional assumptions" by imposing the signal structure and this also makes me question whether majority vote and variants really are the only real alternative.  It would strengthen the paper if theoretical results along these lines could be established.

Theorem 3.1 - Even in the context of the section as review, it still doesn't read as obvious to me that this analysis is direct from them - if it is, why is there a complete proof and so much discussion of how to prove it?  So I think at least a bit more guidance for the reader about where the ideas are coming from and why they are being presented in the detail they are is needed.
limitations_and_societal_impact: On the negative side, the results are somewhat narrow as the approach would start to run into all the standard challenges in social choice once there are more than two alternatives.  There is also a bit of a tension where the solution concept aims for ex-ante properties (e.g. Bayes-Nash), but somewhat oddly the goal of the algorithm is ex-post (choosing the preferred alternative conditioned on the true state).  This is perhaps defensible, but certainly seems different from the more common goal of maximizing expected utility.  In particular, this mechanism doesn’t seem appealing in the finite T case to agents who have, e.g., a weak preference to avoid false negative errors but a strong preference to avoid false positives.

I also have a number of comments on the presentation, but they largely seem easy to resolve, although the page limit seems to be a bit of a constraint and some adjustments may be needed elsewhere:
- As someone not familiar with many of the cited papers I found 1.2 (and to a lesser extent 1.3) hard to follow.  Eventually I just gave up and read the introduction of Austen-Smith and Banks, after which it made more sense. So more is needed here to make this material self-contained.  
- I’m much more familiar with the work discussed in Appendix B and was wondering by the end of the paper why none of it was discussed.  I think this really needs to be part of the main paper to position it properly and putting it in the appendix is at least somewhat abusive of the page limit. 
- I disagree with some of the discussion around the revelation principle.  While I agree that this mechanism is not quite the revelation principle applied to plurality voting, it still seems to me to be an application of it.  In particular, the revelation principle does not actually require the entire agent’s type to be revealed, but only a sufficient statistic of it to act on the agent’s behalf which is what this mechanism appears to do.  Maybe there is a deeper reason this interpretation is wrong, but the superficial one presented isn't convincing.
- To what extent is Theorem 3.1 novel?  It seems to be analyzing Prelec et al. but translated to the model of this paper so I’m not clear whether it is just a translation of their analysis or a new analysis of their algorithm that extends to this one?
- The transition into 3.2 seems rushed and jumps into the analysis in mid thought: “At Step 3 of the mechanism...”
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider elections that have two alternatives and three distinct classes of voters: candidate-friendly, candidate-unfriendly, and contingent agents. Candidate-friendly and candidate-unfriendly agents have made up their minds before the election, but each contingent voter's opinion depends on an unobservable state variable; they each receive a private signal about this state variable. The authors present a mechanism that elicits private signals from voters and which outputs the correct answer based on the state of the world. This mechanism is also strategyproof against even coalitions in the sense that truthful reporting is a strong Bayes Nash equilibrium. The mechanism draws on the "surprisingly popular" method of Prelec et al.

main_review: I found the setting to be a fairly natural one -- at least in US politics, it seems to fit well. Furthermore, I enjoyed the incorporation of the "surprisingly popular" mechanism, which is a very elegant and nice result. 

The technical results are not too surprising, and they use mostly standard techniques (at least in the body of the paper).The proofs are relatively cleanly laid out and it is easy to follow the big ideas in the paper's technical content.

If I'm not mistaken, the crux of the correctness proof relies on the chain of inequalities in Theorem 3.1. In particular, this means that the population breakdown between candidate-friendly, candidate-unfriendly, and contingent agents must be exactly known public information, which seems like a very strong assumption. I assume that imperfect knowledge of this breakdown (however slight the error) could, in theory, lead to the population making the wrong decision. 

Also, the Bayesian update step is quite complicated, and I don't think people will perfectly update every time. 

I think this paper would significantly benefit from some experiments in which people are assigned affiliations (candidate-friendly, candidate-unfriendly, and contingent), and contingent agents must report the fraction of contingent agents who will report signal h. If this works well in practice even when (a) agents don't perfectly perform Bayesian updates and/or (b) the exact population breakdown isn't known, then that would be a very nice proof of concept.

Minor comments:

All instances of "surprising popular" should be surprisingly popular" (e.g., 90, 125, 253, ...)
124: suggest removing "rely on the same notions"
Thm 3.1: period at end
279: You should note that c as defined after line 279 is for Chernoff bounds later (e.g., in Thm 3.2).
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the two-alternative voting problem with imperfectly informed voters. In this setting, each voter receives a signal which is positively correlated to voter's true preferences (over two alternatives). The goal is to aggregate these signals to find out the majority voting winner w.h.p. Specifically, the paper gives a mechanism such that  1) the mechanism will output the majority voting winner under the true preferences w.h.p.  2) the mechanism incentives every voter to truthfully report the signal they received.

The main technical contribution of this work is that their mechanism uses the idea of "surprisingly popular" approach (Prelec et al., 2017)  from the information aggregation literature. They show that "surprisingly popular" approach can be well adapted to two-alternative social choice setting and can incentivize voters to report truthfully (for two-alternative). In addition, they show their mechanism is user-friendly, and does not require voters to understand deep mathematics.
main_review: The problem this paper tries to solve is well-motivated, and I believe it is a very important problem. Social choice problems with imperfectly informed voters are practical and significant in real world. It's actually a game-theoretic version of information aggregation, they not only need to aggregate partial information to get the correct answer w.h.p, but they also have to guarantee that nobody is willing to strategically misreport information they know. Previous work in the information aggregation literature does not consider potential strategic behaviors of participants. This paper is novel as it is the first one considers both correctness and truthfulness in this setting.

The major contribution of this work is extending the "surprisingly popular" approach (Prelec et al., 2017) to the social choice setting. In their mechanism, each voter are asked to provide the signal they received as well as their prediction of other voters' preferences. They prove this mechanism is both correct and truthful. I really appreciate that authors use a paragraph to describe how to design questionnaire for this mechanism, which clearly demonstrates that this mechanism is user-friendly and easy to implement. 

The weakness of this paper is that the two-alternative social choice setting is too simple. Moreover, by reading the proof,  I might be missing something but I have a sense that in this setting, a mechanism is truthful as long as it is correct. So I guess maybe plugging any correct information aggregation mechanism other than the "surprisingly popular" mechanism will result in a truthful mechanism as well. In that case, two-alternative voting with imperfectly informed voters is essentially the same as conventional information aggregation setting.

Overall, I think it's a good paper which is well-motivated and clearly written. However, the setting seems to be too weak and I feel it's just a somewhat straightforward extension of the existing "surprisingly popular" mechanism (while it is still valuable to point out the connection between two settings).

### Questions:
1) What if I replace median in the mechanism with mean? Is there any obvious objection to that?
2) Is it true that truthfulness ($\epsilon$-strong BNE) is directly followed by correctness (output the correct answer w.h.p)? Is it true that plugging any (non game-theoretic) mechanism from the information aggregation literature will immediately result in a truthful voting scheme in your setting? 

### Typos:
1) line 180 "$v_t(H, A) > v_t(L, A)$" -> "$v_t(H, A) > v_t(H, R)$"
limitations_and_societal_impact: Authors have adequately addressed the limitations, and I don't see any potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers two alternative elections in which the voters are imperfectly informed. There is an unobservable state that may affect some voters’ preferences. Each voter receives a signal correlated with the state. The voter’s signals are conditionally independent and follow the same publicly known distribution. The designer’s goal is to elicit truthful information and aggregate the information to find the alternative that is preferred by the majority. The paper proposes a mechanism that guarantees truthful reporting is an approximate strong BNE and outputs the right alternative with high probability.

main_review: The problem considers an interesting problem. The idea of combining information elicitation and voting when the voters are imperfectly informed is good. The problem setup as well as the main technique builds heavily on the previous work [Prelec et al. 2017]. But the trick of using the median to guarantee strong truthfulness is cute. 

The overall writing is good, but the definition of the state in the model is a little bit confusing (see the comments below). I did not find any glaring mistakes in the proofs. 

Comments:

The way that the state W is introduced in the model is confusing. “Here, L stands for low quality where more agents prefer R, and H stands for high quality where more agents prefer A.” The state W seems to be defined in a way that depends on the voting outcome, but the voting outcome depends on the voters’ preference which depends on the state. Suppose there are 30% of rejecting voters, 30% of accepting voters, and 40% of swing voters. Then should the state be L or H in this case? Assuming it’s L, then the 40% swing voters would prefer rejecting and it is indeed L. Assuming it’s H, then the swing voters would prefer accepting and it is indeed H. It seems that the state should be a predetermined random variable that does not depend on the outcome.

It would be good to discuss a little bit how to extend the result to more general settings in the main text.

Questions:

Please comment on the definition of the state. Does it have to represent which alternative is more preferred? Is it actually considered as a predetermined random variable that is independent of the outcome?

At Line 369: “We have seen that the deviating coalition D cannot contain any contingent agents (since their utilities have already been maximized)” Is this utility the ex-ante utility or the ex-post utility?

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: There is not much substantive disagreement among the reviewers; the disagreement is mostly about how to value these results, in particular given the restriction to two alternatives.  (Such a restriction is common in social choice due to challenges that start to appear with three or more alternatives.)  The paper is left in a borderline position, but I'm inclined to give it the benefit of the doubt and recommend it for poster (in particular I think social choice results with two alternatives can be interesting and valuable).  The authors should take seriously though some of the reviewers' comments to improve the presentation of the paper.
Decision: Accept (Poster)