Research
[To appear in the "New Directions in Market Design" NBER volume]
Abstract: Research on centralized school assignment mechanisms often focuses on whether parents who participate in specific mechanisms are likely to truthfully report their preferences or engage in various costly strategic behaviors. However, a growing literature suggests that parents may not know enough about the school options available to them to form complete preference rankings. We develop a simple model that explains why it is not surprising that many participants in school assignment mechanisms possess limited information about the schools available to them. We then discuss policies that could improve both the information that participants bring to school assignment mechanisms and the quality of the schools in their choice sets.
Abstract: We study matching markets with aligned preferences and establish a connection between common design objectives—stability, efficiency, and fairness and the theory of optimal transport. Optimal transport gives new insights into the structural properties of matchings obtained from pursuing these objectives, and into the trade-offs between different objectives. Matching markets with aligned preferences provide a tractable stylized model capturing supply-demand imbalances in a range of settings such as partnership formation, school choice, organ donor exchange, and markets with transferable utility where bargaining over transfers happens after a match is formed.
Abstract: We introduce a novel family of mechanisms for constrained allocation problems which we call local priority mechanisms. These mechanisms are parameterized by a function which assigns a set of agents -- the local compromisers -- to every infeasible allocation. The mechanism then greedily attempts to match agents with their top choices. Whenever it reaches an infeasible allocation, the local compromisers move to their next favorite alternative. Local priority mechanisms exist for any constraint so this provides a method of constructing new designs for any constrained allocation problem. We give axioms which characterize local priority mechanisms. Since constrained allocation includes many canonical problems as special constraints, we apply this characterisation to show that several well-known mechanisms, including deferred acceptance for school choice, top trading cycles for house allocation, and serial dictatorship can be understood as instances of local priority mechanisms. Other mechanisms, including the Boston mechanism, are not local priority mechanisms. We give sufficient conditions for a local priority mechanism to be group strategy-proof. We also provide conditions which enable welfare comparisons across local priority mechanisms.
A Topological Proof of The Gibbard-Satterthwaite Theorem (with Yuliy Baryshnikov) [arXiv] Economics Letters, January 2024 [Slides]
Abstract: We give a new proof of the Gibbard-Satterthwaite Theorem. We construct two topological spaces: one for the space of preference profiles and another for the space of outcomes. We show that social choice functions induce continuous mappings between the two spaces. By studying the properties of this mapping, we prove the theorem.
Royal Processions: Incentives, Efficiency and Fairness in Two-sided Matching (with Sophie Bade) [Slides]
[Presented at the 2023 ACM Conference on Economics and Computation][Extended Abstract for EC 2023]
Abstract: We study the set of incentive compatible and efficient two-sided matching mechanisms. We classify all such mechanisms under an additional assumption -- "gender-neutrality" -- which guarantees that the two sides be treated symmetrically. All group strategy-proof, efficient, and gender-neutral mechanisms are recursive and the outcome is decided in a sequence of rounds. In each round two agents are selected, one from each side. These agents are either "matched-by-default" or "unmatched-by-default." In the former case either of the selected agents can unilaterally force the other to match with them while in the latter case, they may only match together if both agree. In either case, if this pair of agents is not matched together, each gets their top choices among the set of remaining agents. As an important step in the characterization, we first show that in one-sided matching all group strategy-proof and efficient mechanisms are sequential dictatorships. An immediate corollary is that there are no individually rational, group strategy-proof and efficient one-sided matching mechanisms.
Efficiency in Random Resource Allocation and Social Choice (with Federico Echenique and Fedor Sandomirskiy)
Abstract: We study efficiency in general collective choice problems where agents have ordinal preferences and randomization is allowed. We explore the structure of preference profiles where ex-ante and ex-post efficiency coincide, offer a unifying perspective on the known results, and give several new characterizations. The results have implications for well-studied mechanisms including random serial dictatorship and a number of specific environments, including the dichotomous, single-peaked, and social choice domains.
7. Incentives and Efficiency in Constrained Allocation Mechanisms (with David Ahn) [Job Market Paper] [Video] [Slides]
[Winner of the young scholar award, International Conference on Social Choice and Voting]
Abstract: We study private-good allocation mechanisms where an arbitrary constraint delimits the set of feasible joint allocations. This generality provides a unified perspective over several prominent examples that can be parameterized as constraints in this model, including house allocation, roommate assignment, and social choice. We first characterize the set of two-agent strategy-proof and Pareto efficient mechanisms, showing that every mechanism is a "local dictatorship." For more than two agents, we leverage this result to provide a new characterization of group strategy-proofness. In particular, an N-agent mechanism is group strategy-proof if and only if all its two-agent marginal mechanisms (defined by holding fixed all but two agents' preferences) are individually strategy-proof and Pareto efficient. To illustrate their usefulness, we apply these results to the roommates problem to discover the novel finding that all group strategy-proof and Pareto efficient mechanisms are generalized serial dictatorships, a new class of mechanisms. Our results also yield a simple new proof of the Gibbard-Satterthwaite Theorem.
8. Stable Matching Under General Constraints
Abstract: This paper proposes a unified framework for studying two-sided matching problems with constraints. I introduce a matching algorithm called the constrained cumulative deferred acceptance algorithm capable of accommodating a wide variety of constraints. Like the deferred acceptance algorithm, one side of the market makes proposals to another. A "constraint correspondence" dynamically limits the choices of the receiving side in order to enforce that the ultimate match satisfies the constraint. If the constraint correspondence satisfies a "generalized substitutes" condition, the ultimate match will be constrained stable in the sense that satisfying any blocking pair would lead to a violation of the constraint. I provide two further conditions, "aggregate monotonicity" and "constraint IIA," on the constraint correspondence which ensure the constrained cumulative deferred acceptance algorithm implements a strategy-proof mechanism. Finally, I study the comparative statics of constraint correspondences.