15 Aug 2003 Bram   » (Master)

Trust Metrics

I think I've figured out how to fix the gameability problems I've talked about in the last few entries.

Water pours in at a fixed rate from the seed. At any given time, each node is either trying to collect water, done collecting water and now dispensing it, or done dispensing water and simply passing it through. When a node is dispensing water it will do so at a rate depending on the amount of water flowing into it.

We will construct a schedule of what water goes where when. For each node which is trying to collect water, we ask 'if all dispensing nodes were to allocate their full amount to this node, when would it be full?' The node which does so the fastest gets added first, and all the dispensation of the nodes which certify it gets allocated up until the time. When deciding on later nodes to add, it is assumed that dispensers don't start contributing until after their previously allocated contributions are done.

Note that when a node is first added its rate of dispensation is zero. When all of the nodes which a dispenser certifies have been added, then that node's rate of dispensation is distributed evenly across all the nodes it certifies. Dead ends are skipped over, to avoid water wastage. More sophisticated forms of backlogging indirect dead ends could be made, but the simplest one should work fine in practice.

I'm very enamored of this technique. It does accurate proportional representation and is very hard to game outside of the gameability inherent in having proportional representation at all. My one current gripe is that while the technique for selecting which node gets added next is linear on the number of nodes, the technique for redistributing the dispensation of full peers is quadratic. Harumph.

To see the gameability inherent in proportional representation, consider this case: There are three voters, who will elect three candidates. Two voters prefer A, B, and C, while the third one prefers A, B, and D. Clearly the winners should be A, B, and C, but the third voter can list simply D and get exactly the candidates he wants elected.

Election Methods

On a related subject, I've for a long time been thinking about improvements to single transferable vote. There is a form of gameability of STV which I think can be completely overcome. Specifically, a voter can make their vote much stronger by taking a candidate who has no hope of winning and ranking them first. This causes very bad distortions, including the occasional candidate with no hope who actually wins!

My modification is surprisingly simple. The first winner is selected by the condorcet method. Later candidates are elected one at a time using essentially the condorcet method but with the pairwise results modified based on previous winners. Specifically, if we're comparing candidates A and B, then if X was already elected we take all candidates who ranked X above both A and B and evenly distribute a reduction in their vote strength by a total of the droop quota.

I did some testing of this and found (assuming I didn't botch up my implementation) that when using minimax there are circumstances in which the weight of a vote becomes negative. I suspect this stops happening if you use ranked pairs instead.

This technique completely obliterates the rank-a-weak-candidate-higher form of gaming which plagues STV. It also has the nice feature of not requiring all votes to be kept around. All you need to do is collate the vote counts of each two- and three-way race and the winners can be calculated from that.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!