Strategyproof Voting under Correlated Beliefs
Authors: Daniel Halpern
Rachel Li
Ariel D. Procaccia
Venue: NeurIPS 2023 poster (2023)
Keywords: social choice
strategyproof
voting
TL;DR: We study strategyproof voting rules when agents have beliefs about how others may vote.

Abstract: In voting theory, when voters have ranked preferences over candidates, the celebrated Gibbard-Satterthwaite Theorem essentially rules out the existence of reasonable strategyproof methods for picking a winner. What if we weaken strategyproofness to only hold for Bayesian voters with beliefs over others' preferences? When voters believe other participants' rankings are drawn independently from a fixed distribution, the impossibility persists. However, it is quite reasonable for a voter to believe that other votes are correlated, either to each other or to their own ranking. We consider such beliefs induced by classic probabilistic models in social choice such as the Mallows, Placket-Luce, and Thurstone-Mosteller models. We single out the plurality rule (choosing the candidate ranked first most often) as a particularly promising choice as it is strategyproof for a large class of beliefs containing the specific ones we introduce. Further, we show that plurality is unique among positional scoring rules in having this property: no other scoring rule is strategyproof for beliefs induced by the Mallows model when there are a sufficient number of voters. Finally, we give examples of prominent non-scoring voting rules failing to be strategyproof on beliefs in this class, further bolstering the case for plurality.

Strategyproof Voting under Correlated Beliefs
Daniel Halpern Harvard University dhalperngg. harvard.edu
Rachel Li
Harvard University
rachelli@college harvard. edu
Ariel D. Procaccia Harvard University
arielprodseas harvard. edu
Abstract
In voting theory, when voters have ranked preferences over candidates, the cele- brated Gibbard-Satterthwaate Theorem essentially rules out the existence of rea- sonable strategyproof methods for picking a winner. What if weaken strate- gyproofness only hold for Bayesian voters with beliefs over others' preferences? When voters believe other participants' rankings are drawn independently from a fixed distribution, the impossibility persists. However, it is quite reasonable for a voter to believe that other votes are correlated, either to each other or to their own ranking. We consider such beliefs induced by classic probabilistic models in social choice such as the Mallows, Placket- We single out the plurality rule (choosing the candidate ranked first most often) as a particularly promising choice as it is strategyproof for a large class of beliefs containing the specific ones introduce. Further, show that plurality is unique among positional scoring rules in having this property: no other scoring rule is strategyproof for beliefs induced by the Mallows model when there are sufficient number of voters. Finally, we give examples of prominent non-scoring voting rules failing be strategyproof on beliefs in this class, further bolstering the case for plurality.
and Seuurtonne-ostelle
models.
Introduction
One of the most celebrated results in voting theory the Sibbaad-SStterthwall Theorem [8, 22]. states that when voters express ordinal preferences over at least 3 candidates, there is no "reasonable" aggregation rule that is strategy-proof: there will always exist instances where voters will be incentivized to manipulate and lie about their preferences to achieve a better outcome.
However, caveat about this strong negative result is that, priori, voter may need perfect information about how others vote to manipulate successfully. Perhaps, if the voter is slightly uncertain, manipulation helps consistently enough be worthwhile. Majumdar and Sen [13] analyzed exactly this question when voters have independent beliefs. That is, when a voter is considering whether not to manipulate, they assume all others have rankings drawn independently from fixed distribution. The classic notion of strategyproofness no longer makes sense in this probabilistic Bayesian setting, so they instead incentive compatible (OBIC), essentially that the rules are strategyproof in expectation no matter what underlying cardinal values voters have. Their results, unfortunately, are widely negative. They show that for "large" set of distributions, where many rules are OBIC, e.g., the uniform distribution over all rankings. Still, these positive examples are extremely brittle: even slight perturbation leads back to the impossibility.
the natural extension known as ordinally Bayesian
still holds. There do exist distributions
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

But independent beliefs are quite restrictive. They cannot capture several kinds of beliefs that would likely occur practice. For one, when the number of voters large, the uncertainty essentially vanishes. Suppose a distribution places probability 1 1/4 on other voters having the ranking a > b > c. In that case, when the number of voters large, is extremely unlikely that the proportion of voters with this ranking is anything other than 1/4 + e. In real presidential election, a voter may quite plausibly believe that a candidate will receive anywhere between 45% and 55% of the votes, but this situation simply cannot be captured by a single independent ranking distribution. Second, one's own ranking may influence the probability placed on others. Suppose a voter, after much research, discovers that they prefer one proposal to another; they may reasonably believe others are clever enough to have reached a similar conclusion. In terms of their beliefs, they may place a slightly higher probability others voting more similarly them than not, no matter what their realized preferences are.
This has led follow-up work to consider the same question under correlated beliefs [1, 16, 14, 2]. However, besides some impossibilities, the work so far has largely been of the following form: for any reasonable voting rule, there existy set of belief's where the rule is OBIC. But perhaps the more natural direction is the converse: under a natural set of beliefs, is there a reasonable voting rule that is consistently OBIC? Can this property help us distinguish between voting rules, showing that under some reasonable beliefs, certain rules are not OBIC, thereby bolstering the case for the provably nncentive-coppatibe ones? These are the questions tackle.
Our contributions. We begin by presenting various classes of beliefs induced by classic proba- bilistic social choice models such as the Mallows [15], Cetrsttone-Mstellle [23, 18], and Placket- Luce [20, 12] models. In essence, these are the beliefs a voter would have if they assume that voter preferences were generated by such model. Inspired by these models, we present novel class of mildly correlated beliefs that includes all of them. We show that, under this class of beliefs, the plurality rule is OBIC.
Next, we provide a negative result: Among positional scoring rules (where each voter assigns fixed score to each position in their ranking), plurality is unique in being OBIC when voters have Mallows beliefs. All other rules will become not OBIC when there are three candidates, at least when there are sufficient number of voters. In addition, we provide some robustness checks on this negative result. A popular positional scoring rule known as Borda Count fails for any number of voters. By contrast, we identify other positional scoring rules that are OBIC with two voters, meaning our result could not be strengthened by relaxing the sufficient number of voters requirement.
Finally, we complement this more sweeping classification with examples of other prominent rules, such as Copeland and maximin, which fail to be OBIC with specific Mallows beliefs and few voters. This further bolsters the case for plurality as an unusually attractive rule when viewed through the lens of ordinal Bayesian incentive compatibility under correlated beliefs.
Related work. As mentioned above, the analysis of OBIC voting rules began with Majumdar and Sen [13] essentially providing the final word on independent beliefs; their notion of OBIC dates back to work on committee selection [5].
Since then, there have been a few lines of work on correlated beliefs with slightly different goals. The most closely related is that of Majumdar and Sen [14]. They define a large class of positively correlated beliefs based on the Kemeny metric and then show in similar fashion to the Gibbard- Satterthwaite Theorem that any voting rule that is OBIC with respect to these beliefs, along with being Pareto efficient, is necessarily dictatorial. They do present one voting rule that is both OBIC with respect to these beliefs and nondictatorial (while not being Pareto efficient), but it is a clearly impractical rule that is designed to make a technical point. Note that all the rules we consider are Pareto efficient.
Another line of work considers local OBIC. voting rule is locally OBIC with respect class of beliefs if there exists a belief in the class such that any belief in a neighborhood of the original is OBIC. This means the rule remains OBIC even after a slight perturbation to the underlying belief, Bhargava et al. [1] and Bose and Roy [2] attempt to classify the set of locally OBIC voting rules with
'Their rule is called Unanimity with Status Quo. There is one default candidate x. If there is candidate which every single voter places their top choice, then y is elected, but in any other case, wins.

