Acykliczność

Acykliczność to własność preferencji i innych relacji dwuczłonowych, która wymaga aby przeciwsymetryczna część relacji nie zawierała cykli.

Definicja

Formalnie, relacja dwuczłonowa $R$ jest acykliczna, jeżeli nie istnieje ciąg $x_{1},\;x_{2},\;...,\;x_{n}$ elementów takich, że $x_{1}Rx_{2},\;x_{2}Rx_{3},\;\dots ,\;x_{n-1}Rx_{n},\;x_{n}Rx_{1}.$ Często zakłada się dodatkowo, że relacja $R$ jest przeciwsymetryczna.

Acykliczność a przechodniość

Dla każdej (słabej) relacji preferencji $R$ można zdefiniować przeciwsymetryczną podrelację silnej preferencji $P$ oraz symetryczną podrelację obojętności $I$ w następujący sposób. Konsument silnie preferuje $x$ wobec $y,$ co zapisuje się jako $xPy,$ jeżeli woli $x$ niż $y$ (zachodzi $xRy$) oraz nie woli $y$ niż $x$ (nie zachodzi $yRx$). Konsument jest obojętny między $x$ i $y,$ co zapisuje się jako $xIy,$ jeżeli jednocześnie woli $x$ niż $y$ i woli $y$ niż $x$ (zachodzi jednocześnie $xRy$ i $yRx$).

Własność acykliczności (przy założeniu przeciwsymetryczności) jest istotnie słabsza niż podobna do niej własność przechodniości. Na przykład jeżeli $xPy,$ $yPz$ oraz $xIz,$ wówczas relacja silnej preferencji $P$ jest acykliczna, mimo że nie jest przechodnia. Podobnie, jeżeli $xIy,$ $yIz$ i $xPz$ wówczas relacja obojętności $I$ jest acykliczna, mimo że nie jest przechodnia.

Acykliczność w naukach społecznych

Gdy zbiór $S$ dostępnych alternatyw zawiera więcej niż dwa elementy, wówczas istnieje potrzeba zdefiniowania podzbioru $C(S)$ zbioru $S,$ złożonego z tych alternatyw które mogłyby zostać wybrane, gdyby decydent mógł wybierać spośród wszystkich elementów zbioru $S.$ Tak więc $C$ jest odwzorowaniem wielowartościowym przyporządkowującym rozważanym zbiorom pewne ich podzbiory. Taka multifunkcja wyboru, powinna być w jakimś sensie zgodna z dwuczłonową relacją preferencji $P$ zdefiniowaną na zbiorze $S.$ Naturalnym kandydatem na takie odwzorowanie wielowartościowe $C(S)$ jest zbiór alternatyw, które nie są zdominowane, czyli takich elementów $x$ należących do zbioru $S,$ dla których nie istnieje element $y$ w tym zbiorze spełniający warunek $xPy.$

Acykliczność relacji $P$ jest warunkiem koniecznym i dostatecznym istnienia niepustego podzbioru niezdominowanych elementów, dla dowolnego, skończonego podzbioru $S.$ Dodatkowo, zdefiniowana w ten sposób multifunkcja wyboru $C(S)$ posiada następującą własność: jeżeli $T$ jest podzbiorem $S$ i jeżeli $x$ jest elementem zarówno $T,$ jak i $C(S),$ wówczas $x$ musi być elementem $C(T).$ Intuicyjna interpretacja tej własności jest następująca: Jeżeli osoba $x$ jest mistrzem świata (elementem $C(S)$) i Polakiem (elementem $T$), wówczas musi ona być również mistrzem Polski (elementem $C(T)$). Ta własność jest atrakcyjna, ponieważ oznacza ona, że jeżeli jakaś opcja $x$ nie została wybrana z podzbioru $T,$ to nie trzeba jej rozpatrywać przy analizie wyboru z większego zbioru $S,$ ponieważ opcja $x$ nie zostanie również wybrana z $S.$ Intuicyjnie, mistrzem świata nie może być osoba, która nie jest mistrzem Polski, ponieważ w Polsce istnieje ktoś od niej lepszy.

Historia

Badanie relacji acyklicznych sięga wstecz co najmniej do 1785 roku, gdy Jean Condorcet analizował paradoks głosowania, w którym preferencje poszczególnych wyborców są przechodnie, a mimo tego preferencja uzyskana przez głosowanie większościowe jest cykliczna.

Acykliczność ma spore znaczenie we współczesnej teorii ekonomii. W teorii wyboru konsumenta mocny aksjomat preferencji ujawnionych stwierdza, że relacja preferencji ujawnionych konsumenta jest acykliczna. Acykliczoność pojawia się również w teorii gier. Acykliczność relacji dominacji jest ściśle związana z jednoznacznością istnienia punktu równowagi w rozwiązaniu zaproponowanym przez Johna von Neumanna i Oskara Morgensterna. Najwięcej uwagi acykliczność zyskała jednak w związku z badaniami laureata Nagrody Banku Szwecji im. Alfreda Nobla w dziedzinie ekonomii, Kennetha Arrowa, dotyczącymi jego twierdzenia o niemożności. Jego twierdzenie dotyczy agregacji preferencji indywidualnych w preferencje społeczne. Arrow udowodnił, że agregacje preferencji spełniające dwa aksjomaty i przechodniość muszą być dyktatorskie. W latach późniejszych próbowano uniknąć tego paradoksu, osłabiając wymaganie aby preferencje społeczne były nie przechodnie, lecz jedynie acykliczne. Okazuje się, że takie reguły istnieją, jednak ich własności są podobne do reguł dyktatorskich.

Zobacz też

• graf acykliczny