O kojarzeniu małżeństw i rejestracji kandydatów na studia cz.2 :: Artykuły / Polski Serwis Naukowy

Polecamy również:

Trwa coroczne badanie opinii i preferencji studentów kierunków ekonomicznych

Warsztaty nt. testowania opartego na modelu, Pafos, Cypr

Pierwsze warsztaty nt. interoperacyjności bazującej na modelu, Oslo, Norwegia

44. Szkoła Matematyki Poglądowej w Sulejowie

Zbliża się XLVI Szkoła Matematyki Poglądowej

Nowa kolekcja i nagroda dla modelu z poprzedniej linii Casio Exilim na Photokina 2008

Rozwój teorii stabilnych kojarzeń

Artykuł Gale'a i Schapley'a zapoczątkował burzliwy rozwój teorii i zastosowań modelu dwustronnych skojarzeń.

Badania teoretyczne można podzielić na dwa nurty:
(i) Nurt pierwszy obejmuje analize własności podstawowego modelu Gale'a i Schapley'a, szukanie jego powiązań z różnymi działami matematyki i analiza różnych modyfikacji algorytmu GS (lub innych algorytmów prowadzących do stabilnych skojarzeń).
(ii) Nurt drugi zajmuje się analizą różnych uogólnień podstawowego modelu GS (np. modyfikowane są założenia o preferencjach, limitach itd.).

Do nurtu pierwszego można zaliczyć badanie struktury zbioru skojarzeń stabilnych w modelu GS. W zbiorze tym można wyprowadzić dwa naturalne porządki (skojarzenie s jest lepsze od skojarzenia t, jeśli zachodzi

lub

drugi porządek definiowany jest tak samo, ale uwzględniamy mężczyzn). Można się zastanawiać nad liczbą skojarzeń stabilnych w modelu GS. Załóżmy, że mamy n kobiet i m mężczyzn i chcemy określić minimalną i maksymalną liczbę skojarzeń stabilnych przy różnych układach preferencji. Minimalna liczba jest równa 1 (jeśli na przykład wszystkie kobiety lub wszyscy mężczyźni mają te same preferencje, to algorytm GS daje to samo rozwiązanie zarówno dla kobiet jak i dla mężczyzn i jest to jedyne rozwiązanie stabilne). Nie wiadomo natomiast w jaki sposób zależy od n maksymalna liczba skojarzeń stabilnych.

Ważną własnością rozwiązania Gale'a-Schapley'a jest tzw. niemanipulowalność (strategy-proofness). Załóżmy, że mamy zbiór kandydatów

i zbór szkół

oraz układ preferencji kandydatów i szkół.
$P=(P(K_1),\ldots,P(K_n),P(S_1),\ldots,P(S_n))$
Załóżmy też, że określona jest jakaś metoda przyporządkowująca każdemu układowi preferencji

skojarzenie s(P)

. Metoda ta jest manipulowalna, jeśli dla pewnego kandydata K_i

istnieją preferencje $P^\prime(K_i) \neq P(K_i)$ i takie, że:

$[s(P^\prime)(K_i)] >_i [s(P)(K_i)]$

gdzie $P^\prime$ jest układem powstałym z

przez zastąpienie P(K_i)

przez $P^\prime(K_i)$ . Wzór ten oznacza, że szkoła, w której znalazł się kandydat K_i

przy preferencjach $P^\prime$ jest lepsza (w sensie preferencji P(K_i)

) od szkoły, w której znalazłby się on przy preferencjach

.

Interpretacja manipulowalności jest następująca. Zakładamy, że kandydat K_i

ma jakieś "prawdziwe'' preferencje P(K_i)

. Podając preferencje P(K_i)

kandydat (przy założeniu, że wszyscy inni kandydaci podają preferencje z układu

) zostaje umieszczony w szkole s(P)(K_i)

. Kandydat K_i

może jednak spróbować podać "fałszywe'' preferencje $P^\prime(K_i)$ licząc na to, że skorzysta dzięki temu i znajdzie się w szkole lepszej niż s(P)(K_i)

