Orosz Alexandra. Árverési mechanizmusok

Eötvös Loránd Tudományegyetem Természettudományi Kar

Orosz Alexandra Árverési mechanizmusok Szakdolgozat Matematika BSc szak Matematikai elemző szakirány Témavezető: Bérczi-Kovács Erika

2016

Köszönetnyilvánítás Ezúton szeretném megragadni az alkalmat, hogy köszönetemet fejezzem ki mindazoknak, akik lehetővé tették szakdolgozatom létrejöttét. Először is szeretném megköszönni témavezetőmnek, Bérczi-Kovács Erikának, aki magyarázataival, észrevételeivel és tanácsaival segítette a munkámat, elengedhetetlen segítséget nyújtott a szakdolgozatom létrejöttéhez. Köszönöm a családomnak és páromnak, hogy szeretetükkel támogattak, türelmet és megértést tanúsítottak felém szakdolgozatom írása közben, nélkülük ez a munka nem jöhetett volna létre.

1

Tartalomjegyzék Tartalomjegyzék

2

Előszó A dolgozat felépítése . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4

1. Alapfogalmak 1.1. Stratégiai játékok . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1. Tiszta Nash-egyensúly stratégiai játékokban . . . . . . 1.1.2. Bayesi játék . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 6

2. Aukciók, mint stratégiai játékok 2.1. A leggyakoribb aukciófajták és jellemzésük 2.2. Az aukciók egyensúlyának vizsgálata . . . 2.3. Ha a Louvre képbe kerül... [5] . . . . . . . 2.3.1. A Louvre csak saját részre vásárol . 2.3.2. A Louvre későbbi eladásra vásárol . 3. Az aukciók hatékonysága 3.1. Kombinatorikus aukciók . . . . 3.2. A mag . . . . . . . . . . . . . . 3.3. Emelkedő aukciók . . . . . . . . 3.3.1. Primál-Duál Algoritmus

2

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

8 8 10 11 12 15

. . . .

17 17 23 26 27

Bevezetés Manapság nagyon közkedveltek és elterjedtek az aukciók, rendkívül színes a szabályrendszerük, és az értékesítésre felkínált termékek is sokfélék: műtárgyak, könyvek, antik tárgyak, mezőgazdasági termékek, ásványkincsek feletti rendelkezési jog, államkötvények, vállalatok, egy munka elvégzésének joga, arany. Történelmi példák szerint a rabszolgapiacon is közkedvelt volt ez a módszer, sőt arra is volt precedens, hogy valaki szeretett feleségétől vált meg így. A dolgozat első felében bemutatjuk a legismertebb aukció típusokat, melyekben egy eladó van, aki egy tárgyát szeretné eladni. Ez az eladó annak a vevőnek szeretné eladni a tárgyát, aki a lehető legtöbbet fizetne érte. Ennek érdekében megnézzük a különböző ismert aukciós formák (angol árverés, zárt licit aukció, Holland aukció, stb.) egyensúlyi állapotait. A dolgozat második felében az úgynevezett kombinatorikus aukciókkal foglalkozunk, melyekben több tárgy kerül elárverezésre, és a vevők ezen tárgyak részhalmazaira licitálhatnak. Úgy közelítjük meg a feladatot, mint egy kooperációs játék, melyben az elosztás alapjául az aukciós mechanizmusok szolgálnak. Belátjuk, hogy a leírt mechanizmus a lehető legnagyobb összhasznosságot biztosítja a részvevőknek.

3

TARTALOMJEGYZÉK

4

A dolgozat felépítése Az első fejezetben bevezetjük a stratégiai játékok, a stratégia, a tiszta Nashegyensúly és a bayesi játék fogalmát. A második fejezetben jellemezzük a leggyakoribb aukciófajtákat és a hozzájuk tartozó licitstratégiákat; bevezetjük az alap definíciókat és jelöléseket, melyek nélkülözhetetlenek ahhoz, hogy le tudjuk írni azokat az aukció tervezési feladatokat, melyeket tanulmányozni fogunk. Bevezetjük a rezervációs ár fogalmát; megnézzük, hogy ez milyen függvényként írható le, és milyen tulajdonságai vannak az eladóra, illetve a licitálókra nézve. A harmadik fejezetben pedig más szemszögből vizsgáljuk meg az aukciókat. Ebben a részben megvizsgáljuk a kombinatorikus aukciókat, és egyre hatékonyabb lineáris programozási modellekkel keresünk optimális megoldást. Végezetül pedig kooperatív játékokra keresünk a bemutatott lineáris programokon alapuló hatékony elosztást emelkedő aukciók segítségével, melyet a dolgozat végén definiálunk.

1. fejezet Alapfogalmak 1.1.

Stratégiai játékok

Megadunk egy formális modellt, amit a következőkben stratégiai játék alatt fogunk érteni. – Véges sok, n játékos van. – Az i. játékoshoz adott egy Si halmaz, aminek elemeit a játékos stratégiáinak nevezzük. – A játék egy lehetséges kimenetele az, hogy minden játékos választ egyszerre egy-egy stratégiát. A kimenetelek halmaza tehát S := S1 × S2 × . . . × Sn . A kimeneteleket más néven stratégiaválasztásoknak hívjuk. – Feltesszük, hogy a játékosok a kimenetelekhez hozzá tudnak rendelni egy valós számot, hogy mennyi a nyereségük ebben a helyzetben. Az i. játékos nyereségét az ui : S → R nyereségfüggvény írja le. A veszteség negatív értékű nyereség, a nulla kimenetel pedig semlegesnek számít. Minden játékos célja a saját nyereségének maximalizálása.

5

FEJEZET 1. ALAPFOGALMAK

1.1.1.

6

Tiszta Nash-egyensúly stratégiai játékokban

Ha z, z 0 ∈ Si az i. játékos két stratégiája, akkor azt mondjuk, hogy z gyengén dominálja z 0 -t, ha z-vel mindig legalább olyan jól jár, mint z 0 -vel, vagyis ui (s1 , . . . , si−1 , z, si+1 , . . . , sn ) ≥ ui (s1 , . . . , si−1 , z 0 , si+1 , . . . , sn ) a többi játékos összes lehetséges sj stratégia választása esetén. z erősen dominálja z 0 -t, ha mindig szigorú egyenlőtlenség áll, vagyis a többiek bármely sj ∈ Sj (j 6= i) stratégiáira ui (s1 , . . . , si−1 , z, si+1 , . . . , sn ) > ui (s1 , . . . , si−1 , z 0 , si+1 , . . . , sn ). Egy stratégia domináns, ha a játékos összes többi stratégiáját dominálja. 1 ≤ i ≤ n-re jelöljük S−i -vel a ×j6=i Sj halmazt, vagyis az Si -től különböző stratégiahalmazok szorzatát. Ennek elemeit részleges stratégiaválasztásnak nevezzük: az i játékos kivételével minden játékoshoz ki van jelölve egy stratégia. Egy (si , . . . , si−1 , z, si+1 , . . . , sn ) ∈ S−i részleges stratégiaválasztást röviden s−i -vel jelölünk; a (s1 , . . . , si−1 , z, si+1 , . . . , sn ) vektort pedig (z, s−i ) rövidíti. Egy s−i részleges stratégiaválasztásra az i játékos egy legjobb válasza egy olyan z stratégia, amire ui (z, s−i ) maximális. Legjobb válasz persze több is lehet, és ha Si nem véges, akkor lehet, hogy nincs is. Egy s = (s1 , . . . , sn ) stratégiaválasztás tiszta Nash-egyensúly, ha minden i játékos esetén az si stratégia legjobb válasz s−i -re, vagyis ha egyik játékos sem járhat jobban, ha megváltoztatja a stratégiáját, feltéve, hogy a többiek nem változtatnak. Formálisan, minden i játékosra ui (si , s−i ) ≥ ui (z, s−i ) tetszőleges z ∈ Si -re.

1.1.2.

Bayesi játék

Bayesi játéknak szokás nevezni az olyan szituációkat, ahol a játékosok egyes tulajdonságait (például a különböző kimenetelek esetén elért kifizetését) a többiek közvetlenül nem tudják megfigyelni. Egymás típusaira (illetve csak a különböző típusok bekövetkezésének valószínűségére) a játékosok saját típusuk, illetve a többiekről feltételezett stratégiák alapján következtetnek: a

FEJEZET 1. ALAPFOGALMAK

7

Bayes-törvény alapján feltételes valószínűségeket számítanak a típusok mindenki által ismert előzetes (a priori) együttes eloszlásából. Bayesi Nashegyensúlynak tulajdonképpen egy bayesi játék Nash-egyensúlyát nevezzük.

