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

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 between cooperative games and networks, we apply our results to some applications in Economics and Operations Research.