A proxy for Monroe's "strategic election of universally loathed candidates" criterion
So I'm gonna try this list thing again. We'll see how the plonking goes.
But I'm kind of tired of debate, (particularly the sort that ends in
back-and-forth insults,) so let's try something a bit closer to research.
Before I left, there was a mention of Monroe's Nonelection of Irrelevant
Alternatives as a measure of burial resistance, so I tried to play with
it a bit. But I found it very hard because you have to come up with
separate Myerson-Weber strategies depending on the method and their
state spaces. (So hard that Monroe might actually have got some of the
failure results in his draft paper wrong!) So I thought I'd try to find
a more... mechanically applicable criterion that would imply NIA - i.e.
if a method passes this, it passes NIA.
And I think I've found two. One that's still pretty complex but that can
be checked purely mechanically (at least for ranked methods), and
another that's much easier but limited to majoritarian unrestricted
domain methods. Both criteria only properly cover/imply NIA if the
method also passes a (pretty straightforward) mono-add-plump-related
criterion.
(One might seriously question the relevance or realism of the knife's
edge election that follows, but such a knife's edge is what Monroe based
his reasoning on, so...)
Both criteria start with a three-candidate honest election of the form:
N: A>B>C
N: B>A>C
1: C>A>B
1: C>B>A
with N being a very large number (or equivalently, replace the C-faction
weights with some infinitesimal epsilon). The idea is that most methods
will give this as an A=B tie. Then there might exist some risky
strategic ballot that the A faction can cast, and some risky strategic
ballot that the B faction can cast, so that if one of them does so, then
their candidate wins, but if both do it, then C wins.
The A and B factions are balanced so that there's initially a tie. And
the incredibly weak C faction exists to stop a method from passing the
criteria by refusing to elect candidates who have no first preferences.
The C-faction also helps restore results that Monroe might have got
wrong, thus being closer to the spirit of his criterion.
So let's go to the criteria.
The complex criterion is the "strong non-collapse tie criterion" or
SNCTC for short. I'm going to limit myself to deterministic methods
because handling nondeterministic ones seems to come with a ton of
corner cases.
I'll also call the A-faction just "A" and similarly for the other factions.
Here's the SNCTC definition:
===
If C is elected (wins or ties) in the honest election, then the method
fails.
Otherwise, define an effective ballot s for A as one that:
1. when A casts s instead of his honest ballot, A becomes the only
winner, and
2. no matter what ballot t B casts, if A casts s and B casts t, B does
not become the unique winner.
If A has no such effective ballots, then let every ballot that satisfies
the first point above be an effective ballot for A. (If A still has no
effective ballots, that's okay.)
B's effective ballots are defined similarly. Note that the honest ballot
may be effective if the faction's favorite wins outright.
If only one side has any effective ballots, then we pass (because the
side without effective ballots can't unilaterally make their candidate
win, so the collapse can't occur).
If there exists an effective ballot s for A so that no matter what
effective ballot t that B chooses, if A casts s and B casats t, then C
doesn't win; and the same is true (with the faction labels flipped) of
the B faction; then we pass.
Otherwise, we fail.
For methods that are more expressive than ranked ones, the above must
hold for every election whose rank data correspond to the honest ranked
election. E.g. for a rated method, every rated ballot where the A
faction rates A higher than B and B higher than C, the B faction rates B
higher than A and A higher than C, etc., must pass. The criterion is
inapplicable to methods that are less expressive (like Approval).
===
The point is that an effective ballot by A is a strategy (either safe or
risky) that can't be exploited by B: i.e. A casting it improves A's
winning chances without B being able to exploit this by casting some
other ballot that makes B the winner.
By reasoning this way, when A and B strategize, they'll limit themselves
to effective ballots.
Then we pass if A and B can't step on each other's toes no matter what
effective ballots they use. No matter what they do, C is not going to win.
This is still pretty cumbersome, but for ranked methods with truncation
and/or equal-rank, we can at least test every possible ballot to
determine which ballots are effective. Rated methods require more
general reasoning and can't be done mechanically.
So, let's say we want to simplify it even more. Here's a criterion for
majoritarian unrestricted domain methods (i.e. no equal-rank or truncation):
DH2:
Let election e1 be:
N: A>B>C
N: B>A>C
1: C>A>B
1: C>B>A
Let election e2 be:
N: A>C>B
N: B>A>C
1: C>A>B
1: C>B>A
Let election e3 be:
N: A>B>C
N: B>C>A
1: C>A>B
1: C>B>A
And let election e4 be:
N: A>C>B
N: B>C>A
1: C>A>B
1: C>B>A
- If C wins or ties for first in e1, the method fails.
- If A doesn't uniquely win in e2, the method passes.
- If B doesn't uniquely win in e3, the method passes.
- If C doesn't win or tie for first in e4, the method passes.
Otherwise, the method fails.
The criterion is named after Warren Smith's DH3 ("dark horse plus
three") because, in a sense, this is "dark horse plus two".
The explanation is:
For 1.: if C wins in the first election, then C wins even without
strategy, which is a failure. (I don't expect that to happen, but why
not cover our bases?)
For 2. and 3.: if unilateral burial doesn't break the tie in favor of
the buriers, then the buriers have no reason to do it. (Particularly not
if it makes C win too.) And if only one side (at most) has a reason to
bury, then the combined effect of two sides burying can never happen,
because only one side (at most) has any incentive to bury.
And for 4.: if they both have incentive to bury, then the two burying
at once must not make C win.
Why is this equivalent to SNCTC? Consider the effective ballots for A.
By the majority criterion, ranking anybody but A first will make that
candidate win. So the effective ballots must either be A>B>C or A>C>B.
If it's A>B>C, then B can't unilaterally break the tie, hence B has no
reason to strategize, and we pass. If it's A>C>B, then we get e2, e3,
and e4.
===
I've skipped my reasoning about how SNCTC plus a mono-add-plumpish
criterion implies NIA, what criterion is required for the implication,
and what methods pass SNCTC or DH2, because this post is long enough.
Just ask if you'd like more info.
But I can say that if method M passes DH2, then all of Condorcet,M and
Resistant,M and Condorcet//M and Condorcet,M pass. Resistant//M pass for
all M. Resistant,M may fail for some M (e.g. Borda) but there's a tweak
that makes them pass for all M.
Range with any sufficiently large discrete scale passes SNCTC, as does
discrete lp-cumulative vote with any p-norm >= 1. (The continuous
versions fail on a technicality.)
Smith passes DH2, but (surprisingly) Schwartz fails!
Ranked methods with no burial incentive immediately pass DH2 because the
only possible strategic effective vote (as established) is A>C>B, but
this buries B, and if there's no burial incentive, that has no effect.
DH2 requires unrestricted domain. In one direction, consider a method
that's like Plurality, but each faction may also indicate "I'm serious".
If one faction does so, that faction's candidate wins, but if both do,
then C wins. This fails SNCTC but its UD version, Plurality, passes DH2.
In the other direction, if I got it right, Bucklin fails DH2 but passes
SNCTC because truncation is just as good as burial and doesn't come with
its risks.
-km
Whatta breath of fresh air in a room full of flatulence.
--
r b-j . _ . _ . _ . _ rbj@audioimagination.com
"Imagination is more important than knowledge."
.
.
.
Thank you so much for all of your hard work+analysis Kris :)
Smith passes DH2, but (surprisingly) Schwartz fails!
Could you clarify what you mean by Smith/Schwartz passing/failing?
————
That said, I'd like to offer some clarification. My concern isn't actually
with DH2 or DH3 scenarios. My point in our earlier discussion was I reject
two common frameworks for strategic analysis.
First, I reject the group strategy framework. In elections, hidden
communication is infeasible because of how many people you'd need to get in
on the conspiracy, and the secret ballot makes collusion impossible to
enforce. If group strategy was a reasonable model of voters, it wouldn't
matter which electoral system we picked, because the outcome would always
be a maximal lottery. What I find more meaningful is individual
incentive-compatibility.
Second, I reject the idea of looking at individual scenarios like DH3 or
Burr, then judging if a voting system fails or succeeds in such a scenario.
(Or rather, using this to rule electoral systems in, not out). This feels
like declaring a theorem proven after trying a few numbers and not finding
a counterexample.
(The Burr dilemma should be the poster boy for this kind of bad strategic
analysis: it focuses on a single scenario, and on group strategy, and it
completely ignores the possibility of correlated equilibria and mixed
strategies...)
What I generally believe in is starting with a reasonable model
characterizing voting behavior, then identifying how the method performs
across all elections in this model. The two models I've gotten a lot of
mileage out of reading and studying are:
- Myerson-Weber-style decisive vote models, where voters only care about
deciding an uncertain election. - Balinski and Laraki's grading model, where voters look to optimize the
score of candidates they support (because votes send signals about
popularity of different policies).
I do wonder if it's possible to get a system where the optimal strategy in
most elections is min-maxing, whereas with zero information the best
strategy is strict ranking (a real advantage of most ordinal methods). I
know there are incentive-compatible cardinal mechanisms in the
zero-information case (http://dx.doi.org/10.1016/j.geb.2017.04.012
https://www.researchgate.net/publication/316805816_Ordinal_Versus_Cardinal_Voting_Rules_A_Mechanism_Design_Approach).
Later-no-help+no favorite betrayal would be enough to guarantee min-maxing
with perfect information.
On Sat, Jul 20, 2024 at 11:18 AM Kristofer Munsterhjelm <
km-elmet@munsterhjelm.no> wrote:
So I'm gonna try this list thing again. We'll see how the plonking goes.
But I'm kind of tired of debate, (particularly the sort that ends in
back-and-forth insults,) so let's try something a bit closer to research.
Before I left, there was a mention of Monroe's Nonelection of Irrelevant
Alternatives as a measure of burial resistance, so I tried to play with
it a bit. But I found it very hard because you have to come up with
separate Myerson-Weber strategies depending on the method and their
state spaces. (So hard that Monroe might actually have got some of the
failure results in his draft paper wrong!) So I thought I'd try to find
a more... mechanically applicable criterion that would imply NIA - i.e.
if a method passes this, it passes NIA.
And I think I've found two. One that's still pretty complex but that can
be checked purely mechanically (at least for ranked methods), and
another that's much easier but limited to majoritarian unrestricted
domain methods. Both criteria only properly cover/imply NIA if the
method also passes a (pretty straightforward) mono-add-plump-related
criterion.
(One might seriously question the relevance or realism of the knife's
edge election that follows, but such a knife's edge is what Monroe based
his reasoning on, so...)
Both criteria start with a three-candidate honest election of the form:
N: A>B>C
N: B>A>C
1: C>A>B
1: C>B>A
with N being a very large number (or equivalently, replace the C-faction
weights with some infinitesimal epsilon). The idea is that most methods
will give this as an A=B tie. Then there might exist some risky
strategic ballot that the A faction can cast, and some risky strategic
ballot that the B faction can cast, so that if one of them does so, then
their candidate wins, but if both do it, then C wins.
The A and B factions are balanced so that there's initially a tie. And
the incredibly weak C faction exists to stop a method from passing the
criteria by refusing to elect candidates who have no first preferences.
The C-faction also helps restore results that Monroe might have got
wrong, thus being closer to the spirit of his criterion.
So let's go to the criteria.
The complex criterion is the "strong non-collapse tie criterion" or
SNCTC for short. I'm going to limit myself to deterministic methods
because handling nondeterministic ones seems to come with a ton of
corner cases.
I'll also call the A-faction just "A" and similarly for the other factions.
Here's the SNCTC definition:
===
If C is elected (wins or ties) in the honest election, then the method
fails.
Otherwise, define an effective ballot s for A as one that:
1. when A casts s instead of his honest ballot, A becomes the only
winner, and
2. no matter what ballot t B casts, if A casts s and B casts t, B
does
not become the unique winner.
If A has no such effective ballots, then let every ballot that satisfies
the first point above be an effective ballot for A. (If A still has no
effective ballots, that's okay.)
B's effective ballots are defined similarly. Note that the honest ballot
may be effective if the faction's favorite wins outright.
If only one side has any effective ballots, then we pass (because the
side without effective ballots can't unilaterally make their candidate
win, so the collapse can't occur).
If there exists an effective ballot s for A so that no matter what
effective ballot t that B chooses, if A casts s and B casats t, then C
doesn't win; and the same is true (with the faction labels flipped) of
the B faction; then we pass.
Otherwise, we fail.
For methods that are more expressive than ranked ones, the above must
hold for every election whose rank data correspond to the honest ranked
election. E.g. for a rated method, every rated ballot where the A
faction rates A higher than B and B higher than C, the B faction rates B
higher than A and A higher than C, etc., must pass. The criterion is
inapplicable to methods that are less expressive (like Approval).
===
The point is that an effective ballot by A is a strategy (either safe or
risky) that can't be exploited by B: i.e. A casting it improves A's
winning chances without B being able to exploit this by casting some
other ballot that makes B the winner.
By reasoning this way, when A and B strategize, they'll limit themselves
to effective ballots.
Then we pass if A and B can't step on each other's toes no matter what
effective ballots they use. No matter what they do, C is not going to win.
This is still pretty cumbersome, but for ranked methods with truncation
and/or equal-rank, we can at least test every possible ballot to
determine which ballots are effective. Rated methods require more
general reasoning and can't be done mechanically.
So, let's say we want to simplify it even more. Here's a criterion for
majoritarian unrestricted domain methods (i.e. no equal-rank or
truncation):
DH2:
Let election e1 be:
N: A>B>C
N: B>A>C
1: C>A>B
1: C>B>A
Let election e2 be:
N: A>C>B
N: B>A>C
1: C>A>B
1: C>B>A
Let election e3 be:
N: A>B>C
N: B>C>A
1: C>A>B
1: C>B>A
And let election e4 be:
N: A>C>B
N: B>C>A
1: C>A>B
1: C>B>A
- If C wins or ties for first in e1, the method fails.
- If A doesn't uniquely win in e2, the method passes.
- If B doesn't uniquely win in e3, the method passes.
- If C doesn't win or tie for first in e4, the method passes.
Otherwise, the method fails.
The criterion is named after Warren Smith's DH3 ("dark horse plus
three") because, in a sense, this is "dark horse plus two".
The explanation is:
For 1.: if C wins in the first election, then C wins even without
strategy, which is a failure. (I don't expect that to happen, but why
not cover our bases?)
For 2. and 3.: if unilateral burial doesn't break the tie in favor
of
the buriers, then the buriers have no reason to do it. (Particularly not
if it makes C win too.) And if only one side (at most) has a reason to
bury, then the combined effect of two sides burying can never happen,
because only one side (at most) has any incentive to bury.
And for 4.: if they both have incentive to bury, then the two
burying
at once must not make C win.
Why is this equivalent to SNCTC? Consider the effective ballots for A.
By the majority criterion, ranking anybody but A first will make that
candidate win. So the effective ballots must either be A>B>C or A>C>B.
If it's A>B>C, then B can't unilaterally break the tie, hence B has no
reason to strategize, and we pass. If it's A>C>B, then we get e2, e3,
and e4.
===
I've skipped my reasoning about how SNCTC plus a mono-add-plumpish
criterion implies NIA, what criterion is required for the implication,
and what methods pass SNCTC or DH2, because this post is long enough.
Just ask if you'd like more info.
But I can say that if method M passes DH2, then all of Condorcet,M and
Resistant,M and Condorcet//M and Condorcet,M pass. Resistant//M pass for
all M. Resistant,M may fail for some M (e.g. Borda) but there's a tweak
that makes them pass for all M.
Range with any sufficiently large discrete scale passes SNCTC, as does
discrete lp-cumulative vote with any p-norm >= 1. (The continuous
versions fail on a technicality.)
Smith passes DH2, but (surprisingly) Schwartz fails!
Ranked methods with no burial incentive immediately pass DH2 because the
only possible strategic effective vote (as established) is A>C>B, but
this buries B, and if there's no burial incentive, that has no effect.
DH2 requires unrestricted domain. In one direction, consider a method
that's like Plurality, but each faction may also indicate "I'm serious".
If one faction does so, that faction's candidate wins, but if both do,
then C wins. This fails SNCTC but its UD version, Plurality, passes DH2.
In the other direction, if I got it right, Bucklin fails DH2 but passes
SNCTC because truncation is just as good as burial and doesn't come with
its risks.
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
On 2024-08-04 19:26, Closed Limelike Curves wrote:
Thank you so much for all of your hard work+analysis Kris :)
Smith passes DH2, but (surprisingly) Schwartz fails!
Could you clarify what you mean by Smith/Schwartz passing/failing?
Sure :-) Suppose we have
N: A>B>C
N: B>A>C
1: C>A>B
1: C>B>A
The Smith and Schwartz sets are {A, B}. Now suppose that A buries:
N: A>C>B
N: B>A>C
1: C>A>B
1: C>B>A
The Smith set is still {A, B}, but the Schwartz set is {A} (unless
there's a bug in my code - and rbvote).
Hence there exist Smith methods that pass DH2.[1] But there don't exist
Schwartz methods that do so, because unilateral burial will lead the
buriers' candidate to win, and bilateral burial makes C the CW.
As I have stated, I wouldn't put too much into this kind of knife edge
election. It's not going to make me throw away RP or Schulze. But if
you're going by the letter of the criterion, then Schwartz does seem to
imply failure.
————
That said, I'd like to offer some clarification. My concern isn't
actually with DH2 or DH3 scenarios.
[...]
Second, I reject the idea of looking at individual scenarios like DH3 or
Burr, then judging if a voting system fails or succeeds in such a
scenario. (Or rather, using this to rule electoral systems in, not out).
This feels like declaring a theorem proven after trying a few numbers
and not finding a counterexample.
(I'll get to the rest at a later point)
I find this surprising. What initially got me to investigate this was
your reply to my post about resistant set performance, where I showed
that even Resistant,Borda had low manipulability. You said something
like, and I'm paraphrasing, "but how do I know that the remaining share
of manipulable elections isn't all turkey-raising of no-hope
candidates?", and then pointed at Monroe's analysis.
If you have no concern about DH2 or DH3, then it would seem that you
have no concern with Monroe's NIA either, because my whole point was
that we could reduce all this complicated thinking about M-W equilibria
in Monroe's scenario with a much simpler mechanically approximable
criterion.
But if you weren't interested in Monroe's NIA to begin with, you should
have made that more clear when you replied to my resistant set post.
(The Burr dilemma should be the poster boy for this kind of bad
strategic analysis: it focuses on a single scenario, /and/ on group
strategy, /and/ it completely ignores the possibility of correlated
equilibria and mixed strategies...)
I may get into why I don't think that's an accurate depiction, either,
later. But before I do that, I would like to know if single scenarios
concern you when it comes to ruling methods out.
Do you consider concrete criteria and/or single scenario analyses
valuable in making sure a method doesn't blow up on its users after
implementation (or as a proxy for the risk that such an event may occur)?
And do you consider statistical analyses like manipulability and VSE
useful to determine the viability of a method? Or are you more
fundamentally saying that we can only rule methods out, but we can't
rule them in by either approach?
-km
[1] Strictly speaking, all that this argument shows is that there may
exist such a method. But since Smith,X preserves X's DH2 resistance, we
can just let X=IRV and so we know that one exists.
So, to be clear, I don't think the DH2/DH3 analyses are useless. They're
very much useful for ruling methods out (rather than in), because this
particular pathology is bad enough to be disqualifying.
I gave these as examples of pathologies that might be hiding in methods
that perform very well on criteria. I'm very sorry if I was unclear about
that—I think most of my comments on this topic went out just after you left
the mailing list, so you might not have seen them.
My broader point is I can't really recommend a voting system to the public
until I have an actual mathematical proof that nothing like DH2 or DH3 is
hiding in it. Not having found a counterexample yet isn't sufficient for a
proof. What if it turns out DH3 isn't a problem, but DH7 is? Or what if,
under realistic models of voter behavior, resistant-set methods never ever
elect the Condorcet winner in any center squeeze? It would take an
infinitely long time to evaluate all possible scenarios, so we just can't
do that.
Instead I want to start by building a useful model of strategic actors in
elections*, *then use it to prove theorems about all situations, given a
decent solution concept. This is the standard approach of mechanism
design: It's not enough to find situations where your method works; you
have to show it will always work.
The approach I've found most satisfying so far has been the Myerson and
Weber one, or some of Laslier's papers. Both show that positioning yourself
at the median voter maximizes your probability of winning an election. I've
also gotten quite a bit out of Balinski and Laraki's analysis of
level/score manipulation, which assumes voters' main concern is to show
support or opposition with regard to candidates. This is a very useful
framework if you think voters use their ballots to send messages to
politicians about the popularity of their positions.
On Mon, Aug 5, 2024 at 4:28 AM Kristofer Munsterhjelm <
km-elmet@munsterhjelm.no> wrote:
On 2024-08-04 19:26, Closed Limelike Curves wrote:
Thank you so much for all of your hard work+analysis Kris :)
Smith passes DH2, but (surprisingly) Schwartz fails!
Could you clarify what you mean by Smith/Schwartz passing/failing?
Sure :-) Suppose we have
N: A>B>C
N: B>A>C
1: C>A>B
1: C>B>A
The Smith and Schwartz sets are {A, B}. Now suppose that A buries:
N: A>C>B
N: B>A>C
1: C>A>B
1: C>B>A
The Smith set is still {A, B}, but the Schwartz set is {A} (unless
there's a bug in my code - and rbvote).
Hence there exist Smith methods that pass DH2.[1] But there don't exist
Schwartz methods that do so, because unilateral burial will lead the
buriers' candidate to win, and bilateral burial makes C the CW.
As I have stated, I wouldn't put too much into this kind of knife edge
election. It's not going to make me throw away RP or Schulze. But if
you're going by the letter of the criterion, then Schwartz does seem to
imply failure.
————
That said, I'd like to offer some clarification. My concern isn't
actually with DH2 or DH3 scenarios.
[...]
Second, I reject the idea of looking at individual scenarios like DH3 or
Burr, then judging if a voting system fails or succeeds in such a
scenario. (Or rather, using this to rule electoral systems in, not out).
This feels like declaring a theorem proven after trying a few numbers
and not finding a counterexample.
(I'll get to the rest at a later point)
I find this surprising. What initially got me to investigate this was
your reply to my post about resistant set performance, where I showed
that even Resistant,Borda had low manipulability. You said something
like, and I'm paraphrasing, "but how do I know that the remaining share
of manipulable elections isn't all turkey-raising of no-hope
candidates?", and then pointed at Monroe's analysis.
If you have no concern about DH2 or DH3, then it would seem that you
have no concern with Monroe's NIA either, because my whole point was
that we could reduce all this complicated thinking about M-W equilibria
in Monroe's scenario with a much simpler mechanically approximable
criterion.
But if you weren't interested in Monroe's NIA to begin with, you should
have made that more clear when you replied to my resistant set post.
(The Burr dilemma should be the poster boy for this kind of bad
strategic analysis: it focuses on a single scenario, /and/ on group
strategy, /and/ it completely ignores the possibility of correlated
equilibria and mixed strategies...)
I may get into why I don't think that's an accurate depiction, either,
later. But before I do that, I would like to know if single scenarios
concern you when it comes to ruling methods out.
Do you consider concrete criteria and/or single scenario analyses
valuable in making sure a method doesn't blow up on its users after
implementation (or as a proxy for the risk that such an event may occur)?
And do you consider statistical analyses like manipulability and VSE
useful to determine the viability of a method? Or are you more
fundamentally saying that we can only rule methods out, but we can't
rule them in by either approach?
-km
[1] Strictly speaking, all that this argument shows is that there may
exist such a method. But since Smith,X preserves X's DH2 resistance, we
can just let X=IRV and so we know that one exists.