Paths to Stability in Two-Sided Matching under Uncertainty

Monday, May 5, 2014, 4:00pm – 6:00pm
Presented by Emiliya Lazarova, and Dinko Dimitrov
Located in TBD
In track CoopMAS2014

In the present paper we re-visit the question whether an equilibrium outcome in the standard one-to-one, two-sided market can be reached in a decentralized manner when, realistically, the assumption of perfect information is removed. In our setup, market participants have preferences over the types of agents with whom they can be matched, but not over their identities. We keep information requirements to the minimum, that is, initially, players only know their own type, which is allowed to be independent of individual preferences. Thus, two agents of the same type may have di fferent preferences. Agents gather information about the type of their partners in the process of matching and thus, each player’s information set expands by matching with a new partner. We defi ne an outcome for such a two-sided matching problem under uncertainty to consist of a matching and a system of beliefs collecting each agent’s beliefs about the type of the agents from the opposite side of the market. We focus on outcomes where the system of beliefs is consistent with the process of learning via matching and where there are no further pro table deviations for any pair of players. Using these main ingredients of our setup, we address the question whether it is possible to reach a stable and consistent outcome from any initial self-consistent outcome, and answer it in the positive (Theorem 1). We then turn to the study of the links of a matching problem under uncertainty and the corresponding problem under complete information, where agents’ preferences over individuals in the latter follow their preferences over types in the former. We can readily show that the matching part of any stable and consistent outcome for the problem under uncertainty is a stable matching for the problem under complete information (Theorem 2). In order to connect, however, a stable matching for the latter problem to a stable and consistent outcome of the former, we need to take into account the way in which types are attributed to agents. If types are assigned as random independent draws from the set of types without replacement, then any stable matching under complete information is part of a stable and consistent outcome of the corresponding matching problem under uncertainty (Theorem 3). If, on the other hand, types are assigned to agents as random independent draws from the set of types with replacement, then two important features connecting the problem under uncertainty and its corresponding problem under complete information play a crucial role: (1) strict preferences over types do not imply strict preferences over potential partners any more, and (2) knowing the type of one partner is not informative about the probability with which other potential partners are ranked higher than the current one. We handle these issues by restricting our analysis to matching problems where agents of the same type have preferences which are dichotomously aligned, that is, we require for any two agents of the same type that the sets of their individually rational types as well as their top types coincide. Then, our nal result (Theorem 4) relates any stable matching for the problem under complete information to a homomorphic matching and a consistent system of beliefs for the problem under uncertainty, provided that agents’ preferences over types are dichotomously aligned. Here we de ne two matchings to be homomorphic if the number of same-type agents who are matched to a given type of agents on the other side of The market is equal in both matchings.