  We explore the performance of polynomial-time incentive-compatible mechanisms
in single-crossing domains. Single-crossing domains were extensively studied in
the economics literature. Roughly speaking, a domain is single crossing if
monotonicity characterizes incentive compatibility. That is, single-crossing
domains are the standard mathematical formulation of domains that are
informally known as ``single parameter''. In all major single-crossing domains
studied so far (e.g., welfare maximization in various auctions with
single-minded bidders, makespan minimization on related machines), the
performance of the best polynomial-time incentive-compatible mechanisms matches
the performance of the best polynomial-time non-incentive-compatible
algorithms. Our two main results make progress in understanding the power of
incentive-compatible polynomial-time mechanisms in single-crossing domains:
  We provide the first proof of a gap in the power of polynomial-time
incentive-compatible mechanisms and polynomial-time non-incentive-compatible
algorithms: we present an objective function in a single-crossing multi-unit
auction for which there is a polynomial-time algorithm that provides an
approximation ratio of $\frac{1}{2}$, yet no polynomial-time
incentive-compatible mechanism provides a finite approximation (under standard
computational complexity assumptions).
  The objective function used above is not natural. We show that to some extent
this is unavoidable by providing a sweeping positive result for the most
natural objective function in multi-unit auctions, that of welfare
maximization. We present an incentive-compatible FPTAS mechanism for every
multi-unit auction with single-crossing domains. This improves over the
mechanism of Briest et al. [STOC'05] that only applies to the much simpler case
of single-minded bidders.
