[EM] Generalizing "manipulability"

[Jonathan Lundell]

On Jan 18, 2009, at 9:56 AM, Steve Eppley wrote:

> Manipulability by voter strategy can be rigorously defined without  
> problematic concepts like preferences or sincere votes or how a  
> dictator would vote or or how a rational voter would vote given  
> beliefs about others' votes.

I appreciate the formalism, and I think we're on the same page. I  
note, though, that concepts like preferences or sincere votes are  
implicit in the formalism, or at least its consequences, indeed as you  
mention below ("… vi is consistent with the voter's sincere order of  
preference").

Your second definition requires a little work, or at least we qualify  
ballot admissibility to be more restrictive than the voting rule  
itself might be. For the purposes of applying the second definition to  
approval, we need to rule out (for purposes of the definition) ballots  
approval all or none of the alternatives X. Such a ballot satisfies  
(3), but it makes approval trivially manipulable (though it's  
manipulable anyway).

Likewise, for the generalization to apply to ranked methods, we need  
to restrict truncation, perhaps by adding a condition that vi rank  
C(v) and better. But that introduces difficulties for the generalizing  
to approval.



>
>
>    Let X denote the set of alternatives being voted on.
>    Let N denote the set of voters.
>
>    Let V(X,N) denote the set of all possible collections of admissible
>    votes regarding X, such that each collection contains one vote
>    for each voter i in N.  For all collections v in V(X,N) and all
>    voters i in N, let vi denote i's vote in v.
>
>    Let C denote the vote-tallying function that chooses the winner
>    given a collection of votes. That is, for all v in V(X,N), C(v) is
>    some alternative in X.
>
>    Call C "manipulable by voter strategy" if there exist two  
> collections
>    of votes v,v' in V(X,N) and some voter i in N such that both of
>    the following conditions hold:
>         1.  v'j = vj for all voters j in N-i.
>         2.  vi ranks C(v') over C(v).
>
> The idea in condition 2 is that voter i prefers the winner given the  
> strategic vote v'i over the winner given the sincere vote vi.
>
> That definition works assuming all possible orderings of X are  
> admissible votes.  I think it works for Range Voting too (and Range  
> Voting can be shown to be manipulable).  The following may be a  
> reasonable way to generalize it to include methods like Approval  
> (and if this is done then Approval can be shown to be manipulable):
>
>    Call C "manipulable by voter strategy" if there exist two  
> collections
>    of votes v,v' in V(X,N) and some voter i in N and some ordering o  
> of X
>    such that all 3 of the following conditions hold:
>         1.  v'j = vj for all j in N-i.
>         2.  o ranks C(v') over C(v).
>         3.  For all pairs of alternatives x,y in X,
>              if vi ranks x over y then o ranks x over y.
>
> The idea in condition 3 is that vi is consistent with the voter's  
> sincere order of preference.  For example, approving x but not y or  
> z is consistent with the 2 strict (linear) orderings "x over y over  
> z" and "x over z over y."  It's also consistent with the weak (non- 
> linear) ordering "x over y,z."  Approving x and y but not z is  
> consistent with "x over y over z" and "y over x over z" and "x,y  
> over z."  Interpreting o as the voter's sincere order of preference,  
> condition 2 means the voter prefers the strategic winner over the  
> sincere winner.
>
> Another kind of manipulability is much more important in the context  
> of public elections.  Call the voting method "manipulable by  
> irrelevant nominees" if nominating an additional alternative z is  
> likely to cause a significant number of voters to change their  
> relative vote between two other alternatives x and y, thereby  
> changing the winner from x to y.  We observe the effects all the  
> time given traditional voting methods.  It explains why so many  
> potential candidates drop out of contention before the general  
> election (Duverger's Law).  It explains why the elites tend not to  
> propose competing ballot propositions when asking the voters to  
> change from the status quo using Yes/No Approval.  I expect this  
> kind of manipulability to be a big problem given Approval or Range  
> Voting or plain Instant Runoff or Borda, but not given a good  
> Condorcet method.
> The reason manipulability by irrelevant nominees is more important  
> than manipulability by voter strategy is that it takes only a tiny  
> number of people to affect the menu of nominees, whereas voters in  
> public elections tend not to be strategically minded--see the  
> research of Mike Alvarez of Caltech.
>
> Regards,
> Steve
> --------------------------------------------------------------
> On 1/17/2009 10:38 PM, Juho Laatu wrote:
>> --- On Sun, 18/1/09, Jonathan Lundell <jlundell at pobox.com> wrote:
>>
>>
>>> On Jan 17, 2009, at 4:31 PM, Juho Laatu wrote:
>>>
>>>
>>>> The mail contained quite good
>>>> definitions.
>>>>
>>>> I didn't however agree with the
>>>> referenced part below. I think "sincere"
>>>> and "zero-knowledge best strategic"
>>>> ballot need not be the same. For example
>>>> in Range(0,99) my sincere ballot could
>>>> be A=50 B=51 but my best strategic vote
>>>> would be A=0 B=99. Also other methods
>>>> may have similarly small differences
>>>> between "sincere" and "zero-knowledge
>>>> best strategic" ballots.
>>>>
>>> My argument is that the Range values (as well as the
>>> Approval cutoff point) have meaning only within the method.
>>> We know from your example how you rank A vs B, but the
>>> actual values are uninterpreted except within the count.
>>>
>>> The term "sincere" is metaphorical at best, even
>>> with linear ballots. What I'm arguing is that that
>>> metaphor breaks down with non-linear methods, and the
>>> appropriate generalization/abstraction of a sincere ballot
>>> is a zero-knowledge ballot.
>>>
>>
>> I don't quite see why ranking based
>> methods (Range, Approval) would not
>> follow the same principles/definitions
>> as rating based methods. The sincere
>> message of the voter was above that she
>> only slightly prefers B over A but the
>> strategic vote indicated that she finds
>> B to be maximally better than A (or
>> that in order to make B win she better
>> vote this way).
>>
>> Juho
>>
>>
>>
>>
>>>> Juho
>>>>
>>>>
>>>> --- On Sun, 18/1/09, Jonathan Lundell
>>>>
>>> <jlundell at pobox.com> wrote:
>>>
>>>>> The generalization of a "sincere" ballot
>>>>>
>>> then
>>>
>>>>> becomes the zero-knowledge (of other voters'
>>>>>
>>> behavior)
>>>
>>>>> ballot, although we might still want to talk about
>>>>>
>>> a
>>>
>>>>> "sincere ordering" (that is, the sincere
>>>>>
>>> linear
>>>
>>>>> ballot) in trying to determine a "best
>>>>>
>>> possible"
>>>
>>>>> outcome.