On social rankings and their properties

Session : SS5-2 / SS5 : Foundations and algorithms for ranking systems
Vendredi 12 février 15:00 - 16:00 Salle : CI2-06
Stefano Moretti et Meltem Öztürk

Several real-life complex systems, like human societies or economic networks, are formed by interacting units characterized by patterns of relationships that may generate a group-based social hierarchy. In this paper, we address the problem of how to rank the individuals with respect to their ability to influence'' the relative strength of groups in a society. indent For instance, consider a company with three employees $1, 2$ and $3$ working in the same department. According to the opinion of the manager of the company, the job performance of the different teams $S subseteq N={1, 2, 3}$ is as follows: ${1, 2, 3} succcurlyeq {3} succcurlyeq {1, 3} succcurlyeq {2, 3} succcurlyeq {2} succcurlyeq {1, 2} succcurlyeq {1} succcurlyeq emptyset$ ($S succcurlyeq T$, for each $S,T subseteq N$, means that the performance of $S$ is at least as good as the performance of $T$). Based on this information, the manager asks us to make a ranking over his three employees showing their attitude to work with others as a team or autonomously. Intuitively, $3$ seems to be more influential than $1$ and $2$, as employee $3$ belongs to the most successful teams in the above ranking. Can we state more precisely the reasons driving us to this conclusion? And what can we say if we have to decide who between $1$ and $2$ is more productive and deserves a promotion? The central question of this paper seems closely related to the well known problem of measuring the power of players in a cooperative game (see, for instance, [1]). However, our framework is different for at least two reasons: first, we face coalitional situations where only a qualitative (ordinal) comparison of the strength of coalitions is given; second, we look for a ranking over the single objects in $N$, and we do not require a quantitative assessment of the power'' of the players. As far as we know, the only attempt in the literature to generalize the notions of coalitional game and power index within an ordinal framework has been provided in [3], where, given a total preorder representing the relative strength of coalitions, a social ranking over the player set is provided according to a notion of textit{ordinal influence} and using the Banzhaf index [1] of a canonical'' coalitional game. We also noticed a connection with some kind of inverse problems'', precisely, how to derive a ranking over the set of all subsets of $N$ in a way that is compatible'' with a primitive ranking over the single elements of $N$ (see, for instance, [2]). Social rankings A textit{Social ranking} is defined as a map associating to each textit{power relation} (i.e., a total preorder over the sets of all subsets of $N$ representing the relative strength of coalitions) a social ranking over the elements of $N$. The properties for social rankings that we analyse in this paper have classical interpretations, such as textit{anonymity} and textit{symmetry}, saying that the ranking should not depend on the identity of the players, or the textit{dominance}, saying that a player $i$ should be ranked higher than a player $j$ whenever $i$ dominates $j$, i.e. the coalition $S cup {i}$ is stronger than coalition $S cup {j}$ for each $S subset N$ not containing neither $i$ nor $j$. Another property we study in this paper is the textit{independence of irrelevant coalitions} (iic), saying that the social ranking between two players $i$ and $j$ should only depend on the relative ranking of coalitions $U,W subset N$ such that $U setminus {i}=W setminus {j}$. Finally, we introduce the notion of textit{separability}, which specifies how to combine social rankings associated to compatible'' power relations, i.e. power relations whose intersection is still a power relation. We use these properties to axiomatically characterize social rankings on particular classes of power relations. We first notice that two natural properties, precisely, dominance and symmetry, are not compatible over the class of all power relations, despite the fact that, in some related axiomatic frameworks (see, for instance, [2]), similar axioms have been successfully used in combination. Then, we provide an axiomatic characterization of social rankings satisfying symmetry, dominance, iic and separability on a specific domain of compatible power relations (those whose intersection is still a power relation). Finally, we prove that iic and dominance determine a kind of dictatorship of the cardinality' when power relations are linear orders and a relation of dominance among coalitions of the same size holds: in this case, the only social ranking satisfying those two properties is the one imposed by the relation of dominance of a given cardinality $s in {1, ldots, |N|}$. Conclusions There are several potential directions for future research in this framework. First of all, the question about which axioms could be used to characterize a social ranking over the domain of all possible power relations is still open. In view of our results, some of the axioms we propose in this paper should be abandoned. In this respect, it is worth noting that all the properties that we analysed are based on the comparison of subsets having the same number of elements. Therefore, it would be interesting to study properties based on the comparison among subsets with different cardinalities. For instance, if $N={1,2,3}$, the information of the type ${1} succ {2, 3} succ{1, 3} succ {2}$ could be used to establish that $1$ is socially stronger than $2$ (note that $1$ strictly dominates $2$ on coalitions of size $1$, and $2$ strictly dominates $1$ of coalitions of cardinality $2$, but the interval'' between ${2, 3}$ and ${1, 3}$ is smaller than the one between ${1}$ and ${2}$).\ Another interesting aspect is related to the evaluation of the interaction among the elements of $N$. For instance, how to compare the interaction among pairs of objects taking into account their effects over all possible subsets (for instance, establishing whether the level of interaction between two objects $x$ and $y$ on a given power relation is stronger than the interaction between two other objects $w$ and $z$). References [1] Banzhaf III, J.F. (1964) Weighted voting doesn't work: A mathematical analysis. textit{Rutgers Law Review}, 19, 317. [2] Barber{a} S., Bossert W., Pattanaik P. K. (2004), Ranking sets of objects, in S. Barbera, P.J. Hammond, Ch. Seidl (eds.), Handbook of Utility Theory, Volume 2, Kluwer Academic Publishers. [3] Moretti, S. (2015) An axiomatic approach to social ranking under coalitional power relations, textit{Homo Oeconomicus}, 32(2): 183-208.

Mots clés : social ranking, coalitional power, axiomatic approach