2. fejezet Aukciók, mint stratégiai játékok Az árveréseket a stratégiai játékok közé lehet sorolni, ezért a könnyebb megértésükért bevezetünk pár új fogalmat és jelölést, melyeket Szatmári Alexandra [5] cikkének feldolgozására fogunk használni. Legyen egy játékos rezervációs ára az a legnagyobb érték, amennyiért még megvásárolná a licitálásra bocsátott tárgyat. A dolgozatban feltételezzük, hogy ez az érték egy konkrét érték, amit mindenki meg tud határozni saját magának, és ezen az értéken a későbbiekben sem fog változtatni. Az i. játékos rezervációs árát ti -vel fogjuk jelölni. Ekkor egy játékos ui nyeresége egy egyszerűen a rezervációs ár és a nyertes kifizetésének a különbsége, azaz: ui = ti − hkifizetési.

2.1.

A leggyakoribb aukciófajták és jellemzésük

Az életben aukciókat rengeteg szabály szerint lehet rendezni, viszont most csak a legtöbbek által ismert, vagy a modellezés szempontjából legérdekesebbeket nézzük meg. Angol árverés (first-price open cry auction) Szabályok: minden licitáló szabadon tehet árajánlatot, többször is. Mindenki hallja az összes licitet. A licitálás akkor ér véget, ha már senki sem emeli az aktuális árat. A köznapi értelemben ezt a típust szokás árverésnek

8

FEJEZET 2. AUKCIÓK, MINT STRATÉGIAI JÁTÉKOK

9

nevezni. Stratégia: minden licitáló a saját rezervációs árának, a többiek rezervációs áráról alkotott feltevésének, valamint az éppen aktuális licit nagyságának a függvényében dönti el, hogy emeli-e a licitet. Nyereség: a legtöbbet kínáló nyeresége a rezervációs árának és a vételárnak (ami ebben az esetben maga a legmagasabb licit) a különbsége. Versenytárgyalás (first-price sealed bid auction) Ezt a fajta aukciót alkalmazzák műkincsek, ingatlanok eladásakor, valamint az Egyesült Államok kormánya is ezt használja az ásványkincsek feletti rendelkezési jog odaítélésénél. Szabályok: minden játékos egyetlen árajánlatot tesz, a többiek licitjét nem ismerve. Az fogja megvásárolni a tárgyat, aki a legmagasabb licitet tette, és kifizeti az általa tett licitnek megfelelő összeget. Stratégia: a játékos árajánlata a többiek rezervációs áráról alkotott hiedelmének a függvénye. Nyereség: a nyertes nyeresége a saját rezervációs árának és a vételárnak, azaz a legmagasabb licitnek a különbsége. Vickrey-féle aukció (second-price sealed bid auction) Szabályok: minden licitáló egy árajánlatot tesz, miközben a többiek árajánlatát nem ismeri. Stratégia: a játékosok stratégiája a saját rezervációs árának és a többiek rezervációs áráról alkotott feltételezésének a függvénye. Nyereség: a nyertes nyeresége a saját rezervációs árának és a vételárnak (amely ebben az esetben a második legmagasabb ajánlati ár) a különbsége. Holland aukció (ereszkedő - Dutch vagy descending auction) Ez a fajta aukció a gyakorlatban is igen közkedvelt: legtöbbször így adják el a vágott virágot Hollandiában (innen kapta az elnevezését is), a halat Izraelben vagy a dohányt Ontarióban (ez utóbbi árverés még azzal a sajátossággal is rendelkezik, hogy itt jogában áll a dohány eladójának az árverést követően a vevők ajánlatait visszautasítani, ha a végső árat túl alacsonynak tartja).


10

Szabályok: az eladó megállapít egy árat, majd ezt folyamatosan csökkenti egészen addig, amíg egy vevő azt nem jelzi, hogy az aktuális árért hajlandó megvásárolni a terméket. Stratégia: az eladó megállítása a játékosok rezervációs árának és a többiek rezervációs árairól alkotott feltevésüknek a függvénye. Nyereség: A nyertes nyeresége a rezervációs árának és az aukció vezetőjének megállításakor érvényben levő árnak, vagyis a vételárnak a különbsége.

2.2.

Az aukciók egyensúlyának vizsgálata

A továbbiakban azt is feltesszük, hogy a játékosok rezervációs árai egymástól függetlenek, és ezek a rezervációs árak a [0; 1] intervallumba esnek. A licitálók rezervációs árai egymástól független, azonos F eloszlásfüggvénnyel jellemezhető eloszlást követnek. Legyen bi az i. játékos licitje, vagyis bi az i játékos által tett árajánlat. A licitálás ti szigorúan monoton növekedő függvénye (az a játékos többet fog ajánlani, akinek többet ér a tárgy), ezért létezik az inverze: ti = Φ(bi ). A későbbiekben feltesszük, hogy ez differenciálható. Versenytárgyalás A versenytárgyalás nyilván bayesi játék, hiszen a licitálók nem ismerik egymásnak a termékre vonatkozó megítélését, rezervációs árát, így utólagos kifizetését sem. Az i-edik játékos várható nyeresége: a játék megnyerése esetén élvezett többlet, (ti − bi ), és a nyerés valószínűségének, P (bj < bi , ∀j 6= i), szorzata. A Nash-egyensúly felírásának és meghatározásának egyik módja a következő: minden i játékosra maximalizáljuk az illető célfüggvényét azon korlátozó feltételek mellett, hogy a többi játékos is egyensúlyi stratégiát játszik: max πi = (ti − bi )P (bj < bi , ∀j 6= i) bi

Ennek a feladatnak a megoldása azért ad Nash-egyensúlyt, mert a maximumfeladat korlátja az ellenfél egyensúlyi stratégiája, tehát a maximumfeladat minden játékos esetében az ellenfelek egyensúlyi stratégiájára adott leg-


11

jobb válasz - ami éppen a Nash-egyensúly meghatározása. A Nash-egyensúly másképp fogalmazva azért bayesi, mert a P (bj < bi , ∀j 6= i) valószínűségeket a játékosok a típusok a priori együttes eloszlásából Bayes-tétellel határozzák meg, minden rendelkezésre álló információ (saját típusuk és az egyensúlyi stratégiák) felhasználásával. Keressük meg a versenytárgyalás bayesi Nash-egyensúlyát n résztvevő esetén! (A konkrét megoldás függ a résztvevők számától, amelyről feltesszük, hogy a licitálók ismerik azt.) Mivel az eloszlások függetlenek, és a licitálók egyszerre döntenek, ezért nincs egyéb rendelkezésre álló információ, csak a típusok a priori eloszlása. Annak valószínűsége, hogy az összes többi játékos alacsonyabb licitet mond be az i-ediknél: P (bj < bi , ∀j 6= i) = P tj < Φ(bi ), ∀j 6= i = F n−1 Φ(bi ) . Ekkor a célfüggvényt a licit függvényében a következőképpen írhatjuk fel: Πi = (ti − bi )F n−1 Φ(bi ) . A függvény maximalizálásának elsőrendű feltétele: F Φ(bi ) ∂Φ . (ti − bi ) = ∂bi (n − 1)f Φ(bi ) (A képletben f az eloszlás sűrűségfüggvényét jelöli.) Ha a rezervációs árak egyenletes eloszlásúak, azaz F (ti ) = ti , akkor ti = Φ(bi ) behelyettesítésével az optimális licit: n−1 . n Könnyen megállapítható, hogy ha n elég nagy, vagyis sokan licitálnak, akkor a licit közel lesz a rezervációs ár értékéhez. bi = ti ·

2.3.

Ha a Louvre képbe kerül... [5]

Most pedig vizsgáljunk meg egy olyan aukciót, amely a valóságban is létezik, ám egy speciális feltétellel, amelynek eredményeképpen a játékosok


12

stratégiája is némileg módosul az eddig megismert stratégiákhoz képest. A problémafelvetés alapja megtalálható Rasmusen [3] könyvének 257. oldalán. Az aukció szabályai a következők: Franciaországban a műtárgyak aukcióin az utolsó licit elhangzása, vagyis a vételár meghatározása után a Louvre képviselőjének jogában áll felemelnie a kezét és bejelenteni, hogy „préemption de l’État”. A bejelentést követően az aukción kialakult vételárat fizeti ki, és a festmény a Louvre-ba kerül. A következőkben megnézzük, hogy mindez milyen hatással van a játékosok stratégiájára abban a két esetben, ha a Louvre csak saját részére vásárolhatja meg a tárgyat, illetve ha azt később értékesítheti is. Az aukció szabályrendszerének ilyen megváltoztatásától nem várható, hogy az eladó nagyobb bevételhez jut, mint amekkorát akkor érhetne el, ha a Louvre-t mint előjogokkal nem rendelkező résztvevőt vonná be egy angol típusú árverésbe. Sőt, bármely két árverési szabályrendszer, amely a terméket ugyanannak a vevőnek juttatja, valamint a licitálókat rezervációs áruk önkéntes felfedésére készteti (ún. ösztönző mechanizmus), ugyanakkora várható bevételt biztosít az eladó számára. Tekintsük az eddigi jelöléseket, kiegészítve azzal, hogy jelentse tL a Louvre rezervációs árát! Először azt az esetet vizsgáljuk, amikor a Louvre csak saját részére vásárolhat, a tárgyat később sem adhatja el, majd kitérünk arra az esetre is, ha a Louvre később eladhatja a képet.

