Algorithmic incentives
Interactive proofs are a type of mathematical game, pioneered at MIT, in which one player — often called Arthur — tries to extract reliable information from an unreliable interlocutor — Merlin. In a new variation known as a rational proof, Merlin is still untrustworthy, but he's a rational actor, in the economic sense. Image: Howard Pyle In 1993, MIT cryptography researchers Shafi Goldwasser and Silvio Micali shared in the first Gödel Prize for theoretical computer science for their work on interactive proofs — a type of mathematical game in which a player attempts to extract reliable information from an unreliable interlocutor. In their groundbreaking 1985 paper on the topic, Goldwasser, Micali and the University of Toronto’s Charles Rackoff ’72, SM ’72, PhD ’74 proposed a particular kind of interactive proof, called a zero-knowledge proof, in which a player can establish that he or she knows some secret information without actually revealing...