Members of the G²OAT research group from the Department of Theoretical Computer Science and their colleagues from the Department of Applied Mathematics at the Faculty of Information Technology of the Czech Technical University in Prague (FIT CTU) presented the results of their research this year at the prestigious international conference IJCAI (International Joint Conference on Artificial Intelligence). The 35th edition of the conference was held jointly with the 28th European Conference on Artificial Intelligence (ECAI) from 15 to 21 August in Bremen, Germany. IJCAI is one of the world’s most important international gatherings of artificial intelligence researchers.
The first paper, entitled “Learning Minimally Rigid Graphs with High Realization Counts,” was co-authored by Oleksandr Slyvka, Jan Rubeš (ETH Zurich), Rodrigo Alves, and Jan Legerský. The authors study graphs that can be used, for example, to describe various interconnected systems. They focus on how to find graphs that can have as many different configurations as possible while remaining firmly “connected.”
This can be imagined as a network of points connected by rods. The rods have fixed lengths, yet the entire structure can still be arranged in several different ways. The researchers looked for graphs with the largest possible number of such configurations. To find them, they used machine-learning methods, specifically reinforcement learning, in which an algorithm gradually learns how to construct the best possible solution. The proposed method successfully discovered new examples of graphs with a record-high number of possible configurations.
The second paper, “Tight Asymptotic Bounds for Fair Division with Externalities,” addresses a problem we may encounter in everyday life: how to divide a limited amount of goods among several people as fairly as possible. The authors are Frank Connor (MIT), Max Dupré la Tour (McGill University), Vishnu V. Narayan (IIT Bombay), and Šimon Schierreich.
The situation becomes more complicated when people care not only about what they receive themselves, but also about how the remaining items are allocated. One example could be a new coffee machine purchased for a department: although each employee would appreciate having the coffee machine assigned to them, if that does not happen, they may prefer the machine to go to a colleague in the same office rather than to someone on the other side of the building. The researchers show what theoretical guarantees on the degree of fairness can be achieved in such models.
“Our research aims to bring the theory of fair resource allocation closer to real life. We therefore sought to extend the basic model by incorporating so-called externalities, which allow us to express more complex preferences of our agents. Our results show that, in this more complex model, we lose many of the fairness guarantees that hold in the absence of externalities,” explains Šimon Schierreich.
The third article, “Agreement, Diversity, and Polarization Indices for Approval Elections,” focuses on the design of indices that measure fundamental properties of elections: agreement among voters, diversity of their opinions, and societal polarization. Based on the proposed indices, the authors created a map of elections that makes it possible to compare individual elections according to their characteristics. The map incorporates data from various sources, including Pabulib and PrefLib. The analysis of real-world elections also shows that most elections exhibit low levels of polarization and tend to have higher diversity than agreement among voters. At the same time, the proposed visualization method is able to preserve the structure of the data with very little distortion. The authors are Piotr Faliszewski (AGH University of Kraków), Jitka Mertlová, Krzysztof Sornat (AGH University of Kraków), Stanisław Szufa (University of Geneva), and Tomasz Wąs (University of Oxford).
Researchers from the G²OAT research group also contributed to the programme of the 4th IJCAI Workshop on Computational Fair Division, which was held as part of the conference. The workshop focused on computational methods for fair resource allocation and was co-organized by Šimon Schierreich. At the workshop, Dušan Knop also presented the joint paper “Dividing Indivisible Items for the Benefit of All: It Is Hard to Be Fair Without Social Awareness,” which was also published this year at the prestigious AAAI conference.