čtvrtek 31. března 2011

Racionalita a vězňovo dilema


Vězňovo dilema je asi nejznámějším myšleným experimentem, na kterém se ilustrují základní principy teorie her. V dilematu vystupují dva komplicové podezřelí z několika trestných činů, řekněme krádeže a vraždy. Státní zástupce každému z nich učiní následující nabídku:

Státní zástupce: Máme dost důkazů k tomu, abychom vám oběma prokázali krádež. Za to dostanete dva roky na tvrdo. Policie chce vykázat i vraždu jako objasněnou, k jejímu prokázání ale potřebujeme vaše doznání nebo aspoň svědectví. Nepočítáme, že by se kterýkoli z vás přiznal, protože za vraždu hrozí trest smrti. Zůstává zde ovšem možnost svědčit proti svému kumpánovi a celou vinu hodit na něho.
Vězeň: A proč bych to dělal?
SZ: Nu, takové svědectví je považováno za závažnou polehčující okolnost. Když budete svědčit, místo dvou let za krádež vyváznete s podmínkou. Navíc uvažte, že zde existuje riziko, že váš komplic se pokusí hodit vinu na vás, a nemusím snad zdůrazňovat, že i jemu vylíčíme jeho situaci tak důkladně, jak ji teď vysvětluji vám. Pokud se rozhodne vás zradit, byl byste odsouzen k smrti. Jestliže ale budete i vy svědčit proti němu, soud to znovu vezme v potaz jako polehčující okolnost, a dostanete oba patnáct let. Nic moc, ale lepší než provaz.
V: Když se rozhodnu proti němu svědčit, rozzuří ho to a rozhodne se v odvetě svědčit proti mně...
SZ: Nedostane šanci. Vy i váš kumpán máte možnost sepsat svědectví předem. O tom, zda ten druhý ho zradil, se každý z vás dozví až u soudu, kde ale na případnou změnu svědectví bude pozdě — soud ji bude vnímat jako pomstu z afektu a nebude jí věřit. Se soudcem jsme tak dohodnutí a hrajeme férově.

Zbývá ještě doplnit pár idealizačních předpokladů, jako že žádnému z vězňů ani za mák nesejde na osudu toho druhého a že státní zástupce je naprosto důvěryhodný a říká pravdu, a nakonec otázku: je z hlediska vězně racionální zradit?



X nesvědčí X svědčí
Y nesvědčí X: 2 roky
Y: 2 roky
X: podmínka
Y: smrt
Y svědčí X: smrt
Y: podmínka
X: 15 let
Y: 15 let


Z tabulky je názorně vidět, že nezávisle na tom, jak se rozhodne jeho kumpán, pro každého z vězňů je lepší svědčit. Když ho jeho komplic práskne, zachrání mu to život, a pokud komplic bude držet jazyk za zuby, ušetří to prvnímu vězni dva roky žaláře. Přitom není v silách ani jednoho z vězňů ovlivnit rozhodnutí toho druhého. V terminologii teorie her je svědčit dominující strategie, zatímco nesvědčit je strategie dominovaná. Je přijímaným postulátem, že při rozhodnutí mezi takovými strategiemi je vždy racionální dát přednost strategii dominující před tou dominovanou. V teorii her vzdělaný vězeň se tudíž rozhodne svého komplice prásknout.

Zajímavá vlastnost vězňova dilematu je ta, že pokud se oba vězni rozhodnou „iracionálně“ pro mlčení, dopadnou výrazně lépe, než jejich „racionální“ kolegové. V našem případě půjdou ti „iracionální“ domů o třináct let dříve. To ukazuje, že na herněteoretické racionalitě může být něco shnilého.

