We present the Multi-vAlue Rule Set (MARS) model for interpretable classification with feature efficient presentations. MARS introduces a more generalized form of association rules that allows multiple values in a condition. Rules of this form are more concise than traditional single-valued rules in capturing and describing patterns in data. MARS mitigates the problem of dealing with continuous features and high-cardinality categorical features faced by rule-based models. Our formulation also pursues a higher efficiency of feature utilization, which reduces the cognitive load to understand the decision process. We propose an efficient inference method for learning a maximum a posteriori model, incorporating theoretically grounded bounds to iteratively reduce the search space to improve search efficiency. Experiments with synthetic and real-world data demonstrate that MARS models have significantly smaller complexity and fewer features, providing better interpretability while being competitive in predictive accuracy. We conducted a usability study with human subjects and results show that MARS is the easiest to use compared with other competing rule-based models, in terms of the correct rate and response time. Overall, MARS introduces a new approach to rule-based models that balance accuracy and interpretability with feature-efficient representations.