We prove an elementary property of order statistics that bounds the k-th largest order statistic of a given sample using the largest order statistic of a (random) subsample. This property is applied to the design of com- binatorial auctions when the auctioneer has limited statistical information about the joint distribution of the bidders’ valuations. The VCG mechanism is asymptotically optimal—its revenue-guarantee differs from the highest revenue-guarantee by at most O(1/n).