Název „vězňovo dilema“ není vázán na vězení a soudy, nýbrž se používá pro označení všech situací (tedy vlastně her, když už užívám příslušnou terminologii), kdy dva soupeři volí mezi „spoluprací“ a „zradou“, přičemž by raději zradili, ať už protivník zradí nebo spolupracuje, ale oba zároveň preferují oboustrannou spolupráci před oboustrannou zradou. Uvažujme třeba situaci, kdy se X a Y domluví, že v domluvený den společně postaví plot mezi svými chatami. X může uvažovat takto: „Y přijede na chatu vlakem v deset, jak jsme domluvení, a čeká, že přijedu autobusem v půl jedenácté a pak začneme stavět. Když ale řeknu, že jsem si cestou na autobus vyvrknul kotník, Y plot postaví sám, protože vlak zpět mu jede až ve sedm večer a na chatě v tuhle dobu stejně není nic jiného na práci (a Y se nerad nudí). Já tak získám k plotu i volný den navíc.“ Y může uvažovat podobně, a získáme tak tabulku typu vězňova dilematu:



X přijede X simuluje
Y přijede X: plot
Y: plot
X: plot + volný den
Y: plot + práce navíc
Y simuluje X: plot+práce navíc
Y: plot+volný den
X: volný den
Y: volný den


Reálná vězňova dilemata jsou komplikována tím, že většina lidí má silnou morální averzi ke zradě [*] a není tak snadné dostat se do situace, kdy oba hráči skutečně preferují výsledky úspěšně provedené zrady před její alternativou. Simulovat v předchozí tabulce může způsobit výčitky svědomí, a ty mohou být tak nepříjemné, že X i Y můžou preferovat oboustrannou spolupráci před možností, že všechnu práci udělá ten druhý. Zrada navíc vede ke ztrátě reputace, a ta se může v důsledku pěkně prodražit. Nechme ale tyto komplikace stranou a omezme se na zjednodušený případ, kdy toto nenastává. Je tehdy zrada optimální strategie?

Intuice nemá až tak velký problém toto přijmout pro izolované vězňovo dilema, tedy pokud se jedná o jediné rozhodnutí, které se nebude opakovat. Jinak se ale díváme na opakované vězňovo dilema, ve kterém dva hráči vstupují do téže interakce mnohokrát po sobě, a mohou tak reagovat na chování soupeře. Když jeden z hráčů zradí, druhý může na oplátku zradit v následujícím kole. Občas se jako racionální v takových případech doporučuje strategie „oko za oko“: když v předchozím případě soupeř spolupracoval, odměň ho spoluprací; když zradil, potrestej ho zradou. Od racionálních hráčů by člověk očekával, že budou schopni předvídat. Sousedé, kteří se dvacetkrát za sebou domluví na tom, že společně postaví plot, a pokaždé si pak místo stavby oba „vymknou kotník“ nejen že nebudou mít plot, ale budou vypadat jako naprostí idioti.

To všechno zní sice dobře, dokonce spravedlivě, ale bohužel to nesouhlasí se závěrem teorie her: Jediná racionální strategie je vždy zrada! A logika teorie her je neúprosná. Je přeci jasné, že N, tj. počet opakování vězňova dilematu, bude „pouze“ konečný — nikdo nežije věčně. Před posledním opakováním tak budou hráči před sebou mít izolované dilema. Soupeř nebude mít šanci pomstít zradu, tudíž je jedině racionální sledovat dominující strategii a zradit. Oba hráči, jsou-li racionální dle definice užívané v teorii her, zradí. Jestliže hráči o sobě navzájem vědí, že jsou tímto způsobem racionální, vědí od samého začátku, jak N-tá hra dopadne, a v předposlední hře se tak nemusejí starat o možnost, že by se jim soupeř v poslední hře pomstil; ten zradí tak jako tak. Tudíž i v N - 1. oba „racionálně“ zradí, a není těžké to vědět již před N - 2. hrou... A tak dále, přesně ve stylu uvažování diskutovaném minule v paradoxu nečekaného věšení [1].

Zatímco tak většina lidí v opakovaném vězňově dilematu spolupracuje, herní teoretici se točí v bludném kruhu zrady, majíce svůj postup podepřený neprůstřelným argumentem.

