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 :-)
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 :-)