2.3.1.

A Louvre csak saját részre vásárol

A Louvre számára ez rendkívül előnyös lehetőség, sokkal jobban jár így, mintha „neki” is licitálnia kellene, hiszen így nem kell versenybe szállnia a többi licitálóval, és csak a végén kell döntenie arról, hogy egy konkrét árért megveszi-e a terméket, vagy sem. A Louvre szakértőjének stratégiája ismert: akkor fogja megvásárolni a tárgyat, ha az a saját rezervációs áránál nem drágább. Ebből adódik, hogy egy játékos akkor vásárolhatja meg a tárgyat, ha ő nyeri meg az árverést, valamint az így kialakult ár magasabb a Louvre rezervációs áránál.


13

Angol árverés A Louvre képviselője egészen addig a pillanatig nem befolyásolja a játékosok stratégiáját, amíg a legmagasabb rezervációs árral rendelkező egyén egyedül nem marad, vagyis addig, ameddig mindenki más ki nem száll a licitálásból. Ekkor az a kérdés, hogy érdemes-e saját magára licitálnia, vagy nem. Ha magasabb licitet mond be, csökkenti annak a valószínűségét, hogy a végén a Louvre falán lógjon a kép, viszont a licit emelésével az is együtt jár, hogy nyerés esetén a vételár magasabb lesz. A legmagasabb rezervációs árral rendelkező játékos a várható profitját fogja maximalizálni: Πi = (ti − bi )P (tL < bi ). az optimális licit nem lesz alacsonyabb a Louvre nélküli szabályokkal meghatározott licitnél, hiszen addig most is mindenkinek érdemes elmenni a licitálásban, mint a Louvre nélküli esetben. Most pedig tegyük fel, hogy a Louvre rezervációs ára szintén egyenletes eloszlású, akárcsak a játékosoké! Ekkor a Πi = bi (ti − bi ) célfüggvényt maximalizáljuk azzal a feltétellel, hogy bi legalább akkora, mint a korábban elhangzott összes licit. Az elsőrendű feltételből kapott optimális licit: ti . 2 Ha a korábbi licitálás során az ár nem emelkedett a legmagasabb rezervációs árral rendelkező játékos értékelésének feléig, akkor a korlátozó feltétel biztosan teljesül, és így neki érdemes tovább licitálnia. Amennyiben az utolsó, elhangzott licit már meghaladja ti felét, akkor a nyereségfüggvény a licitben csökken, ezért a nyertes nem licitál önmagára. bi =

Versenytárgyalás Az i-edik játékos nyeresége (ti − bi ), ha megkapja a tárgyat, egyébként zérus. Minden játékos a várható nyereségét maximalizálja, amely Πi = (bi − ti )P (bj < bi , ∀j 6= i)P (tL < bi ).


14

Annak valószínűsége, hogy az összes többi játékos alacsonyabb licitet mond be az i-ediknél: P (bj < bi , ∀j 6= i) = P tj < Φ (bi ) , ∀j 6= i = F n−1 (Φ(bi )) . Hasonlóképpen, feltéve, hogy a Louvre rezervációs ára szintén F eloszlást követ: P (tL < Bi ) = F (bi ). Vagyis a maximalizálandó függvény: Πi = (ti − bi )F n−i (Φ(bi )) F (bi ). Az elsőrendű feltételből átrendezés után adódik: ∂Φ −F (Φ(bi )) · F (bi ) + f (bi )(ti − bi )F Φ(bi ) · · F (bi )(n − 1) = 0. ∂bi A kifejezés a Louvre nélküli állapothoz tartozóhoz képest a nem negatív f (bi )(ti − bi )F (Φ(b)) taggal több, ezenkívül a többi tag F (bi ) > 0-val be van szorozva. Ezért a kifejezés a zérushelyét nagyobb értéknél veszi fel, mint a Louvre nélküli esetben, vagyis egyensúlyban a licitbemondás nagyobb lesz annál az értéknél, mint amekkora a Louvre nélkül volt. Éljünk a szokásos feltevéssel, miszerint a rezervációs árak eloszlása egyenletes. Ekkor az optimális licitre triviális megoldás: n . n+1 Az egyensúlyi licit magasabb, mintha a Louvre-t nem kellene figyelembe vennünk: épp akkora, mintha a közgyűjtemény mezei licitálóként venne részt a versenytárgyaláson. Érdekes eredmény, hogy noha a Louvre utólag adja be az ajánlatát és az addigi maximális licit ismeretében (és így nem a licitjét, hanem a rezervációs árát kell a többieknek figyelembe venniük), a játékosok mégis úgy tekintik, mint előjogokkal nem rendelkező további résztvevőt. bi = ti ·


15

Vickrey-féle aukció Az előbb már levezettük, hogy Louvre nélkül is minden játékos a rezervációs árán fog licitálni. Ennél többet pedig nem akarhatunk. A Louvre képviselőjének jelenléte nincsen hatással a stratégiákra. Holland aukció Belátható, hogy az árverés kimenetele ismét megegyezik a legmagasabb kínálati árat vételi árnak tekintő aukció stratégiájával. Vagyis akkor érdemes egy játékosnak megállítani az aukció levezetőjét, ha a licit eléri a bi = ti ·

n n+1

értéket.

2.3.2.

A Louvre későbbi eladásra vásárol

Abban az esetben, ha a Louvre később eladhatja a képet, akkor bármelyik aukciófajtát alkalmazzák, érdemes megvennie a tárgyat. Hiszen azt az összeget, amit neki kell adnia a tárgyért, azt már más is felajánlotta. A Louvre nem veszít rajta semmit, ha megpróbálkozik azzal, hogy miután megvette a tárgyat, drágábban adja el, legrosszabb esetben az történik, hogy csak annak tudja eladni, aki az előbb a legmagasabb licitet ajánlotta, mégpedig éppen annyiért, amennyiért ő vette. Ekkor viszont – bármilyen áron vette is meg – mindig érdemes újabb aukciót rendeznie, hátha valamelyik játékos a Louvre rezervációs áránál drágábban is hajlandó megvenni a tárgyat. Ekkor azt a feltételt érdemes kikötnie, hogy ha az aukción kialakuló vételi árat túl alacsonynak tartja, akkor nem köteles eladni a terméket. Ebben az esetben egyensúlyra vezet, ha az első aukción egyáltalán nem licitálnak, hiszen a Louvre mindig vásárol, ha felteheti azt, hogy a licitálók stratégiái olyanok, hogy nem ajánlanak nagyobb árat, mint a rezervációs áruk. Ekkor viszont teljesen felesleges bármekkora árajánlatot is tenni, amikor egy "informatív" kezdeti licitálási stratégia esetleg hasznos információkkal szolgálhat a Louvre-nak, s az növelheti a végső eladási árat. Az viszont világos, hogy senkinek sem éri meg a saját rezervációs áránál többet licitálnia, mivel


16

ekkor – bár így a Louvre ellen dolgozhat – bizonyos valószínűséggel maga ellen játszik. Tehát ennél a kiegészítésnél éppen az ellenkezője fog történni annak, amit el akartunk érni: a játékosok nem fognak licitálni.

3. fejezet Az aukciók hatékonysága Idáig az aukciókat csak úgy vizsgáltuk, hogy egyetlen tárgyat kínáltunk eladásra. A dolgozat hátralévő részében olyan esetet vizsgálunk, ahol több tárgyat szeretnénk eladni, lehetőleg minél magasabb áron, amit Vohra [2] könyvéből dolgozunk fel. Minden játékosnak van egy, a tárgyak olyan X ⊆ 2G halmaza, melyet meg szeretne vásárolni. Hatékony elosztás néven egy olyan közösségi döntést keresünk, ahol adott a lehetséges kimenetelek egy halmaza. Egy csoport minden tagjának vannak (csak számára ismert) preferenciái vagy értékelési függvénye az alternatívákon. Valamilyen meghatározott eljárás keretében saját preferenciáik alapján döntéseket hoznak. Célunk egy olyan eljárás tervezése, amely bizonyos szempontok szerint igazságosnak tekinthető. [6]