Mám s takto pojatou racionalitou problém. Jestliže skupina A v určité hře volí strategii tak, že vykazuje systematicky horší výsledky než skupina B, a jestliže všichni členové skupiny A vědí, proč tomu tak je, a jsou schopni tyto výsledky předvídat, pak těžko tvrdit, že chyba je na straně skupiny B, a stejně tak se mi příčí tvrdit, že jednání členů skupiny A je racionální.

Nemíním tento článek jako frontální útok na teorii her. Ve většině situací je výběr dominantní strategie skutečně to nejlepší, co lze učinit. Stejně tak teorie her nabízí standardní řešení pro situace typu vězňova dilematu: vytvořit dodatečnou motivaci pro spolupráci a naopak dohodnout trest pro zrádce. Ve většině reálných situací je to optimální řešení, a lidé tak reálně postupují. Na druhou stranu, toto řešení znamená změnu pravidel hry, a nejenže tak z čistě teoretického pohledu představuje úhýbání před námitkou, ale ani není vždy proveditelné.

Mám za to, že v ideálním vězňově dilematu (ať už opakovaném nebo ne), za předpokladu, že není možné měnit „pravidla“, a za předpokladu společné znalosti (viz pozn.[1]) o racionalitě obou soupeřů, je racionálním rozhodnutím spolupráce.


Poznámky:
1. Úvaha vyžaduje tzv. společnou znalost o racionalitě obou hráčů. Tj. X ví, že Y je racionální; Y ví, že X ví, že Y je racionální; X ví, že Y ví, že X ví, že Y je racionální; atd. Podobně s prohozením X a Y.

