Static and Dynamic Theoretical Studies on Improving Matching Design

This thesis consists of three independent papers on market design and matching theory. Each paper addresses a different matching model and environment, and together they represent a significant range of real-life matching problems which have not received enough attention. In the first paper, we consider a new matching model to assign agents and objects on two sides of the market to each other. The new feature is that agents have consecutive acceptance intervals which are based on an exogenously given commonly known ranking of the objects. Each agent finds acceptable a consecutive set of objects with respect to this objective common ranking of the objects. Each agent has an individual preference ranking of the objects in her acceptance interval, which is determined independently of the common ranking of the objects. The main objective is to find new matching rules (algorithms) which are simpler and more efficient than the complicated conventional general algorithms for achieving a maximum matching which is Pareto-optimal, exploiting the special structure of consecutive acceptance intervals which are a common feature of many real-life matching problems. Our main algorithm, the Block Serial Dictatorship Rule, starts with finding an ordering of agents based only on the acceptance interval structure and thus it is preference profile independent. This ordering is then used as a basis for a Serial Dictatorship which always finds a maximum Pareto-optimal matching, regardless of the agents’ preferences, for the solvable interval profiles that we characterize in the paper. These rules are also group strategy-proof. In the second paper, I consider a matching model with minimum quotas for one side of the market. The main objective is to find algorithms which respect minimum quotas and find matchings which are both nonwasteful and fair if there exists such a matching. Otherwise, the algorithms find either fair or nonwasteful matchings. My algorithms, CNWF and FCNW (constrained nonwasteful fair and fair constrained nonwasteful), start with finding the range of possible matchings when there are minimum quotas. Then, using an innovative graph, they select the matchings which are both fair and nonwasteful, and if there do not exist such matchings, CNWF selects a constrained nonwasteful matching with a maximum degree of fairness, and FCNW selects a fair matching with a maximum degree of nonwastefulness. Furthermore, I show that my algorithms are applicable to the case where there are different types of agents, which is a key factor for matching markets that are concerned with diversity. Compared to the existing algorithms my algorithms are unified and more intuitive. In the third paper, I consider a novel matching model in a dynamic environment. I define a dynamic environment in which the market is open for more than one period. At the beginning of each period new agents enter the market and the matched agents leave at the end. My model is motivated by couple match-making but the results apply to other similar matching markets as well. The main objective is to find an appropriate genderneutral algorithm with nice properties. I introduce a new algorithm which is based on the DA (Deferred Acceptance) algorithm and whose structure provides an opportunity to find two-sided optimal matchings, considering the requirements and characteristics of this dynamic marriage problem. The novel structure of my algorithm, DM (Dynamic Marriage), allows both sides to make offers simultaneously and selects a matching which is optimal for both sides in a realistic dynamic setup whenever such a matching exists, and otherwise the algorithm finds a matching without favouring either side. This property makes the matching fair in the sense that it gives both sides a fair chance. I also study the dynamic strategy-proofness of the algorithm, as well as its stability and efficiency properties. Compared to previous algorithms that apply to the marriage problem in a static or dynamic environment, my algorithm is more realistic since it allows for realistic dynamic preferences and for real-life marriage considerations. Furthermore, it is more integrated regarding the optimality of the two sides than other algorithms and avoids some of the common issues of dynamic algorithms