Problemas de conexion y de repartode costes

Federico Perea Justo Puerto*

MaMaEuSch**

Management Mathematics for European Schools94342 - CP - 1 - 2001 - DE - COMENIUS - C21

*Universidad de Sevilla**Este proyecto ha sido desarrollado con ayuda parcial de la Union Europea dentro del marco del pro-

grama Socrates. El contenido no refleja necesariamente la posicion de la Union Europea ni implica ningunaresponsabilidad por parte de la Union Europea.

0

1. Conceptos previos

En este trabajo describimos algunas situaciones que pueden ser representadas mediantegrafos. Para investigar dichas situaciones no necesitamos un estudio detallado de grafos,aunque sı algunos conceptos. Comenzamos introduciendo la idea de grafo a partir deunos ejemplos.

1.1. Ejemplos

El diagrama de la figura 1 es un mapa de lo que sera el metro de la ciudad de Sevilla.Como todos los mapas, no representa cada detalle de la ciudad, sino solo aquellos derelevancia para sus usuarios. En el caso de este mapa, la localizacion geografica exactade las estaciones no son importantes. Sin embargo, lo que sı es importante es la formaen la que estan interconectadas, de tal forma que un pasajero pueda planear una rutadesde una estacion hasta otra. El mapa es simplemente un diagrama que indica comolas estaciones estan interconectadas.

Planos arquitectonicos El plano de la planta baja de una casa viene representado en lafigura 2.

Para pequenos planos como este, tales diagramas son apropiados para mostrar quehabitaciones estan conectadas, pero para planos grandes necesitarıamos una repre-sentacion mas comoda. Una representacion posible serıa la mostrada en la figura 3,donde las habitaciones vienen dibujadas como pequenos cırculos rellenos.

Los arquitectos denominan a estos diagramas diagramas de circulacion, debido a suuso al analizar movimientos de personas en edificios grandes. En particular, se hanusado en el diseno de aeropuertos y en el trazado de supermercados. Diagramas de estetipo son utiles para representar la conexion entre varias habitaciones, pero no nos daninformacion sobre su tamano o forma.

1.1.1. Definicion de un grafo

El punto que tienen en comun los ejemplos anteriores es que en cada uno de ellos tenemosun sistema de ‘objetos’ que estan interrelacionados de alguna forma. En el primer ejemplolos objetos son estaciones interconectadas por vıas de tren, y en el segundo ejemplo sonhabitaciones con accesos entre ellas. En cada caso podemos dibujar un diagrama en el cual losobjetos vienen representados por puntos y las interconexiones se representan mediante lıneas.Dichos diagramas se denominan grafos. Los puntos que representan los objetos se llamanvertices (tambien llamados nodos o puntos), y las lıneas que representan las interconexiones

1

Figura 1: Futuro metro de la ciudad de Sevilla.

se denominan ejes (tambien llamadas arcos o simplemente lıneas). Por ejemplo, el diagramade circulacion de la casa es un grafo con siete vertices (la cocina, el hall, la sala de estar, etc.)y diez ejes (que son las interconexiones entre las diferentes habitaciones).

Podemos formalizar estas ideas de la siguiente forma:

Definicion 1.1 Un grafo es un diagrama que se compone de puntos, llamados vertices, unidosentre sı por lıneas, llamadas ejes; cada eje une exactamente dos vertices.

Tambien necesitamos conocer dos conceptos: el de ciclo y el de conexion.Decimos que un grafo G es conexo si entre cada par de puntos en G existe un camino que

los une. Tanto el ejemplo del metro como el del plano de la planta baja de la casa nos dangrafos conexos. El grafo de la figura 4 es disconexo, en otras palabras, no conexo.

Un camino que conecta un vertice consigo mismo se denomina ciclo. En la figura 3 elcamino

2

Figura 2: Planta baja.

sala de estar - salon - estudio - sala de estar

es un ciclo, porque une la sala de estar consigo misma.Estos conceptos nos llevan a un tipo de grafos que vamos a usar en este trabajo: los arboles.

Un grafo conexo que no contiene ciclos es un arbol. En la figura 5 se muestran algunos ejemplosde arbol.

Si G es un grafo conexo, entonces un arbol de union en G es un arbol que contiene a todoslos vertices de G. Consideremos como ejemplo el grafo de la figura 6.

El numero de arboles de union en un grafo puede ser muy grande (acotado superiormentepor 2n−2, donde n es el numero de nodos que tiene la red). En la figura 7 presentamos tresposibles arboles de union del grafo mostrado en la figura 6.

1.2. Situaciones cooperativas

En muchas situaciones encontramos varios agentes que, cuando unen sus esfuerzos, puedenobtener mayores beneficios (o menores costes) despues de llevar a cabo una accion, por ejem-plo un negocio. Esas situaciones se llaman situaciones cooperativas, porque se permite a losagentes que cooperen. Veamos un ejemplo.

1.2.1. Ejemplo

Tres amigos, Julian, Paula y Marcos, estan pensando la posibilidad de crear un centro deatencion para la tercera edad, dirigido a personas de entre 60 y 80 anos. Despues de investigar

3

Figura 3: Grafo.

las leyes locales y el mercado, estiman lo siguiente. Necesitan una enfermera por cada cuatroancianos de entre 71 y 80 anos, y una enfermera por cada diez personas de entre 60 y 70 anos.Se necesitan 8 metros cuadrados interiores y 4 exteriores por cada anciano de entre 71 y 80anos. Para los clientes entre 60 y 70 anos se exigigen 5 y 6 metros cuadrados respectivamente.Despues de calcular los costes se dan cuenta de que pueden obtener un beneficio neto de 200Euros por cada cliente de entre 71 y 80 anos y un beneficio neto de 150 Euros por cada unodel otro grupo.

Julian conoce a 9 personas a las que podrıa contratar como enfermeras. Tambien tiene laposibilidad de alquilar 260 metros cuadrados interiores y 200 exteriores. Por lo tanto tieneque resolver un problema de programacion lineal para calcular el maximo beneficio que puedetener por su cuenta cumpliendo con las leyes. Si llamamos x1 al numero de ancianos del grupode edad 71-80 que puede atender, y x2 al numero de personas que puede alojar del otro grupo,el problema a resolver para calcular el maximo beneficio que Julian puede obtener es: 1

1Para mas detalles sobre programacion lineal ver: H.W.Hamacher, E.Korn, R.Korn, S.Schwarze Planifi-cacion de la Produccion y Optimizacion Lineal en la pagina web de MaMaEuSchhttp://www.mathematik.uni-kl.de/ mamaeusch/allgemein e/frames2 e.html (2004).

4

Figura 4: Grafo disconexo.

max 200x1 + 150x2

s.a. 14x1 + 1

10x2 ≤ 9

8x1 + 5x2 ≤ 2604x1 + 6x2 ≤ 200x1 ≥ 0, x2 ≥ 0

Despues de resolver el problema se deduce que puede obtener un beneficio de 7000 Eurossi actuase solo, alojando a 20 personas de cada grupo de edad.

Paula conoce a 5 personas a las que puede contratar como enfermeras y Marcos conocea 14. Paula tiene la posibilidad de alquilar 120 metros cuadrados interiores y 200 exteriores,mientras que Marcos puede alquilar 590 interiores y 400 exteriores. Cuando resolvemos losproblemas de programacion lineal para Paula y Marcos, averiguamos que Paula puede tenerun beneficio maximo de 3600 Euros si actua sola, y Marcos puede ganar 14000 Euros si montala residencia contando solo con sus medios.

Pero tambien pueden combinar sus recursos. Suponemos que no hay coincidencias entre laspersonas que pueden emplear como enfermeras. Si Julian y Paula decidiesen trabajar juntos,tendrıan un beneficio de 11000 Euros. Si Julian y Marcos trabajasen juntos obtendrıan unbeneficio de 22500 Euros. Si Paula y Marcos trabajasen juntos ganarıan 19500. Y si todosellos unen sus recursos y trabajan juntos obtendran un beneficio de 26500 Euros. La situacion

5

Figura 5: Arboles.

se puede resumir en la siguiente tabla:

S v(S) S v(S) S v(S) S v(S){1} 7000 {3} 14000 {1,3} 22500 {1,2,3} 26500{2} 3600 {1,2} 11000 {2,3} 19500 ∅ 0

donde denotamos a Julian con el numero 1, a Paula con el 2 y a Marcos con el 3, y v(S) esel maximo beneficio que el grupo S puede obtener si actua uniendo sus recursos y sin contarcon la ayuda de los demas.

Su beneficio total es maximizado si combinan sus recursos. En este caso tendran queencontrar la forma de dividir los 26500 Euros que ganan entre los tres.

2. Problemas de conexion y de reparto de costes

En muchas situaciones cotidianas nos encontramos con problemas de optimizacion. Sueleocurrir que cuando varios elementos (personas, empresas, etc.) unen esfuerzos para realizar

6

Figura 6: Este grafo no es un arbol.

una accion en comun que va a dar servicio a todos ellos, el gasto total generado es inferioral gasto que generarıan realizando dicha accion por separado. Hasta ese momento todo esventajoso, ya que entre todos van a gastar menos dinero al actuar en comun y tendran elmismo servicio. Pero un nuevo problema aparece: como se reparten los pagos que ha generadola realizacion de la accion comun.

Imaginemos que un grupo de granjeros va a construir una valla de alambre para separar sustierras. Debido a que las vallas delimitan dos territorios estas son usadas por varios granjeros.Por ello parece logico que las vallas sean instaladas entre todos ellos y no que cada uno seconstruya su propia alambrada. Llega la hora de pagar y, por tanto, aparecen los problemas.

En muchas situaciones similares a las descritas se llega a la determinacion de que todoslos usuarios del servicio han de pagar los gastos a partes iguales, en adelante esta reglasera llamada reparto proporcional, e incluso se piensa que es los mas justo. Veremos a travesde unos ejemplos que el reparto proporcional no siempre es “justo”, teniendo en cuenta losproblemas que el significado de la palabra “justicia” puede ocasionar.

3. El problema de asignacion de costes de conexion

El primer problema que vamos a abordar pertenece a una clase de problemas: problemasde arbol de expansion de coste mınimo (minimum spanning tree). En estos problemas tenemosuna serie de usuarios que quieren beneficiarse de un producto proveniente de una fuente fijada.Queremos conectar a todos los usuarios a la fuente. La red de conexion no es fija, es decir, se

7

Figura 7: Arboles.

podran conectar los puntos de cualquier forma posible.

Ejemplo 3.1 Consideremos un grupo de aldeas, cada una de los cuales necesita ser conectadaa un embalse, directamente o a traves de otras aldeas. Cada posible conexion tiene alguncoste asociado y el problema radica en como conectar todas las aldeas al embalse de tal modoque los costes totales de crear la red sean mınimos. La red construida a mınimo coste sedenominara arbol de mınima union (minimum spanning tree).

Sin embargo, la construccion de un arbol de union mınima es solo parte del problema.Ademas de minimizar los costes totales, tambien tiene que ser planteado un problema dereparto de costes, es decir, decidir cuanto paga cada aldea para construir la red que lasconecta a todas. En siguientes ejemplos plantearemos varias reglas de reparto y discutiremosla idea de reparto justo.

Formalmente, un problema de mınima union es una tripleta T = (N, ∗, t), donde N ={1, ..., n} es el conjunto de jugadores (aldeas), ∗ es la fuente (el embalse) y t : EN∗ → R+ es lafuncion de coste no negativa, es decir, asigna a cada arista un coste (lo que costarıa construir

8

cada tuberıa). ES esta definida como el conjunto de todas las aristas entre pares de elementosde S ⊂ N∗, ası que (S, ES) es el grafo completo sobre S.

ES = {{i, j} / i, j ∈ S, i 6= j}.Como los costes de conexion son no negativos, es obvio que un grafo de coste mınimo que

conecte todos los jugadores a la fuente es en realidad un arbol, lo que explica el nombre delproblema.

Dado un problema T = (N, ∗, t) y un juego (N,R) para la coalicion principal, el repartode Bird, βR(T ) se construye mediante la asignacion de cada nodo i ∈ N al coste de la primeraarista sobre el camino unico en (N∗, R) desde el jugador i a la fuente ∗. La computacion deeste reparto puede ser obtenida a partir del algoritmo de Prim, el cual, empezando desde laraız fijada, construye un arbol de union mınima mediante la consecuente adicion de aristas conel coste mas bajo, sin introducir ciclos (caminos que unen un punto con si mismo). Veamosun ejemplo.

En el caso que aparece en la figura 8, queremos conectar tres nodos; A, B y C a una fuente(S) localizada en el punto rojo del dibujo, con el menor coste posible.

Figura 8: Ejemplo del algoritmo de Prim.

Primero unimos la fuente con su nodo mas cercano, que en este ejemplo es B. Despuesde eso encontramos el nodo mas cercano a B o a la fuente, y este resulta ser A. A esta mascerca de B que de C, por tanto conectamos A con B. Para terminar tenemos que conectarC al grafo. Para conseguir el mınimo arbol de union tenemos que hacerlo a mınimo coste,es decir, conectamos C a su nodo mas cercano de entre los que ya estan en el grafo. En el

9

ejemplo, el nodo mas cercano a C es la fuente, por eso construimos el arco que une C conla fuente. El resultado es el dibujo numero 4 de la figura 8, el mınimo arbol de union de losnodos mostrados en el dibujo numero 1.

Veamos formalmente como funciona la Regla de Bird:

Entrada: un problema de mınima union (N, ∗, t).Salida: un conjunto de aristas R ⊂ EN∗ y el correspondiente reparto de Bird βR(T ).

1. Elegir la fuente ∗ como raız

2. Iniciar R = ∅.3. Encontrar una arista de coste mınimo e = {i, j} ∈ EN∗\R incidente en ∗, o en cualquiera

de los vertices presentes en una de las aristas en R, de tal modo que la union e a R nointroduzca un ciclo.

4. Uno de los vertices i, j, digamos j, fue conectado previamente a la fuente y el otrovertice i es un jugador que no estaba todavıa conectado a la fuente. Asignamos el costeβR

i (T ) = t(e) al agente i.

5. Unimos e a R.

6. Si no estan todos los vertices conectados a la raız en el grafo (N∗, R), volver al paso 3.

El siguiente ejemplo sirve para ilustrar la regla.

Ejemplo 3.2 Consideremos el problema de mınima union T con N = {1, 2, 3} como sepresenta en la figura 9, donde los numeros sobre las aristas representan los costes.

Cuando aplicamos el algoritmo a este problema, la primera arista que unimos a R es{∗, 1} o bien {∗, 3} (son las aristas de mınimo coste que parten de la fuente). Supongamosque elegimos la primera de ellas, entonces el coste βR

1 (T ) = 10. Posteriormente, siguiendo elalgoritmo, anadimos {1, 2} a R, y queda βR

2 (T ) = 6, anadimos {2, 3} a R, y queda βR3 (T ) = 5.

Esto nos lleva al siguiente reparto de costes (10, 6, 5). Por otra parte, si partimos de {∗, 3},obtendrıamos finalmente el reparto de costes βR(T ) = (6, 5, 10).

Los dos arboles de union a mınimo coste (arboles de mınima union) estan representadosen la figura 10.

Es decir, en la primera solucion tenemos que, segun la regla de Bird, el punto 1 ha depagar 10 unidades, el 2 pagara 6 y el tercero 5. Por el contrario, segun la segunda solucion yla regla de Bird, los jugadores habran de pagar 6, 5 y 10 unidades respectivamente.

10

Figura 9: Un problema de arbol de union de coste mınimo T .

4. Aplicacion

Andalucıa es una de las 17 regiones que integran el territorio nacional de Espana. Esta di-vidida en ocho provincias, cada una de ellas con una capital. El mapa geografico de estaComunidad Autonoma, en donde se han senalado con un punto negro la localizacion de susdiferentes capitales, aparece en la figura 11.

Como aplicacion del problema de mınima union presentamos los siguientes casos:

4.1. Caso 1: conexion sin fuente

Supongamos que una empresa de comunicaciones desea conectar las ocho capitales deprovincia andaluzas mediante un cable de fibra optica. Las distancias en kilometros entretodas las capitales vienen dadas en la siguiente tabla:

11

Figura 10: Dos arboles de mınima union.

Almerıa Cadiz Cordoba Granada Huelva Jaen Malaga SevillaAlmerıa 0 484 332 166 516 228 219 422Cadiz 484 0 263 335 219 367 265 125

Cordoba 332 263 0 166 232 104 187 138Granada 166 335 166 0 350 99 129 256Huelva 516 219 232 350 0 336 313 94Jaen 228 367 104 99 336 0 209 242

Malaga 219 265 187 129 313 209 0 219Sevilla 422 125 138 256 94 242 219 0

Construir el mınimo arbol de union para este caso y decidir cuanto ha de pagar cada capitalde provincia para su construccion.

12

Figura 11: Andalucıa.

4.2. Caso 2: conexion con fuente

Supongamos ahora que las ocho capitales han de estar conectadas a una fuente de energıasituada en Malaga capital. Construir en mınimo arbol de union para este caso suponiendoque las distancias entre capitales son las dadas en la tabla anterior y decidir cuanto ha depagar cada capital de provincia, suponiendo que el coste generado en Malaga para construirla fuente es ya suficiente y que esa ciudad no debe pagar nada mas.

4.3. Soluciones

En el primer caso no tenemos ninguna fuente por lo que la primera arista sera la que unalas dos capitales mas cercanas entre sı, en este caso Sevilla y Huelva. Despues uniremos laciudad mas cercana de las seis restantes a una de las que ya tenemos en la red, en este casoCadiz es la mas cercana a una de las dos y esta mas cerca de Sevilla, luego la siguiente aristasera Sevilla-Cadiz. Se procede ası con todas las ciudades y el arbol de mınima union es elformado por:

13

Sevilla, Huelva, 94Sevilla, Cadiz, 125

Sevilla, Cordoba, 138Jaen, Cordoba, 104Jaen, Granada, 99

Malaga, Granada, 129Granada, Almerıa, 166”distancia total”, 855

Para el caso en el que tenemos una fuente predeterminada, logicamente el arbol de mınimaunion es el mismo y tan solo cambia el orden de aparicion de las aristas en el algoritmo:

Malaga, Granada, 129Jaen, Granada, 99Jaen, Cordoba, 104

Sevilla, Cordoba, 138Sevilla, Huelva, 94Sevilla, Cadiz, 125

Granada, Almerıa, 166”distancia total”, 855

El mapa con la conexion de mınimo coste viene descrito en la figura 12 para ambos casos.

4.4. Reparto de costes

En el ejemplo uno, supongamos que cada kilometro de la red ha costado 10000 Euros y queel coste de dicha red ha de correr a cargo de las diferentes capitales. ¿Cuanto debe pagar cadauna de ellas en el caso 1?

En el ejemplo dos, si suponemos que Malaga ha invertido dinero en la construccion dela planta que abastecera al resto de capitales y que, por tanto, no debe pagar nada de laconstruccion de la red, ¿cuanto ha de pagar cada una de las restantes capitales si la redcosto 10000 Euros el kilometro?

14

Figura 12: Arbol de mınima union.

4.5. Reparto tras la conexion sin fuente

En el primer caso, debido a que no tenemos fuente, no podemos aplicar la regla de Bird.Se pueden proponer muchas reglas de reparto. Nosotros aplicamos las siguientes:

Reparto proporcional: Dividimos el coste total (8550000 Euros) entre el numero deciudades conectadas por la red (8). Cada ciudad paga lo mismo, (1068750 Euros).

Cada ciudad paga la mitad de las conexiones en las que intervenga, por ejemplo, laconexion Sevilla - Huelva correra a cargo de ambas ciudades por igual.

4.6. Reparto tras la conexion con fuente

En el segundo caso si tenemos una fuente predeterminada, Malaga, por lo que podemosaplicar la regla de Bird. Antes veremos como funciona el reparto proporcional y los problemasque origina. Para terminar propondremos un tercer sistema de reparto.

15

Reparto proporcional.

El coste total de la red ascendio a 8550000 Euros, por lo que cada una de las sieteciudades conectadas a Malaga tiene que pagar 8550000

7= 1221428,6 Euros. ¿Es esto

justo?

Veamos que pasa si Granada y Jaen deciden hacer la red por su cuenta, es decir, decidenaliarse y construir una red que las conecte solo a ellas. Aplicando el algoritmo delminimum spanning tree como antes, llegarıamos a que la conexion mas corta para ambasciudades y Malaga tiene un total de 129 + 99 kilometros, es decir, un coste de 2280000Euros. Si ambas ciudades tienen que someterse al reparto proporcional pagaran entreambas un total de 2442857.2 Euros. Logicamente estas ciudades no estan de acuerdocon repartir el gasto total proporcionalmente, pues ellas por separado pueden construirseuna red que las abastece igualmente por menos dinero.

Este es un ejemplo en el que el reparto proporcional no sera secundado por todos.Si al hacer un reparto encontramos subgrupos de usuarios que por su cuenta puedanconectarse y pagar menos, ese reparto probablemente sera desechado.

En Teorıa de Juegos los repartos que cumplen esa condicion, i.e., aquellos en los que nohay ningun subgrupo que actuando por su cuenta salga ganando, se dice que pertenecena un conjunto denominado core.

Veamos ahora la Regla de Bird.

Cada ciudad pagara:

Granada 1290000 Euros.

Jaen 990000 Euros.

Cordoba 1040000 Euros.

Sevilla 1380000 Euros.

Huelva 940000 Euros.

Cadiz 1250000 Euros.

Almerıa 1660000 Euros.

(Cada ciudad paga el coste de la arista que la conecta a la red).

Se puede comprobar que tras este reparto no hay subgrupo de ciudades que salganganando si actuan por su cuenta, es decir, en Teorıa de Juegos dirıamos que este repartopertenece al core.

Esta demostrado que en todo problema de conexion con mınimo coste (minimum span-ning tree) la regla de Bird proporciona un reparto que pertenece al core.

16

Para terminar presentaremos otro tipo de repartos utilizado en problemas de conexion.Un reparto en el que cada ciudad pagara la parte proporcional de las aristas que utilice(si una arista es utilizada por varias ciudades, pagan el coste de dicha arista entre todaslas que la usen). Veamos como funciona este reparto:

La arista Malaga-Granada es utilizada por todas las ciudades, ası que dividen su coste(1290000 Euros) entre siete.

La arista Granada-Almerıa solo es utilizada por Almerıa, luego ella correra con todoslos gastos (1660000 Euros).

La arista Granada-Jaen es utilizada por: Jaen, Cordoba, Sevilla, Cadiz y Huelva. Ası ca-da una pagara 990000

5Euros.

La arista Jaen-Cordoba es empleada para conectarse a la fuente por Cordoba, Sevilla,Cadiz y Huelva. Ası cada una de estas ciudades pagara 1040000

4Euros.

La conexion Cordoba-Sevilla es utilizada por Sevilla, Cadiz y Huelva, por lo que cadauna de ellas pagara 1380000

3Euros.

La conexion Sevilla-Cadiz solo es utilizada por Cadiz, por lo que correra con todos losgastos de esta arista (1250000 Euros).

Por ultimo, la conexion Sevilla-Huelva solo es utilizada por Huelva, por lo que pagara los940000 Euros de su construccion.

Ası el gasto de cada una de las ciudades es:

Granada: 184285.7

Almerıa: 184285.7 + 1660000 = 1844285.7

Jaen: 184285.7 + 198000 = 382285.7

Cordoba: 184285.7 + 198000 + 260000 = 642285.7

Sevilla: 184285.7 + 198000 + 260000 + 460000 = 1102285.7

Cadiz: 184285.7 + 198000 + 260000 + 460000 + 1250000 = 2352285.7

Huelva: 184285.7 + 198000 + 260000 + 460000 + 940000 = 2042285.7

