[EM] Identifying clone sets via the pairwise matrix

[Kristofer Munsterhjelm]

On 07/17/2017 09:08 PM, Monkey Puzzle wrote:
> Is it possible to identify a group of clones via the pairwise matrix?
> Or must it be done strictly via an examination of ballots?

I suspect it's like mutual majority: you can make a method that passes 
the associated criterion and only uses the pairwise matrix, but you 
can't identify the set itself.

Some fiddling with linear programming gives a concrete counterexample.

Ballot set 1:

6: A>B>C
1: C>A>B
3: C>B>A

Here the clone set is {A, B}. {A, C} can't be a clone set because of the 
first group of voters, and {B, C} can't be a clone set because of the 
second group.

The pairwise values are:

A>B: 6 + 1 + 0 = 7
A>C: 6 + 0 + 0 = 6
B>C: 6 + 0 + 0 = 6

Since every ballot is strict, I'm skipping the "other-way" pairwise 
values (B>A, C>A, C>B) since they can be determined from the three 
values above.

Ballot set 2:

3: A>B>C
3: A>C>B
3: B>C>A
1: C>A>B

{A, B} can't be a clone set because of the second group of voters. {A, 
C} can't be a clone set because of the first group of voters. And {B, C} 
can't be a clone set because of the last group. Thus there are no clone 
sets (except possibly the set of all candidates).

The pairwise values are:

A>B: 3 + 3 + 0 + 1 = 7
A>C: 3 + 3 + 0 + 0 = 6
B>C: 3 + 0 + 3 + 0 = 6

So the method can't identify a clone set from the pairwise matrix alone.

There may be other polyspace data structures that one could use to 
identify clones, though I suspect not. A pigeonhole argument might work 
to show that, but that's just a hunch.

I'd say it's likely that there exists some data structure that does the 
job and, while taking superpolynomial space in the number of candidates, 
scales much more slowly than recording every ballot. But I don't know 
what it is :-)