World's most popular travel blog for travel bloggers.

[Answers] Rating elements via partial orders

, , No Comments
Problem Detail: 

I would like to rate a set of $n$ elements, with each element assigned a rating from ${0,\dots, 10}$.

The way in which I want to rate is by repeatedly selecting subsets of $k$ elements and querying a user to rank them relative to each other. I would like a means of minimizing the number of necessary queries to assign ratings (i.e. "how do I pick which elements I should ask about?"), and a way of aggregating my partial orders into the appropriate buckets ("when do I stop, and how do I map the partial order into my range?").

Are there any decent references I should be looking at?

Asked By : Julian

Answered By : Francesco Gramano

What you're essentially asking is to find a total ordering of a graph of users whose partial orderings are results of querying a user for their relative rank. Your asymptotic complexity of the minimum necessary number of partial orders will relate to the Stirling number of the Second Kind To find this total ordering (re: "how do I map the partial order into my range?") you would topologically sort the graph you're describing. Note that for every vertex, $u\leq_p v\Rightarrow (u,v) \in E$, and the graph would be directed.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback