The 'Useless' Theory Behind Modern SNARKs (ft. Gödel Prize Winner Noam Nisan)

So nineteen ninety-nine, as we discussed, algorithmic mechanism design, the paper with Amir Ronen came out, um, made a huge splash right away, and that was, you know, part of a bunch of simultaneous beginnings of the field called now algorithmic game theory or computer science and economics.

So help me just connect the dots a little bit.

So you talked about how in working on the Popcorn project, you know, the economic and coordination issues already were striking you as sort of the most scientifically fascinating parts of it.

You've told me in the past that, you know, algorithmic mechanism design actually sort of started from Amir kind of walking into your office with a mechanism design paper, and you were kind of like, "What is this?" Am I remembering the story correctly or-

Yeah.

So what was it like? Was you already thinking you wanted to work on some kind of-

Yes

... more economic problem, and that was the right opportunity or?

I sort of wanted to work about incentives and computation.

I thought that was really interesting, how to get different computers to cooperate.

And I had no idea that there was a subfield of economics called algorithm mechanism design.

So I did know that there was something called game theory, and I learned a little bit of game theory.

And I, you know, uh, Miron then came, and I told him, "Look, this is very interesting.

It's somewhat related to game theory.

Maybe you can learn a little bit game theory." And he got this big, uh, microeconomics Mascolell et al pa- uh, book, and he started reading it and telling me stuff.

And at certain point in time, he realized that, oh, there is this is kind of subfield of economics called mechanism design that seemed to be very related to what we were looking at.

And w- at that time, did you know that, um, you know, for example, Ilias Koutsoupias and Christos Papadimitriou were sort of thinking about game theory and computer science at that time, or were those just sort of parallel, simultaneous developments?

I was thinking about this, and then at about the same time I heard about-

Yeah

... uh, Christos and Ilias, and I heard about your work with Eva.

So I know that in some sense, your work is a continuation of Papadimitriou and Ilias.

But from my point of view, there was this, like, three different threads because Papadimitriou then was looking at a slightly other thing.

I really was, you know, seeing what Eva and her students, for example, you were doing, and the same thing about what Christos was doing, and we were all in the same space.

And I thought, "Oh, this means that, you know, we're onto something here because completely different people from completely different angles are looking at this general field." And I think for a few years there, uh, there was this kind of thing that were maybe five universities giving courses in algorithmic game theory and economic to computation different time, and all of us would always look at all the courses that the others were giving and basically steal from each other all the time.

So it was really nice.