výuka

Petr Olmer, MFF UK

11.01.2007

11. přednáška (9. ledna 2007)

Vytváření koalic, faktorizace.

Nashova rovnováha je proti koalicím slabá. Silná Nashova rovnováha (odolnost vůči libovolné podmnožině agentů, kteří si zvýší užitek změnou své strategie) pak téměř neexistuje.

 

Vytváření koalic se převádí na hru charakteristických funkcí (CFG), ve které je cena každé koalice dána funkcí. Vytvoření koalice spočívá ve třech krocích, které jsou na sobě závislé a překrývají se: Generování struktury koalice, optimalizace cílů a zdrojů a dělení získané hodnoty.

 

Generování struktury koalizace je faktorizací množiny agentů. Všechny hry nejsou superaditivní (pak by byla triviální velká koalice, ale samotné vytvoření koalice něco stojí).

 

Hledání nejlepší koalice je superexponenciální. Algoritmus lze stáhnout na exponenciální složitost tak, že nenalezneme optimální řešení, ale víme, kolikrát je nalezené řešení horší.

 

Je potřeba projít alespoň 2^(|A|-1) koalic, nalezené řešení je pak |A|-krát horší než optimální.

Petr Olmer, 11.01.2007, 18:40:00, trvalý odkaz,

Komentáře (0)

Přidání komentáře