***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Martin Loebl (Charles U)

Thursday 15th October, 3:00 in Fine Hall 224.

Title:  Shapley meets Tutte
 
 We initiate the study of cooperative games where there exist groups of pre-aligned agents. For
 example, in a road network, the agents are cross-roads and pre-aligned groups are road-segments.
 For a set of datasets, the agents are attributes and each database which connects two (or more)
 attributes is pre-aligned. In this paper, each pre-aligned group has size two.
 
Our goal is to find a way to determine the contribution of each individual local connection
 (pre-aligned couple) to the connectivity of the network, having an adversarial attack in mind or
 planning a defense of the network, or wanting to split the profits of the network between various
 owners of the individual local connections of the network. We model these contributions by Shapley
 values of the connectivity augmented ’local values’ which are characteristic functions determined,
 e.g., by failure probabilities of local connections.

 We link the concepts of potential and Shapley values of these connectivity augmented local
 values to the world of chromatic and Tutte polynomials and the partition function of the Potts
 model from statistical physics. For the paper see https://arxiv.org/abs/2607.23106
 
		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)