Исследовательский семинар 13 марта

Приглашаем на семинар, который состоится 13 марта (понедельник!) в 16.50.
Адрес: Кантемировская ул., дом 3,Высшая Школа Экономики, ауд. 356 
Тема доклада: Generalization of binomial coefficients to numbers on the nodes of graphs
Докладчик: Anna Khmelnitskaya (ПМ-ПУ СпбГУ; University of Twente)

Аннотация: The topic of this work does not relate directly to the game theory, but the interest to this study was strongly influenced by our study of Shapley-type solutions for cooperative games with limited cooperation introduced by communication graphs. Without 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 communication 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.
The triangular array of binomial coefficients, or Pascal's triangle, is formed by starting with an apex of 1. Every its row 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 starting with this node and adding subsequently neighboring nodes one by one. Using this interpretation we generalize the sequences of binomial coefficients on rows of Pascal's triangle to so-called connectivity degrees assigned to the nodes of an arbitrary (connected) graph. We show that the connectivity degrees of nodes have properties very similar to that of binomial coefficients. We also show that for a given connected cycle-free graph the connectivity degrees of nodes, when normalized to sum up to one, are equal to the steady state probabilities of some Markov chain on the nodes. Because the connectivity degree of a node in a connected graph 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 of the nodes can be seen as a measure of centrality in a graph. On the subclass of connected cycle-free graphs we provide axiomatic characterization of this connectivity centrality measure.

Цель семинара – обсуждение work in progress,
своих или чужих идей, показавшихся интересными.
Приглашаются все желающие!

Если Вы хотите выступить на семинаре, свяжитесь с Федором Сандомирским: sandomirski@yandex.ru, +7(921)633-23-53