Azar Abizada at Rochester: Pairwise Stability for Assignment Problem with Budget Constraints
Abstract: We study assignment problem with fixed budget constraints. Examples include assigning students to graduate schools when colleges have fixed budget, a faculty member with a fixed research fund hiring research assistants, a manager assigning workers to different projects where each project has fixed total benefit, assigning post-doctoral candidates to universities with fixed budgets etc. In graduate college admissions, each college has a fixed amount of money to distribute as stipends. Each college has strict preferences overs individual students that can be extended to the group of students. On the other hand, each student is matched with at most one college and receives a stipend from it. Each student has quasi-linear preferences over college-stipend bundles.
Differently from earlier literature, in this paper, we specify a fixed budget for each college. One other different feature of our model is that colleges value money only to the extend that it allows them to enroll better students. We show that introducing budget constraint results in loosing some of the previous results in the literature. We define pairwise stability and show that a pairwise stable allocation always exists. We construct an algorithm. The rule defined through this algorithm always selects a pairwise stable allocation. This rule is also strategy-proof for students: no student can ever benefit from misrepresenting his preferences. Finally, we show that starting from an arbitrary allocation, there exist a sequence of allocations, each allocation being obtained from the previous one by "satisfying" a blocking pair, such that the final allocation is pairwise stable.
Gabriel Carroll at MIT: A General Equivalence Theorem for Allocation of Indivisible Objects
Abstract: We consider markets in which n indivisible objects are to be allocated to n agents. A number of recent papers studying such markets have shown various interesting equivalences between randomized mechanisms based on trading and randomized mechanisms based on serial dictatorship. We prove a very general equivalence theorem from which many previous equivalence results immediately follow, and we give several new applications. Our general result also sheds some light on why these equivalences hold by presenting the existing serial-dictatorship-based mechanisms as randomizations of a general mechanism which we call serial dictatorship in groups. The proof technique, a hybrid of explicit bijective and enumerative methods, is cleaner than previous bijective proofs.
Songzi Du at Stanford GSB: Unraveling and Chaos in Matching Markets, with Yair Livne. (Job Market Paper)
Abstract: This paper discusses the strategic manipulation of stable matching mechanisms. We find that the expected proportion of agents who may obtain a significant utility gain from manipulation vanishes as a market becomes large. This result reconciles the success of stable matching mechanisms in practice with the theoretical concerns about strategic manipulation. We also introduce new techniques from the theory of random bipartite graphs for the analysis of large matching markets.
Abstract: We study many-to-one matching problems with firm preferences that satisfy no complementarity and respect the absolute desirability of workers. We allow for randomization to achieve procedural fairness in centralized matching markets. Randomization is also a useful device to explore decentralized markets for lotteries may be considered to represent the frictions in these markets. We analyze stochastic dominance (sd) Nash equilibrium in the game induced by a random stable matching rule. We prove that a unique match is obtained as the outcome of each sd-Nash equilibrium. Individual rationality is a necessary and sufficient condition for an equilibrium outcome while stability is achieved as the outcome of an equilibrium where firms behave truthfully. We also study sd-Nash equilibrium of the game induced by a stable matching rule in many-to-many matching problems under the same domain of preferences. We show that all results but the stability of the equilibrium outcome holds in these problems. Our results provide an implementation of the individually rational correspondence when all agents are strategic and of the stable correspondence when only workers are strategic.