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, haré los siguientes supuestos (declarados informalmente):
- Igualmente "disfruto" cualquier problema particular disponible para que yo pueda trabajar (para evitar la respuesta "suave" (¡y correcta!) De "¡Haz lo que quieras!").
- Puedo o no tener éxito en encontrar una respuesta a cualquier problema en el que decida trabajar. Para cualquier problema, tengo una estimación de la probabilidad de cuán bueno seré para resolver un problema (después de invertir tiempo en él).
- Mi objetivo es maximizar mi recompensa cuando me evalúan en el futuro (solicitar un trabajo, solicitar la tenencia, solicitar una beca, etc.), que es una función de cuántos problemas resuelvo y cuán importantes o difíciles son los problemas . No tengo una idea clara de los pagos exactos por problema, pero puedo hacer una estimación razonable.
- Hay una relación inversa floja entre el pago del problema y la dificultad del problema. Otra declaración de mi objetivo es "jugar" las diferencias (es decir, buscar "fruta baja").
- Una instancia de este problema general se especifica mediante una lista de preguntas de investigación (posiblemente infinitas en número), a la que adjunto firmemente (sin costo computacional; se da como entrada) una estimación del valor de la pregunta y la dificultad de la pregunta. Estoy jugando este juego contra un adversario (la persona que me evalúa); la naturaleza decide, dada la probabilidad de que resuelva un problema dado, si lo resuelvo con éxito después de elegir intentarlo.
En un esfuerzo por formalizar realmente lo que está sucediendo (y eludir las respuestas poco interesantes o argumentativas / de tipo debate), veré este problema como un juego de forma extensa con información incompleta con un conjunto de acciones infinito .
Pregunta : Supongo que los juegos de este tipo no son computables de manera eficiente. Sin embargo, ¿existe un algoritmo de tiempo polinómico para maximizar aproximadamente mi recompensa? ¿Qué pasa con un PTAS?
O, alternativamente, ¿hay un modelo teórico de juego más preciso para este problema? Si es así, la misma pregunta es válida: ¿puedo (aproximadamente) maximizar mi pago de manera eficiente? ¿Si es así, cómo?
fuente
Respuestas:
Voy a tratar de responder su pregunta proponiendo un modelo alternativo para la pregunta. Normalmente hago más preguntas de las que respondo aquí, así que espero que me perdones si mi respuesta no es óptima, aunque estoy haciendo mi mejor esfuerzo.
Creo que la forma de formular la pregunta que sería óptima para permitir que la teoría de juegos sea útil sería asumir un escenario más competitivo. Es decir, debe haber competencia entre una variedad de actores diferentes. Entonces, asumiría lo siguiente:
Ahora, suponiendo que no sea posible la cooperación en ningún problema, considere lo que voy a referir como un "juego iterativo dinámico". Este es un juego que se juega repetidamente, pero que cambia ligeramente cada vez que se juega.
Sea M el número de movimientos o turnos en el juego. La manifestación inicial del juego podría representarse como una lista que contiene cada actor (investigador) y cada problema en el que podrían trabajar, además de todos los valores asociados con cada actor y cada problema que enumeré anteriormente. (Supongo, por supuesto, que cada investigador sabe todo lo que se sabe actualmente sobre todos los problemas, y sobre todos los demás investigadores, haciendo de este un juego de información perfecta).
Durante cada iteración del juego, un actor determinado elige una pregunta de investigación para trabajar. A cada actor se le permite cambiar las preguntas en cualquier momento, y si se resuelve un problema, el beneficio para la carrera U se reduce a 0 para todos los demás jugadores. Si un jugador invierte suficiente tiempo y no resuelve el problema, entonces ese jugador en particular tiene prohibido intentar resolver ese problema nuevamente ... aunque cualquier otro jugador puede continuar trabajando en el problema, y otro actor puede resolverlo. con éxito El juego termina después de que se hayan tomado todos los turnos M.
Cada turno en el que un investigador haya seleccionado un problema hará que ese jugador se acerque más a alcanzar el "momento de la verdad" y posiblemente a resolver el problema, si la Naturaleza lo permite. Un problema, una vez resuelto, agrega un cierto beneficio a la carrera del investigador basado en l . El talento de investigación amplifica la probabilidad de éxito, mientras que el tiempo libre amplifica la capacidad de progresar en un turno dado.
Dudo que haya algún algoritmo de tiempo polinómico para resolver esto; No veo ninguna razón por la cual los investigadores deberían limitarse a jugar equilibrios de Nash de estrategia pura, por lo que el problema implicaría equilibrios de Nash de estrategia mixta y, por lo tanto, en el peor de los casos, PPAD completo, si considera que "resolver el problema" significa "encontrar un Nash equilibrio para el problema ". (Uno podría imaginar que si usted es el investigador más proactivo, podría seguir adelante y calcular su equilibrio de Nash favorito y luego señalarlo a todos los demás jugadores ... lo que le da cierta confianza de que nadie cambiará las estrategias de la estrategia perfil que ha señalado).
En cualquier caso, esta es la respuesta más complicada que he publicado. Espero que sea de al menos algún valor. Avíseme si alguien tiene alguna respuesta o recomendaciones para mejorarla.
fuente