¿Cómo es investigar en teoría de juegos?

Contexto: soy profesor asistente en un departamento de economía (por lo que probablemente tenga una perspectiva algo diferente de la que tendría alguien que hace teoría de juegos, por ejemplo, en un departamento de matemática pura, informática o biología teórica, aunque tengo bastante contacto con el CS comunidad de teoría de juegos). Trabajo en el diseño de mecanismos, que considero como un área de teoría de juegos, aunque algunos podrían estar en desacuerdo.

Respuesta: es fantástico. Hay mucha libertad, pero también una combinación particular de desafíos si quieres hacer un buen trabajo.

Como teórico de juegos, mi trabajo es principalmente mental; Los implementos principales son lápices y papel de borrador. Pienso en esto como liberador en comparación con (digamos) economía empírica o experimental, donde generalmente hay mucho trabajo mecánico o administrativo que hacer, y ciertamente en comparación con las ciencias duras en las que generalmente hay que pasar mucho tiempo en un laboratorio. Significa que no tenemos que preocuparnos por la financiación de equipos, datos o viajes. Significa que es posible ser productivo mientras está en la ducha o paseando por el bosque. También significa que cuando tengo una idea, a menudo es posible escribir un borrador en papel en el espacio de un par de semanas. (¡Por supuesto, tener una idea que valga la pena escribir no sucede con tanta frecuencia!) La otra cara de esto es que el esfuerzo mental puede ser agotador; Muy rara vez puedo trabajar productivamente en un problema durante más de unas pocas horas a la vez.

También me gustaría respaldar el punto de Melissa Dalis acerca de que la teoría de juegos es muy interdisciplinaria. Esto significa que uno se expone a varias formas diferentes de pensar; es genial si disfrutas de la variedad.

En cuanto a los desafíos, es un trabajo mental y requiere habilidades conceptuales y técnicas, pero es una experiencia diferente a, por ejemplo, trabajar en matemática pura muy abstracta. Es un acto de equilibrio, porque si quieres hacer un trabajo influyente tienes que lograr varias cosas a la vez. En primer lugar, debes tener relevancia en el mundo real. Hay una gran cantidad de trabajo abstracto, admirablemente sofisticado técnicamente, en la teoría de juegos que tiende a vivir en su propio mundo estrecho porque no da respuestas a preguntas económicas concretas. En segundo lugar, y de manera relacionada, sus supuestos de modelado deben ser interpretables en términos del comportamiento de los humanos reales (o de cualquier agente que esté describiendo). Si sus resultados se centran en construcciones teóricas como las condiciones topológicas en las creencias de orden superior, pueden dejar a los no especialistas encogiéndose de hombros. De hecho, muchos de los mayores problemas abiertos en la teoría de juegos (en mi opinión) son preguntas sobre cómo modelar las cosas correctamente para describir el comportamiento real de las personas, para lo cual nuestros conceptos de equilibrio existentes son inadecuados. En tercer lugar, su contribución debe ser lo suficientemente simple desde el punto de vista técnico como para que las personas que realizan un trabajo más aplicado (o al menos otros teóricos) puedan usarlo y desarrollarlo, pero no tan simple como para ser trivial o bien entendido.

Todo esto significa, entre otras cosas, que se pasa mucho tiempo tratando de encontrar buenas preguntas para hacer y buenos modelos para hacerlas, y no, por ejemplo, tratando de probar conjeturas ya bien formuladas. Puede ser frustrante. En un día típico, me voy a casa pensando “otro día tratando de tener nuevas ideas y no tener ninguna”. Por supuesto, las otras partes rutinarias de la vida académica (enseñanza, arbitraje, lectura de nuevos artículos, etc.) ayudan a evitar que esa sensación de falta de objetivos se vuelva abrumadora.

Otra cosa a mencionar sobre la teoría de juegos es que es un campo en declive. [Editar: Esto es específico de la economía; ver comentarios.] La proporción de artículos teóricos en las principales revistas económicas ha disminuido drásticamente desde la década de 1980 más o menos. En parte, esto se debe a que se ha recogido una gran cantidad de fruta de bajo perfil, pero también los grandes avances en el poder computacional y la disponibilidad de datos han estimulado el avance en la economía empírica y la econometría, mientras que la teoría no ha tenido un motor de crecimiento similar. Además, mi impresión es que fuera de los 50 principales departamentos de economía, la teoría a menudo se ve como un lujo ya que los estudiantes de economía en la mayoría de los lugares están interesados ​​en preguntas más aplicadas. Sin embargo, no siento esta disminución en el día a día. Por el contrario, me siento parte de una comunidad amplia y viva y siento que hay un compromiso con nuestros colegas que hacen cosas más aplicadas: están interesados ​​en nuestras perspectivas teóricas y, a cambio, su trabajo nos da fuentes de nuevos problemas para pensar .

