Cách giải (lý thuyết trò chơi)

Trong lý thuyết trò chơi, cách giải được định nghĩa là một nguyên tắc chính thống, dùng để dự đoán trò chơi sẽ diễn ra như thế nào. Những dự đoán này được gọi là "lời giải"; trong lời giải sẽ miêu tả những chiến lược được người chơi lựa chọn, và theo đó là cả kết quả của trò chơi. Những cách giải thường được sử dụng nhất là các khái niệm cân bằng, nổi tiếng nhất là cân bằng Nash.

Đa phần các cách giải, trong nhiều trò chơi, sẽ tìm được nhiều hơn một lời giải. Điều này khiến ta phải đặt ra nghi vấn lời giải nào có giá trị, do đó các nhà nghiên cứu lý thuyết trò chơi có thể áp dụng một số cách tinh giản để giảm bớt số lượng lời giải tìm được. Mỗi cách giải được trình bày sau đây sẽ lần lượt cải thiện cách giải trước đó, bằng cách loại bỏ các thế cân bằng vô hiệu trong những trò chơi phức tạp hơn.

Định nghĩa chính thức

Coi $\Gamma$ là nhóm tất cả các trò chơi, và đối với mỗi trò chơi $G\in \Gamma$, coi $S_{G}$ là tập hợp các hồ sơ chiến lược của $G$. Một cách giải là một phần của tích $\Pi _{G\in \Gamma }2^{S_{G}};$ ví dụ, hàm $F:\Gamma \rightarrow \bigcup \nolimits _{G\in \Gamma }2^{S_{G}}$ sao cho $F(G)\subseteq S_{G}$ đối với mọi$G\in \Gamma .$

Tính lý trí và thế áp đảo lặp

Trong cách giải này, người chơi được coi như hành động theo lý trí, và do đó, các chiến lược bị áp đảo hoàn toàn sẽ bị loại bỏ khỏi tập hợp các chiến lược có thể được thực hiện. Một chiến lược bị áp đảo hoàn toàn khi có những chiến lược khác mà tại đó người chơi luôn luôn nhận được khoản thu hoạch cao hơn, không cần tính đến các chiến lược mà đối thủ lựa chọn. (các chiến lược bị áp đảo hoàn toàn cũng rất quan trọng trong cây trò chơi Tối thiểu hóa khoản thu hoạch tối đa - minimax). Ví dụ, trong trò chơi song đề tù nhân (chỉ chơi một lượt duy nhất) (được trình bày dưới đây), chiến lược hợp tác bị áp đảo hoàn toàn bởi chiến lược Bất hợp tác đối với cả hai người chơi, vì mỗi người đều được lợi hơn khi chọn Bất hợp tác, không cần biết đến lựa chọn của đối phương.

Tù nhân 2 Hợp tác	Tù nhân 2 Bất hợp tác
Tù nhân 1 Hợp tác	−0.5, −0.5	−10, 0
Tù nhân 1 Bất hợp tác	0, −10	−2, −2

Cân bằng Nash

Thế cân bằng Nash là một hồ sơ chiến lược (một hồ sơ chiến lược chỉ rõ từng chiến lược cho mỗi người chơi, ví dụ trong trò chơi Song đề tù nhân ở trên, hồ sơ chiến lược (Hợp tác, Bất hợp tác) chỉ ra Tù nhân 1 sẽ chọn Hợp tác và Tù nhân 2 sẽ chọn Bất hợp tác), trong đó mỗi chiến lược đều là phản ứng tốt nhất đối với những chiến lược khác được thực hiện. Một chiến lược của mỗi người chơi được coi là phản ứng tốt nhất đối với chiến lược của đối thủ, nếu không có chiến lược nào khác có thể thực hiện và thu được khoản lợi nhuận lớn hơn trong bất kì trường hợp nào sử dụng đến chiến lược mà đối thủ đã chọn.

Quy nạp ngược

