[EM] HBH

[Juho Laatu]

This HBH method seemed interesting, so I coded it and reactivated some old code that can produce Yee figures and do some further analysis on the election methods. I rewrote some parts of the old software and I'm not quite sure that the old code, the new code and the new implementation of HBH are quite bug free (few hours ago they were not), but let's hope for the best.

Two dimensional simulations are not a complete analysis of a method, but two-dimensional pictures can often visualize the properties of different methods very well, so let's take that route. First I tested some basic variants of the HBH method.

<https://lh6.googleusercontent.com/-YRF-TTVNxsg/Tis-1SkFYaI/AAAAAAAAARQ/-Zv9-v1fXrY/hbh3.jpg>

The first figure above is a Yee figure with 6 random candidates (coloured dots) and 100 random voters (small white dots). In this figure the method is HBH with 3 possible rating values (i.e. voters can rate candidates using e.g. numbers 2, 1 and 0). The candidates are all centrists in the sense that voters have been distributed in a wider area than the candidates (deviations 10 vs. 3). This method is very centrist oriented since the cyan area that indicates the area where the most centrist candidate (cyan) wins is quite big.

Small grey boxes indicate elections that had to use lottery in some phase of the counting process. You can see that those lotteries did not cause any meaningful randomness in the results since all the boxes are in uniformly coloured areas or on some clear borderlines between two uniform winning areas.

The large white circle represents the centre point (average) of all the voters. Some voters can not be seen since they are outside of the borders of the figure. The voters are shown in a position that corresponds to the location of the voters (average voter) in the election whose end result is shown in the middle of the figure (big white circle). In other elections these voters are moved to left/right/up/down. In this simulation the pattern (relative location) of the 100 voters was kept the same in all points of the Yee figure (i.e. no new randomization in the other spots).

In the simulations I assumed that the voters will normalize their vote, i.e. they will rate one candidate at max and one at min value. There was no truncation (other that what the limited number of rating values leads to). The voters rated the candidates according to their preferences (distance in the two dimensional space) and did not try e.g. (in Borda or ranking style) to allocate all candidates to different slots (even when there were many enough slots to do that).

All the later figures have mostly the same parameters. I'll try to tell when there are some differences.

<https://lh6.googleusercontent.com/-PSqd-hbjgH0/Tis_dyS75DI/AAAAAAAAARU/BwumL83i954/hbh5.jpg>
<https://lh6.googleusercontent.com/-lpZoZyZoqWk/Tis_jZYp42I/AAAAAAAAARY/pyX1tB6tXjs/hbh7.jpg>
<https://lh6.googleusercontent.com/-denzTfcNVxk/Tis_oj00M5I/AAAAAAAAARc/B0J6A3javuE/hbh10.jpg>
<https://lh4.googleusercontent.com/-oREdtEZBnYs/TitMO-n9N-I/AAAAAAAAASU/2EvwWV5pJwo/hbh50.jpg>

Then I made corresponding figures with 5, 7, 10 and 50 different rating values. You can see that the method becomes less "centrist oriented" when the number of different ratings grows.

<https://lh5.googleusercontent.com/-GWE7VgOGB4Q/Tis_y852DXI/AAAAAAAAARk/EmYXAgT44NU/mmm.jpg>

Here's also one traditional method for comparison. This figure shows the same simulation with minmax(margins). Note that HBH with 50 different values is already quite close to the classical Condorcet results.

I'll continue with the HBH method with 10 ratings (it provides quite nice figures and is maybe close enough to the intended number of ratings (?)). All the remaining figures are thus "HBH(10)" figures.

<https://lh4.googleusercontent.com/-afIWrWshyzw/Tis_-PgwjXI/AAAAAAAAARo/e8KM0qBJges/hbh10_red_candidate.jpg>

This is not a classical Yee figure but an analysis on what how one of the candidates can influence the outcome of the election by changing his policy / marketing / location in the two-dimensional space. The red candidate has a white border line and the big white ring is also there to point out that in this simulation the red candidate moves in the two-dimensional space. (Voters are shown in grey since they do not move in this simulation. Only the red candidate moves.) It is quite obvious that in this kind of centrist oriented method the best place for the red candidate is in the middle. Red candidate will win if it can move below the yellow and cyan candidates. If the red candidate moves to the left, yellow candidate will win. Nothing too dramatical here. This is pretty much as expected. Other candidates than red have pretty similar strategic opportunities (the red picture was just the nicest of them).

<https://lh6.googleusercontent.com/-0fZbQXqCJcQ/TitADR6lYOI/AAAAAAAAARs/TEPnCcDOBT0/hbh10_to_darkgreen.jpg>

Then another simulation to check how different voter groups could influence the end result. Here the HBH(10) method is actually quit immune to voters strategies. In this figure those candidate that prefer the dark green candidate to the candidate that wins the election (cyan) when the voters are in the central position (that is shown in the figure) have been shown as white. Other voters are shown in grey. In the simulation the white voters will move. The figure thus shows what strategic opportunities those "dark green > cyan" voters have to make the dark green candidate win. In this case they have no chances to improve the outcome of the election from their point of view. All they can do is to make yellow win. And that is not what they want.