a mianowicie w szkole $s(P^\prime)(K_i)$ (lepszej z punktu widzenia ,,prawdziwych'' preferencji P(K_i)

). Jeśli jakiś system rekrutacji dopuszczałby taką sytuację, to oznaczałoby to możliwość manipulowania preferencjami przez kandydatów (niektórzy z nich mogliby podawać nieprawdziwe preferencje po to aby znaleźć się w lepszej szkole od tej, w której mogliby się znaleźć podając swoje rzeczywiste preferencje). Chcielibyśmy aby dobry system rekrutacji był w tym sensie niemanipulowalny. okazuje się, że metoda GS jest niemanipulowalna. Jest to jednak niemanipulowalność tylko z punktu widzenia jednej strony (a więc jeśli kandydaci nie mogą manipulować, to szkoły mogą i na odwrót).

W nurcie drugim mieści się wiele prac poświęconych różnym uogólnieniom metody GS np. zamiast preferencji w postaci liniowych porządków możemy dopuszczać w modelu preferencje uwzględniające równoważności między kandydatami.
Inne uogólnienia otrzymamy jeśli uwzględnimy konieczność wspólnego przyjmowania par małżeńskich lub dolne limity przyjmowania kandydatów.

Autor: Dawid Dembek*

*Autor jest studentem V roku zastosowań matematyki Wydziału Matematyki i Informatyki Uniwersytetu Mikołaja Kopernika w Toruniu.

komentuj publikację

Czy wiesz że...?

wersja BETA

Preferencje (ang. preference) są podstawowym pojęciem w teorii ekonomii oraz w mikroekonomii, szczególnie w teorii wyboru konsumenta i w teorii gier. Preferencje konsumenta odzwierciedlają i formalizują gusty konsumenta i nie zależą w żaden sposób od cen dóbr lub budżetu konsumenta, lecz wyłącznie od zadowolenia, satysfakcji, szczęścia lub użyteczności jakie mu zapewniają. Preferencje pozwalają konsumentowi dokonywać wyborów w obliczu rozmaitych alternatyw. pełny tekst

Twierdzenie o kojarzeniu małżeństw (twierdzenie Halla) przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane w roku 1935. Jest ono często ilustrowane poprzez przedstawienie następującego problemu: pełny tekst

Na stronie Pomoc:Personalizacja opisane jest jakie możliwości daje oprogramowanie MediaWiki w dostosowywaniu Wikipedii do własnych potrzeb. Pytaniem podstawowym jest jak to wykorzystać. Najprostsze jest przejście na stronę Specjalna:Preferencje i ustawienie tam paru opcji. To jednak nic w porównaniu z tym jakie możliwości daje posiadanie własnego arkusza stylów (plik CSS), a przede wszystkim własnego JavaScriptu (plik JS). pełny tekst

MBTI, czyli Myers-Briggs Type Indicator wskaźnik psychologiczny, służący do określenia typu osobowości. Jest rozszerzoną koncepcją Carla Gustava Junga, który zaobserwował, że osoby mają określone preferencje co do kierowania swojej energii i "ładowania baterii", sposobu zbierania informacji i podejmowania decyzji. W ten sposób określił on 8 typów osobowości. Isabel Briggs Myers i Katherine Cook Briggs rozwinęły pomysł Junga dotyczący hierarchii poszczególnych preferencji w każdym typie osobowości i dodały wymiar opisujący nastawienie do świata zewnętrznego. W ten sposób powstał uniwersalny 4 literowy kod opisujący dany typ psychologiczny, z którym co roku zapoznaje się ponad 2 miliony nowych osób. Kod ten powstaje poprzez wybór jednej preferencji z każdego z 4 poniższych wymiarów: pełny tekst

Rozdzielczość tonalna rejestracji- Rozdzielczość tonalna świadczy o zdolności układu rejestracji do reprodukcji zmian intensywności w rejestrowanym obrazie, a więc do wierności odwzorowania walorów obrazu. W przypadku rejestracji przy pomocy materiałów halogenosrebrowych trudno jest mówić o tym parametrze ze względu na bezstopniowość reprodukcji tonalnej tej metody rejestracji (a więc charakterze reprodukcji naturalnym dla widzenia człowieka). Rozdzielczość tonalna będzie natomiast kluczowa dla systemów cyfrowej rejestracji obrazu, gdzie sygnał intensywnościowy jest kwantowany. pełny tekst

Moduł "Czy wiesz że...?" (wersja testowa, beta): definicje/pojęcia wygenerowane w obrębie tego modułu pochodzą z Wikipedii i udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Dostęp do pełnej wersji każdego hasła (oraz dokładnch informacji na temat licencji, autora oraz edycji) możliwy jest po kliknięciu w odnośnik opisany jako "pełny tekst".