Lokalne koalicje w grach na sieciach

Prelegent(ci)

Piotr Sankowski

Afiliacja

Uniwersytet Warszawski

Termin

9 października 2008 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Jakosc equilibrium Nasha w grach na sieciach zostala juz dobrze zrozumiana i seminarium zaczne od wprowadzenia problmu i przypomnienia najwazniejszych wynikow. Natomiast glownym tematem saminarium bedzie cena anarchii w grzach na sieci z kosztem Shaplya, w przypadku gdy dozwolone sa lokalne koalicje miedzy graczami. W przypadku rozproszonym nie zawsze mozliwe jest komunikacja i zawiazywanie sie koalicji miedzy dowolnymi zbiorami graczy, a gracze tworzacy koalicje musza nawzajem byc swiadomi swojgo istnienia. Tutaj bede zakladal, ze gracze ktorzy dziela jakis zasob moga utworzyc koalicje, w przypadku gier na sieciach oznacza, ze gracze wspoluzytkujacy jakas krawedz moga utworzyc koalicje. Pokarze, ze taki zalozenie prowadzi zo zmniejszenia sie ceny anarchii z k do log(k), w przypadku nieskierowanych gier o jednym terminalu, w ktorych w kazdym wierzcholku umieszczony jest gracz, a k to liczba graczy. W przypadku gier skierowanych, badz o wielu terminalach lokalne koalicje nie maja duzego wplywu na cene anarchii. A wrecz moga prowadzic do negatywnych skutow, gdyz w przypadku ceny stabilnosci zwieksza sie ona z log(k) do k.

---