[EM] [CES #4429] Looking at Condorcet

[Kristofer Munsterhjelm]

On 02/03/2012 08:45 PM, Andy Jennings wrote:

> - If someone built a computer program that presented me pairs of
> candidates at a time as Kristofer suggested, that would make it somewhat
> easier.  I think I would still prefer to divide them into tiers first,
> but if I divided them into tiers first, I might not need the pairwise
> comparison hand-holding.  Also, suppose that I analyzed the candidates
> in three different policy dimensions that I consider equally important
> and I found that my policy preferences were:
> Foreign Policy: A>B>C
> Domestic Social Issues: B>C>A
> Domestic Economic Issues: C>A>B
> Now I prefer A to B, B to C, and C to A.  A cycle among my own personal
> preferences when I compare them pairwise.  Then my output ranking would
> depend on the order in which the pairwise questions were asked.  ??!?

You could look at a (single-winner) voting method as a stand-in for a 
deliberative process. A ranked voting method tries to find the best 
common ranking given the data it has to go on, which are the votes 
themselves.

In the ideal case, you'd just have a deliberative process instead of the 
voting. There would be some back-and-forth and then you'd reach a 
consensus. The problem is that it doesn't scale.

But if a voting method is a stand-in for a deliberative process, then it 
makes sense that each voter's preference would be transitive. The voters 
would already have gone through an internal deliberative process to 
arrive at a ranking of the candidates they are considering. So if I'm 
right about that, then the voter would already know his own consensus 
ranking based on the "foreign vs social vs economic" tradeoffs and the 
relative weights they have to him.

In practice, things aren't that clean, but I think it works to show, 
intuitively, that people would have transitive rankings and so wouldn't 
encounter the internal cycle problem.

If a voter's internal ranking is transitive, then you would only need to 
ask him "X better than Y?" n lg n times for n candidates*, where lg is 
the base-2 logarithm. If not, you would have to ask him n^2 times. 
Condorcet-type methods could handle both cases - in the latter, n^2 
case, a pairwise method would incorporate intra-individual cycles by the 
exact same logic as it'd handle inter-individual cycles.

(As I have said before, I have been thinking about using Condorcet 
methods for getting a ranking out of preference comparisons where the 
individual may have internal cycles because the set is so large. Ranking 
pictures is a simple example of that, as there may be so many pictures 
that the person looks at different things when comparing X to Y than 
when comparing Y to Z. However, doing n^2 comparisons grows very quickly 
and becomes quite tiresome. Some amount of preprocessing may speed it up 
- like your "tiers" or an Approval first stage where the person is 
generous with the approvals but excludes that which he considers 
obviously uninteresting.)

* The simplest algorithm that achieves this bound is, in essence, an 
insertion sort that uses a binary search for each insertion. Its 
constant factor is better than say, quicksort, too, since all we care 
about is the number of comparisons, not the time it takes to insert.