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

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.