  Suppose that we have $n$ agents and $n$ items which lie in a shared metric
space. We would like to match the agents to items such that the total distance
from agents to their matched items is as small as possible. However, instead of
having direct access to distances in the metric, we only have each agent's
ranking of the items in order of distance. Given this limited information, what
is the minimum possible worst-case approximation ratio (known as the
distortion) that a matching mechanism can guarantee?
  Previous work by Caragiannis et al. proved that the (deterministic) Serial
Dictatorship mechanism has distortion at most $2^n - 1$. We improve this by
providing a simple deterministic mechanism that has distortion $O(n^2)$. We
also provide the first nontrivial lower bound on this problem, showing that any
matching mechanism (deterministic or randomized) must have worst-case
distortion $\Omega(\log n)$.
  In addition to these new bounds, we show that a large class of truthful
mechanisms derived from Deferred Acceptance all have worst-case distortion at
least $2^n - 1$, and we find an intriguing connection between thin matchings
(analogous to the well-known thin trees conjecture) and the distortion gap
between deterministic and randomized mechanisms.
