A panting rule in minimum cost spanning tree problems with multiple sources
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
Otros trabajos en la misma sesión
Últimas noticias
-
04/06/18
Certificados -
13/04/18
Resumen del programa y Programa detallado -
22/03/18
Descuentos en medios de trasporte para congresistas y acompañantes -
01/02/18
Ampliación del plazo de tarifa superreducida -
19/01/18
Ampliación de plazos -
15/01/18
Programación para el día 29 de mayo -
15/01/18
Conferenciantes plenarios -
12/01/18
Sede: Palacio de Congresos -
24/12/17
Sesión plenaria en memoria del Profesor Pedro Gil -
24/12/17
Corrección bases del Premio Ramiro Melendreras
