Prírodou inšpirované algoritmy

Úvod

Základná myšlienka

"To, že vidíš pred sebou mreže, ešte neznamená, že si väzeň. Možno si vonku ty."

Hra Väzenská dilema (Prisoners dilemma - PD) je hrou medzi dvoma hráčmi, pričom každý hráč si musí nezávisle od druhého hráča vybrať svoj postup (čiže nepozná rozhodnutie druhého). Výsledok závisí od oboch rozhodnutí. Hráči majú dve možnosti: buď spolupracujú s druhým hráčom alebo ho zradia.

Klasická hra Väzenská dilema má jedno kolo. Existuje tzv. Iterovaná väzenská dilema, ktorá má konečný počet krokov, pričom hráči si pamätajú rozhodnutie spoluhráča z predchádzajúceho kroku (resp. z predchádzajúcich n krokov).

Príbeh

Dvaja kriminálnici, Bert a Ernie, boli zatknutí za menší zločin - krádež auta. Uväznili ich v oddelených celách, teda nedokážu komunikovať medzi sebou. Polícia si však myslí, že Bert ako aj Ernie sú vinní v závažnejšom zločine: zabili člena ochrannej služby pri krádeži mikročipu. Detektív chce, aby obaja zradili toho druhého (teda nespolupracovali spolu). Ak ani jeden z nich neprehovorí (teda spolupracujú a predstierajú nevinu), obaja dostanú rok väzenia za krádež auta. Ak obidvaja zradia druhého, dostanú 10 rokov za vraždu. Ak jeden prehovorí a druhý ostane mlčať, nespolupracujúceho (ktorý prehovoril) prepustia, a druhý (spolupracujúci) dostane celý trest - 20 rokov väzenia. Dilemou je, či prehovoriť, alebo mlčať.

Väzenská dilema je svätým grálom teórie hier. Bola preskúmaná tisíckami matematikov, psychológov, politológov, filozófov, ekonómov, pokúšali sa ju vyriešiť a napriek tomu je stále taká tajomná a fascinujúca, ako v roku 1950, keď bola po prvý krát zverejnená Merrilom Floodom a Melvinom Drescherom.

Teória hier

Teória hier má svoje korene v teórii rozhodovania. Teória rozhodovania opisuje postup ako priniesť optimálne rozhodnutia pri neistote prostredia. Postup obsahuje určenie konečného počtu alternatív, výpočet cien a výhod jednotlivých alternatív, a odhad pravdepodobností ich nastatia. Cieľom je určiť variantu s najvyšším očakávaným prínosom.

Uvažujme príklad farmára, ktorý plánuje kúpu zavlažovacieho systému, pričom sa musí rozhodnúť medzi systémom ACME Irrigation System za $10 000 a Econo Irrigation System za $5 000. Systém Acme má postačujúci výkon aj pre dlhotrvajúce suché obdobia, systém Econo zvládne len prechodné suchoty. Dilema, pred ktorou farmár stojí spočíva v neurčitosti ktorá je spojená s dažďom. Extrémne suchoty sú extrémne zriedkavé. Farmár predpokladá, že dlhé suchoty sú raz za desať rokov. V rokoch bez sucha očakáva výnos $50 000, samozrejme bez ohľadu na typ zavlažovacieho zariadenia. Keď však príde suchý rok, polia zavlažované systémom Econo neprinesú žiadnu úrodu, kým polia zavlažované systémom Acme ešte dokážu vyprodukovať výnos $25 000.

Očakávaná hodnota :	pravdepodobnost_sucha * ( zisk_za_sucha - cena ) + pravdepodobnost_vlahy * ( zisk_za_vlahy - cena )
Acme:	0.10 * ( 25 000 - 10 000 ) + 0.90 * ( 50 000 - 10 000 ) = 37 500
Econo:	0.10 * ( 0 - 5 000 ) + 0.90 * ( 50 000 - 5 000 ) = 40 000

Podľa teórie rozhodovania na základe uvedených informácií očakávaný výnos pri systéme Acme je 37 500 a pri systéme Econo 40 000. Racionálne uvažujúci farmár vyberie systém, ktorý ponúka väčší výnos, teda systém Econo.

Zvyčajne predpokladáme, že ľudia zodpovední za rozhodovania v rámci medzinárodných vzťahoch formálne alebo neformálne vykonajú podobný výpočet, keď sa rozhodujú medzi alternatívami. Avšak medzi rozhodovaním o investícii do zavlažovacieho systému a rozhodovaním v medzinárodných vzťahov je jeden zásadný rozdiel: existencia oponenta. Rozhodujúci nemôže jednoducho určiť výsledok jeho rozhodnutia, ten závisí aj od rozhodnutia oponenta. Pri analýze problémov s viacerými účinkujúcimi a vzájomne závislými voľbami sa využíva teória hier.