Stability and (Obviously) Strategy-proofness in Matching Theory

Abstract

We analyze stability and (obviously) strategy-proofness in two well-known models of matching theory, namely “assignment problem” (a one-sided matching model) and “marriage problem” (a two-sided matching model). • In assignment problem, a set of heterogeneous indivisible objects are to be allocated over a set of agents based on the agents’ preferences over the objects. Each agent can receive at most one object and monetary transfers are not allowed. Such problems arise when, for instance, the Government wants to assign houses to the citizens, or hospitals to doctors, or a manager wants to allocate offices to employees, or tasks to workers, or a professor wants to assign projects to students. Agents are asked to report their preferences over the objects and the designer decides the allocation based on these reports. • An instance of classical marriage problem involves n men and n women, each of whom specifies a preference over the members of the opposite sex. A matching μ is a set of (man, woman) pairs such that each person belongs to exactly one pair. If (m, w) ∈ μ, we say that w is m’s partner in μ, and vice versa, and we write μ(m) = w, μ(w) = m. Agents are asked to report their preferences and the designer decides the matching based on these reports. This thesis comprises of four chapters. A brief introduction of the chapters is provided below. In Chapter 2, we consider assignment problems where agents are to be assigned at most one indivisible object and monetary transfers are not allowed. We provide a characterization of assignment rules that are Pareto efficient, non-bossy, and implementable in obviously strategy-proof (OSP) mechanisms. As corollaries of our result, we obtain a characterization of OSP-implementable fixed priority top trading cycles (FPTTC) rules, hierarchical exchange rules, and trading cycles rules. Troyan (2019) provides a characterization of OSP-implementable FPTTC rules when there are equal number of agents and objects. Our result generalizes this for arbitrary values of those. In Chapter 3, we study the implementation of a fixed priority top trading cycles (FPTTC) rule via an obviously strategy-proof (OSP) mechanism (Li, 2017) in the context of assignment problems with outside options, where agents are to be assigned at most one indivisible object and monetary transfers are not allowed. In a model without outside options, Troyan (2019) gives a sufficient (but not necessary) and Mandal & Roy (2020) give a necessary and sufficient condition for an FPTTC rule to be OSPimplementable. This paper shows that in a model with outside options, the two conditions (in Troyan (2019) and Mandal & Roy (2020)) are equivalent for an FPTTC rule, and each of them is necessary and sufficient for an FPTTC rule to be OSP-implementable. In Chapter 4, we consider assignment problems where heterogeneous indivisible objects are to be assigned to agents so that each agent receives at most one object. Agents have single-peaked preferences over the objects. In this setting, first we show that there is no strategy-proof, non-bossy, Pareto efficient, and strongly pairwise reallocation-proof assignment rule on a minimally rich single-peaked domain when there are at least three agents and at least three objects in the market. Next, we characterize all strategyproof, Pareto efficient, top-envy-proof, non-bossy, and pairwise reallocation-proof assignment rules on a minimally rich single-peaked domain as hierarchical exchange rules. We additionally show that strategyproofness and non-bossiness together are equivalent to group strategy-proofness on a minimally rich single-peaked domain, and every hierarchical exchange rule satisfies group-wise reallocation-proofness on a minimally rich single-peaked domain. In Chapter 5, we provide a class of algorithms, called men-women proposing deferred acceptance (MWPDA) algorithms, that can produce all stable matchings at every preference profile for the marriage problem. Next, we provide an algorithm that produces a minimum regret stable matching at every preference profile. We also show that its outcome is always women-optimal in the set of all minimum regret stable matchings. Finally, we provide an algorithm that produces a stable matching with given sets of forced and forbidden pairs at every preference profile, whenever such a matching exists. As before, here too we show that the outcome of the said algorithm is women-optimal in the set of all stable matchings with given sets of forced and forbidden pairs.