---

respect to a large class of correlated beliefs and show that under minimal conditions, this requirement
can be satisfied.
Mandal and Parkes [16] consider a different notion of incentive compatibility which, rather than requiring that no manipulation lead to utility gain in expectation, bounds the probability under which there is utility gain. They again do this with respect to several different classes of belief', including one that we consider based on the Mallows Model.
Further afield, there are extensive lines of research on circumventing the Theorem. We provide examples of three here, although there are many others. One line considers the complexity, showing that some rules, while in principle susceptible to manipulation, have instances where it is hard (in the worst case) to find such a manipulation [7, 3]. Another considers strategyproofness under restricted domains, where a voter's set of possible rankings is limited [7, 3]. A third considers the likelihood of an individual arriving in instance where they are able to manipulate at all [17, 25].
Finally, without considering strategyproofness, there has been much work on probabilistic social choice, making use of the models on which our results are based, especially in learning preferences from data [11, 24, 10, 19].
2 Model
We begin by introducing the classic social model and then later describe relevant definitions for social choice under uncertainty.
Classic social choice model. Let N [l.....n] n be a set of n voters, and let A {(1..................... am be set of alternatives. Let L be the set of rankings over A, where for L, ( is the j ''th candidate in ranking a and o (a)) is the ranking index of candidate a. We use the notation a >a to denote that o (a) (b) and a Za b to denote o (a) S o (b), i.e., a is strictly (or weakly) preferred to b under a. Additionally, instead of writing a = a > > c, when it is clear from context, will sometimes shorten this to a abc. Each voter i has a ranking o; E L and the tuple of these rankings a = (oI,..., .n) E L is called the preference profile We let a E L denote the profile without voter i, and for a ranking of E C. we let (o- o/) be the profile with o, replaced with o/
A voting rule is a function f that, given a profile o,, outputs distribution over winning alternatives. We define several voting rules of interest here. Our theoretical results will primarily focus on positional scoring rules [26]. A positional scoring rule f is parameterized by vector of ( 8m) where each 8, E Zzo with 81 2 ... 2 8m and 81 > 8mn On a profile a,, for each voter i, their j'th candidate (j) is given 8j points. The points
added up over all voters, and the winning candidate is the one with the most points. More formally, for a ranking a E L and candidate c E A. So-1(c) for the points (or score) given to c by a. For a profile o, we write sc((o) = Σ, sc! (a:) to the total points. When f clear from context, we may drop it from the notation. In deterministic settings, when there is a tie, a tie-breaking rule needs to be given (i.e., tie-break in favor of lower index candidates). Since we will be working in a probabilistic setting, will be more convenient to assume uniform random tie beebbreaknng, candidates, each wins with probability 1/k. However, our results would continue to hold even with arbitrary deterministic choices. Two rules of particular interest are plurality, parameterized by the vector (1, (1......,9) 0), and Borda count, parameterized by the vector (m - 1, m - 2...., ......,,,00) 1,.
we write sc (a)
that if there is a tic among k
We consider two additional rules beyond positional scoring rules, Copeland and maximin. To define them, for a profile o we define the pairwise margin for two candidates a and b, Nat(or) [ilaa > b)), i.e., the number of voters that prefer candidate to candidate b.
For Copeland, we define the Copeland score for a candidate a Enga (o) > n/2] (N/2)INN<(o) n n/2]. In words, the candidate gets one point for every other candidate they pairwise beat and a half point for every other candidate they pairwise tie. The Copeland winners are those with the highest Copeland scores (with uniform tie-breaking). For maximin, we define the maximin score for a candidate as mingya (a) i.e., the smallest margin by which a beats another candidate. Again, the maximin winners are those with the highest maximin scores (with uniform tie- breakin.
3

---

A voting rule f is called strategy-proof if for all profiles o, all voters i, and all alternative manip- ulations of E C. f(a) Zo. f() That is, no voter can ever improve the outcome of the vote by misreporting. A rule is called onto if for all candidates a E A, there is a profile or where f(o)= = a, and called dictatorial if there a voter for which f(a) = o ) i.e., voter i always gets their top choice. The that is strategy-prool and onto is necessarily dictatorial. Since "reasonable" rules must be onto and nondictatorial, this eliminates the possibility of any being strategy-proof.
Theorem states that any rule for m 2 3 candidates
These notions can also be extended to randomized rules. utility function u is a mapping from candidates to real numbers. We say that u is consistent with ranking a if u(z) > u(y) +> x >o y. (randomized) voting rule f is called SD-strategy-pree -proof if for all profiles a. all voters i, all manipulations o', and all utility functions u consistent with os, B[u(f(or) 2 Blu(f(o-i;:) =.)]. This says that no matter what underlying utilities an agent has, as long as they are consistent with their ranking, they cannot improve their expected utility by manipulation. An equivalent definition can be given with respect to stochastic dominance (hence the SD in the name). For S m, let (x) = {o((), ..... ( [k)} be the set of the k best alternatives according to Then, SD-strategy- proofness can be rephrased as requiring that for all profiles a, all voters i, all manipulations af. and all k S m, (r( E Bx (a,)) 2 Pr[f(o -i, of) E (o.)).
We say a rule f is unilateral it depends only on a single voter, i.e., there a voter such that for all o and o'. if 0; = of then f(o) = f(o'). A rule f is called a duple if its range is two candidates, i... there is pair of candidates a and such that for all o. f(r) {a, bj. Gibbard [9] extended the Subbbard-Sattertwwall strategyproof is a mixture over unilateral and duple rules. Since unilateral and duple rules are seen as undesirable, this implies that finding a reasonable, strategy-prom voting rule, even allowing randomization, is a hopeless endeavor.
theorem to randomized rules as follows: Any randomized rule f that
Social choice under uncertainty. A belief for voter is a probability measure P. over the set of profiles f (when the i is clear from context will drop it from the notation). This describes i's prior probability over profiles before considering their own ranking. After observing their own ranking og the voter can update their posterior using the conditional distribution P[- o; = ā.]. For notational convenience, we will often shorten this to PP[- ō.].
In this model, we need a slightly different notion of strategyyroofnes.. A voting rule is called ordinally Bayesian incentive compatible (OBIC) with respect to a beliefs (PI...., Pn)) if for all voters i, all rankings o,, all manipulations of and all utility functions u consistent with o,, E (fu(f(o og)) 6,] 2 ff o') ō,]. This is the natural generalization of SD-strategyyrooffees to a Bayesian setting. Just as with SDD-strategyrroofness all manipulations d', and all < m, (1, E BL(),) | at 2 ([ (i--i,,))) of) E Ba( ō.).
an equivalent definition is for all voters all rankings os,
We now present few possible choices of "reasonable" priors based on well-known probabilistic models of social choice. The first is based off of a Mallows Model [15]. This model is parameterized by ground truth ranking E L and a dispersion quantity sp We define the Kendall tau distance between rankings d(01, 02) = ({a,b) E A² a >ai b b >oz a}1. ie., the number of pairs of candidates which d1 and d2 disagree. In Mallows Model, each voter's ranking is drawn independently with probability proportional to dlee.)) More formally, the probability that a specific ranking a is drawn is equal to sd((r.-) where Z = =E (dl(..)) is the normalizing constant. One can easily check that if we extend the notion of Kendall tau distance to operate on profile and ranking, with d(a r) = E; d(a;,,)) T), then the probability of sampling a profile or is proportional to pe((.r) (this time with a z" normalizing constant).
We convert this model into prior in two ways. The first we call confident Mallows prior parameterized by s. The agent assumes a ground truth т is first drawn from some (arbitrary) distribution, then, given this ground truth, a; with probability and the remainder of the profile a-; is drawn from a Mallows Model with a fixed using r. Essentially, the agent believes that they correctly know the ground truth, but all others only approximate this truth using a Mallows Model. The conditional distribution over the remainder of the profile o given à; then follows a standard Mallows model with the ground truth equal to o; so P ; a.] x la ..)
This is equivalent to the Conditional Mallows Model of Mandal and Parkes [16].

