Targ rybacki

Fisher market to model ekonomiczny przypisywany Irvingowi Fisherowi . Ma następujące składniki:

Zbiór $.$ produktów z wcześniej określonymi zapasami (zwykle znormalizowanymi tak, że podaż każdego dobra wynosi 1)
Zbiór $kupujących$ .
Dla $.$ $_$ _ _

Każdy produkt ${$ swoją cenę $\ displaystyle p_ {j}}$ ; ceny ustalane są metodami opisanymi poniżej. Cena pakietu produktów jest sumą cen produktów w pakiecie. Wiązka jest $}$ przez wektor , gdzie ${\ Displaystyle x = x_ {1}, \ kropki, x_ {m$ to ilość produkt ${\ displaystyle j}$ . Więc cena pakietu wynosi $p$ $\ suma _ {j = 1} ^ {m} p_ { j}\cdot x_{j}}$ ⋅ .

Pakiet jest dostępny dla kupującego, jeśli jego cena nie przekracza budżetu kupującego. To znaczy, pakiet jest dostępny dla kupującego $\ Displaystyle p ($ $jeśli$ p $) \ równoważnik B_ {i}}$ .

Każdy nabywca ma relację preferencji w stosunku do pakietów, którą można przedstawić za pomocą funkcji użyteczności. Funkcja użyteczności kupującego $displaystyle$ oznaczona przez $u_ {i}}$ . Zbiór popytowy nabywcy to zbiór pakietów przystępnych cenowo, które maksymalizują użyteczność nabywcy spośród wszystkich pakietów przystępnych cenowo, tj.:

${\ Displaystyle {\ tekst {popyt}} _ {i} (p): = \ arg \ max _ {p (x )\równoważnik B_{i}}u_{i}(x)}$ .

Równowaga konkurencyjna ( $CE )$ wektor ceny, każdemu agentowi pakiet zestaw popytowy, tak że całkowita alokacja jest dokładnie równa podaży produktów. Odpowiadające im ceny nazywane są cenami rozliczeniowymi . Głównym wyzwaniem w analizie rynków Fisher jest znalezienie CE.

Powiązane modele

w modelu Fisher market budżet nie ma wartości wewnętrznej – jest przydatny tylko na zakup produktów. Kontrastuje to z rynkiem walrasowskim z agentami o quasilinearnych użytecznościach , na którym pieniądz sam w sobie jest produktem i ma swoją własną wartość.
Arrow -Debreu jest uogólnieniem modelu Fishera, w którym każdy agent może być zarówno kupującym, jak i sprzedającym. Oznacza to, że każdy agent jest dostarczany z pakietem produktów, a nie tylko z pieniędzmi.
Rynki Eisenberga-Gale'a to kolejne uogólnienie liniowego rynku Fishera.

Targ rybny z podzielnymi przedmiotami

Kiedy wszystkie pozycje na rynku są podzielne, CE zawsze istnieje. Można to udowodnić za pomocą słynnego lematu Spernera .

Załóżmy, że ilości są znormalizowane, tak że na produkt przypada 1 jednostka, a budżety są znormalizowane, że ich suma wynosi 1. Załóżmy również, że wszystkie produkty są dobre, tj. agent zawsze ściśle woli mieć więcej każdego produktu, jeśli można sobie na to pozwolić.

Rozważmy standardowy simpleks z m wierzchołkami. Każdy punkt w tym simpleksie odpowiada wektorowi ceny, gdzie suma wszystkich cen wynosi 1; stąd cena wszystkich towarów razem wynosi 1.

W każdym wektorze ceny p możemy znaleźć żądany zestaw każdego agenta, następnie obliczyć sumę wszystkich żądanych zestawów, a następnie znaleźć całkowitą cenę tego zagregowanego popytu. Ponieważ cena każdego żądanego zbioru jest co najwyżej budżetem agenta, a suma budżetów wynosi co najwyżej 1, to cena zagregowanego popytu wynosi co najwyżej 1. Zatem dla każdego p istnieje co najmniej jeden produkt, dla którego całkowity popyt wynosi co najwyżej 1. Nazwijmy taki produkt „produktem drogim” w p.

Wykonaj triangulację m -vertex simplex i oznacz każdy wierzchołek triangulacji p indeksem dowolnego drogiego produktu w p . W każdej twarzy simplex niektóre produkty kosztują 0. Ponieważ wszystkie produkty są dobre, popyt każdego agenta na produkt, który kosztuje 0, wynosi zawsze 1; stąd produkt, który kosztuje 0, nigdy nie może być uważany za drogi. Zatem powyższe oznakowanie spełnia warunek brzegowy Spernera.

