Operations Research seminar

Operations Research seminar

Generalization of binomial coefficients to numbers on the nodes of graphs

Anna Khmelnitskaya, UT-EWI-DMMP


The topic of this work does not relate directly to game theory, but the interest for this study is strongly influenced by our study of Shapley-type solution concepts for cooperative games with restricted cooperation introduced by means of communication graphs. If there are no restrictions on cooperation, the classical Shapley value assigns to each player as a payoff the average of the players’ marginal contributions with respect to all possible orderings of the players. However, in case of limited cooperation represented by a graph not all orderings of the players are feasible, but only those that are consistent with the graph. When the graph is a linear graph, the numbers of feasible orderings starting from each of its nodes are given by the binomial coefficients.

Any row of Pascal's triangle can be seen as a linear graph to each node of which the corresponding binomial coefficient is assigned. We show that the binomial coefficient of a node is equal to the number of ways the linear graph can be constructed when starting with this node and adding neighboring nodes one by one. Using this interpretation we generalize the sequences of binomial coefficients on the rows of Pascal's triangle to so-called connectivity degrees assigned to the nodes of an arbitrary (connected) graph. We show that on the class of connected cycle-free graphs the connectivity degrees have properties very similar to the properties of binomial coefficients. We also show that for a given connected cycle-free graph the connectivity degrees, when normalized to sum up to one, are equal to the steady state probabilities of some Markov chain on the nodes of the graph. Properties of the connectivity degrees for arbitrary connected graphs are also discussed. Because the connectivity degree of a node is defined as the number of ways the graph can be constructed by a sequence of increasing connected subgraphs starting from this node, the connectivity degrees can be seen as a measure of centrality in the graph.

Coauthored with Gerard van der Laan from the VU University Amsterdam, and Dolf Talman from the Tilburg University