Estrategias óptimas de coloración para el juego Max-Cut
Autores: Garuglieri, Andrea; Madeo, Dario; Mocenni, Chiara; Palma, Giulia; Rinaldi, Simone
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Estrategias óptimas de coloración para el juego Max-Cut
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Explorar
Equilibrios de Nash
Juego de corte máximo
Equilibrios fuertes
Vértices
Color
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Exploramos los equilibrios de Nash fuertes en el juego de corte máximo en un grafo no dirigido y no ponderado con un conjunto de colores. Aquí, los vértices representan a los jugadores y las aristas denotan sus relaciones. Cada jugador selecciona un color como su estrategia, y su pago (o utilidad) se determina por el número de vecinos que han elegido un color diferente. Existen hallazgos limitados sobre la existencia de equilibrios fuertes en juegos de corte máximo. En este documento, avanzamos en la comprensión de las características de los equilibrios fuertes. Específicamente, nuestro resultado principal demuestra que las soluciones óptimas son equilibrios siete-robustos. Esto implica que para que una coalición de vértices desvíe y cambie el sistema a una configuración diferente, es decir, una coloración diferente, se necesita un número de vértices de la coalición mayor que siete. Luego, establecemos algunas propiedades de los subconjuntos mínimos con respecto a una desviación robusta, revelando que cada vértice dentro de estos subconjuntos se desviará hacia el color de uno de sus vecinos.
Descripción
Exploramos los equilibrios de Nash fuertes en el juego de corte máximo en un grafo no dirigido y no ponderado con un conjunto de colores. Aquí, los vértices representan a los jugadores y las aristas denotan sus relaciones. Cada jugador selecciona un color como su estrategia, y su pago (o utilidad) se determina por el número de vecinos que han elegido un color diferente. Existen hallazgos limitados sobre la existencia de equilibrios fuertes en juegos de corte máximo. En este documento, avanzamos en la comprensión de las características de los equilibrios fuertes. Específicamente, nuestro resultado principal demuestra que las soluciones óptimas son equilibrios siete-robustos. Esto implica que para que una coalición de vértices desvíe y cambie el sistema a una configuración diferente, es decir, una coloración diferente, se necesita un número de vértices de la coalición mayor que siete. Luego, establecemos algunas propiedades de los subconjuntos mínimos con respecto a una desviación robusta, revelando que cada vértice dentro de estos subconjuntos se desviará hacia el color de uno de sus vecinos.