[EM] Covering Pairs

[Forest Simmons]

Can anybod find a simpler example of a candidate set that cannot be covered
by some pair of its members?

This is a cycle of cycles created by cloning each member of an ABCA cycle
... replacing A with an a1a2a3a1 cycle, B with a b1b2b3b1 cycle, and C with
a c1c2c3c1 cycle.

It's tedious but not impossible to construct a ballot set that creates this
cycle of cycles.

No pair covers it.

But the triple {a1,a2,b1} does cover it, as does {a3,b2,c1}, for example.

Two questions:

Q1: Is there a simpler example of a candidate set not covered by some pair
of candidates?

Q2: What is the likelihood of such a pair appearing in a public election?

-Forest

On Thu, Mar 9, 2023, 4:13 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> A subset K of candidates covers the entire set of candidates kappa iff no
> member of kappa-K (the complement of K) defeats every member of K.
>
> Let W be the matrix whose j_th entry in row i is 1 or 0 depending on
> whether or not candidate i is ranked ahead of candidate j on more ballots
> than not.
>
> This W is called the pairwise win matrix.
>
> Let C be a set of columns of W. Then AND(C) is a vector in the column
> space of W formed by applying the logical AND operator component-wise to
> the set of columns.
>
> When dealing with zeros and ones, AND is the same as both muliplication
> and minimization: 1×1=1, 1×0=0, min(1,1)=1, min(1,0)=0.
>
> It is easy to see that AND(C) is the zero vector iff the set of candidates
> K contributing the set of columns C covers the entire set of candidates
> kappa.
>
> In particular, the j_th and k_th columns of W will have a dot product of
> zero iff candidates j and k together cover kappa.
>
> This fact is of practical importance because ... if kappa is the set of
> candidates in a public election, there will practically always be a pair of
> candidates that together cover kappa.
>
> A single candidate covers kappa iff its column in W is the zero vector ...
> which means it is unbeaten pairwise.
>
> So not every ballot set has a Condorcet Winner, but every public election
> has a covering pair ... with practical certainty ... no known public ballot
> set has ever required more than two candidates to cover it ... and it's not
> easy to devise a plausible theoretical one.
>
> These considerations are the practical basis for the following method:
>
> If there is no single covering candidate (i.e. Condorcet Candidate) ...
> ... then within 24 hours after the votes have been tallied, each candidate
> must submit a proposed covering pair.
>
> Any proposed pair that does not cover the candidates is thrown out.
>
> The majority winner of each confirmed covering pair is then determined.
>
> Finally, the winner with the most votes is elected.
>
> That's it ... except ...  legally the theoretical possibility of
> non-existence of a covering pair must be "covered".
>
> In that vein I suggest including a clause that says ... if no candidate is
> able to submit a valid covering pair, an additional 24 hours is allowed for
> each candidate to propose a covering triple.
>
> Among the respective IRV winners of the confirmed covering triples, elect
> the one with the most transferred votes.
>
> -Forest
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230309/c8c33034/attachment.htm>