  In most social choice settings, the participating agents express their
preferences over the different alternatives in the form of linear orderings.
While this clearly simplifies preference elicitation, it inevitably leads to
poor performance with respect to optimizing a cardinal objective, such as the
social welfare, since the values of the agents remain virtually unknown. This
loss in performance because of lack of information is measured by the notion of
distortion. A recent array of works put forward the agenda of designing
mechanisms that learn the values of the agents for a small number of
alternatives via queries, and use this limited extra information to make
better-informed decisions, thus improving distortion. Following this agenda, in
this work we focus on a class of combinatorial problems that includes most
well-known matching problems and several of their generalizations, such as
One-Sided Matching, Two-Sided Matching, General Graph Matching, and
$k$-Constrained Resource Allocation. We design two-query mechanisms that
achieve the best-possible worst-case distortion in terms of social welfare, and
outperform the best-possible expected distortion achieved by randomized ordinal
mechanisms.
