[EM] Dyadic Approval definition (fourth installment)

[Forest Simmons]

I'm keeping this cumulative, so skip down to fourth installment for the
new stuff.
-------------------------------------------------------------------
First Installment:

Dyadic Approval is a generalization of both Approval and Condorcet.

It generalizes Condorcet by allowing expression of degrees of preference
(in a consistent way that doesn't encourage preference reversals or
collapses) as well as by retaining the pairwise aspect of Condorcet. 

It generalizes Approval by allowing the voter to make refinements within
various previously defined categories of Approval by specifying which
candidates within a category would be approved if they were the only ones
left. 

I find it is easiest to start with a sample voted ballot, and then
interpret it, and explain how it is scored and put into matrix form for
addition into the election totals.

Once the total matrix is in, the winner can be determined from the matrix
by SSD or any other good Condorcet method. However I am going to recommend
another method that takes advantage of the hierarchical structure of the
ballots for use when there are (generalized) Condorcet cycles (cycles of
pairwise preferences among candidates).

Here's a sample voted ballot with eight candidates:

        A > B >> C > D >>> E > F >> G > H

This one is ideal ... a precisely balanced binary tree with one leaf at
the end of each twig. I'll show some more typical and extreme ones
presently, to demonstrate the range of possibilities.

We interpret this ballot as follows. The voter supports (on the coarse
level of ordinary Approval) candidates A through D, and rejects E through
H.

However, if candidates A through D were to be eliminated (by
assassination, Approval runoff, heart attacks, etc.) then among the
remaining candidates E and F would be supported, while G and H would be
disapproved. Similarly, if all of the candidates except C and D were
eliminated, then the voter would approve only C.  I think you can see the
pattern.

For scoring, we note that the coarsest distinction is made by a string of
three inequality signs: >>>, so the score of any pairwise comparison of a
pair that straddles that string receives a weight of 1. Then any pair that
straddles >> (but not >>> ) receives a weight of one half.  Similarly, any
pairwise comparison between candidates on opposite sides of a single >
symbol (but no string of them) receives a weight of one fourth. 

Another voted ballot (for seven candidates this time) could look like the
following: 

      A >> B > C >>> D >>>> E, F >>> G

In this ballot the voter chose to not distinguish between E and F.  All
comparisons between E and F add zeros to the corresponding positions
in the scoring matrix. Furthermore, the underlying binary tree is not as
well balanced; some possible categories are missing.

The coarsest comparisons are the ones straddling the string of four
inequality signs ( >>>> ) so they are the ones that receive a weight of
one on this ballot.  By the time we get down to the comparison between B
and C, it only gets a weight of one eighth.

In particular, the comparison between the pair A and G  gets the same
weight as the comparison between D and E, so there is no temptation to
insincerely move D further up the list or E further down the list.

Two extreme possibilities are:

     A > B >> C >>> D >>>> E >>>>> F >>>>>> G

                       and

     A >>>>>> B >>>>> C >>>> D >>> E >> F > G

In the first of these two extreme cases, all comparisons relative to G
have a weight of one. Only the comparison between A and B has a weight of
1/32 . If this were a zero info election, it would mean the utilities were
skewed towards the upper end of the scale. 

In the second case, all comparisons relative to A receive a weight of one,
while the comparison between F and G has a weight of 1/32 .  If this were
a zero info election, it would mean the utilities were skewed toward the
low end of the scale. 

Promises for future installments:

(1) the binary string representation of the ballots.

(2) natural hierarchy resolution of cycles.

(3) answers to frequently asked questions.

(4) how to use these same style ballots for Approval Runoff.

--------------------------------------------------------------------

Second Installment:

There are two things I would really like to emphasize to this point.

First, the Dyadic Approval ballot is potentially richer in information
than either a plain preference ballot or a plain Approval ballot.

To convert to a plain preference ballot, just ignore the fact that there
are several kinds of inequality strings, and treat them all the same (i.e.
as in Condorcet). 

To recover the plain Approval information, just ignore all the approval
refinements (i.e. all the approval levels except the coarsest).

Second, if the ballots are only used to compare the candidates pairwise
(with consistent weights as outlined above), then there is no reason for
any voter to reverse any preference or to collapse any preference.

By collapse a preference, I mean making no distinction when there really
is a preference.  Regular Approval falls short in this regard because the
voter has no choice but to collapse some preferences. Cardinal Ratings
(CR) falls short because there are strong strategic incentives to vote
only at the extremes.

