A. Navarro Ramos, G. Bergantiños
Consider a group of agents is interested in some service provided by several suppliers, called sources. The connections have associated costs and agents do not care if they are connected directly or indirectly to such sources but they want to be connected to all of them. This situation is a generalization of the classical minimum cost spanning tree problem where there is a unique source. Given a cost spanning tree problem with multiple sources, the first issue to solve is to look for the least costly connection (a tree) that provides all the agents with the resource. Such tree can be obtained, in polynomial time, using the same algorithms as in the classical problem. The second issue is how to allocate the cost of the obtained tree among the agents. To address this, we extend the painting rule, a cost distribution rule of connection problems involving one source, to this context. We prove that this rule coincides with the generalized folk rule and provide an axiomatic characterization.
Palabras clave / Keywords: cost sharing, minimum cost spanning tree problems, multiple sources, folk rule, painting rule, axiomatic characterization
Programado
Sesión J02 Teoría de Juegos II
31 de mayo de 2018 09:00
Sala 5
