Fisherův trh - Fisher market

Fisherův trh je ekonomický model přičítáno Irving Fisher. Má následující přísady:^[1]

• Sada ${ displaystyle m}$ dělitelné produkty s předem stanoveným množstvím (obvykle normalizované tak, že množství každého zboží je 1).
• Sada ${ displaystyle n}$ kupující.
• Pro každého kupujícího ${ displaystyle i = 1, tečky, n}$, existuje předem stanovený peněžní rozpočet ${ displaystyle B_ {i}}$(obvykle normalizováno tak, že součet rozpočtů je 1).

V modelu Fisher nemá rozpočet žádnou vlastní hodnotu - je užitečný pouze pro nákup produktů. To je na rozdíl od a kvazilineární nástroj model, ve kterém jsou peníze samy o sobě produktem a mají svou vlastní hodnotu.

Každý produkt ${ displaystyle j}$ má cenu ${ displaystyle p_ {j}}$; ceny jsou určovány metodami, které popisujeme níže. Cena a svazek produktů je součet cen produktů v balíčku. Balíček je reprezentován vektorem ${ displaystyle x = x_ {1}, dots, x_ {m}}$, kde ${ displaystyle x_ {j}}$ je množství produktu ${ displaystyle j}$. Takže cena balíčku ${ displaystyle x}$ je ${ displaystyle p (x) = součet _ {j = 1} ^ {m} p_ {j} cdot x_ {j}}$.

Balíček je cenově dostupné pro kupujícího, pokud cena tohoto balíčku je maximálně rozpočet kupujícího. Tj. Svazek ${ displaystyle x}$ je pro kupujícího cenově dostupný ${ displaystyle i}$ -li ${ displaystyle p (x) leq B_ {i}}$.

Každý kupující má preferenční vztah přes svazky, které mohou být reprezentovány užitnou funkcí. Užitková funkce kupujícího ${ displaystyle i}$ je označen ${ displaystyle u_ {i}}$. The sada poptávky kupujícího je sada dostupných balíčků, které maximalizují užitek kupujícího mezi všemi dostupnými balíčky, tj .:

${ displaystyle { text {Demand}} _ {i} (p): = arg max _ {p (x) leq B_ {i}} u_ {i} (x)}$.

A konkurenční rovnováha (CE) je cenový vektor ${ displaystyle p_ {1}, tečky, p_ {m}}$ve kterém je možné každému agentovi přidělit balíček z jeho sady poptávky, takže celková alokace se přesně rovná nabídce produktů. Vyvolávají se odpovídající ceny ceny zúčtování trhu. Hlavní výzvou při analýze rybářských trhů je nalezení CE.^{[2]:103–105}

Existence konkurenční rovnováhy

Existenci CE lze prokázat na základě slavného Spernerovo lemma.^[3]:67

Předpokládejme, že množství je normalizováno tak, že na jeden produkt připadá 1 jednotka a rozpočty jsou normalizovány tak, že jejich součet je 1. Předpokládejme také, že všechny produkty jsou dobré, tj. Agent vždy striktně upřednostňuje mít více z každého produktu může si to dovolit.

Zvažte standardní simplex s m vrcholy. Každý bod v tomto simplexu odpovídá cenovému vektoru, kde součet všech cen je 1; proto je cena veškerého zboží společně 1.

V každém cenovém vektoru p, můžeme najít požadovanou sadu každého agenta, poté vypočítat součet všech požadovaných sad a poté zjistit celkovou cenu této agregované poptávky. Protože cena každé požadované sady je nanejvýš rozpočet agenta a součet rozpočtů je nanejvýš 1, cena agregované poptávky je nanejvýš 1. Proto pro každou p, existuje alespoň jeden produkt, u kterého je celková poptávka nejvýše 1. Pojďme tento produkt označit jako „drahý produkt“ p.

