logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro