Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences
Authors: Grant Schoenebeck
Biaoshuai Tao
Venue: NeurIPS 2021 Poster (2021)
Keywords: information aggregation
social choice
mechanism design

Abstract: We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. As a special case, our model captures the common scenario where voters can be categorized into three types: those who always prefer one alternative, those who always prefer the other, and those contingent voters whose preferences depends on the state.  In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased.

We present a mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority.  In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences
Grant Schoenebeck School of Information University of Michigan schoeneb@umich ch. edu
Biaoshuai Tao* John Hopcroft Center for Computer Science Shanghai Jiao Tong University bs jastoosjjen tu. edu. cn
Abstract
We consider two-alternative elections where voters' preferences depend on state variable that not directly observable. Each voter receives private signal that is correlated to the state variable. Voters may be "contingent" with different prefer- ences in different states; or predetermined with the same preference in every state. In this setting, even if every voter is contingent voter, agents voting according their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased.
We present an easy-to-deploy mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms strong Bayes Nash equilibrium (where coalition of voters can deviate and receive a better outcome).
Introduction
Social choice theory studies how to aggregate participants' heterogeneous opinions/preferences and output collective decision from a set of alternatives. Typically, though not always, is assumed that each participant has a clear preference over the alternatives, e.g., preference order over all the alternatives, a valuation for each alternative, etc. However, even with only two alternatives, this not the typical case for all participants. In addition to the participants who have clear, predetermined preferences for one alternative over the other, typically there are also contingent participants who only have partial information which alternative is "preferable for them" and yet would like to select the alternative that is "preferable for them."
A standard example would be an election with two candidates and coming from political parties and respectively. Voters are normally partitioned into three types: some partisans for Party A prefer candidate based on his support for the platform of party A; other partisans for Party B prefer candidate based on her support for the platform of party B; finally, there are swing voters who are largely indifferent between the parties' platforms and would like to elect whichever candidate can make more progress on non-partisan issues. However, swing voters not have perfect information about which candidate is better suited for addressing the non-partisan needs of the community. Instead, each voter has a hunch which candidate will perform better on the non non-partin partisan problems facing the community based on both public information and their private experiences and belief'.
Additional examples where participants have preferences, but may or may not know what is "prefer- able for them",, abound. In votes for corporate strategies, for hiring decisions, and for policy decisions typically some participants would like select according to some truth they are collectively trying to
A full version of this paper is available at https:/arxivvorg/ab////00 http:////a/////00///9///99
This material based upon work supported by the National Science Foundation under Grant No. 2007256. corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

discern (e.g., impact on future profits, suitability for the position, efficacy of policy, etc.) while others may have predetermined preferences, for example, because of the way they are uniquely affected (e.g., prominence of their position in future corporate strategy, vision/skills of the job candidate, who in particular the policy benefits/harms).
1.1 Informal Setting
In this paper, we consider a two-alternative social choice setting where voters' preferences may depend on a state variable. In the above example, the state is which candidate will make more progress non-partisan issues.
We consider binary state variables in the main body of this paper. In general. the state need not be binary. For example, we could generalize the above example so which candidate would preform better on non-partisan issues is on scale of to 10 (where indicates candidate is much better and 10 indicates candidate b is much better). Predetermined voters' preferences would still not depend on the state. However, contingent voters' may have different thresholds on the state where they would transfer their support from candidate to candidate b. In Appendix D we discuss the non-binary setting and extend our results to this setting.
The state variable is not directly observable in the election phase, as the performance of new government official, a new hired employee, new policy, etc., may not be revealed until many years after the vote. Instead, each voter receives a signal that is correlated to the hidden state which models the information voters received from difference sources.
Our goal is to select the majority wish, the alternative that would be preferred by the majority if they knew the state of the world. If some type of predetermined voters forms majority, this is rather easy. However, in the case where the predetermined voters of neither alternative forms a majority, the mechanism needs aggregate the information and preferences of the contingent voters and selects the alternative which, for a majority of voters, is "preferable for them".
1.2 Imperfectly Informed Voters
Social Choice Social choice theory with imperfectly informed voters dates back Condorcet's jury theorem in 1785 (De Condorcet 1785]. and has also been widely studied [Miller] 1986 Young
1988 Ladha 1992 Nitzan and Paroush 2017). In Condorcet's ss setting, there are two alternatives, one of which is "correct", and each voter votes for the correct alternative with probability Condorcet's s jury theorem states that the probability that the majority voting scheme outputs the correct alternative goes to 1 as the number of voters increases when 0.5, and, conversely, this probability goes to 0 when p < 0.5.
Two unfortunate limitations for Condorcet's 's jury theorem are 1) It fails to output the correct alternative in the case voters' beliefs are aligned the incorrect alternative (i.c., p < 0.5), and 2) It assumes voters vote truthfully and disregards voters' potential strategic behaviors. However, even in the case all voters have the same preference for the correct alternative, voting truthfully still may not be Nash equilibrium ASsttnn-Smith and Banks 1996].
To circumvent the first limitation, Feddersen and Pesendorfer [1977 consider the scenario where voters play a Nash equilibrium strategy profile, while the voting rule is still the majority scheme. Feddersen and Pesendorfer (1997) show that when the number of voters tends to infinity, the probability that a majority voting scheme outputs the correct alternative approaches to 1 if voters play the equilibrium strategy profile, while this probability is bounded away from if voters play the truthful strategy profile instead. Feddersen and Pesendorfer's 's model assigns each voter a preference parameter x E [-1, 1] describing his/her alignment the two alternatives. In their model, the unique (Bayes) Nash equilibrium is characterized by two thresholds Zg. voters with preferences below To always vote for one alternative, voters with preferences above 21 always vote for the other, and voters with preferences between Tp and 22 vote truthfully. Although Feddersen and Pesendorfer's solution guarantees that the correct alternative is output with high probability, it requires sophisticated voters. The voters need to calculate the values of zo and xi to decide their actions. The values Zn and xi are each the zero point of continuous monotone function involving complicated Riemann integral. This is usually too demanding for voters in practice,
[-1, with Zo < such that

---

especially those who do not have a mathematical background. Moreover, it needs to be common knowledge that all agents can and will perform this computation.
In this paper, we take a different approach. Instead of asking voters to play the Nash equilibrium for majority voting, seek to design more sophisticated voting scheme, mechanism, than the majority voting scheme, such that voters are incentivized to vote truthfully under the mechanism, while guaranteeing the correct alternative is output with high probability. Our social choice mechanism thus elicits truthful information from the voters and then aggregates it.
Information Aggregation The information aggregation literature considers how to obtain a "cor- rect answer" by aggregating individuals' partial information the crowd's wisdom. The straight- forward procedure of outputting the answer that believed to be correct by the majority does not always work [Chen et al., 22004, SSimmons et al. 201T]. An example where this fails is when the crowd has a strong prior belief for the incorrect answer while novel specialized knowledge is only shared among a minority of the agents. It is also known that further calibration based on collecting participants' confidences (the posterior of their beliefs) does not always solve this problem [Hertwig 2012 Prelec et al. 2017]. In a seminal work by Prelec et al. [017]. new "surprisingly popular' approach was proposed: the participants' predictions over the other remaining participants reported answers collected, and the answer that is reported by more participants than predicted is output (we will review this in Section B.T). They justified this approach both theoretically and through experimentation. In particular, they demonstrate the viability of approaches that require agents to predict reports of the other agents. [Hossenni et al. [021] empirically extend the surprisingly popular approach to the non-binary setting, where the goal is to learn the correct ranking over many options instead of the correct answer in two options.
The work by Prelec et al. [2017] and Hosseini et al. 202 does not fit into the social choice context in two aspects. Firstly, the objective for an information aggregation mechanism is to output the correct answer. Participants who collaboratively contribute their knowledgeeinformationn do not have preferences on which answer is finally selected. This is fundamentally different from the social choice setting where the whole point of social choice mechanism is to select alternative favored by the majority. Secondly, as agents care about the outcome, agents may be strategic and manipulate their reports in order to make their preferred alternatives win, while Prelec et al. [017 and Hosseini et al. [222T] do not put the problem in a game theory setting.
1.3 Our Results
In this paper, we study the social choice problem in a game theory setting with the existence of imper- fectly informed voters who only have partial information regarding which alternative is more favorable. For various settings with two alternatives, we propose a mechanism that aggregates participants' private information and outputs the alternative favored by more than half of the participants the majority wish. Our mechanisms are truthful, in the sense that the truthful strategy profile forms a strong Bayes Nash Equilibrium.
wwwp:ooo--t----d-ooooooroee voting mechanism, presented in the paper, applies to the case of two worlds/states, where each agent receives a binary signal. We show it has strong truthfulness and aggregation properties, even for relatively small numbers of agents (Section 3). This result requires that the distribution of agents is common knowledge. In the full version, results. First, the common knowledge assumption is necessary to attain a strongly truthful mechanism that outputs the majority wish with high probability (Appendix D. Additionally, extend our results to the setting of more than two worlds (A (Appendix F.2). Finally, we show how to extend our results to the case of more than two signals (Appendix E.3)
Our main
show several additional
Our mechanism can easily be implemented using a simple questionnaire that elicits voters' information and preferences. The questions in the questionnaire are friendly to those voters who do not have relevant backgrounds in mathematics, game theory, etc., and they require participants to predict the responses of other agents, which is empirically validated by the surprisingly popular method from Prelec et al. [2077].
We ensure our mechanisms have group truthfulness property by employing "median trick." Intuitively, by the Median Voter Theorem [Black] 19488 Hotelling 1929], the median voter's vote (in binary choice) is favored by the majority. By careful design, our mechanism ensures that
3

---

the voters who are "below" the median have conflict of interest to the voters who are "above" the median, which makes sure less than half of the voters have an incentive to deviate and those voters can only change the outcome in the unfavorable direction by the property of median.
From a high level, our work be understood However this view is not entirely accurate. First, our equilibrium concept is strong Bayes Nash cquilibrium while we only know that plurality voting implements the majority wish outcome in (Bayesian) Nash equilibrium [Feddersen and Pesendorfer 1997]. Second, the revelation principal requires that agents report all their knowledge. In our case, this would include the entire prior, which is not realistic. In contrast, our mechanisms only require that agents report a preference and a prediction of other agents' preferences. Such reporting requirements have previously been shown to be pragmatic [John et al., 2012 Prelec et al., 2017 Hosseini et al. 2021]. Third, our setting is different than prior work [Feddersen and Pesendorfer, 1997], and this makes our results incomparable. In particular, we deal with a discrete state space. This difference also allows us to achieve some of our results not just in the limit, but for finite sets of agents.
revelation principal applied plurality voting
Appendix A contains an additional comparison of our work with Feddersen and Pesendorfer [197] s.
1.4 Additional Related Work
Our work is additionally related to the recent work on incentive compatible machine learning (Perote and Perote-Penal 2004 Dekel et al. 2010 Chen et al. 2018]. In these settings, the "social choice" being made is a machine learning predictor where agents benefit from their point having small error with respect to the chosen predictor. As in our setting, the information of the optimal model is distributed among the agents. Unlike our model, the private information and the preferences of the agents essentially coincide.
Information elicitation without verification, sometimes call peer prediction, is another very related line of research which shares some of the intuitions and techniques from information aggregation. The information elicitation literature has been well established in the past decades, starting from Preleed 22004'ss 's Baysian Truth Serum and Miller al. [2005]: 's peer-prediction method. These mechanisms cleverly design payments to the agents to guarantee that the truthful reporting of received information forms Nash equilibrium.
A mass of recent work (see Faltings and Radanovic [2017] for a survey) is dedicated to design- ing information elicitation mechanisms that work in more general settings (such as, supporting
small number of agents [Dasgupta and Ghosh| 2013 Zhang and Chen 2014 (Schoenebeck and
Yu 2020). allowing agents having information with different levels of sophistication [Gao al. 2016 Kong and Schoenebeck 2018b) ). or achieving better truthful guarantees (such as, strict Nash equilibrium [Schoenebeck and Yu 2021 J. informed Nash equilibrium (Shnayder al. 2016), or even dominant strategy equilibrium [Kong and Schoenebeck] 2019 Kong 2020 ) sometimes by studying more restrictive settings (e.g. multiple similar questions being asked simultaneously (Dasgupta and Ghosh, 2013). ). Indeed, following Bayesian Truth Serum, many of these mechanism require the agents to predict other agents' reports (Zhang and Chen 2014 Kong and Schoenebeck 2018a b
2019 Kong et al. 2020 SSchonnbbeck and Yu 2022).
However, all these mechanisms rely payments the agents incentivize truth-telling. In social choice setting, on the other hand, we need to incentivize truth-telling solely based on choosing the winning alternative.
2 Model and Preliminaries
In this paper, we will define our model and present our main result with two states and two signals. The extension to general numbers of states and signals is discussed in Appendix E. We use the standard signal structure that is commonly used in the peer prediction (e.g., the work in Sect. T.4). information aggregation (e.g., (Prelec et al. 2017)) ) and social choice literature (e.g., [Feddersen and Pesendorfer] (997)).
'Loosely speaking. the revelation principal states that any outcome that can be implemented in equilibrium can also be truthfully implemented in equilibrium by having the mechanism play the equilibrium strategy on behalf of the truthful agents.

---

Suppose department of 'T' faculty members, or agents, need to decide whether or not to hire a
new faculty candidate. In our model, those T' agents are voting for two alternatives, A and R (corresponding to "accept" and "reject"). There is a set of 2 possible worlds (or states) W = (T,, H), which describes the underlying quality of the candidate. Here, T. stands for "low quality", and H stands for "high quality". Agents do not know which world is the actual world that they are in. They have a common prior belief on the likelihood of each world. In the candidate hiring example, the CV of the candidate is given to those T faculty members before any individual interviews, and a prior belief is formed. Let W be the actual world which is viewed as a random variable. We use W L and W H to denote the events that the actual world is L and H respectively. Let (PL, PH) = (Pr(W~ = L). Pr(W- = H)) be the prior over worlds. Each agent knows the values of PL and Pи prior beliefs. We further assume PL, PH > 0.
An individual interview for this candidate held for each of the agents. Each agent receives a signal, represented by the random variable St, from the set S = {e, h). Given W I. or W H, the signals agents receive have the same distribution and are conditionally independent. Let Ptr = Pr(S, é W = L) be the probability that signal will be received (by an arbitrary agent t) if the actual world is L. Let Put, PEи and PaR have similar meanings. The set of values {Per. PEH. PaL, P is known by all the agents, but not the mechanism (such mechanisms are called detail-free in the peer prediction literature). Naturally, signals are positively correlated to the worlds:
PeL > PeR and
PuR > PAL.
(1)
Different agents may have different bars on the quality of the candidate. For example, if theory candidate is interviewed in a computer science department, the theory faculty members may want to accept this candidate at a lower quality compared with the AI, software and hardware faculty
members. To capture this, each agent is assigned utility function v2 Wx (A, R) - 10, B}. Naturally, voters receive higher utilities for A in world H and for R in world L:
Uy A) > A))
and ve(H, R) < (1, R).
(2)
Since we can always rescale agents' utilities, for simplicity, we assume without loss of generality that agents' utilities are integers and bounded by B Z+. Endowed with their prior beliefs, upon receiving their signals, agents will have posterior beliefs about the distribution of W and react to the mechanism in a way maximizing their expected utilities accordingly.
We assume u2 (L,,, A) A (L, R) and (HH A) a ve H, R) for each agent f, so that agents always strictly prefer one alternative over the other. Let F be the set of the candidate frienddly agents who always prefer A: ve (H, > (L, > vy (L, R) > U, H. R). Let U be the set of the candidate- unfriendly agents t who always prefer R: U, (L, R) > 0e H, R) > D, A) > 2/ (L, A). Let C be the set of the contingent agents I. whose preference depends on the actual world: vy L,, R) > v. (L, A) v. (H, R).
and ve (H,A) A)
Let OF numbers of theory, AI, software, hardware faculty members are known to everyone, we assume that the values of a,, az and ac are common knowledge. Admittedly, this assumption may not apply to some specific scenarios. In Appendix D we discuss the model where agents have only partial information on ap, au and ac, and present strong impossibility result for this model.
F T av [T]
U and ac = |C| be the fractions of the three types of agents. Since the T
The goal is to output the majority wish, the alternative that is preferred by at least half of the agents conditioned on the true state. We assume T is an odd number to avoid ties. Clearly, A should be output if of > }. should be output ouy > 1. In the case OF,, ar < 2. A should be output if the actual world is H and R should be output if the actual world is L.
Our results will sometimes require T. the number of agents, to be sufficiently large, and it may be helpful to think of T + co. However, we will always assume that the parameters of the model: B, (Pi, }H). (PeL. PeH, PAL, Pht J. and {ap, ar, ) do not depend on T' in any way.
The traditional social choice setting with agents having predetermined preferences can be viewed as a special case of our model, by setting |C| = 0 (i.e., there is contingent agent).
For the ease of comprehension, we have used the faculty candidate hiring as a running example for this paper. This can be replaced by any example from most practical scenarios where different types of imperfectly informed voters are voting between two alternatives, including all the examples we mentioned in Section[]]
5

