Essays in matching and cost sharing problems.

摘要

This thesis is a collection of essays on matching and cost sharing problems. In chapter 1, we study decentralized matching processes in which agents make offers to one another directly. By observing these offers, each agent gathers information about other agents' preferences, which may lead him/her to update his/her preferences. We formulate and explore intuitive conditions on updating in terms of "when" and "how" to update. Then, we study the implications of updating on a "natural" matching process related to the deferred acceptance algorithm (Gale and Shapley, 1962). We consider separately the effects of updating for proposers and receivers. We show that if updating satisfies some of the above mentioned conditions, the matching may not be stable with respect to the last preference profile. We introduce processes that recover stability. When proposers update, we present two ways to modify the decentralized deferred acceptance algorithm. The main feature of these processes is that they allow agents to withdraw some offers in order to propose to other agents. When receivers update, we propose a, process that allows them to resolve their blocking pairs, but without completely altering the roles of proposers and receivers.;In chapter 2, we study the problem of allocating objects among people. We consider cases where each object is initially owned by someone, no object is initially owned by anyone, and combinations of the two. The problems we look at are those where each person has a need for exactly one object and initially owns at most one object (also known as "house allocation with existing tenants"). We split with most of the existing literature on this topic by dropping the assumption that people can always strictly rank the objects. We show that, without this assumption, problems in which either some or all of the objects are not initially owned are equivalent to problems where each object is initially owned by someone. Thus, it suffices to study problems of the latter type. We ask if there are efficient rules that provide incentives for each person not only to participate (rather than stay home with what he owns), but also to state his preferences honestly. Our main contribution is to show that the answer is positive. The intuitive "top trading cycles" algorithm provides such a rule for environments where people are never indifferent Ma (1994). Our solution is a generalization of this algorithm that allows for indifference without compromising on efficiency and incentives.;In Chapter 3, we consider a problem in which the cost of building an irrigation canal has to be divided among a set of people. Each person has different needs. When the needs of two or more people overlap there is congestion. In problems without congestion, a unique canal serves all the people and it is enough to finance the cost of the largest need to accommodate all the other needs. In contrast, when congestion is considered, more than one canal might need to be built and each canal has to be financed. In problems without congestion, axioms related with fairness and group participation constraints are generally compatible. With congestion, we show that these two axioms are incompatible. We define weaker axioms of fairness and group participation constraints that in conjunction with a few other axioms characterize the sequential contributions family of rules. Moreover, when we include a new axiom we characterize a subfamily of rules. Finally, we adapt some other properties to the problem with congestion and study which of the rules we define satisfy these axioms.