  We study mechanism design problems in the {\em ordinal setting} wherein the
preferences of agents are described by orderings over outcomes, as opposed to
specific numerical values associated with them. This setting is relevant when
agents can compare outcomes, but aren't able to evaluate precise utilities for
them. Such a situation arises in diverse contexts including voting and matching
markets.
  Our paper addresses two issues that arise in ordinal mechanism design. To
design social welfare maximizing mechanisms, one needs to be able to
quantitatively measure the welfare of an outcome which is not clear in the
ordinal setting. Second, since the impossibility results of Gibbard and
Satterthwaite~\cite{Gibbard73,Satterthwaite75} force one to move to randomized
mechanisms, one needs a more nuanced notion of truthfulness.
  We propose {\em rank approximation} as a metric for measuring the quality of
an outcome, which allows us to evaluate mechanisms based on worst-case
performance, and {\em lex-truthfulness} as a notion of truthfulness for
randomized ordinal mechanisms. Lex-truthfulness is stronger than notions
studied in the literature, and yet flexible enough to admit a rich class of
mechanisms {\em circumventing classical impossibility results}. We demonstrate
the usefulness of the above notions by devising lex-truthful mechanisms
achieving good rank-approximation factors, both in the general ordinal setting,
as well as structured settings such as {\em (one-sided) matching markets}, and
its generalizations, {\em matroid} and {\em scheduling} markets.
