Kombinatorikus aukciók és alkalmazásaik

Kápolnai Richárd
konzulensek: Dr. Kis Tamás és Dr. Váncza József (MTA SZTAKI, tamas.kis@sztaki.hu, vancza@sztaki.hu)

Elterjedőben van a közkedvelt aukciónak egy új általánosítása, a kombinatorikus aukció, melyben különböző árukat árvereznek el úgy, hogy az aukciós ház (az árverező) egyrészt megengedi a licitálóknak, hogy az áruk kombinációira tegyenek ajánlatot, másrészt garantálja az egyes licitálóknak, hogy vagy valamelyik kért kombinációt kapják meg, vagy pedig semmit. Például az aukciós ház elfogadhat ajánlatokat telkek árverése során szomszédos telkekre, vagy beszállítói pályázatok esetén különböző alkatrészekre együtt stb. A leggyakrabban említett alkalmazás az amerikai Federal Communinations Commision (FCC) által szervezett aukciók, ahol például távközlési frekvenciasávok koncessziós jogait árverezik el. A győztesek kiválasztasása általános esetben NP-nehéz feladat (ábra).

Egy aukcióval szemben számos követelményt szokás támasztani, mi a második félév során az ösztönzést vizsgáltuk. Egy aukció igazmondásra ösztönöz, ha a licitálók számára a lehető legjobb stratégia a saját, titkos értékelés felfedése (például Vickrey-féle aukció). A licitálókról feltételezzük, hogy önző, és racionális ágensek, ami azt jelenti, hogy egyetlen céljuk az aukción való részvétel során a saját profitjuk maximalizálása, azaz számukra minél értékesebb kincsekhez jutni minél olcsóbban. Céljaik eléréséért különféle stratégiákhoz folyamodnak, a valódi értékelésük természetesen titkos. Az egyfordulós aukciók esetében sokféle elfajult aukciót kizártunk, melyek biztosan nem lehetnek ösztönzők. Többfordulós aukciók analitikus vizsgálata nagyon nehéz, ezért írtam egy szimulációs programot, melyben többféle stratégiát versenyeztettünk megmaradt repülőjegyekért (ábra). Az esetek többségében kimagaslóan jól járt az a játékos, mely őszintén felfedte titkát, és teljesen rábízta magát az aukciós házra (s1 stratégia). Sokkal gyengébb volt az a játékos, mely mindig résen volt, és ha túllicitálták, minimálisan emelt az ajánlatán (s5 stratégia).

Általánosítsuk az aukció fogalmát: mechanizmusnak nevezünk egy (A, P) párost, ahol A allokációs függvény kiosztja (vagy lefoglalja) az erőforrásokat, P fizetségfüggvény kiszámítja az árakat. A harmadik (utolsó) félév során egy kötegelt ütemező mechanizmusát (ütemező + fizetség) terveztük meg. A kötegelt ütemezési feladat a következő: adott N oszthatatlan feladat, a feladatok n típusba (kötegbe) sorolhatóak, az azonos típusú feladatok azonos adottságúak. A feladatokat különböző sebességű gépekhez kell rendelni úgy, hogy egy gépnek egy feladat megkezdése előtt a típusra jellemző beállítási feladatot el kell végeznie (csak egyszer). Cél a befejezési idő leszorítása (mely NP-nehéz). Modellünkben önző és racionális ágensek birtokolják a gépeket, és a gép pontos sebességet csak a tulajdonosa ismeri. A mechanizmusunk randomizált, várható értékben ösztönző, gyors és közelítőleg hatékony (a befejezési idő legfeljebb 6-szorosa az optimumnak). Az ütemező először kiszámít egy T alsó korlátot a befejezési időre abból, hogy minden beállítást legalább egyszer biztosan meg kell csinálni (ábra), majd 2T határidővel egy tört (preemptív) ütemezést készít (ábra), majd sorsolással egészértékűvé kerekíti az ütemezést, legfeljebb megháromszorozva a befejezési időt (ábra).

Eredmények értékelése

Az implementált iteratív aukcióban a statisztikák szerint nem érdemes kihasználni az iteratív aukció adta lehetőségeket, és apránként emelgetni a licitet, hogy ne essünk ki, ajánlatosabb az automatikus licitálást választani. Az áremelés lépésközének változtatásával vagy a fordulók számának növelésével csökkenthető lenne a két stratégia közötti eltérés, de a valóságban erősen korlátozottak ezen értékek. Az eredmény összhangban volt feltevésünkkel. Említésre méltó eredményt nem találtunk az irodalomban sem iteratív stratégiákról, sem az automatikus bid Vickrey-árral való kapcsolatáról, mellyel eredményeinket alátámaszthatnánk.

Az ütemező mechanizmusunk eddig az egyetlen létező ösztönző protokoll a kötegelt ütemezési feladatra. A kötegelt ütemezés magában is nagyon nehéz, még jó approximációs közelítést sem publikáltak. A kötegnélküli speciális eset megoldásából indultunk ki (Archer és Tardos, 2001), de az általánosításunk során több ötletre is szükségünk volt, melyek nélkülözhetetlen részei lettek a végső mechanizmusnak.

A kombinatorikus aukciókról, közelítő ütemezésekről és a mechanizmus-tervezésről rengeteg irodalmat találhat az Érdeklődő az Interneten. Kulcsszavak angolul: “combinatorial auction”, “bidding strategies” (licitálási stratégiák), “incentive compatible” vagy “truthful” (ösztönzés), proxy bid (automatikus bid), “approximation scheduling” (közelítő ütemezés), “mechanism design”.


Kapcsolódó publikációk