---

The second we call an unconfident Mallows prior. Here, the agent believes that the ground truth T is drawn uniformly at random. and then the entire profile (including their own ranking) is drawn from Mallows Model. Therefore, Poa) क. Erec = Pr(a; = =,s] m!!
Since for any o; by symmetry
2"
can write the conditional probability as
oallia (:fe).))
l0 (.)
Plo |6
z
TEC
TEC
We will abuse notation slightly and write P(r [āg] gd(0).7)
and Plo- 1
|-] 2" r. so that
Plo-: [i)] = Σ Pla- T P/r 6:]-
TEC
We can interpret this as saying the voter has a posterior over ground truths, P(T @z]. and using this posterior to infer the probability of the rest of the profile. Intuitively, the agent is uncertain over ground truths but, due to the observation of their ranking, places higher weight on ground truths that closer to their own ranking. This decomposition is possible because the rest of the profile a is conditionally independent of o; given the ground truth T.
The Whurstone-Mostelle model is defined with respect to underlying means (4. for each candidate e E AA To sample a ranking, a value X. NN 1) drawn independently for each candidate e from normal distribution with variance around the mean. The resulting ranking is the order of the X values from highest to lowest. The Placket-Lace model is defined with respect underlying weights w. > 0 for each candidate E A. To sample ranking, we iteratively select a candidate c from the remaining unchosen candidates P with probability Eeep wn
To convert these models to beliefs, we assume that the voter believes there are underlying distinct means μ1 > ... pm (resp. weights w1 > .... > wm) but is uncertain about which candidate has which mean (resp. weight). To relate this to the Mallows belief, we will call this order т, the ground truth. In the confident version, the voter believes that their ranking is always equal T, but all other votes are drawn from the corresponding model. In the unconfident version, the voter believes a priori that F is drawn uniformly random, and then all voter rankings, including their own, are drawn from the corresponding model. As with the Mallows beliefs, the voter can do a Bayesian update to compute a posterior about which candidate was assigned to which weight. We can again decompose
PPoo- [. = Σ Plo || PP[T [
where, by Bayes' rule, P(rr| ā.] x P[o.[T]. the probability of generating à under the model with ground truth
Note that to make this more general, it would also make sense for the voter to believe there is a distribution over means or weights; our results continue hold with this more general class; however, for ease of presentation, we focus on the more restricted form.
3 Plurality is OBIC
We start by defining class of beliefs that we call top-choice correlated. The class is similar in spirit (although incomparable) to the class of top-set correlated beliefs introduced by Bhargava et al. [1].
To define the class, given profile and a candidate e E A, we let (L) = H[ (x(1) c}l be the plurality score of c, i... the number of voters that rank c first. Further, we let (LU(Or be the vector of plurality scores indexed by the candidates. A belief IP; is top-choice correlated if the following holds. Fix a ranking à; and let a = (1). Then, for all candidates b of a and all pairs of plurality vectors and r' such that r. = r' for all * a, b, Ta The lb r'. and Ta Tb. P(PLU(o-)) = r ō,] 2 (((LLU(O-;) = r'/ ā,]. This says that if the voter is told the remaining plurality scores of all other candidates except a and b, as well as possible scores for and b, they would think it is more likely that a (their top choice) has the higher score. In other words, all else being equal, the voter's top choice is more likely to perform better than other candidates.
We now claim that all of the specific beliefs we have introduced are top-choice correlated, suggesting that this condition is quite weak.
5

---

Lemma 1. The confident and unconfident versions of Mallows, Thutstone-Moseellr, and Placket- Luce beliefs under any parameter settings are top-choice correlated.
The proof of Lemma can be found in Appendix A. For confident versions of these beliefs, this is relatively straightforward as the models directly place higher mass on the voter's top choice being chosen. For the unconfident versions, slightly more intricate analysis is necessary show that more mass is placed on ground truth rankings where the voter's top choice higher, and from this, we can reach the same conclusion.
Despite the breadth of the class of top-choice correlated beliefs, it turns out that plurality OBIC for all beliefs in this class.
Lemma 2. Under any top-choice correlated beliefs, plurality is OBIC.
Proof. Let f be the plurality voting rule, i be an agent, and be their top-choice correlated belief. Suppose observes oz. and let be arbitrary utility function that is consistent with o,. Let a (1) be their top-ranked alternative.
Let af be possible manipulation for voter i, and let b = (1) be the top-ranked alternative. Notice that = then the outcome under plurality is identical, and this manipulation cannot be an improvement. Hence, from now we assume that * a.
E[u(f(o o:))l be the expected utility gain of switching from o; to of when others report a We wish to show that EiUG(o=_))áá) - O, where the expectation over the belief P. To simplify notation, we will allow the utility function u to operate on (nonempty) sets of candidates S as uS)) I
For o-i. let UG(o- -i).
Elu(f((--;;))
[ Eces u(c). Note that when the set of plurality winners on a profile is S, the expected utility is uSS).
We now partition the possible a-; based on their utility gain. Let C S A bJ be (nonempty) fine eight sets of profiles a-s depending on the winners under (a-1, σi) and (a-1. of). E1 (C)), En (C)), Ez(C)), C2(C)), Fa(C)), (C (C), (C). In each E(C) set, C will be the set of candidates excluding and b with the highest plurality score. We abuse notation slightly and write PLU(C) for the (tied) plurality score of each of these candidates and PLU(a) and PLU(b) for the plurality scores of and b. respectively. The sets are otherwise defined by the set of plurality winners in (a o2) and (a-s.o')) The definitions can be found in Table 1. One can check that these (disjoint) sets collectively cover all possible o where UG(o-:) is nonzero.
candidates not including a and b. For each set C, we de-
We can now rewrite the expected utility gain in terms of these sets. For each set E(C), we write UG (C)) for the expected utility gain for profiles a- E F(C)) (which will always be the same for all - E E(C)). From this, we have
B(UG(o
Σ
(a.)(a.) CAf
Our goal, again, is show that this expression is most 0. Notice that for each C, UG (C))
u(b) u(a) < 0 and UG(Es(C)) = Pे (u(b) - u(a)) < 0 because u(a) > u(c) for all other candidates In what remains, we show that for all C and each j 3,
P (EEC((()))))))C))) +
(EE (IE,
(I)
Fix arbitrary C. To do this, we show that for each j. UG (C))) 0. (C)(E(CC))) UG (C))) and (C)) 2 (C)) Together, these imply (1).
2
We analyze the case j = 1; the arguments for j = and j are very similar. Notice that
|C|
UG(E)(C))) = (Cu(ulo) - u(a) = C + (u(C) - u(a)),

---

Set
Condition
(0-1;0) Winners
(a-1.0) Winners
PLU(a)= PLU(C) PLU(6)
C'
PLU(b) PLU(C) > PLU(O) +1
CU
b
C2(C)
a PLU(C) PI +1
CU (a,b)
(2
(L) PLU(C) = (LU(a)) +1
C' (a,b)
b
(C) = PLU(a) + 1> (LU( +1
(u
C
C2 6
CLU PLU( + (LU
+1
C
cu(b)
E1(C)
a PLU(6) 2 PLU(C)
b C
ES(C)
CLU(C) = PLU(a)+ PLU(6) +1
(a
Table I: Definition of the sets E (C) ( E2()), E2( (a)) Ea(C), and (C). They contain all - that satisfy the corresponding condition. In each set, the contained o-; all have the same winners both (o- σ2) and (o- of) as seen in the corresponding columns.
and symmetrically
CC|
UG(E((C))) = u(b) - u(C = |C| + (u(b) - u(C)).
Since u(a) is maximal, (CY") - 0. Further,
(w0)))))))-- u(b)) 2 O.
IC|
uG (F()))))))))))( |C| | (u(a)
Finally, to show P[EI(C)) (C)) we consider the vectors of plurality scores (indexed by candidates) r and r that lead profile - end in up in Ei (C'² and (C) respectively. Due to the symmetry, there is natural bijection between these two sets of vectors obtained by swapping the a and b components. Further, by the definition of Fn (C)2 and E1 (C)), , the component of r is always strictly larger than the component. Since is top-choice correlated, for any two vectors that differ by swapping the and b components, IP[-|a:] always places higher mass on the vector in r". Therefore, P[E, 2 (C))__)) as needed.
From these two lemmas, we immediately derive our main positive result.
Theorem 1. When voters have beliefs that are any of the confident or unconfident versions of Mallows, Thurstone-Mosteller, or Placket-Lace under any parameter settings, plurality is OBIC.
4 Other Voting Rules Are Not OBIC
From the positive result about plurality, one might wonder whether satisfying OBIC with respect to these beliefs is a relatively weak condition. If several rules satisfy it, this property is not useful for mechanism designer who is comparing between rules to implement. In this section, we show this is the case. Specifically. we focus on both the confident and unconfident variants of Mallows beliefs. Our main theoretical negative result is that plurality is uniquely OBIC among positional scoring rules in certain regimes of Mallows beliefs.
Theorem 2. Let J be a non-plurality positional scoring rule on three candidates. If a voter has unconfident or confident Mallows beliefs with yp S .988, for a sufficiently large n, f is not OBIC.
Below we provide detailed proof sketch. However, we shunt some unwieldy technical derivations into two lemmas relegated the appendix.
Proof sketch of Theorem 2. we can translate and scale the vector such that 53 0 and si and 52 are relatively prime integers with
Fix a non-plurality scoring vector (2,, Sa). Without loss of generality,
$2 > 0. Fix a voter i with unconfident Mallows beliefs P with parameter yp < .988; we will describe later how extend it confident Mallow's 's belief. Suppose they observe ranking d; = a > b c. We will show that for sufficiently large n, it will be beneficial to switch to o = > c > b. More specifically, we will show that this manipulation increases the probability that candidate a wins, which means the rule cannot be OBIC with respect to these beliefs. Formally, we will show that,
Prif(a-1,
6.] Prif(o-1,6
0x),
7

---

or equivalently,
Pr[f(o-i.o)
-
[ >0.
Notice that since looking at the difference in probabilities of two events, ignore their intersection when both reports lead to a as the winner. That is, the left-hand side is equal to
Pr[f(a-i; -;; of) (i 0x) + 0t] Pr[f(aa-i- ..)
f(o Fa
To shorten notation, we will label the events of interest as 8ob = [ 0100 = a -, + a àd}} (i.e., ranking above causes a to win) and &oe = [[(ari,, 0;) = a (( of) # [ū]]
(i.e., ranking b above e causes win), so wish to show that
P| - ((, > 0.
Using the definition of the Mallows belief model, we can expand the left-hand side using ground truths to
Σ
( [r] - P( 7]) P(r ō.].
TEC
Consider the T= > c b term. Notice that, by symmetry Pl a > cx 6] P by c) and P[ a > -> b] = P(g a b b c). Further Pla + c > b o, = p- p-P b - e 0,
as d(a c> b, 0,) d(a
c, 5.) + Hence.
(
e> - Pl
r cx bl) Pla > b bl [s
= = (PPE T a > c| - Plgbe
T -= a > b c) F/a > > c 6:))
b c term. In fact, this same property holds for the other two pairs of ground truth rankings where remains in the same position and is swapped with c, so b > e with c > b and b c > with e b > Hence, we can write the entire expression (2) as
in words, the a > <> term is exactly equal to -p times the
(1 - v)) ( (IP(Er
T a + b c) P(
T = a > b Pla > b cl 6,
+ (PPggh
T b > a> c - Pighe
T b > a> c)) P/b > > c 6.]
+ (I((Ebb)
T b > a] - P 1 by c> al) Plb > a 0:1
Notice that since we wish to show this strictly larger than 0 and 1 - yp > 0. we show only that the sum of the probability terms is positive. Additionally, subbing in the values of P(r ō:] with the corresponding Kendall tau distances, the above simplifies
(p(gcb T a > by c) 13- - T= a b b c)
+ 40 (P(geb T = b > a > c) P(ghe -= b b- 0 a c)
(3)
+ 2² (19
> a] Plche T== by c al)
We will now show that for some ei C2 be chosen later, the first positive term P| | 7 a >
b > c] 2(cr)) and each negative term P| r] E O(e)), which implies that for sufficiently large n, the entire sum is positive, as needed. In addition, for the result to hold with confident Mallows rather than unconfident, it is only required that the first difference be positive, i.e.
Pf T a > b c] - P(ghe r b 0.
This is also directly implied by showing the above bounds.
We relegate these arguments to the following two lemmas, established in Appendices B and C, respectively.
Lemma 3. P 7] E O(c)) for =
p(1+2p) 14p++"2
*Note that since f is randomized, to make this precise we would need to specify the joint distribution of its outputs on different inputs. However, the remainder of the proof will not rely on how this is done, so the joint distribution be arbitrary.
8

---

t-p2 Lemma 4. P| T-= a b cl ((r)) oj > eaa v1oo) 1+++p"
[1122))
Together, the two lemmas imply the desired result.
We now complement this result with some additional robustness checks. First, even though the result asymptotic, in special cases of interest, this is, in fact, not necessary.
Theorem 3. With three candidates, when voler has unconfident or confident Mallows beliefs with sp < 1, Borda Count is not OBIC for any 2 2.
Notice that n = 1 a degenerate case with no other voters, so ni 2 2 the strongest we can hope for. The proof of Theorem 3 can be found in Appendix D. The beginning is nearly identical to the proof sketch of Theorem 2, but they diverge after this point. While Lemmas and 4 are asymptotic in nature, the corresponding portion for Theorem 3 requires careful counting of the number of profiles satisfying different conditions to ensure that for any fixed n, the incqualities hold.
In light of Theorem 3, it may seem plausible that Theorem 2 could be strengthened to hold for all rather than just asymptotically. However, we can give examples where this not the case, suggesting that a "sufficiently large n" requirement may be necessary. In particular, there are scoring rules that, while not being plurality, are "close" to plurality in the sense that 82 so tiny it only matters when there is tie among the plurality winners. For example, say we have the scoring rule (4, 1, with n = voters. If any candidate receives two first-place votes, they immediately have out of the 15 available points, so they necessarily win. Only when each candidate is ranked first by one voter is there any difference. We show in Appendix E that such close-to-plee -oluurallyy rules, at least for n = 3, are OBIC for confident Mallows beliefs with any & < 1.
Finally, we consider other prominent non-scoring rules, namely Copeland and maximin. Note that for explicitly- -effined beliefs and a number of voters we can determine whether or not rule is OBIC by computing the probabilities of winners under all possible manipulations. We do so for the aforementioned rules under both confident and unconfident Mallows beliefs with ş 0.25, 0.5, 0.75, n 2, 50, and m 3. The results can be found in Table 2. Although slightly mixed in the sense that in a few specific cases, OBIC holds, the key takeaway is that none of the rules considered are as consistently OBIC as plurality.
Copeland even
maximin with & 0.25,, 0.5
maximin with o 0.75
confident Mallows
all n # 3
+ 3
unconfident Mallows
n #
Table 2: Scenarios where the Copeland and maximin rules fail to be OBIC with respect to Confident and Unconfident Mallows beliefs with &p 0.25, 0.50, 0.75, 2.... 50, and m 3.
5 Discussion
In summary, we have considered the problem of strategic voting when voters have certain correlated beliefs over others. We have singled out plurality an auspicious choice, being incentive compatible for large class of beliefs, and have complemented this with negative results showing other prominent voting rules do not satisfy this property. However, our work is certainly not the final word on this topic. The current negative results are only for three candidates, and although we believe they should extend to larger number, the technical work in showing this seems to get quite messy. Further, although we have checked many prominent voting rules, we have not ruled out the existence of other "reasonable" rules that perform well plurality while simultancously satisfying other desiderata.
Finally, taking more practical viewpoint, although OBIC is theoretically compelling condition, is susceptible to common criticisms of models of voter behavior. As with many models of this form, the utility difference of misreporting, or of choosing any vote for that matter, can be very low, and is debatable whether this is the driving force in how voters make decisions. It raises questions similar in spirit to the so-called Parudox of Voting [6]: why would any rational agent choose to vote if the cost almost certainly outweighs the expected benefits? Despite these challenges, we do believe that the exploration and refinement of models such as OBIC can lead to an improved understanding of voter behavior and, ultimately, to the development of more effective voting systems.

---

References
[1] M. Bhargava, D. Majumdar, and A. Sen. Incentive-compatible voting rules with positively correlated beliefs. Theoretical Economics, 10(3):8678885, 2015.
[2] A. Bose and S. Roy. Correction to "Incentive-compaibble voting rules with positively correlated beliefs". Theoretical Economics, 17(2):99--94,, 2022.
[3] V. Conitzer and T. Walsh. Barriers to manipulation in voting. In F. Brandt, V. Conitzer, U. Endress, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 6. Cambridge University Press, 2016.
[4] M. Cover and J. A. Thomas. Information theory and statistics. Elements of Information Theory, 1(1):279-335, 1991.
[5] C. d' Aspremont and B. Peleg. Ordinal Bayesian incentive compatible representations of committees. Social Choice and Welfare, 5(4):261-279, 1988.
[6] A. Downs. An economic theory of political action in democracy. Journal of Political Economy, 65(2)1135-150, 1957.
[7] Faliszewski and A. D. Procaccia. AI's on manipulation: Are we winning? Al Magazine, 3 31(4):53-66 64, 2010.
[8] A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587-602, 1973.
[9] A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45:665-681, 1977.
[10] A. Kahng, M. K. Lee, R. Noothigattu, A. D. Procaccia, and C.-A. Psomas. Statistical foundations of virtual democracy. Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3173-3182, 2019.
[11] Lu and C. Boutilier. Learning Mallows models with pairwise preferences. In Proceedings of the 28th International Conference on Machine Learning (ICML), pages 145-152, 2011.
[12] R. Luce, Individual Choice Behavior: Theoretical Analysis. Wiley, 1959.
[13] D. Majumdar and A. Sen. Ordinally Bayesian incentive compatible voting rules. Econometrica, 72(2):523-54) 2004.
[14] D. Majumdar and A. Sen. Robust incentive compatibility of voting rules with positively correlated beliefs. Social Choice and Welfare, pages 1-33, 2021.
[15] C. L. Mallows. Non-null ranking models. Biometrika, 44:114-130, 1957.
[16] D. Mandal and D. Parkes. Correlated voting. In Proceedings of the 25th International Joint Conference Artificial Intelligence (IJCAI), pages 366-372, 2016.
[17] E. Mossel, A. Procaccia, and M. Rácz. A smooth transition from powerlessness to absolute power. Journal of Artificial Intelligence Research, 48:923-951, 2013.
[18] Mosteller. Remarks on the method of paired comparisons: the least squares solution assuming equal standard deviations and equal correlations. Psychometrika, 16(1):3-9, 1951.
[19] R. Noothigattu, D. Peters, and A. Procaccia. Axioms for learning from pairwise comparisons. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 17745-17754, 2020.
[20] R. Plackett. The analysis of permutations. Applied Statistics, 24:193 1022992222000 1975.
[21] N. Sanov. On the probability of large deviations of random variables. United States Air Force, Office of Scientific Research, 1958.
10

