Some Axiomatic and Algorithmic Perspectives on the Social Ranking Problem
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
- PDF / 258,078 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 69 Downloads / 187 Views
Abstract. 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. We also analyse the effect of basic properties in the computation of a social ranking within specific classes of (ordinal) coalitional situations. We show that the pairwise combination of these natural properties yields either to impossibility (i.e., no social ranking exists), or to flattening (i.e., all the individuals are equally ranked), or to dictatorship (i.e., the social ranking is imposed by the relative comparison of coalitions of a given size). Then, we turn our attention to an algorithmic approach aimed at evaluating the frequency of “essential” individuals, which is a notion related to the (ordinal) marginal contribution of individuals over all possible groups. Keywords: Social ranking · Coalitional power · Ordinal power · Axioms
1
Introduction
Ranking is a fundamental ingredient of many real-life situations, like the ranking of candidates applying to a job, the rating of universities around the world, the distribution of power in political institutions, the centrality of different actors in social networks, the accessibility of information on the web, etc. Often, the criterion used to rank the items (e.g., agents, institutions, products, services, etc.) of a set N also depends on the interaction among the items within the subsets of N (for instance, with respect to the users’ preferences over bundles of products or services). In this paper we address the following question: given a finite set N of items and a ranking over its subsets, can we derive a “social” ranking over N according to the “overall importance” of its single elements? We are grateful to Hossein Khani for pointing out a mistake in the proof of Proposition 2. We also thank four anonymous referees for their valuable suggestions and comments on a former version of this paper. This work benefited from the support of the projects AMANDE ANR-13-BS02-0004 and CoCoRICo-CoDec ANR-14-CE240007 of the French National Research Agency (ANR). c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 166–181, 2017. DOI: 10.1007/978-3-319-67504-6 12
Some Axiomatic and Algorithmic Perspectives on the Social Ranking
167
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 ⊆ N = {1, 2, 3} is as follows: {1, 2, 3} {3} {1, 3} {2, 3} {2} {1, 2} {1} ∅ (S T , for each S, T ⊆ 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
Data Loading...
