Does participation imply monotonicity?
BTernaryTau last edited by
Looking at the criteria tables on Wikipedia, there don't seem to be any voting methods listed that pass participation but fail monotonicity. And given how similar participation failures are to monotonicity failures, it seems plausible that these two criteria are linked in some way. However, when I investigated this further I found what I believe is a counterexample to the claim that participation implies monotonicity.
Consider an election with candidates A, B, C, and D, where the winner is chosen by plurality voting with ranked ballots and alphabetical tie-breaking. Now modify the voting method slightly such that when D>C>B>A is the only ballot cast, B wins, and when D>B>C>A is the only ballot cast, C wins. This creates an instance of non-monotonicity where ranking B higher changes the winner from B to C. However, it does not create any instances of participation failure. In a single-voter election, a voter who honestly casts either of these ballots improves their result (B or C is elected instead of A). In a two-voter election, if one voter casts either of these ballots, the other voter is guaranteed to have their top candidate win (since D never wins when there's a tie). And all other cases consist of elections identical to those under plurality voting.
Assuming I didn't make any mistakes, my next question is whether there are any restrictions that can be placed on the class of voting methods being considered to change this result by eliminating contrived examples like the one above. For example, maybe the combination of unanimity, anonymity, neutrality, and participation implies monotonicity, and as a result pretty much any "reasonable" voting method that passes participation will also pass monotonicity.
Keith Edmonds last edited by
@bternarytau There is an interplay between House and population monotonicity.
Marylander last edited by
@keith-edmonds I do not see what this has to do with the question.
Keith Edmonds last edited by
Failing the participation criterion is an an example of failing Population Monotonicity
Not saying I have a full answer but this may be a fruitful place to look.
@bternarytau I just want to point out that this system is a priori discriminatory toward the candidates. I think for symmetry the rule should be that if there is only one ranking A>B>C>D among the ballots, then C is the winner. This way the labels A,B,C,D are always stand-ins for arbitrary distinct candidates.
In your example it seems that A and D are particular candidates somehow chosen even before the ballots are cast to play a different role in the decision algorithm than B and C. I don’t know if formally disallowing this kind of discrimination would have an effect on your example. The formality might be, for example, that the rules for the decision algorithm must always leave the election results unchanged under any permutation of candidate references.
In particular, what I mean is that if we simply swap the roles of A and B in the decision algorithm and leave everything else unchanged, the same exact ballots may lead to different election results. Is this problematic? I’m not sure, I'm just trying to point to another sort of “fairness” or “impartiality” criterion to consider. I wonder if something like this could be implicated in a formal connection between participation and monotonicity. It seems important to me to make very clear the distinction between variables and references.
I also think there may be some ambiguity in terms of how you have communicated your example. By saying that, for instance, D>B>C>A is the “only ballot,” do you mean that there is only a single ballot cast in the election, and that it has this form, or that there may be many ballots cast, but that each of them indicates this same ranking?
@bternarytau I returned to thinking about this. I think that if the voting system is homogenous—meaning that scaling the ballot set leaves the winner invariant—and generic, meaning that almost every distribution of ballot sets has a neighborhood of ballot sets of nearby distributions that give the same winner—then it seems very reasonable that the participation criterion would imply monotonicity. And these two criteria seem satisfied by pretty much any reasonable voting system.
I don’t consider this a formal proof but a sketch of plausibility, and this kind of reasoning might somehow lead to a formal proof that for a generic homogeneous voting system, participation almost always implies monotonicity.
If a homogeneous, generic system is not monotonic, then there are two ballot sets B1 and B2 of the same size such that the winner of B1 is x, and such that every ballot in B2 has an identical corresponding copy in B1 except for exactly K ballots for some K, which are all the same as their corresponding ballots in B1 except for having a higher rating of x; however, despite this, the winner of B2 is y≠x.
Now scale up the ballot sets (making the same number of copies of each ballot) by a factor of (1+E) for some positive E to make B1’ and B2’ with the same properties by homogeneity, except now there are K(1+E) ballots in B2’ whose corresponding copies in B1’ rate x lower. Let this set of K(1+E) ballots be called X, and its complement is (B2’-X).
Also, suppose actually that these K(1+E) ballots rate x at maximum. This seems plausible to be able to find.
Note that if the winner of (B2’-X) is x, then we are done, since this is a no-show paradox—the K(1+E) voters can make their favorite x win by abstaining from voting. Therefore we may assume that the winner of the election from the ballots in (B2’-X) is different from x, say z.
Now let a small subset H of X be changed so that the distribution of ballots in the union Hu(B2’-X) of H and (B2’-X) approaches the same distribution of ballots as are in B1.
As H is increased in size, the distribution of ballots in Hu(B2’-X) must be able to approach that of B1 (with respect to whatever metric you consider), and since the system is generic, at some point, the winner of the election in Hu(B2’-X) must switch from z to x, possibly through some intermediaries, but at some point it will almost certainly stabilize at x.
As this subset is grown, the winner of the election based on all of the ballots in B2’ also changes from y to x, also possibly through some intermediaries, but at some point it also almost certainly will stabilize at x.
Now, it seems virtually impossible that these stabilizations will occur simultaneously. If the stabilization of Hu(B2’-X) occurs first, then we are done. If the stabilization occurs second, then right at the boundary of stabilization, if there are any voters outside of X who prefer the intermediary winner to x, they should also abstain from voting, which will push the distribution back the other way.
There are obviously some extra assumptions made here, but I think this is at least convincing that almost all reasonable voting systems will not satisfy participation if they are not also monotonic.
You are def not the first one to ask this: https://link.springer.com/content/pdf/10.1007/s003550100128.pdf Here they give a few examples that participation does not imply monotonicity.