Anarchia ára aukciókon - Price of anarchy in auctions

Az Anarchia ára ( PoA ) a játékelmélet és a mechanizmus tervezésének olyan fogalma, amely azt méri, hogy a rendszer társadalmi jóléte hogyan romlik le ügynökeinek önző magatartása miatt. Széles körben tanulmányozták különböző összefüggésekben, különösen árveréseken .

Egy aukción egy vagy több tétel és egy vagy több ügynök van, akiknek az értékelése eltérő. A tételeket fel kell osztani az ügynökök között. Kívánatos, hogy a szociális jólét - az összes ügynök értékeinek összege - a lehető legmagasabb legyen.

A szociális jólét maximalizálásának egyik megközelítése egy igaz mechanizmus megtervezése . Egy ilyen mechanizmusban minden ügynököt ösztönöznek arra, hogy valódi értékeléseit jelentse az elemeknek. Ezután az aukcióvezető kiszámíthat és megvalósíthat egy allokációt, amely maximalizálja az értékek összegét. Ilyen mechanizmusra példa a VCG aukció .

A gyakorlatban azonban nem mindig valós valósághű mechanizmusok alkalmazása. A VCG-mechanizmus például túl bonyolult lehet a résztvevők megértéséhez, túl sokáig tarthat az aukciós lebonyolítója, és más hátrányai is lehetnek. A gyakorlatban gyakran alkalmaznak nem valósághű mechanizmusokat, és érdekes kiszámolni, hogy ez a nem igazmondás mennyire veszíti el a szociális jólétet.

Gyakran feltételezik, hogy egy nem igaz aukción a résztvevők egyensúlyi stratégiát játszanak, például Nash-egyensúlyt . Az aukció anarchiájának árát az optimális szociális jólét és a legrosszabb egyensúlyban lévő szociális jólét arányaként határozzák meg :

${\ displaystyle PoA = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ min _ {s \ in EquilibriumAllocations} Welf (s)}}}$

Ehhez kapcsolódó fogalom a stabilitás ára ( PoS ), amely a legjobb egyensúlyban méri az optimális szociális jólét és a szociális jólét arányát :

${\ displaystyle PoS = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ max _ {s \ in EquilibriumAllocations} Welf (s)}}$

Nyilvánvalóan . ${\ displaystyle 1 \ leq PoS \ leq PoA \ leq \ infty}$

Ha teljes információ áll rendelkezésre (minden ügynök ismeri az összes többi ügynök értékelését), akkor a közös egyensúlyi típus a Nash-egyensúly - akár tiszta, akár vegyes. Ha hiányos információ van , akkor a közös egyensúlyi típus a Bayes-Nash egyensúly . Ez utóbbi esetben általános az anarchia Bayes-féle áráról vagy BPoA-ról beszélni.

Egy tételes aukciók

Egy első aukciót egyetlen tétel, akkor a Nash-egyensúly mindig hatékony, így a POA és POS 1.

Egy másodáras aukción Nash-egyensúly van, amelyben az ügynökök hűen beszámolnak; hatékony, tehát a PoS 1. Azonban a PoA korlátlan! Tegyük fel például, hogy két játékos van: Alice az elemet a-nak , Bob pedig b-nek értékeli , a > b értékkel .

Létezik egy "jó" Nash-egyensúly, amelyben Alice a , Bob pedig b ; Alice megkapja a tételt és fizet b . A szociális jólét a , ami optimális.

Van azonban egy "rossz" Nash-egyensúly is, amelyben Alice 0, Bob pedig +1 ajánlatot tesz ; Bob megkapja a tételt, és nem fizet semmit. Ez egyensúly, mivel Alice nem akarja túllicitálni Bobot. A szociális jólét b . Ezért a PoA a / b , amely nincs korlátozva.

Ez az eredmény túlságosan pesszimistának tűnik:

Először is, egy második árverésen gyengén domináns stratégia, hogy minden ügynök beszámoljon valódi értékeléséről. Ha feltételezzük, hogy az ügynökök követik domináns stratégiájukat, akkor a PoA értéke 1.
Sőt, minden ügynök számára meghatározó stratégia , hogy a valódi értékelése fölötti értéket jelentse.

