Lokalne koalicje w grach na sieciach

Speaker(s)

Piotr Sankowski

Affiliation

Uniwersytet Warszawski

Date

Oct. 9, 2008, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---