Approximately Equivalent Induced Subgraph Games

Speaker: Filippo Bistaffa - researcher at the IIIA-CSIC. 

Characteristic function games (CFGs) are a well-known game-theoretic concept in which every subset of a given set of agents is associated to a value by a so-called "characteristic function". This approach inherently requires an exponential amount of space to store the characteristic function, severely limiting the scalability of characteristic function games for real-world applications. In this talk, I will discuss AE-ISG, our approach that allows one to approximate every CFG as an induced subgraph game (ISG), a succinct game representation that is based on a weighted graph among the agents. Such a transformation incurs obvious benefits in terms of tractability of computing solution concepts for the initial game. We propose a novel coalition structure generation (CSG) approach for ISGs that is based on graph clustering, which outperforms existing CSG approaches for ISGs by using off-the-shelf optimisation solvers.