<div dir="ltr"><div><div><div><div><div><div><div><div>Hi Kristofer,<br><br></div>There is a PR method based on Bucklin that could be used fairly easily on this problem.<br><br></div>See <a href="https://github.com/dodecatheon/graded-approval-transferable-vote">https://github.com/dodecatheon/graded-approval-transferable-vote</a><br>

<br></div>I'm currently working on a newer version but the basic version would give you a reasonable estimate.<br><br></div>In my newer version, all candidates are given a set of scores, and they are then sorted based on that set, using multiple key sorting.<br>

<br></div>My proposed set of scores would be to first use the average score, but only down to two-quotas from the top.  If those scores are tied, as they could well be if based on a coarse scoring system, the quota-threshold score is then used, and if that is tied, then the votes at or above the quota-threshold score.<br>

<br></div>The number of votes at or above the quota-threshold score are used to reweight ballots for the next round.  So in retrospect, calling it a transferable vote method is a bit of a misnomer, but the reweighting formula is very similar to the one used in STV.<br>

<br></div>With M candidates, there is an O(M) sort (or perhaps an O(M log M) sort) for each winner.  There is also the O(N) tally over all the ballots to accumulate the scores for each candidate, and this would be constant whatever M is.<br>

</div><div><br>Ted<br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Dec 3, 2013 at 4:49 AM, Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km_elmet@t-online.de" target="_blank">km_elmet@t-online.de</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Recently, I've been fiddling a bit with recommender systems, and I have noticed what is often a problem with these systems: they recommend very many things of the same sort.<br>


<br>
That is, if it detects that a person likes action movies, it may recommend a whole slate of them. This may even be correct in the respect that the user would like any randomly picked action movie ranked highly by the system more than the non-action movies that come later. But if he were to watch all of the movies from most recommended to least, he would grow tired very quickly.<br>


<br>
I noted that in political terms, this is similar to the cloning problem you get when using a good majoritarian method (say, Condorcet) to fill a council. If the majority-preferred candidate has many clones, then all of that candidate's clones will fill the council, because the method (correctly) judges that the majority prefers each clone to the other candidates.<br>


<br>
How can we deal with that in a political context? We can do so by using PR. And this suggests that one could also do something similar in a recommender system context.<br>
<br>
That is, consider a cosine distance system: "you're likely to like what others that liked what you did also like". Then each user has a weighted vote corresponding to the similarity of sets (how much he likes what you likes), and the recommender system works by running a weighted Approval or Range election.<br>


<br>
Which brings me to the point of my post (I tend to write long introductions!). In such systems you can easily have thousands or millions of "candidates". Which method should we choose if we want a PR election in order to provide diversity? The sheer number poses problems for many of the known systems.<br>


<br>
For one, because there are so many "candidates", most of them will be tied in a Plurality elimination stage like the one in STV. So elimination will be more or less random at first, until one gets down to sufficiently few candidates that the votes can accumulate. So ordinary STV doesn't seem to be all that good.<br>


<br>
So how about the virtual contest or combinatorial methods that avoid this problem? Both virtual contest methods (like Schulze STV or CPO-STV) and combinatorial methods (like PAV) don't scale well enough. And sequential ones (PRV, sequential PAV, etc) fail setwise election criteria.<br>


<br>
Thus my question: Can you think of any method that would work well in this setting?<br>
<br>
The only ones I can think of at the moment are STV-ME and a quadratic STV method I don't remember the details of. The former, by its "elimination election" by Condorcet among the losers, should have a greater chance of telling different zero-Plurality-votes candidates apart. And the quadratic STV method was a patch to STV that would let one use any positional method possible while still retaining the quota guarantees of STV. Again, that would make it easier to tell losers apart.<br>


<br>
There is of course the compromise solution of just using sequential PAV or proportional Range voting. In "worse-is-better" style, it wouldn't care very much about theoretical guarantees as long as the method is good enough. These sequential methods could also be brought closer to the combinatorial ones by considering chunks of k candidates at a time, with the greatest k that is still practical for the available processing power.<br>


----<br>
Election-Methods mailing list - see <a href="http://electorama.com/em" target="_blank">http://electorama.com/em</a> for list info<br>
</blockquote></div><br><br clear="all"><br>-- <br> Frango ut patefaciam -- I break so that I may reveal<br>
</div>