Algoritmická teorie her - Algorithmic game theory

Algoritmická teorie her je oblast na křižovatce herní teorie a počítačová věda s cílem porozumět a navrhnout algoritmy ve Windows strategický prostředí.

V problémech s algoritmickou herní teorií je vstup do daného algoritmu obvykle distribuován mezi mnoho hráčů, kteří mají na výstupu osobní zájem. V těchto situacích agenti nemusí pravdivě nahlásit vstup kvůli svým osobním zájmům. Teorii algoritmické hry můžeme vidět ze dvou pohledů:

  • Analýza: podívat se na současné implementované algoritmy a analyzovat je pomocí nástrojů Teorie her: vypočítat a dokázat jejich vlastnosti Nashovy rovnováhy, cena anarchie, dynamika nejlepší odezvy ...
  • Design: designové hry, které mají dobré herně teoretické i algoritmické vlastnosti. Tato oblast se nazývá návrh algoritmického mechanismu.

Kromě obvyklých požadavků v klasickém návrhu algoritmu, řekněme doba běhu polynomu, dobrý aproximační poměr, ... designérovi musí záležet také na motivačních omezeních.

Dějiny

Nisan-Ronen: nový rámec pro studium algoritmů

V roce 1999 byla zveřejněna klíčová práce z Nisan a Ronen [1] upozornil komunitu Theoretical Computer Science na navrhování algoritmů pro sobecké (strategické) uživatele. Jak tvrdí abstraktně:

Uvažujeme o algoritmických problémech v distribuovaném prostředí, kde nelze předpokládat, že se účastníci řídí algoritmem, ale spíše vlastním zájmem. Protože tito účastníci, nazývaní agenti, jsou schopni manipulovat s algoritmem, měl by návrhář algoritmů předem zajistit, aby zájmy agentů byly nejlépe uspokojeny správným chováním. V návaznosti na pojmy z oblasti návrhu mechanismu navrhujeme rámec pro studium těchto algoritmů. . V tomto modelu je algoritmické řešení zdobeno platbami účastníkům a je označováno jako mechanismus. Platby by měly být pečlivě vybírány tak, aby motivovaly všechny účastníky, aby jednali podle přání návrháře algoritmů. Aplikujeme standardní nástroje návrhu mechanismu na algoritmické problémy a zejména na problém s nejkratší cestou.

Tento příspěvek vytvořil tento termín návrh algoritmického mechanismu a byl uznán v roce 2012 Gödelova cena výbor jako jeden ze „tří příspěvků položil základy růstu v Algorithmic Game Theory“.[2]

Cena anarchie

Hlavní článek: Cena anarchie

Další dva články citované v Gödelově ceně za rok 2012 za základní příspěvky k teorii algoritmické hry představily a vyvinuly koncept „ceny anarchie“. Ve svém příspěvku z roku 1999 „Nejhorší rovnováha“[3] Koutsoupias a Papadimitriou navrhl nové opatření ke snížení účinnosti systému v důsledku sobeckého chování jeho agentů: poměr mezi účinností systému v optimální konfiguraci a jeho účinností v nejhorší Nashově rovnováze. (Termín „Cena anarchie“ se objevil až o několik let později.[4])

Internet jako katalyzátor

Internet vytvořil novou ekonomiku - jak jako základ pro výměnu a obchod, tak samostatně. Výpočtová povaha internetu umožňovala použití výpočetních nástrojů v této nově se rozvíjející ekonomice. Na druhé straně je samotný internet výsledkem jednání mnoha lidí. To byl nový způsob klasického přístupu „shora dolů“ k výpočtu, který platil do té doby. Teorie her je tedy přirozeným způsobem pohledu na internet a interakce v něm, lidské i mechanické.

Teorie her studuje rovnováhy (např Nashova rovnováha ). Rovnováha je obecně definována jako stav, kdy žádný hráč nemá motiv ke změně své strategie. Rovnováhy se vyskytují v několika oblastech souvisejících s internetem, například finanční interakce a vyrovnávání komunikační zátěže[Citace je zapotřebí ]. Teorie her poskytuje nástroje pro analýzu rovnováh a běžným přístupem je pak „najít hru“ - to znamená formalizovat konkrétní internetové interakce jako hru a odvodit související rovnováhy.

Přeformulování problémů, pokud jde o hry, umožňuje analýzu internetových interakcí a konstrukci mechanismů, které splňují stanovené požadavky. Pokud lze prokázat rovnováhu, je třeba odpovědět na další otázku: lze najít rovnováhu a v rozumném čase? To vede k analýza algoritmů pro nalezení rovnováhy. Zvláštní význam má třída složitosti PPAD, který zahrnuje mnoho problémů v teorii algoritmických her.

Oblasti výzkumu

Návrh algoritmického mechanismu

Hlavní článek: Návrh algoritmického mechanismu

Návrh mechanismu je podoblast ekonomiky, která se zabývá optimalizací za motivačních omezení. Návrh algoritmického mechanismu uvažuje o optimalizaci ekonomických systémů podle požadavků na výpočetní účinnost. Typické studované cíle zahrnují maximalizaci výnosů a maximalizaci sociálního zabezpečení.

Neúčinnost rovnováhy

