This paper considers the problem of finding confidence sets of the parallelepiped type based on extreme order statistics for multivariate medians when no parametric assumptions are made. A partial characterization of a multivariate distribution which will minimize the probability of the specified parallelepiped covering the multivariate median is given. This characterization enables one to obtain a sharp lower bound for the probability of coverage, provided the number of medians does not exceed seven and under the assumption that the structure is independent of the sample size.