Bachelor Thesis from the year 2009 in the subject Economics - Other, grade: 5.0, University of Zurich (Sozialökonomisches Institut (SOI)), language: English, abstract: Matching is the part of economics that deals with the question of who gets what, e.g. who gets which jobs, who goes to which university, who receives which organ or who marries whom. During the second part of the last century, many markets have been discovered to have failed in providing the necessary conditions for efficient matches. These market failures have partly evolved on ethical or institutional grounds, but are more generally attributed to congestion or coordination problems caused by the inability of the market to make it safe for participants to act on their private information. For this reason, a variety of allocation mechanisms have been developed and subsequently tested in field and laboratory experiments for possible implementation in real-world applications. This work attempts at giving a condensed review of different matching mechanisms and the performance of algorithms that have been implemented for solving the problems in their respective environments. The theoretical properties of these mechanisms as described in the increasingly vast literature on matching design will be used as a benchmark to compare their relative performance in terms of overall efficiency. The results yield some basic insights in the varying success of the competing algorithms in practice, indicating that both the quality of theoretical predictions and the actual performance of the algorithms decrease with the complexity of market environments. In particular, they show that imperfections of markets such as information asymmetry and incentive problems can have far-reaching consequences with respect to the effective working of matching procedures.

While most college admission markets are decentralized, the United Kingdom, home to one of the most prestigious markets for higher education, operates a centralized system. The thesis at hand analyses the efficiency of the match this system generates and its main determinants. The efficiency is found to be surprisingly high given the fact that the system for matching student and colleges deviates greatly from what has been identified to be optimal in theory. While the matching mechanism does in theory exhibit substantial flaws, these do not substantially affect the outcome in practice as students and colleges act highly rational and hereby ensure the functioning of the market.

The Social Cloud framework leverages existing relationships between members of a social network for the exchange of resources. This thesis focuses on the design of coordination mechanisms to address two challenges in this scenario. In the first part, user participation incentives are studied. In the second part, heuristics for two-sided matching-based resource allocation are designed and evaluated.

Criteria for evaluating school choice mechanisms are first, whether truth-telling is sometimes punished and second, how efficient the match is. With common knowledge preferences, Deferred Acceptance (DA) dominates the Boston mechanism by the first criterion and is ambiguously ranked by the second. Our laboratory experiments confirm this. A new ex ante perspective, where preferences are private information, introduces new efficiency costs borne by strategy-proof mechanisms, like DA. In a symmetric environment, truth-telling can be an equilibrium under Boston, and Boston can first-order stochastically dominate DA in terms of efficiency, both in theory and in the laboratory.

When several two-sided matching markets merge into one, it is inevitable that some agents will become worse off if the matching mechanism used is stable. I formalize this observation by defining the property of integration monotonicity, which requires that every agent becomes better off after any number of matching markets merge. Integration monotonicity is also incompatible with the weaker efficiency property of Pareto optimality.Nevertheless, I obtain two possibility results. First, stable matching mechanisms never hurt more than one-half of the society after the integration of several matching markets occurs. Second, in random matching markets there are positive expected gains from integration for both sides of the market, which I quantify.

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.