Sprawiedliwy podział przedmiotów i pieniędzy

Sprawiedliwa alokacja przedmiotów i pieniędzy jest klasą problemów sprawiedliwej alokacji przedmiotów , w których podczas procesu alokacji możliwe jest dawanie lub branie pieniędzy od niektórych uczestników. Bez pieniędzy sprawiedliwy podział niepodzielnych rzeczy może być niemożliwy. Na przykład, jeśli jest jeden przedmiot i dwie osoby, a przedmiot musi być w całości przekazany jednej z nich, przydział będzie niesprawiedliwy w stosunku do drugiej osoby. Płatności pieniężne umożliwiają osiągnięcie sprawiedliwości, jak wyjaśniono poniżej.

Dwóch agentów i jeden przedmiot

Mając dwóch agentów i jeden przedmiot, możliwe jest osiągnięcie uczciwości przy użyciu następującego prostego algorytmu (który jest wariantem wycinania i wybierania ):

• Alicja podaje cenę p , którą jest gotowa zapłacić za przedmiot.
• George wybiera, czy wziąć przedmiot i zapłacić p , czy zostawić przedmiot Alicji, aby Alicja zapłaciła p .

Algorytm ten zakłada, że ​​agenci mają użyteczności quasiliniowe , to znaczy, że ich użyteczność jest wartością przedmiotów plus ilość posiadanych przez nich pieniędzy. Jeśli George myśli, że cena Alicji jest niska (jest gotów zapłacić więcej niż p ), wtedy bierze przedmiot i płaci p , a jego użyteczność jest dodatnia, więc nie zazdrości Alicji. Alicja również nie zazdrości George'owi, ponieważ jego użyteczność - w jej oczach - wynosi 0. Podobnie, jeśli George uważa, że ​​cena Alicji jest wysoka (jest skłonny zapłacić p lub więcej), to zostawia przedmiot Alicji i nie zazdrość, ponieważ użyteczność Alicji w jego oczach jest negatywna.

Zapłacone pieniądze p można później równo podzielić między graczy, ponieważ równy transfer pieniężny nie wpływa na względne użyteczności. Następnie agent kupujący płaci p /2 agentowi sprzedającemu. Całkowita użyteczność każdego agenta wynosi co najmniej 1/2 jego/jej użyteczności dla przedmiotu. Jeżeli agenci mają różne uprawnienia , to wypłaconą kwotę p należy podzielić między wspólników proporcjonalnie do ich uprawnień.

Istnieją różne prace rozszerzające ten prosty pomysł na więcej niż dwóch graczy i bardziej złożone ustawienia. Głównym kryterium słuszności w tych pracach jest brak zazdrości . Ponadto niektóre prace rozważają ustawienie, w którym życzliwa strona trzecia jest skłonna dotować przydział, ale chce zminimalizować kwotę dotacji podlegającej zazdrości. Ten problem nazywa się alokacją wolną od zazdrości przy minimalnych dotacjach .

Agenci żądający jednostek

Agenci popytu jednostkowego są zainteresowani co najwyżej pojedynczym przedmiotem.

Harmonia wynajmu

Szczególnym przypadkiem tego ustawienia jest podział pomieszczeń w mieszkaniu między lokatorów. Charakteryzuje się trzema wymaganiami: (a) liczba agentów jest równa liczbie przedmiotów, (b) każdy agent musi otrzymać dokładnie jeden przedmiot (pokój), (c) łączna kwota pieniędzy zapłacona przez agentów musi być równa ustalonej stała, która reprezentuje całkowity czynsz za mieszkanie. Jest to znane jako Harmonii wynajmu .

Bardziej ogólne ustawienia

