Tesis
|
Estévez-Fernández, A. (2006) "Cooperative behavior, competition and
operations research", PhD thesis, Tilburg University, The Netherlands.
(Resumen)
(CentER Ph.D. Thesis Series)
|
Teoría de juegos es una herramienta matemática
para estudiar cooperación ycompetición. Desde los inicios de la investigación operativa y la teoría de
juegos ambos campos has estado estrechamente relacionados. Esta tesis investiga esta relación. Problemas
de reparto de costes o beneficios que surgen de poblemas de secuanciación,
problemas del viajante y diseño de marco de la teoría de juegos.
Refinamientos del conjunto de soluciones óptimas de problemas de programación
lineal son estudiados mediante el uso de la relación entre problemas de
programación lineal, problemas de complementariedad lineal y juegos
matriciales. Finalmente, analizamos ámbitos competitivos, es decir juegos bimatriciales que satisfacen algunas propiedades interesantes de los
juegos matriciales. |
|
|
Publicaciones
-
Lazarova, E., Borm, P., and Estévez-Fernández, A.
(2016) "Transfers and exchange-stability in two-sided matching problems" Theory and Decision 81, 53-71.
(Resumen) (Antes TI 2014-086/II)
|
En este trabajo consideramos problemas de emparejamiento
de uno-a-varios donde las preferencias de los agentes implicados
están representados por funciones de beneficios (en términos
monetarios). Caracterizamos emparejamientos Pareto óptimos
mediante intercambios contractualmente estables y emparejamientos de
máximo beneficio total por medio de intercambio de compensación
estable. Para concluir, demostramos que al pasar de un emparejamiento
inicial a un emparejamiento de máximo beneficio total, siempre
se puede obtener un esquema de compensación que será
estable a posteriori en el sentido de que no habrá ningún
subconjunto de agentes que puedan obtener una mayor recompensa al
desviarse del emparejamiento elegido. La demostración de este
resultado utiliza el hecho de que el core de un juego de compensación
con restricciones asociado es no vacío |
|
-
Sánchez, E., Borm, P., Estévez-Fernández, A., Fiestras-Janeiro, and M.G., Mosquera, M.A.
(2015) "k-core covers and the core", Mathematical Methods of Operations Research
81, 147-167.
(Resumen)
(Antes TI 2013-177/II )
|
Este trabajo En este trabajo se extiende el concepto de
derecho mínimo individual para un juego de utilidad transferible ( juego-UT) al derecho
mínimo de una coalición utilizando familias minimales equilibradas de un tipo
específico, definiendo así un juego de derechos mínimos correspondiente. Se
muestra que el núcleo de un juego-UT coincide con el núcleo del correspondiente
juego de derechos mínimos. Además, el documento introduce el concepto de
k-core cover como una extension del core cover. El "k-core cover de un
juego-UT consta de todos los vectores de pago eficientes para los que el pago total de cualquier
coalición de tamaño menor o igual a k es acotado superiormente por el
valor del juego de utopia para esa coalición e inferiormente por el valor del juego de
derechos mínimos para esa coalición. También se demuestra que el núcleo
de un juego-UT con conjunto de jugadores N coincide con el ⌊|N|/2⌋-core
cover. Además, se dan caracterizaciones completas de los juegos para los que el
k-core cover es no vacío y para los que el k-core cover coincide
con el núcleo. |
|
-
Van den Brink, R., Estévez-Fernández, A., van der Laan, G., and Moes, N. (2014) "Independence of downstream and upstream benefits in river water allocation problems",
Social Choice and Welfare 43, 173-194.
(Resumen)
(Antes TI 2011-128/1)
|
En este trabajo estudiamos el problema de distribución del agua de un río entre los agentes ubicados a lo largo de este.
Cada agente tiene preferencias cuasi-lineales sobre el agua del río y dinero, y el beneficio que se obtiene por el consumo
de una cantidad determinada de agua es dado por una función de beneficio continua y cóncava. Una solución para
el problema distribuye de manera eficiente el agua del río entre los agentes y no malgasta dinero. Se introduce un
número de axiomas (de independencia) para caracterizar dos soluciones nuevas y dos ya existentes. Aplicamos las soluciones
para el caso particular en el que cada agente tiene un beneficio marginal constante igual a uno hasta un punto de saciedad y un
beneficio marginal igual a cero a partir de entonces. En este caso nos encontramos con que dos de las soluciones
(una existente y otra nueva) pueden llevarse a cabo sin transferencias monetarias entre los agentes. |
|
-
Estévez-Fernández, A. and Reijnierse, H. (2014) "On the core of cost-revenue games: minimum cost spanning tree games with revenues",
European Journal of Operational Research 237, 606-616.
(Resumen)
(Antes TI 12-101/II)
|
En este trabajo, se analizan los problemas de costes que se deriven de un servicio general
donde tomamos explícitamente en cuenta los ingresos generados. A este problema de costes-ingresos, asociamos un juego
cooperativo con utilidad transferible, llamado juegos de costes-ingresos. Al considerar la cooperación entre los agentes que
utilizan el servicio general, el valor de una coalición se define como la utilidad neta máxima que la coalición
puede obtener por medio de cooperación. Como resultado, una coalición pueden beneficiarse de no permitir que todos sus
miembros obtengan el servicio que genera los ingresos. Nos centramos en el estudio del core de juegos de costes-ingresos. Bajo el
supuesto de que cooperación entre los miembros de la gran coalición garantiza el uso del servicio en consideración
a todos sus miembros, se demuestra que un juego de costes-ingresos tiene un núcleo no vacío para cualquier vector de
ingresos si, y sólo si, el juego dual del juego de costes tiene un núcleo grande. Con este resultado, se investigan problemas de
"minimum cost spanning tree" con ingresos. Se demuestra que si todos los costes de conexión sólo pueden tomar dos
valores (coste bajo o alto), entonces, el juego de "minimum cost spanning tree" con ingresos correspondiente tiene un core
no vacío. Además, ofrecemos un ejemplo de un juego de "minimum cost spanning tree" con los ingresos con un core
vacío en el que cada coste de conexión sólo puede tomar uno de tres posibles valores (coste bajo, medio o alto). |
|
-
Estévez-Fernández, A., Borm, P., and Hamers, H. (2012) "A note on passepartout problems",
International Game Theory Review 14 (2), 1250013 (9 páginas).
(Resumen)
(Antes TI 2010-031/1 y originalmente
"The museum pass game and its value "revisited"",
CentER DP 2004-07)
|
Esta nota es un estudio
metodológico del reparto de los ingresos obtenidos a partir de un passepartout. En
un sistema de passepartout, un grupo de proveedores de servicios ofrece un paspartout
que permite a sus propietarios el uso de determinados servicios un número
ilimitado de veces durante un período fijo de tiempo. El problema de reparto
correspondiente es cómo repartir adecuadamente los ingresos obtenidos mediante
el sistema de passepartout entre los proveedores de servicios. Se dan argumentos
para modelar el problema del passepartout en el marco de problemas de bancarrota
y se consideran propiedades contextuales con el fin de seleccionar una regla de
reparto adecuada. |
|
-
Estévez-Fernández, A., Fiestras-Janeiro, M.G., Mosquera, M.A., Sánchez, E. (2012)
"A bankruptcy approach to the core cover",
Mathematical Methods of Operations Research 76, 343-359.
(Resumen)
(Antes TI 2012-012/1)
|
En este trabajo se establece una relación entre el core cover de un juego compromiso
admisible y el core de un juego de bancarrota, en particular: el core cover de un juego compromiso admisible es, de hecho, una
traslación del conjunto de asignaciones que son coalicionalmente estables capturado por un juego de quiebra correspondiente. Además,
se analiza la complejidad combinatoria del core cover y, en consecuencia, del core de un juego compromiso estable. |
|
-
Estévez-Fernández, A. (2012) "New characterizations for largeness of the core ", Games and Economic Behavior 76, 160-180.
(Resumen) (Antes
TI 2011-086/1)
|
En este artículo se proponen
tres nuevas caracterizaciones de "largeness of the core". La primera caracterización de
"largeness of the core" se basa en coberturas mínimas de la gran coalición y desigualdades
asociadas. La segunda caracterización muestra la relación entre las bases que proporcionan los puntos extremos del "core" y
las bases que proporcionan los puntos extremos del "core" de los juegos que se obtienen del original,
aumentando el valor de la gran coalición. La tercera caracterización de "largeness of the core" se basa
en la idea de que si una base de la gran coalición no proporciona un elemento del "core" del juego, no
debe proporcionar un elemento del "core" de un juego que difiere del original sólo por un aumento del
valor de la gran coalición. Por medio de estas caracterizaciones, demostramos la equivalencia entre
"largeness of the core" y la estabilidad del "core" para los juegos con un máximo de 5 jugadores y se
revisan algunos resultados sobre "largeness of the core" ya existentes. |
|
-
Estévez-Fernández, A. (2012)
"A game theoretical approach to sharing penalties and rewards in projects",
European Journal of Operational Research 216, 647-657.
(Resumen) (Antes
TI 2009-090/1)
|
Este artículo analiza situaciones en las que
un proyecto que consiste de varias actividades no es ejecutado de acuerdo al plan inicial. Si
el proyecto se adelanta, se produce un beneficio. Análogamente, se cre un coste si el proyecto se
retrasa. Este artículo considera el caso de funciones de beneficio y coste monótonas para el
adelanto y retraso total, respectivamente. Nuestra atención se centra en comodividir el beneficio
(coste) total entre las actividades: el núcleo de un juego de proyecto correspondiente determina
un conjunto de repartos del beneficio (coste) total. In la definición de juegos de proyecto, mecanismos
de reparto de excedentes (costes) son utilizados para tomar en consideración las características
específicas de la función de beneficios (costes) considerada. Resulta que los juegos de proyecto
están relacionados con juegos de bancarrota y de taxación. Esta relación nos permite establecer
que los juegos de proyecto tienen un núcleo no vacío.
|
|
-
Apt, K., Estévez-Fernández, A. (2009)
"Sequential pivotal mechanisms for public project problems ", in:
Algorithmic Game Theory (Eds. Mavronicolas, M. and Papadoupoulou, V.G.), 85-96.
(Resumen)
(Enlace)
|
Es bien sabido que
para varios problemas de decisión no existen mecanismos de
Groves con un presupuesto equilibrado. Esto ha motivado
recientemente una investigación sobre el diseño de
variantes del mecanismo de Groves (denominado como "redistribución
de los pagos VCG (Vickrey-Clarke-Groves)") que generan
reducción de déficit. Con esto en mente, estudiamos el mecanismo
secuencial y consideramos las estrategias óptimas que podrían
reducir el déficit en el marco del mecanismo simultáneo. Mostramos
que tales estrategias existen para el mecanismo fundamental
secuencial del problema del proyecto público. También presentamos
una estrategia óptima con la propiedad de que genera máximo bienestar social
cuando cada jugador la sigue. Por último, demostramos que estas
estrategias pueden ser implementacdas por medio de un equilibrio de Nash.
|
|
-
Borm, P., Estévez-Fernández, A., and Fiestras-Janiero, M.G. (2009)
"Competitive environments and protective behaviour",
Games and Economic Behavior 67, 245-252.
(Resumen) (Antes
CentER DP 2006-43)
|
La clase the juegos competitivos para dos jugadores es
introducida y analizada. Para cualquier juego en esta clase, el conjunto de equilibrios de Nash es
convexo y todos los equilibrios de Nash llevan al mismo vector de pagos. Juegos competitivos son
comparados con otros ámbitos competitivos como juegos unilateralmente competitivos y juegos de rivalidad.
Además, se analiza comportamiento protectivo dentro de
ámbitos competitivos. Es bien sabido que para juegos
matriciales las estrategias protectivas se corresponden con los equilibrios propios. Demostramos que este
resultado se puede extender a juegos unilateralmente competitivos. |
|
-
Estévez-Fernández, A., Borm, P., Meertens, M., and Reijnierse,
H. (2009) "On the core of routing games with revenues",
International Journal of Game Theory 38, 291-304.
(Resumen) (Antes
CentER DP 2006-63)
|
El problema del viajante con beneficios es una
generalización del problema del viajante. Aquí, además de costes de desplazamiento también se
genera un beneficio explícito cada vez que una ciudad es visitada. En este artículo analizamos
problemas de ruta con beneficios, donde una ruta predetermineda para todas las ciudades determina
las rutas para los subgrupos. Analizamos los correspondientes juegos de ruta con beneficios.
Demostramos que estos juegos tienen un núcleo no vacío y damos una descripción de dicho núcleo. |
|
Estévez-Fernández, A., Mosquera. M.A., Borm, P., and Hamers, H. (2008) "Proportionate flow shop games",
Journal of Scheduling 11, 433-447.
(Resumen) (Antes
CentER DP 2006-63)
|
En un problema de flow shop proporcional
(PFS) varios trabajos tienen que ser procesados en una secuencia de máquinas y el tiempo de
procesado de un trabajo es el mismo en cada máquina. Identificando los trabajos con
agentes, cuyos costes dependen linealmente en el tiempo de complección de sus trabajos,
y asumiendo un orden inicial de ejecución de los trabajos, nos enfrentamos a dos problemas:
el primero es como obtener un orden óptimo de procesado que minimice el coste total de
procesado, el segundo es como repartir los ahorros obtenidos tras la ordenación óptima de los
trabajos. En este artículo nos concentramos en el problema de reparto. Asociado a problemas PFS
definimos juegos PFS. Vemos que los juegos PFS tienen un núcleo no vacío. Es más, demostramos
que los juegos PFS son convexos si los trabajos están inicialmente ordenados en sentido decreciente
de sus urgencias. Para esta situación, se da una expresión explícita del valor de Shapley independiente
de los valores coalicionales del juego. |
|
-
Estévez-Fernández, A., Borm, P., Calleja, P., and Hamers, H. (2008) "Sequencing games with repeated players",
Annals of Operations Research 158, 189-203.
(Resumen) (Antes
CentER DP 2004-128)
|
En este artículo consideramos dos clases
de situaciones de secuenciación en una máquina donde cada trabajo pertenece exactamente
a un jugador pero cada jugador puede tener más de un trabajo, los llamados situaciones
de sequenciación con jugadores repetidos (RP). En situaciones de secuenciación max-RP,
se asume que la función de coste de cada jugador es lineal con respecto al tiempo máximo
de complelcción de sus trabajos, mientras que en una situación de secuenciación min-RP
la función de coste de cada jugador es lineal con respecto al tiempo mínimo
de complelcción de sus trabajos. Para ambas clases se proporcionan procedimientos para ir
del orden inicial de procesado al orden óptimo de procesado para la gran coalición y se
definen reglas de reparto igualitario de ganancias. Se demuestra que estas reglas proporcionan
elementos del núcleo de los juegos de secuenciación RP asociados. Además se demuestra que los
juegos de secuenciación min-RP son convexos. |
|
-
Estévez-Fernández, A., Borm, P., and Hamers, H. (2007) "Project games", International Journal of Game Theory 36, 149-176.
(Resumen) (Antes
CentER DP 2005-91)
|
Este artículo estudia situaciones en las que un proyecto
que consiste de varias actividades no es ejecutado de acuerdo al plan inicial. El artículo está
dividido en tres partes. La primera parte analiza el caso en el que las actividades pueden sufrir
retraso, lo cual puede inducir un retraso del proyecto que incurre en costes
adicionales. Se definen juegos de proyecto retrasado y se demuestra que tienen
un núcleo no vacío. La segunda parte considera el caso en el que las actividades
pueden finalizar antes de tiempo, lo cual puede llevar a acabar el proyecto antes
de lo planeado. Se definen juegos de proyecto acelerado y se demuestra que son
convexos. La tercera parte considera el caso en el que alguans actividades se retrasan mientras
otras finalizan. Se definen juegos de proyecto y se demuestra que tienen un núcleo no vacío. |
|
-
Calleja, P., Estévez-Fernández, A., Borm, P., and Hamers, H.
(2006) "Job scheduling, cooperation and control", OR Letters
34, 22-28.
(Resumen) (Antes
CentER DP 2004-65)
|
Este artículo estudia situaciones de secuencialización con una
máquina donde los clientes pueden tener más de un trabajo para ser procesado
y cada trabajo puede ser de interés para varios cllientes. Introducimos juegos cooperativos para
este tipo de situaciones y demostramos que son equilibrados. |
|
-
Estévez-Fernández, A., Borm, P., and Hamers, H. (2006)
"On the core of multiple longest traveling salesman games",
European Journal of Operational Research 174, 1816-1827.
(Resumen) (Antes
CentER DP 2003-127)
|
En este artículo introducimos múltiple juegos del
viajante más largo (MLTS). Un juego MLTS surge de una red en la que un viajante tiene que
visitar cada nodo (jugador) exactamente una vez, con excepción de su lugar de partida, de tal
manera que se maximiza el beneficio total. Primero demostramos que el valor de las coaliciones de
un juego MLTS se puede determinar tomando el máximo de combinaciones adecuadas de coaliciones de
una y dos personas. A continuación se demuestra que los juegos MLTS con cinco o menos jugadores
tienen un núcleo no vacío. Sin embargo, un juego MLTS puede tener un núcleo vacío. Para el caso especial
en el que el beneficio entre dos nodos es igual a 0 ó 1, damos relaciones entre la estructura del núcleo
y la red correspondiente. |
|
-
Estévez-Fernández, A. and Fiestras-Janiero, M.G. (2004)
"On properties of several refinements of optimal solutions in linear
programming", Journal of Optimization Theory and Applications
122, 41-62.
(Resumen)
|
En este artículo investigamos las propiedades
de las soluciones óptimas que obtenemos cuando transcribimos los conceptos de soluciones
perfectas, propias y débilmente propias del contexcto de problemas de complementariedad lineal
al marco de problemas de programación lineal. |
|
|
Trabajos todavía no publicados
-
Dietzenbacher, B., Estévez-Fernández, A., Borm, P., and Hendrickx, R. (2016) "Proportionality,
Equality, and Duality in Bankruptcy Problems with Nontransferable Utility",
CentER Discussion Paper; vol. 2016-026.
(Resumen)
|
En este trabajo se analizan los problemas de bancarota con utilidad intransferible (NTU) como generalización de problemas de bancarrota con un estado monetario y demandas.
Siguiendo la teoría axiomática clásica de bancarrota, formulamos algunas propiedades apropiadas para las reglas de bancarrota NTU
y estudiamos su trascendencia. Exploramos la dualidad de reglas de quiebra y derivamos varias caracterizaciones de la regla proporcional generalizada
y la regla de reparto relativamente igualitaria restringida. |
|
-
Estévez-Fernández, A., Borm, P., Fiestras-Janeiro, M.G., Mosquera, M.A. and Sánchez, E.
(2015) "On the 1-nucleolus for classes of cooperative games",
TI 2015-123/II.
(Resumen)
|
Este trabajo analiza el 1-nucleolo y, en particular,
su relación con el nucleolo y el valor de compromiso. Se ve que el 1-nucleolo de un juego
cooperativo puede ser caracterizado utilizando una combinación de reglas de bancarrota
estándar para los problemas de bancarota asociados. En particular, para cualquier juego
equilibrado cero normalizado, el 1-nucleolo coincide con la regla de Aumann-Maschler (Aumann
y Maschler, 1985) en este sentido. A partir de este resultado, se derivan no sólo
las condiciones necesarias en un juego compromiso estable tal que el 1-nucleolo y el nucleolo
coinciden, sino también condiciones necesarias y suficientes de manera que el 1-nucleolo
y el valor de compromiso coinciden para juegos exactos. |
|
-
Estévez-Fernández, A., Borm, P., and Fiestras-Janeiro
(2014) "Nontransferable utility bankruptcy games",
TI 14-030/II.
(Resumen)
|
En este trabajo, analizamos problemas de bancarrota con
utilidad no transferible (NTU), desde el enfoque de teoría de juegos redefiniendo los
correspondientes juegos NTU de bancarrota en una forma adecuada. Se demuestra que los juegos NTU
de bancarrota son tanto "merge coalitional" convexos y ordinal convexos. Generalizando
las nociones de "core cover" y estabilidad de compromiso para juegos de utilidad
transferible (TU) a juegos NTUs, también demostramos que los juegos NTU de bancarrota son
compromiso estables. Así, los juegos NTU de bancarrota retienen las dos propiedades que
caracterizan a los juegos TU de bancarrota: convexidad y estabilidad de compromise. Como primer
ejemplo de una regla asociada al juego NTU de bancarrota, analizamos la regla proporcional
corregida NTU y demostramos que esta regla se corresponde con el valor de compromiso de los
juegos NTU de bancarrota. |
|
|
Trabajos en progreso
"Chinese postman problems and related games"
(con Marloes Gerichhausen and Herbert Hamers).
"On generalizations of the Talmud rule"
(con Peter Borm).
"Generalization of bankruptcy problems".
|
|
|