1 Preferencje w teorii wyboru społecznegoPreferencje w teorii wyboru społecznego. Wybór społeczny a sztuczna inteligencja. Joanna Iwaniuk Wojciech Łobacz
2 Preference Handling in Combinatorial Domains: From AI to Social ChoiceYann Chevaleyre (Univ. Paris-Dauphine) Ulle Endriss (Univeristy of Amsterdam) Jérôme Lang (CNRS & Univ. Paul Sabatier) Nicolas Maudet (Univ. Paris-Dauphine) Publikacja: grudzień 2008, „AI Magazine”
3 Po co formalizować relację preferencji?Podejmowanie decyzji jednostkowych jest stosunkowo łatwe Podejmowanie decyzji grupowych wymaga bardziej zaawansowanych mechanizmów
4 Teoria wyboru społecznegobada mechanizmy podejmowania kolektywnych decyzji Problem podziału ciasteczka Protokoły głosowania Mechanizmy aukcyjne
5 O(n) θ(2n) Aspekt obliczeniowyjak trudne jest algorytmiczne rozwiązanie problemów teorii wyboru społecznego Wykorzystanie rozwiązań ze sztucznej inteligencji i systemów wieloagentowych Rozważania na płaszczyźnie złożoności obliczeniowej O(n) θ(2n)
6 Dziedzina kombinatorycznaCzęsto przestrzeń możliwych decyzji ma rozmiar wykładniczy Przykłady: Alokacja zasobów niepodzielnych Wybór komitetu Relacja preferencji to porządek na wszystkich możliwościach
7 Po co formalizować relację preferencji? cd.Znajomość preferencji wszystkich graczy jest konieczna dla rozwiązania problemów teorii wyboru społecznego Dobra reprezentacja jest kluczowa, aby móc rozwiązać problem dla dużych danych wejściowych Nie należy oczekiwać, że gracze podadzą explicite całą swoją relację preferencji na wykładniczej liczbie elementów
8 Oczekiwania wobec języków reprezentujących preferencjeMożliwość zdefiniowania swoich preferencji dla koszyków z 30 dóbr w czasie krótszym niż czas istnienia wszechświata
9 Oczekiwania wobec języków reprezentujących preferencjeEkspresywność Zwięzłość Złożoność obliczeniowa Łatwość odczytywania informacji Możliwości używania przez ludzi
10 Typy języków Sposoby klasyfikacji można mnożyć w nieskończoność...Funkcje użyteczności vs relacje preferencji Języki specyficzne dla danego zastosowania vs języki ogólne Języki oparte na grafach Języki oparte na logice
11 Przykład języka – CP-nets (Conditional preference networks)Ogólny język do reprezentacji relacji preferencji Graf skierowany: wierzchołki – zmienne będące przedmiotem preferencji; krawędzie – zależności między zmiennymi Tabelka preferencji zależnych dla każdej zmiennej Zwykle zakłada się acykliczność
12 Przykład języka – CP-nets (Conditional preference networks)
13 Przykład 2 – języki ofertowe (bidding languages)Aukcje kombinatoryczne – sprzedający oferują więcej niż jedno dobro. Mogą występować zależności między dobrami (np. substytucja) Należałoby wycenić wartość każdego koszyka Cechy szczególne języków ofertowych Brak efektów zewnętrznych Zamiast relacji porządkującej mamy wycenę Propozycji języków powstało wiele...
14 Przykład 2 – język OR OR OR OR < , 10> < , 10>< , 10> < , 10> OR < , 10> OR < , 40> OR
15 Przykład 2 – języki ofertowe cd.Język XOR wyraża wykluczanie się koszyków Przykład: <{a}, 2> XOR <{b}, 3> - za koszyk {a, b} zapłacimy 3 OR* - dodanie sztucznych dóbr do OR w celu wyrażenia wykluczania się koszyków OR of XOR i różne inne warianty Koszyki jako formuły logiczne
16 Głosowania w dziedzinie kombinatorycznejProblematyczne przykłady: zamówienie w restauracji decyzje w lokalnych samorządach wybory komitetu sterującego
17 Paradoks wielokrotnych wyborówDzielenie zależnych preferencji wyborców Decyzja samorządu lokalnego odnośnie budowy basenu lub kortu tenisowego. Basen – {A, Ᾱ} Kort tenisowy – {U,Ū}
18 Problem lokalnego samorządu Paradoks wielokrotnych wyborówRozkład preferencji: V1, v2: AŪ > ᾹU > ᾹŪ > AU V3, v4: ᾹU > AŪ > ᾹŪ > AU V5: AU > AŪ > ᾹU > ᾹŪ Problemy? - jak powinni głosować wyborcy?
19 Problem lokalnego samorządu Paradoks wielokrotnych wyborówGłosowanie basen: AAAᾹᾹ kort: UUUŪŪ Rezultat: Basen + kort Wszyscy szczęśliwi...
20 Rozwiązania paradoksu Mniej lub bardziej złe1. pytanie o zbiór alternatyw 2. pytanie o k najwyżej wycenianych preferencji 3. limitowane kombinacje do głosowania 4. reprezentacja przy użyciu specjalnego języka 5. podział dziedziny, głosowanie (nie)zależne
21 Rozwiązania paradoksu Rozwiązanie numer 5!Porządek O = X1 > … > Xp Reguły zwycięstwa: R = { r1, … rn} Schemat działania: Pytamy wyborców o Xi niezalżne od Xi+1, … Xn przy danych X1, … Xi-1 Stosujemy ri do wyłonienia wartości Wyznaczamy Xi+1
22 Przykład rozwiązania nr 5Zmienne: DanieGłówne { M, G } > Zupa {R, K} Głosujący: 7-osobowa rodzina Prefrencje: v1, v2, v3 MK > MR > GR > GK v4, v GK > GR > MR > MK v6, v GR > GK > MK > MR DanieGłówne = G Zupa = R
23 Alokacja zasobów uczciwy podziałAukcje kombinatoryczne Efekty zewnętrzne Szczerość?
24 Uczciwość a sprawność najlepiej jedno i drugieUmieszczenie satelity na orbicie Drogo... Efektywność czy sprawiedliwość?
25 Efektywność a sprawiedliwość sposoby zapewnieniaZasada optymalności wg Pareto Dobrobyt społeczny Egalitaryzm Leximin-ordering Stop zazdrości W ekonomii dobrobytu oznacza sytuacje równowagi, polegającej na tym, ze nikt nie może otrzymać więcej dóbr bez konieczności ich odebrania komuś innemu. Należy podkreślić, ze taki podział nie komentuje sprawiedliwości podziału zysków. Zasada optymalności wg Pareto jest skrajnie niesprawiedliwa, jak też czysto egalitarna jeśli chodzi o podział dochodów. Termin ten jest użyteczny dla definicji poprawy. Zasada poprawy wg Pareto oznacza zmianę poziomu dobrobytu na korzyść danej osoby lub grupy społecznej, pod warunkiem, że nie dzieje się to kosztem żadnej innej osoby i zasada ta może mieć miejsce nawet wówczas, gdy większość populacji nie ma zysków.
26 Alokacja scentralizowana a rozproszonaOgraniczenia strukturalne Racjonalność agentów sprzedaż jednego buta
27 Podsumowania oraz pokrewne tematyWymiana informacji Złożoność jako korzyść Podział ciastka
28 Pytania ? Dziękujemy za uwagę !