Ranking players based on comparison functions
Stefano Moretti (LAMSADE - Université Paris Dauphine)
Ranking players based on comparison functions
Stefano Moretti (LAMSADE - Université Paris Dauphine)
Classical solutions for coalitional games are gaining growing attention for converting group performance data into individual importance metrics, with significant success in recent applications to AI. However, in many situations, the available information about coalition performance is comparative, focusing on pairs of coalitions rather than providing a numerical attribution for each coalition. Nevertheless, the final goal always stands on how to provide a meaningful ranking over individual elements. To address this problem, in this work we introduce and study a novel general framework aimed at converting the information contained within a comparison function f, which associates to each pair of coalitions S and T a real number f(S,T) representing how much S is better than T, into an attribution of importance for each single player. Our approach begins by examining how to aggregate information from comparison functions into a suitable comparison set function. We then explore the key properties of these set functions and analyze how semivalues can be computed to assess the importance of individual players, with a special focus on the Banzhaf value. After analyzing various notions of comparison functions (particularly, Net-Outdegree, Net-Flow, and Net-Schulze), which are all rooted in a concept of coalitional network where nodes are coalitions and the capacity of edges indicates the strength of direct comparisons between pairs of coalitions, we proceed with the analysis of an application context aimed at addressing the problem of social ranking, which is the ordinal counterpart of evaluating the power of players in coalitional situations.
Joint work with Daniela Bubboloni .