THE: Teorie aukc´ı Auction Theory Martin Hrub´y Brno University of Technology Brno Czech Republic
November 27, 2014
Martin Hrub´ y
Teorie aukc´ı
´ Uvod
ˇ ano z: Cerp´ ◮
Krishna, V.: Auction theory, Elsevier
◮
Nisan et al.: Algorithmic Game Theory
◮
Klemperer, P.: Auctions: Theory and Practice
◮
Shubik, M.: Game Theory in the Social Sciences, Vol. 1: Concepts and Solutions
Martin Hrub´ y
Teorie aukc´ı
Co je aukce?
◮
◮
Aukce (t´eˇz draˇzba) je ekonomick´y mechanismus prodeje hmotn´eho/nehmotn´eho statku. ˇ Je to forma trhu, kde se soustˇreduje nab´ıdka a popt´avka po konkr´etn´ım druhu zboˇz´ı typicky mezi mal´ym poˇctem prod´avaj´ıc´ıch a vˇetˇs´ım poˇctem kupuj´ıc´ıch.
◮
Je to zp˚ usob, jak prodat vˇec, u kter´e nechci stanovit jej´ı cenu (napˇr. proto, ˇze ji nezn´ am nebo chci vyuˇz´ıt odliˇsn´eho ch´ap´an´ı hodnoty vˇeci mezi prod´ avaj´ıc´ım a kupuj´ıc´ım).
◮
Aukce nejsou jenom draˇzby historick´ych pˇredmˇet˚ u nebo kuriozit, maj´ı aplikaci v kaˇzdodenn´ım praktick´em obchodˇe.
◮
E-bay aukce (Internet, electronic market design).
Aukce jako n´akup pˇredmˇetu.
Martin Hrub´ y
Teorie aukc´ı
Teorier veˇrejn´e volby versus aukce Teorie veˇrejn´e volby: ◮
Kolektivn´ı rozhodnut´ı o spoleˇcn´e preferenci, potaˇzmo o v´ıtˇezi.
◮
Uˇzitek hr´aˇce z rozhodnut´ı.
◮
Manipulovatelnost. Dikt´ atorstv´ı. Arrow˚ uv teor´em.
Teorie aukc´ı: ◮
V´ıtez´ı spoleˇcensky nejefektivnˇejˇs´ı alternativa. Co je alternativa?
◮
Zkoum´ame manipulovatelnost (nepravdiv´e ohodnocen´ı alternativ), protoˇze potenci´ alnˇe sniˇzuje v´ynos z aukce.
◮
Hr´aˇci plat´ı za u ´ˇcast v mechanismu. Vliv na manipulovatelnost.
◮
Vickrey-Clarke-Groove mechanismus.
Martin Hrub´ y
Teorie aukc´ı
Aukce o dolar (jeden)
Pˇredmˇetem aukce je jeden USD. Kdo za nˇej nab´ıdne nejv´ıc, ten dolar vyhraje a zaplat´ı svou nab´ıdku. Vyvol´ avac´ı cena je jeden cent. Pˇredpokl´ad´ame, ˇze se aukce dostane do stavu, kdy je nab´ızeno 99 cent˚ u (posledn´ı racion´ alnˇe m´ınˇen´ a nab´ıdka) a moˇzn´a 100 cent˚ u (chci vyhr´at za kaˇzdou cenu, cena v´ıtˇezstv´ı je vyˇsˇs´ı neˇz jeden USD). Hodnotu 1 USD kaˇ zd´ y zn´ a. V aukc´ıch ovˇsem prod´ av´ ame pˇredmˇ ety, u kter´ ych jejich hodnota nen´ı implicitnˇ e jasn´ a.
Martin Hrub´ y
Teorie aukc´ı
Proˇc n´as maj´ı aukce zaj´ımat?
◮
Aukce jsou souˇc´ast ekonomiky svˇeta.
◮
Obchodn´ıci prod´avaj´ı svoje zboˇz´ı, vl´ ady licence (3G s´ıtˇe) a lid´e svoje pˇredmˇety.
◮
Aukce jsou uk´azkou strategick´eho chov´ an´ı hr´ aˇc˚ u (kupuj´ıc´ı, prod´avaj´ıc´ı) – my studujeme jejich matematick´e modely.
◮
M˚ uˇzeme st´at na stranˇe prod´ avaj´ıc´ıho (kter´y se rozhoduje nad formulac´ı mechanismu, aby maximalizoval sv˚ uj uˇzitek) nebo kupuj´ıc´ıho (kter´y se snaˇz´ı v r´ amci mechanismu maximalizovat sv˚ uj uˇzitek).
◮
Chceme-li modelovat tyto situace, poznejme pˇr´ısluˇsnou Teorii aukc´ı.
Martin Hrub´ y
Teorie aukc´ı
Co je uˇzitek z aukce Aukce je nekooperativn´ı hra (kdo jsou hr´ aˇ ci, co jsou strategie?) ◮
◮
◮
◮
Prod´avaj´ıc´ı maximalizuje v´ynos z aukce – nestanovuje ovˇsem cenu (vyvol´avac´ı cena), ale hled´ a mechanismus, kter´y donut´ı kupuj´ıc´ı k maxim´ aln´ım s´ azk´ am. Volba mechanismu je pro nˇ ej strategi´ı ve hˇre. Kupuj´ıc´ı i si soukromˇe (tajnˇe) cen´ı pˇredmˇet aukce na ˇc´astku xi . Pokud za vˇec zaplat´ı yi , pak je rozd´ıl (nejl´ epe kladn´ y) ui = xi − yi jeho ziskem z aukce. D˚ uleˇzit´y fakt: c´ılem kupuj´ıc´ıho nen´ı z´ıskat pˇredmˇ et aukce, ale maximalizovat sv˚ uj zisk. Pokud kupuj´ıc´ı zaplat´ı yi = xi a pˇresto m´ a pocit kladn´eho zisku (pˇr´ınosu), pak evidentnˇe pˇredmˇet aukce chybnˇe ocenil. ◮
◮
Podobnˇe naopak (nen´ı neobvykl´e, Winner’s curse).
Tajn´e ocenˇen´ı pˇredmˇetu kupuj´ıc´ım je fenom´en aukc´ı a souˇcasnˇe z´akladn´ı stavebn´ı k´ amen mechanism designu. Martin Hrub´ y
Teorie aukc´ı
Tajn´e ocenˇen´ı hodnoty pˇredmˇetu aukce ◮
Prod´avaj´ıc´ı neoˇcek´ av´ a, ˇze by za vˇec dostal v´ıc neˇz je maxi ∈Q [xi ] (obecnˇe vzato).
◮
Z toho plyne, ˇ ze jeho hlavn´ım z´ ajmem je zjistit hodnoty xi hr´ aˇ c˚ u.
◮
Toto ovˇsem zaj´ım´ a i samotn´e hr´ aˇce – pokud hr´aˇci zjist´ı xi sv´ych protihr´aˇc˚ u, pak mohou strategicky ovlivnit sv´ e s´ azky.
Jak se bude chovat hr´ aˇc v tˇechto dvou situac´ıch: ◮
Vyhraje nejvyˇsˇs´ı nab´ıdka, ale nic se neplat´ı. Logicky pak hr´aˇc vsad´ı xi′ >> xi libovolnˇe vysok´e.
◮
Vyhraje nejvyˇsˇs´ı nab´ıdka, ale nˇeco se zaplat´ı – y . Hr´aˇc se tedy bude snaˇzit maximalizovat xi − y . Zˇrejmˇe nevsad´ı ˇc´astku vˇetˇs´ı neˇz xi .
Martin Hrub´ y
Teorie aukc´ı
Tajn´e ocenˇen´ı hodnoty pˇredmˇetu aukce Notace: ◮
xi – tajn´ e ocenˇen´ı pˇredmˇetu aukce kupuj´ıc´ım i ∈ Q.
◮
bi – s´azka (nab´ıdka, angl. bid) podan´ a kupuj´ıc´ım v aukci (mnoˇzina vˇsech moˇzn´ych s´ azek je jeho mnoˇzinou strategi´ı).
◮
yi – ˇc´astka, kterou zaplat´ı hr´ aˇc (´ uˇcastn´ık aukce) na konci aukce (existuj´ı mechanismy, kdy obecnˇe plat´ı kaˇzd´y).
Hr´aˇc-kupuj´ıc´ı si cen´ı pˇredmˇet aukce na xi , ale vsad´ı bi ≤ xi , aby v ide´aln´ım pˇr´ıpadˇe zaplatil yi ≤ bi . Hr´aˇc-prod´avaj´ıc´ı nezn´a cenu pˇredmˇetu a vol´ı mechanismus aukce tak, aby z´ıskal v ide´aln´ım pˇr´ıpadˇe maxi [xi ]. Je to moˇ zn´ e?
Martin Hrub´ y
Teorie aukc´ı
Tajn´e ocenˇen´ı hodnoty pˇredmˇetu aukce Tajn´e ocenˇen´ı pˇredmˇetu aukce je priv´ atn´ı informac´ı ve hˇre (hrajeme hru s ne´ uplnou informac´ı). Hr´ aˇci si modeluj´ı n´azor na xi protivn´ık˚ u pravdˇepodobnostn´ım rozloˇzen´ım – distribuˇcn´ı funkc´ı F (x) : h0, ωi → h0, 1i Zkoumaj´ı pak sloˇzenou distribuˇcn´ı funkci G (x) ≡ F (x)N−1 My nebudeme cht´ıt zabˇrednout do anal´yzy spojit´ych distribuˇcn´ıch funkc´ı a pravdˇepodobnost´ı. Uk´ aˇzeme si pouze v´ysledn´ a ekvilibria. Bude pro n´as d˚ uleˇzit´e, ˇze hr´ aˇci jsou symetriˇct´ı ve sv´em n´azoru na ohodnocen´ı (ˇr´ıd´ı se u vˇsech stejn´ym rozloˇzen´ım). Povede to na symetrick´a ekvilibria. Martin Hrub´ y
Teorie aukc´ı
Winner’s curse
◮
V´ıtˇezem se obvykle st´ av´ a hr´ aˇc s nejvyˇsˇs´ı nab´ıdkou (standardn´ı ´ aukce). Umˇernˇe tomu i zaplat´ı.
◮
Zat´ım bez znalosti model˚ u aukc´ı.
◮
Pˇredpokl´ad´ame, ˇze bi ≤ xi . Kl´ıˇcov´e bude spr´ avnˇe urˇcit xi .
◮
Mnohdy se stane, ˇze hr´ aˇc vyhraje, ale pak nen´ı r´ad (pˇr´ıliˇs mnoho zaplat´ı, pˇredmˇet se uk´ aˇze m´enˇe hodnotn´y, ...).
◮
Ocenˇen´ı ropn´ych vrt˚ u, licenc´ı na provozov´ an´ı (napˇr. s´ıt´ı), ocenˇen´ı akci´ı, ...
Pozn.: velmi slavn´a je situace aukˇcn´ıho prodeje licenc´ı na provozov´an´ı 3G-mobiln´ıch s´ıt´ı. Vˇetˇsinu evropsk´ych telefonn´ıch oper´ator˚ u tato aukce t´emˇeˇr ekonomicky zlikvidovala [Klemperer].
Martin Hrub´ y
Teorie aukc´ı
Aukce o 3G licence v Evropsk´ych zem´ıch [Klemperer] V´ynos z aukce vyj´adˇren´y v eurech na hlavu (obˇcana). rok 2000 rok 2001 Rakousko 100 Belgie 45 Nˇemecko 615 D´ ansko 95 ˇ It´alie 240 Recko 45 Holandsko 170 ˇ ycarsko Sv´ 20 Velk´a Brit´anie 650 ˇ ycarsko: zvolilo anglickou aukci (inspirace z v´ysledk˚ Sv´ u UK), na poˇc´atku bylo 9 zainteresovan´ych kupuj´ıc´ıch a v prodeji 4 licence. Po v´ysledku aukce v It´ alii ovˇsem slabˇs´ı hr´ aˇci odpadli a z˚ ustali 4 hr´aˇci (na 4 licence!!!). Nakonec se uk´ azalo, ˇze pˇr´ısluˇsn´e ministerstvo nasadilo velmi n´ızkou ”reserve price” (minim´aln´ı v´yslednou hodnotu), takˇze hr´ aˇci fakticky mohli utvoˇrit koalici a zaˇr´ıdit se dle zn´am´ych teori´ı. Martin Hrub´ y
Teorie aukc´ı
Co jsou pravidla aukce? V ˇcem spoˇc´ıv´a ten mechanismus? Tv˚ urce aukce specifikuje pravidla t´ykaj´ıc´ı se: ◮
Zp˚ usobu pod´av´an´ı nab´ıdek (s´ azek) – jedna s´ azka (ob´ alkov´a metoda, angl. sealed-bid auction), postupn´e pˇrihazov´an´ı.
◮
Zp˚ usobu interakce mezi hr´ aˇci – vˇeˇrejnˇe nebo tajnˇe pod´ avan´e nab´ıdky.
◮
Zp˚ usobu volby v´ıtˇeze aukce – napˇr. hr´ aˇc s nejvyˇsˇs´ı nab´ıdkou (pokud je nab´ıdka pouze jednorozmˇern´ a).
◮
Zp˚ usobu zaplacen´ı za u ´ˇcast v aukci – vstupn´ı poplatek, platba za v´ysledek aukce.
◮
Probereme z´akladn´ı mechanismy intuitivnˇe, pak Revenue Equivalence Theorem a VCG-mechanismus. Martin Hrub´ y
Teorie aukc´ı
Tradiˇcn´ı aukˇcn´ı principy – Anglick´a aukce (ascending auction) Asi nejzn´amˇejˇs´ı forma aukce. Hr´aˇci se sejdou na veˇrejn´em m´ıstˇe, kde probˇehne aukce. ◮ Prod´ avaj´ıc´ı stanov´ı vyvol´ avac´ı cenu. ◮ Hr´ aˇci cenu potvrd´ı sv´ym z´ ajmem, pˇr´ıpadnˇe sekvenˇcnˇe cenu navyˇsuj´ı. Nab´ıdky pod´ avaj´ı veˇrejnˇe. ◮ Hr´ aˇc i s podanou nejvyˇsˇs´ı nab´ıdkou bim se stane v´ıtˇezem aukce. ◮ V´ ıtˇez aukce i zaplat´ı bim . Ostatn´ı neplat´ı nic. Zˇrejmˇe nejobl´ıbenˇejˇs´ı mechanismus veˇrejn´e aukce. Je povaˇzov´an za nejf´erovˇejˇs´ı. Uk´aˇzeme si, ˇze (teoreticky) nevede k maxim´aln´ımu v´ynosu z aukce. ◮ ◮
Vˇsimnˇeme si, ˇze kaˇzd´y hr´ aˇc m˚ uˇze pˇrihodit libovolnˇe mal´e ∆, aby nav´yˇsil pˇredchoz´ı nab´ıdku. Vyplyne z toho, ˇze v´ıtˇ ez plat´ı cenu, kter´ a se fakticky rovn´ a druh´ e nejvyˇsˇs´ı nab´ıdce. Martin Hrub´ y
Teorie aukc´ı
Anglick´a aukce - platba V´ıtˇez aukce: i ∗ = arg max[bi ] i ∈Q
Platba hr´aˇc˚ u za u ´ˇcast v aukci: ( bi yi = 0
i = i∗ jinak
Zisk hr´aˇce z aukce: ( xi − bi ui = 0
i = i∗ jinak
V´ynos z aukce: u ∗ = bi ∗ Martin Hrub´ y
Teorie aukc´ı
Anglick´a aukce v pod´an´ı E-bay ◮ ◮
Hr´aˇc stanov´ı svou pracovn´ı maxim´ aln´ı nab´ıdku bim . Aukˇcn´ı arbitr (robot) nastavuje automaticky stav aktu´aln´ı nejvyˇsˇs´ı nab´ıdky b M s pˇr´ıchodem nov´e nab´ıdky ◮ ◮
◮
b M je druh´a nejvyˇsˇs´ı nab´ıdka plus ∆. Postupn´ym pˇrihazov´an´ım pouze zjist´ım doˇcasnˇe nejvyˇsˇs´ı pˇredchoz´ı nab´ıdku protihr´aˇce.
Aukce konˇc´ı vyprˇsen´ım ˇcasov´eho limitu s v´yslednou cenou b M . Zˇrejmˇe v´ıtˇez aukce nastavil bim ≥ b M .
◮
V´ıtˇez tedy plat´ı druhou nejvyˇsˇs´ı cenu. Je to elektronick´a forma anglick´e aukce.
◮
Rozˇsiˇruj´ıc´ı atributy: reserve price (je tajn´ a aˇz do okamˇziku jej´ıho pˇrekroˇcen´ı (?)).
Racion´aln´ı chov´an´ı v e-bay aukci: zvolte si opravdov´e (naprosto pravdiv´e a realistick´e) vaˇse ocenˇen´ı zboˇz´ı xi , nastavte bim := xi a d´al se na aukci radˇeji ned´ıvejte. Martin Hrub´ y
Teorie aukc´ı
Holandsk´a aukce (descending auction)
◮
◮
◮
◮
Byla zavedena na trz´ıch s kvˇetinami (pouˇz´ıv´ ano u ”spˇechaj´ıc´ıch” komodit – napˇr. ryby). Prod´avaj´ıc´ı ohl´as´ı vyvol´ avac´ı (poˇc´ ateˇcn´ı) cenu b 0 . Nechˇt k = 0, 1, ... oznaˇcuje aktu´ aln´ı kolo aukce. Pokud existuje kupuj´ıc´ı, kter´y za tuto cenu b k chce koupit (stane se v´ıtˇezem), aukce konˇc´ı a kupuj´ıc´ı zaplat´ı b k . Jinak prod´avaj´ıc´ı sn´ıˇz´ı cenu b k o ∆ a v dalˇs´ım kole ohl´as´ı cenu b k+1 = b k − ∆.
Tato aukce je velmi u ´ˇcinn´ a. Ot´azka: bude kupuj´ıc´ı reagovat v kole k, kdy b k ≈ xi ? Co by t´ım z´ıskal? Hr´aˇci zˇrejmˇe nechaj´ı cenu ”vhodnˇe” klesnout pod xi .
Martin Hrub´ y
Teorie aukc´ı
All-pay auction ◮
Hr´aˇci vsad´ı svoje s´ azky bi .
◮
V´ıtˇez´ı klasicky nejvyˇsˇs´ı s´ azka maxi [bi ].
◮
Kaˇzd´y ovˇsem zaplat´ı svou s´ azku yi = bi .
◮
Modeluje ˇcasto reklamu, lobbying, pˇredvolebn´ı kampanˇe (vˇse s charakterem Vˇezˇ nova dilematu).
◮
Racion´aln´ı chov´an´ı v t´eto aukci: pokud se do aukce d´am, pak je pro mˇe racion´aln´ı vsadit absolutn´ı maximum bi = xi .
◮
D˚ ukaz [Krishna, p.32]
Je tu jist´a podobnost s ”Shubikovou aukc´ı o dolar” (model investov´an´ı do nˇeˇceho). Hr´ aˇci nejsou schopni odhalit okamˇzik, kdy je l´epe pˇriznat ztr´atu a odstoupit z aukce. Pozn.: Obskurn´ı formy ”aukc´ı” – bonus.cz Martin Hrub´ y
Teorie aukc´ı
Z´akladn´ı formy aukc´ı ◮
Veˇrejn´a vzestupn´a draˇzba – anglick´ a aukce. Japonsk´a aukce.
◮
Veˇrejn´a sestupn´a draˇzba – holandsk´ a aukce.
◮
Tajn´a draˇzba s prvn´ı cenou (First-Price Sealed-bid Auction).
◮
Tajn´a draˇzba s druhou cenou (Second-Price Sealed-bid Auction).
Jsou nˇekter´e z nich strategicky ekvivalentn´ı (z pohledu kupuj´ıc´ıho)?
Theorem Veˇrejn´a sestupn´a draˇzba (holandsk´ a aukce) je ryze strategicky ekvivalentn´ı s tajnou draˇzbou s prvn´ı cenou. Veˇrejn´a vzestupn´a draˇzba (anglick´ a aukce) je slabˇe strategicky ekvivalent´ı s tajnou draˇzbou s druhou cenou. D˚ ukazy vyplynou z dalˇs´ı slajd˚ u. Martin Hrub´ y
Teorie aukc´ı
Ekvilibrium v z´akladn´ıch aukc´ıch ◮
Veˇrejn´e aukce n´as nyn´ı strategicky nezaj´ımaj´ı (anglick´a v˚ ubec ne, holandsk´a v pod´ an´ı tajn´e s 1st cenou).
◮
Zn´ame (pˇredpokl´ ad´ ame) strategickou ekvivalenci mezi veˇrejn´ymi a tajn´ymi aukcemi.
◮
Uk´aˇzeme si ekvilibrium (tzn. Nashovo) v tajn´ych aukc´ıch (first-price, second-price). Strategicky jednoduˇsˇs´ı je second-price aukce.
◮
◮ ◮
◮
◮
Uk´aˇzeme, ˇze je strategicky nemanipulovateln´a (Vickrey). Uk´aˇzeme, ˇze hr´aˇci nemus´ı zkoumat tajn´e ohodnocen´ı xi sv´ych protihr´aˇc˚ u Uk´aˇzeme, ˇze m´a nejvyˇsˇs´ı v´ynos (aˇz na revenue-equivalence theorem). Je z´akladem multi-object aukc´ı s margin´aln´ı cenou (market-clearing price).
Martin Hrub´ y
Teorie aukc´ı
Strategick´a nemanipulovatelnost v aukc´ıch
Definition Uvaˇzujme mnoˇzinu hr´aˇc˚ u N a vektor (xi )i ∈N jejich tajn´ych ohodnocen´ı pˇredmˇetu aukce. Aukˇcn´ı mechanismus je strategicky nemanipulovateln´y, pokud ˇz´adn´y hr´aˇc i jednotlivˇe nezlepˇs´ı sv˚ uj v´ysledek (rozd´ıl mezi pˇr´ıjmem a platbou), kdyˇz pod´a s´ azku jinou neˇz je xi . Podobnˇe v ostatn´ıch ˇc´ astech Mechanism designu: skuteˇcn´a preference, prezentovan´ a preference, v´ysledek mechanismu, uˇzitek pro hr´aˇce.
Martin Hrub´ y
Teorie aukc´ı
Formalizace aukce Definition Aukce s jedn´ım nedˇeliteln´ym pˇredmˇetem koupˇe je strategick´a situace s N hr´aˇci (mnoˇzina hr´ aˇc˚ u Q), kde kaˇzd´y hr´aˇc m´a pro pˇredmˇet aukce sv´e tajn´e priv´ atn´ı ohodnocen´ı xi . Mechanismus aukce specifikuje volbu v´ıtˇeze aukce i ∗ a ˇc´ astku, kterou kaˇzd´y hr´aˇc mus´ı zaplatit yi . Za standardn´ı aukci povaˇ zujeme aukci, kde v´ıtˇ ezem je hr´ aˇ cs nejvyˇsˇs´ı podanou nab´ıdkou (a hr´ aˇ c s nulovou s´ azkou plat´ı 0). Z pohledu Mechanism design je volba v´ıtˇeze (a platby hr´aˇc˚ u) mechanismem specifikovan´ym Funkc´ı veˇrejn´ı volby (social choice function).
Martin Hrub´ y
Teorie aukc´ı
Tajn´a aukce s druhou cenou (Vickrey auction)
Hr´aˇc se stane v´ıtˇezem, pokud nab´ıdne nejvyˇsˇs´ı cenu.
Definition Nechˇt je v´ıtˇezem aukce hr´ aˇc i s nejvyˇsˇs´ı deklarovanou cenou bi a nechˇt zaplat´ı druhou nejvyˇsˇs´ı deklarovanou cenu y ∗ = max [bj ] j∈Q\{i }
Deklarovan´a cena: bi = xi .
Martin Hrub´ y
Teorie aukc´ı
Tajn´a aukce s druhou cenou
Theorem Pro kaˇzdou s´azku b1 , b2 , ..., bN a kaˇzdou jinou bi′ , nechˇt ui je uˇzitek i-t´eho hr´aˇce pˇri hran´ı bi a ui′ je jeho uˇzitek pˇri hran´ı bi′ . Pak ui ≥ ui′ . William Vickrey (1960) William Vickrey – Nobelova cena (1996). Hr´ aˇc je tedy na tom slabˇ e l´ epe, pokud s´az´ı sv´e pravdiv´e ohodnocen´ı pˇredmˇetu aukce. Rothkopf, M.H., 2007. Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical. Operations Research, 55(2), pp.191–197.
Martin Hrub´ y
Teorie aukc´ı
D˚ ukaz Vickreyova teor´emu
Proof. Pˇredpokl´adejme, ˇze hr´ aˇc i pˇri sv´e s´ azce bi vyhraje a zaplat´ı (druhou nejvyˇsˇs´ı) cenu y ∗ . Jeho zisk je tedy ui = bi − y ∗ ≥ 0. Pˇri moˇzn´e manipulaci bi′ > y ∗ , i je st´ ale v´ıtˇez´ıc´ım hr´ aˇcem a ui′ = ui . V ′ ∗ ′ druh´em pˇr´ıpadˇe, kdy bi < y , i prohraje a u = 0 ≤ u. Pokud hr´aˇc i pˇri s´azce bi prohraje, pak ui = 0. Pak je v´ıtˇez j ∈ Q; j 6= i se s´azkou bj ≥ bi (nebo l´epe bj > bi ). Pro bi′ < bj hr´aˇc i st´ale prohr´av´a a ui′ = 0. Pro bi′ ≥ bj (nebo striktnˇe vyˇsˇs´ı), i vyhr´av´a a plat´ı y ∗ = bj , ale jeho zisk je ui′ = bi − bj ≤ 0, tzn. ui′ ≤ ui .
Martin Hrub´ y
Teorie aukc´ı
Historicky prvn´ı sealed-bid 2nd price aukce
Korespondenˇcn´ı aukce zn´ amek, 1893, Wainwright & Lewis, of Northampton, Massachusetts (citov´ ano z David Lucking-Reiley: Vickrey Auctions in Practice: From Nineteenth Century Philately to Twenty-first Century E-commerce). Catalogue of a Collection of U.S. and Foreign Stamps To be sold WITHOUT RESERVE except where noted. Bids will be received up to 4 P.M., May 15, 1893. Bids are for the LOT, and, contrary to the usual custom in sales of this kind, we shall make this a genuine AUCTION sale; that is to say, each lot will be sold at an advance of from 1c to 10c above the second highest bidder. Address all bids to Wainwright & Lewis, Northampton, Mass.
Martin Hrub´ y
Teorie aukc´ı
V´ybˇerov´a ˇr´ızen´ı na dod´avku ... ◮
V´ybˇerov´a ˇr´ızen´ı (klient, dodavatel´e) jsou tak´e aukce – napˇr. ˇ pohotovost v toˇciv´ych rezerv´ ach (CEPS).
◮
Bˇeˇznˇe neb´yv´a pak kontraktovan´ a cena dodrˇzena (stavby).
◮
Modelem toho m˚ uˇze b´yt aukˇcn´ı mechanismus demonstrovan´y M. Shubikem (dollar auction, 1971, Journal of Conflict Resolution).
◮
Pˇredpokl´adejme aukci, kdy v´ıtˇez zaplat´ı svou cenu, ale svou nab´ıdnutou cenu zaplat´ı i hr´ aˇc na druh´em m´ıstˇe. Jak by potom dopadla ”dollar auction”? Pˇri re´aln´em experimentu [Shubik] byl dolar vydraˇzen za 3.xx dolary.
◮
◮
◮
Shubikova aukce modeluje ”pˇreplacen´ı” u investorsk´ych projekt˚ u (stavby, v´yvoj Concorde) Souˇcasnˇe je vysvˇetlen´ım mnoha spoleˇcensko/psychologick´ych jev˚ u, kde se ´uˇcastn´ık aukce stane ”zainteresovan´ym” a nut´ı ho to d´ale investovat (sledov´an´ı TV poˇrad˚ u). Martin Hrub´ y
Teorie aukc´ı
Multi-Object aukce
◮
Pˇredpokl´adejme n kus˚ u (kapacity) zboˇz´ı v aukci.
◮
Hr´aˇci pod´avaj´ı nab´ıdky ve form´ atu (mnoˇzstv´ı, cena)
◮
Nab´ıdky jsou seˇrazeny sestupnˇe podle ceny a jsou zobchodov´any aˇz do kapacity n.
◮
Kolik v´ıtˇezn´ı hr´aˇci zaplat´ı? Svoji cenu nebo jednotnou (margin´aln´ı, market-clearing price) cenu.
◮
Aukce s margin´aln´ı cenou je multi-object varianta Vickreyovy aukce (2nd price, po zobecnˇen´ı VCG mechanismus). Bˇeˇznˇe aukce na dod´ avku elektˇriny, n´ akup pˇreshraniˇcn´ıch profil˚ u (hr´aˇci tvoˇr´ıc´ı margin´ aln´ı cenu, hr´ aˇci s´ azej´ıc´ı limitn´ı cenu).
◮
◮
Na tˇechto trz´ıch prob´ıh´a uˇz opravdov´y ”gambling”.
Martin Hrub´ y
Teorie aukc´ı
Pˇr´ıklad komplikovanˇejˇs´ı aukce – FlowBased-aukˇcn´ı mechanismus VET PL EON
CZ SK
UA
AT HU
◮
◮ ◮
Pˇredpokl´adejme aukci o pˇreshraniˇcn´ı elektrick´e veden´ı mezi dvˇema zemˇemi tf → tt . Pˇredpokl´adejme fyzik´ aln´ı z´ akony toku elektˇriny v obvodu. Je zaveden centralizovan´y aukˇcn´ı syst´em na pˇridˇelov´an´ı pˇrenosov´e kapacity. Martin Hrub´ y
Teorie aukc´ı
Ekvilibrium v aukci s prvn´ı cenou
Tajn´a aukce s prvn´ı cenou (nebo ekvivalentn´ı Holandsk´a veˇrejn´a aukce) je strategicky n´ aroˇcnˇejˇs´ı neˇz Vickreyovsk´e mechanismy. Hr´aˇc zˇrejmˇe nebude s´azet bi = xi , protoˇze by nikdy nedos´ahl ui > 0. Nejsp´ıˇs bude jeho s´ azka z´ aviset na odhadu ocenˇen´ı xj jeho protivn´ıky. Pˇredpokl´ad´ame: Hr´aˇci oceˇ nuj´ı vˇec v intervalu h0, ωi. Ohodnocen´ı vˇeci hr´aˇci je d´ano distribuˇcn´ı funkc´ı F na intervalu h0, ωi. Pˇredpokl´ad´ame symetrii mezi hr´ aˇci, tzn. F je pro vˇsechny hr´aˇce stejn´a a F je common knowledge.
Martin Hrub´ y
Teorie aukc´ı
Ekvilibrium v aukci s prvn´ı cenou
Theorem Mˇejme N nez´avisl´ych hr´ aˇc˚ u s priv´ atn´ım ohodnocen´ım xi , kter´e je rovnomˇernˇe distribuov´ ano na h0, ωi. Pak je symetrick´ym Nashov´ym ekvilibriem hr´ at: β I (x) =
N −1 x N
D˚ ukaz [Krishna] (projekty).
Toto symetrick´e Nashovo eq. pˇredpokl´ ad´ a risk-neutral hr´aˇce (to zat´ım nezkoum´ame).
Martin Hrub´ y
Teorie aukc´ı
Pˇr´ıklad: Ekvilibrium v aukci s prvn´ı cenou Pˇredpokl´adejme tajn´e symetrick´e ohodnocen´ı pˇredmˇetu rovnomˇern´ym pravdˇepodobnostn´ım rozloˇzen´ım na intervalu h0, 1i. Pokud je m´e ohodnocen´ı napˇr. x1 = 0.8 a N = 2, pak je m˚ uj oˇcek´avan´y zisk d´an: b1 π1 = pravdˇepodobnost v´yhry ∗u1 0.8 0.8*0 0.7 0.7*0.1=0.07 0.6 0.6*0.2=0.12 0.5 0.5*0.3=0.15 0.4 0.4*0.4=0.16 0.3 0.3*0.5=0.15 0.2 0.2*0.6=0.12
Martin Hrub´ y
Teorie aukc´ı
Ekvilibrium v aukci s prvn´ı cenou II.
Theorem Mˇejme N nez´avisl´ych hr´ aˇc˚ u s priv´ atn´ım ohodnocen´ım xi , kter´e je exponenci´alnˇe distribuov´ ano na h0, ∞i. Pak je symetrick´ym Nashov´ym ekvilibriem hr´ at: Je-li F (x) = 1 − exp(−λx) pro λ > 0, N = 2, pak: β I (x) =
x exp(−λx) 1 − λ 1 − exp(−λx)
Martin Hrub´ y
Teorie aukc´ı
Dalˇs´ı t´emata aukc´ı
◮
Vliv rizika na chov´ an´ı hr´ aˇc˚ u – jak hr´ aˇci ch´ apaj´ı sv´e riziko v aukci (riziko ne´ uspˇechu).
◮
Revenue Equivalence Theorem – za jist´ych okolnost´ı (vztaˇzeno k riziku) jsou vˇsechny z´ akladn´ı aukce strategicky ekvivalentn´ı (n´avrh´ aˇr mechanismu si zjednoduˇs´ı pr´aci).
◮
Vickrey-Clarke-Groves mechanismus – matematick´e z´aklady ”Vickrey auction”.
Martin Hrub´ y
Teorie aukc´ı
Vztah k riziku
◮
Risk-neutral, Risk-averse (nesn´ aˇs´ı riziko), Risk-seeking (vyhled´av´a riziko).
◮
Risk-averse hr´aˇc nem´ a vztah mezi ziskem a uˇzitkem line´arn´ı.
◮
Pˇr´ıklad: Je nab´ıdnuto 50 penˇez nebo 50% z´ısk´an´ı 100 penˇez. Risk-averse hr´aˇc vezme 50 penˇez, risk-seeking hr´aˇc vezme ˇsanci 50% na z´ısk´ an´ı 100 penˇez a risk-neutral je indiferentn´ı mezi obˇema.
◮
Prod´avaj´ıc´ı (n´avrh´ aˇr mechanismu) by si mˇel vˇs´ımat vztahu kupuj´ıc´ıch k riziku, protoˇze v pˇr´ıpadˇe 1st-aukce m´a v´yznam pro volbu β I (x).
Martin Hrub´ y
Teorie aukc´ı
Ekvilibrium v aukci s prvn´ı cenou s ohledem na riziko Pˇr´ıstup k β I (x) je pro hr´ aˇ ce volbou jeho strategie. Profil (β I (x1 ), β I (x2 ), ...) je NE, protoˇze ˇz´ adn´y hr´ aˇc nezv´yˇs´ı zv˚ uj uˇzitek volbou jin´eho pˇr´ıstupu. Ekvilibrium pro risk-neutral hr´ aˇce (pouze maximalizuj´ı zisk): N −1 x N Ekvilibrium pro risk-averse hr´ aˇce s koeficientem α ∈ h0, 1i nebo α = 1. β I (x) =
β I (x) = x α Ekvilibrium pro risk-seeking hr´ aˇce: (najdˇete v literatuˇre, projekty)
Martin Hrub´ y
Teorie aukc´ı
Revenue Equivalence Principle ◮
Zn´ame racion´aln´ı chov´ an´ı kupuj´ıc´ıch v aukci – tzn., jakou maj´ı zvolit strategii v zadan´em aukˇcn´ım mechanismu.
◮
Jak´a je ovˇsem pozice prod´ avaj´ıc´ıho? Volba pravidel aukce je zp˚ usobem jeho strategick´eho rozhodov´ an´ı.
◮
I prod´avaj´ıc´ı pˇrem´yˇsl´ı o situaci: jak´e ohodnocen´ı maj´ı hr´aˇci? Jak´ y maj´ı vztah k riziku?
◮
Revenue = v´ynos aukce pro prod´ avaj´ıc´ıho.
◮
Budeme pˇredpokl´ adat standardn´ı aukce – aukce, kde v´ıtˇez je ten, co vsadil nejv´ıc (opaˇcn´ym pˇr´ıkladem je loterie s losy, kde se ˇsance zv´ıtˇezit zvyˇsuje s poˇctem zakoupen´ych los˚ u, ale v´ıtˇez m˚ uˇze b´yt kdokoliv).
Uk´aˇzeme, ˇze za jist´ych okolnost´ı (nepˇr´ıliˇs nepravdˇepodobn´ych) jsou vˇsechny aukˇcn´ı mechanismy ekvivalentn´ı z pohledu v´ynosu aukce (zaruˇcuj´ı shodn´y oˇcek´avan´y v´ynos aukce). Martin Hrub´ y
Teorie aukc´ı
Revenue Equivalence Principle
Porovnejme 1st a 2nd price aukce, kde jsou dva hr´aˇci s ohodnocen´ımi a a b, a, b je rovnomˇernˇe rozloˇzeno na h0, 1i. V´ynos yII∗ = min(a, b) a yI∗ = max(a/2, b/2). Jak´e jsou ovˇsem oˇcek´avan´e (pravdˇepodobnostn´ı) v´ynosy? E (yII∗ ) = E (yI∗ ) =
Martin Hrub´ y
1 3
Teorie aukc´ı
Revenue Equivalence Principle
Theorem Pˇredpokl´adejme risk-neutral hr´ aˇce. Maj´ı-li symetrick´e a nez´avisl´e priv´atn´ı ohodnocen´ı pˇredmˇetu aukce, aukce je standardn´ı a zaruˇcuje nulovou platbu hr´ aˇci deklaruj´ıc´ımu nulov´e ohodnocen´ı. Pak je v´ ynos aukce pˇri aukci s prvn´ı cenou shodn´ y s aukc´ı s druhou cenou. Obecnˇe vzato pak nez´ aleˇz´ı na typu aukˇcn´ıho mechanismu. Pr˚ umˇern´y oˇcek´avan´y v´ynos z aukce bude vˇzdy stejn´y. Hraj´ı-li risk-neutral hr´ aˇ ci, je z hlediska oˇ cek´ av´ an´ı v´ ynosu jedno, zda vol´ıme 1st nebo 2st price aukci.
Martin Hrub´ y
Teorie aukc´ı
Rozd´ıl v´ynos˚ u mezi 1st a 2nd price aukcemi pˇri risk-averse hr´aˇc´ıch
Theorem Pˇredpokl´adejme risk-averse hr´ aˇce. Maj´ı-li symetrick´e a nez´avisl´e priv´atn´ı ohodnocen´ı pˇredmˇetu aukce, pak je v´ynos aukce pˇri aukci s prvn´ı cenou vyˇsˇs´ı neˇz u akce s druhou cenou. Hraj´ı-li risk-averse hr´ aˇ ci, je l´ epe volit 1st price aukci.
Martin Hrub´ y
Teorie aukc´ı
Vickrey-Clarke-Groves mechanismus
◮
W. Vickrey v roce 1961 publikoval n´ avrh aukce s druhou cenou, kde uk´azal, ˇze je nemanipulovateln´ a (hr´aˇc deklaruj´ıc´ı nepravdiv´e ohodnocen´ı pˇredmˇetu nez´ısk´ a v´ıc).
◮
Clarke (1971) a Groves (1973) tuto myˇslenku zobecnili do VCG-mechanismu.
◮
Budeme VCG-mechanismus definovat.
◮
Uk´aˇzeme, ˇze je strategicky nemanipulovateln´y.
◮
Uk´aˇzeme aplikace.
Martin Hrub´ y
Teorie aukc´ı
Notace Pˇredpokl´adejme mnoˇzinu alternativ A. Kaˇzd´y hr´aˇc deklaruje svou ohodnocovac´ı funkci vi : A → R Hr´ aˇ c d´ av´ a funkc´ı vi veˇrejnˇ e najevo, jak si cen´ı jednotliv´ e alternativy a ∈ A. Mnoˇzina vˇsech ohodnocovac´ıch funkc´ı hr´ aˇce je Vi (je to totoˇzn´e s Si u strategick´ych her). M˚ uˇ ze n´ am sdˇ elit libovoln´ y postoj vi ∈ Vi , my chceme jeho pravdiv´ y postoj. D´ale definujeme v = (v1 , v2 , ..., vN ) jako profil, v ∈ V , V = V1 × V2 × ... × VN . Podobnˇe ch´ apeme V−i a v−i . Martin Hrub´ y
Teorie aukc´ı
Mechanismus (direct revelation) Definition Mechanismus je d´an funkc´ı veˇrejn´e volby f : V1 × ... × VN → A a vektorem plateb p1 , ..., pN , kde pi : V1 × ... × VN → R je ˇc´astka, kterou zaplat´ı hr´aˇc i . Pak pr˚ ubˇeh: ◮
Hr´aˇci sdˇel´ı sv´e ocenˇen´ı, tzn. postoje vi ∈ Vi v˚ uˇci r˚ uzn´ym alternativ´am a ∈ A.
◮
Funkce veˇrejn´e volby rozhodne, kter´ a alternativa a ∈ A se zvol´ı.
◮
Urˇc´ı se pro kaˇzd´eho hr´ aˇce i ∈ Q, kolik zaplat´ı – pi : V1 × ... × VN .
Martin Hrub´ y
Teorie aukc´ı
Nemanipulovatelnost mechanismu Definition Mechanismus (f , p1 , ..., pN ) se naz´yv´ a nemanipulovateln´ y (incentive compatible, strategy-proof), pokud pro kaˇzd´eho hr´aˇce i , pro kaˇzd´y profil v ∈ V a kaˇzd´e vi′ ∈ Vi , pokud v´ıme, ˇze a = f (vi , v−i ) a a′ = f (vi′ , v−i ), pak plat´ı vi (a) − pi (vi , v−i ) ≥ vi (a′ ) − pi (vi′ , v−i ) St´ale dokola: pokud hr´ aˇc ˇr´ık´ a pravdu, nen´ı na tom h˚ uˇr neˇz kdyˇz lˇze. Kde je zdroj manipulace? Co n´am to m˚ uˇze pˇripom´ınat? Martin Hrub´ y
Teorie aukc´ı
VCG-mechanismus Hled´ame takovou funkci veˇrejn´e volby f P , aby v dan´e situaci vyb´ırala veˇrejn´e optimum, tzn. maxa∈A i vi (a).
Definition
Mechanismus (f , p1 , ..., pN ) se naz´yv´ a Vickrey-Clarke-Groves mechanismus (VCG), pokud: ◮
f maximalizuje spoleˇcensk´y uˇzitek, tedy # " X f (v1 , ..., vN ) ∈ arg max vi (a) a∈A
◮
i
pro sadu funkc´ı h1 , ..., hN , kde hi : V−i → R, definujeme X pi (v1 , ..., vN ) = hi (v−i ) − vj (f (v1 , ..., vN )) j6=i
Martin Hrub´ y
Teorie aukc´ı
VCG-mechanismus
pi (v1 , ..., vN ) = hi (v−i ) −
X
vj (f (v1 , ..., vN ))
j6=i
Jinak ˇreˇceno, platba za u ´ˇcast ve hˇre je d´ ana sloˇzkami: ◮
◮
hi (v−i ), tedy platby, o kter´e rozhodne mechanismus z kontextu v−i P − j6=i vj (f (v1 , ..., vN )), tedy slevou hodnoty, kterou protihr´aˇci deklaruj´ı jako jejich pˇr´ınos z volby v´ıtˇezn´e alternativy.
Martin Hrub´ y
Teorie aukc´ı
VCG-mechanismus (nemanipulovatelnost)
Theorem Kaˇzd´y VCG-mechanismus je strategicky nemanipulovateln´y. Hr´aˇc, kter´y deklaruje nepravdiv´e ohodnocen´ı, nez´ısk´ a v´ıc. Jak m˚ uˇze hr´aˇc manipulovat volbu? Svou deklarac´ı vi ∈ V : snaha o ovlivnˇen´ı prvn´ıho a druh´eho ˇclenu platby. D˚ ukaz [Nisan, p. 219]
Martin Hrub´ y
Teorie aukc´ı
Clarke Pivot Rule Trochu jsme odsunuli probl´em jeho pˇreveden´ım na formulaci funkc´ı {hi (v−i )}i ∈Q .
Definition ◮
Mechanismus je (ex-post) individu´ alnˇe racion´aln´ı, pokud hr´aˇci vˇzdy z´ıskaj´ı kladn´y zisk (tedy i nulov´y). Form´alnˇe, pro vˇsechny v ∈ V : vi (f (v )) − pi (v ) ≥ 0; ∀i ∈ Q.
◮
Mechanismus nem´ a ˇz´ adn´e postrann´ı platby, pokud ˇz´adn´y hr´aˇc platbou nez´ısk´a. Form´ alnˇe, ∀v ∈ V : ∀i ∈ Q : pi (v ) ≥ 0 (pi ned´av´a z´aporn´e hodnoty platby).
Hr´aˇc i u ´ˇcast´ı ve hˇre z´ısk´ av´ a ui (v ) = vi (f (v )) − pi (v ), tzn. jak si cen´ı v´ysledku f (v ) po odeˇctu platby pi (v ).
Martin Hrub´ y
Teorie aukc´ı
Clarke Pivot Rule Definition Clarke pivot platba je
hi (v−i ) = max b∈A
X j6=i
vj (b)
Potom je platba hr´aˇce v profilu v ∈ V d´ ana pi (v ) = max b
X j6=i
vj (b) −
X
vj (a)
j6=i
kde a = f (v ). Hr´aˇc zaplat´ı do syst´emu ˇc´ astku, kter´ a se rovn´ a celkov´e ˇskodˇe, kterou ostatn´ım zp˚ usobil. Martin Hrub´ y
Teorie aukc´ı
Clarke Pivot Rule
Lemma VCG mechanismus s Clarke pivot platbou nezp˚ usobuje ˇz´adn´e postrann´ı platby. Pokud je vi (a) ≥ 0 pro vˇsechny vi ∈ Vi a a ∈ A, pak je tak´e individu´alnˇe racion´ aln´ı.
Martin Hrub´ y
Teorie aukc´ı
VCG mechanismus – single-object aukce
◮
A = {winsi |i ∈ Q} – kdo m´ a vyhr´ at.
◮
Kaˇzd´y hr´aˇc hodnot´ı sv´e v´ıtˇezstv´ı kladnˇe, v´ıtˇezstv´ı jin´eho nulovˇe:
◮
Vi = {vi |vi (winsi ) ≥ 0; ∀j 6= i : vi (winsj ) = 0}
◮
Pokud m´a hr´aˇc v pl´ anu deklarovat pouze cenu xi , pak je vi (winsi ) = xi , vi (winsj ) = 0 ∀j 6= i . Jinak m˚ uˇze deklarovat 1 2 dalˇs´ı funkce vi , vi , ...
◮
VCG mechanismus s Clarkov´ym pivotem n´ am d´av´a pˇresnˇe Vickreyovu aukci.
Martin Hrub´ y
Teorie aukc´ı
VCG mechanismus – single-object aukce Mˇejme situaci tˇr´ı hr´aˇc˚ u, tzn. A = {1, 2, 3}, kde x1 = 10, x2 = 15, x3 = 4. N´ asleduje jeden moˇzn´y profil v : i /A 1 2 3 v1 (a) 10 0 0 v2 (a) 0 15 0 v3 (a) 0 0 4 f (v ) = 2 je zvolena alternativa ”vyhr´ al 2”. Platby hr´aˇc˚ u jsou: p1 (v ) = max[0, 15, 4] − 15 = 0 p2 (v ) = max[10, 0, 4] − 0 = 10 p3 (v ) = max[10, 15, 0] − 15 = 0 Zkusme to manipulovat. Hr´ aˇc 2 nezlepˇs´ı sv˚ uj v´ysledek manipulac´ı. Zkusme hr´aˇce 1: a) v1 (1) = 16, b) v1 (2) = 5, c) v1 (2) = −6. Martin Hrub´ y
Teorie aukc´ı
VCG mechanismus – stavba veˇrejnˇe prospˇeˇsn´eho objektu Vl´ akladech C , pokud Pada pl´anuje zbudovat objekt o stavebn´ıch n´ i vi > C . ◮
Pˇredpokl´ad´ame hr´ aˇce vi ≥ 0, ale je pˇr´ıpustn´e i vi < 0
◮
Probl´emem je ozn´ amit pivotn´ı pravidlo takov´e, aby hr´aˇci mˇeli potˇrebu pravdivˇe deklarovat sv´ a vi
◮
Clarke pivot: hr´aˇc i s vi ≥ 0 zaplat´ı nenulovou ˇc´astku pouze tehdy, je-li pivotn´ım hr´ aˇcem, tzn.: P P j6=i vj ≤ C a souˇ Pcasnˇe j∈Q vj > C . V takov´em pˇr´ıpadˇe zaplat´ı pi = C − j6=i vj .
◮
Hr´aˇc se z´aporn´ Pym ohodnocen´ Pım zaplat´ı nenulovouPˇc´astku pouze, kdyˇz j6=i vj > C a j vj ≤ C , pak pi = j6=i vj − C . P Bohuˇzel vˇzdy bude platit i pi < C . ◮
Martin Hrub´ y
Teorie aukc´ı
VCG mechanismus – stavba veˇrejnˇe prospˇeˇsn´eho objektu Situace je jin´a, neˇz u pˇr´ıkladu se Shapleyho hodnotou (tady hr´aˇci nemus´ı d´at v sumˇe C). Mˇejme tˇri hr´ aˇce v1 = 10, v2 = 5, v3 = 4, C = 17. p1 = 17 − 9 = 8 p2 = 17 − 14 = 3 p3 = 17 − 15 = 2 P j pj = 13 Mechanismus je odoln´y proti manipulaci, neboˇt pokud v1′ = 8, pak p1′ = 17 − 9. Pˇri v1′′ = 7 se stavba jiˇz nepostav´ı. Jak to dopadne pˇri v = (20, 5, 1)? Dalˇs´ı pˇr´ıklady kap. 9.3.5. [Nisan, s. 220]. Model: cost-sharing.
Martin Hrub´ y
Teorie aukc´ı
Zanedb´ano
◮
Third-price auction.
◮
Nesymetrick´e distribuˇcn´ı funkce ohodnocen´ı hr´aˇci.
◮
Modelov´an´ı risk-averse hr´ aˇc˚ u.
◮
Multi-object aukce.
Martin Hrub´ y
Teorie aukc´ı
Pˇr´ıˇstˇe
◮ ◮
◮
Evoluˇcn´ı teorie her. ˇ a stˇredn´ı Case-study: modelov´ an´ı energetick´ych trh˚ u v CR Evropˇe. Z´avˇereˇcn´e opakov´ an´ı.
Martin Hrub´ y
Teorie aukc´ı
