I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems.

I cannot find the original papers which invented/advocated adversary argument or the first problems whose lower bounds are obtained by adversary argument. (In particular, I am quite surprised that there are no wiki pages on adversary argument.)

Do you know some original literature on adversary argument?

  • $\begingroup$ Huh. This is not exclusive to lower bounds, so maybe it comes from a whole different area? $\endgroup$ – Raphael Apr 20 '18 at 11:49

The oldest literature can be traced back to Andrew Yao's min-max principle, which inturns has its elder root from von Neumann's.

History of game theory is not continuous in time. At least, there was some rise and then fall in the intensity of mathematicians' attention to this theory.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.