Papers on matching by job market candidates

Matching is popular on the economics job market this year, including interesting papers from students other than mine. Here are a few that caught my attention (please let me know of those I've missed).

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: We show that the timing of transactions is difficult to coordinate in large matching markets. In our model, some agents have the option of matching early before others arrive. Even with a market mechanism that implements a stable matching after all agents arrive, and without any discounting or risk aversion, some agents have incentives to match early. We show that as the market gets large, on average approximately one quarter of all agents have strict incentives to match early, independent of the underlying distributions of types and utility functions. Moreover, as the market gets large, with probability tending to 1 there is no dynamic matching scheme that is stable, even though the market would be stable if it was static.

SangMok Lee at Cal Tech: Incentive Compatibility of Large Centralized Matching Markets
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.

Taro Kumano at Washington U.  Stability and Efficiency in the General-Priority-based Assignment (2011), [joint with Aytek Erdil], Preliminary draft

Abstract: A school choice problem is a priority-based assignment problem. A priority ranking of a school in practice inherently exhibits indifference relations among the subsets of the set of students. We introduce a general class of priority rankings over sets of students, which captures both indifferences and substitutability. Our notion of substitutability ensures the existence of stable assignments. The characterization of efficient priority structures implies that there is usually a conflict between efficiency and stability. Thus we turn to the problem of finding a constrained efficient assignment, and give an algorithm which solves the problem for any priority structure that falls in our class. In an important application, school priorities that care about affirmative action can be captured by our model, but not previous models in the literature.

Ayse Yazici from Rochester:  Random stable rules and Nash Equilibrium in  two-sided matching problems
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.