Cena anarchie v aukcích - Price of anarchy in auctions

The Cena anarchie (PoA) je koncept v herní teorie a konstrukce mechanismu to měří, jak sociální péče systému se zhoršuje kvůli sobeckému chování jeho agentů. To bylo studováno značně v různých kontextech, zejména v aukce.

V aukci existuje jedna nebo více položek a jeden nebo více agentů s různým oceněním položek. Položky je třeba rozdělit mezi agenty. Je žádoucí, aby sociální péče - součet hodnot všech agentů - být co nejvyšší.

Jedním z přístupů k maximalizaci sociálního blahobytu je navrhování a pravdivý mechanismus. V takovém mechanismu je každý agent motivován hlásit své skutečné ocenění k položkám. Poté může dražebník vypočítat a implementovat alokaci, která maximalizuje součet hodnot. Příkladem takového mechanismu je Aukce VCG.

V praxi však není vždy možné použít pravdivé mechanismy. Například mechanismus VCG může být pro účastníky příliš složitý na to, aby jej pochopili, může trvat příliš dlouho, než to dražebník spočítá, a může mít další nevýhody.^[1] V praxi se často používají nepravdivé mechanismy a je zajímavé spočítat, o kolik se sociální nepravda touto nepravdivostí ztrácí.

Často se předpokládá, že v nepravdivé aukci účastníci hrají rovnovážnou strategii, například a Nashova rovnováha. The cena anarchie aukce je definován jako poměr mezi optimální sociální péčí a sociální péčí v EU nejhorší rovnováha:

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

Příbuzný pojem je Cena stability (PoS), který měří poměr mezi optimální sociální péčí a sociální péčí v EU nejlepší rovnováha:

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

Očividně ${ displaystyle 1 leq PoS leq PoA leq infty}$.

Když tam je úplné informace (každý agent zná ocenění všech ostatních agentů), běžným typem rovnováhy je Nashova rovnováha - čistá nebo smíšená. Když tam je neúplné informace, je běžný rovnovážný typ Bayes-Nashova rovnováha. V druhém případě je běžné hovořit o Bayesiánská cena anarchienebo BPoA.

Aukce s jedním předmětem

V aukce první ceny jedné položky je Nashova rovnováha vždy efektivní, takže PoA a PoS jsou 1.

V dražba druhé ceny, existuje Nashova rovnováha, ve které agenti hlásí pravdivě; je efektivní, takže PoS je 1. PoA je však neomezený! Například,^[2]Předpokládejme, že existují dva hráči: Alice si váží položky jako A a Bob jako b, s A>b.

Existuje „dobrá“ Nashova rovnováha, ve které Alice draží A a Bob nabídky b; Alice obdrží předmět a zaplatí b. Sociální péče je A, což je optimální.

Existuje však také „špatná“ Nashova rovnováha, ve které Alice draží 0 a Bob např. A+1; Bob obdrží předmět a nic neplatí. Jedná se o rovnováhu, protože Alice nechce Bobovi nadhodit. Sociální péče je b. Proto je PoA A/b, který je neomezený.

Tento výsledek se zdá být příliš pesimistický:

• Zaprvé, v aukci druhé ceny je to slabědominantní strategie aby každý agent nahlásil své skutečné ocenění. Pokud předpokládáme, že agenti sledují své dominantní strategie, pak je PoA 1.
• Navíc je to dominovala strategie aby každý agent nahlásil jakoukoli hodnotu vyšší než jeho skutečné ocenění.

Proto je běžné analyzovat PoA pod a žádné nabízení cen předpoklad - žádný agent draží nad jeho skutečné ocenění. Za tohoto předpokladu je PoA aukce s jedním předmětem 1.

Souběžné aukce

