Bài giảng Lý thuyết nâng cao: chiến lược hỗn hợp và sự tồn tại cân bằng

CHƯƠNG IV

LÝ THUYẾT NÂNG CAO:

CHIẾN LƯỢC HỖN HỢP VÀ SỰ TỒN TẠI CÂN BẰNG

Giới thiệu : Chiến lược hỗn hợp

 Chúng ta đã Si là tập hợp các chiến lược của

đấu thủ i ,

 tổ hợp các chiến lược (s1*,…sn*) là cân bằng

NASH nếu với mỗi đấu thủ i si* là phản ứng tốt nhất đối với n-1 đấu thủ còn lại.

 Theo định nghĩa này sẽ không có cân bằng

NASH nào trong trò chơi sau đây

Trò chơi đọ xu – không có cân bằng chiến lược thuần tuý

Đấu thủ 2

Sấp

Ngửa

-1 , 1

1 , -1

Sấp

Đấu thủ 1

Ngửa

1 , -1

-1 ,1

Nhận xét

 Trong trò chơi này tập hợp chiến lược của mỗi

đấu thủ là {ngửa, sấp}

 Nhưng nếu người chơi không phải sẽ chơi ngửa hoặc sấp mà sẽ chơi ngửa với xác suất p và sấp với xác suất là q=1-p thì ta sẽ có khái niệm về chiến lược hỗn hợp

Giải thích chiến lược hỗn hợp

 Một chiến lược hỗn hợp đối với đấu thủ i là

một phân phối xác suất trên (một số hay tất cả) các chiến lược trong tập các chiến lược của i  Điều quan trọng hiểu chiến lược hỗn hợp ở đây là tập hợp các xác suất gắn với chiến lược thuần sao cho mỗi chiến lược thuần có một xác suất chơi dương và tổng xác suất ứng với tất cả các chiến lược thuần phái bằng 1.

Định nghĩa chiến lược hỗn hợp

 Định nghĩa:  Một chiến lược hỗn hợp đối với đấu thủ i là

một phân phối xác suất trên (một số hoặc tất cả) các chiến lược trong si.

 Một cách hình thức có thể định nghĩa: Trong trò chơi dạng chuẩn G. Khi đó một chiến

lược hỗn hợp đối với đấu thủ i là một phân phối xác suất pi=(pi1,..…pik) vơi 0pik1, pi1+…+pik=1

Thí dụ

Đấu thủ 2

Sấp

Ngửa

-1 , 1

1 , -1

Sấp

Đấu thủ 1

Ngửa

1 , -1

-1 ,1

Giải thích

 Một chiến lược của hỗn hợp của đấu thủ 1 là

một phân phối xác suất trên các chiến lược {sấp , ngửa} chẳng hạn người chơi 1 sẽ chơi sấp với xác suất p và ngửa vơi xác suất 1-p.

 chiến lược của hỗn hợp của đấu thủ 2 là một phân phối xác suất trên các chiến lược {sấp , ngửa} chẳng hạn người chơi 2 sẽ chơi sấp vớp xác suất q và ngửa với xác suất 1-q.

Thí dụ 2: Cuộc chiến giữa 2 giới

Ca nhạc

Đấu bóng

0 , 0

Ca nhạc

2 , 1

Đấu bóng

0 , 0

1 ,2

Giải thích

 Giả sử p1 là xác suất để C chơi chiến lược ca nhạc và 1-p1 là xác suất để C chơi chiến lược đấu bóng

 Giả sử q1 là xác suất để P chơi chiến lược ca nhạc và 1-q1 là xác suất để P chơi chiến lược đấu bóng

Thí dụ Về bài toán tìm chiến lược hỗn hợp

TĐ

2 , 1

0 , 0

TĐ

0 , 0

1 ,2

Giải bài toán cuộc chiến giữa 2 giới

 Tập hợp người chơi chỉ có 2 người là C và P.  Tìm chiến lược hỗn hợp:  (1) Chiến lược hỗn hợp của C: giả sử C chơi Ca nhạc với xác suất p1 và Đấu bóng với xác suất p2 =1-p1

 (2) Chiến lược hỗn hợp của P: Giả sử P chơi ca nhạc với xác suất q2= 1-q1 và xem đấu bóng với xác suất q1.

Phân tích để thiết lập bài toán

 Lợi ích mà C thu được khi chơi chiến lược Ca nhạc là : 2q1+0.q2.Lợi ích mà C thu được khi chơi ĐB là: 0q1+1q2.

 Vậy lợi ích kỳ vọng của C khi chơi chiến lược

hỗn hợp p1,p2 sẽ là:

 p1[2q1+0.q2]+p2[0q1+1q2]  Tương tự lợi ích kỳ vọng của P sẽ là:  q1[1p1+0.p2]+q2[0p1+2p2]

Thiết lập bài toán và giải

 Như vậy bài toán tìm lợi ích kỳ vọng của đấu

thủ hàng sẽ là

 Max p1(2q1+0.q2)+p2(0.q1+1.q2)(1)  P1+p2=1 , pi không âm  Max q1(1p1+0.p2)+q2(0.p1+1.p2)(2)  q1+ q2=1 , qi không âm  Cách giải: Thay p1=1-p2 và (1) và q1=1-q2 vào (2) và giải ta sẽ được chiến lược hỗn hợp cân bằng Nash

Thiết lập bài toán trong trường hợp tổng quát

 Xét trò chơi với 2 đấu thủ1 và 2. Gọi S1, S2 là không

gian chiến lược của đấu thủ 1 và 2 tương ứng.  Gọi J là số chiến lược thuần trong S1, K là số chiến

lược thuần trong S2.Nghĩa là:

 S1={s11,…., s1J} và S2={s21,…., s2K}  Giả sử đấu thủ 1 tin rằng đấu thủ 2 chơi các chiến lược {s21,…., s2K} với xác suất ={p21,…., p2K}, thì thu hoạch kỳ vọng của đấu thủ 1 từ việc chơi chiến lược thuần túy s1j là:

Thiết lập bài toán trong trường hợp tổng quát

 thì thu hoạch kỳ vọng của đấu thủ 1 từ việc

)

k 2

s 2 k

