v�uka

Petr Olmer, MFF UK

6.04.2008

15. p�edn�ka (10. b�ezna 2008)

Vytv��en� koalic.
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^(|AG|-1) koalic, nalezen� �e�en� je pak |AG|-kr�t hor�� ne� optim�ln�.

Petr Olmer, 6.04.2008, 19:51:00, trval� odkaz,

Koment��e (0)

P�id�n� koment��e