In this simulation the dark green supporters are coordinated. That means that they will vote as one block. All white voters will thus cast a similar vote. That improves their ability to influence the outcome of the election (but not enough from their point of view in this case).

Other voter groups didn't have any better chances to influence the outcome. Some of them could not change the end result at all.

(This figure was not very interesting. Maybe the simulation technique is of more interest. With some other methods this technique provides much more informative and interesting results. Also other strategies like exaggeration could be simulated, but I'll skip that for now.)

<https://lh3.googleusercontent.com/-DcbEwzueLs0/TitAM9Ho9PI/AAAAAAAAARw/igISLh3Esxk/hbh10_add_magenta.jpg>

Next, a simulation on the impact of additional candidates. HBH(10) was quite immune to voter strategies in the previous example simulation but this figure shows that additional candidates can influence the outcome. The basic strategy that is visible in this figure is to nominate extra candidates that will influence the elimination order. Even though the candidates themselves might be eliminated early on, they may still influence the outcome in some controllable way. In this simulation the existing candidates and voters will stay where they are, but there will be one additional candidate (magenta) whose position will change.

It seems that in this simulation the yellow candidate could win if there was another (extreme) candidate in the same direction. The same pattern applies also to red, dark green and blue candidates. (Note that the scale of this figure is different from the earlier ones since the interesting things are in the edges and in extreme opinions / candidates.)

I will not say anything about how common this pattern is since I didn't do extensive simulations on this topic, and since the two-dimensional may not be a sufficient proof anyway. But this figure anyway shows that there is such a tendency. This method is quite dependent on the relative position of the candidates. Adding one candidate to one side of the field makes the more centrist candidates of that side more centric, and in a centrist oriented method that will help them win. The elimination process aims at eliminating the outmost candidates. One may thus to some extent protect one's own favourite candidate by nominating additional candidates next to it.

It is not possible to control the whole chain of elimination. But it is possible to force some candidates from the "opposing side" to be nominated as V (see the description of the HBH method below). Once someone has been nominated as "V", that candidate will be compared also to others, and chances of it becoming eliminated will increase.

It is possible that many key candidates would follow this plan and all nominate additional candidates. Probably there are some limits to what one can do in the form of nomination rules. But strategies seem to be possible here.

(Note that in the middle of the figure there is also a small magenta area where the added candidate can win himself.)

<https://lh5.googleusercontent.com/-155af5-JA2E/TitAR0Ku_WI/AAAAAAAAAR0/z-M1mbwaJw8/hbh10_add_magenta_05.jpg>

I show also this simulation since it is interesting. This simulation is similar to the previous one but here the strength of the added (magenta) candidate is only 50% of the strength of the other candidates. The reduced strength of a candidate means here that it is less attractive to the voters. Distance between a voter and a candidate is n times the distance to a regular candidate if the strength of this candidate is 1/n times the strength of a regular candidate. (The simulations may have also candidates that are stronger than other candidates.)

(Do you think this is a natural way to model candidates that have different "overall strength" or "overall popularity" in addition to having a position in the (two-dimensional) political map?)

The interesting point is that weak candidates seem to implement the strategy more efficiently than strong candidates. Maybe it is a good idea to nominate a weak candidate that will be the first "V" candidate. That starts the elimination process in a good way, pointing out the candidate at the opposite side as the next "V". More simulations (and other analysis) would be needed to see if this pattern is common and stable enough to be used as a basis for strategies in real elections.

<https://lh6.googleusercontent.com/-t4Tsv1c6qNo/TitAXGsKfFI/AAAAAAAAAR4/x7IdrkE7SRk/hbh10_magenta_added.jpg>

And here I added one possible magenta candidate into the (regular Yee) simulation as a regular candidate (full weight). The magenta candidate (or small part of it) can be seen in the upper left corner. In this example the yellow candidate seems to win instead of the cyan candidate (as expected based on the analysis of two previous figures).

I hope the colours are easy enough to see. If you want to check the results in your own programs I'll give the approximate coordinates of the 6 (random) candidates below.

Juho


Candidate coordinates:
(5.835, 10.155)  red
(3.838, -1.124)  green
(4.659, 1.005)  blue
(3.240, 8.928)  yellow
(5.314, 7.453)  cyan
(7.113, 3.584)  dark green


On 18.7.2011, at 21.25, fsimmons at pcc.edu wrote:

> HBH stands for Hog Belly Honey, the name of an inerrant "nullifier" invented by a couple of R.A. Lafferty 
> characters.  The HBH is the only known nullifier that can "posit moral and ethical judgments, set up and 
> enforce categories, discern and make full philosophical pronouncements," in other words eliminate the 
> garbage and keep what's valuable. The main character, the "flat footed genius," Joe Spade, picks the 
> name "Hog Belly Honey," for it "on account it's so sweet."
> 
> The whole idea of HBH is just starting at the bottom of a pecking order and pitting (for elimination) the 
> current champ against the most distant challenger.  I hope you will keep that in mind as we introduce 
> the necessary technical details.
> 
> HBH is based on range style ballots that allow the voters to rate each alternative on a range of zero to 
> some maximum value M.  [Keep this M in mind; we will make explicit use of it presently.]
> 
> Once the ballots are voted and submitted, the first order of business is to set up a "pecking order" for 
> the purpose of resolving ties, etc.  Alternative X is higher in the pecking order than alternative Y if 
> alternative X is rated above zero on more ballots than Y is rated above zero.  If both have the same 
> number of positive ratings, then the alternative with the most ratings greater than one is higher in the 
> pecking order.  If that doesn't resolve the tie, then the alternative with the greatest number of ratings 
> above two is higher, etc.
> 
> In the practically impossible case that two alternatives have exactly the same number of ratings at each 
> level, ties should be broken randomly.
> 
> The next order of business is to establish a proximity relation between alternatives.  For our purposes 
> closeness or proximity between two alternatives X and Y is given by the number
> 
> Sum over all ballots b, min( M*(M-1), b(X)*b(Y) ).
> 
> [The minimization with M*(M-1) clinches the method's resistance to compromise, as explained below.]
> 
> This proximity value is a useful measure of a certain kind of closeness of the two alternatives: the larger 
> the proximity number the closer the alternatives in this limited sense, while the smaller the number the 
> more distant the alternatives from each other (again, in this limited sense).
> 
> For the purposes of this method, if two alternatives Y and Z have equal proximity to X, then the one that 
> is higher in the pecking order is considered to be closer than the other.  In other words, the pecking 
> order is used to break proximity ties.
> 
> Next we compute the majority pairwise victories among the alternatives.  Alternative X beats alternative 
> Y majority-pairwise if X is rated above Y on more than half of the ballots.
> 
> For the purposes of this method, the "victor" of a pair of alternatives is the one that beats the other 
> majority pairwise, or in the case where neither beats the other majority-pairwise it is the one that is 
> higher in the pecking order. Of the two, the non-victor alternative is called the "loser."  In other words, 
> the pecking order decides pairwise victors and losers when there is no majority defeat.  [This convention 
> on victor and loser is what makes the method plurality compliant, as explained below.]
> 
> Next we initialize an alphanumeric variable V with the name of the lowest alternative in the pecking 
> order, and execute the following loop:
> 
> While there remain two or more discarded alternatives
>   discard the loser between V and the alternative most distant from V,
>   and replace V with the name of the victor of the two.
> EndWhile
> 
> Finally, elect the alternative represented by the final value of V.
> 
> This HBH method is clone free, monotone, Plurality compliant, compromise resistant, and burial 
> resistant.
> 
> Furthermore, it is obviously the case that if some alternative beats each of the other alternatives majority 
> pairwise, then that alternative will be elected.
> 
> Let's see why the method is plurality compliant:
> 
> If there is even one majority defeat in the sequence of eliminations, every value of V after that will be the 
> name of an alternative that is rated positively on more than half of the ballots.  If none of the victories are 
> by majority defeat, then the winner is the alternative highest on the pecking order, i.e. the one with the 
> greatest number of positive ratings.
> 
> Let's see why the method is monotone:
> 
> Suppose that the winner is moved up in the ratings. Then its defeat strengths will only be increased, and 
> any proximity change can only delay its introduction into the fray, so it will only face alternatives that 
> lost to it before.
> 
> Let's see why it is compromise resistant:
> 
> Since Favorite and Compromise are apt to be in relatively close proximity, and pairwise contests are 
> always between distant alternatives, if Compromise gets eliminated, it will almost certainly be by 
> someone besides Favorite, so there can hardly be any incentive for rating Favorite below Compromise.
> 
> Furthermore, there is no likely advantage of rating Compromise equal to Favorite, because rating 
> compromise just below Favorite already makes the maximum possible contribution M*(M-1) to their 
> proximity sum, i.e. the best you can do to make sure they are pitted against each other only after all of 
> the other alternaties have been eliminated (if at all).
> 
> How about burial?
> 
> I don't have such an easy argument for burial resistance, but the experiments I have conducted show 
> that more likely than not it won't pay off.  I hope that Kevin will run his simulations on the method for 
> (hopefully) more support on that account.
> 
> I realize that the method sounds complicated from the description above, but all of the complication is 
> from the details of tie breaking, including what to do when defeats are not majority-pairwise.
> 
> Other than that, as mentioned at the beginning, it is just starting at the bottom of the pecking order and 
> pitting (for elimination) the current champ against the most distant challenger.
> 
> Aint that sweet?
> 
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info