Author: Juan Valencia

Un nuevo giro en trabajo pionero hecho por criptógrafos del MIT (Massachusetts Institute of Technology – Instituto Tecnológico de Massachusetts) hace casi 30 años podría llevar a mejores maneras de estructurar contratos.

Larry Hardesty, MIT News Office. Original (en inglés).

En 1993, los investigadores criptógrafos del MIT Shafi Goldwasser y Silvio Micali compartieron el primer premio Gödel para la ciencia computacional teórica por su trabajo en pruebas interactivas – un tipo de juego matemático en el que un jugador intenta extraer información confiable de un interlocutor no confiable.

En su innovador artículo de 1985 sobre el tema, Goldwasser, Micali y el doctor Charles Rackoff de la Universidad de Toronto propusieron un tipo particular de prueba interactiva, llamada prueba de cero-conocimiento, en la que un jugador puede establecer que él o ella conoce alguna información secreta sin llegar a revelarla. Hoy en día, pruebas de cero-conocimiento son utilizadas para asegurar transacciones entre instituciones financieras y varias compañías nuevas han sido fundadas para comercializarlas.

En el Simposio sobre Teoría Computacional de la Asociación de Maquinaria Computacional en Mayo, Micali, el profesor de Ingeniería en el MIT, y el estudiante graduado Pablo Azar presentarán un nuevo tipo de juego matemático al que están llamando una prueba racional; varía las pruebas interactivas dándoles un componente económico. Cómo las pruebas interactivas, las pruebas racionales pueden tener implicaciones para la criptografía pero también podrían sugerir nuevas maneras de estructurar incentivos en contratos.

“Mientras que estre trabajo es sobre asimetría de información”, añade Micali. “En la ciencia computacional, pensamos que información valiosa es el resultado de un largo cálculo, un cálculo que no puedo hacer yo mismo”. Pero los economistas, dice Micali, modelan el conocimiento como una distribución de probabilidad que precisamente describe un estado de la naturaleza. “Era claro para mi que ambas cosas tenían que converger”, dijo.

Una prueba interactiva clásica involucra dos jugadores, a veces nombrados Arturo y Merlín. Arturo tiene un problema complejo que necesita resolver, pero sus recursos computacionales son limitados; Merlín, por otro lado, tiene recursos computacionales pero no es confiable. Una prueba interactiva es un procedimiento por medio del cual Arturo le hace a Merlín una serie de preguntas. Al final, aunque Arturo no puede resolver el problema por sí mismo, puede decir si la solución que Merlín le ha dado es válida.

En una prueba racional, Merlín sigue siendo no confiable, pero es un actor racional en el sentido económico: Cuando es enfrentado con una decisión, siempre elegirá la opción que maximice su recompensa. “En la prueba interactiva clásica, si haces trampa, eres atrapado”, Azar explica. “En este modelo, si haces trampa, obtienes menos dinero”.

Conexión de complejidad

Investigación en pruebas interactivas y pruebas racionales cae bajo la categoría de la teoría de complejidad computacional, que clasifica problemas computacionales de acuerdo a qué tan difíciles son de resolver. Las dos clases de complejidad mejor conocidas son P y NP. A grandes rasgos, P es un grupo de problemas relativamente fáciles, mientras que NP contiene algunos problemas que, hasta donde se sabe, son muy, muy difíciles.

Problemas en NP incluyen la factorización de grandes números, la selección de una ruta óptima para un vendedor que viaja, y los llamados problemas de satisfacibilidad, en los que uno debe encontrar condiciones que satisfagan conjuntos de restricciones lógicas. Por ejemplo, es posible idear una lista de asistencia para una fiesta que satisfaga la expresión lógica (Alicia O Bob Y Carol) Y (David Y Ernie Y NO Alice)? (Si: Bob, Carol, David y Ernie van a la fiesta, pero Alice no). De hecho, la gran mayoría de los problemas difíciles en NP pueden ser replanteados como problemas de satisfacibilidad.

Para tener un sentido de como funcionan las pruebas racionales, considera la pregunta de cuántas soluciones tiene un problema de satisfacibilidad – problemas aún más difíciles que encontrar una sola solución. Supón que el problema de satisfacibilidad es una versión más complicada del problema de la lista de la fiesta, uno que involucra 20 invitados. Con 20 invitados, hay 1,048,576 posibilidades para la composición final de la fiesta. ¿Cuántas de esas satisfacen la expresión lógica? Arturo no tiene suficiente tiempo para probarlas todas.

¿Pero que sucede si Arturo en su lugar subasta un boleto en una lotería? Incluso escribirá una lista perfectamente aleatoria de asistentes a la fiesta – Alice si, Bob no, Carol si y así sucesivamente – y si satisface la expresión, le dará a quien tenga el boleto $1,048,576. ¿Cuánto ofrecerá Merlín por el boleto?

Supon que Merlín sabe que hay exactamente 300 soluciones para el problema de satisfacibilidad. Las posibilidades de que la lista de la fiesta de Arthur sea uno de ellas son 300 en 1,048,576. De acuerdo al análisis econométrico estándar, una posibilidad de 300 en 1,048,576 vale exactamente $300. Así que si Merlín es racional, apostará $300 por el boleto. De esa información, Arturo puede deducir el número de soluciones.

Knockout a la primera ronda

Los detalles son más complicados que eso, y por supuesto, con muy pocas excepciones, nadie en el mundo real quiere poner un millón de dólares para aprender la respuesta a un problema matemático. Pero el resultado del artículo de los investigadores es que con pruebas racionales, pueden establecer en una ronda – “¿Qué ofreces?” – lo que podría requerir millones de rondas usando pruebas interactivas clásicas. “La interacción, en la práctica, es costosa”, dice Azar. “Es costoso enviar mensajes por una red. Reduciendo la interacción de un millón de rondas a una provee ganancias significativas en tiempo”.

“Pienso que es otro caso donde pensamos que entendemos que es una prueba, y hay un giro, y obtenemos algún resultado inesperado”, dice Moni Naor, la presidenta en el Departamento de Ciencia Computacional y Matemáticas Aplicadas en el Instituto Israelí de Ciencia Weizmann. “Lo hemos visto en el pasado con pruebas interactivas, que resultaron ser muy poderosas, mucho más poderosas de lo que normalmente piensas que lo son pruebas que escribes y verificas”. Con pruebas racionales, dice Naor, “tenemos otro giro, si asignas alguna racionalidad teórica al demostrador, entonces la prueba es otra cosa en la que no pensamos en el pasado”.

Naor advierte que el trabajo está “solo en el comienzo”, y que es difícil decir cuando dará resultados prácticos, y lo que podrían ser. Pero “claramente, vale la pena estudiar”, dijo. “En general, la combinación de la investigación en complejidad, criptografía y teoría de juego es prometedora”.

Micali está de acuerdo. “Pienso que esta es una buena base para futuras exploraciones”, dijo. “Justo ahora, la hemos desarrollado para problemas que son muy, muy difíciles. ¿Pero que hay de los problemas que son muy, muy simples?”. Sistemas de prueba racional que describen interacciones simples podrían tener una aplicación en crowsourcing, una técnica mediante la cual tareas computacionales que son fáciles para los humanos pero difíciles para las computadoras son distribuidas por Internet a ejércitos de voluntarios que reciben pequeñas recompensas financieras por cada tarea que completan. Micali imagina que podrían incluso ser usadas para sistemas biológicos, en los que organismos individuales – o células iguales – pueden ser pensados como productores y consumidores.

Reimpreso con permiso de MIT News.

Fuente
http://web.mit.edu/ (en inglés)