Testing Preferential Domains Using Sampling
This work addresses the challenge of efficiently verifying preference structures in social choice theory, which is incremental as it builds on existing domain studies by introducing sample-based testing methods.
The paper tackles the problem of testing whether a preference profile is close to a specific preferential domain, such as single-peaked or single-crossing, by analyzing sample complexity under two closeness notions and random outlier assumptions. It shows that testing can often be done with high probability using a small number of samples independent of preferences and alternatives, with some cases requiring Ω(n) samples or being impossible.
A preferential domain is a collection of sets of preferences which are linear orders over a set of alternatives. These domains have been studied extensively in social choice theory due to both its practical importance and theoretical elegance. Examples of some extensively studied preferential domains include single peaked, single crossing, Euclidean, etc. In this paper, we study the sample complexity of testing whether a given preference profile is close to some specific domain. We consider two notions of closeness: (a) closeness via preferences, and (b) closeness via alternatives. We further explore the effect of assuming that the {\em outlier} preferences/alternatives to be random (instead of arbitrary) on the sample complexity of the testing problem. In most cases, we show that the above testing problem can be solved with high probability for all commonly used domains by observing only a small number of samples (independent of the number of preferences, $n$, and often the number of alternatives, $m$). In the remaining few cases, we prove either impossibility results or $Ω(n)$ lower bound on the sample complexity. We complement our theoretical findings with extensive simulations to figure out the actual constant factors of our asymptotic sample complexity bounds.