[EM] Low SU CWs?
Bart Ingles
bartman at netgate.net
Sat Jan 24 01:18:02 PST 2004
I haven't found any method better than plain old FPP for eliminating
extremely low CW candidates. The minimum SU in a FPP election is
basically 1/n, where n is the number of candidates. Pairwise methods
have a minimum of zero. Approval and IRV are in the middle, with
Approval slightly better than IRV when nobody has information about how
the others are voting.
Another worst-case SU-related standard is to look at the SU "deficit"
when compared to the highest-SU candidate. For example, a FPP election
can have an SU deficit of up to 2/n, since it's possible for a candidate
with nearly perfect SU to lose to a 1/n candidate:
Sincere preferences & utilities:
----------------------------
34% A(1.0) > B(0.99) > C(0.0)
33% B(1.0) > C(0.99) > A(0.0)
33% C(1.0) > B(0.99) > A(0.0)
Social Utility totals:
-----------------------------
A: .34 B:.99 C:.99
Best zero-info strategy:
-----------------------------
34% A
33% B
33% C
A wins with an SU deficit of (.99 - .34) = .65
For IRV where n=3, the worst-case SU deficit is essentially 0.75. For
FPP and IRV, this number approaches 1.0 as the number of candidates
increases (1.0 meaning the worst possible candidate in terms of SU can
defeat the best possible).
For pairwise methods, the worst-case SU deficit seems to be 0.5
regardless of the number of candidates (at least I haven't been able to
find an example with a higher number). In other words, even though a
near-zero utility candidate can win, this can only happen if there are
no 0.5-utility candidates in the race.
For approval with voters using "better-than-average approval" strategy,
the worst-case SU deficit seems to be also 0.5 for three candidates.
When I attempted to find the worst case for n > 3, the number seemed to
hover slightly above this, but never rose much above 0.6.
I'll leave proof as an exercise for the reader. I had meant to write a
simple brute-force program to confirm the approval case, but never got
around to it.
Bart
More information about the Election-Methods
mailing list