Generalnie w literaturze ekonomicznej przyjmuje się, że każdy agent ma funkcję użyteczności na wiązkach (wiązka to para przedmiotu i pewnej ilości pieniędzy). Funkcja użyteczności powinna być ciągła i rosnąca w pieniądzu. Nie musi być liniowy w pieniądzu, ale musi być „archimedesowy”, tj. istnieje taka wartość V , że dla każdych dwóch obiektów j i k użyteczność obiektu j plus V powinna być większa niż użyteczność przedmiotu k (alternatywnie, użyteczność otrzymania przedmiotu j za darmo jest większa niż użyteczność otrzymania przedmiotu k i zapłacenia V ). Użyteczność quasiliniowa jest szczególnym przypadkiem użyteczności Archimedesa, w której V jest największą różnicą wartości (dla tego samego agenta) między dwoma obiektami.

Svensson po raz pierwszy udowodnił, że gdy wszyscy agenci są Archimedesami, istnieje alokacja wolna od zawiści i jest optymalna w sensie Pareto.

Demange, Gale i Sotomayor pokazali naturalną aukcję rosnącą, która osiąga wolną od zazdrości alokację przy użyciu płatności pieniężnych dla agentów popytu jednostkowego.

Maskin udowodnił istnienie optymalnej alokacji wolnej od zazdrości w sensie Pareto, gdy całkowite wyposażenie pieniężne jest większe niż ( n-1 ) V. Dowody wykorzystują równowagę konkurencyjną .

Zauważ, że może być wymagana dotacja w wysokości ( n -1) V : jeśli wszyscy agenci wyceniają pojedynczy przedmiot na V , a inne na 0, to brak zazdrości wymaga subsydium w wysokości V dla każdego agenta, który nie otrzymuje przedmiotu.

Tadenuma i Thomson badają kilka właściwości spójności reguł alokacji wolnej od zazdrości.

Aragones charakteryzuje minimalną kwotę dotacji wymaganą do uwolnienia się od zawiści. Alokacja, która osiąga tę minimalną dotację, jest prawie wyjątkowa: istnieje tylko jeden sposób łączenia obiektów z agentami, a wszyscy agenci są obojętni na wszystkie alokacje z minimalną dotacją. Zbiega się to z rozwiązaniem zwanym „rozwiązaniem pieniężno-rawlsowskim” Alkana, Demange'a i Gale'a. Można go znaleźć w czasie wielomianowym, znajdując dopasowanie o maksymalnej wadze, a następnie znajdując najkrótsze ścieżki w pewnym indukowanym grafie.

Klijn przedstawia inny algorytm czasu wielomianowego dla tego samego ustawienia. Jego algorytm wykorzystuje polytope płatności pobocznych, które sprawiają, że dana alokacja jest wolna od zazdrości: ta polytope jest niepusta, jeśli pierwotna alokacja jest efektywna w sensie Pareto. Łączność nieukierunkowanego wykresu zazdrości charakteryzuje skrajne punkty tego polytopu. Oznacza to metodę znajdowania przydziałów wolnych od zazdrości.

Dodatki

Dodatkowi agenci mogą otrzymać kilka obiektów, więc problem alokacji staje się bardziej złożony - możliwych alokacji jest znacznie więcej.

Aukcja firmy Knaster

Pierwszą procedurę sprawiedliwego podziału dóbr i pieniędzy wymyślił Bronisław Knaster i opublikował Hugo Steinhaus . Ta aukcja działa w następujący sposób, dla każdego przedmiotu osobno:

• Każdy agent składa ofertę na przedmiot.
• Przedmiot jest przekazywany temu, kto zaoferuje najwyższą cenę (arbitralne zerwanie więzi).
• Zwycięzca płaci ( n -1)/ n swojej oferty;
• Każdy z pozostałych agentów otrzymuje 1/ n swojej oferty;
• Ponieważ zwycięzcą jest oferent, który zaoferował najwyższą cenę, istnieje nieujemna nadwyżka; nadwyżka jest dzielona równo między agentów.

Użyteczność każdego agenta wynosi co najmniej 1/ n wartości, jaką przypisuje on całemu zbiorowi obiektów, więc alokacja jest proporcjonalna . Ponadto alokacja maksymalizuje sumę użyteczności, a więc jest efektywna w sensie Pareto .

