In complexity, the most exciting work studied the problem of finding equilibriums of games. How does one find a Nash Equilibrium when each player's payoffs are given by a matrix. In a 2-player zero-sum game (my gain is your loss), one can easily find equilibriums using linear programming. But if we have unrelated payoffs, computing the equilibrium can be much more difficult.
- The Complexity of Computing a Nash Equilibrium by Constantinos Daskalakis, Paul Goldberg and Christos Papadimitriou
- Settling the Complexity of Two-Player Nash Equilibrium by Xi Chen and Xiaotie Deng
Daskalakis et al. showed that computing the Nash Equilibrium between three players in PPAD-complete and Chen and Deng extended their work to 2-player games. PPAD represents a search problem, solvable if P = NP though not believed to be NP-hard.
You don't have to know the formal definition of PPAD to appreciate this work. PPAD corresponds to a discrete version of the Brouwer fixed-point theorem, the critical tool in proving that Nash Equilibriums exist. One proof of the fixed-point theorem uses Sperner's Lemma, also PPAD-complete. The New York Times has a nice example of using Sperner's Lemma to fairly divide up the rent among three friends who share an apartment with different sized rooms.
Paul Goldberg wrote a nice survey on these and related results, such as finding equilibria in markets.