Talk:Maximal lotteries

Maximal lotteries, Condorcet criterion, participation criterion

Whenever someone proposes a new election method, he first claims that this method satisfies all known criteria, even those that are known to be incompatible with each other. For example, the maximal lotteries article claims that this method satisfies the Condorcet criterion and the participation criterion even though it has been proven that these two criteria are incompatible with each other. Markus Schulze 07:41, 4 August 2015 (UTC)

The theorem by Moulin that you are referring to only holds for deterministic and single-valued rules. Maximal lotteries (ML) yields probability distributions over alternatives. It is shown in this paper that ML satisfies a natural version of participation for probabilistic rules (which is also what is claimed in the Wikipedia article):

http://dss.in.tum.de/files/brandt-research/mlpart.pdf

Set-valued Condorcet-consistent rules that satisfy participation have also been considered:

http://dss.in.tum.de/files/brandt-research/partset.pdf

It seems to be a general problem in the voting articles on Wikipedia that voting methods with very different outputs (single candidates, sets of candidates, rankings of candidates, lotteries over candidates) are compared to each other using the same criteria.

Should I add a link to the first reference above?

And just for the record: ML is not a new method. It has been around since the 1960s.

Flix~enwiki (talk) 10:21, 15 August 2015 (UTC)

It is not true that voting articles on Wikipedia ignore the probabilistic framework. For example, the participation criterion article says: "In a probabilistic framework, the participation criterion says that the addition of a ballot, where each candidate of the set X is strictly preferred to each other candidate, to an existing tally of votes should not reduce the probability that the winner is chosen from the set X." However, even with this version of the participation criterion, Moulin's proof that the Condorcet criterion and the participation criterion are incompatible still works.

In my opinion, the problem with the maximal lotteries article is that it is written too much like an advertisement and too little like an actual description of this method. Furthermore, a concrete example (preferably without a Condorcet winner) would be helpful to understand the article. Markus Schulze 13:05, 15 August 2015 (UTC)

I did not say that voting articles on Wikipedia ignore the probabilistic framework. I said that voting methods with very different outputs (single candidates, sets of candidates, rankings of candidates, lotteries over candidates) are compared to each other using the same criteria. For example, there is a huge table in the article on voting systems which contains set-valued methods (e.g, Approval, Borda, Copeland), ranking methods (e.g., Kemeny-Young), and randomized methods (e.g., random winner). Yet, it's unclear how some of the considered properties should be defined for all these functions. For example, LIIA has only been properly defined for ranking functions and there is no generally accepted definition of participation for set-valued functions. The definition of participation for randomized methods you cite sounds interesting, but to the best of my knowledge has never been considered in social choice theory. The reference points to an article in a non-academic online journal that deals exclusively with multi-seat elections and does not contain the definition given in the Wikipedia article. Also, I don't see why Moulin's proof should go through with this modified definition of participation.

Coming back to maximal lotteries, the article claims that maximal lotteries satisfies a "probabilistic version of participation", which I consider fairly accurate. I also added an example to the article, added the above-mentioned reference, and mentioned the failure of maximal lotteries to satisfy strategyproofness. Flix~enwiki (talk) 13:04, 18 August 2015 (UTC)

The participation criterion article says: "The addition of a ballot, where each candidate of the set X is strictly preferred to each other candidate, to an existing tally of votes should not reduce the probability that the winner is chosen from the set X." This version of the participation criterion has been proposed by Douglas R. Woodall. Here you can see that Moulin's proof (that the Condorcet criterion and the participation criterion are incompatible) still works with Woodall's version.

So if e.g. a ballot, where the candidates are ranked A > B > C > D, is added then Woodall's version says that (1) p(A) must not decrease, (2) p(A)+p(B) must not decrease, and (3) p(A)+p(B)+p(C) must not decrease.

If I understand Brandt's papers correctly, then his version of the participation criterion only says that 3*p(A)+2*p(B)+p(C) must not decrease.

It is easy to see that Woodall participation implies Brandt participation. On the other side, Brandt participation does not imply Woodall participation. For example: p_old(A)=0.25, p_old(B)=0.25, p_old(C)=0.25, p_old(D)=0.25, p_new(A)=0, p_new(B)=1, p_new(C)=0, p_new(D)=0. Woodall participation is violated because p(A) decreases, whereas Brandt participation is satisfied because 3*p(A)+2*p(B)+p(C) increases. Markus Schulze 16:58, 18 August 2015 (UTC)

Woodall's version of participation is indeed interesting. It is equivalent to strong participation with respect to stochastic dominance (SD). What you call Brandt participation is not defined as you state. In terms of your example, it is: When adding ballot A>B>C>D and the resulting lottery changes, then (1) p(A) must increase, or (2) p(A)+p(B) must increase, or (3) p(A)+p(B)+p(C) must increase. This is (weak) participation with respect to SD. Similar notions for strategyproofness (weak and strong SD-strateygproofness) are standard in randomized social choice and assignment. The corresponding notions for participation are defined in this paper: http://www.aamas2015.com/en/AAMAS_2015_USB/aamas/p1411.pdf

Your version of Moulin's proof shows that there is not Condorcet extension that satisfies strong (SD-)participation. BTW: Maximal lotteries also satisfies a notion of participation that is in between strong and weak SD-participation: PC-participation where PC is defined here: http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/download/8534/8468

Flix~enwiki (talk) 12:18, 20 August 2015 (UTC)

Monotonicity criterion

