Dopasowanie bez uzasadnionej zazdrości

W ekonomii i teorii wyboru społecznego dopasowanie bez uzasadnionej zazdrości to dopasowanie na rynku dwustronnym , na którym żaden agent nie preferuje przypisania innego agenta i jednocześnie jest preferowany przez to przypisanie.

Rozważmy na przykład zadanie polegające na dobieraniu lekarzy do rezydentów w szpitalach. Każdy lekarz ma stosunek preferencji co do szpitali, klasyfikując szpitale od najlepszego do najgorszego. Każdy szpital ma stosunek preferencji do lekarzy, klasyfikując lekarzy od najlepszych do najgorszych. Każdy lekarz może pracować co najwyżej w jednym szpitalu, a każdy szpital może zatrudniać co najwyżej określoną liczbę lekarzy (zwaną pojemnością szpitala ). Celem jest dopasowanie lekarzy do szpitali, bez transferów pieniężnych.

Zawiść to sytuacja, w której jakiś lekarz d ₁ , zatrudniony w jakimś szpitalu h ₁ , preferuje inny szpital h ₂ , który zatrudnia innego lekarza d ₂ (mówimy, że d ₁ zazdrości d ₂ ). Zazdrość jest uzasadniona , jeśli jednocześnie h ₂ woli d ₁ od d ₂ . Zauważ, że jeśli d ₁ uzasadnia zazdrość wrt h ₂ , to h ₂ uzasadnia zazdrość wrt d ₁ ( h ₂ zazdrość h ₁ ). W tym przypadku mówimy również, że d ₁ i h ₂ są parą blokującą . Dopasowanie bez par blokujących nazywa się dopasowaniem no-justified-envy (NJE) lub dopasowaniem, które eliminuje uzasadnioną zazdrość .

Terminy pokrewne

Dopasowywanie nieuzasadnionej zazdrości to złagodzenie dwóch różnych warunków:

Dopasowanie bez zazdrości to dopasowanie, w którym w ogóle nie ma zazdrości, uzasadnionej lub nie.
Stabilne dopasowanie to dopasowanie, w którym nie ma uzasadnionej zazdrości, a ponadto nie ma marnotrawstwa . Dopasowanie ma marnotrawstwo, jeśli istnieje lekarz d i szpital h , tak że d woli h od swojego obecnego pracodawcy, h ma kilka wolnych stanowisk i h woli d od wolnego stanowiska.

Struktura kraty

W problemie z dopasowaniem wiele do jednego istnieją stabilne dopasowania, które można znaleźć za pomocą algorytmu Gale-Shapleya . Dlatego istnieją również dopasowania NJE. Ogólnie rzecz biorąc, może istnieć wiele różnych dopasowań NJE. Zbiorem wszystkich dopasowań NJE jest krata . Zbiór stabilnych dopasowań (które są podzbiorem dopasowań NJE) jest stałym punktem operatora Tarsky'ego na tej sieci.

Zarówno górne, jak i dolne kwoty

Często szpitale mają nie tylko górne limity (pojemności), ale i niższe – każdy szpital musi mieć przydzieloną przynajmniej pewną minimalną liczbę lekarzy. W takich problemach stabilne dopasowania mogą nie istnieć (choć łatwo sprawdzić, czy istnieje stabilne dopasowanie, ponieważ zgodnie z twierdzeniem wiejskich szpitali , we wszystkich stabilnych skojarzeniach liczba lekarzy przypisanych do każdego szpitala jest identyczna). W takich przypadkach naturalne jest sprawdzenie, czy istnieje dopasowanie NJE. Warunkiem koniecznym jest, aby suma wszystkich niższych kwot była równa co najwyżej liczbie lekarzy (w przeciwnym razie w ogóle nie istnieje wykonalne dopasowanie). W takim przypadku, jeśli wszystkie pary lekarz-szpital są akceptowalne (każdy lekarz woli dowolny szpital od bezrobocia, a każdy szpital woli dowolnego lekarza od wolnego stanowiska), to dopasowanie NJE zawsze istnieje.

Jeśli nie wszystkie pary są akceptowalne, dopasowanie NJE może nie istnieć. Istnieje możliwość stwierdzenia istnienia EFM w następujący sposób. Utwórz nową instancję problemu, w której górne kwoty są dolnymi kwotami pierwotnego problemu, a dolne kwoty wynoszą 0. W nowym problemie stabilne dopasowanie zawsze istnieje i można je skutecznie znaleźć. Pierwotny problem ma dopasowanie NJE wtedy i tylko wtedy, gdy w stabilnym dopasowaniu nowego problemu każdy szpital jest pełny.

Algorytm można ulepszyć, aby znaleźć maksymalne dopasowanie NJE.

Minimalizowanie nieuzasadnionej zazdrości