Có những trò chơi có nhiều thế cân bằng Nash, trong số đó có một số thế cân bằng không thể diễn ra trong thực tế. Trong trường hợp trò chơi động, những thế cân bằng không thực tế có thể bị loại bỏ khi áp dụng quy nạp ngược, tại đó ta giả dụ các diễn tiến trò chơi trong tương lai đều hợp lý. Do đó cách giải này sẽ loại bỏ những mối đe dọa vô căn cứ, bởi nếu người chơi cố tình thực hiện những mối đe dọa này, hành động của người chơi là phi lý trí, vi phạm giả định ở trên.

Ví dụ, xét một trò chơi động, tại đó các người chơi là một công ty đang độc chiếm một ngành công nghiệp và một công ty đang có ý định tham gia ngành công nghiệp đó. Như vậy, công ty lớn có thế độc quyền trong ngành công nghiệp và không muốn mất bớt thị phần về tay công ty mới nổi. Nếu công ty mới chọn cách không tham gia, lợi nhuận của công ty lớn sẽ cao (giữ được thế độc quyền) và công ty mới không lợi cũng không hại (lợi nhuận bằng không). Nếu công ty mới chọn tham gia, công ty lớn có thể cạnh tranh hoặc dàn hòa với công ty mới. Công ty lớn sẽ cạnh tranh bằng cách giảm giá, đẩy công ty mới đến phá sản (và phải chịu phí tổn để ra khỏi thị trường - phải chịu lợi nhuận âm) và đồng thời cũng làm hại đến lợi nhuận của bản thân. Nếu công ty lớn dàn hòa với công ty mới, công ty lớn sẽ mất bớt một phần doanh số, nhưng vẫn giữ được giá cao và nhận được lợi nhuận cao hơn là khi giảm giá để cạnh tranh (nhưng vẫn thấp hơn lợi nhuận khi độc quyền)

Nếu công ty mới tham gia thị trường, phản ứng tốt nhất của công ty lớn là dàn hòa. Nếu công ty lớn dàn hòa, phản ứng tốt nhất của công ty mới là tham gia thị trường (và thu lợi nhuận). Khi đó hồ sơ chiến lược tại đó công ty lớn chọn dàn hòa nếu công ty mới tham gia thị trường, và công ty nhỏ tham gia thị trường nếu công ty lớn dàn hòa sẽ là một thế cân bằng Nash. Tuy nhiên nếu công ty lớn chọn cách cạnh tranh, phản ứng tốt nhất của công ty mới là không tham gia thị trường. Nếu công ty mới không tham gia thị trường, không cần quan tâm công ty lớn chọn gì (vì không có công ty nào khác để lựa chọn chiến lược - chú ý một điểm là nếu công ty nhỏ không tham gia thị trường, cạnh tranh hay dàn hòa đều dẫn đến cũng một mức lợi nhuận cho cả hai người chơi; công ty lớn sẽ không giảm giá nếu công ty mới không tham gia). Khi đó cạnh tranh có thể được coi là phản ứng tốt nhất của công ty lớn nếu công ty nhỏ không tham gia thị trường. Do đó hồ sơ chiến lược tại đó công ty lớn cạnh tranh nếu công ty nhỏ không tham gia thị trường và công ty nhỏ không tham gia nếu công ty lớn cạnh tranh cũng là một thế cân bằng Nash. Vì đây là trò chơi động, mỗi khi công ty lớn tuyên bố cạnh tranh đều là đe dọa suông, vì khi tới thời điểm công ty lớn phải ra quyết định có cạnh tranh hay không (ví dụ, khi công ty mới đã tham gia thị trường), quyết định cạnh tranh sẽ là phi lý. Do đó, thế cân bằng Nash này có thể bị loại bỏ bằng quy nạp ngược

Xem thêm

• Monetary policy theory
• Stackelberg competition

Cân bằng Nash trong phân đoạn trò chơi hoàn hảo

