Lý thuyết trò chơi

Nếu không ngẫu nhiên hóa, ai đi "sau" (chọn sau khi biết chiến lược của đối thủ) có lợi thế, nên maximin (hàng cam kết trước) nói chung nhỏ hơn hoặc bằng minimax (cột cam kết trước). Nội dung bất ngờ của định lý là với chiến lược hỗn hợp, khoảng cách này đóng hoàn toàn lại: ngẫu nhiên hóa loại bỏ mọi lợi thế của việc hành động sau, vì đối thủ không còn đoán trước — và khai thác — một lựa chọn cố định.

Đố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ý.

Chứng minh xây dựng một ánh xạ liên tục "cải thiện chiến lược một chút" trên không gian mọi hồ sơ chiến lược: đẩy xác suất về phía bất kỳ chiến lược thuần túy nào đang làm tốt hơn mức trung bình. Vì không gian hồ sơ chiến lược compact và lồi, định lý điểm bất động Brouwer đảm bảo ánh xạ này có một điểm bất động — một hồ sơ mà ánh xạ không muốn thay đổi. Phần còn lại của chứng minh cho thấy điểm bất động chính xác là một hồ sơ không có bước lệch có lợi, tức một cân bằng Nash.

Đặt $\Delta = \Delta_1 \times \cdots \times \Delta_n$, tích các đơn hình chiến lược hỗn hợp của những người chơi — một tập con compact, lồi của không gian Euclid. Với $x \in \Delta$, người chơi $i$, và chiến lược thuần túy $j \in S_i$, đặt hàm lợi ích tăng thêm $g_{ij}(x) = \max\big(0,\, u_i(s_{ij}, x_{-i}) - u_i(x)\big)$, lợi ích mà người chơi $i$ thu được nếu chuyển hẳn sang chiến lược thuần túy $j$, hoặc $0$ nếu chuyển như vậy không có lợi. Đặt $f : \Delta \to \Delta$ bởi $f_i(x)_j = \dfrac{x_{ij} + g_{ij}(x)}{1 + \sum_{k \in S_i} g_{ik}(x)}$; vì $u_i$ liên tục (thực ra đa tuyến tính) theo $x$, $g_{ij}$ liên tục, nên $f$ liên tục, và mỗi $f_i(x)$ vẫn là vector xác suất theo cách xây dựng.

Theo định lý điểm bất động Brouwer, ánh xạ liên tục $f$ trên tập compact lồi $\Delta$ có một điểm bất động $x^\star$ với $f(x^\star) = x^\star$. Đặt $S_i := \sum_{k \in S_i} g_{ik}(x^\star)$; phương trình điểm bất động cho mỗi $(i,j)$ là $x_{ij}^\star (1 + S_i) = x_{ij}^\star + g_{ij}(x^\star)$, tức $x_{ij}^\star S_i = g_{ij}(x^\star)$.

Cố định một người chơi $i$ và đặt $d_{ij} := u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)$, nên $g_{ij}(x^\star) = \max(0, d_{ij})$. Nhân phương trình điểm bất động với $d_{ij}$ và cộng theo $j \in S_i$: vế trái, $S_i \sum_j x_{ij}^\star d_{ij} = S_i\left(\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)\sum_j x_{ij}^\star\right) = S_i(u_i(x^\star) - u_i(x^\star)) = 0$, dùng $\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) = u_i(x^\star)$ và $\sum_j x_{ij}^\star = 1$.

Vế phải, $\sum_j g_{ij}(x^\star)\, d_{ij} = \sum_j \max(0,d_{ij})\, d_{ij} = \sum_{j:\, d_{ij} > 0} d_{ij}^2 \ge 0$. Cho hai vế bằng nhau, $\sum_{j:\, d_{ij}>0} d_{ij}^2 = 0$, một tổng bình phương bằng 0, nên mọi số hạng triệt tiêu: không có $j$ nào với $d_{ij} > 0$. Vì $i$ tùy ý, $u_i(s_{ij}, x_{-i}^\star) \le u_i(x^\star)$ với mọi người chơi $i$ và mọi chiến lược thuần túy $j$ — chính xác điều kiện cân bằng Nash. Vậy $x^\star$ là một cân bằng Nash.