Me ha encantado hacer investigación de teoría de juegos. Hay muchos antecedentes diferentes que lo ayudarán: economía para comprender los incentivos, informática para desarrollar algoritmos computacionalmente eficientes para resolver problemas de teoría de juegos, matemáticas / estadísticas para comprender las probabilidades y optimizaciones detrás de las decisiones, negocios para comprender cómo se puede aplicar la teoría de juegos a la publicidad, psicología para una intuición sobre por qué las personas se comportan como lo hacen, etc.

Llegué a la investigación de teoría de juegos con experiencia en informática y matemáticas. Mi profesor investiga sobre los juegos de seguridad : juegos en los que hay un defensor y un atacante, y el defensor está tratando de evitar que el atacante ataque. Siempre me interesaron las matemáticas del juego (en parte inspirado por 21 (película de 2008)), así que me interesé en aplicar estos juegos de seguridad al casino, y quería responder la pregunta: ¿Cómo debería el casino evitar o limitar a los tramposos? de hacer trampa en un casino?

En un casino tenemos tramposos y jugadores honestos, y la seguridad no sabe quién está engañando y quién es honesto. El objetivo del casino es maximizar sus ganancias. En cada punto del juego, queremos desarrollar una estrategia que le diga al casino si deberían expulsar a un jugador que podría estar haciendo trampa. Asumimos que el tramposo puede aprender la estrategia del casino. Es decir, el tramposo puede venir al casino durante un año y observar cuándo el casino expulsa a los jugadores para descubrir cómo comportarse para no ser expulsado.

Para cada secuencia de victorias y derrotas (o cualquier número de resultados), la estrategia le dirá al casino la probabilidad de que el jugador sea expulsado (p = 1 es expulsado, p = 0 definitivamente no es expulsado, de lo contrario obtiene expulsado con una probabilidad entre 0 y 1).

Resolvemos este problema de optimización con programación lineal. El problema es que es muy ineficiente, ¡porque hay exponencialmente muchas secuencias de victorias y derrotas! Entonces, resolvemos el problema de manera más eficiente usando la programación dinámica, y también podemos aproximar la solución con el movimiento browniano con una rápida integración numérica.

Ahora estoy trabajando en un nuevo problema sobre usuarios maliciosos en las redes sociales, pero nada que valga la pena discutir públicamente todavía 🙂

Bastante fascinante en realidad. Como parte de mi plan de estudios de doctorado, tuve que tomar una clase sobre teoría de juegos. Y estaba súper feliz de haberlo hecho.

==== Antecedentes : teoría de juegos y juegos de seguridad ====

Mi asociación con GT fue principalmente en el contexto de los Juegos de seguridad , similar a Melissa Dalis. Mi introducción inicial al campo fue usar Game Theory para crear horarios de patrulla aleatorizados para el personal de seguridad del aeropuerto de LAX. Es decir, dados todos los puntos / calles de entrada / salida a los aeropuertos y al personal de seguridad limitado, ¿cómo debería uno programarlos de manera óptima para maximizar su ‘pago esperado’? Es decir, frente a un adversario / atacante / terrorista adaptativo, etc.,

Lo mismo se aplica para programar comandantes aéreos federales en vuelos, proteger puertos y otra infraestructura civil.

Todos los algoritmos se basan en la programación lineal, pero son bastante eficientes ya que explotan ciertas propiedades de los juegos de seguridad y funcionan en representaciones “compactas” de juegos (es decir, literalmente compactas y comprimidas, pero capturando todos los beneficios / utilidades). Cada algoritmo difiere en su escalabilidad y eficiencia y la mayor parte de la investigación está en resolver juegos de seguridad con algoritmos “eficientes”.

Este es UNO de los pocos campos donde el trabajo realmente dejó el laboratorio y se aplicó en la práctica. Aquí hay un enlace que muestra que: The Teamcore Research Group

==== Investigación : Aplicación de la teoría de juegos a las pruebas de software ====

Encontré las ideas de la teoría de juegos y sus aplicaciones a la seguridad bastante fascinantes y pensé si podría usarse en el campo de la ingeniería de software. Apliqué la idea del juego de seguridad (defensor contra atacante) a las pruebas de software para obtener un programa óptimo de pruebas de regresión aleatoria.

