# Linear ordering from weighted directed graph (kittens)

I want to build a website to find the cutest kitten(TM) there is. People can upload photos of their kittens, but also can vote on which kitten is the cutest. However, I don't want them to rate on a 1 to 10 scale, but kitten cuteness is relative to other kittens.

Every voter is presented with 3 kittens and needs to order them by cuteness using drag and drop.

From these votes I can compute a weighted cyclic graph with the kittens being nodes and the edges being number of votes

Is there an algorithm to approximate a (partial) linear ordering that takes transitive votes into account ? So one can put the kittens on a 1 to 10 scale after all ?

• You may want to check the Maximum Acyclic Subgraph problem (which has an easy 2-approximation) and the Minimum Feedback Arc Set problem, which is 3-approximated by a simple algorithm when the input is a tournament (dimacs.rutgers.edu/~alantha/papers2/aggregating_journal.pdf) Oct 7 '13 at 15:17
• BTW it was only a question of time before kittens made it to CSTheory :) Oct 7 '13 at 17:34
• this is similar to a scene from Social Network movie and the early history/birth of facebook, except images of college students were used.... so called "facemash" aka hot or not? there seems to be some possibility of using elo ratings. there it was done pairwise instead of with triplets.
– vzn
Oct 7 '13 at 18:54
• – vzn
Oct 7 '13 at 19:01
• vzn, thanks for the pointer to elo rankings, that (or glicko) fits my data structure better (so I can even compute it online). Oct 7 '13 at 20:59

Sorry for the brevity, maybe I can come back and expand later. There is work in voting and modeling voters that should be relevant. For example, take a model, i.e. in Mallows model, if A is truly cuter than B, then with probability $p > 0.5$ I rank $A$ ahead of $B$ and otherwise I rank B ahead of A. All rankings are made independently.

Then the corresponding voting rule is to compute the MLE underlying "true" ranking that generates the votes we've seen. For this particular model it is the Kemeny rule and it's NP-hard, but there are other models too.

...

(expansion) Condorcet in the 1700s first used the MLE idea. Say that every voter produces a ranking, and in that ranking any given pair of candidates are in the "correct" order with probability $p > 0.5$. Then, given a bunch of people's votes, we want to compute the single linear order that had the highest probability of generating those votes, the MLE. Young showed that the solution of this is the Kemeny voting rule, which minimizes the average bubblesort distance to all the rankings we are given.

Conitzer and Sandholm ('05) extended this idea to other voting rules, with other noise models (e.g. I put the best candidate in the $n$th place with probability $2^{-n}$).

Since then there's been work, e.g. by Xia and Conitzer (09), on extending these ideas to when people don't see the whole list of alternatives, but just get to see some of the alternatives (submit partial orders). This should be relevant to your setting, I think. There is also at least some empirical-type work in this vein. I am thinking specifically of Pfeiffer et al (12). The setting is basically the same as yours. They have some sort of adaptive strategy of which kitten pair (or whatever they used) to show to the next voter. The goal was to get a good ranking with fewer pairwise comparisons (i.e. not asking every voter to rank all the kittens).

That's what I know of the theoretical and AI work. There's also a lot of statistics that I know less about. Probably the stats will be most helpful if you want to actually implement something that aggregates partial rankings/observations.

I know that some of the most popular statistical models for these things are the Mallows model, Bradley-Terry, and Plackett-Luce. All of these are noise models for how voters randomly generate a ranking given the true underlying "correct" ranking. In fact, there is so much work about this going on in statistics that I might suggest you post on stats.se, because I am woefully ignorant but I think they (or perhaps the machine learning community as well) have a lot of work on algorithms for (approximately) finding solutions (e.g. the MLE) given a bunch of rankings and assuming that they were generated using one of these models. At least, I hope these keywords help you in your search!

• Yes, please expand on that. Even if it's just pointers. Thx! Oct 7 '13 at 20:10