[EM] SODA criteria
Jameson Quinn
jameson.quinn at gmail.com
Thu Feb 2 08:16:22 PST 2012
Example where SODA fails participation. To avoid the issue of ties, just
assume that the alphabetically first candidate wins all ties. (Otherwise,
you have to add votes in groups of two to make things clear).
25: A(>B>C)
5: B
5: C
25: D(>C>B)
40: E
As things are, A gets to delegate first, and approves only B. Now B is the
only candidate who can beat E, so D approves B as well, and B wins. But if
one approval-style vote is added for B and D, then D delegates first, and
approves only C. C wins by the same token. So a vote for B has made B lose.
I can prove this is impossible with 4 or fewer candidates. In particular,
the balance between the (AB) team and the (CD) team mean that such a
scenario can never work without a plausible-threat candidate E.
A similar scenario works for IIA, with the new candidate stealing votes
from A and sharing A's delegation order.
I find these scenarios very highly implausible; for 1 election every 4
years, it's literally "not in a million years".
Jameson
2012/2/1 Jameson Quinn <jameson.quinn at gmail.com>
>
>
> 2012/2/1 Kevin Venzke <stepjak at yahoo.fr>
>
>> Hi Jameson,
>>
>> *De :* Jameson Quinn <jameson.quinn at gmail.com>
>> *À :* Kevin Venzke <stepjak at yahoo.fr>
>> *Cc :* em <election-methods at electorama.com>
>> *Envoyé le :* Mercredi 1 février 2012 11h12
>> *Objet :* Re: [EM] SODA criteria
>>
>> 2012/2/1 Kevin Venzke <stepjak at yahoo.fr>
>>
>> Hi Jameson,
>>
>> I expect that unpredictability (whatever there may be) of candidates'
>> decisions can only hurt criteria compliance.
>> At least with criteria that are generally defined on votes, because with
>> such criteria you usually have to assume
>> the worst about any other influences incorporated into the method.
>>
>>
>> This is true. For most of the criteria, I was implicitly talking about a
>> version of SODA where all candidates use optimum strategy according to
>> their predeclared preferences. This is well-defined and unique, but is not
>> necessarily polytime-calculable. Still, even without being able to
>> calculate results, you can prove criteria compliances for this version by
>> contradiction.
>>
>> For a polytime-calculable version which satisfies most of the same
>> criteria, assume that each candidate, when it is their turn to assign
>> delegated votes, looks at the two "distinct frontrunners"; that is:
>> Candidate X, their most-preferred member of the current Smith set
>> and candidate Y, the candidate, of those whom they prefer differently
>> from X, who does best pairwise (again, using current assignments and
>> unassigned preferences) against X
>> They approve as many candidates as possible without approving both X and
>> Y.
>>
>> This version does not satisfy participation (though again, it's damn
>> close) or IIA, and I'm not 100% sure about its cloneproofness (though I
>> think it is). Otherwise, it satisfies the criteria I said.
>>
>>
>> So I wonder, can you suggest a deterministic version of SODA, where the
>> "negotiations" of SODA are instead
>> calculated directly from the pre-announced preferences of the candidates?
>> And if so, does it satisfy the same
>> criteria in your view?
>>
>> I can say I would be skeptical of how a criterion is being applied, or
>> how clearly it is being defined, if the
>> satisfaction of it *depends* on the fact that candidates have
>> post-voting decisions to make.
>>
>>
>> Are you still suspicious of participation and [delegated] IIA, given that
>> satisfying them depends on assuming optimal strategy?
>>
>>
>>
>> Hmm, I think so, just because "optimal strategy" is hard to define in
>> general. Do you think that it will be possible to produce
>> convincing proofs when somebody asks for one? Pretty daunting task I
>> would think.
>>
>
> The proofs for the condorcet-related properties using optimal strategy are
> pretty simple and obvious.
>
> The participation criterion only applies for delegated voters. The proof
> for that is a bit harder, but not too tough. For approval ballots, it is
> possible to fail the (voted) participation criterion only if the delegation
> order changes, and there are at least 5 candidates (in a delicate balance,
> and for voters whose ballots cannot make sense in a one-dimensional
> ideology space).
>
> I just discovered a hole in my proof for delegated IIA. It works if all
> votes for the new candidate are and were approval-style. It can fail if
> there are at least 4/5 candidates in a tricky balance and the 5th/extra
> candidate pulls delegated votes in a way that changes the delegation order.
> In that case, there is always still a rational strategy for those voters
> which would still preserve IIA. (This proof is tricky.)
>
>>
>> I find myself trying to suggest that it may never be necessary to
>> delegate any power to the candidates. That would make it
>> easier to analyze. But in that case the method is basically Approval and
>> doesn't even satisfy Majority Favorite. Right?
>>
>
> No. In my previous message, I suggested two versions which leave no
> freedom for the candidates, automatically assigning delegated ballots. The
> first – optimal strategy – is not polytime computable that I know of (I
> strongly suspect it's NP-complete in theory, though in practical cases it
> will be easy to compute). The second – vote-one-frontrunner – is easy to
> compute, but it causes violations of IIA and participation.
>
>
>> In
>> your criteria list you had "Majority" but for that you must actually be
>> assuming the opposite of what I am trying, namely that
>> *everyone* is delegating, is that right?
>>
>
> Everyone who votes for the majority candidate is either delegating to
> them, or voting them above all other alternatives - that is, approving only
> them but checking "do not delegate". This is the standard meaning of the
> majority criterion. For instance, by this meaning, approval meets the
> majority criterion.
>
> For MMC, everyone in the mutual majority is either delegating to one of
> the candidates, or approving all of them and nobody else.
>
>
>
>> Kevin
>>
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list
>> info
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20120202/0f01f33e/attachment-0004.htm>
More information about the Election-Methods
mailing list