Dopasowanie bez zazdrości
W ekonomii i teorii wyboru społecznego dopasowanie bez zazdrości (EFM) to dopasowanie między ludźmi do „rzeczy”, które jest wolne od zazdrości w tym sensie, że żadna osoba nie chciałaby zamienić swojej „rzeczy” na rzecz innej osoby. Termin ten był używany w kilku różnych kontekstach.
W nieważonych grafach dwudzielnych
W nieważonym grafie dwudzielnym G = ( X + Y , E ) dopasowanie bez zazdrości to dopasowanie , w którym żaden niedopasowany wierzchołek w X nie sąsiaduje z dopasowanym wierzchołkiem w Y . Załóżmy, że wierzchołki X reprezentują ludzi, wierzchołki Y reprezentują domy, a krawędź między osobą x a domem y reprezentuje fakt, że x chce mieszkać w y . Wtedy EFM jest częściowym przydziałem domów dla ludzi w taki sposób, że każdy bezdomny nie zazdrości nikomu posiadania domu, ponieważ i tak nie lubi żadnego przydzielonego mu domu.
Każde dopasowanie, które nasyca X , jest wolne od zazdrości, a każde puste dopasowanie jest wolne od zazdrości. Ponadto, jeśli | N G ( X )| ≥ |X| ≥ 1 (gdzie NG dopuszcza ( X ) jest zbiorem sąsiadów X w Y ), to G niepusty EFM. Jest to złagodzenie warunku małżeńskiego Halla , który mówi, że jeśli | N G ( X ')| ≥ |X'| dla każdego podzbioru X ' z X istnieje dopasowanie nasycające X.
Na rynkach z pieniędzmi
Rozważmy rynek, na którym jest kilku kupujących i kilka towarów, a każdy towar może mieć swoją cenę. Biorąc pod uwagę wektor ceny, każdy kupujący ma zestaw popytu - zestaw pakietów, które maksymalizują użyteczność kupującego w stosunku do wszystkich pakietów (ten zestaw może obejmować pusty pakiet, na wypadek gdyby kupujący uznał wszystkie pakiety za zbyt drogie).
Dopasowanie bez zazdrości o cenę (przy danym wektorze ceny) to dopasowanie, w którym każdy agent otrzymuje pakiet ze swojego zbioru popytu. Oznacza to, że żaden agent nie chciałby otrzymać kolejnego pakietu w tych samych cenach. Przykładem tego ustawienia jest harmonii czynszów - dopasowywanie najemców (agentów) do pokoi (przedmiotów) przy ustalaniu ceny dla każdego pokoju.
Cena wolna od zazdrości to wektor ceny, dla którego istnieje dopasowanie wolne od zazdrości. Jest to złagodzenie równowagi walrasowskiej : równowaga walrasowska składa się z ceny EF i dopasowania EF, a ponadto każdy przedmiot musi być dopasowany lub mieć cenę zerową. Wiadomo, że w równowadze walrasowskiej dopasowanie maksymalizuje sumę wartości, tj. jest dopasowaniem o maksymalnej wadze . Jednak przychody sprzedawcy mogą być niskie. Motywuje to do złagodzenia cen EF, w których sprzedawca może wykorzystać ceny minimalne w celu zwiększenia przychodów; zobacz ceny wolne od zazdrości , aby uzyskać więcej informacji.
Na rynkach bez pieniędzy
Termin dopasowywanie bez zazdrości jest często używany do określenia słabszego warunku - dopasowywania bez uzasadnionej zazdrości .
W krojeniu ciasta
Termin dopasowywanie bez zazdrości był również używany w innym kontekście: algorytm poprawiający efektywność krojenia ciasta bez zazdrości .