3.1.

Kombinatorikus aukciók

Legyen N a játékosok, G pedig a tárgyak véges halmaza. A tárgyak minden S ⊆ G véges halmazára van minden i játékosnak egy vi (S) ≥ 0 nemnegatív értékelése, ahol vi (∅) = 0. A továbbiakban feltesszük, hogy minden vi (S) egész és monoton, tehát ha S ⊆ T ⇒ vi (S) ≤ vi (T ). Ha i játékos az S ⊆ G részhalmazt (a továbbiakban csomagot), és egy p ∈ R összeget fizet azért az S csomagért, akkor a nettó nyereménye vi (S) − p. Azaz itt különböző tárgyakat úgy adunk el, hogy megengedjük a licitá17

FEJEZET 3. AZ AUKCIÓK HATÉKONYSÁGA

18

lóknak, hogy az áruk egy kombinációjára tegyenek ajánlatot, és még garantáljuk a licitálóknak, hogy vagy megkapják a kért kombinációt, vagy pedig nem kapnak semmit. A tárgyak hatékony elosztásának érdekében az egész értékű lineáris programozási feladatot hívjuk segítségül. Ennek megvan az az előnye, hogy ezzel meghatározhatjuk az árfüggvények terét, melyekre szükségünk lesz. Jelentse y(S, i) = 1 azt, hogy az S ⊆ G csomagot az i ∈ N játékos preferálja. (Fontos, hogy tisztázzuk a jelölést: például ha az i játékos a g, h ∈ G különböző termékeket szeretné egyszerre elvinni, akkor y({g, h}, i) = 1, de y({g}, i) = 0. Egy játékos pontosan csak egyetlen csomagot fog elvinni.) XX V (N ) = max vj (S)y(S, j) j∈N S⊆G

XX

y(S, j) ≤ 1 ∀i ∈ G

S3i j∈N

X

y(S, j) ≤ 1 ∀j ∈ N

S⊆G

y(S, j) = 0, 1 ∀S ⊆ G, ∀j ∈ N . Az első feltétel biztosítja, hogy a tárgyak legfeljebb egyszer legyenek kiosztva. A második pedig azt, hogy a licitálók ne kapjanak egynél több csomagot. Legyen ez a (CAP 1) formula. Jelölje Z1 (N ) az optimális célfüggvény értékét a (CAP 1) relaxációnak. Még ha a (CAP 1) lineáris relaxáció felvenne részleges megoldásokat. Írjuk le a lineáris programozási feladat duálisát! P P Jelölés. Minden S3i j∈N y(S, j) ≤ 1 ∀i ∈ G feltételt társítsuk a pi változóval, ami az i ∈ G tárgy ára. P Jelölés. Minden S⊆G y(S, j) ≤ 1 ∀j ∈ N feltételt társítsuk a πj változóval, ami a j ∈ N licitáló nyeresége.


19

A az előbbi jelöléseket felhasználva a duális feladat X X Z1 (N ) = min pi + πj i∈G

πj +

X

j∈N

pi ≥ vj (S) ∀S ⊆ G

i∈S

πj ≥ 0 ∀j ∈ N pi ≥ 0 ∀i ∈ G. Legyen (π ∗ , p∗ ) ennek egy optimális megoldása. Könnyű látni, hogy #+

" πj∗ = max vj (S) − S⊆G

X

p∗i

,

i∈S

amit értelmezhetünk úgy, hogy egy p árvektor mellett minden licitálónak hagyjuk kiválasztani azt a csomagot, ami maximalizálja a nyereségét. Általában V (N ) 6= Z1 (N ), így nem találunk hatékony elosztást. Értelmezhetjük ezt egy lehetetlenségi eredményként: nincs olyan emelkedő aukció, ami csak a tételes árakat használja és egy hatékony elosztáshoz vezetne. Ekkor természetes, hogy keresünk egy erősebb formulát. Ennek az egyik módja, hogy további változókat vezetünk be. Az ilyen formulákat kibővített formuláknak nevezzük. Legyen Π a G-beli tárgyak összes lehetséges szétosztásának halmaza. Ha σ a Π-nek egy eleme, akkor S ∈ σ azt jelenti, hogy az S ⊆ G csomag σ elosztásnak egy része. Legyen zσ = 1 ha a σ szétosztás van érvényben, különben nulla.


20

Ezeket a segédváltozókat használva írjuk fel újra a (CAP 1) formulát: XX V (N ) = max vj (S)y(S, j) j∈N S⊆G

X

y(S, j) ≤ 1 ∀j ∈ N

S⊆G

X

y(S, j) ≤

j∈N

X

zσ

∀S ⊆ G

S∈σ

X

zσ ≤ 1

σ∈Π

y(S, j) = 0, 1 ∀S ⊆ G, j ∈ N zσ = 0, 1 ∀σ ∈ Π. Legyen ez a (CAP 2) formula. (CAP 2) kiválaszt G-ből egy elosztást és úgy rendeli hozzá a szétosztási halmazokat a licitálókhoz, hogy a hatékonyságot maximalizálja. Jelölje Z2 (N ) az optimális célfüggvény értékét a (CAP 2) lineáris programozási feladat relaxációjának. Attól függetlenül, hogy (CAP 2) erősebb, mint (CAP 1), még mindig nem elég ahhoz, hogy V (N ) = Z2 (N ) mindig igaz legyen. Írjuk fel a (CAP 2) lineáris programozási feladat duálisát! P Jelölés. Legyen πs változó az eladó jövedelme a σ∈Π zσ ≤ 1 feltétel mellett. P P Jelölés. Mindegyik j∈N y(S, j) ≤ S∈σ zσ egy p(S) változóval, ami az S csomag ára.

∀S ⊆ G feltételt társítsuk

Az új jelölések segítségével a duális tehát: X Z2 (N ) = min πj + π s j∈N

πj ≥ vj (S) − p(S) ∀j ∈ N, S ⊆ G X πs ≥ p(S) ∀σ ∈ Π S∈σ

πj , p(S), πs ≥ 0 ∀j ∈ N, S ⊆ G,


21

ami röviden annyit tesz, hogy minimalizáljuk a licitálók nyereségét és az eladó bevételét. Vegyük észre, hogy az árak alakulása a csomagok (nemlineáris) függvénye. Ezek az árak csak akkor tartják fenn a hatékony elosztást, ha V (N ) = Z2 (N ). Ezt is értelmezhetjük egy lehetetlenségi eredményként: általában nincs olyan emelkedő aukció, ami csak nemlineáris árakat használ és hatékony elosztást eredményez. Keressünk egy még erősebb formulát! Jelölje µ a tárgyak szétosztását és az elosztás elemeinek licitálókhoz való hozzárendelését egyszerre. Így µ és µ0 lehet ugyanaz az elosztás, de eltérhet a hozzárendelésekben. Jelöljük Γ-val az ilyen elosztás-hozzárendelés párosok összességének halmazát. Értsük µj jelölés alatt azt, hogy µ-ben a j játékos kapja meg a µj halmazt. Legyen δµ = 1, ha a µ ∈ Γ elosztás-hozzárendelés páros valósul meg, különben nulla. Ezekkel az új változókkal találhatunk hatékony elosztást a következő formula megoldásával, amit hívjunk (CAP 3)-nak.

V (N ) = max

XX

vj (S)y(S, j)

j∈N S⊆G

X

y(S, j) ≤

δµ

∀j ∈ N, ∀S ⊆ G

µ:µj =S

X

y(S, j) ≤ 1 ∀j ∈ N

S⊆G

X

δµ ≤ 1

µ∈Γ

y(S, j) = 0, 1 ∀S ⊆ G, ∀j ∈ N . Bikhchandani és Ostroy [1] megmutatta, hogy ennek a lineáris programozási feladatnak van optimális egész megoldása. 3.1.1. Tétel. A (CAP 3) problémának optimális egész megoldása van. Bizonyítás. Megmutatjuk, hogy a (CAP 3) lineáris relaxációnak van optimális egész megoldása. Legyen (y ∗ , δ ∗ ) egy optimális részleges megoldása, és VLP (N ) a célfüggvény értéke ennek a megoldásnak. Mindegyik µ elosztáshozzárendelés párosnak van egy egész megoldása: y(S, j) = 1, ha µ alatt a


22

j licitálóhoz tartozik az S csomag, különben nulla. Ennek a megoldásnak a várható értéke: " # XX X vj (S)y µ (S, j) . δµ∗ µ

j∈N S⊆G

