  Private selection algorithms, such as the Exponential Mechanism, Noisy Max
and Sparse Vector, are used to select items (such as queries with large
answers) from a set of candidates, while controlling privacy leakage in the
underlying data. Such algorithms serve as building blocks for more complex
differentially private algorithms. In this paper we show that these algorithms
can release additional information related to the gaps between the selected
items and the other candidates for free (i.e., at no additional privacy cost).
This free gap information can improve the accuracy of certain follow-up
counting queries by up to 66%. We obtain these results from a careful privacy
analysis of these algorithms. Based on this analysis, we further propose novel
hybrid algorithms that can dynamically save additional privacy budget.