sup (

 1

chơi chiến lược thuần túy s1j là:

 thì thu hoạch kỳ vọng của đấu thủ 1 từ việc

chơi chiến lược hỗn hợp là: K J

)



)

ppv ,( 1 1 2

sup ( 11 j 2 k

s 2 k

supp ( j 11 2 k 1 j

s 2 k

 (*)

  p 1 j



 1 j

 1

 j 1

 1 k

Thu hoạch kỳ vọng của đấu thủ 2

 Thu hoạch kỳ vọng của đấu thủ 2 từ việc chơi chiến

lược thuần túy s2k là:

)

s 2 k

 1

sup ( j 2  thì thu hoạch kỳ vọng của đấu thủ 2 từ việc chơi

chiến lược hỗn hợp là:



)



)

ppv ,( ) 2 1 2

sup ( j 12 1 j

s 2 k

supp ( 1 j j 12 2 k

s , 2 k

 p 2 k



 (**)

 1 k

 1

 1 j

 1 k

Điều kiện của cân bằng

 Khi cho v1(p1,p2) vµ v2(p1,p2) ta cã thÓ ph¸t biÓu l¹i ®ßi hái cña c©n b»ng Nash r»ng chiÕn lîc hçn hîp cña mçi ®Êu thñ lµ mét ph¶n øng tèt nhÊt ®èi víi chiÕn lîc hçn hîp cña ®Êu thñ kia: ®Ó cÆp chiÕn lîc hçn hîp (p*1,p*2) lµ mét cÊn b»ng Nash, p*1 ph¶i tho¶ m·n

v1(p*1,p*2)  v1(p1,p*2)

  ®èi víi mäi ph©n phèi x¸c suÊt p1 trªn S1, vµ p2 ph¶i

tho¶ m·n

 v2(p*1,p*2)  v2(p*1,p2)  ®èi víi mäi ph©n phèi x¸c suÊt p2 trªn S2.

Định nghĩa : cân bằng NASH chiến lược hỗn hợp

 Trong trß ch¬i d¹ng chuÈn hai ®Êu thñ  G = {S1,S2;u1,u2}, c¸c chiÕn lîc hçn hîp

(p*1,p*2) lµ mét c©n b»ng Nash nÕu chiÕn lîc hçn hîp cña mçi ®Êu thñ lµ mét ph¶n øng tèt nhÊt ®èi víi chiÕn lîc hçn hîp cña ®Êu thñ kia: (*) vµ (**) ph¶i ®óng.

Định lý: NASH (1950)

 Trong trò chơi dạng chuẩn N đấu thủ

G={S1,…,Sn;u1,…,un}, nếu n hữu hạn và Si là hữu hạn đối với mọi i thì tồn tại tít nhất một cân bằng NASH , có thể gắn với các chiến lược hỗn hợp

Bài tập thực hành

 Tìm chiến lược hỗn hợp cân bằng Nash cho các

bài toán sau:  Trò chơi đọ xu  Tình thế khó xử của hai người tù  Trò chơi trừu tượng

Chương V

Trò chơi tĩnh với thông tin không đầy đủ

 Giới thiệu: Chương này bắt đầu nghiên cứu về

các trò chơi với thông tin không đầy đủ, còn gọi là các trò chơi Bayes.

 Hãy nhớ lại rằng trong một trò chơi với thông tin đầy đủ, các hàm thu hoạch của các đấu thủ là kiến thức chung.

 Trái lại, trong một trò chơi với thông tin không đầy đủ, ít nhất có một đấu thủ không chắc chắn về hàm thu hoạch của các đấu thủ khác.

Giới thiệu

 Thí dụ: Trò chơi đấu giá bằng phiếu kín: Mỗi người trả giá biết sự đánh giá của mình đối với hàng hoá bán đấu giá nhưng không biết sự đánh giá của người trả giá nào khác; người trả giá bỏ mức giá mình trả trong những phong bì niêm phong kín để nộp, do vậy có thể coi là các đấu thủ đi cùng lúc.

 Tuy nhiên, hầu hết các trò chơi Bayes thú vị về kinh tế là trò chơi động. Như ta sẽ thấy , sự tồn tại thông tin của riêng tự nhiên dẫn tới những mưu toan để giao thiệp (hoặc đánh lừa) của các bên được thông tin và mưu toan học hỏi và phản ứng của bên không được thông tin. Đây vốn là những vấn đề động.

Lý thuyết: Các trò chơi Bayes tĩnh và cân bằng Nash Bayes

 Thí dụ: Cạnh tranh Cournot trong điều kiện thông tin không

đối xứng

 Hãy xét mô hình Cournot có hai công ty độc quyền với hàm ngược của cầu cho bởi P(Q) = a- Q, ở đây Q = q1+q2 là tổng lượng trên thị trường.

 Hàm chi phí của công ty 1 là C1(q1) = cq1. Hàm chi phí của công ty

2 là C2(q2) = cHq2 với xác xuất  và C2(q2) = cLq2 với xác xuất 1- ở đây cL < cH.

 Thêm nữa, thông tin là không đối xứng: công ty 2 biết hàm chi phí của nó và của công ty 1 nhưng công ty 1 biết hàm chi phí của nó và chỉ biết rằng chi phí biên của công ty 2 là cH với xác xuất  và cL với xác xuất 1-.

 Tất cả điều này là kiên thức chung: công ty 1 biết rằng công ty 2 có

thông tin trội hơn, công ty 2 biết rằng công ty 1 biết đièu này, v.v...

Thí dụ: Cạnh tranh Cournot trong điều kiện thông tin không đối xứng

 Nếu chi phí biên cao, công ty 2 có thể muốn chọn một lượng khác (có lẽ thấp hơn) với trường hợp nếu chi phí biên thấp. Về phần mình, công ty 1 hẳn sẽ đoán rằng công ty 2 có thể thay đổi lựa chọn về lượng của nó hợp với chi phí theo cách này.

 Cho q*2(cH) và q*2(cL) ký hiệu lựa chọn lượng của công ty 2 như một hàm của chi phí, và cho q*1 ký hiệu lựa chọn lượng duy nhất của công ty 1. Nếu chi phí của công ty 2 là cao, nó sẽ chọn q*2(cH) là nghiệm

max [(a-q*1-q2)- cH]q2 q2

   Tương tự, nếu chi phí của công ty 2 là thấp, q*2(cL) là nghiệm  

max [(a-q*1-q2)- cL]q2 q2

Thí dụ: Cạnh tranh Cournot trong điều kiện thông tin không đối xứng

 Cuối cùng, công ty 1 biết rằng chi phí của công ty 2 là cao với xác xuất  và sẽ đoán rằng lựa chọn lượng của công ty 2 sẽ là q*2(cH) hoặc q*2(cL) tuỳ thuộc chi phí của công ty 2. Như vậy công ty 1 chọn q*1 là nghiệm

 max  [(a-q1-q*2(cH))- c]q1 + (1-) [(a-q1-q2(cL))- c]q1  q1  để cực đại hoá lợi nhuận kỳ vọng.Điều kiện cấp một đối với ba bài

toán tối ưu này là

q*2(cH) = (a-q*1- cH) / 2, q*2(cL) = (a-q*1- cL) / 2,

   và  q* = {  [a-q*2(cH)- c] + (1-) [a-q2(cL)- c] }/2

Thí dụ: Cạnh tranh Cournot trong điều kiện thông tin không đối xứng

 Giả sử rằng các điều kiện cấp một này định rõ đặc

điểm của các nghiệm bài các toán trước đây. (Nhớ lại từ Bài toán 1.6 rằng trong mô hình hai công ty độc quyền kiểu Cournot với thông tin đầy đủ, nếu chi phí của các công ty đủ khác nhau thì ở cân bằng, công ty có chi phí cao không sản xuất gì. Như một bài tập, hãy tìm một điều kiện đủ để bác bỏ các bài toán tương tự ở đây.) Các nghiệm đối với ba điều kiện cấp một là

 q*1(cH) = (1/3)(a-2 cH +C) +(1-) (CH-CL)/6  q*2(cH) = (1/3)(a-2 cL +C) +(1-) (CH-CL)/6  và q*1 ={(a-2c+ CH +C)+(1-) CL)}/8

Thí dụ: Cạnh tranh Cournot trong điều kiện thông tin không đối xứng

 So sánh q*2(cH), q*2(cL) và q*1 với cân bằng Cournot trong điều kiện thông tin đầy đủ với chi phí c1 và c2. Giả sử rằng các giá trị c1 và c2 là các giá trị sao cho các lượng cân bằng của cả hai công ty là dương, công ty i sản xuất q*i=(a-2ci +cj)/3 trong trường hợp thông tin đầy đủ này. Trái lại, trong trường hợp thông tin không đầy đủ, q*2(cH) lớn hơn (a-2cH +c)/3 và q*2(cL) nhỏ hơn (a-2cL +c)/3. Điều này xảy ra bởi vì công ty 2 không chỉ thay đổi lượng sản xuất theo chi phí của nó mà còn phản ứng với thực tế là công ty 1 không thể làm như vậy.

Thí dụ: Cạnh tranh Cournot trong điều kiện thông tin không đối xứng

2 .)

 Thí dụ, nếu chi phí của công ty 2 cao thì nó sản xuất ít đi vì chi phí của nó cao nhưng cũng sản xuất nhiều lên vì nó biết rằng công ty 1 sẽ sản xuất một lượng làm cực đại lợi nhuận kỳ vọng của 1 và như vậy nhỏ hơn lượng 1 sẽ sản xuất nếu nó biết chi phí của công ty 2 cao.  (Một đặc điểm có tiềm năng gây lầm lẫn của thí dụ này là q*1 đúng bằng kỳ vọng của lượng Cournot mà công ty 1 sẽ sản xuất trong hai trò chơi tương ứng với thông tin đầy đủ. Điều này điển hình là không đúng; Thí dụ, hãy xét trường hợp trong đó tổng chi phí của công ty i là ciqi

Kiểu và không gian kiểu

 Nhớ lại rằng, biểu diễn dạng chuẩn của trò chơi n đấu thủ với thông tin đầy đủ là G = {S1 ... Sn;u1 ... un}, ở đây Si là không gian chiến lược của đấu thủ i và ui(s1,...,sn) là thu hoạch của đấu thủ i khi các đấu thủ chọn các chiến lược (s1,...,sn).

 Tuy nhiên, như đã thảo luận trong một trò chơi đi cùng lúc với thông

tin đầy đủ một chiến lược đối với một đấu thủ đơn giản là một hành động, do vậy ta có thể viết G = {A1 ... An;u1 ... un}, ở đây Ai là không gian hành động của đấu thủ i và ui(a1,...,an) là là thu hoạch của đấu thủ i khi các đấu thủ chọn các hành động (a1,...,an).

 Để chuẩn bị cho mô tả của chúng ta về trình tự của trò chơi tĩnh với

thông tin không đầy đủ, ta mô tả trình tự của trò chơi tĩnh với thông tin đầy đủ như sau: (1) các đấu thủ chọn các hành động cùng lúc (đấu thủ i chọn ai từ tập khả thi Ai), và rồi (2) nhận được thu hoạch ui(a1,...,an).

Kiểu và không gian kiểu

 Bây giờ ta muốn phát triển biểu diễn dạng chuẩn của trò chơi đi cùng lúc với thông tin không đầy đủ, còn gọi là trò chơi Bayes tĩnh.

 Bước thứ nhất là biểu diễn tư tưởng là mỗi đấu thủ biết hàm thu hoạch của mình nhưng có thể không chắc chắn về hàm thu hoạch của các đấu thủ khác.

 Cho hàm thu hoạch có thể của đấu thủ i biểu thị bởi

ui(a1,...,an;ti), ở đây ti được gọi là kiểu của đấu thủ i và thuộc một tập hợp các kiểu có thể (hay không gian kiểu) Ti.

 Mỗi kiểu ti tương ứng với một hàm thu hoạch khác

nhau mà đấu thủ i có thể có.

Kiểu và không gian kiểu

 Thí dụ giả sử đấu thủ i có hai hàm thu hoạch có thể.  Ta sẽ nói rằng đấu thủ i có hai kiểu, ti1 và ti2 , rằng không gian kiểu của đấu thủ i là T={ti1,ti2}, và rằng hai hàm thu hoạch của đấu thủ i là ui(a1,...,an;ti1) và ui(a1,...,an;ti2).  Ta có thể sử dụng ý tưởng rằng mỗi trong các kiểu của

một đấu thủ tương ứng với một hàm thu hoạch khác nhau mà đấu thủ có thể có để biểu thị khả năng là đấu thủ đó có thể có các tập hợp hành động khả thi khác nhau như sau.

Kiểu và không gian kiểu

 Thí dụ, giả sử rằng tập hợp hành động khả thi của đấu thủ i là {a, b} với xác xuất q và {a, b, c} với xác xuất 1-q.

 Thì ta có thể nói rằng i có hai kiểu (ti1 và ti2, ở đây xác xuất của ti1 là q) và ta có thể định nghĩa tập hành động khả thi của i là {a, b, c} đối với cả hai kiểu nhưng định nghĩa thu hoạch từ việc chọn thực hiện hành động c là - đối với kiểu ti1.

Thí dụ

 Như một thí dụ cụ thể hơn, xét trò chơi Cournot trong mục trước. Các hành động của các công ty là những lựa chọn lượng của họ, q1 và q2. Công ty 2 có hai hàm chi phí có thể và do vậy có hai hàm lợi nhuận hoặc thu hoạch có thể:

(cid:0)2(q1,q2;cL) = [(a- q1- q2)- cL]q2

(cid:0)2(q1,q2;cH) = [(a- q1- q2)- cH]q2 .

(cid:0)1(q1,q2;c) = [(a- q1- q2)- c]q1 .

  và   Công ty 1 chỉ có một hàm thu hoạch có thể:   Chúng ta nói rằng không gian kiểu của công ty 2 là T2 = {CL,CH}

và rằng không gian kiểu của công ty 1 là T1 = {C}.

Thí dụ

 Khi đã cho định nghĩa về kiểu của một đấu thủ, nói rằng đấu thủ i biết hàm thu hoạch của mình là tương đương với nói rằng đấu thủ i biết kiểu của mình.  Cũng như vậy, nói rằng đấu thủ i có thể không chắc

chắn về hàm thu hoạch của các đấu thủ khác là tương đương với nói rằng đấu thủ i có thể không chắc chắn về kiểu của các đấu thủ khác,

 ký hiệu bởi t-i=(t1,...,ti-1,ti+1,...,tn). Ta sử dụng T-i để biểu thị tập hợp tất cả các giá trị có thể của t-i, và sử dụng phân bố xác suất pi(t-i|ti) để biểu thị mức tin tưởng của đấu thủ i về các kiểu của các đấu thủ khác, t-i, khi đã cho kiến thức của đấu thủ i về kiểu của mình, ti.

Thí dụ

 Trong mọi ứng dụng phân tích (và trong hầu hết tài liệu), các kiểu của các đấu thủ là độc lập, trong trường hợp đó pi(t-i|ti) không phụ thuộc vào ti, do đó ta có thể viết mức tin tưởng của đấu thủ i là pi(t-i).

 Tuy nhiên, có những khung cảnh trong đó các kiểu của các đấu thủ tương quan với nhau, do vậy ta cho phép thể hiện điều đó trong định nghĩa của ta về trò chơi Bayes tĩnh bằng việc viết mức tin tưởng của đấu thủ i là pi(t-i|ti).

 Kết nối các khái niệm mới về kiểu, và mức tin tưởng với

những yếu tố quan trọng của biểu diễn dạng chuẩn của trò chơi tĩnh với thông tin đầy đủ cho ta biểu diễn dạng chuẩn của trò chơi Bayes tĩnh.



Biểu diễn dạng chuẩn của một trò chơi Bayes tĩnh

 Định nghĩa: Biểu diễn dạng chuẩn của một trò chơi

Bayes tĩnh n đấu thủ chỉ rõ các không gian hành động của các đấu thủ A1,...,An, các không gian kiểu của họ T1,...,Tn, các mức tin tưởng của họ p1,...,pn, và các hàm thu hoạch của họ u1,...,un. Kiểu của đấu thủ i, ti , được biết riêng bởi đấu thủ i, quyết định hàm thu hoạch của đấu thủ i, ui(a1,...,an;ti), và là một phần tử của tập các kiểu T i. Mức tin tưởng của đấu thủ i, pi(t-i|ti), mô tả sự không chắc chắn về các kiểu có thể của n-1 đấu thủ khác, t-i, khi đã cho kiểu của i, ti. Ta ký hiệu trò chơi này là G = {A1,...,An; T1,...,Tn; p1,...,pn; u1,...,un}.

Giải thích

 Theo cách của Harsanyi (1967), ta sẽ giả sử rằng trình

tự của một trò chơi Bayes tĩnh là như sau:

 (1) tạo hoá rút một véc tơ kiểu t = (t1,...,tn), ở đây ti

được rút từ tập hợp các kiểu có thể Ti;

 (2) tạo hoá tiết lộ ti cho đấu thủ i nhưng không tiết lộ

cho bất cứ đấu thủ nào khác;

 (3) các đấu thủ chọn hành động cùng lúc, đấu thủ i

chọn ai từ tập khả thi Ai; và rồi

 (4) các đấu thủ nhận các thu hoạch ui(a1,...,an;ti).

Giải thích

 Bằng việc đưa vào các nước đi tưởng tượng đi bởi tạo hoá trong các bước (1) và (2), ta đã mô tả một trò chơi với thông tin không đầy đủ như một trò chơi với thông tin không hoàn hảo, ở đây ta ngụ ý thông tin không hoàn hảo (như ở Chương 2) nghĩa là đến một nước đi nào đó trong trò chơi, đấu thủ đến lượt đi không biết toàn bộ lịch sử của trò chơi đến lúc đó.

 Ở đây, vì tạo hoá tiết lộ kiểu của đấu thủ i cho đấu thủ i nhưng không tiết lộ cho đấu thủ j ở bước (2), đấu thủ j không biết toàn bộ lịch sử của trò chơi khi các hành động được chọn ở bước (3).

Giải thích

 Có hai điểm hơi có tính kỹ thuật hơn cần được bao trùm để hoàn thành thảo luận của ta về các biểu diễn dạng chuẩn của các trò chơi Bayes tĩnh.  Thứ nhất, có những trò chơi trong đó đấu thủ i có thông tin riêng không chỉ về hàm thu hoạch của mình mà cả về hàm thu hoạch của các đấu thủ khác.

 Thí dụ, trong mô hình Cournot với thông tin đối xứng từ được thay đổi sao cho các chi phí là kiến thức chung và đối xứng nhưng một công ty biết mức cầu và công ty kia không biết.

Giải thích

 Vì mức cầu ảnh hưởng lên hàm thu hoạch của cả hai đấu thủ, kiểu của công ty được thông tin hiện thân vào hàm thu hoạch của công ty không được thông tin.

 Trong trường hợp n đấu thủ, ta nắm bắt khả năng này bằng việc cho phép thu hoạch của đấu thủ i phụ thuộc vào các hành động (a1,...,an) mà còn phụ thuộc tất cả các kiểu (t1,...,tn). Ta viết thu hoạch này là ui(a1,...,an;t1,...,tn).



Giải thích

 Điểm kỹ thuật thứ hai liên quan đến mức tin

tưởng, pi(t-i|ti). ta sẽ giả sử rằng một kiến thức chung là ở bước (1) trong trình tự của trò chơi Bayes tĩnh, tạo hoá rút một véc tơ kiểu  t = (t1,...,tn) theo phân phối xác xuất tiên

nghiệm p(t).

 Khi tạo hoá tiết lộ ti cho đấu thủ i, anh hay chị

ta có thể tính mức tin tưởng pi(t-i|ti) theo quy tắc Bayes:

Giải thích

 Thêm nữa, các đấu thủ khác có thể tính các mức tin

tưởng khác mà đấu thủ i có thể có, phụ thuộc và kiểu của i, cụ thể là pi(t-i|ti) đối với mỗi ti trong Ti.

 Như đã nói, ta sẽ thường xuyên giả định rằng các kiểu của các đấu thủ là độc lập, trong trường hợp đó pi(t-i) không phụ thuộc vào ti nhưng vẫn được rút ra từ phân phối tiên nghiệm p(t).

 Trong trường hợp này các đấu thủ khác biết mức tin

tưởng của đấu thủ i về kiểu của họ.

Định nghĩa cân bằng chiến lược

 Bây giờ ta muốn định nghĩa một khái niệm cân bằng đối với các trò chơi Bayes tĩnh. Để làm việc đó, trước hết ta phải định nghĩa các không gian chiến lược của các đấu thủ trong một trò chơi như vậy. Nhớ lại rằng chiến lược của một đấu thủ là toàn bộ kế hoạch hành động chỉ ra một hành động khả thi trong mọi tình huống bất ngờ trong đó đấu thủ đến lượt hành động. Khi đã cho trình tự của trò chơi Bayes tĩnh trong đó tạo hoá bắt đầu trò chơi bằng việc rút thăm các kiểu của các đấu thủ, một chiến lược (thuần tuý) đối với đấu thủ i phải chỉ ra hành động khả thi đối với mỗi trong các kiểu có thể của đấu thủ i.

 Định nghĩa: Trong trò chơi Bayes tĩnh G = {A1,...,An; T1,...,Tn;

p1,...,pn; u1,...,un}, một chiến lược đối với đấu thủ i là một hàm si(ti), ở đây đối với mỗi kiểu ti trong Ti, si (ti) chỉ ra hành động từ tập khả thi Ai mà kiểu ti sẽ chọn nếu được rút bởi tạo hoá.

Không gian chiến lược không được cho trong biểu diễn dạng chuẩn

 Không giống như các trò chơi với thông tin đầy đủ, trong một trò chơi Bayes các không gian chiến lược không được cho trong biểu diễn dạng chuẩn của trò chơi.

 Thay vì như vậy, trong một trò chơi Bayes tĩnh, các không gian chiến lược được xây dựng từ các không gian kiểu và các không gian hành động: tập hợp chiến lược (thuần tuý) có thể của đấu thủ i, Si, là tập hợp của tất cả các hàm có thể với miền xác định Ti và miền giá trị Ai.

Không gian chiến lược không được cho trong biểu diễn dạng chuẩn

 Thí dụ, trong chiến lược phân biệt, mỗi kiểu ti trong Ti

chọn một hành động ai từ Ai.

 Trái lại, trong chiến lược gộp (pooling) tất cả cá kiểu chọn cùng một hành động. Sự khác biệt này giữa các chiến lược phân biệt và đổ đồng sẽ quan trọng trong thảo luận của ta về các trò chơi động với thông tin không đầy đủ.

 Ta đưa sự phân biệt vào đây chỉ để giúp mô tả sự khác nhau rộng lớn của các chiến lược có thể đưọc xây dựng từ một cặp không gian kiểu và không gian hành động đã cho, Ti và Ai.

Giải thích hành vi

 Có thể hình như không chắc chắn khi đòi hỏi chiến

lược của đấu thủ i chỉ ra hành động khả thi đối với mỗi kiểu có thể của đấu thủ i. Sau hết, một khi mà tạo hoá đã rút thăm một kiểu và tiết lộ cho một đấu thủ, có thể hình như là đấu thủ đó không cần quan tâm đến những hành động mà anh hay chị ta sẽ làm nếu tạo hoá rút được một kiểu nào đó khác.

 Mặt khác, đấu thủ i cần xem xét cái mà các đấu thủ

khác sẽ làm, và cái họ sẽ làm phụ thuộc vào cái mà họ nghĩ là đấu thủ i sẽ làm đối với mỗi ti trong Ti. Như vậy, trong việc quyết định sẽ làm gì một khi một kiểu đã được rút, đấu thủ i sẽ phải nghĩ về cái mà anh hay chị ta nên làm nếu mỗi trong các kiểu khác trong T được rút.

Thí dụ

 Xét trò chơi Cournot với thông tin không đối xứng trong. Ta đã lập luận rằng lời giải đối với trò chơi bao gồm ba lựa chọn lượng: q*2(CH), q*2(CL) và q*1. Theo định nghĩa về một chiến lược vừa cho, cặp (q*2(CH), q*2(CL)) là chiến lược của công ty 2 và q*1 là chiến lược của công ty 1. Dễ dàng tưởng tượng rằng công ty 2 sẽ chọn các lượng khác nhau tuỳ thuộc chi phí của nó.

 Tuy nhiên, cũng quan trọng để lưu ý rằng việc chọn lượng đơn lẻ

của công ty 1 phải tính đến là lượng của công ty 2 sẽ phụ thuộc chi phí của 2 theo kiểu đó. Như vậy, nếu khái niệm cân bằng của chúng ta đòi hỏi rằng chiến lược của công ty 1 là phản ứng tốt nhất đối với chiến lược của công ty 2 thì chiến lược của công ty 2 phải là một cặp lượng, một lượng đối với mỗi kiểu chi phí có thể, nếu không thì công ty 1 đơn giản không thể tính toán chiến lược của nó có quả thực là một phản ứng tốt nhất đối với chiến lược của công ty 2 hay không.

Thí dụ

 Tổng quát hơn, ta sẽ không thể áp dụng khái niệm cân bằng Nash vào các trò chơi Bayes nếu ta cho phép chiến lược của một đấu thủ không chỉ rõ đấu thủ đó sẽ làm gì nếu một vài kiểu được rút bởi tạo hoá.

 Lập luận này tương tự với lập luận là: Có thể dường như

không cần thiết đòi hỏi chiến lược của đấu thủ i trong một trò chơi động với thông tin đầy đủ phải chỉ rõ một hành động khả thi đối với mỗi tình huống trong đó đấu thủ i đến lượt đi, nhưng ta không thể áp dụng khái niệm cân bằng Nash vào các trò chơi động với thông tin đầy đủ nếu ta cho phép chiến lược của một đấu thủ có những hành động trong một số tình huống còn không định rõ.

Định nghĩa cân bằng Nash Bayes

 Định nghĩa: Trong trò chơi Bayes tĩnh G =

),...,

));

