Ułamkowa efektywność Pareto

W ekonomii i informatyce ułamkowa efektywność Pareto lub ułamkowa optymalność Pareto (fPO) to wariant efektywności Pareto stosowany przy ustalaniu sprawiedliwej alokacji obiektów dyskretnych . Alokacja obiektów nazywana jest dyskretną , jeśli każdy element jest w całości przydzielony jednemu agentowi; nazywa się to ułamkowym , jeśli niektóre obiekty są podzielone między dwóch lub więcej agentów. Alokacja dyskretna nazywana jest efektywną w sensie Pareto (PO), jeśli nie jest zdominowana przez Pareto przez żadną alokację dyskretną; nazywa się to ułamkową efektywnością Pareto (fPO), jeśli nie jest zdominowane przez Pareto przez żadną alokację dyskretną lub ułamkową . Tak więc fPO jest silniejszym wymaganiem niż PO: każda alokacja fPO to PO, ale nie każda alokacja PO to fPO.

Definicje formalne

Istnieje zbiór n agentów i zbiór m obiektów. Alokacja jest określona przez macierz n - xm z , gdzie każdy element z [ i , o ] jest liczbą rzeczywistą z przedziału od 0 do 1. Reprezentuje ona ułamek, który agent i otrzymuje z obiektu o . Dla każdego obiektu o suma wszystkich elementów w kolumnie o jest równa 1, ponieważ cały obiekt jest przydzielony.

Alokację nazywamy dyskretną lub całkową , jeśli wszystkie jej elementy z [ i , o ] wynoszą 0 lub 1; oznacza to, że każdy obiekt jest w całości przydzielony do pojedynczego agenta.

Alokację y nazywamy ulepszeniem Pareto alokacji z , jeśli użyteczność wszystkich agentów w y jest co najmniej tak duża jak w z , a użyteczność niektórych agentów w y jest ściśle większa niż w z . W tym przypadku mówimy również, że y Pareto dominuje z .

Jeśli alokacja z nie jest zdominowana przez żadną alokację dyskretną w sensie Pareto, nazywana jest dyskretną efektywną w sensie Pareto lub po prostu efektywną w sensie Pareto (zwykle w skrócie PO ).

Jeśli z nie jest w ogóle zdominowane przez Pareto przez żadną alokację - czy to dyskretną, czy ułamkową - wtedy nazywa się to ułamkową efektywnością Pareto (zwykle w skrócie fPO ).

Przykłady

PO nie implikuje fPO

Załóżmy, że jest dwóch agentów i dwa przedmioty. Alicja ocenia pozycje na 3, 2, a George na 4, 1. Niech z będzie przydziałem, który daje Alicji pierwszą pozycję, a George'owi drugą. Zauważ, że profil użyteczności z to (3,1).

z jest (dyskretnie) efektywne w sensie Pareto. Aby to zobaczyć, rozważmy inne możliwe dyskretne alokacje: ich profile użyteczności to (7,0) lub (0,3) lub (2,4). W każdym razie użyteczność co najmniej jednego agenta jest mniejsza, więc żadna dyskretna alokacja nie dominuje z .
Jednak z nie jest ułamkowo wydajne w Pareto. Dominuje w nim alokacja y dająca Alicji 1/2 pierwszej pozycji i całą drugą pozycję, a drugą 1/2 pierwszej pozycji George'owi; profil użyteczności y wynosi (3,5, 2), więc daje wyższą użyteczność obu agentom.

Cena fPO

Poniższy przykład pokazuje „cenę” fPO. Alokacja całkowa maksymalizująca iloczyn użyteczności (nazywana także dobrobytem Nasha) to PE, ale nie fPO. Ponadto iloczyn użyteczności w dowolnym alokacji fPO wynosi co najwyżej 1/3 produktu maksymalnego. Istnieje pięć dóbr {h ₁ ,h ₂ ,g ₁ ,g ₂ ,g ₃ } i 3 czynniki o następujących wartościach (gdzie C jest dużą stałą, a d jest małą stałą dodatnią):

Agenci ↓ Towary ⇒	godzina ₁	godzina ₂	g ₁	g ₂	g ₃
1 _{_}	C	C	1	1- d	1- d
2 _{_}	C	C	1- d	1	1- d
3 _{_}	C	C	1- d	1- d	1

