Členové výzkumné skupiny G²OAT z Katedry teoretické informatiky a jejich kolegové z Katedry aplikované matematiky Fakulty informačních technologií ČVUT v Praze (FIT ČVUT) letos prezentovali výsledky svého výzkumu na prestižní mezinárodní konferenci IJCAI (International Joint Conference on Artificial Intelligence). Letošní 35. ročník se konal společně s 28. ročníkem European Conference on Artificial Intelligence (ECAI) od 15. do 21. srpna v německých Brémách. IJCAI patří mezi nejvýznamnější mezinárodní setkání výzkumníků v oblasti umělé inteligence.
První článek s názvem „Learning Minimally Rigid Graphs with High Realization Counts“ vznikl ve spolupráci Oleksandra Slyvky, Jana Rubeše (ETH Zurich), Rodriga Alvese a Jana Legerského. Autoři se zabývají grafy, které lze využít například k popisu různých propojených systémů. Zajímá je přitom otázka, jak najít takové grafy, které mohou mít co nejvíce různých podob, přestože zůstávají pevně „spojené“.
Představit si to můžeme například jako síť bodů propojených tyčemi. Tyče mají danou délku, ale celá konstrukce může být přesto uspořádána několika různými způsoby. Výzkumníci hledali grafy, u nichž je těchto možných uspořádání co nejvíce. K jejich hledání využili metody strojového učení, konkrétně takzvané zpětnovazební učení (angl. reinforcement learning), při kterém se algoritmus postupně učí, jak vytvořit co nejlepší řešení. Navržená metoda dokázala najít nové příklady grafů s rekordně vysokým počtem možných uspořádání.
Druhý článek „Tight Asymptotic Bounds for Fair Division with Externalities“ se zabývá problémem, se kterým se můžeme setkat v běžném životě: jak rozdělit omezené množství věcí mezi více lidí co nejférověji. Autory jsou Frank Connor (MIT), Max Dupré la Tour (McGill University), Vishnu V. Narayan (IIT Bombay) a Šimon Schierreich.
Situace je ještě složitější, pokud lidem nezáleží pouze na tom, co dostanou oni sami, ale také na konkrétním rozdělení ostatních věcí. Příkladem takové situace může být nový kávovar zakoupený na katedru: přestože by každý ze zaměstnanců ocenil, pokud by byl kávovar přidělen právě jemu, v případě, že se to nestane, je jistě lepší, když kávovar dostane kolegyně ze stejné kanceláře než kolega z druhé strany budovy. Výzkumníci ukazují, jaké jsou teoretické hranice stupně férovosti, kterou v takových modelech můžeme garantovat.
„Náš výzkum se snaží přiblížit teorii férového rozdělování zdrojů reálnému životu. Pokusili jsme se tedy základní model rozšířit o tzv. externality, které nám umožňují vyjádřit složitější preference našich agentů. Naše výsledky ukazují, že v tomto složitějším modelu ztrácíme mnohé garance férovosti, které platí bez přítomnosti externalit,“ vysvětluje Šimon Schierreich.
Třetí článek ,,Agreement, Diversity, and Polarization Indices for Approval Elections” se zabývá návrhem indexů, které měří základní vlastnosti voleb: shodu mezi voliči, rozmanitost jejich názorů a polarizaci společnosti. Na základě navržených indexů autoři vytvořili mapu voleb, ve které lze jednotlivé volby porovnávat podle jejich charakteru. Mapa zahrnuje data z různých zdrojů, mimo jiné Pabulib a Preflib. Analýza reálných voleb navíc ukazuje, že většina voleb vykazuje nízkou polarizaci a spíše vyšší rozmanitost než shodu mezi voliči. Navržený způsob vizualizace přitom dokáže strukturu dat zachovat s velmi malým zkreslením. Autory jsou Piotr Faliszewski (AGH University of Kraków), Jitka Mertlová, Krzysztof Sornat (AGH University of Kraków), Sanisław Szufa (University of Geneva) a Tomasz Wąs (University of Oxford).
Výzkumníci z výzkumné skupiny G²OAT se letos podíleli také na programu 4th IJCAI Workshop on Computational Fair Division, který se konal v rámci konference. Workshop byl zaměřený na výpočetní metody pro férové rozdělování zdrojů a na jeho organizaci se podílel Šimon Schierreich. Na workshopu zároveň prezentoval Dušan Knop společný článek „Dividing Indivisible Items for the Benefit of All: It Is Hard to Be Fair Without Social Awareness“, který letos vyšel také na prestižní konferenci AAAI.