Koncepty cena anarchie a cena stability byly zavedeny, aby zachytily ztrátu výkonu systému v důsledku sobeckého chování jeho účastníků. The cena anarchie zachycuje nejhorší výkon systému v rovnováze s optimálním možným výkonem.[5] The cena stability, na druhé straně, zachycuje relativní výkon nejlepší rovnováhy systému.[6] Tyto pojmy jsou protějšky pojmu přibližný poměr v designu algoritmu.

Složitost hledání rovnováhy

Existence rovnováhy ve hře je obvykle stanovena pomocí nekonstruktivní věty o pevném bodě. Pro výpočet nejsou známy žádné efektivní algoritmy Nashovy rovnováhy. Problém je pro třída složitosti PPAD dokonce i ve hrách pro dva hráče.[7] V porovnání, korelované rovnováhy lze efektivně vypočítat pomocí lineárního programování,[8] stejně jako naučené prostřednictvím strategií bez lítosti.[9]

Výpočetní sociální volba

Hlavní článek: Výpočetní sociální volba

Výpočetní sociální volba studuje výpočetní aspekty sociální volba, agregace preferencí jednotlivých agentů. Mezi příklady patří algoritmy a výpočetní složitost volebních pravidel a formování koalice.[10]

Mezi další témata patří:

A oblast se počítá s různými praktickými aplikacemi:[11][12]

Časopisy a zpravodaje

  • ACM Transakce o ekonomice a výpočtu (TEAC) [13]
  • Výměny SIGEcom [14]

Algoritmické teorie her jsou často publikovány také v časopisech Teorie her, jako např GEB,[15] Ekonomické časopisy jako Econometrica a časopisy o informatice, jako je SICOMP.[16]

Viz také

Reference

  1. ^ Nisan, Noame; Ronen, Amir (1999), „Algorithmic mechanism design“, Proceedings of the 31. ACM Symposium on Theory of Computing (STOC '99), str. 129–140, doi:10.1145/301250.301287, ISBN  978-1581130676, S2CID  8316937
  2. ^ „ACM SIGACT představuje Gödelovu cenu za výzkum, který osvětlil účinky sobeckého používání internetu“ (Tisková zpráva). New York. Sdružení pro výpočetní techniku. 16. 05. 2012. Archivovány od originál dne 18. 7. 2013. Citováno 2018-01-08.
  3. ^ Koutsoupias, Elias; Papadimitriou, Christos (květen 2009). „Nejhorší případ rovnováhy“. Recenze informatiky. 3 (2): 65–69. doi:10.1016 / j.cosrev.2009.04.003. Archivovány od originál dne 13. 3. 2016. Citováno 2018-01-08.
  4. ^ Papadimitriou, Christos (2001), „Algorithms, games, and the Internet“, Proceedings of the 33. ACM Symposium on Theory of Computing (STOC '01), str. 749–753, CiteSeerX  10.1.1.70.8836, doi:10.1145/380752.380883, ISBN  978-1581133493, S2CID  207594967
  5. ^ Tim Roughgarden (2005). Sobecké směrování a cena anarchie. MIT Stiskněte. ISBN  0-262-18243-2.
  6. ^ *Anshelevich, Elliot; Dasgupta, Anirban; Kleinberg, Jon; Tardos, Éva; Wexler, Tom; Roughgarden, Tim (2008). "Cena stability za návrh sítě se spravedlivým rozdělením nákladů". SIAM J. Comput. 38 (4): 1602–1623. doi:10.1137/070680096. S2CID  2839399.
  7. ^ *Chen, Xi; Deng, Xiaotie (2006). Vyřešení složitosti Nashovy rovnováhy pro dva hráče. Proc. 47. Symp. Základy informatiky. 261–271. doi:10.1109 / FOCS.2006.69. ECCC  TR05-140..
  8. ^ Papadimitriou, Christos H .; Roughgarden, Tim (2008). "Výpočet korelovaných rovnováh ve hrách pro více hráčů". J. ACM. 55 (3): 14:1–14:29. CiteSeerX  10.1.1.335.2634. doi:10.1145/1379759.1379762. S2CID  53224027.
  9. ^ Foster, Dean P .; Vohra, Rakesh V. (1996). „Kalibrované učení a korelovaná rovnováha“. Hry a ekonomické chování.
  10. ^ Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia, eds. (2016), Příručka výpočetní sociální volby (PDF)
  11. ^ Tim Roughgarden (2016). Dvacet přednášek o algoritmické teorii her. Cambridge University Press. ISBN  9781316624791.
  12. ^ „EC'19 || 20. konference ACM o ekonomii a výpočtu“.
  13. ^ TEAC
  14. ^ Výměny SIGEcom
  15. ^ Chawla, Shuchi; Fleischer, Lisa; Hartline, Jason; Tim Roughgarden (2015), „Úvod do speciálního vydání - Algoritmická teorie her - STOC / FOCS / SODA 2011“, Hry a ekonomické chování, 92: 228–231, doi:10.1016 / j.geb.2015.02.011
  16. ^ SICOMP

externí odkazy

  • gambit.sourceforge.net - knihovna softwaru a nástrojů pro teorii her pro konstrukci a analýzu konečných rozsáhlých a strategických her.
  • gamut.stanford.edu - sada generátorů her určených k testování herně-teoretických algoritmů.