Alokacja całki maksymalnego iloczynu to {h ₁ }, {h ₂ }, {g ₁ , g ₂ , g ₃ }, z iloczynem ${\ Displaystyle C ^ {2} \ cdot ( 3-2d)}$ . To nie jest fPO, ponieważ jest zdominowane przez alokację ułamkową: agent 3 może dać g ₁ agentowi 1 (tracąc użyteczność 1- d ) w zamian za ułamek h ₁ , który obaj agenci wyceniają na 1- d /2. Ten handel ściśle poprawia dobrobyt obu agentów. Co więcej, w dowolnej alokacji integralnej fPO istnieje agent A _i , który otrzymuje tylko (co najwyżej) dobro g _i - w przeciwnym razie można przeprowadzić podobną transakcję. Dlatego alokacja maksymalnego produktu fPO to {g ₁ , h ₁ }, {g ₂ , h ₂ }, {g ₃ }, z iloczynem ${\ Displaystyle (C + 1) ^ {2} }$ . Kiedy C jest wystarczająco duże, a d jest wystarczająco małe, stosunek iloczynu zbliża się do 1/3.

Żadna alokacja fPO nie jest prawie sprawiedliwa

Poniższy przykład pokazuje, że fPO jest nie do pogodzenia z pojęciem sprawiedliwości znanym jako EQx - sprawiedliwość do każdego dobra. Istnieją trzy dobra {g ₁ , g ₂ , g ₃ } i dwa czynniki o następujących wartościach (gdzie e jest małą stałą dodatnią):

Agenci ↓ Towary ⇒	g ₁	g ₂	g ₃
1 _{_}	1+ e	( 1+e ) ¹⁰	1
2 _{_}	1	( 1+e ) ¹⁰	1+ e

Tylko dwie dyskretne alokacje to EQx:

Agent 1 dostaje { g ₂ }, a agent 2 dostaje {g ₁ ,g ₃ }; profil użyteczności to (( 1+e ) ¹⁰ , 2+ e ). Ta alokacja to PO, ale nie fPO, ponieważ jest zdominowana przez alokację ułamkową, która daje agentowi 1 wiązkę {g ₁ , (1-(1+ e ) ⁻⁹ ) ułamek g ₂ }, a agentowi 2 wiązkę {g ₃ , (1+ e ) ⁻⁹ ułamek g ₂ }, w którym profil użyteczności wynosi (( 1+e ) ¹⁰ , 2+2 e ).
Agent 1 dostaje {g ₁ , g ₃ }, a agent 2 dostaje { g ₂ }; profil użyteczności to (2+ e , ( 1+ e ) ¹⁰ ). Ta alokacja to PO, ale nie fPO, ponieważ jest zdominowana przez alokację ułamkową, która daje agentowi 2 wiązkę {g ₁ , (1-(1+ e ) ⁻⁹ ) ułamek g ₂ }, a agentowi 1 wiązkę {g ₃ , (1+ e ) ⁻⁹ ułamek g ₂ }, w którym profil użyteczności to (2+2 e, ( 1+e ) ¹⁰ ).

Ten sam przykład pokazuje, że fPO jest nie do pogodzenia z pojęciem uczciwości znanym jako EFx – bez zazdrości wobec wszelkiego dobra.

Charakteryzacja

Maksymalizacja ważonej sumy użyteczności

Alokacja jest fPO wtedy i tylko wtedy, gdy maksymalizuje ważoną sumę użyteczności agentów. Formalnie niech w będzie wektorem o rozmiarze n , przypisującym wagę w _i każdemu agentowi i . Mówimy, że alokacja z jest w -maksymalna, jeśli zachodzi jedna z następujących (równoważnych) właściwości:

$przypisany$ obiekt o tylko do agentów ja dla których
${\ Displaystyle z_ {i, o}> 0}$ implikuje ${\ Displaystyle w_ {i} v_ {i, o} \ geq w_ {j} v_{j,o}}$ dla wszystkich agentów i , j oraz obiektów o .
Ważona suma użyteczności jest maksymalna spośród wszystkich alokacji, ${\ Displaystyle \ suma _ {i} w_ {i} \ cdot u_ {i} (\ mathbf {z})}$ gdzie ${\ Displaystyle u_ {i} (\ mathbf {z}): = \ suma _ {o} v_ {i, o} \ cdot z_{i,o}=}$ użyteczność agenta i w alokacji z .

Alokacja jest fPO wtedy i tylko wtedy, gdy jest w -maksymalna dla pewnego wektora w o ściśle dodatnich wagach. Ta równoważność została udowodniona dla towarów przez Negishi i Variana . Dowód został rozszerzony na zło przez Branzei i Sandomirskiego. Został on później rozszerzony na wartościowania ogólne (mieszaniny dóbr i złych) przez Sandomirskiego i Segala-Halewiego.

Brak cykli ulepszeń na wykresie zużycia

Alokacja jest fPO wtedy i tylko wtedy, gdy jej wykres konsumpcji skierowanej nie zawiera cykli z iloczynem mniejszym niż 1. Graf konsumpcji skierowanej alokacji z jest grafem dwudzielnym , w którym węzły po jednej stronie są agentami, węzły po drugiej stronie są przedmioty, a skierowane krawędzie reprezentują wymiany: krawędź wchodząca do agenta i reprezentuje przedmioty, które agent i chciałby zaakceptować (dobra, których nie posiada, lub zło, które posiada); przewaga pochodząca od agenta i reprezentuje przedmioty, którymi agent i może zapłacić (towary, które posiada, lub zło, których nie posiada). Waga krawędzi i -> o wynosi | v _i,o |, Waga krawędzi i -> o wynosi | v _{ja, o} | a waga krawędzi o -> i wynosi 1/| v _{ja, o} |.