---

[22] M. Satterthwaite. Strategy-pree proofness and Arrow's ' conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10: 187-217, 1975.
[23] L. L. Thurstone. A law of comparative judgment. Psychological Review, 34:273-286, 1927.
[24] V. Vitelli, Ø. Sørensen, M. Crispino, A. Frigessi Di Rattalma, and E. Arjas. Probabilistic preference learning with the Mallows rank model. Journal of Machine Learning Research, 18 (158):1-49, 2018.
[25] L. Xia. How likely coalition voters can influence a large election? arXiv:2202.064111 2022.
[26] H. Young. Social choice scoring functions. SIAM Journal of Applied Mathematics, 28(4): 824-838, 1975.


Reviews:
[{"review_id": "aB1Js22WIp", "reviewer": "Reviewer_qwQq", "summary": "This paper studies the voting problem where agents' ranking preferences are correlated. Roughly speaking, voters do not know exactly each other's preferences; when a voter knows his/her own preference, (s)he can \"infer\" others' preferences. Strategyproofness is then defined with expected utilities. This is a practical setting where the classical Gibbard-Satterthwaite impossibility theorem does not apply. To model this, a prior distribution of voters' preferences is defined, and then a voter, after \"receiving\" his/her own preference, has a posterior belief over the preference distribution. The authors consider a wide range of distributions including Mallows (with both \"confident\" and \"unconfident\" variants), Placket-Luce, and Thurstone-Mosteller. The authors show that, among all the positional scoring rules (a positional scoring rule assigns a score to each ranking position, and the output depends only on the scores), the plurality voting rule is the only one that is \"strategyproof\" (or, OBIC as defined in the paper). Specifically, the authors show that the plurality voting rule is OBIC. On the other hand, with three alternatives, any other voting rule is not OBIC when the number of voters is sufficiently large. For Borda Count with three alternatives, it fails to be OBIC with any number of voters that is at least 2. One key observation is that any of the abovementioned distributions satisfies the so-called top-choice correlated property.", "questions": "No question.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "I believe the model studied in this paper is very reasonable and practical. The main results of this paper are neat and clean. The main message that the plurality voting rule stands out is also clean and promising. I think this paper provides a significant contribution to the social choice literature.", "weaknesses": "I find the result that the plurality rule being OBIC is not surprising. It is expected that the signal distributions have the top-choice correlated property, and it is also not very surprising that, with this property, plurality voting is OBIC. It may be more surprising to see that other voting rules fail to be OBIC.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "AetJ0X7Rwy", "reviewer": "Reviewer_jEy3", "summary": "The paper considers a typical social choice problem: to design a voting rule that has desirable properties (e.g., it is onto and non-dictatorship) and it does not enable voters to misreport their vote for achieving outcomes that she prefers more. It is known that this is impossible in general, even if one allows the voter to have a prior knowledge on the preferences of other voters. This work focuses on a particular structure of this prior knowledge, namely that other voters' preferences are correlated to the manipulating voter's preferences according to classical models for the generation of preferences in social choice as Mallows model, Placket-Luce model, and Thurstone-Mosteller model.\n\nQuite surprisingly, the paper proves that plurality dynamics is strategyproof when the agent has prior knowledge compatible with these models of preference generation, while other positional scoring (and Copeland and maxmin) rules are not, unless for a large number of voters.", "questions": "I believe that there is an error in the last two equations on page 6 (even if they do not affect the final result). Indeed it should be 1/(|C|+1) (u(C) - |C|u(a)) >= |C|/(|C|+1) (u(c) - u(a)), for c with minimum u(c) among all c in C (similar for the last equation). Am I right?", "limitations": "See above", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The problem is a well-established problem in social choice, and the paper provides a very positive result (the existence of a very natural voting rule that is strategyproof in a very realistic setting).\n\nMoreover, the result is also surprising (the fact that plurality enjoy the property, while other rules fail.) This result is in a way also robust. Indeed the author proves strategyproofness of plurality not only for the above cited models of preference generation, but for a superclass of them (that contains also noisy variations of above models whenever noise is small).", "weaknesses": "As recognized by the authors: the negative results only holds for three candidates (it is thus possible but conjectured to be improbable that for more than three candidates plurality is not the unique rule to enjoy all desired properties).\n\nThe paper only provides an analysis of specific voting rules, but not a characterization of strategyproof rules.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer Comment:**\n\n> I believe that there is an error in the last two equations on page 6 (even if they do not affect the final result). Indeed it should be $1/(|C|+1) (u(C) - |C|u(a)) \\geq |C|/(|C|+1) (u(c) - u(a))$, for $c$ with minimum $u(c)$ among all $c$ in $C$ (similar for the last equation). Am I right?\n\n**Response:**\n\nWe don't believe so. Recall that we defined the utility of a set of candidates to be the mean of the individual utilties, so $u(S) = \\frac{1}{|S|}\\sum_{c \\in S} u(c)$. Therefore, $u(C \\cup \\{a\\}) = \\frac{\\sum_{c \\in C \\cup \\{a\\}} u(c)}{|C| + 1} = \\frac{(\\sum_{c \\in C} u(c)) + u(a)}{|C| + 1}  = \\frac{|C|}{|C| + 1} \\cdot u(C) + \\frac{1}{|C| + 1}u(a).$ When we subtract $u(a)$ from this quantity, we get equality to $\\frac{|C|}{|C| + 1} \\cdot u(C) - \\frac{|C|}{|C| + 1}u(a).$ We will certainly add more justification to this step in a camera-ready revision."}, {"review_id": "EiuV0qcLQj", "reviewer": "Reviewer_qq2e", "summary": "This paper presents several results related to strategy proof voting rules when the set of agents has correlated beliefs. The classic results in social choice theory assume that a manipulating agent has access to the entire set of preferences of all agents, while in the setting discussed in the paper we assume that agents have correlated beliefs and we want to find voting rules that are incentive compatible under a Bayesian model (typically called OBIC rules). The paper provides a positive result in that plurality is OBIC for a number of popular models (Mallows, PL) and show negative results for other positional scoring rules (PSRs) under Mallows and a few results on Copeland and Maximin.", "questions": "? What about Urn models? It seems like the conditions for Lemma 1/2 would hold for Urn type models but I'm not sure.\n\n------- \nAfter Rebuttal:\n\nThanks for the rebuttal and answering my questions -- I overall liked this paper and glad we could identify a place to strengthen the work.", "limitations": "Limitation discussion is not really there but at the end of the day the paper is well scoped so doesn't need to be added (though see weakness above).", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The result that plurality is SP under a large space of correlated beliefs is interesting and a nicely proven result.\n\n+ The writing is good and well presented, the paper sets itself well in the literature.", "weaknesses": "- My biggest comment here is fit for NeurIPS. This is a pretty straight social choice paper. While there are 2 references to ICML papers the bulk of the paper is a pretty straight statistical analysis/bounds paper (AI Stats?). This isn't all bad but it would be nice to include at least a bit more discussion on the relevance to the venue.\n\n- The results are largely negative when we have n > 3 or n=3 in that most rules are no OBIC -- while I like the result for plurality this ties with my last point: what's the take away here for the ML community?\n\n\n### Minor Issues:\n\n* Maybe add the plurality result to Table 2 so it is complete for the entire set of results in the paper.\n\n* \"strategy-proof for a large class of beliefs containing the specific ones we introduce\" --> this isn't clear in the abstract, please revise.\n\n* Note that all the rules we consider are Pareto efficient. --> minor quibble but at line 81 where this is introduced and it is never defined or returned to.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer Comment:**\n\n> My biggest comment here is fit for NeurIPS. This is a pretty straight social choice paper. While there are 2 references to ICML papers the bulk of the paper is a pretty straight statistical analysis/bounds paper (AI Stats?). This isn't all bad but it would be nice to include at least a bit more discussion on the relevance to the venue. \n\n**Response:**\n\nComputational social choice in general has long been of interest to AI/ML researchers. In NeurIPS alone there have been many examples of this over the last decade. \n\nWith respect to voting under stochastic ranking models, the topic we study, NeurIPS papers include:\n* \"Random utility theory for social choice\" (Azari Soufiani et al. 2012)\n* \"Generalized method-of-moments for rank aggregation\" (Azari Soufiani et al. 2013)\n* \"Diverse randomized agents vote to win\" (Jiang et al., 2015)\n* \"Is approval voting optimal given approval votes?\"\" (Procaccia and Shah, 2015)\n* \"Axioms for learning from pairwise comparisons\" (Noothigattu et al., 2020)\n\nIn terms of computational social choice more broadly, NeurIPS papers include:\n* Citizen's assemblies: \"Neutralizing self-selection bias in sampling for sortition\" (Flanigan et al., 2020), \"Fair sortition made transparent\" (Flanigan et al., 2021)\n* Participatory budgeting: \"Proportional participatory budgeting with additive utilities\" (Peters et al., 2021)\n* Models of representative democracy: \"A mathematical model for optimal decisions in a representative democracy\" (Magdon-Ismail and Xia, 2018)\n* Distortion of voting rules: \"Efficient and thrifty voting by any means necessary\" (Mandal et al., 2019)\n* Smoothed analysis: \"The smoothed possibility of social choice\" (Xia, 2020)\n\nWith this in mind, the topic is quite relevant to at least a sizable subset of the NeurIPS community. We would also certainly include more of the aforementioned citations in a camera-ready revision.\n\n**Reviewer Comment:**\n\n> What about Urn models? It seems like the conditions for Lemma 1/2 would hold for Urn type models but I'm not sure.\n\n**Response:**\n\nWe are not currently aware of urn models that generate rankings. However, we certainly believe that a large class of models that lead to some level of correlation (as preferrential-attachment models tend to in other settings) would satisfy Lemma 1. "}, {"review_id": "cg2PvUKitA", "reviewer": "Reviewer_kNTn", "summary": "This paper explores a probabilistic form of strategy-proofness for voting rules referred to as Ordinally Bayesian Incentive Compatible (OBIC) in a setting where voters believe that other voters have correlated votes. The paper considers both the situation when voters believe others have preferences similar to their own, and when they believe other voters have correlated preferences that are not necessarily similar to their own. The primary positive result of the paper explores three correlated preference/belief models and shows that they are \"top-choice correlated\"; ie. under them, when all else is equal a \"voter's top choice is likely to perform better than other candidates.\" It is then shown that under any top-choice correlated beliefs the plurality rule is OBIC. Subsequent negative results identify a number of specific situations where other scoring rules are not OBIC.", "questions": "I found the initial motivating example quite reasonable but it loosely acknowledges that any real election does not have an infinite number of voters. Theorem 2 goes on to rely on \"sufficiently large n\" which seems weakened given the motivation. Is that a reasonable criticism and does that weaken the impact of the result? (Admittedly, the theorem is already rather removed from having impacts on real-world elections)", "limitations": "The authors are clear about the limitations of the work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is generally well written. Theorems are clearly stated and there is a strong combination of high level explanation alongside technical definitions. Reasonable motivation is given for studying the questions focused on in the paper, and it is already a well-established area of research.\n\n\nWhile there is a great deal of research on problems of this nature under independent beliefs, thus far the body of work examining results under correlated beliefs is comparatively small and much more recent. This paper adds novel results to the domain. The significance of any single result in a paper such as this is typically not massive but addressing questions larger than those studied here is quite difficult to fit into a single paper. In that sense, the results are of very reasonable significance.", "weaknesses": "Generally the paper does a good job of explaining high level meanings behind the more heavy annotation however the proof sketches are a fair bit more involved than I would expect. As is common these days, full proofs are not given in the paper itself but relegated to the appendices.\n\nAs noted above, the results are not hugely significant but I do not believe it is realistic to publish papers in this domain only if they are groundbreaking. The amount of work required for incremental progress is significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer Comment:**\n\n> Theorem 2 goes on to rely on \"sufficiently large n\" which seems weakened given the motivation. Is that a reasonable criticism and does that weaken the impact of the result? \n\n**Response:**\n\nThis requirement is theoretically necessary, because it is possible to define positional scoring rules that are arbitrarily close to Plurality (say giving some $\\varepsilon \\ll 1$ points to the second place candidate). However, we don't believe this greatly hinders the impact of the result, when viewed in conjunction with our other results. Indeed, Theorem 3 shows that Borda fails for any $n \\ge 2$, and explicit computation shows that many other \"reasonable\" rules also fail for small $n$."}, {"review_id": "sTTbEkW2F3", "reviewer": "Reviewer_A4JJ", "summary": "Post rebuttal: I improved my scores and encourage the authors to include the information from the rebuttal in the final text.\n\nThe authors study strategy-proofness in voting under the assumption that the voters do not have, as is usual, full knowledge about the votes/preferences of the other voters, but rather have some form of beliefs about them. Specifically, they consider that the election they participate in was generated using the Mallows model and either their vote is the central one (confident setting) or not. They also consider several other similar distributions. Their main result is that in the setting, Plurality is strategy-proof.\n\nOn the mathematical level the paper is OK, but I have serious doubts about the significance of the result. In short, the assumed belief models mean that from the perspective of the considered agent, she is winning. Indeed, if the central ballot agrees with the current vote, the the top choice candidate is expected to have the highest plurality score. Then, strategy-proofness for Plurality is essentially built-in into the definition.  The situation where strategy proofness and strategic behavior is interesting is where there is expected contention. The current model does not capture this.\n\nAnother issue is that, as far as I can tell, the message from the paper would be to use the Plurality rule. But this certainly is not a rule we would like to use.\n\nAll in all, the paper certainly makes a step in an interesting direction and, perhaps, this direction would eventually lead to interesting results. However, in the current shape, it is quite far from giving any definite answers (and, as such, can certainly find home in more focused and specialized conferences).", "questions": "Would you consider your results as arguments for using the Plurality rule in practice?", "limitations": "Limitations were addressed", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "makes some progress in a widely studied topic", "weaknesses": "- the results are not relevant practically\n- the strategyproofness for Plurality is, in essence, built into the considered model", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Reviewer comment:**\n\n>  In short, the assumed belief models mean that from the perspective of the considered agent, she is winning. Indeed, if the central ballot agrees with the current vote, the the top choice candidate is expected to have the highest plurality score. Then, strategy-proofness for Plurality is essentially built-in into the definition. The situation where strategy proofness and strategic behavior is interesting is where there is expected contention. The current model does not capture this.\n\n**Response:**\n\nThis seems to be the reviewer's main concern. We are confident that it stems from a misunderstanding, and believe the rebuttal should fully address it. \n\nFirst, the reviewer appears to be referring to the \"confident\" versions of our model, whereas our results also apply to the \"unconfident\" versions. \n\nSecond, and much more importantly, the statement \"the top choice candidate is expected to have the highest plurality score\" is also true when \"plurality\" is replaced with, say, \"Borda\" — but our results show that Borda is not OBIC in our setting! The question is not whether the manipulator's top choice has the highest chance of winning (not to mention the highest expected score), but whether reporting a different ranking leads to this candidate winning *even more often*. It is not the case that one implies the other. Indeed, almost all rules satisfy the first, but, of the ones we study, only plurality avoids the second. In summary, the reviewer's justification for the assertion that \"strategy-proofness for Plurality is essentially built-in into the definition\" is incorrect. \n\n**Reviewer comment:**\n\n> Another issue is that, as far as I can tell, the message from the paper would be to use the Plurality rule. But this certainly is not a rule we would like to use. [...] Would you consider your results as arguments for using the Plurality rule in practice?\n\n**Response:**\n\nWe disagree with the statement that plurality \"is not a rule we would like to use\": with few exceptions, it's the voting rule that's always used in practice. \n\nNow, based on anecdotal evidence, many social choice theorists do seem to prefer other voting rules to plurality. But this preference is based on a variety of criteria for comparing voting rules: axiomatic desiderata, maximum likelihood estimation under various noise models, distortion, distance rationalizability, etc. Simplicity of preference elicitation is another important criterion, in which plurality excels. \n\nStrategyproofness typically isn't a primary criterion in the comparison of voting rules, due to Gibbard-Satterthwaite. Our approach and results can be seen as potentially elevating this criterion so that it can augment the set of criteria that are being examined. Whether this would tilt the scales in favor of plurality is subjective, but we believe it's a criterion that should certainly play a role in the discussion. \n\nTo explicitly answer your question: yes, we view our results as arguments for using plurality in practice, which should be considered alongside other theoretical and empirical arguments."}]

Author rebuttal:

Meta-review: This paper considers a voting problem, with correlated preferences. Each reviewer has a positive view of the paper. I therefore recommend acceptance.
Decision: Accept (poster)