Téma je vysvětleno ve 1. přednášce ve prvním výukovém týdnu. Vězňovo dilema a jeho varianty se vyskytují v mnohé liteatuře a každý si může najít alternativy, které mu nejvíce vyhovují. Dobrý startovní bod ke studiu problému je určitě relevantní stránka na wikipedii. Dobrý úvod do teorie her a vysvětlení základního názvosloví nabízí český text [Pelis2008]

Princip nekooperativní dvouhráčové hry si vysvětlíme na konkrétním příkladu. Vypůjčíme si příklad z kapitoly 3, knihy [Shoham-Brown2009]. Internetový provoz se řídí protokolem TCP. Představte si, že na síti jste pouze vy (hráč A) a váš kolega (hráč B). Jedním ze základní algoritmů je tzv. backoff mechanismus. V okamžiku, kdy posíláte pakety tak, že dochází k ucpání sítě, oba ustoupíte (backoff) a opakujete vysílání po nějaké náhodné době. Takto funguje správná (Correct) implementace. Špatná (Defective) implementace znamená, že neustoupí a doufá, že tak učiní ten druhý. Máte tak k dispozici dvě strategie: spolupracovat (Cooperate) a nespolupracovat (Defect). Jestliže vy a váš kolega volíte oba C, pak je průměrné zpoždění paketů 1 ms. Jestliže oba volíte D, pak je průměrné zpoždění 3 ms, kvůli vetší režii sítě. Konečně, v případě rozdílných strategií, putují pakety hráče volícího D bez zpoždění, naopak pocitivý hráč, hrající C má zpoždění 4 ms. Možné varianty strategií a výsledných zpoždění shrnuje naásledující tabulka. Řádky patří hráči A, sloupce B. Vektor na pozici [C,D] tedy říká: hráč A kooperuje (ustoupí), hráč B nikoliv. Pakety hráče A budou mít 4 ms zpoždění, pakety hráče B cestují bez zpoždění.

Je to tzv. payoff matice. Jakou strategii zvolíte? Vaším cílem pochopitelně je, aby vaše pakety byly doručovány s co nejmenším zpožděním. Problémem je, že protokol neumožňuje, aby se hráči předem na pevno dohodli o společné strategii. Pakety se odesílají opakovaně, stejně tak je potřeba opakovaně volit vhodnou strategii. Jediné, co máte k dispozici u opakované hry, je její historie, víte tedy jak jste hrál v minulosti vy a jak váš kolega.

Naprogramujte hráče (agenta) který bude hrát opakovanou nekooperativní dvouhráčovou hru. Na vstupu je známa matice zisků (payoff matrix), počet opakování může, ale nemusí být předem znám. Cílem je maximalizovat svůj zisk, připadně minimalizovat ztrátu.

Podrobnější specifikace hráče a turnajů, které se budou hrát.

Úloha má dvě odevzdání, termíny jsou vidět v Upload systému

1. Jednoduchý hráč, který je splňuje formální požadavky, tj. je schopen hrát (úloha 03_PD_hrac).
2. Chytrý hráč, který bude hrát proti všem ostatním. Jeho hlavním úkolem je obehrát ostatní, získat největší zisk (úloha 04_PD_tur).

Hodnocení a termíny. Kolik bodů můžete získat a za co.