Phân đoạn trò chơi hoàn hảo là một cách khái quát hóa quy nạp ngược. Quy nạp ngược dùng giả định rằng tất cả các diễn biến trò chơi trong tương lai đều hợp lý. Trong các thế cân bằng hoàn hảo của phân đoạn trò chơi, các diễn tiến trò chơi trong từng phân đoạn đều hợp lý (đặc biệt là thế cân bằng Nash). Quy nạp ngược chỉ có thể dùng để loại bỏ bớt (một số có giới hạn) các trò chơi diễn ra trong khoảng thời gian nhất định, và không áp dụng được với các trò chơi với thông tin không hoàn hảo. Trong những trường hợp này, có thể sử dụng phân đoạn trò chơi hoàn hảo. Những thế cân bằng Nash bị loại bỏ được nhắc đến ở ví dụ trên là những trường hợp phân đoạn trò chơi không hoàn hảo, bởi vì, chúng không phải là thế cân bằng Nash của phân đoạn trò chơi bắt đầu tại thời điểm công ty mới nổi tham gia thị trường.

Cân bằng Bayes hoàn hảo

Có nhiều lúc, phân đoạn trò chơi hoàn hảo không thể giới hạn được hết các kết quả phi lý. Ví dụ, vì phân đoạn trò chơi không thể cắt ngang một khối thông tin (information set), một trò chơi với thông tin không hoàn hảo có thể chỉ có một phân đoạn trò chơi duy nhất - là toàn bộ trò chơi - do đó không thể dùng phân đoạn trò chơi hoàn hảo để loại bỏ bất kì thế cân bằng Nash nào. Thế cân bằng Bayes hoàn hảo (Perfect Bayesian equilibrium - PBE) là cách miêu tả các chiến lược của người chơi và niềm tin về các nốt trong khối thông tin đã xảy ra trong diễn tiến trò chơi tại thời điểm đó. Một niềm tin về một nốt quyết định, là xác suất mà một người chơi nhất định nghĩ rằng nốt đó được hoặc sẽ được thực hiện (tức là, nốt đó thuộc về đường cân bằng). Để nói chi tiết hơn, có một cách suy luận trực giác về Cân bằng Bayes hoàn hảo, đó là, thế cân bằng này chỉ rõ các chiến lược phù hợp với người chơi, với điều kiện cho trước là niềm tin của người chơi đã được nói rõ, vầ niềm tin này hoàn toàn thống nhất với các chiến lược đã được nêu ra.

Trong trò chơi Bayes, một chiến lược sẽ xác định hành động mà người chơi thực hiện tại mọi khối thông tin thuộc quyền kiểm soát của người chơi đó. Phân đoạn trò chơi hoàn hảo không yêu cầu rõ rệt là niềm tin phải thống nhất với chiến lược. Do đó, Cân bằng Bayes hoàn hảo sẽ đạt điều kiện thống nhất khi xét theo niềm tin của người chơi. Điều này có nghĩa là, đối với mỗi niềm tin của người chơi tại một khối thông tin, không có chiến lược nào khác có thể đem lại lợi nhuận dự tính cao hơn cho người chơi đó. Không như những cách giải đã nói ở trên, không có chiến lược nào của người chơi là bị áp đảo hoàn toàn ngay từ đầu tại bất kì khối thông tin nào, ngay cả khi nó không rơi vào đường cân bằng. Do đó, trong Cân bằng Bayes hoàn hảo, người chơi không thể đe dọa thực hiện những chiến lược bị áp đảo hoàn toàn tại điểm đầu của khối thông tin nằm ngoài đường cân bằng.

Cụm từ "Bayes" trong tên Cân bằng Bayes hoàn hảo nhấn mạnh vào việc người chơi sẽ cập nhật niềm tin của mình theo Nguyên tắc Bayes. Họ tính toán xác suất với điều kiện cho trước là những diễn tiến đã xảy ra trước đó trong trò chơi

Quy nạp xuôi