Alokację nazywamy złośliwą , jeśli jakiś obiekt o jest konsumowany przez agenta i przy v _i,o ≤ 0, nawet jeśli istnieje jakiś inny agent j z v _j,o > 0; lub jakiś obiekt o jest konsumowany przez agenta i z v _i,o < 0, nawet jeśli istnieje inny agent j z v _j,o ≥ 0. Oczywiście każdy złośliwy przydział można ulepszyć w Pareto, przesuwając obiekt o od agenta i do agenta j . Dlatego niezłośliwość jest warunkiem koniecznym dla fPO.

Alokacja to fPO wtedy i tylko wtedy, gdy nie jest złośliwa, a jej wykres ukierunkowanej konsumpcji jako cykl niekierowany, w którym iloczyn wag jest mniejszy niż 1. Ta równoważność została udowodniona dla towarów w kontekście krojenia ciasta przez Barbanela. Został on przedłużony na złe przez Branzei i Sandomirskiy. Został on później rozszerzony na wartościowania ogólne (mieszaniny dóbr i złych) przez Sandomirskiego i Segala-Halewiego.

Związek z równowagą rynkową

Na rynku Fishera , gdy wszyscy agenci mają użyteczności liniowe, każda równowaga rynkowa to fPO. To jest pierwsze twierdzenie o dobrobycie .

Algorytmy

Decydowanie, czy dana alokacja jest fPO

Aby zdecydować, czy dana alokacja z jest fPO, można zastosować następujący algorytm:

Oblicz skierowany wykres zużycia z ;
Zastąp każdą wagę jej logarytmem;
Użyj algorytmu do znalezienia cyklu ujemnego, np. algorytmu Bellmana-Forda .
W oparciu o powyższą charakterystykę, z jest fPO wtedy i tylko wtedy, gdy nie znaleziono ujemnego cyklu.

Czas wykonania algorytmu to O(| V || E |). Tutaj, | V |= m + n i | E |≤ mn , gdzie m to liczba obiektów, a n liczba agentów. Dlatego fPO można określić w czasie O( mn ( m + n )).

Alternatywnym algorytmem jest znalezienie wektora w takiego, że dana alokacja jest w -maksymalizująca. Można to zrobić rozwiązując program liniowy . Czas działania jest słabo wielomianowy.

Natomiast decyzja, czy dana dyskretna alokacja jest PO, jest współ-NP-zupełna . Dlatego jeśli rozdzielacz twierdzi, że alokacja to fPO, agenci mogą skutecznie zweryfikować to twierdzenie; ale jeśli dzielnik twierdzi, że alokacja to PO, skuteczna weryfikacja tego twierdzenia może być niemożliwa.

Znalezienie dominującej alokacji fPO

Znalezienie alokacji fPO jest łatwe. Na przykład można to znaleźć za pomocą dyktatury seryjnej : agent 1 zabiera wszystkie przedmioty, dla których ma wartość dodatnią; następnie agent 2 zabiera wszystkie pozostałe obiekty, dla których ma wartość dodatnią; i tak dalej.

Bardziej interesującym wyzwaniem jest: biorąc pod uwagę początkową alokację z (która może być ułamkowa i nie może być fPO), znajdź alokację fPO z* , która jest poprawą Pareto z . To wyzwanie można rozwiązać dla n agentów i m obiektów o mieszanych (dodatnich i ujemnych) wartościowaniach, w czasie silnie wielomianowym, używając operacji O( n ² m ² ( n + m )). Ponadto w obliczonej alokacji jest co najwyżej n -1 udziałów.

Jeśli początkowa alokacja z jest równym podziałem, to ostateczna alokacja z* jest proporcjonalna. Dlatego powyższy lemat implikuje wydajny algorytm znajdowania ułamkowej alokacji PROP+fPO, z co najwyżej n -1 współdzieleniami. Podobnie, jeśli z jest nierównym podziałem, to z* jest proporcjonalnie ważone (proporcjonalne dla agentów z różnymi uprawnieniami). Implikuje to wydajny algorytm znajdowania ułamkowej alokacji WPROP+fPO z co najwyżej n -1 współdzieleniami.

Połączenie powyższego lematu z bardziej zaawansowanymi algorytmami może dać, w silnie wielomianowym czasie, alokacje, które są wolne od fPO i zazdrości, z co najwyżej n -1 współdzieleniami.