Triangulujte m-vertex simplex a označte každý triangulační vrchol p s indexem libovolného nákladného produktu v p. Na každé straně simplexu stojí některé produkty 0. Protože jsou všechny produkty dobré, poptávka každého agenta po produktu, který stojí 0, je vždy 1; produkt, který stojí 0, proto nelze nikdy považovat za drahý. Výše uvedené označení tedy splňuje okrajovou podmínku Spernera.

U Spernerova lemmatu existuje dětský simplex, jehož vrcholy jsou označeny m různé štítky. Protože funkce poptávky je spojitá, pomocí jemnějších a jemnějších triangulací najdeme jediný cenový vektor p*, ve kterém jsou všechny produkty drahé, tj. agregátní poptávka po nich každý produkt je maximálně 1.

Ale protože součet všech rozpočtů je 1, souhrnná poptávka po každém produktu v p* musí být přesně 1. Proto p* je vektor cen za zúčtování trhu.

Výpočet konkurenční rovnováhy

I když lze k nalezení CE použít Spernerovo lemma, je výpočetně velmi neefektivní. Existují mnohem efektivnější metody, na kterých jsou obvykle založeny konvexní programování nebo lineární programování.

Homogenní nástroje

Předpokládejme, že nástroje všech kupujících jsou homogenní funkce (to zahrnuje zejména nástroje s konstantní pružnost substituce ).

Potom lze podmínky rovnováhy v Fisherově modelu zapsat jako řešení a konvexní optimalizace program zvaný Konvexní program Eisenberg-Gale.^[4] Tento program najde alokaci, která maximalizuje vážený geometrický průměr nástrojů kupujících, kde váhy určují rozpočty. Ekvivalentně maximalizuje vážený aritmetický průměr logaritmů obslužných programů:

Maximalizovat ${ displaystyle sum _ {i = 1} ^ {n} left (B_ {i} cdot log {(u_ {i})} right)}$

Předmět:

Nezáporná množství: Pro každého kupujícího ${ displaystyle i}$ a produkt ${ displaystyle j}$: ${ displaystyle x_ {i, j} geq 0}$

Dostatečné zásoby: Pro každý produkt ${ displaystyle j}$: ${ displaystyle sum _ {i = 1} ^ {n} x_ {i, j} leq 1}$

(protože dodávky jsou normalizovány na 1).

Tento problém s optimalizací lze vyřešit pomocí Karush – Kuhn – Tuckerovy podmínky (KKT). Tyto podmínky zavádějí Lagrangeovy multiplikátory, které lze interpretovat jako ceny, ${ displaystyle p_ {1}, tečky, p_ {m}}$. Při každé alokaci, která maximalizuje program Eisenberg-Gale, obdrží každý kupující požadovaný balíček. Tj. Řešení programu Eisenberg-Gale představuje tržní rovnováhu.^{[5]:141–142}

Lineární nástroje

Zvláštní případ homogenních služeb je, když mají všichni kupující lineární užitečnost funkce. To znamená, že pro každého kupujícího ${ displaystyle i}$ a produkt ${ displaystyle j}$, existuje konstanta ${ displaystyle u_ {i, j}}$ (užitečnost kupujícího ${ displaystyle i}$ pro produkt ${ displaystyle j}$) taková, že celková užitečnost, kterou kupující získá ze svazku, je:

${ displaystyle u_ {i} (x_ {1}, tečky, x_ {j}) = součet _ {j = 1} ^ {m} u_ {i, j} cdot x_ {j}}$, kde ${ displaystyle u_ {i, j} geq 0}$

Předpokládáme, že každý produkt má potenciální kupující - kupující, který má z tohoto produktu pozitivní užitek. Za tohoto předpokladu existují ceny clearingového trhu, které jsou jedinečné. Důkaz je založen na programu Eisenberg-Gale. Podmínky KKT naznačují, že optimální řešení (alokace ${ displaystyle x_ {i, j}}$ a ceny ${ displaystyle p_ {j}}$) uspokojit následující nerovnosti:

1. Všechny ceny jsou nezáporné: ${ displaystyle p_ {j} geq 0}$.
2. Pokud má produkt kladnou cenu, je vyčerpána veškerá jeho nabídka: ${ displaystyle p_ {j}> 0 implikuje součet _ {i = 1} ^ {n} x_ {i, j} = 1}$.
3. Celková užitná hodnota za minci kupujícího (celková užitná hodnota vydělená celkovým rozpočtem) je slabě větší než jeho užitná hodnota za každou minci u každého produktu: ${ displaystyle { frac { suma _ {k = 1} ^ {m} u_ {i, k} cdot x_ {i, k}} {B_ {i}}} geq { frac {u_ {i , j}} {p_ {j}}}}$
4. Pokud kupující koupí kladné množství produktu, jeho celková užitná hodnota za minci se rovná jeho užitné hodnotě za minci z daného produktu: ${ displaystyle x_ {i, j}> 0 implikuje { frac { sum _ {k = 1} ^ {m} u_ {i, k} cdot x_ {i, k}} {B_ {i}} } = { frac {u_ {i, j}} {p_ {j}}}}$

Předpokládejme, že každý produkt ${ displaystyle j}$ má potenciálního kupce - kupujícího ${ displaystyle i}$ s ${ displaystyle u_ {i, j}> 0}$. Z toho potom vyplývá nerovnost 3 ${ displaystyle p_ {j}> 0}$tj. všechny ceny jsou kladné. Potom nerovnost 2 znamená, že jsou vyčerpány všechny zásoby. Nerovnost 4 znamená, že jsou vyčerpány rozpočty všech kupujících. Tj. Trh se vyčistí.

Protože funkce protokolu je přísně konkávní funkce, pokud existuje více než jedna rovnovážná alokace, pak užitek odvozený každým kupujícím v obou alokacích musí být stejný (pokles užitku kupujícího nelze kompenzovat zvýšením užitku jiného kupujícího). To spolu s nerovností 4 znamená, že ceny jsou jedinečné.^[2]:107

Slabý algoritmus polynomiálního času

Pro nalezení rovnovážných cen a alokací na lineárním Fisherově trhu existuje algoritmus slabého polynomiálního času. Algoritmus je založen na podmínce 4 výše. Podmínka znamená, že v rovnováze každý kupující kupuje pouze produkty, které mu poskytují maximální užitek na jednu minci. Řekněme, že kupující produkt „má rád“, pokud mu tento produkt poskytuje maximální užitek na jednu minci v současných cenách. Vzhledem k cenovému vektoru můžeme postavit a toková síť ve kterém kapacita každé hrany představuje celkové peníze „tekoucí“ touto hranou. Síť je následující:

• Existuje zdrojový uzel, s.
• Pro každý produkt existuje uzel; je tu hrana z s ke každému produktu j, s kapacitou ${ displaystyle p_ {j}}$ (toto je maximální částka peněz, kterou lze za produkt vynaložit j, protože nabídka je normalizována na 1).
• Pro každého kupujícího existuje uzel; existuje výhoda od produktu kupujícímu s nekonečnou kapacitou, pokud se kupujícímu produkt líbí (v aktuálních cenách).
• Existuje cílový uzel, t; od každého kupujícího existuje výhoda i na t, s kapacitou ${ displaystyle B_ {i}}$ (maximální výdaje i).

Cenový vektor p je rovnovážný cenový vektor, právě když dva škrty ({s}, V {s}) a (V {t}, {t}) jsou minimální řezy. Rovnovážný cenový vektor lze tedy nalézt pomocí následujícího schématu:

• Začněte s velmi nízkými cenami, u nichž je zaručeno, že budou pod rovnovážnými cenami; v těchto cenách kupujícím zbývá nějaký rozpočet (tj. maximální tok nedosahuje kapacity uzlů do t).
• Neustále zvyšujte ceny a odpovídajícím způsobem aktualizujte síť toku, dokud nebudou vyčerpány všechny rozpočty.

Existuje algoritmus, který řeší tento problém ve slabě polynomiálním čase.^{[2]:109–121}

Rybářské trhy s nedělitelnými předměty

