Chiến lược (lý thuyết trò chơi)
Trong lý thuyết trò chơi, chiến lược của người chơi là bất kì lựa chọn nào mà người chơi có thể thực hiện, trong bối cảnh kết quả thu được không chỉ phụ thuộc vào hành động của bản thân người chơi đó, mà còn phụ thuộc vào hành vi của những người chơi khác.[1] Chiến lược của một người chơi sẽ quyết định người chơi sẽ thực hiện hành động nào tại bất kì giai đoạn nào trong trò chơi.
Khái niệm chiến lược thường bị nhầm lẫn với khái niệm nước cờ. Một nước cờ là một hành động mà người chơi thực hiện tại một thời điểm nhất định trong suốt quá trình diễn ra trò chơi (ví dụ, trong trò chơi cờ vua, một nước cờ là việc di chuyển quân tượng từ ô a2 sang ô b3). Trong khi đó, một chiến lược là một thuật toán hoàn thiện cho toàn bộ quá trình chơi trò chơi, chỉ rõ cho người chơi phải làm gì trong mọi trường hợp có thể xảy ra trong suốt trò chơi.
Một hồ sơ chiến lược (còn được gọi là tổ hợp chiến lược) là một hệ thống các chiến lược của tất cả mọi người chơi, chỉ rõ toàn bộ các hành động sẽ diễn ra trong trò chơi. Một hồ sơ chiến lược phải bao gồm một và chỉ một chiến lược duy nhất cho mỗi người chơi.
Hệ thống chiến lược[sửa | sửa mã nguồn]
Hệ thống chiến lược của một người chơi được định nghĩa là những chiến lược mà người chơi có thể thực hiện.
Một người chơi sẽ có hệ thống chiến lược ''hữu hạn nếu họ có quyền thực hiện một số chiến lược không liền mạch (số chiến lược có thể đếm được, không phải một khoảng trong tập hợp số thực). Ví dụ, trong trò chơi oẳn tù tì, mỗi người chơi chỉ có một hệ thống chiến lược hữu hạn là {đấm, lá, kéo}.
Nếu không thỏa mãn điều kiện trên, một hệ thống chiến lược sẽ được định nghĩa là vô hạn. Ví dụ, một buổi đấu giá với các mức tăng giá thầu được quy định trước sẽ có vô số chiến lược không liền mạch thuộc hệ thống chiến lược, ví dụ {$10, $20, $30,...}. Trong trường hợp khác, ví dụ như trò chơi cắt bánh (một người cắt bánh thành 2 phần cho mình và cho đối phương, cắt lớn hay nhỏ tùy ý, và đối phương có quyền đồng ý với phần được chia hay đạp đổ), hệ thống chiến lược của trò chơi này có khoảng giới hạn chiến lược, nhưng lại có vô số giá trị liên tiếp {Chia bánh theo bất kì tỉ lệ nào mình muốn, từ 0% đến 100% chiếc bánh}.
Trong trò chơi động, một hệ thống chiến lược bao gồm những nguyên tắc nhất định mà người chơi có thể đặt ra cho rô bốt hoặc một người đại diện, để hướng dẫn họ chơi trò chơi. Ví dụ, trong trò chơi tối hậu thư, hệ thống chiến lược của người chơi thứ hai sẽ bao gồm các nguyên tắc đề nghị nào có thể chấp nhận, đề nghị nào cần từ chối.
Trong trò chơi Bayes, hệ thống chiến lược cũng tương tự như trong trò chơi động. Hệ thống bao gồm các nguyên tắc chỉ ra hành động nào cần thực hiện, trong bất kì trường hợp thông tin nào.
Lựa chọn hệ thống chiến lược[sửa | sửa mã nguồn]
Trong ngành ứng dụng lý thuyết trò chơi, định nghĩa hệ thống chiến lược là một phần quan trọng để có thể xây dựng nên một trò chơi có thể giải được khi người chơi ra quyết định tại cùng một thời điểm, và trò chơi đó phải thực sự có ý nghĩa.
Ví dụ, nếu nói cho chính xác, trong trò chơi Tối hậu thư, một người chơi có thể có các chiến lược như sau: Từ chối giá đề nghị là ($1, $3, $5,..., $19), chấp nhận giá đề nghị là ($0, $2, $4,..., $20). Để liệt kê tất cả những chiến lược này cần không gian chiến lược rộng và cách xử lý vấn đề khá phức tạp. Thay vào đó, nhà nghiên cứu lý thuyết trò chơi có thể giới hạn hệ thống chiến lược thành: {Từ chối tất cả các mức giá ≤ x, chấp nhận tất cả các mức giá > x; với mọi giá trị x trong khoảng tập hợp ($0, $1, $2,..., $20)}.
Chiến lược thuần túy và chiến lược hỗn hợp[sửa | sửa mã nguồn]
Một chiến lược thuần túy đưa ra định nghĩa trọn vẹn về cách mà người chơi tham gia trò chơi. Rõ ràng hơn, nó xác định hành động mà người chơi sẽ thực hiện trong bất kì tình huống nào người đó phải đối mặt. Một hệ thống chiến lược của người chơi là một loạt các chiến lược thuần túy mà người chơi đó có thể thực hiện.
Một chiến lược hỗn hợp là cách gán xác suất cho từng chiến lược thuần túy. Điều này cho phép người chơi lựa chọn ngẫu nhiên một chiến lược thuần túy. Vì biểu diễn xác suất là liên tục, nên sẽ có vô số chiến lược hỗn hợp mà người chơi có thể thực hiện.
Đương nhiên, người ta có thể coi một chiến lược thuần túy là một trường hợp của chiến lược hỗn hợp, tại đó một chiến lược thuần túy nhất định sẽ được chọn với xác suất bằng 1 và tất cả các chiến lược khác được chọn với xác suất bằng 0.
Một chiến lược thuần túy hoàn toàn là chiến lược thuần túy, tại đó người chơi gán một xác suất dương cho mỗi chiến lược thuần túy (Chiến lược thuần túy hoàn toàn rất quan trọng khi tinh giản các thế cân bằng, ví dụ như Thế cân bằng hoàn hảo)
Chiến lược hỗn hợp[sửa | sửa mã nguồn]
Ví dụ[sửa | sửa mã nguồn]
| A | B | |
|---|---|---|
| A | 1, 1 | 0, 0 |
| B | 0, 0 | 1, 1 |
Xét bảng thu hoạch đề cập ở trên (thường được gọi là trò chơi hợp tác). Tại đây một người chơi chọn hành động theo hàng ngang và người chơi còn lại chọn theo cột dọc. Người chơi theo hàng ngang sẽ nhận được khoản thu hoạch đứng trước, người chơi theo cột dọc sẽ nhận khoản thu hoạch thứ hai. Nếu người chơi theo hàng chọn thực hiện hành động A với xác suất là 1 (tức là, người chơi chắc chắn sẽ thực hiện A), thì hành động của người đó được gọi là chiến lược thuần túy. Nếu người chơi theo cột chọn cách tung đồng xu, và sẽ thực hiện A nếu đồng xu lật ngửa, và thực hiện B nếu đồng xu lật sấp, khi đó hành động của người chơi được gọi là chiến lược hỗn hợp, không phải chiến lược thuần túy.
Điểm đáng chú ý[sửa | sửa mã nguồn]
Trong bài nghiên cứu rất nổi tiếng của mình, John Forbes Nash đã chứng minh, tất cả các trò chơi hữu hạn đều sẽ đạt được thế cân bằng. Người ta có thể chia thế cân bằng Nash thành hai loại. Thế cân bằng Nash với chiến lược thuần túy là những thế cân bằng Nash, tại đó tất cả người chơi đều thực hiện chiến lược thuần túy. Thế cân bằng Nash với chiến lược hỗn hợp là các thế cân bằng mà tại đó ít nhất một người chơi thực hiện chiến lược hỗn hợp. Trong khi Nash chứng minh rằng tất cả các trò chơi hữu hạn đều đạt được cân bằng Nash, điều đó không có nghĩa tất cả các trò chơi đó đều đạt được cân bằng Nash với chiến lược thuần túy. Xem thêm ví dụ về trò chơi KHÔNG đạt được cân bằng Nash với chiến lược thuần túy tại đây Matching pennies. Tuy nhiên, rất nhiều trò chơi vẫn đạt được cân bằng Nash với chiến lược thuần túy (ví dụ, Trò chơi hợp tác, Song đề tù nhân). Thêm vào đó, nhiều trò chơi vẫn đạt được thế cân bằng với cả chiến lược thuần túy và chiến lược hỗn hợp.
Khái niệm gây tranh cãi[sửa | sửa mã nguồn]
Trong những năm 1980, khái niệm chiến lược hỗn hợp đã bị chỉ trích nặng nề vì không phù hợp với trực giác cảm tính thông thường.[2] Chọn lựa theo xác suất ngẫu nhiên là điểm quan trọng nhất của chiến lược hỗn hợp, được coi là thiếu bằng chứng dựa trên hành vi thực tế. Hiếm khi người ta đưa ra lựa chọn hoàn toàn dựa vào xổ số ngẫu nhiên. Vấn đề nằm ở hành vi của con người, nhận thức của con người hầu như không thể tự mình đưa ra một kết quả ngẫu nhiên, mà không có thiết bị hỗ trợ, ví dụ như máy làm giả kết quả ngẫu nhiên.[2]
Năm 1991,[3] nhà nghiên cứu lý thuyết trò chơi Ariel Rubinstein đưa ra một số cách hiểu khác về khái niệm này. Cách hiểu đầu tiên, theo Harsanyi (1973), [4] được gọi là "tinh lọc", khái niệm này cho rằng cách diễn giải chiến lược hỗn hợp chỉ phản ánh việc chúng ta thiếu hiểu biết về thông tin mà người chơi đã nắm được và quá trình quyết định của người chơi. Rõ ràng là, lựa chọn ngẫu nhiên được coi là hệ quả của các nhân tố ngoại lai không rõ ràng và không liên quan đến kết quả thu được. Tuy nhiên, người ta không hài lòng với những kết quả bị ảnh hưởng bởi các nhân tố không rõ ràng.[3]
Cách hiểu thứ hai đề ra trường hợp tưởng tượng là những người tham gia trò chơi là đại diện cho một nhóm rất đông người. Mỗi người trong số đó sẽ chọn một chiến lược thuần túy, và kết quả thu được phụ thuộc vào tỉ lệ bao nhiêu người chọn chiến lược nào. Do đó, chiến lược hỗn hợp thể hiện cách phân bố chiến lược thuần túy mà mỗi nhóm người đã chọn. Tuy nhiên cách hiểu này không đưa ra được lời giải thích hợp lý trong trường hợp người chơi là từng cá nhân.
Sau này, Aumann and Brandenburger (1995), [5] đã nhìn nhận lại vấn đề này, ông cho rằng thế cân bằng Nash là khái niệm cân bằng trong niềm tin của người chơi, chứ không cân bằng ở hành động mà họ thực hiện. Ví dụ, trong trò chơi oẳn tù tì, cân bằng trong niềm tin của người chơi sẽ khiến mỗi người chơi tin rằng đối phương sẽ lựa chọn mỗi chiến lược với xác suất là như nhau. Tuy nhiên, cách hiểu này làm giảm khả năng dự đoán của Cân bằng Nash, vì trong thế cân bằng này, hoàn toàn có thể xảy ra trường hợp cả hai người chơi đều chọn chiến lược thuần túy là ra Đấm.
Từ trước tới nay, các nhà nghiên cứu lý thuyết trò chơi đều tỏ thái độ rất mâu thuẫn đối với các kết quả sử dụng chiến lược hỗn hợp. Chiến lược hỗn hợp vẫn được sử dụng rộng rãi do nó giúp đem lại cân bằng Nash trong những trò chơi không thể đạt được thế cân bằng với chiến lược thuần túy, nhưng mô hình này không chỉ rõ vì sao người chơi phải đưa ra lựa chọn ngẫu nhiên và họ phải lựa chọn ngẫu nhiên như thế nào.
Chiến lược hành vi[sửa | sửa mã nguồn]
Trong khi chiến lược hỗn hợp gán một phân bố xác suất cho các chiến lược thuần túy, chiến lược hành vi gán một phân bố xác suất cho hệ thống các hành động có thể thực hiện tại mỗi khối thông tin. Mặc dù hai khái niệm này khá gần gũi với nhau trong trường hợp trò chơi được biểu diễn dưới dạng chuẩn tắc (normal form), nhưng trong các trò chơi dạng mở rộng (extensive form), hai khái niệm này lại ám chỉ những ý nghĩa rất khác nhau. Về cơ bản, một chiến lược hỗn hợp sẽ lựa chọn ngẫu nhiên một đường dẫn nhất định chạy dọc theo cây trò chơi, trong khi một chiến lược hành vi có thể chỉ đưa ra một đường dẫn ngẫu nhiên.
Mối quan hệ giữa chiến lược hỗn hợp và chiến lược hành vi được đề cập đến trong Đinh lý Kuhn. Kết quả nói lên rằng, trong bất kì trò chơi dạng mở rộng hữu hạn nào, với bộ nhớ hoàn hảo (tại mỗi thời điểm đưa ra quyết định hành động, người chơi đều nhớ hết và phân tích hết các hành động đã xảy ra trước đó, để có quyết định sáng suốt nhất), đối với mỗi người chơi và mỗi chiến lược hỗn hợp, sẽ tồn tại một chiến lược hành vi sao cho tại đó, so với tất cả các hồ sơ chiến lược của đối phương, phân bố xác suất của các nốt quyết định cuối cùng sẽ giống hệt như phân bố xác suất của chiến lược hỗn hợp tương ứng. Đồng thời điều ngược lại cũng đúng.
Có một ví dụ rất nổi tiếng giải thích tại sao lại cần đến bộ nhớ hoàn hảo trong trường hợp này, đó là trò chơi Tài xế hay quên của Piccione và Rubinstein (1997).
Xem thêm[sửa | sửa mã nguồn]
- Cân bằng Nash
- Haven (graph theory)
- Evolutionarily stable strategy
Tham khảo[sửa | sửa mã nguồn]
- ^ Ben Polak Game Theory: Lecture 1 Transcript ECON 159, ngày 5 tháng 9 năm 2007, Open Yale Courses.
- ^ a b Aumann, R. (1985). “What is Game Theory Trying to accomplish?” (PDF). Trong Arrow, K.; Honkapohja, S. (biên tập). Frontiers of Economics. Oxford: Basil Blackwell. tr. 909–924.
- ^ a b Rubinstein, A. (1991). “Comments on the interpretation of Game Theory”. Econometrica. 59 (4): 909–924. JSTOR 2938166.
- ^ Harsanyi, John (1973), “Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points”, Int. J. Game Theory, 2: 1–23, doi:10.1007/BF01737554
- ^ Aumann, Robert; Brandenburger, Adam (1995), “Epistemic Conditions for Nash Equilibrium”, Econometrica, The Econometric Society, 63 (5): 1161–1180, doi:10.2307/2171725, JSTOR 2171725