[EM] SODA criteria

Jameson Quinn jameson.quinn at gmail.com
Wed Feb 1 16:35:32 PST 2012

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/20120201/bc01c1c0/attachment-0004.htm>

More information about the Election-Methods mailing list