Zatímco původní model předpokládal, že všechny produkty jsou dělitelné, existuje varianta trhu Fisher, u které se položky považují za nedělitelné. V této variantě je nalezení konkurenční rovnováhy výpočetně těžké.

Deng a kol^[6] studoval trh, na který každý agent přichází s počátečním vybavením (spíše než s počátečním příjmem) a všechna ocenění jsou aditivní. Dokázali, že rozhodování o tom, zda existuje CE, je NP těžké i se 3 agenty. Představili algoritmus aproximace, který uvolňuje podmínky CE dvěma způsoby: (1) Balíček přidělený každému agentovi má hodnotu alespoň 1 epsilon optima vzhledem k cenám a (2) poptávka je alespoň 1 epsilonkrát zásoba.

Bouveret a Lemaitre^[7] studoval CE-od-stejných příjmů (CEEI) jako pravidlo pro spravedlivé rozdělení položek. Vztahovali to ke čtyřem dalším kritériím spravedlnosti za předpokladu, že všichni agenti mají aditivní oceňovací funkce. Ptali se, jaká je výpočetní složitost rozhodování o tom, zda existuje CEEI.

Na tuto otázku Aziz brzy nato odpověděl,^[8] kdo dokázal, že problém je slabě NP-těžký, když existují dva agenti a m předměty a silně NP-tvrdé, pokud existují n agenti a 3n položky. Představil také silnější stav zvaný CEEI-FRAC, který je zajímavě snadněji ověřitelný - lze jej ověřit v polynomiálním čase. Miltersen, Hosseini a Branzei^[9] dokázal, že i ověření, zda je daná alokace CEEI, je co-NP tvrdé. Studovali CEEI také pro jednostranné agenty. V tomto případě je ověření, zda je daná alokace CEEI polynomiální, ale kontrola, zda existuje CEEI, je úplná společně.

Heinen a kol^[10] rozšířil práci Bouvereta a Lemaitre z aditiva na k-aditivní obslužné funkce, ve kterém každý agent hlásí hodnotu pro svazky obsahující nejvýše k položek a hodnoty větších svazků jsou určeny sečtením a odečtením hodnot základních svazků.

Budiš^[11] studoval nejobecnější nastavení, ve kterém mohou mít agenti libovolné preferenční vztahy nad svazky. Vynalezl mechanismus Přibližná konkurenční rovnováha ze stejných příjmů, což uvolňuje podmínky CEEI dvěma způsoby: (1) Příjmy agentů nejsou přesně stejné a (2) malý počet položek může zůstat nepřidělen. Dokázal, že vždy existuje přibližná CEEI (ačkoli Othman et al^[12] nedávno prokázal, že výpočet přibližné CEEI je PPAD kompletní ).

Barman a Krishnamurthy^[13] prostudujte si Fisherovy trhy, kde mají všichni agenti aditivní nástroje Ukazují, že zlomek CE (kde je některé zboží rozděleno) lze vždy zaokrouhlit na integrální CE (kde zboží zůstává nedělitelné), změnou rozpočtů agentů. Změna v každém rozpočtu může být stejně vysoká jako největší cena statku ve zlomku CE.

Babaioff, Nisan a Talgam-Cohen^[14] studoval, zda existuje CE, když jsou příjmy obecný, tj. neuspokojují konečný soubor rovností. Jinými slovy: zda existuje CE pro téměř všechny příjmové vektory. Prokázali existenci pro tři zboží a pro čtyři zboží a dva agenty. U pěti zboží a dvou agentů prokázali neexistenci. Později se ukázalo, že se čtyřmi statky a třemi agenty nemusí CE existovat, když jsou ocenění neaditivní, ale vždy existuje, když jsou ocenění aditivní.^[15]

Viz také

• The Šipka – Debreuův model je zobecněním Fisherova modelu, ve kterém může být každý agent kupujícím i prodávajícím. Každý agent přichází s balíčkem produktů, nikoli pouze s penězi.
• Obecná rovnováha
• Trhy Eisenberg – Gale - další zobecnění lineárního Fisherova trhu.^[16]

Reference