Aukce Jan Mysliveček Přf Muni 3.října 2008 Jan Mysliveček (Přf Muni) 3/10 1 / 15 Aukce Jak optimálně prodat předmět o neznámé hodnotě? Jan Mysliveček (Přf Muni) 3/10 2 / 15 Aukce Jak optimálně prodat předmět o neznámé hodnotě? Jediný předmět Jediný prodávající Mnoho zájemců Běžně používaný způsob prodeje (ropná pole, umělecké předměty) Mnoho druhů aukcí Jan Mysliveček (Přf Muni) 3/10 2 / 15 Aukce Jak optimálně prodat předmět o neznámé hodnotě? Jediný předmět Jediný prodávající Mnoho zájemců Běžně používaný způsob prodeje (ropná pole, umělecké předměty) Mnoho druhů aukcí Jak " hrají" racionální hráči? Jak se liší příjem (zisk) vlastníka aukce při různých aukcích? Jan Mysliveček (Přf Muni) 3/10 2 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Každý hráč podá vlastní nabídku Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Každý hráč podá vlastní nabídku Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Každý hráč podá vlastní nabídku Základní typy aukcí Standardní aukce: vítězem je hráč s nejvyšší nabídkou Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Každý hráč podá vlastní nabídku Základní typy aukcí Standardní aukce: vítězem je hráč s nejvyšší nabídkou Aukce s nejvyšší cenou: vítěz platí tolik, kolik on nabídl Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Každý hráč podá vlastní nabídku Základní typy aukcí Standardní aukce: vítězem je hráč s nejvyšší nabídkou Aukce s nejvyšší cenou: vítěz platí tolik, kolik on nabídl Aukce s druhou nejvyšší cenou: vítěz platí druhou nejvyšší nabídku Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s nezávislými hodnotami Hodnoty předmětu pro hráče jsou navzájem nezávislé Každý hráč zná svoji hodnotu předmětu Zná distribuci náhodné proměnné, jejíž realizace určuje hodnotu pro ostatní hráče Každý hráč podá vlastní nabídku Základní typy aukcí Standardní aukce: vítězem je hráč s nejvyšší nabídkou Aukce s nejvyšší cenou: vítěz platí tolik, kolik on nabídl Aukce s druhou nejvyšší cenou: vítěz platí druhou nejvyšší nabídku All-pay aukce: každý platí svoji nabídku Jan Mysliveček (Přf Muni) 3/10 3 / 15 Aukce s druhou nejvyšší cenou Obecné předpoklady n hráčů F : [0, ] [0, 1] distribuční funkce hodnot předmětu, f hustota Xi náhodná veličina, xi její realizace označující hodnotu předmětu Rizikově neutrální hráči (užitek je střední hodnota výhry) Hráči znají vlastní hodnotu (xi ) a distribuci F Jan Mysliveček (Přf Muni) 3/10 4 / 15 Aukce s druhou nejvyšší cenou Obecné předpoklady n hráčů F : [0, ] [0, 1] distribuční funkce hodnot předmětu, f hustota Xi náhodná veličina, xi její realizace označující hodnotu předmětu Rizikově neutrální hráči (užitek je střední hodnota výhry) Hráči znají vlastní hodnotu (xi ) a distribuci F Specifické předpoklady a označení Nabídky jsou podávány současně, v zalepených obálkách Vítězem je hráč s nejvyšší nabídkou (loterie pokud více) Cena je rovna druhé nejvyšší nabídce Hledáme symetrické Nashovy rovnováhy s rostoucími strategiemi (x) Označme Y1 = maxj=i Xj nejvyšší nabídku ostatních hráčů. Jak je Y1 rozdělena? Jan Mysliveček (Přf Muni) 3/10 4 / 15 Model Užitek hráče i s hodnotou x a nabídkou bi ui (x) = x - maxj=i bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (1) kde bi je nabídka i-tého hráče. Jaká je optimální strategie každého hráče? Pokud podává hráč i nejvyšší nabídku, pak je cena určena druhou nejvyšší nabídkou Dokažte, že strategie II (x) = x je slabě dominantní Jan Mysliveček (Přf Muni) 3/10 5 / 15 Model Užitek hráče i s hodnotou x a nabídkou bi ui (x) = x - maxj=i bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (1) kde bi je nabídka i-tého hráče. Jaká je optimální strategie každého hráče? Pokud podává hráč i nejvyšší nabídku, pak je cena určena druhou nejvyšší nabídkou Dokažte, že strategie II (x) = x je slabě dominantní Pro vítěze--nejde si polepšit? Pro prohrávajícího--nejde si polepšit? Jan Mysliveček (Přf Muni) 3/10 5 / 15 Model Užitek hráče i s hodnotou x a nabídkou bi ui (x) = x - maxj=i bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (1) kde bi je nabídka i-tého hráče. Jaká je optimální strategie každého hráče? Pokud podává hráč i nejvyšší nabídku, pak je cena určena druhou nejvyšší nabídkou Dokažte, že strategie II (x) = x je slabě dominantní Pro vítěze--nejde si polepšit? Pro prohrávajícího--nejde si polepšit? Spočtěte očekávaný příjem dražitele Jan Mysliveček (Přf Muni) 3/10 5 / 15 Model Užitek hráče i s hodnotou x a nabídkou bi ui (x) = x - maxj=i bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (1) kde bi je nabídka i-tého hráče. Jaká je optimální strategie každého hráče? Pokud podává hráč i nejvyšší nabídku, pak je cena určena druhou nejvyšší nabídkou Dokažte, že strategie II (x) = x je slabě dominantní Pro vítěze--nejde si polepšit? Pro prohrávajícího--nejde si polepšit? Spočtěte očekávaný příjem dražitele Očekávaná platba hráče s hodnotou x je mII (x) = FN-1 (x) × E[Y1|Y1 < x] Očekávaný příjem pak je n × E[mII (x)] Jan Mysliveček (Přf Muni) 3/10 5 / 15 Aukce s nejvyšší cenou Užitek hráče i s hodnotou x a sázkou bi je ui (x) = x-bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (2) Jan Mysliveček (Přf Muni) 3/10 6 / 15 Aukce s nejvyšší cenou Užitek hráče i s hodnotou x a sázkou bi je ui (x) = x-bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (2) Hrát (x) = x je evidentně nevýhodné Jan Mysliveček (Přf Muni) 3/10 6 / 15 Aukce s nejvyšší cenou Užitek hráče i s hodnotou x a sázkou bi je ui (x) = x-bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (2) Hrát (x) = x je evidentně nevýhodné Předpokládejme, že všichni hráči kromě 1 hrají rostoucí a spojitě diferencovatelnou strategii () Pro jaké je optimální pro prvního hráče hrát rovněž ? Jan Mysliveček (Přf Muni) 3/10 6 / 15 Aukce s nejvyšší cenou Užitek hráče i s hodnotou x a sázkou bi je ui (x) = x-bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (2) Hrát (x) = x je evidentně nevýhodné Předpokládejme, že všichni hráči kromě 1 hrají rostoucí a spojitě diferencovatelnou strategii () Pro jaké je optimální pro prvního hráče hrát rovněž ? Nemá smysl hrát méně než (0) a více než () Jan Mysliveček (Přf Muni) 3/10 6 / 15 Aukce s nejvyšší cenou Užitek hráče i s hodnotou x a sázkou bi je ui (x) = x-bi pro bi > maxj=i bi 0 pro bi < maxj=i bi (2) Hrát (x) = x je evidentně nevýhodné Předpokládejme, že všichni hráči kromě 1 hrají rostoucí a spojitě diferencovatelnou strategii () Pro jaké je optimální pro prvního hráče hrát rovněž ? Nemá smysl hrát méně než (0) a více než () Optimální nabídka b: vítězná pokud b > max i=1 (Xi ) = (max i=1 (Xi )) = (Y1) Výhra je x - b, pravděpodobnost výhry G(-1 (b)). Pro jaké b(x) je tento výraz maximalizován? Jan Mysliveček (Přf Muni) 3/10 6 / 15 Řešení aukce s nejvyšší cenou Podmínky prvního řádu g(-1 (b)) (-1 (b)) (x - b) - G(-1 (b)) = 0 Jan Mysliveček (Přf Muni) 3/10 7 / 15 Řešení aukce s nejvyšší cenou Podmínky prvního řádu g(-1 (b)) (-1 (b)) (x - b) - G(-1 (b)) = 0 V symetrické rovnováze b = (x) dostaneme d dx (G(x)(x)) = xg(x) Jan Mysliveček (Přf Muni) 3/10 7 / 15 Řešení aukce s nejvyšší cenou Podmínky prvního řádu g(-1 (b)) (-1 (b)) (x - b) - G(-1 (b)) = 0 V symetrické rovnováze b = (x) dostaneme d dx (G(x)(x)) = xg(x) Řešení je (x) = 1 G(x) x 0 yg(y)dy = E[Y1|Y1 < x] Hráč 1 vsází očekávanou hodnotu předmětu pro ostatní hráčů za podmínky, že je nižší než x. (Proč?) Jan Mysliveček (Přf Muni) 3/10 7 / 15 Příklad Ukažte, že sázka (x) je vždy menší než x Jan Mysliveček (Přf Muni) 3/10 8 / 15 Příklad Ukažte, že sázka (x) je vždy menší než x Spočtěte očekávaný příjem prodejce Spočtěte optimální strategie I , II pro rovnoměrně rozdělené hodnoty (f = 1 na [0, 1]) Jan Mysliveček (Přf Muni) 3/10 8 / 15 Výnosy standardních aukcí Věta Předpokládejme, že hodnota předmětu je identicky a nezávisle distribuovaná a všichni hráči jsou rizikově neutrální. V každém symetrické a rostoucí rovnováze, ve které hráč s nulovou hodnotou platí v průměru nula, každé standardní aukce, je výnos pro vlastníka předmětu stejný. Jan Mysliveček (Přf Muni) 3/10 9 / 15 Výnosy standardních aukcí Věta Předpokládejme, že hodnota předmětu je identicky a nezávisle distribuovaná a všichni hráči jsou rizikově neutrální. V každém symetrické a rostoucí rovnováze, ve které hráč s nulovou hodnotou platí v průměru nula, každé standardní aukce, je výnos pro vlastníka předmětu stejný. Důkaz: Očekávaná platba m závisí na nabídce, nikoliv vlastní hodnotě předmětu Jan Mysliveček (Přf Muni) 3/10 9 / 15 Výnosy standardních aukcí Věta Předpokládejme, že hodnota předmětu je identicky a nezávisle distribuovaná a všichni hráči jsou rizikově neutrální. V každém symetrické a rostoucí rovnováze, ve které hráč s nulovou hodnotou platí v průměru nula, každé standardní aukce, je výnos pro vlastníka předmětu stejný. Důkaz: Očekávaná platba m závisí na nabídce, nikoliv vlastní hodnotě předmětu Integrací lze ukázat, že m(x) = G(x) × E[Y1|E1 < x] Jan Mysliveček (Přf Muni) 3/10 9 / 15 Výnosy standardních aukcí Věta Předpokládejme, že hodnota předmětu je identicky a nezávisle distribuovaná a všichni hráči jsou rizikově neutrální. V každém symetrické a rostoucí rovnováze, ve které hráč s nulovou hodnotou platí v průměru nula, každé standardní aukce, je výnos pro vlastníka předmětu stejný. Důkaz: Očekávaná platba m závisí na nabídce, nikoliv vlastní hodnotě předmětu Integrací lze ukázat, že m(x) = G(x) × E[Y1|E1 < x] Výraz nezáleží na typu aukce. Jan Mysliveček (Přf Muni) 3/10 9 / 15 Výnosy standardních aukcí Věta Předpokládejme, že hodnota předmětu je identicky a nezávisle distribuovaná a všichni hráči jsou rizikově neutrální. V každém symetrické a rostoucí rovnováze, ve které hráč s nulovou hodnotou platí v průměru nula, každé standardní aukce, je výnos pro vlastníka předmětu stejný. Důkaz: Očekávaná platba m závisí na nabídce, nikoliv vlastní hodnotě předmětu Integrací lze ukázat, že m(x) = G(x) × E[Y1|E1 < x] Výraz nezáleží na typu aukce. Větu lze použít k výpočtu optimální strategie u neobvyklých typu aukcí (všichni platí, třetí nejvyšší cena). Jan Mysliveček (Přf Muni) 3/10 9 / 15 Aukce se společnou hodnotou Každý hráč nemusí znát hodnotu přesně (může mít jen odhad) A jeho hodnota záleží na tom, jakou má předmět hodnotu pro ostatní Označme Xi signál i-tého hráče Náhodná veličina Vi , její realizace je očekávaná hodnota předmětu pro daného hráče vi (x1, x2, . . . , xn) = E[Vi |X1 = x1, . . . , Xn = xn] Nestranný signál E[Xi |Vi = v] = v Jan Mysliveček (Přf Muni) 3/10 10 / 15 Přidružené signály Budeme požadovat aby signály byly přidružené (affiliated) Definice Náhodné veličiny X1, . . . , Xn rozdělené na intervalu X n, popsané hustotou f , jsou přidružené, pokud pro každé x , x X platí f (x x )f (x x ) f (x )f (x ), x x = (max(x1, x1 ), . . . , max(xn, xn )) x x = (min(x1, x1 ), . . . , min(xn, xn )) U dvojitě spojitě diferencovatelné, všude kladné, hustoty je to ekvivalentní 2 xi xj ln f 0 Jan Mysliveček (Přf Muni) 3/10 11 / 15 Přidruženost--důsledky Pro libovolnou rostoucí funkci a x > x platí E[(Y1)|X1 = x ] E[(Y1)|X1 = x]. Vyšší signál pro i-tého hráče indikuje vyšší očekávání signálu pro ostatní hráče Definujeme v(x, y) = E[V1|X1 = x, Y1 = y] Předpokládáme existenci funkce u symetrické vzhledem k posledním n - 1 složkám takovou, že vi (X) = u(Xi , X-i ) Všichni ostatní hráči mají stejně kvalitní informaci z mého pohledu Jan Mysliveček (Přf Muni) 3/10 12 / 15 Aukce s druhou nejvyšší cenou Ukážeme, že optimální strategie je (x) = v(x, x) Jan Mysliveček (Přf Muni) 3/10 13 / 15 Aukce s druhou nejvyšší cenou Ukážeme, že optimální strategie je (x) = v(x, x) Zisk prvního hráče je (b, x) = -1 (b) 0 (v(x, y) - (y))g(y|x)dy, Jan Mysliveček (Přf Muni) 3/10 13 / 15 Aukce s druhou nejvyšší cenou Ukážeme, že optimální strategie je (x) = v(x, x) Zisk prvního hráče je (b, x) = -1 (b) 0 (v(x, y) - (y))g(y|x)dy, Protože (y) = v(y, y), a výraz v(x, y) - v(y, y) je rostoucí v x. Maximum integrálu tedy nastáví pro -1 (b) = x Jan Mysliveček (Přf Muni) 3/10 13 / 15 Aukce s druhou nejvyšší cenou Ukážeme, že optimální strategie je (x) = v(x, x) Zisk prvního hráče je (b, x) = -1 (b) 0 (v(x, y) - (y))g(y|x)dy, Protože (y) = v(y, y), a výraz v(x, y) - v(y, y) je rostoucí v x. Maximum integrálu tedy nastáví pro -1 (b) = x Obecně nejde o slabě dominantní strategii. Jan Mysliveček (Přf Muni) 3/10 13 / 15 Aukce s druhou nejvyšší cenou Ukážeme, že optimální strategie je (x) = v(x, x) Zisk prvního hráče je (b, x) = -1 (b) 0 (v(x, y) - (y))g(y|x)dy, Protože (y) = v(y, y), a výraz v(x, y) - v(y, y) je rostoucí v x. Maximum integrálu tedy nastáví pro -1 (b) = x Obecně nejde o slabě dominantní strategii. Příklad: Tři hráči, V je společná hodnota předmětu rozdělená rovnoměrně na [0, 1]. Signály hráčů jsou rozděleny na [0, 2v]. Jan Mysliveček (Přf Muni) 3/10 13 / 15 Anglická aukce Postupné zvyšování ceny, odpadávání dražitelů je viditelné Zdroj relevantních informací na rozdíl od aukcí s nezávislými hodnotami Označení: Strategie jednoho hráče je (n , n-1 , . . . , 2 ), k : [0, 1] × n-k + + Funkce i určuje cenu odpadnutí při i stále aktivních hráčích a cenách, při kterých odpadli ostatní hráči Jan Mysliveček (Přf Muni) 3/10 14 / 15 Anglická aukce Postupné zvyšování ceny, odpadávání dražitelů je viditelné Zdroj relevantních informací na rozdíl od aukcí s nezávislými hodnotami Označení: Strategie jednoho hráče je (n , n-1 , . . . , 2 ), k : [0, 1] × n-k + + Funkce i určuje cenu odpadnutí při i stále aktivních hráčích a cenách, při kterých odpadli ostatní hráči Definujeme n (x) = u(x, . . . , x), Jan Mysliveček (Přf Muni) 3/10 14 / 15 Anglická aukce Postupné zvyšování ceny, odpadávání dražitelů je viditelné Zdroj relevantních informací na rozdíl od aukcí s nezávislými hodnotami Označení: Strategie jednoho hráče je (n , n-1 , . . . , 2 ), k : [0, 1] × n-k + + Funkce i určuje cenu odpadnutí při i stále aktivních hráčích a cenách, při kterých odpadli ostatní hráči Definujeme n (x) = u(x, . . . , x), Existuje jeidné xn takové, že n (xn = pn Definujme n-1 (x, pn) = u(x, . . . , x, xn) A tak dále až k (x, pk+1, . . . , pn) = u(x, . . . , x, xk+1, . . . , xn), Jan Mysliveček (Přf Muni) 3/10 14 / 15 Aukce s nejvyšší cenou Očekávaný zisk při strategii ostatních hráčů (x), hodnotě x a nabídce z je (z, x) = z 0 (v(x, y) - (z)g(y|x)dy Jan Mysliveček (Přf Muni) 3/10 15 / 15 Aukce s nejvyšší cenou Očekávaný zisk při strategii ostatních hráčů (x), hodnotě x a nabídce z je (z, x) = z 0 (v(x, y) - (z)g(y|x)dy Podmínky prvního řádu vedou na diferenciální rovnici Jan Mysliveček (Přf Muni) 3/10 15 / 15 Aukce s nejvyšší cenou Očekávaný zisk při strategii ostatních hráčů (x), hodnotě x a nabídce z je (z, x) = z 0 (v(x, y) - (z)g(y|x)dy Podmínky prvního řádu vedou na diferenciální rovnici (x) = (v(x, x) - (x)) g(x|x) G(x|x) Jan Mysliveček (Přf Muni) 3/10 15 / 15 Aukce s nejvyšší cenou Očekávaný zisk při strategii ostatních hráčů (x), hodnotě x a nabídce z je (z, x) = z 0 (v(x, y) - (z)g(y|x)dy Podmínky prvního řádu vedou na diferenciální rovnici (x) = (v(x, x) - (x)) g(x|x) G(x|x) Její řešení je I (x) = x 0 v(y, y)dL(y|x), L(y|x) = exp - x y g(t|t) G(t|t) dt Jan Mysliveček (Přf Muni) 3/10 15 / 15