Prediction of an order of vectors using partially ordered set How to order a set of vectors $W$ if we are given a training set $V$ consisting of $k$ $n$-dimensional vectors and partial order of them? It is not the total order, so some vectors might not be comparable with some other. The answer will depend on assumptions, so feel free to make any reasonable assumptions.
Example
Let: $k=4$ and $n=2$
$v_{1}=(1,2)$
$v_{2}=(5,8)$
$v_{3}=(4,3)$
$v_{4}=(9,6)$
We know that $v_{1}<v_{3}$, $v_{2}<v_{4}$ and $v_{3}<v_{4}$
Vectors that we want to order are following:
$w_{1} = (2,6)$
$w_{2} = (7,4)$
$w_{3} = (5,5)$  
The most intuitive order is $w_{1}<w_{3}<w_{2}$, because it seems that the first attribute is the most important.
 A: This problem is identical with the problem of "learning to rank (LTR)" in the field of Machine Learning and IR. LTR focuses on how to rank the web pages according a given query. So, your problem is same as LTR's. Now, many approaches have been applied to address this problem. These approaches can be categorized into three directions: 1. point-wise approach, that is treat the ranking problem as a regression or classification problem (similar with the approaches proposed as linear transformation.). 2. pair-wise approach, as described by @GaBorgulya, the state-of-art model is RankSVM, which works well for this task. 3. List-wise approach, treating the list as whole, performing permutation (as I guss), then find a best ranking.
I'm lazy man, you can easily ask for google to search "Learning to Rank", and also the Yahoo conducts a context about this field last year. You will find more technique and theory papers for this task.  
A: In the example if we order the vectors according to the first attribute the three pairwise comparisons will be satisfied. This is the same solution as what you suggested in your last sentence. Why aren't you satisfied with this solution? Do you have any further information on the problem? 
A: If you can find some mapping from $R^N \rightarrow R^M$ where $R^M$ is some space with a nice distance measure (e.g. euclidean) then you could determine ordering based off of distance. For example, suppose you were very lucky and could find a mapping to $R^1$, then you could just use the scalar value as the index (which is essentially a hash function).
There are many approaches to actually solving for that mapping (e.g. you could train a multi-layer perceptron). You might also find something simple like PCA could work if there are only a few dimensions that play an important role in ordering.
