Instability vs anonymization in E Pluribus Hugo

The latest episode of Hugo voting-system fever is that the Hugo administrators were hoping to be able to release anonymized nomination data for this year's Hugo Awards, in order to test the new "E Pluribus Hugo" (single-divisible-vote last-place-elimination) slate-resistant nomination scheme. But now they have realized that anonymization is difficult: one of them made a first cut at anonymizing the data and another was able to match ballots to individual people even after the anonymization. As a result they're delaying (perhaps indefinitely) any release of the anonymized data.

So this naturally raises some questions: is anonymization really possible? What can we do to scramble the data, and what useful information would we lose by doing it?

One can't really anonymize the identities of the nominated works (at least, the more popular ones) without significantly changing the data, because their ranking by popularity gives them away. And knowing the identity of some of these works may be enough to identify some voters (who have been enthusiastic about the same set of works elsewhere on the net) and from that identify the less-popular works as well. Even just the connections between pairs of voters implied by the presence of a less-popular work on both of their lists would likely be enough to infer much of the structure of their social network and from that their individual identities. Some of the proposed anonymization techniques I've seen suggested to get around these problems include

• Replacing voter names by randomized identifier numbers (an obvious first step, but not good enough)

• Separately randomize voter names in each of the nomination categories (loses some possible information about slates, but reduces the amount of information that can be correlated to learn voter identities)

• Remove obvious-loser nominees. In the new EPH system being proposed, if the total number of voters for a given nominee is less than the fifth-largest total number of points (with one point per voter, spread evenly among their candidates), then no matter how the points are redistributed the nominee can't possibly win a place in the final ballot. So it would seem to be safe to remove those nominees from the data.

• Alternatively, randomly re-distribute the votes for obvious-loser nominees among the voters, to break up any social-network structure that might be inferred from them. They're not going to win, so why should it matter which voters voted for them?

Unfortunately the first two anonymization techniques aren't good enough and (as I want to show below) the last two can change the result. The issue is that in certain unusual circumstances, EPH can be highly unstable, so that the ordering in which even very weak nominees are eliminated can make a significant difference in who ends up included in the final ballot. It seems likely to me that this sort of instability wouldn't happen much in practice, but I don't know that; it's one of the things one would like to test with real data. And it's not possible to do that if anonymization has altered the data in a way that might eliminate any instabilities.

Specifically, consider the following scenario. It is the year 2025. Fandom has splintered into a sequence of factions, each 2/3 as numerous as the previous one in the sequence. The two remaining publishers, Geb and Roan, have remained scrupulously neutral and each publish only one book a year from the authors of each faction. Most Hugo voters nominate only the two books of their own faction, but a small fraction of voters (a consistent percentage of each faction, probably consisting of the publishers' employees) defect, and instead nominate two works of their favorite publisher, one from their own faction and one from the next larger faction. The defectors are equally split among the two publishers.

What happens if we use EPH to find the five top nominees? The algorithm eliminates nominees one at a time, roughly in order by faction strength. In the first round, one of the two candidates from the weakest faction will be eliminated, but in each round after that, the weakest remaining faction will have only one candidate left. If the second weakest remaining faction also has only one candidate, the one from the weakest faction is eliminated. But if the second weakest remaining faction still has both of its candidates, the division of points will cause these two candidates to be weaker than the single candidate of the weakest faction, so one of the two candidates from the second weakest faction will be eliminated. We repeat elimination steps of these types until finally the top two factions have both of their nominees still present, but the third faction has only one of its two. Which one? That depends...

If any one faction has its Geb candidate eliminated first, then the defectors from that faction will cause the Geb candidate for the next larger faction to be stronger, and the next larger faction will have its Roan candidate eliminated first. In the same way, if one faction has its Roan candidate eliminated first, then the next larger faction will have its Geb candidate eliminated first. And so the choice made in the first step, for the smallest faction, will echo through the process and change the result made in the final step, the one that determines which of the third-strongest faction's candidates makes it onto the final ballot.

Even though some candidates may be obvious losers, omitting them can change the overall outcome. In particular, if the strongest omitted candidate is the only one omitted from its faction, its publisher will determine the publisher of the third-faction choice in the final ballot. Additionally, the pattern of defector nominations in the balloting pattern described above would be strong enough to identify the defectors (possibly by name, if we have external information about who belongs to which faction and who works for each publisher) and to identify which nominated works are by which publisher. Any permutation of nominations among voters that is strong enough to provide anonymization against this sort of identification will also likely be strong enough to break the instability.

Does this potential instability in EPH indicate a flaw in the system? Maybe, but all voting systems have flaws. Any time two candidates are nearly tied and on the bubble for inclusion or elimination, small differences elsewhere in the input are likely to lead to big changes in the output. A little instability, unlikely to occur in practice, seems a small price to pay for the other nice properties of EPH. But the "unlikely to occur in practice" part is only my opinion, with little theory to back it up, and I think the only way to be sure is to test it on unaltered real data by omitting random subsets of obvious losers and seeing whether the results change.

The moral of the story seems to be that, if we ever do get safely-anonymized nomination data, it will only be because it has been rearranged to the point that we won't be able to do all the experiments we would like to on it. In particular it may be difficult to test whether the nomination results are unstable or stable. The alternative would be to make the data available only in a restricted way (either giving it to researchers who could be trusted to keep it confidential or keeping it entirely private and letting the researchers submit experiment code for the guardians of the data to run). Neither seems entirely satisfactory from the point of view of increasing our understanding of how well voting systems work on real world data, but privacy of voter data is more important and that may be the best we can do.

---

Comments: