A panting rule in minimum cost spanning tree problems with multiple sources
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
Otros trabajos en la misma sesión
C. M. Manuel García, D. Martín García
J. Castro Cantalejo, R. Espínola Vílchez, D. Gómez González, I. Gutiérrez García-Pardo
I. Gutiérrez García-Pardo, J. Castro Cantalejo, R. Espínola Vílchez, D. Gómez González
Ú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