Ezért gyakori, hogy a PoA elemzését túlfeltételezés nélküli feltételezéssel elemezzük - egyetlen ügynök sem ajánlatot tesz a valódi értékelése fölött. E feltételezés szerint az egy tételes aukció PoA értéke 1.

Párhuzamos aukciók

Párhuzamos (egyidejű) aukción a tárgyakat egyidejűleg ugyanazon résztvevői csoportnak adják el . Ellentétben a kombinatorikus aukcióval - amelyben az ügynökök árucsomagokra tudnak licitálni, itt az ügynökök csak az egyes tételekre licitálhatnak a többitől függetlenül. Vagyis az ügynök stratégiája az ajánlatok vektora, tételenként egy ajánlat. A PTA a vevők értékeléseinek típusától és az egyes tételeknél alkalmazott aukció típusától függ. ${\ displaystyle m}$ ${\ displaystyle n}$

1. eset: szubmoduláris vevők, másodáras aukciók , teljes információk :

Tiszta Nash-egyensúly létezik , optimális szociális jóléttel. Ezért a PoS 1.
Kiszámítható polinom időben egy tiszta Nash-egyensúly a szociális jóléttel, amely legalább az optimális fele. Ezért a "polinomiális időbeli stabilitás" ára legfeljebb 2.
A PoA korlátlan - amint azt a fenti egy tételes példa már bemutatta. Azonban egy erős, semmilyen túllicitálás nélküli feltételezés szerint (bármely vevő bármely csomagra tett ajánlatának összege legfeljebb annak a csomagnak az értéke a vevő számára), a PoA legfeljebb 2. Ez utóbbi eredmény akkor is érvényes, ha a vevők az értékelések töredékesen aladditívek .

2. eset: töredékesen aladditív vevők, 2. áras aukció, hiányos információk . Ha feltételezzük, hogy nincs túlzott túllépés , akkor bármely (vegyes) Bayes-Nash egyensúly elvárások szerint legalább az optimális jólét 1/2-át éri el; ennélfogva a BPoA legfeljebb 2. Ez az eredmény nem függ a szerek közös prioritásától.

3. eset: másodlagos vevők, 2. árverések . Alatt erős-no-overbidding feltételezés:

Teljes információval minden tiszta Nash-egyensúly jóléte legalább az optimális fele, tehát a PoA legfeljebb 2.
Hiányos információk birtokában léteznek olyan Bayes-Nash-egyensúlyi viszonyok, amelyek jóléte kevesebb, mint az optimális 1/2 , tehát a BPoA több mint 2.
A BPoA legfeljebb , hol van az elemek száma. Ez a garancia durva korrelált egyensúlyra is érvényes - és így a vegyes Nash-egyensúly és a korrelált egyensúly speciális eseteire is . ${\ displaystyle 2 \ log {m}}$ ${\ displaystyle m}$
A PoA fenti két felső határa kecsesen romlik, amikor a szubadditivitás és a túlfeltételezés nélküli feltételezések enyhülnek. Pl.: Ha azt feltételezzük, hogy minden játékos legfeljebb valamilyen állandó tényezővel túlzsúfol, akkor a PoA legfeljebb állandó tényezővel növekszik.

4. eset: Általános (monoton) vevők, első árverések , teljes információk :

