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

René van den Brink (jrbrink@feweb.vu.nl) and Agnieszka Rusinowska
Additional contact information
René van den Brink: VU - Vrije Universiteit Amsterdam [Amsterdam], Tinbergen Institute - Tinbergen Institute

Post-Print from HAL

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.

Keywords: Group decisions and negotiations; Weighted graph; Degree centrality; Von Neumann–Morgenstern expected utility function; Cooperative game (search for similar items in EconPapers)
Date: 2022-06
New Economics Papers: this item is included in nep-upt
Note: View the original document on HAL open archive server: https://hal.science/hal-03513560v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Published in European Journal of Operational Research, 2022, 299 (3), pp.1033-1044. ⟨10.1016/j.ejor.2021.10.017⟩

Downloads: (external link)
https://hal.science/hal-03513560v1/document (application/pdf)

Related works:
Journal Article: The degree measure as utility function over positions in graphs and digraphs (2022)
Working Paper: The degree measure as utility function over positions in graphs and digraphs (2022)
Working Paper: The degree measure as utility function over positions in graphs and digraphs (2022)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-03513560

DOI: 10.1016/j.ejor.2021.10.017

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD (hal@ccsd.cnrs.fr).