De ez azzal egyenlő, hogy   XX XX X vj (S)y ∗ (S, j) = VLP (N ). vj (S) ·  δµ∗  ≥ j∈N S⊆G

j∈N S⊆G

µ:µj =S

Az egyenlőtlenség az alábbiból következik: X y ∗ (S, j) ≤ δµ∗ ∀j ∈ N, ∀S ⊆ G. µ:µj =S

Így a véletlenszerűen generált egész megoldás várható értéke legalább annyi, mint az optimális részleges megoldásé. Továbbá, ezen egész megoldások közül legalább egynek nagyobb vagy egyenlő az értéke, mint az optimális részleges megoldásé. Nem lehet szigorúan nagyobb, mert ez ellentmondana az (y ∗ , δ ∗ ) optimalitásának. Tehát mindegyik yµ -nek vagy megegyezik a célfüggvény értéke (y ∗ , δ ∗ ) megoldáséval, vagy nincs optimális részleges megoldása. P Jelölés. Mindegyik y(S, j) ≤ µ:µj =S δµ feltételt társítsuk egy pj (S) ≥ 0 változóval, ami azt fejezi ki, hogy a j játékos mennyit fizet az S csomagért. P Jelölés. Mindegyik S⊆G y(S, j) ≤ 1 feltételt társítsuk egy πj ≥ 0 változóval, ami a j licitáló többlete. P Jelölés. A µ∈Γ δµ ≤ 1 feltételt kapcsoljuk össze a πs változóval, ami az eladó bevétele.


23

Az új változóinkat használva a DP 3 duális tehát: X V (N ) = min πj + π s j∈N

pj (S) + πj ≥ vj (S) ∀j ∈ N, ∀S ⊆ G X − pj (S) + πs ≥ 0 ∀µ ∈ Γ µ:µj =S

pj (S) ≥ 0 j ∈ N, ∀S ⊆ G πj ≥ 0 ∀i ∈ N ∪ {s}. A (CAP 3) feladat teljességi feltételének köszönhetően pontos ez a duális feladat. 3.1.2. Lemma. Ha (DP 3) egy optimális megoldása {πi }i∈N ∪s , akkor πj ≤ V (N ) − V (N \ j) minden j ∈ N -re. Bizonyítás. V (N ) az optimális célfüggvény értéke a (CAP 3) problémának. P Válasszuk ki bármely j ∈ N játékost és csökkentsük nullára a S⊆G y(S, j) ≤ 1 feltétel jobboldalát. Ennek a mesterkélt programnak a célfüggvény értéke V (N \ j). Tehát a πj duális változó nem haladja meg a V (N ) − V (N \ j) értéket.

3.2.

A mag

A kombinatorikus aukciós példák kapcsolatban állnak a kooperatív játékokkal. Legyen a kooperatív játék játékosainak halmaza N ∗ = N ∪ {s}, ahol s az eladó. Minden K ⊆ N ∗ játékoshalmazra legyen u(K) = V (K \ {s}) ha s ∈ K, különben nulla, azaz csak a koalíciók tartalmazzák az eladó által ∗ generált értéket. A π ∈ R|N | vektorok halmazát, mely kielégíti a X πi = u(N ∗ ) i∈N ∗

és X i∈K

πi ≥ u(K) ∀K ⊂ N ∗


24

feltételeket, az (N ∗ , u) kooperatív játék magjának nevezzük. A mag ebben az esetben nemüres, mert πs = u(N ∗ ) és πi = 0 minden i ∈ N -re, ami a magban van. 3.2.1. Tétel. Legyen a (DP 3) egy optimális megoldása (π ∗ , p∗ ). Ekkor π ∗ a mag egy eleme. Ha π ∗ a mag egy eleme, akkor létezik olyan p∗ , hogy a (DP 3) egy optimális megoldása (π ∗ , p∗ ). Bizonyítás. Először tegyük fel, hogy (π ∗ , p∗ ) egy optimális megoldása(DP 3)nak. Megmutatjuk, hogy π ∗ a magban van. A mag megszorításai egyértelműek a K és {s} diszjunkt halmazokra. Ezután bármely R ⊆ N halmazra, {πj∗ }j∈N , πs és {p∗j }j∈R a (CAP 3) primál feladat duálisának egy lehetséges megoldása, amikor korlátos az R halmaz. Így a gyenge dualitás X πj∗ + πs∗ ≥ v(R) = u(R ∪ s). j∈R

Végül az erős dualitással X

πj∗ + πs∗ = V (N ) = u(N ∗ ).

j∈N

Most tegyük fel, hogy π ∗ a mag egy eleme. A mag minden része kötődik a tárgyak kiosztásához, hogy elérjék a π ∗ -ot. Legyen µ∗ a π ∗ -hoz kapcsolódó elosztás-hozzárendelés. Ha a j ∈ N játékoshoz tartozik az S csomag µ∗ alatt, akkor legyen p∗j (S) = max{vj (S) − πj∗ , 0}. Ez elegendő annak az ellenőrzéséhez, hogy (π ∗ , p∗ ) alkalmas (DP 3)-ban az optimalitás igazolására, mivel a magfeltétel azt mondja, hogy V (N ) a megoldás célfüggvény értéke. 3.2.2. Definíció. A j játékos határterméke V (N ) − V (N \ j) a kombinatorikus aukciók körében. Gondoljuk át a (CAP 3) problémát. A duális változót összekapcsoltuk a P S⊆G y(S, j) ≤ 1 feltétellel, amit értelmezhetünk a j játékos határtermékeként. Egy j ∈ N játékosnál csökkentsük nullára a megfelelő feltétel jobb oldalát, hogy lássuk miért. Így a j licitálót kivettük a problémából, és az optimális célfüggvény értékében történő változás lesz a j játékos határterméke.


25

Ez az érvelés csak azt mutatja meg, hogy a (CAP 3) optimális duális megoldásai között csak egy olyan van, ami visszaadja j játékos határtermékét. Van-e olyan optimális megoldása (DP 3)-nak, amely egyszerre adja vissza az összes N -beli játékos határtermékét? A válasz: általában nincs. De ha a helyettesítési feltétel teljesül, a válasz igen. 3.2.3. Definíció. Helyettesítési feltétel: a játékosok minden M ⊂ N részhalmazára X V (N ) − V (M ) ≤ V (N ) − V (N \ i) . i∈N \M

Ez a definíció Shapley és Shubik-nak [4] köszönhető. A definíció könnyebben értelmezhető, ha M -et kicseréljük N \ K-ra (K ⊆ N )-re. Ekkor X V (N ) − V (N \ K) ≥ V (N ) − V (N \ i) . i∈K

Azaz a K halmaz határterméke legalább olyan nagy, mint a benne levő játékosok határtermékeinek az összege. 3.2.4. Tétel. Ha a helyettesítési feltétel teljesül, akkor az (N ∗ , u) magban van egy olyan π ∗ pont, melyre πj∗ = V (N ) − V (N \ j) minden j ∈ N -re. Továbbá, ez a π ∗ a magnak azon pontja, ami minimalizálja πs -t. Bizonyítás. Ha πj∗ = V (N ) − V (N \ j) minden j ∈ N , szükségünk lesz a következőre, hogy benne legyen a magban: X πs∗ = V (N ) − (V (N ) − V (N \ j)). j∈N

Bármely K ⊆ N -re X πj∗ + πs∗ = j∈K

=

X X (V (N ) − V (N \ j)) + V (N ) − (V (N ) − V (N \ j)) = j∈K

= V (N ) −

j∈N

X j∈N \K

(V (N ) − V (N \ j)) ≥ V (K) = u(K ∪ s).


26

Az egyenlőtlenség a helyettesítési feltételből következik. Legyen π a mag egy tetszőleges pontja. Emlékezzünk vissza, hogy X πj + πs = V (N ) j∈N

P és j∈N \i πj + πs ≥ V (N \ i). Nézzük csak az egyenlő esetet, és adjuk hozzá az előző egyenlethez, ami azt mondja, hogy πi ≤ V (N ) − V (N \ i). Mivel π ∗ könnyen eléri ennek a felső határát, ebből következik, hogy a π ∗ az a pont a P magban, ami maximalizálja j∈N πj -t. Ez azzal egyenértékű, hogy π ∗ a mag azon pontja, amely πs -t minimalizálja.

3.3.

Emelkedő aukciók

Az emelkedő aukció tulajdonképpen egy hatékony elosztást kereső algoritmus. A hatékony elosztás érdekében az emelkedő aukciókat a szakirodalomban primál-duál algoritmussal, vagy szubgradiens algoritmussal optimalizálják. A dolgozatban csak a primál-duál algoritmust nézzük meg.

