Chương 1
LÝ THUYẾT TRÒ CHƠI
LÝ THUYẾT TRÒ CHƠI
10/6/2012 1MaMH: C02012 Chương 1: Lý thuyết trò chơi
NỘI DUNG
1. Giới thiệu bài toán tổng quát
2. Trò chơi 2 người tổng không
3. Chiến lược thuần túy, chiến lược hỗn hợp
4. Lý thuyết trò chơi dưới dạng QHTT
10/6/2012 2MaMH: C02012 Chương 1: Lý thuyết trò chơi
GIỚI THIỆU BÀI TOÁN TỔNG QUÁT
1. Giới thiệu
−Trò chơi thường có ít hai người chơi và dựa vào
một quy luật đã được đưa ra trước khi bắt đầu trò
chơi. Cuối trò chơi, mỗi người chơi sẽ nhận được
một
thu
hoạch
(payoff)
nào
đó
,
tùy
theo
thỏa
thuận
một
thu
hoạch
(payoff)
nào

hành
động
khác
nhau
để
cố
gắng
làm
tối
đa các kết quả nhận được.
10/6/2012 4MaMH: C02012 Chương 1: Lý thuyết trò chơi
GIỚI THIỆU BÀI TOÁN TỔNG QUÁT
− Lý thuyết trò chơi được ứng dụng trong nhiều
lĩnh vực:
• Kinh tế và kinh doanh: đấu giá, mặc cả…
• Sinh học: phần lợi của trò chơi là sự thích nghi,
ứng
dụng
vào
việc
giải
thích
sự
tiến
hóa
(
và
bền
ứng
dụng

p
=
=
∑
chơi k người tổng 0.
- Trường hợp k = 2, ta có trò chơi 2 người tổng 0.
10/6/2012 6MaMH: C02012 Chương 1: Lý thuyết trò chơi
1
i
=
TRÒ CHƠI 2 NGƯỜI TỔNG 0
Dạng ma trận
- Người chơi thứ nhất (P
1
) có m chiến lược, được
biểu diễn là các hàng của ma trận.
- Người chơi thứ hai (P
2
) có n chiến lược, được
biểu
diễn
là
các
cột
của
ma
trận
.
biểu
diễn

 
 
= =
 
 
⋯ ⋯
⋮
⋯
⋮
P
1
chọn chiến lược i , P
2
chọn chiến lược j và
người này không biết sự lựa chọn của người kia.
Khi đó, P
1
sẽ nhận (P
2
trả ).
10/6/2012 8MaMH: C02012 Chương 1: Lý thuyết trò chơi
1m mj mn
a a a
 
 
 
⋮
ij
a
ij

thứ
i
.
1
{ , , }
m
x x x
=
1
0, 1, , , 1
m
i i
i
x i m x
=
≥ = =
∑
thứ
i
.
10/6/2012 10MaMH: C02012 Chương 1: Lý thuyết trò chơi
CHIẾN LƯỢC THUẦN TÚY
Chiến lược hỗn hợp trong đó , những
thành phần còn lại bằng 0 được gọi là một chiến
lược thuần túy.
i
x
ξ
=
1

i j
A x y x a y xA y
= =
= =
∑∑
ĐỊNH LÝ MINIMAX
Đặt
là giá trị thu được của P
1
,
là giá trị thu được của P
2
.
: maxmin ( , )
I
y Y
x X
V A x y
∈
∈
=
: minmax ( , )
II
y Y
x X
V A x y
∈
∈
=
2



∃ >


• Trong ma trận A, ta nói cột j trội cột l nếu
→ Áp dụng tính trội để rút ngắn cỡ của ma trận A.
10/6/2012 14MaMH: C02012 Chương 1: Lý thuyết trò chơi
,
: .
ij il
ij il
a a i
i a a
≤ ∀



∃ <


CÁCH GIẢI TRÒ CHƠI 2 x 2
Xét ma trận thu hoạch (không có điểm yên ngựa)
Đặt
a b
A
c d
 
=
 

trong hình vẽ. Sau đó, lấy tức là điểm
(đoạn) cao nhất trên đường (gấp khúc) này.
10/6/2012 16MaMH: C02012 Chương 1: Lý thuyết trò chơi
2 1 2 1 1
( ) , 0 1.
j j j j
z a a a x x
= + − ≤ ≤
min
j
j
z
1
maxmin
j
j
x
z
CÁCH GIẢI TRÒ CHƠI 2 x n (tt)
- Giao điểm cho ta nghiệm của bài toán. Cụ thể,
xác định được x
1
, v và x
2
.
- Để tìm chiến lược tối ưu cho , ta
xem điểm cao nhất nhận được là giao của 2 đường
z
nào
,

’
và
j
’’
,
thì
ta
sẽ
có
ma trận cấp 2 x 2 là hai cột tương ứng j
’
và j
’’
của
ma trận A. Giải trò chơi với ma trận này, ta sẽ nhận
được .
- Vậy, ngoại trừ hai giá trị vừa tính được, các
thành phần còn lại của Y sẽ có giá trị là 0.
10/6/2012 17MaMH: C02012 Chương 1: Lý thuyết trò chơi
' ''
,
j j
y y
' ''
,
j j
y y
TRÒ CHƠI m x 2
- Ma trận thu hoạch có m hàng, 2 cột.
→ Cách giải tương tự trò chơi 2 x n.



∑
Vì hàm mục tiêu chưa phải hàm tuyến tính, nên ta
thêm một biến mới p :
10/6/2012 19MaMH: C02012 Chương 1: Lý thuyết trò chơi
1 2
1
0, 1, ,
m
i
x x x
x i m
+ + + =


≥ =

1
min
i ij
j n
p x a
≤ ≤
≤
DẠNG QUY HOẠCH TUYẾN TÍNH
Bài toán trở thành: Tìm p, x
i
sao cho
1



≤



+ + + =

≥ =



∑
⋮
DẠNG QUY HOẠCH TUYẾN TÍNH
Tương tự, bài toán của P
2
: Tìm w, y
j
sao cho
1
1
min
n
j j
j
w
w a y
=



≥ =



∑
⋮
DẠNG QUY HOẠCH TUYẾN TÍNH
(1), (2) có dạng tuyến tính.
→ Dùng phương pháp đơn hình để giải.
10/6/2012 22MaMH: C02012 Chương 1: Lý thuyết trò chơi