UC Berkeley

In this dissertation, I study the properties of and propose the use of a family of random mechanisms for a large class of problems where agents need to be matched to objects or to each other without the use of monetary transfers.

In the first chapter, I study the problem of kidney exchange under strict ordinal preferences and with constraints on the length of the trading cycles. The requirement of individual rationality in this setting incentivizes patient-donor pairs who are compatible with each other to participate in the kidney exchange, thus increasing the match rate for incompatible pairs. I show that deterministic mechanisms have poor properties in this environment. Instead, I explicitly define an individually rational, efficient and fair random mechanism for the case of pairwise kidney exchange. Finally, I show that individual rationality, efficiency and weak strategyproofness are incompatible for the cycle-constrained case making the proposed mechanism, called the 2-Cycle Probabilistic Serial (2CPS) mechanism, a second-best mechanism.

In the second chapter, I extend the idea behind the 2CPS mechanism to arrive at a constrained efficient mechanism for a general matching environment and regardless of what the ex-post constraints on the outcome are, including individual rationality, limits on the cycle lengths, maximizing the number of proposed matches etc. Several mechanisms from the existing literature are special cases of this mechanism, called the Generalized Constrained Probabilistic Serial (GCPS) mechanism.

In the final chapter, I consider two natural notions of strategyproofness in random matching mechanisms based on ordinal preferences. The two notions are stronger than weak strategyproofness but weaker than strategyproofness. I demonstrate that the two notions are equivalent and provide a geometric characterization of the new intermediate property which I call convex strategyproofness. I then show that the probabilistic serial mechanism (a special case of the GCPS mechanism) is, in fact, convexly strategyproof. I finish by showing that the property of weak envy-freeness of the random serial dictatorship can be strengthened in an analogous manner.