Putting these two observations together, we see that Dyadic Approval not
only has more information potential than either plain Approval or plain
Condorcet, it actually realizes that potential (when scored
appropriately). The voted ballots are indeed richer in information than
either plain Approval or plain Condorcet voted ballots. 

To understand the significance of this, consider the case of CR. The CR
ballot has potential for more information than either Approval or
Condorcet, but it cannot realize that potential (except on the perfect
honor system) since there are strong strategic incentives to inflate and
deflate the ratings all of the way to the respective extremes. 

As near as I know, Dyadic Approval and its obvious variations are the only
high resolution methods that don't suffer a strategic collapse of
information. (Compare Borda, a rather low resolution method that suffers
from strategic order reversals, worse than the mere collapses of CR and
plain Approval.)

On a practical note, a real Dyadic Approval election with several
candidates (and unsophisticated voters) would have to be via interactive
voting machines that that repeatedly ask the voters, "Which one or ones of
THESE candidates would you support if THEY were the only ones in the
race?"

For sophisticated voters in a committee situation, a voted ballot would be
written vertically (to make room for longer names) instead of
horizontally, and the marks separating the categories would be, lines,
double lines, triple lines, of different thickness, color, and other
attributes to emphasize the hierarchical order (i.e. binary tree
structure).

--------------------------------------------------------------

Third Installment:

Martin asked how to actually use Dyadic Approval. After I summarize in
general terms, I'll give a specific example:

First you figure the pairwise matrix for each ballot. Then you add up all
of the pairwise matrices to get the total matrix.

Once the total matrix is in, the winner can be determined from the matrix
by SSD, Ranked Pairs, or any other good Condorcet method. However I am
going to recommend another method that takes advantage of the hierarchical
structure of the ballots for use when there are (generalized) Condorcet
cycles (cycles of pairwise preferences among candidates). 

Example:

60 A >> B > C 
40 B > C >> A


Matrix for a ballot from the first faction:
    A       B       C
A   0       1       1
B   0       0      1/2 
C   0       0       0

Matrix for a ballot from the second faction:
    A       B       C
A   0       0       0
B   1       0      1/2
C   1       0       0

Total matrix for the election (60 times the first plus 40 times the
second):
    A       B       C
A   0      60      60   
B  40       0      50
C  40       0       0

We see that A beats both B and C, sixty to forty.

There's nothing particularly interesting about this example, since it is
only given to show how to calculate the winner. We see that our result
gives the majority and (ordinary) Approval winner, so it disagrees with no
major method other than Borda Count.

I hope that explains how to use Dyadic Approval.  I repeat that once you
have the total matrix you can forget all about Dyadic Approval and pretend
that the matrix came from ordinary Condorcet, and then process it
according to SSD rules, if that is your favorite Condorcet method. 

So in that respect it is more like Condorcet than Approval. On the other
hand when you are voting it feels more like Approval Runoff than
Condorcet.

--------------------------------------------------------------------
Fourth Installment:

Now I'll explain my recursive method for handling cycles (based on
the built in hierarchical structure of Dyadic Approval).

Suppose there are N candidates, so that the maximum depth (distance from
root to leaf) of the binary tree associated with a ballot is N-1. 

Initialize depth D as N.

[Start recursion]

1. Decrement D.

2. Calculate the Dyadic Smith set based on the total pairwise comparison
matrix calculated from the Dyadic Approval ballots (as described in
the preceding installment) collapsed to depth D.

3. Recursively pick a winner from the Dyadic Smith set using the Dyadic
Approval ballots collapsed to a depth of D-1.

[End of Recursion]

The recursion must come to an end before the depth reaches zero, because
at a depth of one the collapsed Dyadic Approval ballots are ordinary
Approval ballots which do not admit cycles. In other words, at that depth
the Smith set consists of just one candidate or a set of precisely tied
candidates.  In the latter (very unlikely) case resolve the tie with
random ballot. 

To prove that this method satisfies FBC do an induction on the maximum
depth of the Dyadic Approval ballots:

Initial condition:

The method satisfies FBC if the max depth is one, because ordinary
Approval satisfies FBC.

Induction step:

If the method satisfies FBC when the depth is D, then the method satisfies
FBC when the depth is D+1, because an FBC method (D depth Dyadic Approval)
is used to pick a winner from the Smith set.

The induction conditions are both satisfied, therefore D depth Dyadic
Approval satisfies FBC for all natural values of D.

[End of sketch of induction proof]

As near as I know, this formulation of Dyadic Approval is the only high
resolution method that gives no incentive to reverse or collapse any
preference.

[End of fourth installment]