Quy nạp xuôi được đặt tên như vậy bởi vì, cũng như quy nạp ngược giả định mọi diễn tiến trò chơi trong tương lai đều hợp lý, quy nạp xuôi giả định mọi diễn biến trò chơi trong quá khứ đều là hợp lý. Nếu một người chơi không biết kiểu người chơi của đối phương (ví dụ như: khi có thông tin không hoàn hảo và không cân xứng), người chơi đó có thể đặt ra niềm tin về kiểu người chơi của đối phương bằng cách quan sát hành động của đối phương trong quá khứ. Do đó, niềm tin do người chơi đó đặt ra về kiểu người chơi của đối thủ sẽ dựa vào diễn tiến trong quá khứ, tại đó coi như đối phương hành động theo lý trí. Một người chơi có thể đánh tin hiệu về kiểu người chơi của bản thân thông qua hành động mình thực hiện.

Kohlberg và Mertens (1986) đã giới thiệu cách giải Thế cân bằng tĩnh, một cách tinh giản thỏa mãn logic của Quy nạp xuôi. Người ta đã tìm ra một phản ví dụ, tại đó thế cân bằng tĩnh không thỏa mãn quy nạp ngược. Để giải quyết vấn đề này, Jean-François Mertens giới thiệu một khái niệm mà ngày nay các nhà nghiên cứu lý thyết trò chơi gọi tên là Thế cân bằng tĩnh Mertens, đây có thể là cách giải đầu tiên thỏa mãn cả quy nạp xuôi và quy nạp ngược.

Xem thêm

• Extensive form game
• Trembling hand equilibrium
• "The Intuitive Criterion" (ChoKreps1987)

Tham khảo

• Cho, I-K.; Kreps, D. M. (1987)."Signaling Games and Stable Equilibria".Quarterly Journal of Economics 102 (2): 179–221. doi:10.2307/1885060. 
• Fudenberg, Drew; Tirole, Jean (1991).Game theory Lưu trữ 2012-10-08 tại Wayback Machine. MIT Press.ISBN 978-0-262-06141-4. .
• Harsanyi, J. (1973) Oddness of the number of equilibrium points: a new proof. International Journal of Game Theory 2:235–250.
• Govindan, Srihari & Robert Wilson, 2008. "Refinements of Nash Equilibrium," The New Palgrave Dictionary of Economics, 2nd Edition.[1] Lưu trữ 2010-06-20 tại Wayback Machine
• Hines, W. G. S. (1987) Evolutionary stable strategies: a review of basic theory. Theoretical Population Biology 31:195–272.
• Kohlberg, Elon & Jean-François Mertens, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-37, September.
• Leyton-Brown, Kevin; Shoham, Yoav (2008).Essentials of Game Theory: A Concise, Multidisciplinary Introduction. San Rafael, CA: Morgan & Claypool Publishers.ISBN 978-1-59829-593-1. 
• Mertens, Jean-François, 1989. "Stable Equilibria - A reformulation. Part 1 Basic Definitions and Properties," Mathematics of Operations Research, Vol. 14, No. 4, Nov. [2]
• Noldeke, G. & Samuelson, L. (1993) An evolutionary analysis of backward and forward induction. Games & Economic Behaviour 5:425–454.
• Maynard Smith, J. (1982) Evolution and the Theory of Games. ISBN 0-521-28884-3
• Osborne, Martin J.; Rubinstein, Ariel (1994).A course in game theory. MIT Press.ISBN 978-0-262-65040-3. .
• Selten, R. (1983) Evolutionary stability in extensive two-person games. Math. Soc. Sci. 5:269–363.
• Selten, R. (1988) Evolutionary stability in extensive two-person games – correction and further development. Math. Soc. Sci. 16:223–266
• Shoham, Yoav; Leyton-Brown, Kevin (2009).Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press.ISBN 978-0-521-89943-7. 
• Thomas, B. (1985a) On evolutionary stable sets. J. Math. Biol. 22:105–115.
• Thomas, B. (1985b) Evolutionary stable sets in mixed-strategist models. Theor. Pop. Biol. 28:332–341