Sesión Matemática Discreta

Diciembre 15, 15:50 ~ 16:10

ttRandom Path to Stability in a Decentralized Market with Contracts

Millán Guerra, Beatriz Alejandra

An essential point to consider in matching models is the stability of the outcomes. In this regard, significant progress has been achieved in centralized matching markets, where a central coordinating body produces stable matchings, generally by using deferred acceptance algorithms (Gale and Shapley (1962) defined the pioneering Deferred Acceptance Algorithm). In contrast, the functioning of decentralized markets is less known. This paper makes a contribution in this direction. Roth and Vande Vate (1990) noted that several decentralized markets work well, despite the lack of a central coordinating body. They hypothesized that some markets can reach stable matchings or allocations by means of decentralized decisions. A decentralized process can be modeled through a blocking path; i.e., a succession of allocations such that every allocation is obtained from the previous one by satisfying an unilateral or a bilateral block (an agent rules out unacceptable partners, or a pair of agents are assigned which possibly discards some less desired partners). For the one-to-one matching model, in which each agent can have one partner at the most, Kunth (1976) proved that the process of satisfying blocking pairs iteratively, starting from an arbitrary matching, does not necessarily lead to a stable outcome. Consequently, blocking paths in general may fail to converge to stable matchings. However, Roth and Vande Vate (1990) defined a path that converges to a stable outcome by satisfying a certain sequence of unilateral blocks and blocking pairs, starting from an arbitrary matching. In their proof, an algorithm is designed which successively introduces the agents, one at the time, into the system, and lets them satisfy blocking pairs at each stage by a decentralized system. For many-to-many matching models, Kojima and Unver (2008) showed the existence of a convergent blocking path when all agents on one side of the market have substitutable preferences and all agents in the other side have q-responsive preferences. The specific aim of this paper is to extend the previously mentioned work by providing a convergent blocking path for a many-to-many matching model where all agents on one side of the market have substitutable preferences and all agents in the other side have preferences satisfying law of aggregate demand (LAD) and q-concongruence, a condition that we introduce here. This is the first contribution of our paper. Another relevant aspect of our work is its contextualization in a many-to-many matching model with contracts. Since the matching without contracts models can be addressed as special cases of the matching with contracts models, we also extend the above-mentioned results in this direction.

Autores: Millán Guerra, Beatriz Alejandra / Pepa Risma, Eliana Beatriz.