When facing uncertainty, decision-makers want predictions they can trust. A\nmachine learning provider can convey confidence to decision-makers by\nguaranteeing their predictions are distribution calibrated -- amongst the\ninputs that receive a predicted class probabilities vector $q$, the actual\ndistribution over classes is $q$. For multi-class prediction problems, however,\nachieving distribution calibration tends to be infeasible, requiring sample\ncomplexity exponential in the number of classes $C$. In this work, we introduce\na new notion -- \\emph{decision calibration} -- that requires the predicted\ndistribution and true distribution to be ``indistinguishable'' to a set of\ndownstream decision-makers. When all possible decision makers are under\nconsideration, decision calibration is the same as distribution calibration.\nHowever, when we only consider decision makers choosing between a bounded\nnumber of actions (e.g. polynomial in $C$), our main result shows that\ndecisions calibration becomes feasible -- we design a recalibration algorithm\nthat requires sample complexity polynomial in the number of actions and the\nnumber of classes. We validate our recalibration algorithm empirically:\ncompared to existing methods, decision calibration improves decision-making on\nskin lesion and ImageNet classification with modern neural network predictors.\n