Optymalny system rekrutacji kandydatów do szkół

• Autorzy: Świtalski Z.

Warianty tytułu

EN

Optimal recruitment system of candidates to schools

• Języki publikacji: PL

Abstrakty

PL

W pracy uogólniono znany algorytm Gale’a–Shapleya [4] dotyczący optymalnego przydziału kandydatów do szkół. W klasycznym modelu G-S dany jest zbiór szkół S, zbiór kandydatów K, preferencje kandydatów w zbiorze S oraz preferencje szkół w zbiorze K (reprezentowane przez ostre liniowe porządki). Zakładamy, że każda szkoła posiada limit przyjęć q, tzn. q jest maksymalną liczbą kandydatów, którą ta szkoła może przyjąć. Chcemy przyporządkować kandydatów szkołom w taki sposób, aby był spełniony pewien warunek stabilności (zdefiniowany w pracy [4]). W podanym w pracy uogólnionym modelu preferencje szkół są reprezentowane przez tzw. „funkcje odrzuceń”. Wprowadzamy uogólniony warunek stabilności i formułujemy warunki, przy których uogólniony algorytm G-S prowadzi do rozwiązań stabilnych i optymalnych. Przedstawione wyniki można wykorzystać wykorzystane w praktyce, na przykład przy konstruowaniu komputerowych systemów rekrutacji, w których chcemy uwzględnić „miękkie” limity i „nieporównywalność” kandydatów

EN

We generalize a well–known Gale–Shapley algorithm [4] concerning optimal assignment of candidates for schools. In the classical Gale–Shapley model we consider a set of schools (colleges) S, a set of candidates K, candidates’ preferences in S and schools’ preferences in the set K (represented by strict linear orders). We assume that each school has a quota q, i.e., q is the maximal number of candidates which it can admit. We want to assign candidates for schools in such a way that some condition of stability (defined in [4]) is satisfied. In our generalized model schools’ preferences are represented by the so-called “rejection functions”. We introduce a generalized stability condition and formulate conditions under which the generalized G-S algorithm leads to stable and optimal assignments. Our results can be applied in practice, e.g. they can help in constructing computerized recruitment systems, in which we want to incorporate “soft” quotas and ties between candidates.

Słowa kluczowe

PL

system rekrutacji; zagadnienie skojarzenia dwustronne; algorytm Gale'a-Shapleya

EN

recruitment system; two-sided matching problem; Gale-Shapley algorithm

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2005
• Tom: nr 3-4
• Strony: 85--98
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Świtalski Z.

• Katedra Badań Operacyjnych, Akademia Ekonomiczna, al. Niepodległości 10, 60-967 Poznań,

Bibliografia

• [1] ALKAN A., GALE D., Stable schedule matching under revealed preference, Journal of Economic Theory, 2003, nr 112, s. 289–306.
• [2] BALINSKI M., SÖNMEZ T., A Tale of Two Mechanisms: Student Placement, Journal of Economic Theory, 1999, nr 84, s. 73–94.
• [3] EHLERS L., Monotonic and implementable solutions in generalized matching problems, Journal of Economic Theory, 2004, nr 114, s. 358–369.
• [4] GALE D., SHAPLEY S., College admissions and the stability of marriage, American Mathematical Monthly, 1962, nr 69, s. 9–15.
• [5] PAWŁOWSKI J., Żeby w wyniku naboru nikt nie poczuł się „nabrany”. Rodzicielskie refleksje po egzaminach do szkół średnich, Informatyka w szkole – Biuletyn Informacyjny, 31(2000), (www.vulcan.edu.pl/biuletyn).