Aukcja Knastera nie jest strategiczna . Niektórzy badacze analizowali jego wydajność, gdy agenci grają strategicznie:

• Essen udowadnia, że ​​alokacja równowagi jest nadal efektywna w sensie Pareto, ale może nie być proporcjonalna ex post. Jednak średnio agenci uzyskują taki sam wynik, jak gdyby wszyscy byli prawdomówni. Oznacza to, że mechanizm jest proporcjonalny ex ante.
• Fragnelli i Marina pokazują, że nawet agenci, którzy są nieskończenie niechętni ryzyku, mogą bezpiecznie zyskać poprzez wspólne błędne raportowanie swoich wycen, niezależnie od deklaracji innych agentów.

Aukcja firmy Knaster została dostosowana do sprawiedliwego przydziału kanałów bezprzewodowych.

Aukcja Raitha

Matthias G. Raith przedstawił wariant aukcji Knastera, który nazwał „Adjusted Knaster”. Podobnie jak w licytacji Knaster, każdy przedmiot jest przekazywany temu, kto zaoferuje najwyższą cenę. Jednak płatności są różne. Płatności są ustalane w następujący sposób:

• Każdy agent wygrywający przedmiot płaci swoją ofertę za ten przedmiot;
• Całkowita kwota pieniędzy zapłacona przez agentów jest dzielona między nich proporcjonalnie do ich ofert.

Aby zilustrować różnicę między aukcją Knastera a aukcją Raitha, rozważmy ustawienie z dwoma przedmiotami i dwoma agentami o następujących wartościach:

	Przedmiot 1	Pozycja 2	Suma
Alicja	10	10	20
Jerzy	60	120	180

W obu aukcjach Jerzy wygrywa oba przedmioty, ale płatności są różne:

• Na aukcji Knastera George płaci 90, Alicja otrzymuje 10, a różnica 80 jest dzielona równo, więc użyteczność netto wynosi 50, 130.
• W aukcji Raitha George płaci 180 i dzieli się to w stosunku 20:180 = 1:9, czyli Alice dostaje 18, a George 162. Zauważ, że płatności są obliczane dla wszystkich przedmiotów na raz - nie dla każdego przedmiotu z osobna.

W eksperymentach na ludziach stwierdzono, że uczestnicy wolą aukcję Raitha (Dostosowany Knaster) niż Podziel i Wybierz oraz Knaster Proporcjonalny (wariant, w którym każdy zwycięzca płaci 1/n wygranej każdemu przegranemu; w powyższym na przykład George płaci Alicji 90, a media netto wynoszą 90, 90).

Procedura kompensacyjna

Haake, Raith i Su przedstawiają procedurę kompensacyjną. Ich procedura dopuszcza arbitralne ograniczenia dotyczące pakietów przedmiotów, o ile są one anonimowe (nie rozróżniają partnerów na podstawie ich tożsamości). Na przykład nie może istnieć żadne ograniczenie lub może istnieć takie ograniczenie, jak „każdy partner musi otrzymać przynajmniej określoną liczbę przedmiotów” lub „niektóre elementy muszą być połączone razem” (np. ponieważ są to działki, które muszą pozostać połączone) itp. „Przedmioty” mogą mieć zarówno pozytywne, jak i negatywne użyteczności. Istnieje „wymóg kwalifikacyjny” dla partnera: suma jego ofert musi być co najmniej równa kosztowi całkowitemu. Procedura działa w następujących krokach.

