Lý thuyết trò chơi cho tác nhân

Lý thuyết trò chơi cung cấp khuôn khổ toán học để phân tích tương tác chiến lược giữa các tác nhân hợp lý, dự đoán cách các nhà ra quyết định vị kỷ hành xử khi kết quả của mỗi người phụ thuộc vào lựa chọn của những người khác.

Definition

Lý thuyết trò chơi nghiên cứu các tình huống trong đó nhiều tác nhân hợp lý, mỗi tác nhân chọn các hành động mà phần thưởng của chúng phụ thuộc vào lựa chọn của tất cả các tác nhân, và mô tả hành vi chung ổn định hoặc hợp lý thông qua các khái niệm giải pháp như cân bằng.

Scope

Chủ đề này bao gồm các nền tảng lý thuyết trò chơi được sử dụng trong AI đa tác nhân: trò chơi dạng chuẩn và dạng mở rộng, chiến lược trội, cân bằng Nash và sự tồn tại của nó, chiến lược hỗn hợp, và các ví dụ chính như thế lưỡng nan của tù nhân và trò chơi tổng bằng không; cùng với các vấn đề thuật toán về tính toán cân bằng. Nó đề cập đến cách các tác nhân suy luận về nhau và những hành vi chung nào là ổn định. Việc thiết kế các quy tắc tương tác được xử lý trong thiết kế cơ chế, và học cách chơi trò chơi thuộc về phân ngành học máy.

Core questions

• Tương tác chiến lược được biểu diễn dưới dạng trò chơi dạng chuẩn hay dạng mở rộng như thế nào?
• Những khái niệm giải pháp nào (chiến lược trội, cân bằng Nash) dự đoán cách các tác nhân hợp lý hành xử?
• Khi nào thì một cân bằng được đảm bảo tồn tại, có thể trong các chiến lược hỗn hợp?
• Việc tính toán cân bằng khó đến mức nào, và điều này ảnh hưởng đến việc sử dụng chúng của các tác nhân ra sao?

Key concepts

• trò chơi dạng chuẩn và dạng mở rộng
• phần thưởng và chiến lược
• chiến lược trội
• cân bằng Nash
• chiến lược hỗn hợp
• trò chơi tổng bằng không và minimax
• thế lưỡng nan của tù nhân
• tính toán cân bằng

Key theories

Cân bằng Nash

Cân bằng Nash là một tập hợp các chiến lược trong đó không tác nhân nào có thể cải thiện phần thưởng của mình bằng cách đơn phương thay đổi chiến lược của riêng mình; Nash đã chứng minh rằng mọi trò chơi hữu hạn đều có ít nhất một cân bằng như vậy, có thể trong các chiến lược hỗn hợp.

Minimax trong trò chơi tổng bằng không

Trong các trò chơi tổng bằng không hai người chơi, định lý minimax của von Neumann đảm bảo một giá trị và các chiến lược tối ưu (có thể ngẫu nhiên) cho cả hai người chơi, kết nối lý thuyết trò chơi với việc ra quyết định đối kháng.

Chiến lược trội và thế lưỡng nan

Phân tích trò chơi thông qua các chiến lược trội giải thích các kết quả như thế lưỡng nan của tù nhân, nơi các lựa chọn hợp lý cá nhân dẫn đến một kết quả tồi tệ hơn về mặt tập thể, minh họa sự căng thẳng giữa tính hợp lý cá nhân và nhóm.

Clinical relevance

Phân tích lý thuyết trò chơi cung cấp thông tin cho việc thiết kế đấu giá và thị trường, chiến lược an ninh và tuần tra, định tuyến và tắc nghẽn mạng, và đàm phán tự động, bằng cách dự đoán cách các tác nhân chiến lược sẽ hành động và xác định các kết quả ổn định trong các môi trường cạnh tranh.

History

Lý thuyết trò chơi được thành lập bởi von Neumann và Morgenstern (1944) và được mở rộng bởi khái niệm cân bằng của Nash (1950). Nó trở thành trung tâm của kinh tế học và, từ những năm 1990, đối với AI và khoa học máy tính thông qua lý thuyết trò chơi thuật toán, nghiên cứu độ phức tạp tính toán của cân bằng và việc sử dụng chúng trong các hệ thống đa tác nhân.

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

Cân bằng Nash là gì?

Cân bằng Nash là một sự kết hợp các chiến lược, mỗi tác nhân một chiến lược, sao cho không tác nhân đơn lẻ nào có thể làm tốt hơn bằng cách chỉ thay đổi chiến lược của riêng mình trong khi những tác nhân khác giữ nguyên chiến lược của họ. Nó nắm bắt một khái niệm về hành vi hợp lý ổn định, nhất quán lẫn nhau.

Tại sao thế lưỡng nan của tù nhân lại quan trọng đối với các tác nhân AI?

Thế lưỡng nan của tù nhân cho thấy rằng các tác nhân hành động vì lợi ích cá nhân hợp lý của họ có thể đạt đến một kết quả tồi tệ hơn cho tất cả họ so với việc họ đã hợp tác. Nó nhấn mạnh lý do tại sao việc thiết kế các cơ chế khuyến khích và phối hợp lại quan trọng khi xây dựng các hệ thống tác nhân vị kỷ.