Aunque este reparto parece justo no pertenece al core, ya que si Sevilla, Cadiz y Huelvadeciden construir una red para ellas tres los costes serıan 2190000 (Sevilla-Malaga) +940000 (Sevilla-Huelva) +1250000 (Sevilla-Cadiz), lo que asciende a un total de 4380000Euros, inferior a los 5496855 Euros que pagan entre las tres tras el reparto descrito antes.

Es decir, este reparto no cumple condiciones de justicia suficientes para que se de y, portanto, probablemente no se llevara a cabo.

17

5. El problema del pago de un ascensor en una comu-

nidad de vecinos

Aun existen edificios en los que no hay ascensor y los vecinos quieren ponerlo. En estoscasos surge la polemica de como pagar el ascensor. Como vimos antes el reparto proporcionalpuede dar lugar a situaciones en las que un grupo de usuarios decida actuar por su cuenta sincontar con los demas, ya que aunque el gasto total se vera incrementado el suyo en particularva a ser menor. Veamos el siguiente caso:

En un bloque de cinco plantas, con un piso en cada planta, se quiere instalar un ascensor.La empresa encargada de la instalacion del ascensor tiene un precio de instalacion fijo segunel numero de plantas. Debido a problemas tecnicos el coste de la conexion entre dos plantasincrementa segun su altura, es decir, costara mas construir el hueco de ascensor entre la sextay la septima planta que entre la primera y la segunda. Los precios fijos segun la altura delascensor vienen reflejados en la siguiente tabla:

No de Plantas Coste del ascensor1 100002 210003 330004 460005 60000

El esquema del ascensor es el siguiente:En la comunidad de vecinos se propuso pagar el ascensor entre todos los vecinos a partes

iguales, es decir, 10800 euros cada uno. ¿Es este reparto de costes ”justo”? ¿Como repartirıaslos gastos del ascensor entre todos los vecinos?

5.1. Reparto de costes

Veremos las tres reglas de reparto de antes aplicadas a la nueva situacion.

1. El reparto proporcional dice que cada vecino ha de pagar 10800 Euros por el ascensor.Pero, ¿es esto justo? Si el vecino del primer piso quisiera construir un ascensor para elsolo tendrıa que pagar menos (10000 Euros), por lo que no querra formar parte de laconstruccion conjunta del ascensor.

18

Figura 13: Esquema del ascensor.

2. La regla de Bird, que como sabemos es un reparto tras el que ningun subgrupo devecinos podra construir un ascensor para ellos por menos dinero, en este caso dice que:

El vecino del primero paga 10000, el del segundo 11000, el del tercero 12000, el delcuarto 13000 y el del quinto 14000. Este reparto es un elemento del core, ningun grupode vecinos podra construir un ascensor sin contar con los demas y a menor coste.

3. Se propone la siguiente regla de reparto: cada vecino pagara por la cantidad de tramosque el ascensor ha de recorrer hasta llegar a su planta, es decir, el vecino del tercerpiso pagara por el primer tramo, el segundo y el tercero. En este caso lo que paga cadavecino es:

El primer tramo cuesta 10000 Euros y sera pagado entre los cinco vecinos, pues lousan todos (10000

5= 2000 Euros).

Pagan el segundo tramo los vecinos desde el segundo hasta el quinto, (110004

= 2750Euros).

El tercer tramo tiene un coste de 12000, que pagan los tres ultimos vecinos, (120003

=4000 Euros).

El tramo entre el tercer y el cuarto piso cuesta 13000 es pagado a medias entre losvecinos del cuarto y el quito piso, (13000

2= 6500 Euros).

El tramo entre el cuarto y el quinto piso es pagado por el vecino del quinto, elunico que lo utiliza, (14000

1= 14000 Euros).

19

Por tanto, el vector de pagos es:

(2000, 4750, 8750, 15250, 29250),

donde el vecino del i-esimo piso pagara la componente i-esima del vector anterior.

Aunque es un reparto que pertenece al core, parece exagerado que el vecino del quintopiso pague quince veces mas que el del primero.

¿Que opinas sobre la justicia al repartir costes?

20