  Algorithmic Mechanism Design attempts to marry computation and incentives,
mainly by leveraging monetary transfers between designer and selfish agents
involved. This is principally because in absence of money, very little can be
done to enforce truthfulness. However, in certain applications, money is
unavailable, morally unacceptable or might simply be at odds with the objective
of the mechanism. For example, in Combinatorial Auctions (CAs), the
paradigmatic problem of the area, we aim at solutions of maximum social welfare
but still charge the society to ensure truthfulness. Additionally, truthfulness
of CAs is poorly understood already in the case in which bidders happen to be
interested in only two different sets of goods.
  We focus on the design of incentive-compatible CAs without money in the
general setting of $k$-minded bidders. We trade monetary transfers with the
observation that the mechanism can detect certain lies of the bidders: i.e., we
study truthful CAs with verification and without money. We prove a
characterization of truthful mechanisms, which makes an interesting parallel
with the well-understood case of CAs with money for single-minded bidders. We
then give a host of upper bounds on the approximation ratio obtained by either
deterministic or randomized truthful mechanisms when the sets and valuations
are private knowledge of the bidders. (Most of these mechanisms run in
polynomial time and return solutions with (nearly) best possible approximation
guarantees.) We complement these positive results with a number of lower bounds
(some of which are essentially tight) that hold in the easier case of public
sets. We thus provide an almost complete picture of truthfully approximating
CAs in this general setting with multi-dimensional bidders.
