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

René van den Brink*, Agnieszka Rusinowska

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

109 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)1033-1044
Number of pages12
JournalEuropean Journal of Operational Research
Volume299
Issue number3
Early online date17 Oct 2021
DOIs
Publication statusPublished - 16 Jun 2022

Bibliographical note

Funding Information:
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.

Publisher Copyright:
© 2021

Keywords

  • Cooperative game
  • Degree centrality
  • Group decisions and negotiations
  • Von Neumann–Morgenstern expected utility function
  • Weighted graph

Fingerprint

Dive into the research topics of 'The degree measure as utility function over positions in graphs and digraphs'. Together they form a unique fingerprint.

Cite this