How to compare 2 predictive models where one uses predictor with missing values I am developing a model to predict y from a dataset (N=20,000) that contains x1, x2. 
Say I want to compare the models lm(y~x1+x2,data) with lm(y~x1,data).
Predictive accuracy is my goal so I decided to put them through a k-fold cross validation and measure the mean squared prediction error.
The problem is that x2 is only available on 20% of the entire dataset. So how would you fairly compare these models?
Would you just focus on the 20% of data? This seems wasteful to me.
 A: You will ultimately be limited by the 20% nonmissing data. 
MAB's solution will not offer a valid comparison, as you cannot calculate the model containing x2 for 80% of subjects- regardless of validation or derivation sets.
A: More experienced users might correct me on this - but throwing out cases (as some have mentioned) will produce unbiased estimates only if the data are missing completely at random (MCAR). I don't know if that's a reasonable assumption with your data. 
There are methods to impute or "fill in" missing data. Gelman and Hill (2006) pp. 529-545 has a good introduction to missing data with examples describing imputation methods.
A: Answer of fair comparison is in focusing on the question: Why you want to compare the two models ? The reason will justify how we can do a fair comparison.
Compare on just 20% if :
The purpose of comparison is to figure out which model is better when both x1 and x2 are available (ofcourse the assumption is that 20% is representative of the test data having both x1 and x2)
Compare on all 100% : 
if : you want to quantify the real-world-returns each model will give you on complete data which is expected to have data with x2 missing
by : defining the value of output as $n.d.$ for 80% cases (where you have no x2 available) and modifying the error function by assigning a value to ${y_{true} - n.d. }$ as some real-number/function which shows the impact a $n.d.$ will have on the real world application.
example : in case $y$ represents the stock market index and a $n.d.$ will mean you won't know the stock market movement for the next day and hence not invest money into it; incurring no loss and no profit you might want to assign a value $0$ to ${y_{true} - n.d. }$ as it doesn't affect you much. On the other hand if you are a stock trader by profession, not knowing a prediction might just be unacceptable to you in which case you can assign a VERY large value even +infinity to ${y_{true} - n.d. }$

$n.d.$ stands for not defined.
