Un juego de teoría que demuestra la resistencia óptima de las coloraciones a desviaciones fuertes
Autores: Madeo, Dario; Mocenni, Chiara; Palma, Giulia; Rinaldi, Simone
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un juego de teoría que demuestra la resistencia óptima de las coloraciones a desviaciones fuertes
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Conjetura
Coloraciones óptimas
Juegos de max-cut
Grafos no ponderados
Grafos no dirigidos
Teoría de juegos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 20
Citaciones: Sin citaciones
Este documento proporciona una prueba formal de la conjetura que establece que las coloraciones óptimas en juegos de corte máximo sobre grafos no ponderados y no dirigidos no permiten la formación de ninguna coalición fuertemente divergente, es decir, un subconjunto de nodos capaz de aumentar sus propias ganancias simultáneamente. El resultado se obtiene mediante un nuevo método fundamentado en la teoría de juegos, que consiste en dividir los nodos del grafo en tres subconjuntos: la coalición en sí misma, el límite de la coalición y los nodos sin relación con la coalición. Además, encontramos resultados adicionales relacionados con las propiedades de las coloraciones óptimas.
Descripción
Este documento proporciona una prueba formal de la conjetura que establece que las coloraciones óptimas en juegos de corte máximo sobre grafos no ponderados y no dirigidos no permiten la formación de ninguna coalición fuertemente divergente, es decir, un subconjunto de nodos capaz de aumentar sus propias ganancias simultáneamente. El resultado se obtiene mediante un nuevo método fundamentado en la teoría de juegos, que consiste en dividir los nodos del grafo en tres subconjuntos: la coalición en sí misma, el límite de la coalición y los nodos sin relación con la coalición. Además, encontramos resultados adicionales relacionados con las propiedades de las coloraciones óptimas.