Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Obliczeniowa teoria wyboru społecznego

Informacje ogólne

Kod przedmiotu: 1000-2M09OTW Kod Erasmus / ISCED: 11.303 / (0612) Database and network design and administration
Nazwa przedmiotu: Obliczeniowa teoria wyboru społecznego
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:

Obliczeniowa teoria wyboru spolecznego łaczy informatyke z naukami społecznymi w kwestiach dotyczących metod podejmowania decyzji. Informatycy analizują ciekawe zagadnienia społeczne z obliczeniowego punktu widzenia. Z drugiej strony nauki społeczne pozwalają zrozumieć i zaprojektować skomplikowane systemy informatyczne, takie jak np. systemy wieloagentowe.

Wiele technik analizowanych w ramach obliczeniowej teorii wyboru społecznego wykorzystywane jest przy tworzeniu usług i oprogramowania najwiekszych firm z branży IT, takich jak, na przykład, Google, Ebay czy Microsoft (Yahoo).

Pełny opis:

Czy zastanawialiście się kiedyś w jaki sposób wyszukiwarki internetowe tworzą rankingi stron odpowiadające kryteriom wyszukiwania? Dlaczego na aukcjach ebay.com wygrany płaci nie tyle ile sam zaproponował, ale tyle ile oferował drugi z kolei licytant? Czy głosując możesz manipulować wynikiem wyborczym? Czy w aukcjach kombinatorycznych trzeba dużo kombinować? Jak sprawiedliwie podzielić ciasteczko? Jak duża jest nagroda za efektywny algorytm wspierający internetowe systemy rekomendacyjne i w jaki sposób chciałbyś/chciałabyś wydać milion dolarów?

Obliczeniowa teoria wyboru społecznego łączy informatykę z naukami społecznymi w kwestiach dotyczących metod podejmowania decyzji. Informatycy analizują ciekawe zagadnienia społeczne z obliczeniowego punktu widzenia. Z drugiej strony nauki społeczne pozwalają zrozumieć i zaprojektować skomplikowane systemy informatyczne, takie jak np. systemy wieloagentowe.

W trakcie wykładu omówimy, między innymi, ważniejsze pojęcia teorii gier w tym teorii tworzenia się koalicji, teorie głosowania, sposoby reprezentowania preferencji wyborców, techniki manipulacji, rankingi, działanie systemów rekomendacyjnych, aukcje, języki ofertowe, aukcje kombinatoryczne, procedury cake-cutting, itp.

Wiele z powyższych technik wykorzystywane jest przy tworzeniu usług i oprogramowania najwiekszych firm z branży IT, na przykład Google, Ebay, Microsoft (Yahoo).

Zajęcia powinny być interesujące dla osób, które chciałyby zobaczyć w jaki sposób ciekawe rozwiązania algorytmiczne i obliczeniowe przekuwane są na realne zastosowania biznesowe.

Literatura:

Literatura podstawowa: materiały przygotowane dla studentów.

Literatura rozszerzająca: zostanie podana na początku zajęć.

Nie ma jednego podręcznika, w którym można znaleźć całość materialu omawianego podczas wykładów. Proszę więc o zapoznanie się z poniższymi artykułami (podzielone są one wg omawianych zagadnień; gdyby mieli Państwo jakikolwiek problem z dostępem do tych pozycji proszę o kontakt):

1. Wprowadzenie do Obliczeniowej Teorii Wyboru Społecznego:

Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A Short Introduction to Computational Social Choice. Proc. SOFSEM-2007, Springer-Verlag, 2007.

Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. Preference Handling in Combinatorial Domains: From AI to Social Choice. AI Magazine, 29(4):37-46, 2008.

Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

2. Wprowadzenie do Teorii Gier

Jim Ratliff on-line resources at http://virtualperfection.com/gametheory/ Three first chapters: Strategic Form Games, Nonequilibrium Solution Concepts and Nash Equilibrium

3. Reprezentowanie Gier Koalicyjnych:

S. Ieong and Y. Shoham. Marginal contribution nets: A complact representation scheme for coalitional games. ACM EC-06, pages 170-179, 2006.

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

T. P. Michalak, T. Rahwan, J. Sroka, A. Dowell, M. J. Wooldridge, P. J. McBurney, and N. R. Jennings. On representing coalitional games with externalities. In EC'09: Proceedings of the tenth ACM conference on Electronic commerce, pages 11-20, New York, NY, USA, 2009. ACM.

4. Obliczania Wartosci Koalicji i Generowanie Optymalnych Struktur Koalicyjnych

A dynamic programming approach to the complete set partitioning problem. BIT Numerical Mathematics, 26(4):467-474, 1986.

T. Rahwan and N. R. Jennings (2008). An Improved Dynamic Programming Algorithm for Coalition Structure Generation. In Proceedings of the 7th