V paralelní (simultánní) aukci ${ displaystyle m}$ položky se prodávají současně stejné skupině ${ displaystyle n}$ účastníků. Na rozdíl od a kombinatorická aukce - ve kterém mohou agenti dražit na svazky položek, zde mohou agenti dražit pouze na jednotlivé položky nezávisle na ostatních. Strategie agenta je vektor nabídek, jedna nabídka na položku. PoA závisí na typu ocenění kupujících a na typu aukce použité pro každou jednotlivou položku.

Případ 1: submodulární kupující, aukce druhé ceny, úplné informace:^[2]

• Existuje čistá Nashova rovnováha s optimálním sociálním blahobytem. Proto je PoS 1.
• Je možné vypočítat v polynomiálním čase čistou Nashovu rovnováhu se sociální péčí nejméně o polovinu optimální. Cena „stability v polynomiálním čase“ je tedy maximálně 2.
• PoA je neomezený - jak již ukazuje příklad jedné položky výše. Nicméně pod a silný-žádný-overbidding předpoklad (součet nabídek kteréhokoli kupujícího na jakýkoli balíček je nanejvýš hodnotou tohoto balíčku pro kupujícího), PoA je nanejvýš 2. Tento druhý výsledek platí, i když jsou hodnocení kupujících zlomkově subaditivní.

Případ 2: zlomkově subaditivní kupující, aukce za 2. cenu, neúplné informace.^[2] Za předpokladu silný-žádný-overbidding, jakákoli (smíšená) Bayes-Nashova rovnováha dosahuje v očekávání alespoň 1/2 optimálního blahobytu; proto je BPoA nanejvýš 2. Tento výsledek nezávisí na společném priorovi agentů.

Případ 3: podaditivum kupující, aukce za 2. cenu. ^[3] Pod silný-žádný-overbidding předpoklad:

• S úplnými informacemi je blahobyt každé čisté Nashovy rovnováhy minimálně 1/2 optimální, takže PoA je maximálně 2.
• S neúplnými informacemi existují Bayes-Nashovy rovnováhy s blahobytem méně než 1/2 optimální, takže BPoA je více než 2.
• BPoA je maximálně ${ displaystyle 2 log {m}}$, kde ${ displaystyle m}$ je počet položek. Tato záruka platí také pro hrubá korelovaná rovnováha - a tedy ke zvláštním případům smíšené Nashovy rovnováhy a korelovaná rovnováha.
• Obě výše uvedené horní hranice PoA se ladně degradují, když se uvolní předpoklady subadditivity a nepřekročení. Např. Pokud předpokládáme, že každý hráč předražuje nanejvýš o nějaký konstantní faktor, pak PoA roste maximálně o konstantní faktor.

Případ 4: Obecní (monotónní) kupující, aukce první ceny, úplné informace:^[4]

• Sada čistých Nashových rovnováh ve hře je přesně ta Walrasian equilibria (cenová rovnováha) trhu.^[5]
• Protože tyto rovnováhy jsou sociálně optimální (podle první věta o blahobytu ), PoA čistých Nashových rovnováh je 1. Bohužel, takové rovnováhy nemusí existovat.
• Smíšená Nashova rovnováha vždy existuje (při výběru správného pravidla pro rozřazení). Není to však nutně společensky optimální. PoA může být stejně vysoký jako ${ displaystyle Omega ({ sqrt {m}})}$, a dokonce i PoS může být stejně vysoký jako ${ displaystyle Omega ({ sqrt {m}} / log {m})}$.
  • Tento výsledek se vztahuje i na aukce druhé ceny, a to i při a slabé - žádné překonání nabídek předpoklad.^[6]
• PoA je nanejvýš ${ displaystyle O (m)}$.
• Pokud jsou všechna ocenění subaditivní, je maximální hodnota PoA ${ displaystyle O ( log {m})}$.
• Když jsou všechna ocenění ${ displaystyle beta}$-zlomkově subaditivní „PoA je nanejvýš ${ displaystyle 2 beta}$ (zejména pro kupující XOS je PoA nejvýše 2).
• Poslední tři hranice platí také pro hrubě korelované rovnováhy; nevyžadují předpoklad „bez překročení nabídek“.

