Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/1546| Mecanismos acíclicos para problemas de reparto de costos en juegos cooperativos Acyclic mechanims for cost sharing problems in coopetative games | |
| JOSÉ DOMINGO COLBES SANABRIA | |
| CARLOS ALBERTO BRIZUELA RODRIGUEZ Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Algoritmos de aproximación,Problemas de reparto de costos,Mecanismos acíclicos,Mecanismos incrementales,Diseño de una red compra-alquiler,Juegos cooperativos | |
| El análisis y diseño de algoritmos para teoría de juegos se ha convertido en un áreade gran relevancia en los últimos años, esto motivado principalmente por el auge deInternet y los problemas que naturalmente surgen del mismo. Una parte fundamentalen esta área es la que trata acerca de los juegos cooperativos en problemas de repartode costos. Existen ciertos requerimientos que deben ser cumplidos por los mecanismosdiseñados, y uno de ellos consiste en encontrar una solución óptima para el problemacombinatorio subyacente, considerando el conjunto de usuarios que reciben el servicio.Además de encontrar esta solución óptima, se debe decidir el monto a cobrar a cadausuario de tal modo a recuperar la inversión (equilibrio de presupuesto) y de tal modoa evitar que los usuarios se vean tentados a mentir sobre su ingreso para conseguir quese les cobre menos por el servicio (a prueba de estrategias de grupo). Un ejemplo es elproblema de reparto de costos en el diseño de una red de compra-alquiler de una solafuente (SSROB-CS). El mismo consiste en encontrar un árbol de costo mínimo dondeexista un camino desde un vértice fuente a un subconjunto de vértices del grafo querepresentan a los usuarios, considerando que las aristas del grafo pueden ser compradaso alquiladas. Luego, se debe repartir el costo de este árbol entre los usuarios. Comoel problema combinatorio subyacente pertenece a la clase NP-difícil, y si P 6= NP, elmismo sólo puede ser resuelto con cierto grado de aproximación. El mejor factor deaproximación del equilibrio del presupuesto para este problema es de 4.6, el cual estádado por un mecanismo de Moulin.Recientemente se han propuesto los mecanismos acíclicos, los cuales generalizan losmecanismos de Moulin que tradicionalmente se utilizan para los problemas de reparto decostos. Un caso especial de los acíclicos lo constituyen los mecanismos incrementales, loscuales permiten utilizar algoritmos combinatorios ya existentes para transformarlos enmecanismos de reparto de costos, heredando el factor de aproximación de los mismos. Se ha demostrado que para ciertos problemas de reparto de costos los mecanismosincrementales y los acíclicos básicos obtienen mejores resultados que los mecanismos deMoulin.En este trabajo se analiza la aplicación del algoritmo primal-dual propuesto porSwamy y Kumar (2004) (cuyo factor de aproximación es de 4.55) en un mecanismoacíclico básico y en uno incremental. Se demuestra que este algoritmo de aproximaciónno puede aplicarse a estos tipos de mecanismos.A partir de este resultado, se propone un mecanismo incremental con un factorde aproximación esperado de 4 en el equilibrio del presupuesto a partir del algoritmoaleatorio de Gupta et al. (2003). También se propone otro mecanismo incremental queutiliza el algoritmo combinatorio de Gupta et al. (2008), el cual es aplicado en el mecanismode Moulin que da, a la fecha, el mejor resultado para el problema considerado.Aunque no se pudo demostrar teóricamente la factibilidad de su aplicación, resultadosexperimentales sobre casos de prueba generados aleatoriamente motivan a conjeturarque este algoritmo es aplicable en un mecanismo incremental para cualquier caso delproblema.Por último, se realizan experimentos para analizar el beneficio que reciben los usuarios(costo social) cuando se aplica el último mecanismo incremental propuesto yel mejor mecanismo para este problema de reparto de costos, obteniéndose resultadosdiferenciados. Cuando los ingresos de los jugadores son altos, no existen diferenciassignificativas entre ambos mecanismos; pero a medida que los mismos van decreciendo,el mecanismo de Moulin obtiene mejores resultados. The algorithmic game theory has attracted the attention of many researchers in thelast few years, largely motivated by the emergence of the Internet and the problemsthat naturally arise from it. An essential part of this line of research is the mechanismdesign for cost-sharing problems in cooperative games. There are some requirements tobe fulfilled by the designed mechanisms, and one of them is to find an optimal solutionto the underlying optimization problem considering the users to be served. Besidesfinding the optimal solution the mechanism should decide how to share the cost amongthe users in order to recover the service cost (budget balance). It also should motivateeach player to reveal his true value, even if any group of them collude (group strategyproof).An example is the design of a mechanism for the single source rent-or-buycost-sharing problem (SSROB-CS). This problem consists in finding a minimum-costtree connecting a subset of vertices (representing the users) to the source, consideringthe fact that an edge can be rented or bought. Then, the cost-share of each user must becalculated to recover the cost of the tree. Since the underlying combinatorial problem isNP-hard, only approximations to the optimum can be guaranteed. The best up-to-datebudget-balance approximation factor for this problem is 4.6, with a Moulin mechanism.Recently, acyclic mechanisms have been proposed by Mehta et al. (2007). Thisclass of mechanism strictly generalizes Moulin mechanisms that are traditionally usedfor cost-sharing problems. A special case of acyclic mechanisms is the incrementalapproach, which allows the use of approximation algorithms for the underlying combinatorialproblem to turn them into cost-sharing mechanisms, preserving their approximationfactors. It has been demonstrated that the basic acyclic and the incrementalmechanisms outperform Moulin mechanisms for certain classes of cost-sharing problems.In this work we analyze the application of the primal-dual algoritm proposed bySwamy and Kumar (2004) (whose approximation factor is 4.55) to both, basic acyclicand incremental mechanisms, showing that this algorithm is not suitable for thesemechanisms.From this result, we propose an incremental mechanism with an (expected) approximationfactor of 4 in budget-balance from the randomized algorithm proposed byGupta et al. (2003). Also, we propose another incremental mechanism using the combinatorialalgorithm of Gupta et al. (2008), which is applied to the Moulin mechanismthat gives the best up-to-date result for this cost-sharing problem. Although we couldnot demonstrate the feasibility of its application, experimental results on randomlyivgenerated instances lead to the conjecture that this algorithm can be applied to anincremental mechanism for any instance of the problem.Finally, we compare the performance of the proposed incremental mechanism withthat of the best known mechanism for this problem, regarding the social cost. Theresults show that when the mechanism achieves a high participation, then both mechanismsperform similarly. However, when there is a low participation the Moulin mechanismoutperforms the proposed approach. | |
| CICESE | |
| 2011 | |
| Tesis de maestría | |
| Español | |
| Colbes Sanabria,J.D.2011.Mecanismos acíclicos para problemas de reparto de costos en juegos cooperativos.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xiv, 163pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 187511.pdf | Versión completa de la tesis | 11.24 MB | Adobe PDF | Visualizar/Abrir |