Lone Wolf Theorem for One-Sided Matching Problems with Outside Option

Year 2018, Volume: 73 Issue: 4, 1169 - 1176, 23.11.2018

Duygu Nizamoğulları

https://doi.org/10.1501/SBFder_0000002530

Abstract

In this paper, we study one-sided matching problems (so-called roommate problems) with the outside option. In the classical roommate problems, remaining single is conceived as the outside option. However, there are many real life applications where this is not the case. We study roommate problems in which the outside option is defined as having no room. In this general framework, we discuss the generalization of so-called "Lonely Wolf Theorem" which states that any agent who is single in one stable matching is single in all other stable matchings. In this study, we show that for the general model with outside option Lonely Wolf Theorem still holds. 

Keywords

Roommate Problems, Individual Rationality, Outside Option, Capacity Constraint, Lone Wolf Theorem

Dış Mekan Seçeneğinin Olduğu Tek Taraflı Eşleşme Problemlerinde Lone Wolf Teoremi

Abstract

Bu makalede dış mekan seceneğinin olduğu tek taraflı eşleşme problemlerini (oda arkadaşı problemlerini) çalışıyoruz. Klasik oda arkadaşı problemlerinde yalnız kalmak dış mekan seçeneği olarak
tasarlanmıştır. Ancak, durumun böyle olmadığı birçok uygulama vardır. Biz dış mekan seçeneğinin hiçbir odaya sahip olmamak olarak tanımlandığı oda arkadaşı problemlerini çalışıyoruz. Bu genel çerçevede "Lone Wolf Teoremi" olarak adlandırılan teoremin genelleştirilmesini ele alıyoruz. Bu teorem, durağan bir eşleşmede yalnız kalan bir kişinin diğer tüm durağan eşleşmelerde de yalnız kaldığını belirtir. Bu çalışmada, dış mekan seçeneğinin olduğu genel modelde Lone Wolf Teorem' in hala geçerli olduğunu gösteriyoruz. 

Keywords

Ev Arkadaşı Problemleri, Bireysel Rasyonellik, Dış Mekan Seçeneği, Kapasite Kısıtı, Lone Wolf Teoremi

References

• Referans 1 Abraham, David J., Peter Biró and David F. Manlove (2006), ""Almost stable" matchings in the roommate problem," In: Erlebach, T., Persiano, G. (Eds.), Proceedings of WAOA2005.