Graduate admission problem with quota and budget constraints

Abstract

Bu tez çalışmasında kota ve bütçe kısıtları altında doktora kabul problemi iki taraflı eşleşme olarak incelenmiştir. Gale - Shapley algoritmasının uzantıları olan çeşitli algoritmalar yazılmış ve bu algoritmalardan biri için algoritma durursa oluşan eşleşmenin çekirdek kararlı (ve böylece Pareto en iyi) olduğu gösterilmiştir. Fakat bu algoritmalar bazı problemler için durmadığı gibi, algoritmaların dur madığı ve çekirdek kararlı bir eşleşmenin bulunduğu durumlar da mevcuttur. Ayrıca bütçe kısıtı altında bölüm optimal eşleşme ve öğrenci optimal eşleşme yoktur. Bu yüzden Gale - Shapley algoritmasının uzantıları olan algoritmalar kota ve bütçe kısıtları altında doktora kabul problemi için kendilerinden bekle nen işlevi yerine getirmemektedir. Bütçe kısıtmm varlığı bu sonuçlarda önemli bir rol oynamaktadır. Anahtar sözcükler: ikili kararlı eşleşme, çekirdek kararlı eşleşme, Pareto en iyi eşleşme, Gale - Shapley algoritması, kota ve bütçe kısıtları.

In this thesis, we have studied the graduate admission problem with quota and budget constraints as a two sided matching market. We constructed algorithms which are extensions of the Gale - Shapley algorithm and showed that if the algorithms stop then the resulting matchings are core stable (and thus Pareto optimal). However the algorithms may not stop for some problems. Also it is possible that the algorithms do not stop and there is a core stable matching. Also there is no department optimal matching and no student optimal matching under budget constraints. Hence straightforward extensions of the Gale - Shapley algorithm do not work for the graduate admission problem with quota and budget constraints. The presence of budget constraints play an important role in these results. Keywords: pairwise stable matching, core stable matching, Pareto optimal match ing, the Gale - Shapley algorithm, quota and budget constraints.