As you like it: Localization via paired comparisons

Suppose that we wish to estimate a vector x from a set of binary paired comparisons of the form "x is closer to p than to q" for various choices of vectors p and q. The problem of estimating x from this type of observation arises in a variety of contexts, including nonmetric multidimensional scaling, "unfolding," and ranking problems, often because it provides a powerful and flexible model of preference. We describe theoretical bounds for how well we can expect to estimate x under a randomized model for p and q. We also present results for the case where the comparisons are noisy and subject to some degree of error. Additionally, we show that under a randomized model for p and q, a suitable number of binary paired comparisons yield a stable embedding of the space of target vectors. Finally, we also show that we can achieve significant gains by adaptively changing the distribution for choosing p and q.