Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmiczna teoria gier koalicyjnych

Informacje ogólne

Kod przedmiotu: 1000-2M12TGK Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmiczna teoria gier koalicyjnych
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

Gry koalicyjne stanowią duży, aktywnie rozwijany dział teorii gier. Są one dobrym modelem w każdej sytuacji, w której występuje synergia między graczami - zamiast grać osobno, mogą oni łączyć się w większe grupy w celu osiągnięcia korzystniejszego wyniku. Dlatego też znajdują one zastosowanie w dziedzinach tak różnych jak ekonomia, informatyka (systemy wieloagentowe), medycyna czy nauki polityczne. Badania nad grami koalicyjnymi prowadzą największe firmy z branży IT: Google, Yahoo, Microsoft.

Pełny opis:

Wykład ma na celu przedstawienie modelu gier koalicyjnych oraz głównych zagadnień tej dziedziny:

- podstawowy model - funkcja charakterystyczna oraz funkcja partycji

- kompaktowe (tj. przyjazne obliczeniowo) modele gier koalicyjnych

- najciekawsze rozwiązania gier koalicyjnych: koncepcje pozytywne i normatywne wyznaczania równowagi / podziału wypłaty

- aspekty obliczeniowe i algorytmiczne

- rozszerzone modele gier koalicyjcnyh: gry koalicyjne z efektami zewnętrznymi, gry koalicyjne z celami, gry w sieciach.

Wykład, poza teoretycznymi podstawami gier koalicyjnych, które sięgają początku poprzedniego wieku, będzie prezentował także nowe koncepcje pojawiające się w literaturze ostatnich lat oraz wiele problemów dla których wciąż nie znamy zadowalających rozwiązań. Szczególny nacisk będziemy kładli na realne zastosowania gier koalicyjnych w sztucznej inteligencji i e-businessie.

Wykład obejmować będzie:

Wprowadzenie do teorii gier

Gry w formie funkcji charakterystycznej

Pozytywne koncepcje rozwiązania gry koalicyjnej (np. rdzeń, jądro)

Normatywne koncepcje rozwiązywania gier koalicyjnych (wartość Shapleya)

Kompaktowe, przyjazne obliczeniowo, reprezentacje gier koalicyjnych – reprezentacja oparta na grafach, sieci wkładów marginalnych, algebraicznych diagramach decyzyjnych, itp.

Gry z nietrasferowalną użytecznością

Gry koalicyjne z celami, opisane umiejętnościami graczy

Gry z efektami zewnętrznymi (w formie funkcji partycji)

Rozwiązania dla gier z efektami zewnętrznymi

Aplikacje gier koalicyjnych w e-businessie

Literatura:

Literatura obowiązkowa (będzie ewentualnie rozszerzona o kilka pozycji po rozpoczęciu zajęć):

Aadithya, K. V., Michalak, T. P., & Jennings, N. R. (2011). Representation of coalitional games with algebraic decision diagrams. In AAMAS ’11: Proceedings of the 10th International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 1121–1122

Elkind, E., Goldberg, L., Goldberg, P., & Wooldridge, M. (2009). A tractable and expressive class of marginal contribution nets and its applications. Mathematical Logic Quarterly, 55 (4), 362–376.

Gómez, D., González-Arangüena, E., Manuel, C., Owen, G., Del Pozo, M., & Tejada, J. (2003). Centrality and power in social networks: A game theoretic approach. Mathematical Social Sciences, 46 (1), 27–54.

Ieong, S., & Shoham, Y. (2005). Marginal contribution nets: a compact representation scheme for coalitional games. In EC ’05: Proceedings of the Sixth ACM Conference on Electronic Commerce, pp. 193–202.

Michalak, T., Marciniak, D., Samotulski, M., Rahwan, T., McBurney, P., Wooldridge, M., & Jennings, N. (2010a). A logic-based representation for coalitional games with externalities. In AAMAS ’10: Proceedings of the 9th International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 125–132.