* tsu (( 1 i 1

tpt (  i i

* s ),...  t 1

* sa ,  t 1 i

* ts ( nn

t ( t

t )/ i

 1

 1

{A1,...,An; T1,...,Tn; p1,...,pn; u1,...,un}, các chiến lược s*=(s*1,...,s*n) là một cân bằng Nash Bayes (chiến lược thuần tuý) nếu đối với mỗi i và đối với mỗi một kiểu của i, ti trong Ti, s*i (ti) là nghiệm của bài toán   Max Aa i i

Tt    i i



Giải thích

 Nghĩa là, không đấu thủ nào muốn thay đổi chiến lược của mình, ngay cả nếu thay đổi đó chỉ liên quan đến một hành động bởi một kiểu.

 Dễ dàng chỉ ra rằng, trong một trò chơi Bayes tĩnh (nghĩa là, một trò chơi trong đó n là hữu hạn và (A1,...,An) và (T1,...,Tn) tất cả đều là tập hữu hạn), có tồn tại một cân bằng Nash Bayes, có lẽ trong các chiến lược hỗn hợp.

 Chứng minh này song song và gần gũi với chứng

minh về sự tồn tại một cân bằng Nash là chiến lược hỗn hợp trong tò chơi lặp với thông tin đầy đủ và do đó ở đây ta bỏ qua.

Chương 6: Ứng dụng của trò chơi tĩnh với thông tin không đầy đủ

 Nhắc lại về các chiến lược hỗn hợp  Harsanyi (1973) gợi ý rằng chiến lược hỗn hợp của đấu thủ j biểu thị sự không chắc chắn của đấu thủ i về lựa chọn chiến lược thuần tuý của j, và rằng lựa chọn của j đến lượt nó lại phụ thuộc sự nhận thức một lượng nhỏ thông tin riêng.

 Bây giờ ta có thể cho một phát biểu chính xác hơn ý tưởng này:

một cân bằng Nash chiến lược hỗn hợp trong một trò chơi với thông tin đầy đủ có thể được diễn giải như một cân bằng Nash Bayes chiến lược thuần tuý trong một trò chơi liên quan mật thiết có thông tin hơi không đầy đủ.

 Nói một cách dễ liên tưởng hơn, đặc điểm cốt yếu của một cân bằng Nash chiến lược hỗn hợp không phải là đấu thủ j chọn một chiến lược một cách ngẫu nhiên mà đúng hơn là đấu thủ i không chắc chắn về lựa chọn của đấu thủ j; sự không chắc chắn này có thể nảy sinh hoặc do sự ngẫu nhiên hoá hoặc (đáng tin cậy hơn) là do thông tin hơi không đầy đủ, như trong thí dụ sau đây.

Nhắc lại về các chiến lược hỗn hợp

 Nhớ lại rằng trong cuộc chiến giữa hai giới, có hai cân bằng Nash chiến lược thuần tuý (ca nhạc, ca nhạc) và (Trận đấu, Trận đấu) và một cân bằng Nash chiến lược hỗn hợp trong đó C chơi ca nhạc với xác suất 2/3 và P chơi Trận đấu với xác suất 2/3.

 ( Viết lại ma trận thu hoạch)

Nhắc lại về các chiến lược hỗn hợp

 Bây giờ giả sử rằng, mặc dù họ đã biết nhau khá lâu, C và P không hoàn toàn chắc chắn về thu hoạch của nhau. Nói riêng, giả sử rằng: thu hoạch của C nếu cả hai đi xem ca nhạc là 2+tc, ở đây tc chỉ riêng C biết; thu hoạch của P nếu cả hai đi xem Trận đấu là 2+tp; ở đây tp chỉ riêng P biết; và tc và tp là những rút thăm độc lập từ một phân bố đều trên [0,x].

 Tất cả các thu hoạch khác y như cũ. Trong các thuật ngữ của trò

chơi Bayes tĩnh trừu tượng dưới dạng chuẩn G = {Ac,Ap;Tc,Tp;pc,pp;uc,up}, , các không gian hành động là Ac = Ap = {Ca nhạc, Trận đấu}, các không gian kiểu là Tc = Tp =[0,x], các mức tin tưởng là pc(tp) = pp(tc) = 1/x đối với mọi tc và tp, và các thu hoạch như sau:

Ma trận thu hoạch

Ca nhạc

Trận đấu

ca nhạc

2+ tc,1

0,0

Trận đấu

0,0

1,2+ tp

ĐẤU GIÁ

 Xét cuộc đấu giá bằng phiếu kín lấy giá cao nhất sau đây. Có hai người trả giá ký hiệu là 1, 2.  Người trả giá i đánh giá giá trị của hàng hoá được đấu giá là vi - nghĩa là, nếu người trả giá i mua được hàng hoá đó và trả giá p thì thu hoạch của i là vi- p.

 Những đánh giá của hai người trả giá có phân phối

đều và độc lập trên đoạn [0,1].

 Các mức trả giá quy định là không âm.  Những người trả giá nộp mức trả giá của họ cùng

lúc.



ĐẤU GIÁ

 Người trả giá cao hơn sẽ giành được hàng hoá và phải trả với giá mà chị ta đặt; người kia không nhận được gì và không phải trả gì.

 Trong trường hợp hoà nhau, người chiến

thắng được quyết định bằng cách gieo đồng xu.

 Những người trả giá trung gian với chuyện

may rủi (risk-neutral)

ĐẤU GIÁ

 Tất cả điều đó là kiến thức chung.  Để hình thành bài toán này như một trò chơi Bayes tĩnh, ta phải nhận dạng các không gian hành động, các không gian kiểu, các mức tin tưởng và các hàm thu hoạch.

 Hành động của đấu thủ i là nộp một mức trả giá (không âm)

và kiểu của chị ta là đánh giá của chị ta, vi.

 (Trong trò chơi trừu tượng G = {A1,A2; T1,T2; p1,p2; u1,u2}, không gian hành động là Ai = [0,] và không gian kiểu là Ti = [0, 1].) Vì các đánh giá là độc lập, đấu thủ i tin rằng vj có phân phối đều trên [0, 1], giá trị của vj không thành vấn đề.



Hàm thu hoạch của đấu thủ i





b i

)

v i ( v i

b i b i

;



 Cuối cùng, hàm thu hoạch của đấu thủ i là





, vvbbu 2 2 i

b i

 2  b



b i

     v  

Cân bằng Nash của trò chơi

 Trong một cân bằng Nash Bayes, chiến lược b1(v1) của đấu thủ 1 là một phản ứng tốt nhất đối với chiến lược b2(v2) của đấu thủ 2 và ngược lại.

 Nói một cách hình thức, cặp chiến lược (b1(v1), b2(v2)) là một cân bằng Nash Bayes nếu đối với mỗi vi trong [0,1], bi(vi) là nghiệm:











))



 )

 bPb ) i i

