Exchange stability: An analysis of the roommate problem in the presence of room scarcity

Abstract

Bu makalede takas istikrarı, oda kısıtı bulunan oda arkadaşı problemleri için incelenmektedir. Takas istikrarı, Gale ve Shapley (1962) tarafından tanımlanan istikrar ve Morrill (2007) tarafından önerilen Pareto optimum ile kıyaslandığında problemin çözümü için daha uygun bir özellik olduğu görülmektedir. Bu makalede takas istikrarını sağlayan eşleşmelerin kümesinin boş küme olabileceği gösterilmiştir. Ayrıca bu kümenin Pareto optimum eşleşmelerinin kümesinin alt kümesi olduğu kanıtlanmıştır. Kanıtlanan önemli sonuçlardan biri ise takas istikrarı ve tutarlılık hakkında bir imkansızlık sonucudur. Buna göre takas istikrarını sağlayan eşleşmelerin kümesinin boş küme olmadığı durumlarda bu küme ile örtüşen ve aynı zamanda tutarlı bir çözüm yoktur. Bunun yanı sıra Gale-Shapley istikrarı ve takas istikrarının bağımsız olduğu kanıtlanmıştır. Bu durum Gale-Shapley istikrarını sağlayan eşleşmelerin bulunması için kullanılan algoritmaların takas istikrarını sağlayan çözümleri bulmada kullanılamayacağını vurgular. Ayrıca, oda arkadaşı probleminin özel bir durumu olan evlilik problemi için bir eşleşmenin hem Gale-Shapley istikrarını ve takas istikrarını sağlaması için gerekli koşullar belirtilmiştir.

This paper analyzes exchange stability for the roommate problem under the restriction that the rooms are in a scarce supply. While the central axioms in matching problems are Gale-Shapley stability (Gale and Shapley, 1962) and Pareto optimality, recently a new property, exchange stability is proposed. We demonstrate that the set of exchange stable matchings, which can be empty, is a subset of Pareto optimal matchings. We also prove an impossibility result that there is no well-defined solution which coincides with the set of exchange stable matchings whenever it is non-empty and satisfies consistency. Moreover, we show that Gale-Shapley stability and exchange stability are independent concepts, thus, algorithms to find Gale-Shapley stable solutions cannot be used for identifying exchange stable solutions. In addition, a necessary condition for a matching to satisfy both Gale-Shapley stability and exchange stability is found for the marriage problem, which is a special case of the roommate problem.