Az emelkedő aukció definíciója Adott p ∈ R|G| termék árak mellett jelöljük D(p)-vel a tárgyak azon részhalmazait, amik maximalizálják egy játékos hasznosságát, azaz X D(p) = arg max{v(S) − pi }. S⊆G

i∈S

3.3.1. Definíció. Bruttó helyettesítők: Az árak minden p, p0 vektorára, melyekre p0 > p, és minden S ∈ D(p), akkor van olyan B ∈ D(p0 ), melyre {i ∈ S : pi = p0i } ⊂ B. G

3.3.2. Definíció. Legyen p : [0, 1] → R2 ×N egy ár-út. Ekkor minden H ⊆ G csomagra legyen pi,H (t) az az ár, amit az i licitáló lát a H csomagra a t „időpillanatban”.


27 G

3.3.3. Definíció. Egy A emelkedő aukció a licitálók összes v ∈ R2+ ×N értékelési profiljához hozzárendel egy A(v) = p ár-utat, ami csak a kereslettől G függ: minden v, v 0 ∈ R2+ ×N értékelési profilra legyen p = A(v), ha (∀t ∈ [0, 1], i ∈ N, Di (p(t); v) = Di (p(t), v 0 )) akkor A(v 0 ) = A(v). Így, ha egy v profil meghatároz egy emelkedő aukcióban egy p ár-utat, és ha egy másik v 0 profilban mindegyik licitáló a p út árain keresi ugyanazt a terméket, akkor a v 0 profil az aukcióban ugyanazt a p ár-utat eredményezi.

3.3.1.

Primál-Duál Algoritmus

Először a primál-duál algoritmus egy magasabb szintű leírásával kezdjük, amit később (CAP 3)-ban alkalmazunk. Nézzük meg a következő lineáris programozási feladatot: Z = max(cx) n X

aij xj ≤ bi

∀i = 1, . . . , m

j=1

xj ≥ 0

∀j = 1, . . . , n

Itt A = {aij } egy valós számokból álló mátrix. Ennek a lineáris programozási feladatnak a duálisa: Z = min(yb) m X aij yi ≥ cj

∀j = 1, . . . , n

i=1

yi ≥ 0 Legyen y ∗ a duális egy megoldása. P (1) y ∗ > 0 ⇒ nj=1 aij xj = bi ; Pm ∗ (2) i=1 aij yi > cj ⇒ xj = 0.

∀i = 1, . . . , m


28

Meg kell oldanunk a következőt feladatot, hogy találjunk a primál feladatnak egy lehetséges megoldást, ami az y ∗ komplementere: n X j=1 n X

aij xj = bi

∀i ha y ∗ > 0

aij xj ≤ bi

∀i ha y ∗ = 0

j=1

xj = 0 ∀j ha

n X

aij yi∗ > cj

i=1

xj ≥ 0 ∀j ha

n X

aij yi∗ = cj .

i=1

Ez a rendszer a korlátozott primál feladat. Ha megvalósítható a korlátozott primál feladat, akkor kész vagyunk. Ha nem, akkor a Farkas Lemmának köszönhetően az alternatív feladatnak (a korlátozott primál feladat duálisának) van megoldása. Legyen ez a megoldás y, ami teljesítse a következőket: (1) yb < 0, és (2) y ∗ + y megvalósítható a duálisban elég kicsi > 0-ra. Válasszuk y ∗ + y-t a duális új lehetséges megoldásának, és ismételjük meg a kört. Az aukciós környezetben a duális változók megfelelnek az áraknak. Az y változó pedig az árkorrekció irányának. Egy „emelkedő” aukció bizonyításáért biztosítani kell, hogy y ≥ 0. Probléma lehet még megválasztása. Ezt úgy adjuk meg, hogy feltesszük, mint korábban, hogy a változóink egészek. Ezzel emelhetjük az árakat egy egységgel anélkül, hogy megsértenénk a duális megvalósíthatóságot. Primál-duál alkalmazása (CAP 3)-ban Az árak bármely listájára legyen pj (S) ≥ 0 (ahol pj (∅) = 0), a többi változót pedig az alábbiak szerint megválaszhatjuk úgy (DP 3)-ból, hogy biztosítsák a


29

megvalósíthatóságot. Az egész algoritmusban fenntartjuk a következő egyenlőségeket: πj = max [vj (S) − pj (S)] S⊆G

πs = max µ∈Γ

X

pj (µj ),

j∈N

ahol πj a j játékos nyeresége az aktuális árakon, πs pedig az eladóé. Illetőleg definiáljuk még az aktív licitálók halmazát, a keresleti összhangot bármely j licitálóra, az eladó kínálati megfelelését, és olyan feladatot, hogy ne jelöljön ki nemkeresett tárgyakat. (1) N + = {j ∈ N : πj > 0} (2) Dj (p) = arg maxS⊆G (vj (S) − pj (S)) = {S ⊆ G : πj = vj (S) − pj (S)} P P (3) Γ∗ = arg maxµ∈Γ j∈N pj (µj ) = {µ ∈ Γ : πs = j∈N pj (µj )} (4) Γ∗ (D) = µ ∈ Γ∗ | ∀j ∈ N : µj ∈ Dj (p) ∪ {∅} Az eladó kínálati megfelelésének Γ∗ (D) halmaza összeegyeztethető a licitálók keresletével abban az értelemben, hogy nincsenek kijelölve nemkeresett csomagok. A (nem redundáns) kiegészítő eltérési feltételek: X j ∈ N + =⇒ y(S, j) = 1 ∅6=S⊆G

S∈ / Dj (p) ∪ {∅} =⇒ y(S, j) = 0 µ∈ / Γ∗ =⇒ δµ = 0. Fűzzük hozzá ezeket a feltételeket (CAP 3)-hoz, hogy kihozzuk a korlá-


30

tozott primál feladatot: X

y(S, j) =

δµ

∀j ∈ N, ∀S ⊆ G

µ:µj =S

X

y(S, j) = 1 ∀j ∈ N +

∅6=S⊆G

X

y(S, j) ≤ 1 ∀j ∈ / N+

∅6=S⊆G

X

δµ = 1

µ∈Γ

0 ≤ y(S, j) ∀j ∈ N, ∀S ∈ Dj (p) ∪ ∅ y(S, j) = 0 ∀j ∈ N, ∀S ∈ / Dj (p) ∪ ∅ 0 ≤ δµ

∀µ ∈ Γ∗

δµ = 0 µ ∈ / Γ∗ . Ezek a feltételek azt jelentik, hogy minden µ ∈ / Γ∗ (D)-hez δµ = 0. Egyszerűsíthetjük úgy a programot, hogy az összes változót nullára csökkentjük. Ezentúl tekintsük a (δµ )µ∈Γ / ∗ (D) és (y(S, j))S∈Dj (p)∪{∅} változókat, melyeket beállítunk nullára. X δµ ∀j ∈ N, ∀S ∈ Dj (p) ∪ {∅} (RP) y(S, j) = µ∈Γ∗ :µj =S

X

y(S, j) = 1 ∀j ∈ N +

S∈Dj (p)

X

y(S, j) ≤ 1 ∀j ∈ / N∗

∅6=S∈Dj (p)

X

δµ = 1

µ∈Γ∗ (D)

0 ≤ y(S, j) ∀j ∈ N, ∀S ∈ Dj (p) ∪ {∅} 0 ≤ δµ

∀µ ∈ Γ∗ (D).


31

Ha (RP ) megvalósítható, akkor egy (π, p) optimális megoldásból kezdtünk, és kész is vagyunk. Másképpen a Farkas Lemma azt jelenti, hogy van lehetséges megoldása a következő alternatív egyenletrendszernek: X (DRP) λ+ λj < 0 j∈N

λj + ρj (S) ≥ 0 ∀j ∈ N, ∀S ∈ Dj (p) ρj (∅) ≥ 0 ∀j ∈ N + X λ− ρj (µj ) ≥ 0 µ ∈ Γ∗ (D) j∈N

ρj (S) ≷ 0 ∀j ∈ N, ∀S ∈ Dj (p) λ≷0 λj ≷ 0 ∀j ∈ N + λj ≥ 0 j ∈ / N +, ahol ρj (S) a j licitáló árváltoztatásának iránya az S csomagért. Ennek következtében a nem keresett csomagok árait nem változtatjuk meg. Legyen λj a j játékos nyereségében történő változás, λ pedig az eladóéban. Amikor (RP ) végrehajthatatlan, akkor (DRP ) első egyenlőtlensége szerint csökken a teljes nyereség. Egy emelkedő aukció definiálása érdekében találnunk kell (DRP )-nek egy olyan megoldást, hogy ρj (S) ≥ 0 minden j ∈ N -re és S ∈ Dj (p) ∪ ∅-ra. Egy ilyen megoldás nem létezik, ha (DP 3) változóit (azaz pj (S)-eket) önkényesen választjuk. Létezik azonban, ha teljesül az ún. túlkeresleti tulajdonság, melyet a későbbiekben definiálunk. Azt szeretnénk megmutatni, hogy ez a tulajdonság teljesülni fog a későbbi eljárás során. A túlkeresleti tulajdonság definiálásához (RP )-be mesterséges változókat


