  PPAD refers to a class of computational problems for which solutions are
guaranteed to exist due to a specific combinatorial principle. The most
well-known such problem is that of computing a Nash equilibrium of a game.
Other examples include the search for market equilibria, and envy-free
allocations in the context of cake-cutting. A problem is said to be complete
for PPAD if it belongs to PPAD and can be shown to constitute one of the
hardest computational challenges within that class.
  In this paper, I give a relatively informal overview of the proofs used in
the PPAD-completeness results. The focus is on the mixed Nash equilibria
guaranteed to exist by Nash's theorem. I also give an overview of some recent
work that uses these ideas to show PSPACE-completeness for the computation of
specific equilibria found by homotopy methods. I give a brief introduction to
related problems of searching for market equilibria.