1. Znajdź alokację o sumie maksymalnej ( utylitarnej ) — alokację o najwyższej sumie użyteczności, która spełnia ograniczenia na wiązkach przedmiotów. Jeśli nie ma żadnych ograniczeń, to alokacja, która przydziela każdą pozycję partnerowi z najwyższą wyceną, to maxsum. Jeśli istnieją ograniczenia (takie jak „co najmniej jedna pozycja na partnera”), znalezienie maksymalnej sumy może być trudniejsze do znalezienia.
2. Pobieraj od każdego partnera wartość przydzielonego mu pakietu. Tworzy to początkową pulę pieniędzy.
3. Zapłać koszt z początkowej puli. Jeśli wszyscy partnerzy spełniają wymagania kwalifikacyjne, wówczas środki w puli są wystarczające i może pozostać pewna nadwyżka .
4. Wyeliminuj zazdrość, wynagradzając zazdrosnym partnerom. Istnieje $rund$ . Procedura jest w pełni opisowa i wyraźnie mówi, jakie rekompensaty należy wypłacić iw jakiej kolejności. Co więcej, jest na tyle prosty, że można go przeprowadzić bez wsparcia komputera.
5. Suma kompensacji dokonanych we wszystkich rundach jest najmniejszą sumą potrzebną do wyeliminowania zazdrości i nigdy nie przekracza nadwyżki. Jeśli zostanie jakaś nadwyżka, można ją podzielić w dowolny sposób, który nie budzi zazdrości, np. dając każdemu partnerowi równą kwotę (w artykule omówiono inne opcje, które można uznać za „sprawiedliwsze”).

Gdy istnieje wiele elementów i złożonych ograniczeń, początkowy krok – znalezienie alokacji maksymalnej sumy – może być trudny do obliczenia bez komputera. W takim przypadku Procedura Odszkodowawcza może rozpocząć się od arbitralnego przydziału. W takim przypadku procedura może zakończyć się alokacją zawierającą cykle zazdrości . Cykle te można usunąć, przesuwając wiązki wzdłuż cyklu, jak w procedurze wykresu zazdrości . To ściśle zwiększa całkowitą sumę mediów. Dlatego po ograniczonej liczbie iteracji zostanie znaleziona alokacja sumy maksymalnej, a procedura może być kontynuowana jak powyżej, aby utworzyć alokację wolną od zazdrości.

Procedura kompensacyjna może obciążyć niektórych partnerów płatnością ujemną (tj. dać partnerom dodatnią kwotę pieniędzy). Autorzy mówią:

„nie wykluczamy możliwości, że jednostka może otrzymać zapłatę od innych za wzięcie paczki towarów. W kontekście sprawiedliwego podziału nie uważamy tego za problematyczne. Rzeczywiście, jeśli grupa nie chce wykluczyć któregokolwiek ze swoich członków, to nie ma powodu, dla którego grupa nie miałaby dotować członka za otrzymanie niepożądanej paczki. Ponadto wymóg kwalifikacyjny gwarantuje, że subsydiowanie nigdy nie jest konsekwencją niedostatecznej wyceny przez gracza kompletu obiektów do Rozpowszechniane".

Minimalne procedury dotacyjne

Niektóre prace zakładają, że życzliwa osoba trzecia jest skłonna dotować alokację, ale chce zminimalizować kwotę dotacji podlegającej zazdrości. Ten problem nazywa się alokacją wolną od zazdrości przy minimalnych dotacjach .

Halpern i Shah badają minimalizację dotacji w ogólnym ustawieniu alokacji przedmiotów. Rozważają dwa przypadki:

