[EM] strategy-free Condorcet method after all!
Warren Smith
warren.wds at gmail.com
Sat Nov 14 11:32:23 PST 2009
(Same post as before, but with annoying typos corrected.)
> Jobst Heitzig (with slight editing by me):
>Method: Reverse Llull
>=====================
>1. Sort the options into some arbitrary ordering X1,...,Xn (e.g.
>alphabetically or randomly), publish this ordering, and put i=n.
WDS: will different orderings yield different results? ("Agenda
manipulation"?)
>2. If already i=1, then X1 is the winner. Otherwise, ask all voters
>whether they prefer Xi or the option they expect to be the winner of
>applying this method to the remaining options X1,...,X(i-1).
WDS: a slight altering in wording would be "or the expected utility of
the winner when applying this method to the remaining options X1,...,X(i-1)."
This change makes no difference under the perfect info assumption that the
voter can predict the winer 100% accurately, but does make a difference if
imperfect info.
>3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by
>1 and repeat steps 2 and 3.
>Why should this be strategy-free?
>If n=2, the question in step 2 is whether X1 or X2 is preferred and the
>method is traditional majority choice in which sincere voting is known
>to be the dominant strategy in case of 2 options.
>For n>2, we prove strategy-freeness inductively, assuming it has been
>proved for n-1 options already: Since we assume that each voter follows
>dominant strategies and knows enough about the other voter's
>preferences, and since each voters knows that sincere voting is the
>unique dominant strategy for all cases of at most n-1 options, she will
>know in step 2 which option Xj would win if the method was applied to
>X1,...,X(i-1), and she will also know that her vote at this step does
>not influence which option Xj is but only whether Xi or Xj will win.
>That is, in step 2 all voters face a simple majority choice between two
>known options Xi and Xj, so again voting sincerely in this step is the
>unique dominant strategy. By induction, the whole method is strategy-free.
>The method is in some sense the reverse of Llull's famous earliest known
>"Condorcet' method from the 13th century ...
-------
Fascinating. Now I suppose one could argue in the same manner
that the voter can provide all (n-1) of her votes ahead of time, as n-1
binary "bits." Which would actually be n bits if an extra (unused)
vote-bit also
were provided for X1. Note this then is an approval-voting-style ballot.
Now suppose the candidate ordering happens to be
the ordering in decreasing likelihood of victory.
The "moving mean" strategy for approval voting (actually applicable to
a wide class of kinds of voting, which I defined many years ago...)
is precisely the following.
1. order the candidates in decreasing likelihood of victory.
2. approve exactly one of the first two candidates (whichever you prefer).
3. go thru the remaining candidates in order, approving/disapproving
each, if you prefer/not him versus the average utility among
the preceding candidates.
One really should use weighted average weighted by conditional
probability of victory -- though I had in mind unweighted average at
that time, based on the theory that under certain circumstances they
were going to be effectively the same thing. When deciding on the
approval of X[k+1] the probabilities for X1,X2,...,Xk need to be
conditioned on the assumption that X[k+1] is going to have a decent
chance to win, i.e. is near-tied with the leader among X1,X2,...Xk,
while X[k+2],...,Xn are regarded as having negligible winning chances.
If this ordering happens to coincide with the one used by Jobst Heitzig,
then the moving-mean-strategy approval ballot, will coincide with
honest=strategic reverse-Llull voting.
Now the following alternative vote-tallying algorithm will elect Jobst
Heitzig's same winner:
1. go thru the candidates in reverse order (n, n-1, n-2,..., 2, 1)
2. As soon as you find a candidate with more than 50% approval, elect him.
3. If no such candidate exists, elect X1 (but in fact, with Heitzian
"honest" voting, i.e. Smithian moving-mean-strategic voting, one will
always exist, so X1's election would have been automatic without need
for rule 3).
This way of rewording the algorithm seems to make it pretty clear that
the winner CAN depend on the ordering. (Answering my own question
above.) Therefore, this method (if deterministic) disobeys
"neutrality."
A method which, however, is similar and happens to obey "neutrality"
is plain old
APPROVAL VOTING.
Observe that if a Condorcet winner exists, then it automatically is
unique and automatically is elected, both by Reverse Llull, and (with
the same votes) by ordinary approval voting.
They only can differ in circumstances where no Condorcet winner exists.
--
Warren D. Smith
http://RangeVoting.org <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html
More information about the Election-Methods
mailing list