projekt Sonata 2015/19/D/ST6/03113, finansowany przez Narodowe Centrum Nauki
realizowany @ MIM Uniwersytet Warszawski, 2016-2019.
Przy dużej ilości partii w parlamencie często trudno jest określić, jaką siłę ma każda z nich. Partia która ma więcej niż połowę miejsc w sejmie, posiada oczywiście całą władzę, bo może przegłosować praktycznie każdą ustawę. Utrata większości chociażby jednym głosem diametralnie zmienia jednak sytuację - partie muszą wówczas tworzyć koalicje, aby rządzić, a rozkład siły staje się skomplikowaną funkcją zależną od liczby mandatów posiadanych przez każdą z partii.
Matematycy mają jednak do tej analizy specjalne narzędzie - gry głosowania ważonego. W tym niezwykle prostym modelu każdy z graczy (w naszym przykładzie reprezentujący partię polityczną) ma pewną liczbę głosów, a decyzja podejmowana jest, jeżeli liczba głosów graczy ją popierających osiągnie pewien próg. Od modelu jest już tylko krok do policzenia siły - służą do tego indeksy siły, które liczą jak często głosy danego gracza zmieniają przegrywającą koalicję na wygrywającą.
Niestety jak większość modeli teoretycznych gry głosowania ważonego opierają się na wielu upraszczających założeniach. Model zakłada między innymi, że każdy gracz jest zawsze zdolny do współpracy z każdym innym graczem. W rzeczywistości jednak ze względu na sympatie i antypatie polityczne wiele rozpatrywanych w modelu koalicji nie jest realnie prawdopodobnych.
Kluczowym celem naszego projektu jest zaproponowanie bardziej realistycznego modelu gier głosowania ważonego, który radzi sobie ze wspomnianymi problemami oraz stworzenie technik, które pozwolą na efektywne obliczenie w nim siły graczy.
W sercu systemów wieloagentowych znajduje się możliwość współpracy aby polepszyć działanie indywidualnych agentów lub całego systemu. Powszechnie w literaturze zakłada się, że taka współpraca jest praktycznie nie Istotą systemów wieloagentowych jest umiejętność współpracy w celu poprawy wydajności poszczególnych agentów i/lub systemu jako całości. Podczas gdy powszechnym założeniem w literaturze jest to, że taka współpraca jest zasadniczo nieograniczona, w wielu realistycznych sytuacjach to założenie nie jest spełnione. Bardzo popularnym podejściem do modelowania takich scenariuszy są gry ograniczone grafem wprowadzone przez Myersona. W tym podejściu agenci są reprezentowane przez węzły w grafie, krawędzie reprezentują kanały komunikacyjne, a grupa może generować dowolną wartość tylko wtedy, gdy istnieje bezpośredni lub pośredni kanał komunikacji między każdą parą agentów w grupie. Dwie podstawowe koncepcje rozwiązania, które zostały zaproponowane dla takich gier to wartość Myersona i wartość Shapley. Chociaż opracowano algorytm obliczający wartość Shapleya w dowolnychgrafach, do tej pory nie opracowano takiego algorytmu dla wartości Myersona. Mając to na uwadze, postanowiliśmy opracować dla takich gier algorytm ogólnego przeznaczenia do obliczania wartości Myersona i bardziej efektywnego algorytmu obliczania wartości Shapley.
Gry ograniczone grafem Myersona są znanym formalizmem do modelowania ograniczeń w kooperacji. (...) Calvo et al. uogólnił rezultaty Myersona rozpatrując grafy probabilistyczne w których agenci mogą kooperować tylko w pewnym zakresie czy też z pewnym prawdopodobieństwem. W tej pracy proponujemy pierwszy algorytm dla uogólnionego modelu Calvo et al. Nasz algorytm bazuje na enumerowaniu wszystkich podgrafów w grafie. Jako przykładową aplikację nowego algorytmu rozpatrujemy graf probabilistyczny który reprezentuje prawdopodobieństwo współpracy pomiędzy partiami politycznymi przed wyborami parlamentarnymi w 2015 roku w Wielkiej Brytanii.
Assessing the progress made in AI and contributions to the state of the art is of major concern to the community. Recently, Frechette et al. [2016] advocated performing such analysis via the Shapley value, a concept from coalitional game theory. In this paper, we argue that while this general idea is sound, it unfairly penalizes older algorithms that advanced the state of the art when introduced, but were then outperformed by modern counterparts. Driven by this observation, we introduce the temporal Shapley value, a measure that addresses this problem while maintaining the desirable properties of the (classical) Shapley value. We use the tempo- ral Shapley value to analyze the progress made in (i) the different versions of the Quicksort algorithm; (ii) the annual SAT competitions 2007–2014; (iii) an annual competition of Constraint Programming, namely the MiniZinc challenge 2014–2016. Our analysis reveals novel insights into the development made in these important areas of research over time.