Z definicji w dopasowaniu NJE może istnieć lekarz d i szpital h taki, że d woli h od swojego obecnego pracodawcy, ale h nie preferuje d nad którymkolwiek z jej obecnych pracowników. Można to nazwać „nieuzasadnioną zazdrością”. Dopasowanie bez jakiejkolwiek zazdrości istnieje tylko w rzadkich przypadkach, w których każdy lekarz może być dopasowany do swojego pierwszego wyboru. Kiedy takie „całkowicie wolne od zazdrości dopasowanie” nie istnieje, nadal rozsądne jest znalezienie dopasowań, które minimalizują „ilość zazdrości”. Istnieje kilka sposobów mierzenia wielkości zazdrości, na przykład: całkowita liczba przypadków zazdrości w stosunku do wszystkich lekarzy lub maksymalna liczba przypadków zazdrości na jednego lekarza.

Zobacz też

Wolność od zazdrości
Wycena bez zazdrości - inna koncepcja związana z brakiem zazdrości i dopasowaniem.

^ Abdulkadiroğlu, Atila; Sonmez, Tayfun (2003-06-01). „Wybór szkoły: podejście do projektowania mechanizmów” . Amerykański Przegląd Ekonomiczny . 93 (3): 729–747. doi : 10.1257/000282803322157061 . hdl : 10161/2090 . ISSN 0002-8282 .
^ Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A.; Roth, Alvin E.; Tercieux, Olivier (2017-03-27). „Minimalizacja uzasadnionej zazdrości w wyborze szkoły: projekt OneApp w Nowym Orleanie” . doi : 10.3386/w23265 . S2CID 9497845 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
Bibliografia _ Roth, Alvin E. (1 maja 2018). „Sieć połączeń wolnych od zazdrości”. Gry i zachowania ekonomiczne . 109 : 201–211. doi : 10.1016/j.geb.2017.12.016 . ISSN 0899-8256 .
^ ^ab ^Fragiadakis , Daniel; Iwasaki, Atsushi; Trojan, Piotr; Ueda, Suguru; Yokoo, Makoto (1 stycznia 2016). „Dopasowanie strategiczne z minimalnymi limitami”. Transakcje ACM dotyczące ekonomii i obliczeń . 4 (1): 6:1-6:40. doi : 10.1145/2841226 . ISSN 2167-8375 . S2CID 1287011 .
^ Yokoi, Yu (17 kwietnia 2017). „Pozbawione zazdrości dopasowania z niższymi kwotami”. arXiv : 1704.04888 [ cs.GT ].
^ „Jak dobre są popularne dopasowania?” (PDF) . www.cse.iitm.ac.in . Zarchiwizowane od oryginału (PDF) w dniu 17 stycznia 2019 r . Źródło 16 stycznia 2019 r .
^ Tadenuma, Koichi (2011), „Partnerstwo, solidarność i minimalna zazdrość w problemach z dopasowywaniem”, w: Fleurbaey, Marc; Salles, Maurycy; Weymark, John A. (red.), Etyka społeczna i ekonomia normatywna , Studies in Choice and Welfare , Springer Berlin Heidelberg, s. 155–167, doi : 10.1007/978-3-642-17807-8_6 , ISBN 9783642178078

[1] Abdulkadiroğlu, Atila; Sonmez, Tayfun (2003-06-01). „Wybór szkoły: podejście do projektowania mechanizmów” . Amerykański Przegląd Ekonomiczny . 93 (3): 729–747. doi : 10.1257/000282803322157061 . hdl : 10161/2090 . ISSN 0002-8282 .

[2] Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A.; Roth, Alvin E.; Tercieux, Olivier (2017-03-27). „Minimalizacja uzasadnionej zazdrości w wyborze szkoły: projekt OneApp w Nowym Orleanie” . doi : 10.3386/w23265 . S2CID 9497845 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )

[:0-3] Bibliografia _ Roth, Alvin E. (1 maja 2018). „Sieć połączeń wolnych od zazdrości”. Gry i zachowania ekonomiczne . 109 : 201–211. doi : 10.1016/j.geb.2017.12.016 . ISSN 0899-8256 .

[:1-4] Fragiadakis , Daniel; Iwasaki, Atsushi; Trojan, Piotr; Ueda, Suguru; Yokoo, Makoto (1 stycznia 2016). „Dopasowanie strategiczne z minimalnymi limitami”. Transakcje ACM dotyczące ekonomii i obliczeń . 4 (1): 6:1-6:40. doi : 10.1145/2841226 . ISSN 2167-8375 . S2CID 1287011 .

[5] Yokoi, Yu (17 kwietnia 2017). „Pozbawione zazdrości dopasowania z niższymi kwotami”. arXiv : 1704.04888 [ cs.GT ].

[6] „Jak dobre są popularne dopasowania?” (PDF) . www.cse.iitm.ac.in . Zarchiwizowane od oryginału (PDF) w dniu 17 stycznia 2019 r . Źródło 16 stycznia 2019 r .

[7] Tadenuma, Koichi (2011), „Partnerstwo, solidarność i minimalna zazdrość w problemach z dopasowywaniem”, w: Fleurbaey, Marc; Salles, Maurycy; Weymark, John A. (red.), Etyka społeczna i ekonomia normatywna , Studies in Choice and Welfare , Springer Berlin Heidelberg, s. 155–167, doi : 10.1007/978-3-642-17807-8_6 , ISBN 9783642178078