Định lý minimax của von Neumann

Đối ngẫu yếu. Với mọi $x_0 \in \Delta_m$ và $y_0 \in \Delta_n$ cố định: $\min_y x_0^\top A y \le x_0^\top A y_0 \le \max_x x^\top A y_0$. Lấy $\max_{x_0}$ vế trái và $\min_{y_0}$ vế phải giữ nguyên bất đẳng thức: $\max_x \min_y x^\top A y \le \min_y \max_x x^\top A y$. Chiều này không cần lập luận ngẫu nhiên hóa nào cả.

Quy về quy hoạch tuyến tính. Vì $y \mapsto x^\top A y$ tuyến tính, cực tiểu của nó trên đơn hình $\Delta_n$ đạt tại một đỉnh, tức tại một chiến lược thuần túy $j$ nào đó: $\min_y x^\top A y = \min_{j} \sum_{i=1}^m x_i A_{ij}$. Vậy bài toán $\max_x \min_y x^\top A y$ của người chơi hàng là quy hoạch tuyến tính: cực đại hóa $v$ với ràng buộc $\sum_{i=1}^m A_{ij} x_i \ge v$ với mọi $j = 1, \dots, n$, và $x \in \Delta_m$.

Bài toán đối ngẫu. Theo lý thuyết đối ngẫu chuẩn của quy hoạch tuyến tính, đối ngẫu của quy hoạch này là: cực tiểu hóa $w$ với ràng buộc $\sum_{j=1}^n A_{ij} y_j \le w$ với mọi $i = 1, \dots, m$, và $y \in \Delta_n$ — chính xác là công thức quy hoạch tuyến tính cho bài toán $\min_y \max_x x^\top A y$ của người chơi cột.

Đối ngẫu mạnh. Cả miền khả thi nguyên thủy và đối ngẫu ($\Delta_m$ và $\Delta_n$) đều khác rỗng và compact, nên quy hoạch tuyến tính khả thi và bị chặn; định lý đối ngẫu mạnh cho quy hoạch tuyến tính khi đó đảm bảo giá trị tối ưu nguyên thủy và đối ngẫu trùng nhau: $\max_x \min_y x^\top A y = \min_y \max_x x^\top A y$. Cùng với đối ngẫu yếu đã cho $\le$ ở chiều này, đẳng thức xảy ra, chứng minh định lý.