Entonces, las pruebas de regresión crecen exponencialmente en tamaño wrt para el software. A medida que pasa el tiempo, hay más pruebas que hacer y menos tiempo / recursos / presupuesto para hacerlo. Suponiendo que los desarrolladores verifiquen (o puedan) registrar un código insuficientemente probado para el sistema, ¿cómo podemos (de manera óptima) aleatorizar las pruebas de regresión para maximizar los beneficios para el probador (es decir, encontrar tantos errores como sea posible)?

Aquí están los supuestos que hicimos para explorar esta idea desde el punto de vista teórico del juego:

  • Los probadores son defensores: defienden contra la mala calidad del software al garantizar que el código esté lo más libre de errores / errores posible
  • Desarrolladores como atacantes: suponemos que los desarrolladores pueden ingresar código insuficientemente probado para terminar más trabajo en lugar de “perder” el tiempo probándolo a fondo. Una suposición justa en la práctica.
  • Las pruebas deterministas se pueden jugar: si los desarrolladores saben exactamente qué se está probando y cuándo, pueden elegir ser descuidados con los elementos que no se probarán. Una vez más, una suposición justa ya que en la mayoría de los casos lo que se probará cuando sea conocido por todos (es decir, los desarrolladores conocen la estrategia de prueba por adelantado)
  • Los desarrolladores tienen una observación perfecta, es decir, conocen las probabilidades de la frecuencia con la que se ejecuta cada caso de prueba. (Suponemos en los juegos de seguridad que el adversario tiene una observación perfecta. Ayuda a garantizar que los juegos sean robustos frente a los peores escenarios).

Por lo tanto, si aleatorizamos las pruebas de regresión, damos una noción de beneficios para los probadores / desarrolladores, podemos disuadir a los desarrolladores de hacer un trabajo descuidado, aumentando así la calidad del software.

Esta fue una aplicación bastante creativa / innovadora de juegos de seguridad para pruebas de software y nunca se hizo en el pasado. Presentamos esta idea a expertos en nuestro campo y en conferencias y recibimos una buena respuesta. Actualmente lo estamos explorando más a fondo para ver qué sucede y si se puede crear un marco de trabajo de código abierto, ¡mucho en la línea de extender jUnit pero con la capacidad adicional de aleatorizar suites de regresión!

Entonces, para responder a sus preguntas, la teoría de juegos se puede aplicar incluso en campos previamente desconocidos para su aplicación. Básicamente, la teoría de juegos es un modelo matemático para estudiar la interacción entre jugadores, dada alguna noción de recompensas. Los jugadores podrían ser humanos, agentes informáticos, enrutadores, etc. ¡Es una lente de ver el problema bajo una luz particular que podría proporcionar información fascinante!

Por ejemplo, ¡aplicarlo en el casino como sugiere Melissa fue bastante fascinante para mí! ¡Simple pero no tan obvio!

He tenido algunas experiencias mixtas con eso. Mi experiencia es que puedes hacer un trabajo muy razonable sin tener que ser un súper especialista (como en otros subcampos matemáticos más puros), mientras tienes una idea de los fenómenos del mundo real. La principal frustración para mí ha sido la aplicabilidad muy limitada de los resultados y la forma en que simplemente no tenemos suficientes herramientas matemáticas para lidiar con la complejidad de la realidad.

Entonces, en resumen, tiene algunos de los buenos aspectos de la emoción estimulante de resolver problemas complejos e interesantes de campos duros y puros (matemática, física) y algo del sentido realista de la utilidad y la comprensión de la realidad de los campos más aplicados (como química o biología). Los inconvenientes son que todavía es demasiado abstracto para aplicarse bien a los aspectos más interesantes de la realidad, y es demasiado aplicado para ser respetado como un esfuerzo intelectual por sí mismo (es decir, siempre tendrá que justificar todos sus movimientos en términos de utilidad, social o de otro tipo).

Mi fondo :

Hice mi licenciatura en matemáticas, con una tesis en teoría de juegos (en particular en la división justa). Me gustó y pensé que era interesante, pero no pensé que hubiera tanto para mí.

Después de eso, estudié ciencias de la computación y finalmente terminé estudiando biología computacional. A partir de ahí, descubrí la teoría de los juegos evolutivos y vi la oportunidad de conciliar mis intereses pasados ​​y presentes. He publicado algunos artículos en el campo y supongo que de vez en cuando todavía puede considerarme un biólogo teórico haciendo investigación de teoría de juegos.