1. Alokacja jest podawana z góry. W tym przypadku jest „wolny od zazdrości” wtedy i tylko wtedy, gdy maksymalizuje sumę użyteczności we wszystkich zmianach przypisań swoich pakietów do agentów, wtedy i tylko wtedy, gdy jego wykres zazdrości nie ma cykli. Cenę wolną od zazdrości przy minimalnym subsydium można obliczyć w silnie wielomianowym czasie, konstruując ważony wykres zazdrości i podając każdemu agentowi i cenę równą maksymalnej wadze ścieżki wychodzącej z i . Waga każdej ścieżki jest co najwyżej sumą m warunków, z których każdy jest wartością jakiegoś agenta dla jakiegoś dobra. W szczególności, jeśli wartość każdego dobra dla każdego agenta wynosi co najwyżej V , to waga każdej ścieżki wynosi co najwyżej mV . Ponieważ zawsze możemy obniżyć ceny tak, że jeden agent otrzyma zerową dotację, wynika z tego, że zawsze istnieje wolna od zazdrości alokacja z dotacją co najwyżej ( n -1) mV . Ta dotacja może być konieczna np. gdy wszystkie towary są identyczne i jeden agent je wszystkie otrzymuje.
2. Alokacja może być wybrana. W takim przypadku dotacja w wysokości ( n -1) V jest wystarczająca w następujących przypadkach:
   • Gdy wyceny agentów są binarne (0 lub 1). Wtedy dowolna alokacja produktu maksymalnego lub optymalna leksyminy wymaga co najwyżej ( n -1) subsydium V i można ją znaleźć w czasie wielomianowym. Obliczenie minimalnej dotacji wymaganej do osiągnięcia EF jest równoważne Turingowi ze sprawdzeniem istnienia alokacji wolnej od zazdrości, która jest NP-trudna, gdy jest ograniczona do niemarnotrawnych alokacji.
   • Gdy wszyscy agenci mają taką samą wycenę addytywną. Wtedy każdy przydział jest wolny od zazdrości. W czasie wielomianowym można znaleźć alokację, która wymaga co najwyżej ( n -1) subsydium V. Alokacja minimalizuje dotację, jeśli minimalizuje maksymalną użyteczność dla dowolnego agenta. Obliczenie takiej alokacji jest NP-trudne i można je rozwiązać za pomocą algorytmu maksymalnego produktu.
   • Gdy jest dwóch agentów, alokacja pozycji z każdym z każdym z określonym agentem zamawiającym znajduje alokację wolną od zazdrości z subsydiami co najwyżej V.

Brustle, Dippel, Narayan, Suzuki i Vetta poprawiają górne granice wymaganej dotacji:

• Przy wycenach addytywnych dotacja w wysokości co najwyżej V na agenta i co najwyżej ( n -1) V w ogóle jest zawsze wystarczająca. Co więcej, istnieje alokacja osiągająca tę granicę, która jest również EF1 i zbilansowana (liczność przydzielonych wiązek różni się co najwyżej o jedno dobro). Można to obliczyć w czasie wielomianowym za pomocą prostego algorytmu: iteracyjnie znajdź dopasowanie maksymalnej wagi w grafie dwudzielnym agent-obiekt .
• Przy ogólnych wycenach monotonicznych dotacja w wysokości co najwyżej 2( n -1) V na agenta i co najwyżej O( n ² V ) jest zawsze wystarczająca. W szczególności wymagana dotacja nie jest uzależniona od liczby obiektów. Alokacja osiągająca tę granicę może być obliczona w czasie wielomianowym przy użyciu zapytań o wartość.

Caragiannis i Ioannidis badają obliczeniowy problem minimalizacji dotacji:

• Dla stałej liczby agentów przedstawiają algorytm przybliżający minimalną kwotę dotacji z dowolną wymaganą dokładnością. Dla dowolnego $OPT+\varepsilon \cdot S$ > > 0, it finds an allocation with subsidy at most , where S is the maximum value that an agent assigns to all objects. The algorithm uses dynamic programming and runs in time $O((m/\varepsilon )^{n^{2}+1})$.
• Dla zmiennej liczby agentów trywialny algorytm aproksymacji osiąga ${\ Displaystyle OPT + (n-1) \ cdot S}$ . Jednak osiągnięcie współczynnika przybliżenia niezależnego od n jest trudne: obliczenie alokacji z dotacją co najwyżej jest NP-trudne. ${\ Displaystyle OPT + 3 \ cdot 10 ^ {-4} \cdot S}$ . Dowód polega na redukcji z ograniczonego wariantu maksymalnego dopasowania trójwymiarowego , w którym każdy wierzchołek występuje dokładnie dwa razy.

Zauważ, że przydział wolny od zazdrości z subsydiami pozostaje wolny od zazdrości, jeśli od każdego agenta zostanie pobrana stała kwota. W związku z tym podobne metody można wykorzystać do znalezienia alokacji, które nie są dotowane:

