[EM] Binary Tree Single Elimination Tourney

[Forest Simmons]

On Mon, Sep 4, 2023, 6:06 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> 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.
>

The more I think about it, the more I see that the pairwise winner of the
champs of H and K is not necessarily the best choice for the champ of the
union of H and K.

Geometrically, it appears that the champ should be somewhere in the
component of the pairwise winner, but not necessarily the pairwise winner
itself.

Perhaps, the best rule is to eliminate the candidates of the losing
component ... i.e. to restrict to the candidates in the winning component.

So remove the weakest edges one by one until S separates into H|K.

Determine which component S', whether H or K, to narrow down to, and apply
the method recursively to S' to find the champ of S.

Two obvious possibilities for S' ... one as mentioned earlier would be the
component whose recursive winner defeats the recursive winner of the other.

The other choice of S' would simply be the component of the pairwise winner
of the last (so strongest) defeat to be removed before the separation into
the two components.  In other words, the directed edge that barely hold H
and K together before it is removed ... that edge points to the losing
component ... away from S'.

This second option is the simplest one, because it does not require the
recursive determination of the respective champs of H and K ... but more
examples are needed to see if it holds up under pressure.


> 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/20230905/5fcc6145/attachment.htm>