The objective of this paper is to briefly review house allocation problems. We first give the definition and the aim of the mechanism design theory. Next we discuss its applications to markets with no monetary transfer, such as house allocation, kidney exchange and school choice. We review the literature for (i) house allocation problems, (ii) house allocation problems with existing tenants, and (iii) house allocation problems with existing tenants and newcomers.
Keywords:Mechanism design, Game theory, House allocation, Housing market, Matching, Random serial dictatorship.
Received: 23 May 2017 / Revised: 17 July 2017/ Accepted: 28 July 2017 / Published: : 7 August 2017
The paper’s primary contribution is to review important studies about the house allocation problems. It covers three different versions of these problems, standard house allocation problems, with existing tenants, and with existing tenants and newcomers.
Mechanism design has witnessed considerable interest among researchers especially the last three decades. Numerous articles have been published about the theory of mechanism design and its applications to many fields such as economics, business, finance, computer science, political science, or psychology. In fact, 2007 Nobel Prize in economic sciences was awarded to Leonid Hurwicz, Eric Maskin, and Roger Myerson for their contributions to the theory of mechanism design and 2012 Nobel Prize was awarded to Alvin E. Roth and Lloyd S. Shapley for their contributions to the theory of stable allocations and the practice of market design.
Mechanism design is a subfield of microeconomics and game theory. It is the design of mechanisms or institutions to achieve desired outcomes in strategic settings. Game Theory also deals with strategic interactions among the agents. The difference is that while game theory concerns predicting the outcomes of the strategic interactions, mechanism design concerns designing the games or systems to achieve the desired outcomes.
Mechanism design is employed in case of a strategic interaction among individuals who possess private information relevant for decision making. Individuals behave strategically and are affected either positively or negatively by the decisions of the others. Therefore, the objective is to design a mechanism in which individuals behave in a self-interested manner and do not have any incentive to misrepresent their true private information so that desired outcome is achieved at the end of the game.
The first contributions of this field are Hurwicz (1960) and Hurwicz (1972). They introduced the idea of “incentive compatibility” to the literature. A mechanism is incentive compatible if each individual can achieve his/her best outcome by declaring his/her true preferences. When there is asymmetric information in a strategic setting, then incentive compatibility is a crucial concept. Another important concept for mechanism design is “revelation principle” which states that to find the best mechanism there is no loss of generality if we focus on only the set direct mechanisms satisfying incentive compatibility. Dasgupta et al. (1979) and Myerson (1979) introduce this principle and later it is developed by Myerson (1982;1986) and Myerson and Satterthwaite (1983).
Later on, mechanism design became the root of many applications of economics. In this paper, we will only consider a subset of these and focus on markets in which monetary compensations are not possible because of legal and ethical considerations. We provide a brief survey of the mechanism designs concerning the following markets: (i) house allocation, (ii) house allocation with existing tenants, and (iii) house allocation with existing tenants and newcomers.
The reminder of the paper is organized as follows. Section 2 introduces and reviews important contributions for house allocation models. In Section 3, we review house allocation problems with existing tenants and in Section 4, we review papers which also allow newcomers.
House allocation problems are introduced by Hylland and Zeckhauser (1979). Briefly, a house allocation problem is a triple; a set of houses, a group of agents, and their strict preferences over houses. There is a central planner who collects preference information from agents and then depending on the preferences, assigns each agent a house. Therefore, the outcome of a house allocation problem is a matching which is a one-to-one and onto function from the set of agents to the set of houses. A mechanism assigns a matching to each house allocation problem.
There are many real life applications of this model, for example, allocation of dormitory rooms to students, allocation of offices or parking space among workers and assigning students to schools. In all these applications, agents have preferences over the houses (dorm rooms, schools, etc.) and monetary transformations are not possible.
The most common mechanism for these problems is random serial dictatorship. This mechanism randomly chooses an order of agents. The first agent is matched with his most preferred house, and then second agent is matched with his most preferred house among the remaining houses and so on. This mechanism is used in many real life applications; allocation of offices or parking space among professors, NYC school choice system, Harvard housing allocation system.
Random serial dictatorship mechanism satisfies many desirable properties. First of all, it is very easy to implement. In addition, Svensson (1994) shows that it satisfies Pareto efficiency and strategy proofness. Thus, if this mechanism is used in the allocation, agents do not have any incentive to misrepresent their true preferences and there is no other mechanism which makes each agent better off without making someone worse off. The problem is that Random serial dictatorship is not the only mechanism that satisfies Pareto efficiency and strategy proofness. However, Abdulkadiroğlu and Sönmez (1998) show that for any Pareto-efficient matching of a given problem, there exists a serial dictatorship that achieves this matching. Also, Svensson (1999) shows that random serial dictatorship mechanism is the only mechanism that is strategy proof, nonbossy and neutral. A mechanism is neutral if an agent can change the outcome of the mechanism only if he can change the allocation for himself at the same time. A mechanism is neutral if the outcome is independent of the names of the agents.
Ehlers (2002) analyzes house allocation problems in which agents may not have strict preferences for the houses. He discusses some interesting real life examples in which agents have not enough information about each house and as a result they are indifferent between some of them. However, he shows that if weak preferences are allowed, then Pareto efficiency and coalitional strategy proofness are not compatible. Therefore, he proposes a maximal domain of preferences including the strict preferences so that these two properties are compatible. In fact, in this domain he proved that mixed dictator pairwise exchange rules are the only rules satisfying Pareto efficiency and coalitional strategy proofness together.
There are some extensions of the house allocation problems. One of the problems with the simple house allocation model is that it does not consider the case where each agent already owns a house. House allocation model with existing tenants, simply housing market has been introduced to the literature by Shapley and Scarf (1974). This model is actually an exchange market and agents can change their house to get better ones or they can continue to keep them. They show that there exists a core matching for any housing market. In addition, Roth and Postlewaite (1977) prove that the matching produced by Gale’s Top Trading Cycle mechanism is the unique core matching. Thus, they show that this mechanism coincides with the competitive mechanism. According to this mechanism, in the first step, each agent points to his most preferred house and each house points to its initial owner. Then, all the cycles are removed by assigning each agent in the cycle the house he points to. If there is at least one agent and one house, we continue with the next step. A detailed discussion of Gale’s Top Trading Cycle mechanism is provided by Gale and Shapley (1962).
Roth (1982) shows that Gale’s Top Trading Cycle mechanism is strategy proof. Another characterization of this mechanism is by Ma (1994) who shows that it is the only mechanism satisfying strategy proofness, Pareto efficiency and individual rationality.
Jaramillo and Manjunath (2012) extend this result by allowing indifferences between the houses. In their model, the agents may not have strict preferences over the houses, so some of the agents can be indifferent between the houses. They show that each mechanism in the family of Top Cycle Rules, which are the generalization of Gale’s Top Trading Cycle mechanism, satisfies Pareto efficiency and strategy proofness and it chooses a matching from the Core.
Abdulkadiroğlu and Sönmez (1998) relate house allocation models with housing markets. They propose core from random endowments mechanism which chooses a random endowment matching for a given house allocation problem and then chooses the core of the induced housing market. They show that this mechanism is equivalent to random serial dictatorship mechanism of the house allocation models.
Abdulkadiroğlu and Sönmez (1999) is a generalized model of both the house allocation problems and the housing market. Some of agents are existing tenants and some of them are newcomers. In addition to occupied houses, there are also some vacant houses. Each agent has strict preferences over the houses. When all agents are existing tenants and when there is no vacant house, the model reduces to the housing market. If all the agents are newcomers, then the model reduces to the house allocation problems.
In most of the real life applications, agents have to move from their house before assigning a new house. However, there is no guarantee for getting a better house, so they prefer not to change their house. In fact, in that case, the matching induced by random serial dictatorship mechanism may not be Pareto efficient. Therefore, they allow existing tenants to stay in their house and at the same time, to participate in the matching. They propose a class of mechanisms which guarantee a house which is at least as good as their own house to the existing tenants. Top trading cycles mechanism first chooses a priority ordering for the agents. The agent with the top priority gets his most preferred house and then the second agent gets his most preferred house among the remaining houses. This continues until one agent wants to get a house of an existing tenant. If that existing tenant has already assigned a house, they proceed the assignment to next agent. Otherwise, the existing tenant becomes the top of priority order and the algorithm continues. If there is cycle in some step, then the cycle is removed by letting agents exchange their house. Top trading cycle mechanism reduces to the random serial dictatorship mechanism when all the agents are newcomers and to the Gale’s top trading cycle mechanism when all agents are existing tenants and there is no vacant house.
Abdulkadiroğlu and Sönmez (1999) show that this mechanism is individually rational, Pareto efficient, and strategy proof. Individual rationality is important here because it guarantees the existing tenants a house which is at least as good as their own house. In addition, they show that it is the only mechanism satisfying these desirable properties as well as weak neutrality and consistency when the population is variable. However, their top trading cycle mechanism is not only mechanism that satisfies those properties.
Sönmez and Ünver (2010) fully characterize this mechanism which is also named as You Request My House- I Get Your Turn mechanism. They show that it is the unique mechanism that satisfies individual rationality, Pareto efficiency, strategy proofness, and also weak neutrality and consistency. A mechanism is weak neutral if the names or labels of the vacant houses cannot change the induced matching. Consistency is about variable population. If some of the agents leave the market with their assigned houses, this property relates the matching induced in the initial problem to the one induced after the departure of those agents.
Kurino (2014) introduces a dynamic model of house allocation problems. The idea behind the dynamic model is that a newcomer agent becomes an existing tenant next year. He introduces a seniority based dynamic rule by using the static serial dictatorship and top trading cycle rules and he shows that it satisfies dynamic Pareto efficiency and incentive compatibility.
In this paper, we reviewed some important contributions of mechanism design for the house allocation problems in the literature. There are many real life applications of these problems including the assignment of dorm rooms to students, offices to professors, public houses to agents or parking spaces to workers. Several approaches to these problems exist in the literature. The first part of the present article focused on house allocation problems in which agents do not have any endowment. The second section reviewed the applications which include settings with existing tenants. Finally, we considered a more general domain in which there are vacant houses, existing tenants and also newcomers.
| Funding: This study received no specific financial support. |
| Competing Interests: The authors declare that they have no competing interests. |
| Contributors/Acknowledgement: Both authors contributed equally to the conception and design of the study. |
Abdulkadiro ğlu, A. and T. Sönmez, 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3): 689-701. View at Google Scholar | View at Publisher
Abdulkadiro ğlu, A. and T. Sönmez, 1999. House allocation with existing tenants. Journal of Economic Theory, 88(2): 233-260. View at Google Scholar | View at Publisher
Dasgupta, P., P. Hammond and E. Maskin, 1979. The implementation of social choice rules: Some general results on incentive compatibility. Review of Economic Studies, 46(2): 185-216. View at Google Scholar | View at Publisher
Ehlers, L., 2002. Coalitional strategy-proof house allocation. Journal of Economic Theory, 105(2): 298-317.View at Google Scholar | View at Publisher
Gale, D. and L. Shapley, 1962. College admissions and the stability of marriage. American Mathematical Monthly, 69(1): 9-15. View at Google Scholar | View at Publisher
Hurwicz, L., 1960. Optimality and informational efficiency in resource allocation processes, mathematical methods in the social sciences, edited by Arrow. Karlin and Suppes: Stanford University Press.
Hurwicz, L., 1972. On Informationally decentralized systems, decision and organization. Edited by C.B. McGuire and R. Radner. North Holland: Amsterdam.
Hylland, A. and R. Zeckhauser, 1979. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2): 293-314. View at Google Scholar | View at Publisher
Jaramillo, P. and V. Manjunath, 2012. The difference indifference makes in strategy-proof allocation of objects. Journal of Economic Theory, 147(5): 1913-1946. View at Google Scholar | View at Publisher
Kurino, M., 2014. House allocation with overlapping generations. American Economic Journal: Microeconomics, 6(1): 258-289. View at Google Scholar
Ma, J., 1994. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory, 23(1): 75-83. View at Google Scholar | View at Publisher
Myerson, R., 1979. Incentive compatibility and the bargaining problem. Econometrica, 47(1): 61-73.View at Google Scholar | View at Publisher
Myerson, R., 1982. Optimal coordination mechanisms in generalized principal agent problems. Journal of Mathematical Economics, 10(1): 67-81. View at Google Scholar | View at Publisher
Myerson, R., 1986. Multistage games with communication. Econometrica, 54(2): 323-358. View at Google Scholar | View at Publisher
Myerson, R. and M. Satterthwaite, 1983. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2): 265-281. View at Google Scholar
Roth, A.E., 1982. Incentive compatibility in a market with indivisibles. Economics Letters, 9(2): 127-132. View at Google Scholar | View at Publisher
Roth, A.E. and A. Postlewaite, 1977. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2): 131-137. View at Google Scholar | View at Publisher
Shapley, L. and H. Scarf, 1974. On cores and indivisibility. Journal of Mathematical Economics, 1(1): 23-37. View at Google Scholar | View at Publisher
Sönmez, T. and M.U. Ünver, 2010. House allocation with existing tenants: A characterization. Games and Economic Behavior, 69(2): 425-445. View at Google Scholar | View at Publisher
Svensson, L.G., 1994. Queue allocation of indivisible goods. Social Choice and Welfare, 11(4): 323-330.View at Google Scholar | View at Publisher
Svensson, L.G., 1999. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4): 557-567. View at Google Scholar