Pregunta teórica relacionada con la informática y la teoría de juegos
A menudo se cita una justificación filosófica para creer que P! = NP incluso sin pruebas. Otras clases de complejidad tienen evidencia de que son distintas, porque si no, habría consecuencias "sorprendentes" (como el colapso de la jerarquía polinómica). Mi pregunta es, ¿cuál es la base para creer...
Decidir si una fórmula booleana cuantificada como ∀ x1∃ x2∀ x3⋯ ∃ xnorteφ ( x1, x2, ... , xnorte) ,∀X1∃X2∀X3⋯∃Xnorteφ(X1,X2,...,Xnorte),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), siempre se evalúa como verdadero es un problema clásico completo de PSPACE....
Estaba (y todavía estoy) realmente interesado en la respuesta a esta pregunta, porque esta es una variación interesante sobre la complejidad de los juegos que no se ha resuelto, así que ofrecí una recompensa. Pensé que la pregunta original era muy difícil, así que publiqué tres preguntas...
Los últimos meses comencé a darme conferencias sobre la elección social, el teorema de la flecha y los resultados relacionados. Después de leer sobre los resultados seminales, me pregunté qué sucede con las preferencias de orden parcial, la respuesta está en el documento de Pini et al. : Agregando...
Esta es una reformulación de una pregunta anterior . Considere el siguiente juego imparcial de información perfecta entre dos jugadores, Alice y Bob. Los jugadores reciben una permutación de los enteros 1 a n. En cada turno, si la permutación actual aumenta, el jugador actual pierde y el otro...
Esta reciente pregunta de teoría de juegos me hizo pensar (esto es una tangente, por supuesto): ¿es posible optimizar eficientemente una estrategia personal para elegir preguntas de investigación para trabajar en el uso de la teoría de juegos? Para avanzar hacia una formalización de la pregunta,...
Mafia es un popular juego de rol en fiestas, una descripción detallada está disponible en wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Básicamente, funciona de la siguiente manera: Al principio, a cada uno de los jugadores se le asigna un rol en secreto, ya sea alineado con la mafia...
Estoy buscando ejemplos de técnicas para probar el precio de los límites de la anarquía que tienen el poder de separar el precio de la anarquía sobre equilibrios correlacionados gruesos (el conjunto limitante de la dinámica sin arrepentimiento externo) del precio de la anarquía sobre los...
Uso el término del título en un sentido muy laxo. Hay una gran cantidad de trabajo sobre la teoría de los juegos evolutivos, incluidos sus fundamentos matemáticos. Me recomendaron "Juegos evolutivos y dinámica de población", pero aún no he profundizado en ello. También hay una gran cantidad de...
Un juego popular en las fiestas navideñas en América del Norte es el intercambio de regalos de elefante blanco . En resumen (ignorando las variaciones) funciona de la siguiente manera: Hay personas y n regalos envueltos. Los jugadores son ordenados arbitrariamente. En el i ª ronda, el jugador que...
¿Qué tipo de conjeturas y principales problemas abiertos son los más importantes en la teoría algorítmica de juegos (o la teoría de juegos en general en lo que se refiere a CS)? Por ejemplo, la resolución de NASH como PPAD completo, creo, habría sido la más grande hasta que se resolvió. (Agregado:...
Como estudiante de informática, me presentaron la teoría de juegos, pero no vi muchos detalles sobre el tema. Busqué en Google, miré algunos libros sobre teoría de juegos y me confirmaron su uso en informática. He comenzado un estudio formal de la teoría de juegos desde la perspectiva del...
Me pregunto si hay una versión computacionalmente limitada del concepto de equilibrio de Nash, algo en las siguientes líneas. Imagine algún tipo de juego de información perfecta para dos jugadores que se juega en un tablero , y que es complejo en el sentido de que el juego óptimo es EXPTIME....
Encontré el siguiente juego. Migraré esto según lo solicitado. Un error es visitar círculos, y un adversario desea maximizar su tiempo de viaje. El adversario coloca un círculo en cada turno. El error camina desde su posición actual directamente hacia el centro del círculo más nuevo, luego se...
Considere el siguiente juego en un gráfico ponderado dirigido con una ficha en algún nodo.GGG Todos los nodos de están marcados por A o B.GGG Hay dos jugadores, Alice y Bob. El objetivo de Alice (Bob) es cambiar el chip a un nodo marcado por A (B). Inicialmente, Alice y Bob tienen y dólares...
Dado un juego determinista de suma cero de información parcial con solo un número finito de estados, cuyos posibles resultados son [perder, empatar, ganar] con valores [-1,0, + 1] respectivamente, ¿cuál es la complejidad de aproximar el valor de tales un juego aditivamente dentro de...
Hay una muy buena construcción por Conway de números surrealistas. Son "números" que contienen números reales y ordinales, están totalmente ordenados y tienen todas las propiedades de un campo (excepto que no forman un conjunto sino una clase). Vea, por ejemplo, este pdf o Wikipedia para una...
Para un problema de búsqueda local polinómica , sabemos que debe existir al menos una solución (óptimo local). Sin embargo, podrían existir muchas más soluciones, ¿qué tan difícil es contar la cantidad de soluciones para un problema PLS completo? Estoy particularmente interesado en el problema de...
Estoy comenzando mis estudios de teoría algorítmica de juegos, y parece que el concepto de equilibrio que generalmente se toma es el de un punto fijo en un gráfico. Sin embargo, ¿la gente ha analizado conceptos de equilibrio alternativos, como los ciclos límite? Me imagino que un ciclo límite...
Como mencionó @Marzio, el siguiente juego se conoce como Geografía Generalizada . Dado un gráfico y un vértice inicial , el juego se define de la siguiente manera:v ∈ VG = ( V, E)sol=(V,mi)G=(V,E)v ∈ Vv∈Vv \in V En cada turno (dos jugadores alternando), un jugador elige u ∈ N( v )tu∈norte(v)u\in...