Na mocy lematu Spernera istnieje baby-simplex, którego wierzchołki są oznaczone m różnymi etykietami. Ponieważ funkcja popytu jest ciągła, wykonując coraz dokładniejsze triangulacje, znajdujemy pojedynczy wektor ceny p *, w którym wszystkie produkty są drogie, tj. łączny popyt na każdy produkt wynosi co najwyżej 1.

Ponieważ jednak suma wszystkich budżetów wynosi 1, zagregowany popyt na każdy produkt w p * musi wynosić dokładnie 1. Zatem p * jest wektorem cen oczyszczających rynek.

Chociaż lemat Spernera może być użyty do znalezienia CE, jest on bardzo nieefektywny obliczeniowo. Istnieją bardziej wydajne metody: zobacz Obliczanie równowagi rynkowej .

Rynki rybackie z niepodzielnymi przedmiotami

Gdy przedmioty na rynku są niepodzielne, nie ma gwarancji istnienia CE. Decydowanie, czy CE istnieje, jest trudnym obliczeniowo problemem.

Deng i wsp. badali rynek, na który każdy agent wchodzi z początkowym wyposażeniem (a nie początkowym dochodem), a wszystkie wyceny są addytywne. Udowodnili, że rozstrzygnięcie, czy CE istnieje, jest NP-trudne nawet przy 3 czynnikach. Przedstawili algorytm aproksymacyjny, który rozluźnia warunki CE na dwa sposoby: (1) pakiet przydzielony każdemu agentowi jest wyceniany co najmniej 1-epsilon optimum przy danych cenach, oraz (2) popyt jest co najmniej 1-epsilon razy Dostawa.

Bouveret i Lemaitre badali CE z równych dochodów (CEEI) jako zasadę sprawiedliwego przydziału pozycji. Powiązali to z czterema innymi kryteriami sprawiedliwości, zakładając, że wszyscy agenci mają addytywne funkcje wyceny. Zapytali, jaka jest złożoność obliczeniowa podejmowania decyzji, czy CEEI istnieje.

Na to pytanie wkrótce potem odpowiedział Aziz, który udowodnił, że problem jest słabo NP-trudny, gdy jest dwóch agentów i m elementów, i silnie NP-trudny, gdy jest n agentów i 3 n elementów. Przedstawił również silniejszy warunek zwany CEEI-FRAC, który, co ciekawe, jest łatwiejszy do zweryfikowania --- można go zweryfikować w czasie wielomianowym. Miltersen, Hosseini i Branzei udowodnili, że nawet sprawdzenie, czy dana alokacja jest CEEI, jest współ-NP-trudne. Studiowali również CEEI dla jednomyślnych agentów. W tym przypadku sprawdzenie, czy dana alokacja jest CEEI, jest wielomianem, ale sprawdzenie, czy CEEI istnieje, jest współ-NP-zupełne.

Heinen i wsp. rozszerzyli pracę Bouvereta i Lemaitre'a z addytywnych na k-addytywne funkcje użyteczności, w których każdy agent podaje wartość dla wiązek zawierających co najwyżej k pozycji, a wartości większych wiązek są określane przez dodawanie i odejmowanie wartości pakiety podstawowe.

Budish zbadał najbardziej ogólne otoczenie, w którym agenci mogą mieć dowolne relacje preferencji względem wiązek. Wynalazł mechanizm przybliżonej równowagi konkurencyjnej od równych dochodów , który rozluźnia warunki CEEI na dwa sposoby: (1) dochody agentów nie są dokładnie równe i (2) niewielka liczba pozycji może pozostać nieprzydzielona. Udowodnił, że przybliżony CEEI zawsze istnieje (chociaż Othman i wsp. niedawno udowodnili, że obliczenie przybliżonego CEEI jest zakończone PPAD ).

Barman i Krishnamurthy badają rynki Fishera, na których wszyscy agenci mają dodatkowe narzędzia. Pokazują, że ułamkową CE (gdzie niektóre towary są podzielone) zawsze można zaokrąglić do całkowitej CE (gdzie towary pozostają niepodzielne), zmieniając budżety agentów. Zmiana w każdym budżecie może być tak wysoka, jak najwyższa cena dobra w ułamkowym CE.

Babaioff, Nisan i Talgam-Cohen badali, czy CE istnieje, gdy dochody są ogólne , tj. nie spełniają skończonego zestawu równości. Innymi słowy: czy istnieje CE dla prawie wszystkich wektorów dochodów. Udowodnili istnienie trzech towarów, czterech towarów i dwóch agentów. Udowodnili nieistnienie pięciu towarów i dwóch agentów. Później okazało się, że przy czterech towarach i trzech agentach CE może nie istnieć, gdy wyceny nie są addytywne, ale zawsze istnieje, gdy wyceny są addytywne.

Zobacz też

Ogólna równowaga