# Linear least squares with unordered response variable

In the classical linear regression model one considers the equation $$y = X \beta + \epsilon.$$ I was wondering whether there are also results when the ordering of the response variable $y$ is not given, i.e. $y$ is not a vector $(y_1, y_2, \dots, y_n)$ but rather a set $\{y_1, y_2, \dots, y_n\}$.

Would there be efficient ways of estimating $\beta$ ? I suppose there also have to be conditions on $X$ that this is even possible in the noiseless case.

The noiseless case, i.e. $\epsilon = 0$: The condition on $X$ is that the pairs $(X_i, Y_{\pi(i)})$ lie on a single hyperplane for some permutation $\pi$ of $1,\ldots, n$. In dimension 1 this is easy to check, just sort the $X$ and the $Y$. Since you can sort ascending or descending, there is no unique solution unless $\beta$ is zero. In higher dimensions a straightforward attack would be to check linear dependence of the pairs for each possible permutation. Of course this gets cumbersome in practice if $n$ is larger than 9 or 10. Hence an important factor in assessing "efficiency" of the solution is the size of $n$ and the number of factors $p$.
The case with noise: I think here you really need to specify what you want from a solution and what your criterion for efficiency is. Each permutation of the $Y$ is a standard least squares problem and after solving those you will have (in general) $n!$ different solutions for $\beta$. Depending on your estimation problem, you might want to choose the average of those, or that value of $\beta$ which gives you the lowest estimated $R^2$ or variance of $\epsilon$ or something else entirely. From what you say I do not see a single clear criterion for an estimate of $\beta$.
Anyway, due to the permutations involved, I guess the problem will become quickly harder for growing numbers of $n$.