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

Teoria implementacji

Informacje ogólne

Kod przedmiotu: 1000-2M16TIM Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Teoria implementacji
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:

Problem implementacji zdefiniowany jest następująco: mając dany zbiór optymalnych wyników dla różnych stanów świata (w formie reguły wyboru społecznego) skonstruuj grę (mechanizm) taki, że autonomiczni, racjonalni i nastawieni na własne korzyści agenci (czy też gracze) będą mieli motywację do podejmowania indywidualnych wyborów prowadzących do wyników społecznie optymalnych. Prostym przykładem mechanizmu jest aukcja drugiej ceny (powszechnie stosowana w aukcjach internetowych takich jak allegro czy e-bay). Motywuje ona kupującuch do składania ofert równym tyle ile kupowany obiekt jest dla nich wart. Innym przykładem są internetowe systemy punktowe motywujące użytkowników do składania uczciwych ocen.

Które reguły wyboru społecznego są implementowalne w sensie opisanym powyżej? Jakie są kluczowe własności wymagane dla implementowalności? Jak implementować takie reguły? Pytania te stanowią kluczowe zagadnienia podejmowane przez teorię implementacji.

Pełny opis:

Problem implementacji zdefiniowany jest następująco: mając dany zbiór optymalnych wyników dla różnych stanów świata (w formie reguły wyboru społecznego) skonstruuj grę (mechanizm) taki, że autonomiczni, racjonalni i nastawieni na własne korzyści agenci (czy też gracze) będą mieli motywację do podejmowania indywidualnych wyborów prowadzących do wyników społecznie optymalnych. Prostym przykładem mechanizmu jest aukcja drugiej ceny (powszechnie stosowana w aukcjach internetowych takich jak allegro czy e-bay). Motywuje ona kupującuch do składania ofert równym tyle ile kupowany obiekt jest dla nich wart. Innym przykładem są internetowe systemy punktowe motywujące użytkowników do składania uczciwych ocen.

Które reguły wyboru społecznego są implementowalne w sensie opisanym powyżej? Jakie są kluczowe własności wymagane dla implementowalności? Jak implementować takie reguły? Pytania te stanowią kluczowe zagadnienia podejmowane przez teorię implementacji.

Badania nad teorią implementacji zainicjowane zostały przez Leonida Hurwicza, wychowanka Uniwersytetu Warszawskiego. Wraz z Erykiem Maskinem i Rogerem Myersonem otrzymał on nagrodę Nobla z ekonomi za fundamentalny wkład w rozwój teorii implementacji i mechanizmów.

1. Problem dobra publicznego

2. Alokacja zasobów z racjonalnymi agentami nastawionymi na własne korzyści (wstęp)

3. Implementacja w strategiach dominujących mechanizmy bezpośrednie, reguła ujawniania)

4. Implementacja w równowadze Nasha

5. Implementacja wirtualna

6. Niepełna informacja (implementacja Bayesowska)

7. Implementacja racjonalizowalna

8. Implementacja w środowiskach dynamicznych (implementacja online)

9. Odporność na błędy

Literatura:

Literatura podstawowa

L. Corchón, The theory if implementation of Socially Optimal Decisions in Economics

N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani, Algorithmic game theory

Literatura uzupełniająca

E. Maskin, T. Sjöström, Implementation Theory

M. Jackson, A crash course in implementation theory

T. Börgers, An introduction to the theory of mechanism design

M. Osborne, A. Rubinstein, A course in game theory (http://books.osborne.economics.utoronto.ca/)

Efekty uczenia się:

Wiedza:

Zna podstawowe problemy teorii implementacji oraz narzędzia formalne do ich analizowania

Zna pojęcie zgodności motywacji oraz rozumie różnice między jego wariantami

Zna podstawowe własności reguł wyboru społecznego implementowalnych w różnych pojęciach rozwiązań

Umiejętności:

Potrafi analizować implementowalność zadanych reguł wyboru społecznego w różnych pojęciach rozwiązań

Potrafi konstruować mechanizmy implementujące zadane reguły wyboru społecznego

Kompetencje:

Zna podstawowe własności implementowlnych reguł wyboru społecznego oraz odpowiadające im pojęcia zgodności motywacji

Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01)

Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu (w szczególności w kontaktach z nieinformatykiem) lub odnalezieniu brakujących elementów rozumowania (K_K02)

Metody i kryteria oceniania:

Ocena końcowa na podstawie punktów z egzaminu pisemnego. W sesji poprawkowej obowiązują takie same zasady jak w pierwszym terminie.

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

Okres: 2019-02-16 - 2019-06-08
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Marcin Dziubiński
Prowadzący grup: Marcin Dziubiński
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

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

Okres: 2020-02-17 - 2020-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: Marcin Dziubiński
Prowadzący grup: Dorota Celińska-Kopczyńska, Marcin Dziubiń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.