Essays on real life allocation problems

In the first chapter, we introduce a new matching model to mimic inter-college tuition exchange programs for dependents of faculty to attend other colleges tuition-free. Each participating college has to avoid being a net-exporter of students. Programs use decentralized markets making it difficult to achieve balance. We show that stable equilibria discourage net-exporting colleges from exchange. We introduce two-sided top-trading-cycles (2S-TTC) mechanism that is balanced-efficient, student-strategy-proof, and respecting priority bylaws regarding dependent eligibility. Moreover, it encourages exchange, since full participation is dominant strategy for colleges. We prove 2S-TTC is the unique mechanism fulfilling these objectives and introduce new student-strategy-proof mechanisms to achieve other objectives. In the second chapter, we consider a house allocation with existing tenants model in which each transaction is costly for the central authority, a housing office. We compare two widely studied mechanisms, deferred acceptance (DA) and top trading cycles (TTC), based on their costs for the housing offices. A mechanism in which more existing tenants are assigned to their current house is preferred for the housing offices due to the costs of moving. We show that although there is no dominance between the two mechanisms, DA has more desirable features in terms of the cost efficiency for the housing offices. Then we include the welfare of the housing office in the welfare analysis and redefine the Pareto efficiency notion. We show that every fair matching is Pareto efficient. Based on the extended Pareto efficiency definition, the DA mechanism is the unique Pareto efficient, fair, and strategy-proof mechanism. Finally, the third chapter characterizes the top trading cycles mechanism for the school choice problem. Schools may have multiple available seats to be assigned to students. For each school a strict priority ordering of students is determined by the school district. Each student has strict preference over the schools. We first define weaker forms of fairness, consistency and resource monotonicity. We show that the top trading cycles mechanism is the unique Pareto efficient and strategy-proof mechanism that satisfies the weaker forms of fairness, consistency and resource monotonicity. To our knowledge this is the first axiomatic approach to the top trading cycles mechanism in the school choice problem where schools have a capacity greater than one.