---

In our election example in the second paragraph of Section A and R can represent candidates a and b respectively. Correspondingly, for this example, L and H can represent "a is better suited" and "b is better suited" respectively. F and U represent voters aligned to party A and B respectively, while C' represents those swing voters whose preferences depend on the signals (in this case, the signals correspond to their private experiences and beliefs, which may be based on information they obtained from their favorite TV programs, newspapers, etc).
2.1 Strategy and e-strong Bayes Nash equilibrium
mechanism collects report from each agent, and then outputs an alternative which is either or R. The mechanism specifies the content of the report by specifying questions for the agents. Examples of those questions include asking each agent for the signal he/she receives, asking each agent to predict the other agents' reports, etc.
Let R. be the space of all possible reports, which depends on the design of the mechanism. pure strategy of an agent is given by a function a S + R. that maps a signal received by this agent to a report. In mixed strategy, a can be random function.
An agent's 's strategy is truthful it always specifies the correct answer to each question in the report, to the best of the agent's knowledge after receiving the signal. For example, if the mechanism asks for the agent's ss signal, an agent playing the truthful strategy should report the signal he/she receives; if the mechanism asks the agents to predict the fraction of agents who will receive signal m, agent playing the truthful strategy should report his/her posterior belief on this computed by the Bayes rule (Section 2.2 discusses the computation of posterior beliefs).
be the expected utility of agent 4, where the expectation is taken over the sampling of agents' signals. Notice that we use to denote the ex-ante utility (as defined just now) and we have used nt to denote the ex-post utility (see the fourth paragraph in Section 2). Most parts of this paper will focus on the ex-ante utility, especially when are talking about any equilibrium solution concept
Given a strategy profile = (oi...., OT)) let uz
Since we are in social choice setting with a potentially large number of agents, a single agent's behavior may not have much effect. Thus, instead of the typical Bayes Nash Equilibrium, we consider a much stronger goal-the the strong Bayes Nash equilibrium.
Definition 2.1. A strategy profile (d1,..., σr) is an E-strong Bayes Nash equilibrium if there does not exist a subset of agents D and strategy profile (o'......o') such that
1. or og for eacht t D.
2. "u(o",,...,,f . o'r)) 2 u((o,. u4(01....,00 .T) for each E D, and
3. there exist E D such that (o......... .4) > velor....., +
When a strategy profile (aI,...., .,) is not an e-strong Bayes Nash equilibrium, we will call the subset of the agents D in Definition the deviating agents or the deviating coalition. By Definition 2.1 every agent of the deviating coalition must be at least as well off, and some must be strictly better off by at least e. Notice that O-strong Bayes Nash equilibrium is the conventional strong Bayes Nash equilibrium. The larger& is, the harder it is to find a deviating coalition, and so the larger the set of e-strong Bayes Nash equilibria.
2.2 Posterior Update by Bayes Rule
Upon receiving a signal S, E {E, h., agent t updates his/her posterior beliefs (about the probability that (s)he is in world L or H, the fraction of agents that will receive signal & or h, etc.) based on
'However, the goal of the mechanism is to output the majority preferred alternative based on agents' ex-post utilities. Our choice of discussing ex-ante utilities in solution concept and ex-post utilities in the goal is motivated by practical applications. The underlying better alternative is unknown in the election phrase, so ex-ante utilities are considered for the solution concept. On the other hand, the ultimate goal is to select the alternative that turns out to be better after a certain period of time when the underlying better alternative is revealed (c.g.. the performance of selected president or the effect of new policy in the next few years after the election), and in this case the ex-post utilities considered.

---

Bayes rule. Let Tm'm be the probability that an agent who receives signal m E {e, believes that another agent will receive signal m' h.. Straightforward calculations by Bayes rule (available in Appendix B.T reveals
PmL
PH mH
mm'm PmLmL PH Pml
PIOL + PLPML + PH Pml
Pm H-
(3)
Given strategy profile Σ for..... σr) and mechanism M, let (A) be the probability that alternative A is announced as the winner given the actual world is n, then An (RM = Mg
the probability that alternative wins given the actual world is n. We will omit the superscript M when it is clear what mechanism we are discussing.
All the agents' ex-ante utilities depend exclusively on (2)) XA (2) for XE()), AB (2)),, and each agent t's utility is given by
(I) = PL (AL(E) +
(A
(-) (H. R)) (4)
which can also be rewritten as (by noticing (2) + (2) and (x) + (2))
u1 [Σ) = PLo,(L, R) + P H R) + PL)
02 (L,
(5)
+P 2 (vx H, A) - (H,,
We will always use E'
J to denote the truthful strategy profile.
3 The Wisdom-of-the-Crie CrotigVoting Mechanism
We will first review Prelec al.'s Surprisingly Popular algorithm (Prelec et al.) 2017). which works under setting similar to ours but with non-strategic agents. Some part of the intuition behind our mechanism is based on Prelec et al.'s work.
3.1 Prelec et al.'s Surprisingly Popular Algorithm
For the purpose of this paper, we will describe the algorithm with two worlds and two signals. The algorithm asks each agent t the signal (s)he receives, and his/her belief on the fraction of agents who have received signal l (or signal h). In our notation, each agent reports the realization of St and, assuming S, assumed to be non-strategic, those who receive signal e will report (f, Tιx) and those who receive signal à will report (h, Tex). The algorithm then computes the fraction of agents who report signal f, and the average value of all the reported Tim 's. the former is greater than the latter, is considered being "surprisingly popular" and the algorithm will conclude that L is the actual world. Otherwise, will be considered as being "surprisingly popular" and H will be concluded as being the actual world.
E {e, h.. the value of Tam. (or Thmm which equals to 1 - --mm).. Since agents
The correctness of this algorithm is based on the following simple yet important observation in Theorem 3.1 In particular, the average of agents' reported predictions (those Tim 's) will be between Tek and Tix- When the number of agents T sufficiently large. the actual fraction of agents who receive signal l will be either approximately Pez. (if I. is the actual world) approximately Peh (if H is the actual world). Theorem 3.1 then implies the correctness of the Surprisingly Popular algorithm.
Theorem 3.1. PEH < Ten < Tu < Per. and PaR > Thk > The > Pa..
For completeness, the full proof is appears in Appendix B.2 but the intuition is straightforward. The inequality Pt < PiL is by the positive correlation (1. The inequality Te. < Tee is also intuitive: the positive correlation between the signals and worlds implies the positive correlation between two agents' received signals. Finally, (3) implies each of Tea and Tee is a weighted average of Peи and PEL, the value is between Peh and PEL. This concludes the first inequality chain, and the second can be shown similarly.
Throughout this section, we use to denote the following constant, which is used in the Cherooff bounds in our proofs.
min (Tir PHH, Tes
Tea Pat. Ter, PAT Thn Tha Ten, Tea P
(6)
7

---

3.2 The Baalom--f-tee-Crowd-ooiiii Mechanism
Mechanism 1 The Wisdom-of -rw-tthe--C-----ee Crowd-Votiig Voting Mechanism
1: Each agent i reports his/her type (F, U or C) to the mechanism, and he/she of type C, the signal (S)he receives (either e fi), denoted by 8; E he,
2: If agent reports type F, his reported signal will be automatically treated as 8 = h;; if agent I reports type U, his reported signal will be automatically treated 8, f.
3: For each agent & of type C, ask him/her to predict the fraction of agents who will report signal h. Let 8, be t's prediction. The prediction ö, should be made with the type F and type C' agents' predictions defined in the previous step being considered, and the mechanism makes this clear to the agents. For each agent of type F, 6g set to 0, and for each agent of type U, 8, is set to 1.
4: Compute the median of those d2. denoted by d.
5: If more than half of the agents report type F, announce A being the winning alternative; if more than half of the agents reports type U, announce R being the winning alternative.
6: If the fraction of the agents reporting & = h is more than the median 8, announce A being the winning alternative; otherwise, announce R being the winning alternative.
At Step 3 of the mechanism, we only elicit predictions from those contingent agents, and those moddidate-friend]] caandddtt-uuffrient resp.) agents' predictions treated as 0 (1 resp.). In Appendix [ we discuss an alternative mechanism where we clicit all the predictions and then take the median. The alternative mechanism shares the same theoretical properties, and we discuss the advantages and disadvantages of this alternative.
Mechanism D may look too obscure to be implemented in practice. However, very simple and understandable questionnaires implementing the mechanism can be designed. In our running example of faculty candidate hiring, the questionnaire corresponding to our mechanism could look like:
1. Choose one of the followings:
(a) I definitely want accept this candidate, regardless of my colleagues' inputs.
(b) I definitely want reject this candidate, regardless of my colleagues' inputs.
(c) After talking to the candidate, am more inclined accept him/her than before.
(d) After talking to the candidate, am more inclined to reject him/her than before.
2. If your answer is (c) or (d) in the first question, what percentage of the faculty members do you believe will choose (a) or (c) in the first question?
In the first question above, faculty members of type F (type U resp.) will choose (a) ((b) resp.). Faculty members of type C' will choose either (c) or (d) depending on the signals they have received. If a faculty member receives signal h, (s)he believes world H is more likely than before. Notice that, it is still possible that (s)he believes the probability of world H being the actual world is less than 50% and (s)he still prefers rejecting the candidate based his/her private information (for example, his/her prior belief may be only 10% for world H, and his/her posterior belief for this increases to 30% upon receiving signal h),, so the description that (s) is "more inclined to accept the candidate than before" accurately implements Mechanism I
The same holds for those receiving signal E.
3.3 Main Theoretical Results for Our Mechanism
We first show that our mechanism indeed achieves (with an exponentially small failure probability) the goal of outputting the alternative favored by the majority, assuming agents are truth-telling.
Theorem 3.2. If all the agents play the truthful strategy Σ', then, with probability at least 1 - 2 expp( 2200-222cc00 (where is the constant defined in Eqn. 16)), our mechanism outputs an alternative that is favored by more than half of the agents.
Proof. Suppose all the agents report truthfully. Step 5 of the mechanism guarantees that the majority wish will be announced with probability 1 if either are 0.5 or ag > 0.5. It remains to consider the case where we have both or < 0.5 and ag < 0 In this case, A is favored by the majority if the actual world is H, and R is favored by the majority if the actual world is L.
'Recall that have assume I' is odd number, so cannot have ar 0.5 au 0.5.
8

---

If contingent agent t receives signal h, (s)he will believe that a Tha fraction of agents receive (before the treatment at Step 2), and (s)he will report 8, acTna + ar (after considering the treatment at Step 2). Similarly, contingent agent receiving signal will report 6 ac he tor. We have 8, = 0 for each mundidae--rrenndly agent and 6, = for each candidate-unfriendl agent. Since we are considering the case OxF; oU < 0.5, the median ō is in the interval (acThe he + Th + tog) (note that The < Th by Theorem 3.1
Suppose the actual world is L. The expected fraction of the agents receiving signal la would be PAL and the expected fraction of the agents reporting signal h (after the treatment at Step 2) would be ac PhL. + ap. By Chernoff bound, with probability at least 1 - 2 exp(- (app(22caar Tc the fraction of agents reporting signal h is in the interval lac (PAL - c) + aF, ac (PhL + c) + aF]. which is less than ac The + ap I 8 by Theorem 3.1 and 66. Step 6 of the mechanism indicates that R will be announced. The analysis for the case where H is the actual world similar.
Next, we show that the truthful strategy profile is an e-strong Bayes Nash equilibrium of our mechanism for some exponentially small E.
Theorem 3.3. The truthful strategy profile is an e-strong Bayes Nash equilibrium, where (2B² + exp()xxp(22)) exp(-22"accT)
3.4 Proof Theorem
3.3 with T 00
We defer the full proof of Theorem 3.3 to Appendix B.3 Here we prove the following limit version. where T + co, which illustrates the key features while eliminating the need for both Chernoff bound analyses and for some additional subtle corner cases.
Theorem 3.4. For - 00, the truthful strategy profile is strong Bayes Nash equilibrium.
We consider three cases: 1) aF > 0.5, 2) ay > 0.5 and 3) oF < 0.5 and ay < 0.5.
In the first case, more than half of the agents are candidate-friende friendly,, and A will be announced according to Step 5 of the mechanism these agents report truthfully. The truthful strategy profile forms strong Bayes Nash equilibrium, those candidate- friendddf agents receive their maximum utilities by truth-telling and the remaining agents are not able to stop the mechanism from outputting A regardless of what they report. The analysis for the second case is the analogous to the first case. It remains to consider the third case.
Under the third case, A is favored by the majority if the actual world is H, and R is favored by the majority if the actual world is L. By the same analysis as in the proof of Theorem 3.2 supposing agents report truthfully, the actual world is H, and R will be output if the actual world is L. Therefore, the contingent agents (type C)) receive their maximum utilities, and thus have no incentive deviate from the truthful strategy.
know that A will be output with probability 1 (by taking the limit T + oo)
To conclude that truth-telling is strong Bayes Nash equilibrium, we will show that there is no coalition of deviating agents (see the paragraph following Definition 2.1. Let M' be the strategy profile after D's deviation.
Next, we show that D cannot contain both a type F agent and a type U agent. The following lemma shows that an increase in type F agent's 's (ex-ante) utility always results a decrease in type U agent's (ex-ante) utility, and vice versa. This is obvious if we are dealing with ex-post utilities. as a candidate- frrinadd agent and a candidate- candidate-unfrrendlly agent always want the opposite alternatives. However, this becomes less obvious for ex-ante utilities.
Lemma 3.5. Suppose or < 0.5 and ou < 0.5. Let Ex be the truthful strategy profile and E' be an arbitrary strategy profile. Let i be an arbitrary candidate-friendly agent and by be an arbitrary candidate candidate-unfriendae unfriendly agent. We have
(i) If u. (E')- u1,, (Σ*)= > 0, then ut, (E') u1, (E*) < 0.
(ii) ufz (E') Utz (E*) > then uz, (E') We, (E*) < O.
Proof. By (), we have
ue (a'E) us - T -VHHH R)),

---

where r = PL( - -((0)) and Fи = PH(A) - Theorem 3.2 implies
M2 = 0 and (x*) = (with T + oo), which implies T',, 2 O. By
2 we have
AL(,A) A)( <0 (,(,, - v,(H, which further implies A)) er (L, <
2 (H, VeHH, Rj. Since type F agent always prefers A and a type U agent always prefers R,
<< u/ AT -1, (T, R)
ot [., A) - Vt, (H, R):
and
1/2 [L, A) 012 (L, R) < Vty Vt (H, Ut2 (H,R) < <0.
Intuitively, this means U4, (Σ') - v4, (Σ') is more sensitive to HH and u4, (E') - U4g (Σ') ) is more
sensitively to [z. Formally, ut, (E') ut, (Σn) > 0 implies L TH "t, (HIA) - (H.R)
Ve, (L.A) -v, (L.R) [ and
242 (E') Ue, (x*) 2 0 implies r S T "t (H.A) 21, (H.R)
Veg (L,A)- [L,RJ I r H. Thus, ue, (E') U4, (E*) 0
and 14 (E') - 412 (E*) 2 O cannot be both true. The proof for (ii) is similar.
We have seen that the deviating coalition D cannot contain any contingent agents (since their ex-ante utilities have already been maximized). Thus, Lemma 3.5 implies D can only be comprised of either -fiendy agents or candidate-unfrrenddy agents. Finally, we show that minority coalition comprised of only Sandidate-friendde agents or only audidate-unfriendd agents cannot change the outcome by misreporting. We consider sandidate-friendde agents without loss of generality.
Suppose contains only mundidate-friend]] agents. Those agents cannot make the mechanism output A at Step 5, because fewer than 1/2 of the agents report type F no matter how agents in D deviate. To maximize the chance for the mechanism to output A at Step 6, those aundidate-friendf agents would like to maximize the fraction of agents reporting h and minimize the median of the prediction However, the mechanism already does this when those candidate- friiedddy agents play the truthful strategy: their signals are treated as h at Step 2. and their predictions are treated as 0 at Step 3. The same analysis works when D contains only aundidat--unfriende agents. This concludes the proof for Theorem 34
In fact, the arguments in the previous paragraph show that: truth telling is dominant strategy for each candidate-friendle agent and each candidate candidate-umfrrendll agent.
4 Remarks, Limitations and Future Work
We have assumed agents are Bayesian. Although this assumption may not be completely realistic in practice, we believe the theoretical properties of our mechanism still hold to a certain extent. For example, agents may not exactly predict TcT + a or ac oF in practice, but it is reasonable to assume that their predictions are roughly around these two numbers, or in between. If so, all the theoretical properties will still hold. |Prelec et al. [017]] also assume Bayesian agents in the theoretical analysis of the surprisingly popular method, but their empirical experiments with human subjects suggest the method still works in practice.
Our mechanism can be extended to the setting where a fixed fraction 7 of acceptance votes is required to adopt a policy. For example, in many countries, constitutional amendments requires 2/3 majority to pass. To do this, we only need to change Step 4 of Mechanism I such that 5 is the prediction with rank rT, and change Step 5 such that A is announced if more than fraction of agents report type F and R is announced if more than 1 - 7 fraction of agents report type U.
One limitation is that our mechanism only deals with two alternatives. While this is natural in many scenarios (accept/reject, election with two candidates), extending our results to more than two alternatives is an interesting future direction, but faces a multitude of hurdles: the median technique will not straightforwardly work, the "surprisingly popular" formalism faces impossibility results [Prelec et al. 2017). and
social choice impossibility results apply.
Another interesting future direction deployment. Our Wisdom-of- oh-tth-Croww- Crowd-Voting mechanism could be used in any place that currently uses majority voting to better aggregate information. Of course, would suffer from some of the same drawbacks of majority voting: that the majority can impose their will on the minority. It is not clear if either one of these enjoys faimess properties not included by the other, but that would be another direction of future inquiry. It would be interesting to test this mechanism in the real world, and then test to see if participants are, in aggregate, more pleased with the alternatives selected by this mechanism as compared with those selected by a majority vote.
10

---

Acknowledgement
We gratefully thank Noah Burrell and the anonymous reviewers for the helpful comments and suggestions for improving this paper.
Funding Transparency Statement
All the funding support related to this paper has been declared at the bottom of Page 1.
References
David Austen-Smith and Jeffrey S. Banks. Information aggregation, rationality, and the condorcet jury theorem. American political science review, 90(1):34 45, 1996.
Duncan Black. On the Rationale of Group Decision-making Journal of political economy, 56(1), 1948.
Kay- Yut Chen, Leslie R Fine, and Bernardo A Huberman. Eliminating public knowledge biases in information agggregatonn mechanisms. Management Science, 50(7):983-994, 2004.
Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Compulation, pages 9-26, 2018.
Anirban Dasgupta and Arpita Ghosh. Crowdsourced judgement elicitation with endogenous profi- ciency. In Proceedings of the 22nd international conference on World Wide Web, pages 319-330. International World Wide Web Conferences Steering Committee, 2013.
N. De Condorcet. Essai sur l'application de l'analyse la probabilité des décisions rendues à la pluralité des voix. L'imprimerie royale, 1785.
Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8)755-777, 2010.
Boi Faltings and Goran Radanovic. Game theory for data science: Eliciting truthful information. Synthesis Lectures Artificial Intelligence and Machine Learning, 11(2):1-151, 2017.
Timothy Feddersen and Wolfgang Pesendorfer. Voting behavior and information aggregation in
elections with private information. Econometrica, 6525)1102-11058, 1997. ISSN 00129682, 14680262. /ttp:tt://www jstor. wtrgsstabble2171887
A. Gao, J. R. Wright, and K. Leyton-Bree Brown. Incentivizing Evaluation via Limited Access to Ground Truth: Peer-Prediction Makes Things Worse. ArXiv e-prints, June 2016.
Ralph Hertwig. Tapping into the wisdom of the crowd with confidence. Science, 336(6079): 303-304, 2012.
Hadi Hosseini, Debmalya Mandal, Nisarg Shah, and Kevin Shi. Surprisingly popular voting recov- ers rankings, surprisingly! In Proceedings of the International Joint Conference on Artificial Intelligence (forthcoming). 2021.
Harold Hotelling. Stability in Competition. The Economic Journal, 39(153), 1929.
Leslic John, George Loewenstein, and Drazen Prelec. Measuring the prevalence of questionable research practices with incentives for truth telling. Psychological science, 23(5):524-532. 2012.
Yuqing Kong. Dominantly truthful multi-task peer prediction with constant number of tasks. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithums (SODA), 2020.
Yuqing Kong and Grant Schoenebeck. Equilibrium selection in information elicitation without verification via information monotonicity. In Proceedings of the 9th Innovations Theoretical Computer Science (ITCS 2018), January 2018a.

---

Yuqing Kong and Grant Schoenebeck. Eliciting expertise without verification. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), pages 195-212, 2018b.
Yuqing Kong and Grant Schoenebeck. A Framework For Designing Information Elicitation Mecha- nisms That Reward Truth-telling. ACM Transactions Economics and Computation (TEAC), 7 (1), 2019.
Yuqing Kong, Grant Schoenebeck, Biaoshuai Tao, and Fang-Y Yi Yu. Information elicitation mecha- nisms for statistical estimation. In Proceedings the AAAI Conference Artificial Intelligence, volume 34(2), pages 2095-2102, 2020.
Krishna K. Ladha. The Condorcet Jury Theorem, Free Speech, and Correlated Votes. American Journal of Political Science, 36(3), 1992.
N. Miller. Information, Flectorates, and Democracy: some Extensions and Interpretations of the Condorcet Jury Theorem. Information Pooling and Group Decision Making, 1986.
N. Miller, P. Resnick, and R. Zeckhauser. Eliciting informative feedback: The peer- pper-prediction method. Management Science, pages 1373, 2005.
Shmuel Nitzan and Jacob Paroush. Collective decision making and jury theorems. The Oxford Handdbook of Law and Economics, 1, 2017.
Javier Perote and Juan Perote-Pena. Strategy-prodd estimators for simple regression. Mathematical Social Sciences, 47(2):153-176, 2004.
D. Prelec. A Bayesian Truth Serum for subjective data. Science, 306(5695):462 2004.
Dražen Prelec, H Sebastian Seung, and John McCoy. A solution to the single-question crowd wisdom problem. Nature, 5375535))33 2017.
Grant Schoenebeck and Fang-Yt Yi Yu. Two strongly truthful mechanisms for three heterogeneous agents answering question. In Web and Internet Economics, pages 119-132, Cham, 2020. Springer International Publishing. ISBN 978-3-030-64946-3.
Grant Schoenebeck and Fang-Y Yi Yu. Learning and strongly truthful multi-task setting peer prediction: variational approach. In Proceedings of the 12th Innovations in Theoretical Computer Science (ITCS 202/), Jamuary 2021.
Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C Parkes. Informed truthfulness in multi-task peer prediction. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 179-196, 2016.
Joseph P Simmons, Leif D Nelson, Jeff Galak, and Shane Frederick. Intuitive biases in choice versus estimation: Implications for the wisdom of crowds. Journal of Consumer Research, 38(1):1-15, 2011.
Peyton Young. Condorcet's Theory of Voting. American Political Science, 82(4), 1988.
Peter Zhang and Yiling Chen. Elicitability and knowledge free elicitation with peer prediction. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 242- 2014.
12


Reviews:
[{"review_id": "oDGUhisvjAo", "reviewer": "Reviewer_3nmy", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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.\n\nIf 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. \n\nAlso, the Bayesian update step is quite complicated, and I don't think people will perfectly update every time. \n\nI 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.\n\nMinor comments:\n\nAll instances of \"surprising popular\" should be surprisingly popular\" (e.g., 90, 125, 253, ...)\n124: suggest removing \"rely on the same notions\"\nThm 3.1: period at end\n279: You should note that c as defined after line 279 is for Chernoff bounds later (e.g., in Thm 3.2).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "aqeSSrioDEL", "reviewer": "Reviewer_kct9", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nPost Author Response:\nThanks for your response.  On a few of the points raised:\n\nTwo 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.\n\nEx-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.\n\nTheorem 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nI 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:\n- 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.  \n- 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. \n- 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.\n- 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?\n- The transition into 3.2 seems rushed and jumps into the analysis in mid thought: “At Step 3 of the mechanism...”", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "P06eO92jya3", "reviewer": "Reviewer_k218", "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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. \n\nThe 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.\n\nOverall, 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).\n\n### Questions:\n1) What if I replace median in the mechanism with mean? Is there any obvious objection to that?\n2) 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? \n\n### Typos:\n1) line 180 \"$v_t(H, A) > v_t(L, A)$\" -> \"$v_t(H, A) > v_t(H, R)$\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have adequately addressed the limitations, and I don't see any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OG8Z5MOAce1", "reviewer": "Reviewer_M3RC", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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. \n\nComments:\n\nThe 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.\n\nIt would be good to discuss a little bit how to extend the result to more general settings in the main text.\n\nQuestions:\n\nPlease 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?\n\nAt 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)