Wyliczanie alokacji fPO

Istnieje algorytm, który wylicza wszystkie wykresy zużycia, które odpowiadają alokacji fPO. Czas działania algorytmu to ${\ Displaystyle O (3 ^ {{\ Frac {(n-1) n }{2}}\cdot D}\cdot m^{{\frac {(n-1)n}{2}}+2})} , gdzie D$ jest stopniem degeneracji instancji ( D = m - 1 dla identycznych wartościowań; D = 0 dla niezdegenerowanych wartościowań, gdzie dla każdych dwóch agentów współczynniki wartości wszystkich m obiektów są różne). W szczególności, gdy n jest stałe, a D = 0, czas działania algorytmu jest silnie wielomianowy.

Znalezienie alokacji sprawiedliwych i fPO

Kilka ostatnich prac rozważało istnienie i obliczenie dyskretnej alokacji, która jest zarówno fPO, jak i spełnia pewne pojęcie sprawiedliwości .

Barman i Krishnamurthy dowodzą, że dyskretną alokację dóbr fPO+PROP1 można obliczyć w czasie silnie wielomianowym. Pokazują podobny wynik dla dyskretnej alokacji fPO + EF11 , gdzie EF11 oznacza „wolny od zazdrości aż do dodania jednego dobra i usunięcia innego dobra”.
Aziz, Moulin i Sandomirskiy przedstawiają algorytm, który oblicza ułamkową alokację fPO + WPROP obiektów mieszanych (dóbr i obowiązków). Wykorzystuje program liniowy , który maksymalizuje sumę użyteczności podlegającą proporcjonalności. Jeśli zostanie znalezione podstawowe wykonalne rozwiązanie (np. za pomocą algorytmu simpleks ), to wykres zużycia wynikowej alokacji jest acykliczny. Alternatywnie możliwe jest usunięcie cykli z wynikowego wykresu zużycia w czasie wielomianowym. Przedstawiają również algorytm, który konwertuje ułamkową alokację fPO+WPROP na dyskretną fPO+WPROP1 w czasie silnie wielomianowym.
Barman, Krishnamurthy i Vaish dowodzą, że zawsze istnieje dyskretna alokacja dóbr, która jest fPO+EF1 .
w czasie pseudowielomianowym można znaleźć dyskretną alokację dóbr fPO+EF1 . Dowodzą również, że gdy wszystkie wartości są dodatnie, może istnieć dyskretna alokacja fPO+EQ1 , którą można znaleźć w czasie pseudowielomianowym. Dla k -arnych przypadków (każdy agent ma co najwyżej k różnych wartości dobra) powyższe dwa wyniki można obliczyć w czasie wielomianowym. Podobnie, gdy liczba agentów jest stała, powyższe dwa wyniki można obliczyć w czasie wielomianowym.
Garg i Murhekar dowodzą, że gdy macierz wartościowania zawiera tylko dwie różne (dodatnie) wartości, zawsze istnieje dyskretna alokacja dóbr fPO+EFx , którą można obliczyć w czasie wielomianowym. Wzmacnia to wcześniejsze wyniki, które wykazały podobne wyniki dla wycen binarnych (0,1) oraz dla PO+EFx. Dają podobne wyniki dla PO+EQx .
Garg, Murhekar i Qin dowodzą, że gdy macierz wartościowania zawiera tylko dwie różne (ujemne) wartości, zawsze istnieje dyskretna alokacja zadań fPO+EF1 , którą można obliczyć w czasie wielomianowym. Dowodzą również, że w tym przypadku ułamkowa alokacja fPO + EF (podzielnych) zadań może być obliczona w czasie wielomianowym.
Freeman, Sikdar, Vaish i Xia przedstawiają algorytm czasu wielomianowego do obliczania alokacji dyskretnej fPO +w przybliżeniu-EQ1 dla przypadków, w których wszystkie wartościowania są potęgami (1+ e ) dla pewnej stałej e > 0. Dowodzą one, że nawet dla takich przypadków (przy co najmniej 3 różnych wycenach) może nie istnieć dyskretna fPO+EQx i dyskretna alokacja fPO+EFx .
Bai i Golz przedstawiają algorytm obliczania wektora wag w taki, że kiedy użyteczności ui _każdego agenta i są losowane i niezależnie od rozkładu (który może być różny dla różnych agentów), każdy agent i ma równe prawdopodobieństwo że w _i u _i jest większe niż wj _u j _. wszystkich innych agentów Pokazują, używając lematu Spernera , że zawsze istnieje wektor wyrównujących wag. Kiedy w jest wektorem wag wyrównawczych, w -maksymalna alokacja jest wolna od zawiści z dużym prawdopodobieństwem. Oznacza to, że z dużym prawdopodobieństwem (w odpowiednich warunkach rozkładów użyteczności) istnieje dyskretna fPO+EF .