Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Teoria implementacji

Informacje ogólne

Kod przedmiotu: 1000-2M16TIM
Kod Erasmus / ISCED: 11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Teoria implementacji
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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. Alokacja zasobów z racjonalnymi agentami nastawionymi na własne korzyści (wstęp)

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

3. Implementacja w równowadze Nasha i niezdominowanej równowadze Nasha

4. Niepełna informacja (implementacja Bayesowska)

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)

Doktoranci znają tendencje rozwojowe nauk przyrodniczych i ścisłych oraz związane z nimi dylematy współczesnej cywilizacji, doktoranci znają właściwy dla swojej dyscypliny dorobek na poziomie pozwalającym na twórcze jej rozwijanie, metodologię badań w swojej dyscyplinie, umieją korzystać ze źródeł (książek, artykułów itp.) przedstawiających wyniki w swojej dyscyplinie także w języku obcym, umieją przedstawiać zaawansowane idee i wyniki w swojej dyscyplinie, umieją zorganizować samokształcenie w swojej dyscyplinie, są gotowi do podejmowania zadań naukowca w społeczeństwie.

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.

Dla doktorantów: przeczytanie aktualnego artukułu z teorii implementacji, wybranego wraz z wykładowcą.

Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)

Okres: 2024-02-19 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-80474ed05 (2024-03-12)