[EM] Binary Tree Single Elimination Tourney

[Forest Simmons]

If we had a natural way of organizing candidates into a binary tree ...
like some sports leagues do for their end of season championship
tournaments, we could have more efficient runoffs ... whether instant or
not.

Even if you had 500 candidates (as contemplated in a recent fantasy thread
about "narrowing the field"), a well balanced binary tree would organize
the single elimination pairwise tournament into just nine stages, since 500
is less than 512= 2^9.

Finally, after two decades of contemplating this possibility, (and many
false starts) I think we've hit upon a natural way of doing this ... the
operative word being "natural" ... hopefully natural enough that it
properly respects sets of cloned candidates, which is the biggest challenge.

One of my more successful false starts was to take the drainage tree in
Jobst's River method and (in the language of geometric topology) "lift" the
branch nodes into general position, which converts the drainage structure
into a binary tree ... reflecting the fact that in nature you rarely see
more than two rivers running together simultaneously.

This new method results in the same binary tree, but more simpl6 and
directly ... bypassing the River approach.

So with only a bit more ado ...

Start with the weighted, directed graph whose vertices are the candidates
(or labels representingvthem) and whose directed, weighted edges represent
the pairwise supports/ oppositions of the two candidates connected by the
respective edges.

The weight of the edge directed from vertex X to vertex Y is the number of
ballots on which candidate X outranks candidate Y.

If the edge from X to Y has greater weight than the edge from Y to X, then
we say that X defeats Y, and that X is the pairwise victor over Y.

It is called the opposition to candidate Y by candidate X, and is also
called the support for X against Y.

The matrix that has the weight of the edge from X to Y in the intersection
of candidate X's row and candidate Y's column, is the weighted adjacency
matrix of the digraph.

The entries in X's row give the respective supports of X against Y. The
entries in Y's column give the respective oppositions to Y from the other
candidates.

The diagonal elements of the matrix can be used to store related
information, like first place counts, approval/ disapproval counts (whether
implicit or explicit) truncation/ abstention counts, etc.

The pairwise matrix allows processing of the weighted digraph without
having to look at it (like flying on instruments). When there are more than
a handful of candidates, the diagram starts to look like a plate of
spaghetti... so as the number of candidates grows, the matrix
represenration waxes and the digraph wanes in computational usefulness  ...
but the digraph continues to trump everything else when it comes to
describing and conceptualizing the process.

The adjacency digraph is highly connected, since every vertex is directly
connected to each of the other vertices by two directed edges.

Removing edges can disconnect the graph, separating it into two or more
smaller components.

To find the champion of a connected component S of the digraph ... remove
its weakest (smallest weight) edges one at a time until it separates into
two smaller components, H and K.

[In standard topological notation
S=H|K]

Component S's champion is the pairwise victor between the (recursively
defined) champions of H and K.

When we apply this procedure to the entire tournament digraph, we get (as
output) the tournament champion.

Example.

46 >B
44 B>C
5 C>A
5 C >B

A>B 51 to 49
B>C 90 to 10
C>A 54 to 46

Eliminating edges of weights 10, 46, 49, 51, and 54, leaves just one edge
.. the one of weight 90 from  B to C.

The two remaining components are
{A} and {B,C}, with respective champs of A and B.

So A, as the pairwise victor of these two components, is the champion of
their union ... i.e. the grand champ.

So far, so good!

fws
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230904/cd0f003a/attachment.htm>