Případ 5: Obecní kupující, aukce za 2. cenu, úplné informace.^[7] U obecných ocenění (které mohou mít komplementaritu) je předpoklad silného nepřekonání nabídky příliš silný, protože brání kupujícím v nabízení vysokých hodnot u balíků doplňkových položek. Pokud je například ocenění kupujícího 100 $ za pár bot, ale 1 $ za každou jednotlivou botu, pak mu předpoklad silného nepřekládání nabídek brání v nabízení více než 1 $ za každou botu, takže má malou šanci vyhrát pár . Proto je nahrazen a slabé - žádné překonání nabídek předpoklad, což znamená, že podmínka nepřevyšování nabídek platí pouze pro balíček, který agent nakonec vyhraje (tj. součet nabídek kupujícího na jeho přidělený balíček je nanejvýš jeho hodnotou pro tento konkrétní balíček). Za tohoto předpokladu slabého a žádného překročení nabídek:

• Sada čistých Nashových rovnováh ve hře je přesně ta podmíněná cenová rovnováha trhu.^[8]
• Jelikož jsou takové rovnováhy napůl sociálně optimální (dosahují alespoň poloviny maximálního sociálního blahobytu), je PoA čisté Nashovy rovnováhy maximálně 2. Bohužel takové rovnováhy nemusí existovat.

Případ 6: Obecní kupující, aukce za 1. cenu, neúplné informace. ^[4] Pro všechny běžné předchozí:

• BPoA je maximálně ${ displaystyle O (mn)}$.
• Když jsou všechna ocenění ${ displaystyle beta}$-frakčně subaditivní, BPoA je nanejvýš ${ displaystyle 4 beta}$ (zejména pro kupující XOS je BPoA maximálně 2 a pro subadditivní kupující je ${ displaystyle O ( log m)}$).

Případ 7: Subadditivní kupující, neúplné informace: ^[6]

• Pokud se položky prodávají v aukcích první ceny, je BPoA maximálně 2.
• Pokud jsou položky prodávány v aukcích druhé ceny, BPoA je maximálně 4. To platí jak za předpokladu silného, ​​tak nepřekonání nabídky (součet nabídek kteréhokoli kupujícího na libovolný balíček je maximálně hodnotou daného balíčku kupující) a pod slabé - žádné překonání nabídek předpoklad (očekávaný součet výherních nabídek kteréhokoli kupujícího je maximálně očekávanou výherní hodnotou kupujícího).

Postupné aukce

V sekvenční aukce, ${ displaystyle m}$ položky se prodávají v po sobě jdoucích aukcích, jedna po druhé. Běžný typ rovnováhy je subgame dokonalá rovnováha v čistých strategiích (SPEPS). Pokud mají kupující úplné informace (tj. Předem znají posloupnost aukcí) a v každém kole se prodá jedna položka, vždy existuje SPEPS.^{[9]:872–874}

PoA tohoto SPEPS závisí na užitných funkcích dražitelů a na typu aukce použité pro každou jednotlivou položku.

Prvních pět výsledků níže platí pro agenty s úplné informace (všichni agenti znají ocenění všech ostatních agentů):

Případ 1: Totožné položky, dva kupující, aukce za 2. cenu:^[10][11]

• Pokud má alespoň jeden kupující konkávní funkci ocenění (klesající výnosy ), PoA je nanejvýš ${ Displaystyle 1 / (1-e) přibližně 1,58}$.
• Numerické výsledky ukazují, že když existuje mnoho uchazečů s konkávními hodnotícími funkcemi, ztráta účinnosti klesá s rostoucím počtem uživatelů.

Případ 2: přísada kupující:^{[9] :885}

• S aukcemi druhé ceny je PoA neomezený - blahobyt v SPEPS může být libovolně malý!

