• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • O kojarzeniu małżeństw i rejestracji kandydatów na studia cz.2

    11.12.2009. 16:55
    opublikowane przez: Przemysaw Szydzik

    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ół.

    Załóżmy też, że określona jest jakaś metoda przyporządkowująca każdemu układowi preferencji skojarzenie . Metoda ta jest manipulowalna, jeśli dla pewnego kandydata istnieją preferencje i takie, że:

    gdzie jest układem powstałym z przez zastąpienie przez . Wzór ten oznacza, że szkoła, w której znalazł się kandydat przy preferencjach jest lepsza (w sensie preferencji ) od szkoły, w której znalazłby się on przy preferencjach .

    Interpretacja manipulowalności jest następująca. Zakładamy, że kandydat ma jakieś "prawdziwe'' preferencje . Podając preferencje kandydat (przy założeniu, że wszyscy inni kandydaci podają preferencje z układu ) zostaje umieszczony w szkole . Kandydat może jednak spróbować podać "fałszywe'' preferencje licząc na to, że skorzysta dzięki temu i znajdzie się w szkole lepszej niż a mianowicie w szkole (lepszej z punktu widzenia ,,prawdziwych'' preferencji ). 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.

    Czy wiesz ĹĽe...? (beta)
    Zasada proporcjonalności: Zasada w myśl której, wyrażane w wyborach przez społeczność preferencje, mają być proporcjonalnie odzwierciedlone w organie do którego wyłaniana jest reprezentacja. Reprezentacja ta może być wybierana w społecznych strukturach rozproszonej władzy równoległej, w sposób zindywidualizowany (w procedurze Brytyjskiej Reprezentacji Proporcjonalnej oraz w jednomandatowej metodzie proporcjonalnego głosu alternatywnego) lub w strukturach wysoce hierarchicznych (w wysokim stopniu zależnych od liderów partyjnych) w sposób kolektywny (w wielomandatowym systemie zamkniętych list partyjnych). Na przykład w polskim Sejmie, rozdział mandatów przypadających partiom politycznym ma możliwie proporcjonalnie reprezentować wszystkie preferencje obywatelskie, które wyrażone zostały w postaci oddanych ważnych głosów wyborczych. Zasada ta została nieco ograniczona wprowadzonym w 1993 r. progiem wyborczym. Warto zauważyć że zasada proporcjonalności odnosi się do proporcjonalnego odzwierciedlenia preferencji wszystkich wyborców na drodze wyłaniania reprezentacji, a zatem na poziomie reprezentacji w organie do którego odbywają się wybory, lub na poziomie proporcjonalnego odzwierciedlania preferencji w procesie wyłaniania reprezentanta (podczas procedury wyborczej na poziomie okręgów). Realizowana jest więc poprzez system list partyjnych, ordynację pojedynczego głosu przechodniego (tzw. Brytyjską Reprezentację Proporcjonalną) lub system proporcjonalnego głosu alternatywnego. 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. 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:

    Metoda analizy starożytnych (analisis antiquorum) – metoda rozwiązywania równań. Aby rozwiązać taką metodą równanie f(x) = g(x) zakładamy, że to równanie ma rozwiązanie i że tym rozwiązaniem jest liczba a. Wówczas otrzymujemy zdanie prawdziwe f(a) = g(a). Następnie, stosując prawa arytmetyki, znajdujemy liczbę a. Na koniec sprawdzamy, czy znaleziona liczba jest rozwiązaniem równania. Reklama behawioralna - reklama, której zasada działania jest podobna do reklamy kontekstowej, jednak głównym kryterium doboru reklamy nie jest treść przeglądanej strony internetowej, ale preferencje internauty. Określa się je na przykład dzięki historii odwiedzanych stron WWW, czy rodzajowi zakupów, jakich dokonuje się w sieci. Dane służące do utworzenia reklamy behawioralnej mają charakter długookresowy i uwzględniają różne aspekty postępowania internauty.

    Zgodność motywacji: W teorii mechanizmów, mechanizm jest zgodny motywacyjnie, jeśli każdy uczestnik otrzymuje największe korzyści, kiedy wyjawia swoje szczere preferencje. Algorytm z nawrotami (ang. backtracking) – ogólny algorytm wyszukiwania wszystkich (lub kilku) rozwiązań niektórych problemów obliczeniowych, który stopniowo generuje kandydatów na rozwiązanie jednak, gdy stwierdzi, że znaleziony kandydat c nie może być poprawnym rozwiązaniem, nawraca (ang. "backtracks") do punktu, gdzie może podjąć inną decyzje związaną z jego budową.

    System pojedynczego głosu przechodniego, czyli Brytyjskiej Reprezentacji Proporcjonalnej (PGP tzw. STV od Single Transferable Vote lub BPR od British Proportional Representation) – jeden z proporcjonalnych systemów wyborczych. W istocie jest to najstarsza ordynacja proporcjonalna po raz pierwszy opracowana przez Thomasa Wrighta Hilla w 1819 roku. W 1840 roku wykorzystano ją w wyborach samorządu miasta Adelaide, a następnie w wyborach parlamentu Duńskiego. Wykorzystywana jest w wyborach w Irlandii Północnej, Irlandii oraz samorządowych wyborach w Australii, Stanach Zjednoczonych i w australijskich wyborach senackich. Jest to proporcjonalna metoda wyłaniania reprezentantów parlamentarnych w której proporcjonalność uzyskana jest nie za pomocą list partyjnych, ale poprzez indywidualne głosowanie (na osobę) z użyciem skali rangowej (ranking). Stosowana jest więc ordynacja preferencyjna, czyli taka w której wyborca głosuje poprzez wskazanie swojej preferencji wobec każdego kandydata, szeregując wszystkich potencjalnych przedstawicieli okręgu od najbardziej do najmniej pożądanego. Wynik odzwierciedla więc wszystkie preferencje wszystkich wyborców, którzy oddali głos skuteczny (ważny). W ten sposób spełniony zostaje warunek proporcjonalności. Podobnym systemem jest jednomandatowa metoda proporcjonalnego głosu alternatywnego stosowana w Australii, z tą różnicą że w przypadku Brytyjskiej Reprezentacji Proporcjonalnej (wykorzystywanej np. w izbie niższej parlamentu irlandzkiego), wybory odbywają się w wielomandatowych okręgach wyborczych. Ze względu rozprzestrzeniania się tej ordynacji wyborczej w krajach byłego Imperium Brytyjskiego, w większości z nich znana jest jako Brytyjska Reprezentacja Proporcjonalna (British Proportional Representation), zaś w Australii jako metoda Hare’a-Clarka. Uznawana jest przez niektórych politologów za bardziej korzystny system wyborczy od ordynacji list z formułą D’Hondta lub Sainte-Lague’a, z uwagi na redukcję do minimum ilości utraconych głosów w wyborach. Wydaje się też dostarczać bardziej demokratycznych wyników wyborów w porównaniu do zamkniętych list partyjnych, ponieważ uniezależnia kandydatów od kierownictw partyjnych (ze względu na brak list, a więc i zobowiązań hierarchicznych wobec gron partyjnych; zobowiązania kandydata wobec wyborców w okręgu są więc silniejsze od zobowiązań wewnątrzpartyjnych). Nowszy proporcjonalny, preferencyjny system, z identycznym oddawaniem głosu, to nowa metoda Schulzego z 1997, która jak dotąd nie została wykorzystana w wyborach parlamentarnych. W teorii obliczalności o maszynie lub języku programowania mówimy, że jest kompletny w sensie Turinga lub zupełny, jeśli można za jego pomocą rozwiązać identyczną klasę problemów obliczeniowych, jak na uproszczonym modelu programowalnego komputera zwanego maszyną Turinga. W praktyce oznacza to, że jeśli dany język lub maszyna potrafi wykonać lub wyrazić każdy algorytm, określany jest mianem zupełnego, przy czym nie jest wymagane, by algorytm ten realizowany był prosto, wydajnie bądź efektywnie.

    Celem funkcji dobrobytu społecznego jest ujęcie ogólnego położenia społeczeństwa, odzwierciedla preferencje jednostek dotyczącą różnych stanów świata.

    Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb. Według finitystów, zwolenników skrajnego nurtu filozofii matematyki, są to jedyne liczby, jakimi powinna zajmować się matematyka - słynne jest stwierdzenie propagatora arytmetyzacji wszystkich dziedzin matematyki Leopolda Kroneckera: Liczby całkowite stworzył dobry Bóg. Reszta jest dziełem człowieka.

    Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. Blended learning lub B-learning - to tak zwana mieszana (zintegrowana) metoda kształcenia, łącząca tradycyjne metody nauki (bezpośredni kontakt z prowadzącym) z aktywnościami prowadzonymi zdalnie przy pomocy komputera (M-learning). Stosunek poszczególnych elementów dobiera się w zależności od treści kursu, potrzeb studentów i preferencji prowadzącego. Metoda ta cechuje się dużą skutecznością, ponieważ pozwala na elastyczny sposób budowania szkolenia z uwzględnieniem celów, tematyki i specyfiki branży oraz grupy uczestników. Zaletą B-learningu jest z pewnością możliwość stosowania zdalnych jak i bezpośrednich form aktywizacji uczniów oraz wspólnej pracy on-line nauczyciela i uczniów. Organizacja czasu w B-learningu jest swobodna dzięki zajęciom zdalnym, a nie wymuszona jak w przypadku tradycyjnych zajęć stacjonarnych.

    Heurystyka (gr. heuresis – odnaleźć, odkryć, heureka – znalazłem) - w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu niektórych zagrożeń komputerowych, takich jak wirusy lub robaki). Metody używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy przypadków, gdy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*).

    Dodano: 11.12.2009. 16:55  


    Najnowsze