  Motivated by kidney exchange, we study the following mechanism-design
problem: On a directed graph (of transplant compatibilities among patient-donor
pairs), the mechanism must select a simple path (a chain of transplantations)
starting at a distinguished vertex (an altruistic donor) such that the total
length of this path is as large as possible (a maximum number of patients
receive a kidney). However, the mechanism does not have direct access to the
graph. Instead, the vertices are partitioned over multiple players (hospitals),
and each player reports a subset of her vertices to the mechanism. In
particular, a player may strategically omit vertices to increase how many of
her vertices lie on the path returned by the mechanism.
  Our objective is to find mechanisms that limit incentives for such
manipulation while producing long paths. Unfortunately, in worst-case
instances, competing with the overall longest path is impossible while
incentivizing (approximate) truthfulness, i.e., requiring that hiding nodes
cannot increase a player's utility by more than a factor of $1 + o(1)$. We
therefore adopt a semi-random model where a small ($o(n)$) number of random
edges are added to worst-case instances. While it remains impossible for
truthful mechanisms to compete with the overall longest path, we give a
truthful mechanism that competes with a weaker but non-trivial benchmark: the
length of any path whose subpaths within each player have a minimum average
length. In fact, our mechanism satisfies even a stronger notion of
truthfulness, which we call matching-time incentive compatibility. This notion
of truthfulness requires that each player not only reports her nodes truthfully
but also does not stop the returned path at any of her nodes in order to divert
it to a continuation inside her own subgraph.