• Obciążenie każdego agenta średnią opłatą daje przydział wolny od zazdrości, który jest również zrównoważony budżetowo . Minimalizowanie dotacji jest równoznaczne z minimalizowaniem maksymalnej kwoty, jaką musi zapłacić pojedynczy agent.
• Możliwe jest również zastosowanie ujemnej dotacji (podatku), przy jednoczesnej minimalizacji łącznej kwoty, którą muszą zapłacić wszyscy agenci.

Dodatkowe procedury

Alkan, Demange i Gale wykazali, że alokacja wolna od zazdrości istnieje zawsze, gdy ilość pieniędzy jest wystarczająco duża. Dzieje się tak nawet wtedy, gdy pozycje mogą mieć ujemne wyceny.

Meertens, Potters i Reijnierse dowodzą istnienia wolnych od zazdrości i optymalnych w sensie Pareto alokacji przy bardzo łagodnych założeniach dotyczących wycen (niekoniecznie quasiliniowych).

Cavallo uogólnia tradycyjne binarne kryteria braku zazdrości, proporcjonalności i wydajności (dobrobytu) do miar stopnia z zakresu od 0 do 1. W kanonicznych ustawieniach sprawiedliwego podziału, w ramach dowolnego mechanizmu efektywnego alokacyjnie, wskaźnik dobrobytu w najgorszym przypadku wynosi 0 a wskaźnik nieproporcjonalności wynosi 1; innymi słowy, najgorsze wyniki są tak złe, jak to tylko możliwe. Poszukuje mechanizmu, który zapewnia wysoki dobrobyt, niską zazdrość i niską dysproporcję oczekiwań w całym spektrum ustawień sprawiedliwego podziału. Mechanizm VCG nie jest zadowalającym kandydatem, ale mechanizm redystrybucji Baileya i Cavallo jest.

Powiązane problemy

Ceny bez zazdrości

Przy sprzedaży przedmiotów kupującym suma płatności nie jest z góry ustalona, ​​a celem jest maksymalizacja albo przychodu sprzedającego, albo dobrobytu społecznego, z zastrzeżeniem braku zazdrości. Dodatkowo liczba przedmiotów może być inna niż liczba agentów, a niektóre przedmioty mogą zostać odrzucone. Jest to znane jako cen bez zazdrości .

Cele wielowymiarowe

Często poza sprawiedliwością trzeba osiągnąć inne cele. Na przykład, przydzielając zadania agentom, wymagane jest zarówno unikanie zazdrości, jak i minimalizowanie makepan ( - czasu wykonania ostatniego agenta). Mu'alem przedstawia ogólne ramy problemów optymalizacyjnych z gwarancją braku zazdrości, która w naturalny sposób rozszerza uczciwą alokację przedmiotów za pomocą płatności pieniężnych.

Aziz dąży do osiągnięcia, za pomocą transferów pieniężnych, alokacji, która jest zarówno wolna od zawiści, jak i sprawiedliwa . Bada nie tylko addytywne użyteczności dodatnie, ale także wszelkie użyteczności nadaddytywne , zarówno dodatnie, jak i ujemne:

• W przypadku narzędzi superaddytywnych istnieje algorytm czasu wielomianowego, który zapewnia brak zazdrości, równość i równowagę budżetową (łatwo jest zamienić saldo budżetowe na dotację).
• Jeśli dana alokacja jest konwertowalna na EFEQ, to minimalną dotację wymaganą, aby była to EF+EQ, można znaleźć w czasie liniowym.
• Znalezienie alokacji, która jest wymienialna na EFEQ przy minimalnej dotacji, jest NP-trudne i nie można jej przybliżyć w ramach żadnego pozytywnego czynnika. Dzieje się tak po prostu dlatego, że sprawdzenie istnienia alokacji EF (która wymaga 0 dotacji) jest NP-trudne.
• Dotacja w wysokości co najwyżej ( n -1) mV jest zawsze wystarczająca i może być konieczna niezależnie od tego, czy alokacja została przyznana, czy nie.

Zobacz też

• Alokacja przedmiotów bez zazdrości - ustawienie bez przelewów pieniężnych.