Example 1:

2 voters: a > b > c

2 voters: b > c > a

1 voter: c > a > b

Result: p(a)=3/5, p(b)=1/5, p(c)=1/5.

Example 2:

2 voters: a > b > c

1 voter: b > c > a

1 voter: c > a > b

1 voter: c > b > a

Result: p(a)=1/3, p(b)=1/3, p(c)=1/3.

So ranking candidate b higher (here: replacing voter c > b > a by voter b > c > a) decreases p(b) from 1/3 to 1/5. This shows that maximal lotteries violates the monotonicity criterion. Markus Schulze 18:29, 19 August 2015 (UTC)

Yes, this counter-intuitive behavior of maximal lotteries is well-known. Whether this is a failure of monotonicity again depends on how you extend the definition to randomized rules. The standard definition says that if x is elected, it should still be elected if x is up-ranked. Your interpretation for randomized rules, which is surprisingly strong, says that p(x) should not decrease if x is up-ranked. Another interpretation would be to say that if x is elected with positive probability it should still be elected with positive probability if x is up-ranked. This second version is satisfied by maximal lotteries. Flix~enwiki (talk) 12:32, 20 August 2015 (UTC)

Population Consistency

Population consistency says: "Whenever two disjoint electorates agree on a lottery, this lottery should also be chosen by the union of both electorates." So population consistency can be considered a probabilistic version for the classic consistency criterion. The following example shows that maximal lotteries fail population consistency.

Electorate 1:

2 voters: a > b > c

2 voters: b > c > a

1 voter: c > a > b

Result: p(a)=3/5, p(b)=1/5, p(c)=1/5.

Electorate 2:

2 voters: a > c > b

2 voters: c > b > a

1 voter: b > a > c

Result: p(a)=3/5, p(b)=1/5, p(c)=1/5.

Reason: The only difference between electorate 1 and electorate 2 is that candidate b and candidate c have been replaced with each other.

Electorate 1+2:

2 voters: a > b > c

2 voters: b > c > a

1 voter: c > a > b

2 voters: a > c > b

2 voters: c > b > a

1 voter: b > a > c

Result: p(a)=1/3, p(b)=1/3, p(c)=1/3.

Reason: The result of maximal lotteries depends only on the entries of the skew-symmetric pairwise matrix. However, this matrix contains only zeros.

Markus Schulze 18:30, 7 September 2015 (UTC)

For the profile given by Electorate 1+2, every lottery is maximal. Hence, population-consistency is satisfied because the (3/5,1/5,1/5) lottery is returned (among other lotteries).

The fact that maximal lotteries satisfy population-consistency was proved in this paper: https://www.econometricsociety.org/publications/econometrica/browse/2016/09/01/consistent-probabilistic-social-choice. 2A09:80C0:41:0:0:0:0:146 (talk) 14:02, 22 June 2023 (UTC)

The above example is correct for electorate 1 and electorate 2. For electorate 3, it is right that the result of maximal lotteries depends only on the entries of the skew-symmetric pairwise matrix, which contains only zeros.

It is important to note, however, that ML is a set-valued solution concept, i.e., there may exist multiple lotteries that are maximal for a given profile. In (the rare) case of a zero matrix, any probability distribution will be maximal with respect to the underlying preference profile; in particular, all three lotteries mentioned above will be amongst the maximal ones. For population consistency as defined in , it is not required that the "lottery chosen by the union of both electorates" is chosen uniquely, but only that it is amongst the maximal lotteries.

Thus, the above example does not disprove that ML satisfies population consistency. (Referring to the formal definitions in might have cleared things up earlier.)

Cgeist (talk) 11:55, 8 September 2015 (UTC)

Reversal Symmetry

The article claims that maximal lotteries satisfy reversal symmetry. In what sense do they do so? If you reverse the example election (take the negative of the margin matrix), the resulting solution is unchanged. The Rivest/Shen paper even uses that phenomenon as one of their reasons for concluding that maximal lotteries don't satisfy reversal symmetry. WildGardener (talk) 20:55, 9 June 2023 (UTC)

Reversal symmetry is defined for profiles that admit a unique winner. Otherwise every anonymous and neutral set-valued SCF would violate reversal symmetry because in the classic Condorcet cycle profile all 3 alternatives are returned, and the same alternatives are returned when reversing all preferences. For randomized rules, reversal symmetry can then be defined for profiles that result in a degenerate lottery, and ML satisfies this condition: If an alternative receives probability 1, it receives probability 0 in the reversed profile. See also https://pub.dss.in.tum.de/brandt-research/minpara.pdf and in particular Footnote 18, which mentions the kind of example you had in mind. 2A09:80C0:41:0:0:0:0:146 (talk) 13:54, 22 June 2023 (UTC)

The way you've stated this sounds very similar to requiring both the Condorcet winner and loser criteria. Is there a published paper somewhere that uses reversal symmetry in that way? The paper you linked (and the two other Brandl, Brandt, et al papers linked in the Condorcet/participation discussion above) don't seem to.

"Reversal symmetry is defined for profiles that admit a unique winner." The Rivest/Shen paper doesn't take such a restrictive view. Also, one could envision a hypothetical system where reversing the ballots causes the candidates with relatively high and low probabilities to switch places. I don't know whether a useful system with that particular property actually exists; I just mean to suggest there are plausible ways to interpret reversal symmetry beyond the narrowest cases. WildGardener (talk) 22:03, 12 July 2023 (UTC)