Sakurai, Y., Ueda, S., Iwasaki, A., ichi Minato, S., & Yokoo, M. (2011). A compact representation scheme of coalitional games based on multi-terminal zero-suppressed binary decision diagrams. In PRIMA ’11: Public Risk Management Association, pp. 4–18.

Shapley, L. S. (1953). A value for n-person games. In Kuhn, H., & Tucker, A. (Eds.), In Contributions to the Theory of Games, volume II, pp. 307–317. Princeton University Press.

Książka nieobowiązkowa, ale omawiająca dużą część poruszanych zagadnień:

Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers.

Literatura uzupełniająca:

Bachrach, Y., Markakis, E., Procaccia, A. D., Rosenschein, J. S., & Saberi, A. (2008a). Approximating power indices. In AAMAS ’08: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 943–950.

Banzhaf, J. F. (1965). Weighted Voting Doesn’t Work: A Mathematical Analysis. Rutgers Law Rev., 19, 317–343.

Castro, J., Gomez, D., & Tejada, J. (2009). Polynomial calculation of the shapley value based on sampling. Computers & Operations Research, 36 (5), 1726–1730.

del Pozo, M., Manuel, C., González-Arangüena, E., & Owen, G. (2011). Centrality in directed social networks. a game theoretic approach. Social Networks, 33 (3), 191–200.

Deng, X., & Papadimitriou, C. (1994). On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19 (2), 257–266.

Fatima, S. S., Wooldridge, M., & Jennings, N. R. (2008). A linear approximation method for the shapley value. Artificial Intellilgence, 172 (14), 1673–1699.

Myerson, R. (1977). Graphs and cooperation in games. Mathematics of Operations Research, 2 (3), 225–229.

Newman, M. (2001). Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E, 64 (1), 016132(1–7).

Suri, N., & Narahari, Y. (2010). A Shapley Value based approach to discover influential nodes in social networks. IEEE Trans. on Automation Science and Engineering, 99, 1–18.

Efekty kształcenia:

Wiedza

1. Ma uporządkowaną wiedzę w zakresie rodzajów gier koalicyjnych, ich rozwiązań, oraz powiązanych z nimi zagadnień algorytmicznych

2. Zna najważniejsze podejścia do kwesti podziału wypłaty z gry koalicyjnej i ich własności

3. Zna najważniejsze rodzaje zwięzłych, przyjaznych obliczeniowo reprezentacji gier koalicyjnych

4. Zna podstawowe własności najważniejszych zastosowań gier koalicyjnych w sztucznej inteligencji, szczególnie w systemach wieloagentowych, teorii grafów i w e-businessie.

Umiejętności

1. Potrafi określić jaki rodzaj gry koalicyjnej najlepiej odzwieciedla modelowana sytuacje w rzeczywistości

2. Potrafi formalizować zadane własności gry koalicyjnej

3. Potrafi udowodnić własności normatywne i/lub pozytywne zadanego rozwiązania gry koalicyjnej

Kompetencje

1. Rozumie potrzebę przekuwania swojej wiedzy i umiejętności informatycznych i matematycznych na konkretne rozwiązania businessowe

2. Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej

3. Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania

Metody i kryteria oceniania:

Zaliczenie ćwiczeń będzie uzależnione od:

- aktywnego uczestnictwa w zajęciach (33%)

- prezentacji przygotowanej na jedne z zajęć w grupach dwuosobowych (33%)

- kolokwkum (34%).

Zaliczenie wykladu się na podstawie egzaminu złożonego z szeregu zadań do rozwiązania (zakres materiału odpowiadać będzie tematom omawianym na zajęciach). Warunkiem dopuszczenia do egzaminu z wykladu jest zaliczenie ćwiczeń.

Zajęcia w cyklu "Semestr letni 2017/18" (w trakcie)

Okres: 2018-02-17 - 2018-06-10
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Tomasz Michalak
Prowadzący grup: Tomasz Michalak, Grzegorz Skoraczyński
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.