[EM] smith/schwartz/landau

[Kristofer Munsterhjelm]

On 03/28/2018 10:26 AM, Juho Laatu wrote:
> Yes, works too. Includes "weak" votes that are not normalised to the 
> 100...1 range.
> 
> My question is still "whether it is a natural extension of the majority 
> rule to require that the winner should always be picked from the Smith 
> Set, when observing the number of voters only”.

I just thought of a way to see if the Smith criterion is a reasonable 
extension of majority; or rather, if it's a reasonable extension of 
Condorcet.

You say that if ABC were one candidate, he should win. What if we make 
ABC originate as one candidate? One way of doing so would be by cloning 
an initial A into ABC. Then we know (if we value clone independence) 
that in any situation where A wins against d in a majority election 
(that's where majority comes in), then if we clone A into ABC, the 
winner should be one of ABC.

And if we can turn any ABCd election (Smith set of size three, plus a 
Condorcet loser) into one where ABC are clones, then we get that any 
clone independent Condorcet method must be Smith in the four candidate 
case, just by extending majority, through Condorcet, into Smith.

Are there any clone-independent methods that meet Condorcet but not 
Smith? The only one I can think of is the "obvious" method that 
collapses clones and then runs Minmax. Perhaps also BTR-IRV? I'm not 
sure. But both of these require access to the ballots themselves, which
makes me suspect that you can't tell a clone scenario from a non-clone 
scenario if all you have is the pairwise matrix.

If I'm right, then for any given (3-cycle + 1) Condorcet matrix, I could 
use my old tool, linear programming, to determine a clone ballot set 
that would produce that matrix. It would be something like:

- Because ABC is a clone set, the only permitted ballots are xD or Dx 
where x is one of ABC ACB BAC BCA CAB CBA, i.e. ABCD ACBD BACD BCAD CABD 
CBAD DABC DACB DBAC DBCA DCAB DCBA.

- We want the pairwise strengths to be as determined beforehand.

- Usual constraints: no negative number of ballots, no infinities.

In your ABCd case, we have:

17: A > B > d > C
16: A > d > B > C
17: B > C > d > A
16: B > d > C > A
17: C > A > d > B
16: C > d > A > B

and the pairwise matrix is (for row, against column)

    A  B  C  d
A -- 66 33 50
B 33 -- 66 50
C 66 33 -- 50
d 49 49 49 --

Programming the LP gives the following clone solution:

33: A>B>C>d
17: B>C>A>d
16: d>B>C>A
33: d>C>A>B

that produces the same pairwise matrix as above.

If we collapse the clone set, we get

50: A>d
49: d>A

so any clone-independent Condorcet method that only knows the pairwise 
matrix must elect from the ABC set here, and since it can't distinguish 
the LP solution (where ABC is a clone set) from the original ballot set, 
there's no way for it to elect d in your example.

I haven't actually proven that clone independence + Condorcet + only 
look at the pairwise matrix implies 4-candidate Smith; that would 
require more linear algebra than I feel like using today. But it's not 
that implausible; and if it's true, that means that whatever makes a 
Condorcet loser deserve to win, if anything, must come from information 
not provided by the pairwise matrix.