A játék tiszta Nash-egyensúlyainak halmaza pontosan a piac walrasi egyensúlya (áregyensúly) .
Mivel az ilyen egyensúlyok társadalmilag optimálisak (az első jóléti tétel szerint ), a tiszta Nash-egyensúlyi PoA értéke 1. Sajnos előfordulhat, hogy ilyen egyensúly nem létezik.
A vegyes Nash-egyensúly mindig fennáll (a megfelelő döntetlen szabály kiválasztásakor). Ez azonban nem feltétlenül társadalmilag optimális. A PoA lehet olyan magas, mint a PoS, és akár a PoS is . ${\ displaystyle \ Omega ({\ sqrt {m}})}$ ${\ displaystyle \ Omega ({\ sqrt {m}})}$ ${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$ ${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
- Ez az eredmény a 2. áras aukciókra is kiterjed, még akkor is, ha feltételezzük, hogy túlságosan túllicitálható .
A PoA legfeljebb . ${\ displaystyle O (m)}$
Amikor az összes értékelés aladditív, a PoA legfeljebb . ${\ displaystyle O (\ log {m})}$
Ha az összes értékelés - töredékesen aladditív , akkor a PoA legfeljebb (különösen az XOS vásárlók esetében a PoA legfeljebb 2). ${\ displaystyle \ beta}$ ${\ displaystyle 2 \ beta}$
Ez utóbbi három határ a durva korrelációjú egyensúlyok esetében is érvényes; NEM igénylik a "nincs túlhúzás" feltételezést.

5. eset: Általános vásárlók, 2. árverések, teljes körű információk . Általános értékelésekkel (amelyek esetlegesen kiegészítik egymást) az erős, túlhúzás nélküli feltételezés túl erős, mivel megakadályozza a vevőket abban, hogy magas értéket ajánljanak a kiegészítő tételek kötegére. Például, ha a vevő értékelése 100 dollár egy cipőért, de 1 dollár az egyes cipőkért, akkor az erős-nem túlzott feltételezés megakadályozza, hogy minden egyes cipőre 1-nél többet licitáljon, így kevés esélye van a pár megnyerésére. . Ezért helyébe egy gyenge-nincs-túlfizetési feltételezés lép, ami azt jelenti, hogy a túlhúzás tilalma csak arra a csomagra vonatkozik, amelyet az ügynök végül megnyer (azaz a vevő ajánlatainak összege a kiosztott csomaghoz legfeljebb az ő értéke ennek a konkrét csomagnak). Ebben a gyenge, nem túlzott feltételezésben:

A játék tiszta Nash-egyensúlyainak halmaza pontosan a piac feltételes ár-egyensúlyi viszonyai .
Mivel az ilyen egyensúlyok félig társadalmilag optimálisak (elérik a maximális szociális jólét legalább felét), a tiszta Nash-egyensúlyi PoA legfeljebb 2. Sajnos ilyen egyensúly nem létezhet.

6. eset: Általános vásárlók, első árverések, hiányos információk . Bármely gyakori előzmény esetén:

A BPoA legfeljebb . ${\ displaystyle O (mn)}$
Amikor az összes értékelés -törvény szerint szub-additív, akkor a BPoA legfeljebb (különösen az XOS-vevők esetében a BPoA legfeljebb 2, a szubadditívebb vevők esetében pedig igen ). ${\ displaystyle \ beta}$ ${\ displaystyle 4 \ beta}$ ${\ displaystyle O (\ log m)}$

7. eset: Aladditív vevők, hiányos információk :

Amikor az árukat első árveréseken értékesítik, a BPoA legfeljebb 2 lehet.
Amikor a tételeket eladják másodáras aukciókon, a BPoA legfeljebb 4. Ez mind az erős, nem túlzott feltevés feltételezése esetén igaz (bármely vevő bármely kötegre tett ajánlatának összege legfeljebb az adott csomag értéke a vevő), és a gyenge-nem túlzott feltételezés szerint (bármely vevő nyertes ajánlatának várható összege legfeljebb az adott vevő várható nyertes értéke).

Szekvenciális aukciók

Egy szekvenciális aukció , tételek értékesítik egymás aukciók, egyiket a másik után. A közös egyensúlyi típus a játék alatti tökéletes egyensúly a tiszta stratégiákban (SPEPS). Ha a vevők teljes információval rendelkeznek (azaz előre tudják az aukciók sorrendjét), és minden körben egyetlen tételt értékesítenek, mindig létezik SPEPS. ${\ displaystyle m}$

A SPEPS POA függ az ajánlattevők hasznossági funkcióitól és az egyes tételeknél használt aukció típusától.

Az alábbi első öt eredmény teljes információval rendelkező ügynökökre vonatkozik (minden ügynök ismeri az összes többi ügynök értékelését):

1. eset: azonos tárgyak, két vevő, 2. árverés :

Ha legalább egy vevőnek homorú értékelési funkciója van ( csökkenő hozam ), akkor a PoA legfeljebb . ${\ displaystyle 1 / (1-e) \ kb. 1,58}$
A numerikus eredmények azt mutatják, hogy ha sok olyan ajánlattevő van, akinek homorú értékelési funkciói vannak, akkor a hatékonyságveszteség csökken a felhasználók számának növekedésével.

2. eset: adalékanyag- vásárlók :

Másodlagos árverésekkel a PoA korlátlan - a SPEPS jóléte önkényesen kicsi lehet!

3. eset: egységigényű vásárlók :

Első árveréseknél a PoA legfeljebb 2 - a jólét egy SPEPS-ben mindig a maximum fele (ha vegyes stratégiák megengedettek, a PoA legfeljebb 4).
Második árverésekkel a PoA ismét korlátlan.

Ezek az eredmények meglepőek, és hangsúlyozzák a tervezési döntés fontosságát, miszerint minden fordulóban első áras aukciót (nem pedig második áras aukciót) alkalmaznak.

4. eset: szubmoduláris vásárlók (vegye figyelembe, hogy az additív és az egységigény a szubmoduláris speciális esetei):

Mind az 1., mind a 2. áras aukcióval a PoA korlátlan, még akkor is, ha csak négy ajánlattevő van. Az az intuíció, hogy a nagy értékű ajánlattevő inkább hagyja, hogy egy alacsony értékű ajánlattevő nyerjen annak érdekében, hogy csökkentse a versenyt, amellyel a következő fordulókban szembesülhet.

5. eset: adalék + UD . Tegyük fel, hogy egyes ajánlattevők additív, míg mások egységigény-értékelésekkel rendelkeznek. Az első áras aukciók sorozatában a PoA lehet legalább , ahol m az elemek száma, n pedig az ajánlattevők száma. Ráadásul a nem hatékony egyensúly még a gyengén uralkodó stratégiák iterált megszüntetése alatt is fennáll. Ez lineáris hatékonyságot von maga után számos természetes környezetben, beleértve: ${\ displaystyle \ perc (n, m)}$

bruttó helyettesítő értékelésekkel rendelkező vevők ,
kapacitív értékelések,
költségvetés-additív értékelések,
additív értékelések, szigorú költségvetési korlátozásokkal a kifizetések terén.

6. eset: egységigényű vásárlók, hiányos információk, első árverések : A BPoA legfeljebb 3.

Kapzsi algoritmusokat alkalmazó aukciók

Lát

Általános második árverések

Lát

Kapcsolódó témák

Az aukciók PoA-jával kapcsolatos tanulmányok betekintést nyújtottak más beállításokba, amelyek nem kapcsolódnak aukciókhoz, például a hálózatképző játékokhoz

Összefoglaló táblázat

[A részleges táblázatot - csak párhuzamos aukciókat tartalmaz - ki kell tölteni]

Több aukció	Egyetlen aukció	Információ	Értékelések	Feltételezések	PoA	Pozíció	Hozzászólások
Párhuzamos	2. ár	teljes	szubmoduláris	erős-nem túlhúzás	2	tiszta: 1 [mindig létezik]
Párhuzamos	2. ár	Bayesian	XOS	erős-nem túlhúzás	2
Párhuzamos	2. ár	teljes	aladditív	erős-nem túlhúzás	2
Párhuzamos	2. ár	Bayesian	aladditív	erős-nem túlhúzás	> 2, <2 log (m)
Párhuzamos	1. ár	teljes	monoton	Egyik sem	tiszta: 1 [ha létezik]		Tiszta NE = MI.
Párhuzamos	1. ár	teljes	monoton	Egyik sem	vegyes: ${\ displaystyle \ Omega ({\ sqrt {m}})}$	${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
Párhuzamos	1. ár	Bayesian	monoton	Egyik sem	${\ displaystyle O (mn)}$	${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
Párhuzamos	2. ár	teljes	monoton	gyenge-nem túlzott	tiszta: 2 [ha létezik]		Tiszta NE = Feltételes MI
Párhuzamos	1. ár	Bayesian	aladditív	Egyik sem	2	${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
Párhuzamos	2. ár	Bayesian	aladditív	gyenge / erős-nem túlzott	4

Languages

In other projects