Empiryczna Ewaluacja Hedonicznego Tworzenia Koalicji z Wykorzystaniem Danych

Rozważmy scenariusz w którym gracze z określoną listą preferencji muszą być podzieleni na grupy w sposób stabilny - taki, że żadna z grup nie będzie dążyła do opuszczenia gry. Dziedziną badającą strategie stablinego podziału w danych warunkach są gry hedoniczne. W niniejszej pracy opisane są gry hedoniczne o strukturze grafowej, gdzie ograniczone są dane na temat preferencji graczy, ale znana jest zasadnicza struktura badanej społeczności. W szczególności opracowana zostala implementacja algorytmu pozyskiwania stablinej partycji Igarashi, Sliwinskiego i Zick'a (ISZ) i ocenione jest jego działanie na dwóch zestawach danych. Stabilna partycja zdefiniowana jest jako podział, w którym nie ma zespółu takiego, że wszyscy gracze woleliby być w innym. Partycje wygenerowane przez algorytm ISZ porównywane są do klastrów uzyskanych przez standardowy algorytm K-means. Wprowadzona została metryka oceny skuteczności algorytmów - "poziom podobieństwa", która porównuje ze sobą klastry uzyskane przy pomocy algorytmu K-means i koalicje otrzymane przy pomocy algorytmu ISZ. W szczególności, metryka definiuje średnią ilość powtórzonych zestawień graczy dla obu podziałów. Wyniki przeprowadzonych eskperymentów sa następujące. Dla obu zestawów danych algorytm ISZ utworzył rdzeniowo stabilne partycje, zgodnie z definicją, w przeciwieństwie do algorytmu K-means. Poziom podobieństwa uzyskany dla obu zestawów danych wyniósł powyżej 20%, zauważono też wzrost tego poziomu przy eksperymentach na większym zestawie danych. Co więcej, dla jednego z zestawów danych 33% utworzonych przez ISZ partycji dokładnie powtórzył się w klastrach K-means. Czas działania algorytmów był krótszy dla algorytmu ISZ przy mniejszym zestawie danych, a przy większym efektywniejszy był algorytm K-means. Wszystkie uzyskane wyniki, w szczególności fakt uzyskania rdzeniowo stabilnych partycji, zdają się potwierdzać skuteczność algorytmu ISZ.

A group of agents with preferences has to form coalitions and the goal is to achieve a stable partition - final grouping with no deviations. This scenario is modeled by hedonic games. In this thesis presented are studies of hedonic games with graph - restricted communications, with the limited knowledge on players preferences  but some knowledge on underlying community structure. Discussed is implementation of the algorithm by Igarashi, Sliwinski and Zick1 for core stable partitioning (ISZ) and evaluated it’s effectiveness using two representative datasets. Core stability is defined as a partition with no coalition such that all players prefer another coalition to their current one. The performance of ISZ algorithm is compared to standard K-means clustering algorithm. Introduced is a metrics that compares partitions of ISZ and K-means clusters, a “similarity degree”. It is defined by the average amount of repetitive groupings that occurred in clusters and the ISZ partition. Results presented in this thesis are as following. For both datasets core stability was checked by its definition, and ISZ has produced core stable partitions, while K-means has not. Also, on two discussed datasets, similarity degree was above 20%. The similarity degree parameter also improved with increase of the dataset size. Moreover, for one of the dataset 33% of all ISZ coalitions were also repeated in K-means clustering. The CPU metrics was more favourable in ISZ for small datasets, while for larger ones it was more efficient for K-means. All aforementioned observations seem to support general effectiveness of the ISZ algorithm: forming stable partitions without much penalty on the CPU required.