Případ 3: jednotková poptávka kupující:^[9]

• U aukcí první ceny je PoA maximálně 2 - blahobyt v SPEPS je vždy alespoň polovina maxima (pokud jsou povoleny smíšené strategie, PoA je maximálně 4).
• S aukcemi druhé ceny je PoA opět neomezený.

Tyto výsledky jsou překvapivé a zdůrazňují důležitost rozhodnutí o návrhu použití aukce první ceny (spíše než aukce druhé ceny) v každém kole.

Případ 4: submodulární kupující^[9] (všimněte si, že aditivum a poptávka po jednotce jsou speciální případy submodulárních):

• U aukcí 1. ceny i 2. ceny je PoA neomezená, i když existují pouze čtyři uchazeči. Intuice spočívá v tom, že uchazeč s vysokou hodnotou může upřednostnit, aby nechal zvítězit uchazeče s nízkou hodnotou, aby se snížila konkurence, které by mohl v budoucích kolech čelit.

Případ 5: aditivum + UD.^[12] Předpokládejme, že někteří uchazeči mají aditivní ocenění, zatímco jiní mají ocenění podle jednotkové poptávky. V posloupnosti aukcí 1. ceny může být PoA minimálně ${ displaystyle min (n, m)}$, kde m je počet položek a n je počet uchazečů. Neefektivní rovnováhy navíc přetrvávají i při opakované eliminaci slabě ovládaných strategií. To znamená lineární neúčinnost pro mnoho přirozených nastavení, včetně:

• kupující s hrubá náhradní ocenění,
• kapacitní ocenění,
• ocenění aditivní k rozpočtu,
• aditivní ocenění s těžkými rozpočtovými omezeními na platby.

Případ 6: kupující s jednotkovou poptávkou, neúplné informace, aukce za 1. cenu:^[13] BPoA je maximálně 3.

Aukce využívající chamtivé algoritmy

Vidět ^[14]

Zobecněné aukce druhé ceny

Vidět ^[15][16][17]

související témata

Studie týkající se PoA v aukcích poskytly informace o dalších nastaveních, která s aukcemi nesouvisí, například hry pro vytváření sítí ^[18]

Souhrnná tabulka

[Částečná tabulka - obsahuje pouze paralelní aukce - měla by být vyplněna]

Multi-aukce	Jednotná aukce	Informace	Ocenění	Předpoklady	PoA	Poz	Komentáře
Paralelní	2. cena	kompletní	submodulární	silný-žádný-overbidding	2	čistý: 1 [vždy existuje]	[2]
Paralelní	2. cena	Bayesian	XOS	silný-žádný-overbidding	2		[2]
Paralelní	2. cena	kompletní	podaditivum	silný-žádný-overbidding	2		[3]
Paralelní	2. cena	Bayesian	podaditivum	silný-žádný-overbidding	> 2, <2 log (m)		[3]
Paralelní	1. cena	kompletní	monotónní	Žádný	čistý: 1 [pokud existuje]		Čistý NE = WE. [4]
Paralelní	1. cena	kompletní	monotónní	Žádný	smíšený: ${ displaystyle Omega ({ sqrt {m}})}$	${ displaystyle Omega ({ sqrt {m}} / log {m})}$	[4]
Paralelní	1. cena	Bayesian	monotónní	Žádný	${ displaystyle O (mn)}$	${ displaystyle Omega ({ sqrt {m}} / log {m})}$	[4]
Paralelní	2. cena	kompletní	monotónní	slabé - žádné překonání nabídek	čistý: 2 [pokud existuje]		Čistý NE = Podmíněné WE[7]
Paralelní	1. cena	Bayesian	podaditivum	Žádný	2	${ displaystyle Omega ({ sqrt {m}} / log {m})}$	[6]
Paralelní	2. cena	Bayesian	podaditivum	slabé / silné - nepřekračování nabídek	4		[6]

Reference