In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits.
Example: If every person likes at least 1/3 of the books in a library, then the library has a book, which at least 1/3 of people like.
Proof: Suppose there are N people and B books. Each person likes at least B/3 of the books. Let people leave a mark on the book they like. Then, there will be at least M=(NB)/3 marks. The averaging argument claims that there exists a book with at least N/3 marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than N/3 marks. However, since there are B books, the total number of marks will be fewer than (NB)/3, contradicting the fact that there are at least