An improved 2-agent kidney exchange mechanism

We study a mechanism design version of matching computationin graphs that models the game played by hospitals participatingin pairwise kidney exchange programs. We present a new randomizedmatching mechanism for two agents which is truthful in expectation andhas an approximation ratio of 3/2 to the maximum cardinality matching.This is an improvement over a recent upper bound of 2 [Ashlagi et al., EC2010] and, furthermore, our mechanism beats for the first time the lowerbound on the approximation ratio of deterministic truthful mechanisms.We complement our positive result with new lower bounds. Among otherstatements, we prove that the weaker incentive compatibility propertyof truthfulness in expectation in our mechanism is necessary; universallytruthful mechanisms that have an inclusion-maximality property havean approximation ratio of at least 2.