[EM] Approval-Condorcet hybrid encouraging truncation

[Forest Simmons]

Dear Steve,

what I once called "Approval Seeded Bubble Sort" but would now (for
increased respectibility) call the "Local Kemenization of the Approval
Order" is a member of the family of methods that satisfy your conditions
(1) and (2).

We initialize with the approval order and then, starting at the top, let
each candidate percolate upward as far as possible by transposing adjacent
pairs whenever the pairwise matrix allows it.

Suppose that the number of ballots that show x above the approval line and
y below the line is greater than the number of ballots that show y above
the line and x below.  Then x is "seeded" above y.  Suppose that it is
also true that more ballots rate x above y than vice versa.  Then the pair
(x,y) will never be transposed in the local Kemenization (i.e. during the
bubble sort).  Therefore, condition (2) is satisfied.

Modifying condition (1) to allow more than two preference strengths,
resulting in successively refined pairwise matrices, makes it possible to
refine the approval order by successive Kemenizations, and thereby satisfy
a generalization of condition (2).

One way to think of this is that the (global) Kemeny order is
computationally intractable because there are so many local optima to
choose from.  It's like hoping that by kicking a soccer ball into a rough
hilly field it would settle into the lowest equilibrium position.

But if we rolled a very large ball (1 km diameter, say) into the terrain
in question, it would settle near the bottom of one of the deeper valleys.
Then a smaller, but still large ball, would settle in one of the deeper
depressions in the valley, and finally, a smaller ball would settle into
one of the dents in the depression of the valley of the countryside
terrain (in the vicinity of the house that Jack built).

Forest

On Mon, 10 Mar 2003, Steve Eppley wrote:

> On 10 Mar 2003 at 11:36, Kevin Venzke wrote:
> > My recent "MinMax" message concluded with a
> > half-hearted attempt at a system combining Approval
> > and Condorcet.  I have a much better proposal now,
> > although I'm not entirely certain of its merits.
> -snip-
>
> I have another way of combining Approval and Condorcet,
> actually a family of voting methods, plus a criterion they
> satisfy that is stronger than Mike Ossipoff's "Strong
> Defensive Strategy Criterion" (a variation of which I call
> the Minimal Defense criterion).
>
>    1. Each voter is allowed to (non-strictly) order the
>    candidates from top to bottom, and optionally
>    may insert a "dividing line" anywhere in her ordering
>    (that partitions the candidates into two subsets,
>    those over the line and those under).
>
> Given a touchscreen voting interface, it would be
> straightforward to implement #1, since the dividing line
> could be dragged and dropped into the desired position just
> like any other candidate.  Given paper ballots that would
> be optically scanned, the following format would suffice:
>
>                 <--BETTER                  WORSE-->
>    Bradley          (X)   ( )   ( )   ( )   ( )
>    Nader            (X)   ( )   ( )   ( )   ( )
>    Gore             ( )   (X)   ( )   ( )   ( )
>    Bush             ( )   ( )   (X)   ( )   ( )
>    Buchanan         ( )   ( )   ( )   ( )   ( )
>    McCain           ( )   (X)   ( )   ( )   ( )
>    Dole             ( )   ( )   (X)   ( )   ( )
>    Keyes            ( )   ( )   (X)   ( )   ( )
>       DIVIDING LINE:   ( )   (X)   ( )   ( )
>
> Each voting method in the family constructs a social
> ordering consistent with the following:
>
>    2. For all pairs of candidates, say x & y, y is socially
>    ordered over x if the number of votes that rank "y over
>    x" exceeds the number of votes that rank "x over y"
>    and the number of votes that rank "y over the dividing
>    line over x" exceeds the number of votes that
>    rank "x over the dividing line over y."
>
> It's not actually necessary to construct such a social
> ordering, as long as the following condition is met:
>
>    For all candidates x, x must not be elected if there
>    exists a candidate y such that the number of votes
>    that rank "y over x" exceeds the number of votes
>    that rank "x over y" and the number of votes that
>    rank "y over the dividing line over x" exceeds the
>    number of votes that rank "x over the dividing line
>    over y."
>
> Assuming only one winner is to be elected, it's always
> possible to satisfy condition 2 (or the revised wording)
> since the subset of pairings that meet condition 2 is
> acyclic. (I have a proof of acyclicity, but it's tedious so
> I won't post it without a request.)
>
> The strong criterion satisfied by these methods is:
>
>    Sincere Defense: For all subsets X of the candidates,
>    all subsets C of voters and all candidates y,
>    if C includes more than half of the voters and
>    every member of C prefers y over every candidate in X,
>    then there must exist a way that the members of C
>    can vote that ensures all candidates in X will lose
>    and does not require any member of C to misrepresent
>    any preferences.
>
> Sincere Defense is stronger than Minimal Defense, which is
> stronger than Strong Defensive Strategy Criterion, since
> Minimal Defense and SDSC allow a majority coalition to
> misrepresent some preferences (by downranking candidate(s)
> to ensure their defeat).
>
> For an example of a preference order method that can be
> tweaked to satisfy Sincere Defense, MAM and other
> variations of Ranked Pairs can be tweaked to allow each
> voter to insert the dividing line in her ranking as in #1
> above, and to give utmost precedence to every pairwise
> majority that meets the condition in #2 above.
>
> I'm concerned that some voters wouldn't use the dividing
> line strategically as intended, and instead treat it as
> some sort of "sincere approval" dividing line.  In that
> case, the dividing line may not have much force because
> condition 2 wouldn't be met by as many pairwise majorities.
> For instance, some Nader voters might rank Gore and Bush
> below the line even though ranking Gore over the line would
> be more effective (by creating a majority voting "Gore over
> the line over Bush" that would ensure the defeat of Bush,
> who is the Nader voters' "greater evil").  So even though
> many voting methods could be tweaked to be in the family
> that satisfies Sincere Defense, only the best methods
> should be considered.  In particular, by tweaking a method
> that satisfies Minimal Defense, the "minimal defensive
> strategy" of downranking X can be simultaneously employed
> as a second line of defense.
>
> -- Steve Eppley
>
> _______________________________________________
> Election-methods mailing list
> Election-methods at lists.electorama.com
> http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com
>