international conference on Autonomous Agents and Multi-Agent Systems (AAMAS-08) in Estoril, Portugal. Pages 1417-1420.

T. Rahwan and N. R. Jennings. An algorithm for distributing coalitional value calculations among cooperative agents. Artificial Intelligence

(AIJ), 171(8-9):535-567, 2007

T. Michalak, A. Dowell, P. McBurney, and M. Wooldridge. Optimal coalition structure generation in partition function games. In ECAI-08, pages 388-392, 2008.

T. Rahwan, T. Michalak, N. R. Jennings, M. Wooldridge, and P. McBurney. Coalition structure generation in multi-agent systems with positive and negative externalities. In In Proceedings of IJCAI, Pasadena, USA, 2009.

T. Rahwan, S. D. Ramchurn, A. Giovannucci, V. D. Dang, and N. R. Jennings. Anytime optimal coalition structure generation. In AAAI-07, pages 1184-1190, 2007.

T. Rahwan and N. R. Jennings (2008). Coalition Structure Generation: Dynamic Programming Meets Anytime Optimization. In Proceedings of the 23rd conference on artificial intelligence (AAAI-08) in Chicago, USA. Pages 156-161.

N. Ohta, V. Conitzer, R. Ichimura, Y. Sakurai, A. Iwasaki, and M. Yokoo. Coalition structure generation utilizing compact characteristic function representations. In To appear in the Fifteenth International Conference on Principles and Practice of Constraint Pro- gramming (CP-09), 2009.

5. Reprezentowanie Preferencji w Zastosowaniach Kombinatorycznych

J. Lang. Logical Preference Representation and Combinatorial Vote. Annals of Mathematics and Artificial Intelligence, 42(1):37-71, 2004.

6. Aukcje Kombinatoryczne - Jezyki Ofertowe

N. Nisan. Bidding and Allocation in Combinatorial Auctions, ACM EC 2000.

Craig Boutilier and H. Hoos, Bidding Languages for Combinatorial Auctions, IJCAI 2001.

7. Aukcje Kombinatoryczne - Problem Wybory Zwyciezcy

Sandholm, T. 2002. Algorithm for Optimal Winner Determination in Combinatorial Auctions.Artificial Intelligence, 135, 1-54.

Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2005. CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions. Management Science 51(3), 374-390, special issue on Electronic Markets.

Tennenholtz, M. 2000. Some Tractable Combinatorial Auctions. In Proceedings of the Seventeenth National Conference on Artificial intelligence and Twelfth Conference on innovative Applications of Artificial intelligence (July 30 - August 03, 2000). AAAI Press / The MIT Press, 98-103.

8. Procedury Cake-Cutting:

S.J. Brams and A.D. Taylor. An Envy-free Cake Division Protocol. American Mathematical Monthly, 102(1):9-18, 1995.

9. Teoria Arrowa:

J. Geanakoplos. Three Brief Proofs of Arrow?s Impossibility Theorem. Economic Theory, 26(1):211-215, 2005.

10. Manipulowanie Wynikiem Wyborów:

J. J. Bartholdi III, C. A. Tovey and M. A. Trick, The computational difficulty of manipulating an election, Social Choice and Welfare, volume 3, no. 6, 1989.

11. Projektowanie Mechanizmów:

H.R. Varian. Economic Mechanism Design for Computerized Agents. Proc. Usenix Workshop on Electronic Commerce, 1995.

Efekty uczenia się:

Wiedza

1. Zna podstawowe problemy i kerunki badawcze obliczeniowej teorii wyboru społecznego.

2. Zna podstawowe pojecia i zagadnienia z zakresu teorii wyboru społecznego.

3. Zna najważniejsze pojęcia, zagadnienia i rozwiązania z zakresu algorytmicznej teorii projektowania mechanizmów, teorii wyboru, algorytmicznej teorii gier.

4. Zna podstawowe własności najważniejszych zastosowań teorii wyboru społecznego w realnych rozwiązaniach biznesowych, w tym w e-businessie, sztucznej inteligencji i systemach wieloagentowych.

Umiejętności

1. Potrafi rozpatrzeć obliczeniowe i kombinatoryczne własność wybranych zagadnień z zakresu wyboru społecznego

2. Potrafi formalnie opisać wybrane systemy głosowania i ich własności

3. Potrafi udowodnić własności normatywne i/lub pozytywne zadanego systemu głosowania, metody podziału, itp.

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ń: na podstawie aktywności (wymagana jest obecność na ćwiczeniach, aktywne uczestnictwo w zajęciach oraz wykonanie dwóch prezentacji w grupach dwuosobowych).

Zaliczenie wykładu: na podstawie egzaminu ustnego.

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-01-25
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, Piotr Skowron
Prowadzący grup: Tomasz Michalak, Piotr Skowron
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (w trakcie)

Okres: 2019-10-01 - 2020-01-27
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
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.