16 komentářů:

  1. Měl bych k vašemu článku několik poznámek:

    1) Zpětnou indukci můžete použít jen pokud víte, kdy hra končí. Pokud tomu tak není (např. protože nevíte kdy umřete), může mít vězňovo dilema dle standartní teorie her mnoho rovnováh, včetně těch kdy hráči kooperují.

    2) V neopakovaném vězňově dilematu je zrada racionální. Když tvrdíte opak, pak tiše předpokládáte, že existuje mechanismus, který potrestá zrádce. Ten ale v neopakované hře chybí. V opakovné hře s neznámým koncem je tímto mechanismem odepření spolupráce v dalším kole.

    3) Společně sdílená racionalita na tomto závěru nic nemění. Naopak, tento předpoklad vás nutí "vyškrtat" všechny dominované strategie.

    Moc pěkný blog.

    OdpovědětSmazat
  2. Souhlasím s předchozím komentářem. Ještě bych ale doplnil, že existují entity, jejichž "smrt" není tak jistá jako smrt lidí. Těmito entitami jsou firmy, státy atd.

    OdpovědětSmazat
  3. Nepředpokládám mechanismus, který potrestá zrádce. Předpokládám pouze, že 1) racionální strategie v tomto případě je ryzí, nikoli smíšená, 2) racionalita strategii determinuje jednoznačně, a tudíž všichni racionální agenti hrají stejně, a 3) racionální strategie je taková z množiny strategií vyhovujících předchozím podmínkám, která vede k nejvyššímu zisku. Z toho plyne, že spolupráce je racionální. (Jinak řečeno, preferuji v tomto případě evidenční teorii rozhodování před kauzální.)

    Námitka, že je nutno vědět, kdy hra končí, je samozřejmě platná.

    OdpovědětSmazat
  4. Problém vidím v předpokladu 2). Co vás vede k tomu, že se omezíte pouze na symetrické situace? Racionalita, tak jak je standartně v teorii her chápána, nic takového nepředpokládá. Společně sdílená racionalita říká, že 1) hráči hrají své nejlepší odpovědi vzhledem k očekáváním, která mají ohledně akcí ostatních 2) tato očekávání musí být v souladu s tím, že ostaní také hrají své nejlepší odpovědi na svá očekávání a tato očekávání musí být v souladu ... Nikde se neříká, že všichni racionální hráči musí dělat to samé.

    Jinými slovy, proč si myslíte, že přesvědčení: "Když já nezradím, tak druhý taky nezradí" je racionální?

    A ještě malí poznámka. Teorie her sice někdy omezuje řešení symetrických her na tzv. symetrické rovnováhy, kdy všichni agenti hrají stejně. To ale není to samé jako zafixovat na začátku očekávání agentů ( v podstatě libovolně) a pak říci, co za takových očekávání bude nejlepší.

    OdpovědětSmazat
  5. Předpokládám, že racionalita je deterministický rozhodovací algoritmus; při určitém konkrétním stavu poznání je rozhodnutí dáno jednoznačně. (Pokud je několik strategií rovnocenných, pak třeba lze volit smíšenou strategii s rovnoměrným rozložením pravděpodobnosti; nemyslím, že v jednorázovém VD tohle hrozí.) Potom v symetrické situaci oba racionální hráči musí rozhodnout symetricky, pokud tak neučiní, aspoň jeden je iracionální.

    Samozřejmě jsem si vědom, že racionalita tak, jak je standardně v teorii her chápána, vypadá jinak. Proto jsem nakonec tenhle článek psal.

    OdpovědětSmazat
  6. Souhlasím s vámi v tom, že racionality je takový deterministický algoritmus, jaký jste popsal. Shodneme se také v tom, že v symetrické situaci se racionální hráči rozhodnou symtericky. V tom ale není jádro sporu. Spor je v tom, co mohou hráči očekávat (resp. jaký je stav poznání). Podle mě je symetrie vlastnost rovnováhy. Podle vás něco s čím mohou hráči kalkulovat.

    Já říkám: "Ve vězňově dilematu hráč zná akce a preference hráčů, ale neví, co druhý udělá. V takové situaci zvolí oba symetricky zradit" (symetricky se rozhodnou v rovnováze každé symetrické hry)

    Vy říkáte: "Ve vězňově dilematu hráč zná akce a preference hráčů a navíc ví, že se druhý rozhodne symetricky. V takové situaci zvolí nezradit."

    Doufám, že jsem váš postoj popsal korektně.

    Mě zajímalo proč si myslíte, že je racionální, aby takové přesvědčení hráči měli, protože z "v symetrické situaci oba racionální hráči musí rozhodnout symetricky, pokud tak neučiní, aspoň jeden je iracionální" neplyne, že mohu očekávat, že druhý bude vždy dělat to co já.

    Každopádně díky za pozdní debatu.

    OdpovědětSmazat
  7. Popsal jste můj postoj téměř korektně, až na to, že netvrdím, že vždy hráč ví, že se druhý rozhodne symetricky. Pouze, že pokud ví, že druhý hráč používá stejný rozhodovací algoritmus, pak musí předpokládat, že se rozhodne symetricky.

    Možná je lepší na začátku slovo racionalita nepoužívat. Máme dva rozhodovací algoritmy, X a Y.

    Algoritmus X říká: Jestliže soupeř taktéž užívá algoritmus X, pak přiřadím pravděpodobnostní rozdělení p(s) soupeřovým strategiím a q(s) vlastním, tak aby moje smíšená strategie daná q maximalizovala očekávaný zisk při soupeřově p a zároveň soupeřova p maximalizovala jeho očekávaný zisk při mojí q. Existuje-li jediné řešení, provedu smíšenou strategii s rozdělením q. Jestliže soupeř užívá jiného algoritmu, řídím se algoritmem Ž. (Ž blíže nespecifikováno.)

    Algoritmus Y říká: jestliže soupeř užívá též algoritmu Y, pak najdu optimální symetrický strategický profil. Existuje-li jediný takový, použiji jemu odpovídající strategii. Jestliže soupeř užívá jiného algoritmu, řídím se algoritmem Ž. (Ž blíže nespecifikováno, ale stejné, jako v předchozím případě.)

    Nyní, hráč užívající algoritmus X, hraje-li proti hráči užívajícímu stejný algoritmus (a ví-li to), spadne vždy do optimální Nashovy rovnováhy, což v jednorázovém VD je zrada-zrada. Hráč užívající Y, hraje-li proti protivníkovi užívajícímu Y, skončí v paretovském optimu spolupráce-spolupráce. Když hraje X nebo Y proti Z různému od X a Y, oba užijí subalgoritmus Ž a dopadnou stejně. Není úplně jasné, co se stane, když hraje X proti Y; výsledek závisí na detailech Ž. Nicméně bez uvážení této situace je Y zaručeně lepší než X, a jestli má být některý z nich nazván racionalitou, pak preferuji Y.

    (Samozřejmě vše visí na předpokladu, že hráč s dostatečnou jistotou zná rozhodovací algoritmus svého soupeře, což v realistických situacích moc nenastává. O tom snad ale není sporu...)

    OdpovědětSmazat
  8. Ano, předpoklad, že znáte rozhodovací algoritmus soupeře je kritický. Pokud víte dopředu, jak se váš soupeř zachová, tak už ani neřešíme problém z teorie her.

    Já bych preferoval jako racionální označit tu strategii, která dává lepší výsledky v situaci, kdy nemusím předpokládat zázračné znalosti. Ale na tom se zjevně neshodneme a není to ani příliš zajímavé.

    Mimochodem, dá se ukázat, že konečně opakované vězňovo dilema s replikační dynamikou, které hrají různé algoritmy (a neznají algoritmus soupeře) může konvergovat jedině k bodu, kdy vymřou všechny algoritmy kromě toho, který vždy zradí (pokud byl samozřejmě tento algoritmus zastoupen v původní populaci).

    OdpovědětSmazat
  9. Preferuji jako racionální označit tu strategii, která dává lepší výsledky ve všech situacích. V situaci, kdy neznám soupeřův algoritmus, je zradit racionální volba, v tom se shodneme (i v tom, že to není příliš zajímavé).

    Na druhou stranu, znalost soupeřova algoritmu není nic extra zázračného. Co jiného je předpoklad, že se soupeř rozhoduje racionálně (ať už je racionalita definována jakkoliv)?

    OdpovědětSmazat
  10. Souhlasím. Jediný problém, který zůstává, je jak se mohou vytvořit správná očekávání ohledně soupeřova rozhodování. A jak mohou vypadat.

    Vezmeme si obdobu vašeho algoritmu Y, který říká: "Jestliže soupeř používá stejný algoritmus a jestliže soupeř ví, jakého algoritmu používám já, pak spolupracuj. V opačném případě zraď."
    Nemám problém označit takový algoritmus za racionální. Jen si myslím, že uvedený algoritmus nevede jednoduše ke spolupráci, protože neexistuje důvod předpokládat, že by se ostatní rozhodovali taktéž dle tohoto algoritmu (ať už ho za racionální označíme nebo ne).

    Představme si populaci algoritmů, které se potkávají a hrají vězňovo dilema. Hra je jednorázová, tj. neexistují žádné strategické vazby mezi jednotlivými setkáními. Všichni hráči si na začátku hry volí algoritmus podle kterého budou hrát. Y vypadá nejlépe (můžeme říci racionálně) a proto zvolím Y. Proč bych měl ale předpokládat, že všichni očekávají, že všichni zvolí Y? Pokud všichni očekávají, že všichni zvolí Y, pak je pro mě lepší zvolit algoritmus X, který říká: "zraď (obecněji hrej dominatní strategii, pokud existuje)". A pokud toto vím, tak nebudu předpokládat, že všichni harjí Y.

    Situace samozřejmě vypadá jinak, pokud řekneme, že existuje mechanismus, který odhaluje algoritmy agentů (např.: řekněme, že každému hráči používající Y svítí nad hlavou svatozář, kterou všichni včetně jeho vidí), pak Y povede ke spolupráci. Podle mě racionálně. Existence takového mechanismu ale není nic samozřejmého.

    OdpovědětSmazat
  11. Příklad s hráči vybírajícími algoritmus je zajímavý a vaše implikace pravdivá, ale pouze posouvá problém o jednu úroveň výše. Jestliže existuje metaalgoritmus vybírající algoritmy pro jednotlivé hry, pak tento metaalgoritmus můžeme zahrnout do toho, o čem hovoříme jako o rozhodovacím algoritmu. Obecně můžeme mít několik úrovní metaalgoritmů, ale rekurse musí v konečném počtu úrovní skončit na axiomech rozhodovací procedury (respektive na hráčově hardwaru). Pokud nálepsku "racionální" aplikujeme na axiomy (a ne pouze na určitý subsystém z nich odvozený), pak vědomí o společné racionalitě a symetrii vnějších podmínek vede ke spolupráci.

    To jistě nic nemění na tom, že neřeším podstatnou otázku, jak poznat (nebo kdy předpokládat), že soupeř má stejný algoritmus. Nemám na to pevný názor.

    OdpovědětSmazat
  12. La Kyria:

    přesvědčení "Když já nezradím, tak druhý taky nezradí" - zavání spíš magickým myšlením - než algoritmickým:)

    a zradit, je logická sebezáchovná strategie.

    OdpovědětSmazat
  13. Dobrý den,
    se zájmem jsem pročetl článek i vaší debatu. Myslím, že celý problém je do značné míry záležitost psychologická. Dovedlo mě to k následujícímu zamyšlení:

    Předně: Vězňovo dilema staví řešení na dost omezujících předpokladech (znám protihráčův algoritmus a jeho vlastnost racionality). Tedy problém vězňova dilematu je jen hrubou aproximací reality, což omezuje oblast její aplikovatelnosti.
    Ve skutečnosti je velmi nepravděpodobné předpokládat, že se sejdou protihráči, kteří budou stejní a používat stejný algoritmus (myšlení). Každý člověk je jiný...

    Další: Když už tedy stejní protihráči, domnívám se, že problém vězňova dilematu vychází ze stylu myšlení a rozhodování lidí - ze strachu. Vychází, že racionální je zradit kvůli minimalizaci ztrát (nejhorší varianta = smrt),tj. proto, že mám STRACH z možnosti, že mě soupeř zradí když já jeho ne. Nebo-li, kdyby hráči v tomto změnili své myšlení, použili by oba strategii spolupráce a vyšli by z toho oba nejlépe.
    Nebylo by pak na světě lépe?? :))

    Sandokan

    OdpovědětSmazat
  14. I když neznáte rozhodovací algoritmus protihráče, musíte zvolit nějakou strategii. Vězňovo dilema znalost protihráčovy strategie nepředpokládá, naopak, zajímavé je právě v případě, kdy tuto strategii neznáte.

    OdpovědětSmazat
  15. Dobrý den, měla bych dotaz. Jak poznám z tabulek co je vězňova dilema? Zadání: Rozhodněte z tabulek, co je vězňova dilema.

    OdpovědětSmazat
    Odpovědi
    1. úloha o vězních je postaveně chybně, tzv. scestné úlohy.
      Případ můžeme nazírat jinak:

      Jelikož každý z vězňů dostane stejné podmínky, pak úlohu vykrátíme 2 a zjednoduší se nám na jednoho jedince.

      Celý problém je totiž v tabulce, která ve skutečnosti neexistuje.
      Po vykrácení vyjde najevo logicky forsírovaná varianta:

      A, Nepráskneš- dostaneš 2 roky nebo můžeš skapat.
      B, Práskneš- dostaneš podmínku nebo můžeš sedět 15 let.

      Protože z uvedených variant je varianta A výrazně horší, bonzovat je nutnost k přežití...

      Není tu tedy co řešit.

      Smazat