6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A ha, thanks for the perspective, that certainly seems like it puts me on the right track (if you care, if you leave that as a response I'll mark it as accepted :), otherwise gonna give this a shot and see if it produces the results I want. Appreciated! $\endgroup$ – Julian Feb 22 '15 at 22:53
2
$\begingroup$

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 mathworld.wolfram.com/StirlingNumberoftheSecondKind.html. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.