An analysis of a real-life allocation problem

Abstract

Sabanc¬ Üniversitesi Yurt Osinin (SÜYO) kar¸s¬la¸st¬¼g¬ bir gerçek hayat problemini in-celedik. Her sene SÜYO (i) yurt yataklar¬n¬ ba¸svuranlar aras¬nda da¼g¬t¬yor ve (ii) herbir oday¬ payla¸sacak oda arkada¸slar¬n¬ belirliyor. Da¼g¬t¬m k¬sm¬ için kullan¬lan kural¬ in-celedik ve gösterdik ki bu kural Pareto verimlilik, strateji korunumluluk ve mazur göster-ilemez öykünüm özelliklerini sa¼glam¬yor. Kural¬n bu eksikliklerini gidermek için, çok iyibilinen dizisel diktatörlük kural¬n¬ de¼gi¸stirerek uygulad¬k. Daha sonra, SÜYO taraf¬ndanoda arkada¸s¬ k¬sm¬ için kullan¬lan kural¬ inceledik ve bu kural¬n ise karars¬z ve Pareto ver-imsiz e¸sle¸smeler üretti¼gini tespit ettik. Bu eksiklikleri yok etmek için kuralda de¼gi¸siklikleryapt¬k. Bunlardan ba¸ska, her bir ajan¬n üç tane oda arkada¸s¬ oldu¼gu yeni bir tür oda arkada¸s¬problemi ortaya koyduk. Ayr¬ca, bu yeni tür oda arkada¸s¬ problemi için kararl¬ e¸sle¸smelerinvarl¬¼g¬n¬ sa¼glayacak çe¸sitli ko¸sullar öne sürdük.Anahtar Sözcükler: Da¼g¬t¬m problemi, mazur gösterilebilir öykünüm, oda arkada¸s¬problemi, kararl¬l¬k

We consider a real-life problemfaced by the Sabanc¬ University Dormitory O¢ce (SUDO).Every year SUDO (i) allocates the dormitory beds among applicants and then (ii) determinesthe roommates that will share each room. For the allocation part, we examine the allocationrule that is currently used and we show that it does not satisfy Pareto e¢ciency, strategy-proofness and justied no envy. To eliminate these shortcomings, we introduce a modiedversion of the well-known serial dictatorship rule. We then analyze the roommate assign-ment rule that is currently used by SUDO. We determine that this rule also has seriousshortcomings such as producing unstable and Pareto ine¢cient matchings. We then modifythe rule to eliminate these failures. Moreover, we introduce a new kind of roommate problemin which each agent has three roommates. We then obtain some conditions which guaranteethe existence of a stable matching for this kind of roommate problem.Keywords: Allocation problem, justied envy, roommate problem, stability