32

vezetünk be. Minden K ⊆ N + -ra legyen X (OD) Z(K) = max − zj j∈K

X

y(S, j) =

µ∈Γ∗ (D):µ

X

δµ

∀j ∈ N, ∀S ∈ Dj (p) ∪ {∅}

j =S

y(S, j) + zj = 1 ∀j ∈ N +

S∈Dj (p)

X

y(S, j) ≤ 1 ∀j ∈ / N+

∅6=S∈Dj (p)

X

δµ = 1

µ∈Γ∗ (D)

0 ≤ y(S, j) ∀j ∈ N, ∀S ∈ Dj (p) ∪ {∅} δµ ≤ 1 0 ≤ δµ

∀µ ∈ Γ∗ (D)

0 ≤ zj

∀j ∈ N + .

A következőkben kihasználjuk, hogy (OD) megoldhatósági tartománya nem függ K megválasztásától. (DP 3) változóinak egy adott listájáról azt mondjuk, hogy a túlkereslet fennáll, ha (OD) megvalósítható és Z(N + ) < 0. (OD) megvalósíthatósága megköveteli, hogy Γ∗ (D) legyen nemüres, viszont ebből az következik, hogy a nem hozzárendelt tárgyakat nem lehet úgy elosztani, hogy az eladónak további nyeresége legyen. Így ez megakadályozza, hogy az árak túl magasra szökjenek. Továbbá, ha a túlkereslet fennál, akkor (RP ) megvalósíthatatlan, mivel (RP ) bármely megengedett megoldása az (OD)-nek is megoldása Z(N + ) = 0 célfüggvény értékkel. A következő definíció fontos ahhoz, hogy leírjuk azokat az árváltozásokat, amiket használunk. 3.3.4. Definíció. Amikor túlkereslet áll fenn, akkor azt mondjuk, hogy egy K ⊆ N + koalíció alulkínált, ha Z(K) < 0. A koalíció minimálisan alulkínált, ha minden K 0 ( K-ra Z(K 0 ) = 0.


33

Vegyük észre, hogy a definíció nem fog megváltozni, ha „minden K 0 ( K” részt kicseréljük „minden K 0 = K \ {j} j ∈ K”-ra. Továbbá, ha túlkereslet van, akkor van legalább egy nemüres, minimálisan alulkínált koalíció. A következő tulajdonság megmutatja, hogy a nemnegatív árváltozásokat ki lehet választani úgy, hogy csak a minimálisan alulkínált licitálók látnak pozitív áremelkedést. 3.3.5. Tétel. Ha a túlkereslet fennáll, akkor bármely minimálisan alulkínált K koalícióra van (DRP )-nek olyan megoldása, hogy ρj (S) = 1 minden j ∈ K-ra és S ∈ Dj (p)-re, különben ρj (S) = 0. Bizonyítás. Tegyük fel, hogy minden T ⊆ N + -ra Z(T ) = max |{j ∈ T : µj ∈ Dj (p)}| − |T |. ∗ µ∈Γ (D)

Jelölje ΓT = arg maxµ∈Γ∗ (D) |{j ∈ T : µj ∈ Dj (p)}| azon elosztásokat, melyek megfelelnek a legtöbb T -beli licitálónak. Legyen K minimálisan alulkínált. Mivel Z(K \ j) = 0 bármely j ∈ K-ra, könnyű látni, hogy Z(K) = −1, tehát |K| − 1 licitáló (lehet) elégedett. A lineáris programozás dualitás tételével kapjuk tehát, hogy: X Z(K) = min λ + λj j∈N

λj + ρj (S) ≥ 0 ∀j ∈ N, ∀S ∈ Dj ρj (∅) ≥ 0 ∀j ∈ N + λ≷0 λj ≥ −1 ∀j ∈ K λj ≥ 0 ∀j ∈ / N \K σ≥0 Mivel Z(K) < 0, a fenti program bármely optimális megoldása (DRP )-nek is egy lehetséges megoldása. Megmutatjuk, hogy van egy, ahol ρj (S) = 1 minden j ∈ K-ra és S ∈ Dj (p)-re, különben ρj (S) = 0.


34

Legyen λj = −1 minden j ∈ K-ra, különben nulla. Legyen λ = |K| − 1. Ez egyértelműen megoldható, és optimális is, mivel X λ+ λj = |K| − 1 − |K| = −1, N

teljesítik a bizonyítást. Így konstruktívan meghatároztuk a következő árkiegyenlítési eljárást: (1) Azonosítsuk a minimálisan alulkínált K licitálók halmazát. (2) Minden j ∈ K-ra és S ∈ Dj (p)-re adjuk hozzá pj (S)-hez ρj (S) = 1-et, egyébként ne változtassunk pj (S) értékén. (3) Minden j ∈ K-ra módosítsuk πj -t λj = −1-re, és minden j ∈ / K-ra ne módosítsunk πj értékén. (4) Növeljük meg πs értékét λ = |K| − 1-gyel. Az árkiegyenlítés után tisztán látszik, hogy minden j ∈ / K licitálóra a keresleti összhang nem változik. Mivel feltettük, hogy az értékelések egészek, így csak egy ρj (S) = 1 (∀j ∈ K) árnövekedés tudja csak a j játékos keresleti összhangját növelni; a keresett csomagokból nem lehet nemkeresett (feltéve, hogy az árak egészek). 3.3.6. Lemma. Ha az árak egészek, akkor Dj (·) gyengén növekszik az árkiegyenlítés után. Ennek megfelelően, ha pj (S) növekedett bármelyik árkiegyenlítés alatt, akkor az összes későbbi iterációban a j licitáló keresletének az S csomagnak kell lennie. Ebből adódóan, ha az algoritmust nulla árakról kezdtük (p = 0), akkor csak a keresett csomagoknak lesz pozitív ára. Egy másik megfigyelés az, hogy egy árkiegyenlítés után az eladó keresletkompatibilis Γ∗ (D) kínálati megfeleltetése két módon változhat. Először, néhány µ ∈ Γ∗ (D)-re egy árváltoztatás után már nem lehet maximalizálni a bevételt. Ebben az esetben, mivel az eladó bevétele λ = |K| − 1 értékkel változik, akkor µ-ből a bevétel változása |{j ∈ K : µj ∈ Dj (p)}| ≤ |K| − 2.


35

Másodszor, néhány µ ∈ / Γ∗ (D) egy árváltoztatás után maximalizálja a bevételt. Ez csak akkor történhet meg, ha {j ∈ K : µj ∈ Dj (p)} = K és még az árváltozás előtt, X X pj (µj ) = pj (µ0j ) − 1, j∈N

j∈N

ahol µ0 ∈ ΓK . Annak bizonyítására, hogy az árak csak az algoritmuson keresztül növekedhetnek, kell a következő eredmény. 3.3.7. Tétel. Kezdjük az algoritmust p = 0-ról. Az algoritmus végéig mindegyik iterációra fennáll a túlkereslet. Bizonyítás. Ha mindegyik árat beállítjuk pj (S) = 0-ra, akkor a túlkereslet: minden licitáló kereslete Dj (p) = G, és Γ∗ (D) az n elosztások halmaza úgy, hogy egy licitálót rendeltünk hozzá G-hez, a többiek pedig nem kapnak semmit. Azaz (OD) lehetséges, ha N + = N és Z(N ) < 0. Továbbá, ha az iteráció elején az árak egészek, akkor utána is egészek maradnak annak köszönhetően, hogy előírtuk az árak egész értékkel való növekedését. Ehhez elég annyit belátni, hogy (OD) megvalósíthatósága a következő iterációból jön: ha Z(N + ) < 0 az iteráció után, akkor fennáll a túlkereslet, egyébként Z(N + ) = 0 és az algoritmus egy optimális megoldásban ér véget. Lentebb a t alsó- vagy felsőindex jelöli az ármódosítás t-edik iterációja alatt egy változó értékét. Tegyük fel, hogy a t iterációban (OD) megoldható (és ezek az árak egészek). Megmutatjuk, hogy a t iterációban (OD) egy optimális megoldása egy megvalósítható megoldást definiál (OD) t+1-edik lépésére. Legyen (δ t , y t , z t ) egy ilyen optimális megoldás, és az általánosság elvesztése nélkül tegyük fel, hogy ez a megoldás egész (ami (CAP 3)-ból következik), így δµtˆ = 1 néhány µ ˆ-ra. A µ ˆ hozzárendelés kielégíti a |K t | − 1 licitáló keresletét (ahol K t a minimálisan alulkínáltak halmaza a t-edik körben). Mivel πst+1 = πst + |K t | − 1, akkor ez a hozzárendelés még mindig maximalizálja a bevételt a t + 1-edik körben, azaz µ ˆ ∈ Γ∗t+1 . A 3.3.6 lemmából következik, hogy µ ˆ ∈ Γ∗t+1 (D). Így (OD) egy lehetséges megoldását a t + 1-edik iterációban úgy állíthatjuk elő, hogy (δ t , y t , z t )-ből beállítjuk δµt+1 = 1-re és az összes többi δµt+1 ˆ


36

változót pedig nullára. Ebből következik, hogy y(ˆ µj , j)t+1 = 1 minden j ∈ N re azzal a feltétellel, hogy µ ˆj ∈ Dj (p) ∪ {∅}, különben y(S, j)t+1 = 0. A zjt+1 változókat nyilván úgy választottuk, hogy teljesítsék a lehetséges megoldásokat minden j ∈ N + -ra, zj = 1 akkor és csak akkor, ha µ ˆj = 0. A 3.3.5 és 3.3.7 tételekből következik, hogy az algoritmusban az árak nemcsökkenők. 3.3.8. Tétel. Módosítsuk az aukciót a következők szerint: rögzítsünk egy k licitálót. Amikor lehetséges, mindegyik szakaszban válasszunk egy olyan minimálisan alulkínált halmazt, mely kizárja k-t. Ekkor a k licitálónak V (N ) − V (N \ k) lesz a végén a kifizetése. Bizonyítás. Megmutatjuk, hogy πs = V (N )−V (N \k) lesz a végén. Tegyük fel, hogy mégsem. Mivel 0 ≤ πi ≤ V (N ) − V (N \ i) minden i ∈ N -re, ebből következik, hogy 0 < πk < V (N ) − V (N \ k). Nézzük meg az utolsó lépést, mondjuk t-t, ahol πkt 6= V (N ) − V (N \ k). Mivel az árak egyszerre egy egységgel nőnek, ebben a lépésben πkt = V (N ) − V (N \ K)-nak kell lennie. A feltevésünk az, hogy nincs olyan minimálisan alulkínált halmaz, mely kizárja k-t. Ezért N -nek minimálisan alulkínáltnak kell lennie. Kell lennie még egy olyan µ ∈ Γ∗ (D)t -nek, amire µj ∈ Djt minden j 6= k-ra. Mivel πkt = V (N ) − V (N \ k) ebben a lépésben, a duális változó értékei itt szuboptimálisak. Így X V (N ) < πst + πit = i∈N

=

X j∈N

ptj (µj ) +

X i∈N

πit =

X j6=k

X t vj (µj ) − πjt + πi ≤ V (N \ k) + πkt . i∈N

Ezért V (N ) < V (N \ k) + (V (N ) − V (N \ k)) = V (N ), ami ellentmondás. Őszinte licitáláskor (CAP 3)-ra a primál-duál aukció olyan árakban végződik, amik maximalizálják a licitálók nyereségét. Ha a túlkeresleti tulajdonság fennáll, abból következik a 3.2.4 tétel, hogy ezek az árak megfelelnek a Vickrey-aukció kifizetésének.


37

3.3.9. Tétel. Ha az túlkeresleti tulajdonság fennáll, akkor a p = 0 árakról kezdve, (CAP 3)-ra a primál-duál aukció a Vickrey-árakban ér véget. Bizonyítás. Megmutatjuk, hogy minden i ∈ N -re πi = V (N ) − V (N \ i) lesz a végén. Tegyük fel, hogy mégsem, és nézzük meg az aukció olyan utolsó esetét, ahol egy vagy több játékosnak meghaladja a többlete a határtermékét. Legyen ez a halmaz a licitálók egy Q halmaza, és tegyük fel, hogy a t lépésben vagyunk. Ekkor πjt = V (N ) − V (N \ j) + 1 ∀j ∈ Q és πjt ≤ V (N ) − V (N \ j) ∀j ∈ / Q. A t iteráció végén egyik licitálónak sem lesz úgy nyeresége, hogy meghaladná a határtermékét. Ebből adódóan minden Q-beli játékosnak látnia kellett az árak egységnyi növekedését. Ezért Q egy K minimálisan alulkínált halmaz egy része. Először tegyük fel, hogy Q a K-nak egy valódi részhalmaza. Ekkor van egy olyan µ ∈ Γ∗ (D) a t lépésben, amely kielégíti Q-ban az összes licitálót. Legyen T a játékosok azon halmaza, akik elégedettek µ-ben. Ekkor X ptj (µj ) és ptj = vj (µj ) − πjt minden j ∈ T -re. πst = j∈T

Mivel az aukció nem ér véget a t lépésben, (DP 3)-ban a πst , és πjt aktuális értékei nem optimálisak. Ebből következik, hogy X V (N ) < πst + πit . i∈N

De πst +

X i∈N

πit =

X

ptj (µj ) +

j∈N

≤ V (T ) +

X i∈N

X i∈T /

πit =

X

X t vj (µj ) − πjt + πi ≤

j∈T

πit ≤ V (T ) +

i∈N

X

(V (N ) − V (N \ i)) .

i∈T /

Az utolsó egyenlőtlenség abból következik, hogy Q ∩ {N \ T } = ∅. Ezért P V (N ) < V (T ) + i∈T / (V (N ) − V (N \ i)), ami ellentmond (ASC)-nek. Most tegyük fel, hogy Q = K. Mivel Q minimálisan alulkínált, a t lépésben tudunk egy olyan µ ∈ Γ∗ (D)-t választani, ami Q-ban kielégíti az összes licitálót, kivéve k-t.


38

Ahogy az előbb, T legyen azon licitálók halmaza, akiket µ kielégített, és X X V (N ) < V (T ) + πit ≤ V (T ) + πik + (V (N ) − V (N \ k) + 1) . (3.1) i∈T /

i∈T / ∪k

Minden i ∈ T ∪ k-ra πit ≤ V (N ) − V (N \ i). Ha ezek közül bármelyik egyenlőtlenség szigorú, akkor a 3.1 egyenlőtlenség ellentmondás. Tegyük fel, hogy nem az. Ekkor πit = V (N ) − V (N \ i) minden i ∈ Q = T ∪ k-ra. Mivel Q-n kívül egy licitáló sem lát áremelkedést, ez azt jelenti, hogy az iteráció végén minden licitálónak a határtermékével megegyező a nyeresége. Ha az algoritmus ebben a pontban ér véget, akkor kész vagyunk. Ha nem, akkor a t + 1-edik iterációban lennie kell egy alulkínált halmaznak. Válasszunk egy µ-t a jelenlegi Γ∗ (D) halmazból. Ekkor, ahogy az előbb X πst+1 + πit+1 = i∈N

=

X

πit+1 =

X

πit ≤ V (T ) +

X

pt+1 j (µj ) +

j∈N

≤ V (T ) +

X i∈N

X i∈T /

Ezért V (N ) < V (T ) + sítési feltételnek.

j∈T

X t+1 vj (µj ) − πjt+1 + πi ≤ i∈N

(V (N ) − V (N \ i) .

i∈T /

P

i∈T /

(V (N ) − V (N \ i)), ami ellentmond a helyette-

Irodalomjegyzék [1] Bikhchandani, S és J. Ostroy [2002]: „The Package Assignment Model”, Journal of Economic Theory, 377-406. oldal [2] Rakesh V. Vohra [2011]: Mechanism Design: A Linear Programming Approach, 82-108. oldal [3] Rasmusen, E. [1990]: Games and Information (An Introduction to Game Theory). Basil Blackwell Ltd. [4] Shapley, L. S. és M. Shubik [1972]: „The Assignment Game I: The Core,” International Journal of Game Theory. 1, 111-130. oldal [5] Szatmári Alexandra [1996]: Aukciók, avagy a képpe kerül, ha a Louvre képke kerül? Közgazdasági szemle, 303-314. oldal [6] Végh László – Pap Júlia – Király Tamás [2016] Játékelmélet jegyzet (http://www.cs.elte.hu/~tkiraly/students/jatekelmelet_ jegyzet.pdf)

39

Orosz Alexandra. Árverési mechanizmusok

Recommend Documents