vb ( j

v ( i

bPb () i i

vb ( j

vMax ( b i

1 2

Lời giải bài toán đấu giá

 Giả sử đấu thủ j theo chiến lược b(.), và giả sử rằng b(.) là tăng ngặt và khả vi. Thì đối với một giá trị đã cho của vi, mức trả giá tối ưu của đấu thủ i là nghiệm

 max (vi-bi) Prob{bi > b(vj)} .   Cho b-1(bj) ký hiệu đánh giá mà đấu thủ j phải có để

đặt mức trả giá bj. Nghĩa là, b-1(bj) = vj nếu bj = b(vj). vì vj có phân phối đều trên [0, 1], Prob{bi > b(vj)} = Prob{b-1(bj) > vj} = b-1(bi). Do đó, điều kiện cấp một đối với bài toán tối ưu của đấu thủ i là



- b-1(bi) + (vi-bi) db-1(bi)/dbi = 0 .

Lời giải bài toán đấu giá

 Điều kiện cấp một này là một phương trình ẩn đối với phản ứng tốt nhất của đấu thủ i trước chiến lược b(.) chơi bởi đấu thủ j, khi cho rằng đánh giá của đấu thủ i là vi.

 Nếu chiến lược b(.) là một cân bằng Nash Bayes đối

xứng, ta đòi hỏi rằng nghiệm của điều kiện cấp một là b(vi): nghĩa là đối với mỗi đánh giá dương của người trả giá i, người trả giá i không muốn chệch khỏi chiến lược b(.), khi cho rằng người trả giá j chơi chiến lược này. Để làm theo đòi hỏi này, ta thay bi= b(vi) vào điều kiện cấp một, cho ta



- b-1(bi) + (vi-b(vi)) db-1(b(vi))/dbi = 0 .

Lời giải bài toán đấu giá

 Tất nhiên, b-1(b(vi) đơn giản là vi. Thêm nữa,

d{b-1(b(vi))}/dbi = 1/b’(vi). Nghĩa là,

 d{b-1(b(vi))}/dbi đo mức đánh giá của người trả giá i thay đổi bao nhiêu để dẫn đến một dơn vị thay đổi trong mức trả giá, còn

 b’(vi) đo những thay đổi mức trả giá tương ứng một đơn vị thay đổi trong mức đánh giá. Như vậy, b(.) phải thoả mãn phương trình vi phân cấp một

 - vi + (vi-b(vi)) (1/b’(vi)) = 0 .

Lời giải bài toán đấu giá

 Nó có thể biểu diễn thuận tiện hơn dưới dạng  b’(vi)vi + b(vi) =vi. Vế trái của phương trình vi phân này chính xác là d{b(vi)vi}/dvi. Do đó, lấy tích phân hai vế của phương trình cho ta

2 + k,

b(vi) vi = (1/2) vi

  ở đây, k là hằng số tích phân. Để khử k, ta cần một

điều kiện biên. May thay, lý giải kinh tế đơn giản cho ta: không có đấu thủ nào trả giá cao hơn đánh giá của anh hay chị ta. Như vậy, ta đòi hỏi b(vi)  vi đối với mọi vi. Nói riêng, ta đòi hỏi b(0)  0, như vậy k = 0 và b(vi) = vi/2 như đã nói trên.

Bài tập tình huống

 Giả sử chính phủ định xây dựng một con đường cao tốc từ A đến B. Chính phủ tiến hành lựa chọn nhà thầu theo cách:

 Bỏ phiếu kín  Người bỏ phiếu với giá thấp nhất sẽ trúng thầu  (a) Hãy phân tích trò chơi này với giả thiết bạn là người tham gia đấu thầu và theo ước tính của bạn, công ty bạn sẽ có thể hoàn thành đoạn đường đó không dưới 10 triệu đô la

Nguyªn t¾c tiÕt lé

 Nguyªn t¾c tiÕt lé, do Myerson (1979) trong bèi

c¶nh trß ch¬i Bayes, lµ mét c«ng cô quan träng ®Ó thiÕt kÕ c¸c trß ch¬i khi c¸c ®Êu thñ cã th«ng tin riªng.

 Nã cã thÓ ®îc ¸p dông trong c¸c bµi to¸n ®Êu gi¸ vµ mua b¸n song ph¬ng ®· m« t¶ trong hai môc tríc, còng nh trong mét líp réng c¸c bµi to¸n kh¸c.

 Trong môc nµy, ta ph¸t biÓu vµ chøng minh nguyªn

t¾c tiÕt lé ®èi víi c¸c trß ch¬i Bayes tÜnh.

C¬ chÕ trùc tiÕp

 Ngêi b¸n cã thÓ sö dông nguyªn t¾c tiÕt lé ®Ó đ¬n gi¶n ho¸ ®¸ng kÓ vÊn ®Ò nµy theo hai c¸ch.

 Thø nhÊt, ngêi b¸n cã thÓ giíi h¹n sù quan

 Nh÷ng ngêi tr¶ gi¸ cïng lóc khai nhËn (cã thÓ kh«ng trung thùc) vÒ kiÓu cña hä (nghÜa lµ ®¸nh gi¸ cña hä).

 Ngêi tr¶ gi¸ i cã thÓ khai nhËn kiÓu bÊt kú i tõ tËp kh¶ thi Ti, gi¸ trÞ ®óng ti lµ bao nhiªu kh«ng thµnh vÊn ®Ò.

C¬ chÕ trùc tiÕp

 Khi ®· cho c¸c khai nhËn cña nh÷ng ngêi tr¶ gi¸ (1,...,n), ®Êu thñ i tr¶ xi(1,...,n) vµ nhËn hµng ho¸ víi x¸c xuÊt qi(1,...,n).

 §èi víi mçi tæ hîp cã thÓ cã cña c¸c khai nhËn (1,...,n), tæng c¸c x¸c suÊt qi(1,...,n)+ ... +qn(1,...,n) ph¶i nhá h¬n hoÆc b»ng 1.  C¸c trß ch¬i lo¹i nµy (nghÜa lµ c¸c trß ch¬i

Bayes tÜnh trong ®ã hµnh ®éng duy nhÊt cña mçi ®Êu thñ lµ nép khai nhËn vÒ kiÓu cña anh hay chÞ ta) ®îc gäi lµ c¸c c¬ chÕ trùc tiÕp.

®éng c¬ khuyÕn khÝch t¬ng thÝch.

 C¸ch thø hai mµ ngêi b¸n cã thÓ sö dông

nguyªn t¾c tiÕt lé lµ giíi h¹n sù quan t©m vµo nh÷ng c¬ chÕ trùc tiÕp trong ®ã ®èi víi mçi ngêi ch¬i nãi thËt lµ mét c©n b»ng Nash Bayes – nghÜa lµ c¸c hµm thu hoạch vµ x¸c xuÊt {x1(1,...,n), ..., xn(1,...,n); q1(1,...,n),...,qn(1,...,n)} ®Ó chiÕn lîc c©n b»ng ®èi víi mçi ®Êu thñ i lµ khai nhËn i(ti) = ti ®èi víi mçi ti trong Ti.

 Mét c¬ chÕ trùc tiÕp trong ®ã nãi thËt lµ mét

Giải thích  Ngoµi lÜnh vùc thiÕt kÕ ®Êu gi¸, nguyªn t¾c tiÕt lé còng cã thÓ ®îc sö dông theo hai c¸ch nµy. BÊt kú mét c©n b»ng Nash Bayes cña bÊt kú mét trß ch¬i Bayes ®Òu cã thÓ ®îc biÓu diÔn bëi mét c©n b»ng Nash Bayes míi trong mét trß ch¬i Bayes míi ®îc chän mét c¸ch thÝch hîp, ë ®©y “biÓu diÔn” cã nghÜa lµ ®èi víi mçi tæ hîp cã thÓ cã cña c¸c kiÓu cña c¸c ®Êu thñ (t1,...,tn), c¸c hµnh ®éng vµ c¸c thu ho¹ch cña c¸c ®Êu thñ trong c©n b»ng míi ®ång nhÊt víi c¸c hµnh ®éng vµ thu ho¹ch trong c©n b»ng cò.

 Dï trß ch¬i ban ®Çu lµ g×, trß ch¬i Bayes míi lu«n lµ mét c¬ chÕ trùc tiÕp; dï c©n b»ng ban ®Çu lµ g×, c©n b»ng míi trong trß ch¬i míi lu«n lµ nãi thËt. Nãi mét c¸ch h×nh thøc h¬n:

§Þnh lý (Nguyªn t¾c tiÕt lé):

 BÊt kú mét c©n b»ng Nash Bayes cña bÊt kú mét trß ch¬i Bayes ®Òu cã thÓ ®îc biÓu diÔn bëi mét c¬ chÕ trùc tiÕp cã ®éng c¬ khuyÕn khÝch t¬ng thÝch.

Thí dụ: Phân tích trò chơi đấu giá

 Chính phủ tiến hành đấu giá xây dựng con

đường cao tốc từ A đến B theo quy tắc thông thường là với yêu cầu kỹ thuật đã cho ai bỏ giá thấp nhất thì người đó sẽ được trúng thầu.  Biết rằng mỗi nhà thầu có thiết bị riêng, cho

nên chi phí để xây dựng con đường đó khôpng giống nhau.

 Về mặt tự nhiên thì có vẻ như là ai có kỹ thuật

tiên tiến với chi phí thấp sẽ trúng thầu

Yêu cầu một cơ chế đấu thầu

 Nhưng các nhà thầu đều có thể nâng giá( không khai thật chi phí của mình- thường khai cao hơn để có thể thu được lợi cao hơn.

 Hãy suy nghĩ để đưa ra chiến lược đấu thầu sao

cho xã hội đỡ tổn thất nhất!