Thuật toán thời gian đa thức cho cân bằng Nash được hỗ trợ tốt 1/2 trong trò chơi Bimatrix
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games.
Kể từ kết quả đầy đủ PPAD để tính toán trạng thái cân bằng Nash ngay cả trong trò chơi hai người chơi, một dòng nghiên cứu quan trọng đã tập trung vào sự phục hồi có thể đạt được trong thời gian đa thức. Bài nghiên cứu này xem xét khái niệm cân bằng Nash được hỗ trợ tốt ε, trong đó ε [0, 1] tương ứng với sự đảm bảo gần đúng. Nói một cách đơn giản, trong trạng thái cân bằng được hỗ trợ tốt ε, mọi người chơi đều chọn các hành động có xác suất dương nằm trong ε của kết quả tối đa có thể đạt được, ngược lại với chiến lược của người chơi khác. Kể từ khi đảm bảo gần đúng ban đầu là 2/3 cho các trạng thái cân bằng được hỗ trợ tốt được thiết lập cách đây hơn một thập kỷ, tiến trình giải quyết vấn đề này cực kỳ chậm và tăng dần. Đáng chú ý là những cải tiến nhỏ lên 0,6608 và cuối cùng là 0,6528 đã đạt được nhờ các thuật toán có độ phức tạp ngày càng tăng. Kết quả chính của bài nghiên cứu này là một thuật toán đơn giản và trực quan, giúp cải thiện độ đảm bảo gần đúng lên 1/2. Thuật toán của bài nghiên cứu này dựa trên lập trình tuyến tính và đặc biệt là khai thác các trò chơi có tổng bằng 0 được xác định phù hợp phát sinh từ ma trận kết quả của hai người chơi. Là sản phẩm phụ, bài nghiên cứu này trình bày cách đạt được mức đảm bảo gần đúng tương tự theo cách truy vấn hiệu quả.
Đọc thêm các bài viết liên quan tại thẻ Tags bên dưới