The degree measure as utility function over positions in graphs and digraphs

This research has been initiated when René van den Brink was Visiting Professor at the Centre d’Economie de la Sorbonne of the University of Paris 1. Agnieszka Rusinowska acknowledges the support by the National Agency for Research (Agence Nationale de la Recherche), Project DynaMITE (ANR-13-BSH1-0010-01). Both authors acknowledge the support by the Labex OSE (ANR-10-LABX-93-01). They thank particularly Stefano Moretti for pointing out the relation between graphs and cooperative TU-games. ; International audience ; We explore the possibility to compare positions in different directed and undirected graphs. We assume an agent to have a preference relation over positions in different weighted (directed and undirected) graphs, stating pairwise comparisons between these positions. Ideally, such a preference relation can be expressed by a utility function, where positions are evaluated by their assigned ‘utility’. Extending preference relations over the mixture set containing all lotteries over graph positions, we specify axioms on preferences that allow them to be represented by von Neumann–Morgenstern expected utility functions. For directed graphs, we show that the only vNM expected utility function that satisfies a certain risk neutrality, is the function that assigns to every position in a weighted directed graph the same linear combination of its outdegree and indegree. For undirected graphs, we show that the only vNM expected utility function that satisfies this risk neutrality, is the degree measure that assigns to every position in a weighted graph its degree. In this way, our results provide a utility foundation for degree centrality as a vNM expected utility function. We obtain the results following the utility approach to the Shapley value for cooperative transferable utility games of Roth (1977b), noticing that undirected graphs form a subclass of cooperative games as expressed by Deng and Papadimitriou (1994). For directed graphs, we extend this result to a class of generalized games. Using the relation ...