Thạc Sĩ Bài toán cân bằng Nash trong không gian có thứ tự

Đề tài: Bài toán cân bằng Nash trong không gian có thứ tự
Lời cảm ơn
Lời đầu tiên, tôi xin chân thành cảm ơn PGS.TS Nguyễn Bích Huy, người thầy đã
nhiệt tình giảng dạy và hướng dẫn tôi hoàn thành bản luận văn.
Xin trân trọng biết ơn các thầy cô thuộc khoa Toán trường Đại học Sư phạm và
Đại học Khoa học Tự nhiên Tp.HCM đã nhiệt tình giảng dạy các chuyên đề và giúp
tôi làm quen với công việc nghiên cứu khoa học.
Xin chân thành cảm ơn Ban giám hiệu, các đồng nghiệp thuộc bộ môn Toán khoa
KHCB trường Đại học Sư phạm Kỹ thuật Tp.HCM đã tạo điều kiện thuận lợi cho tôi
tham gia khóa học này.
Cuối cùng, tôi xin chân thành cảm ơn các thầy cô phòng KHCN-SĐH trường Đại
học Sư phạm Tp.HCM đã giúp đỡ tôi hoàn tất các thủ tục bảo vệ luận văn.
TP.Hồ Chí Minh, ngày 10 tháng 09 năm 2008
Người thực hiện
Phạm Duy Khánh2
Mục lục
Lời cảm ơn 1
Mục lục 2
Mở đầu 3
Chương 1 Bài toán cân bằng Nash trong nửa dàn 6
1.1. Định lý Knaster-Kuratowski-Mazurkiewiez và định lý tách Ky Fan 6
1.2. Bổ đề Ky Fan và định lý điểm bất động Fan-Browder . 10
1.3. Định lý điểm yên ngựa 12
1.4. Định lý về sự tồn tại của điểm cân bằng Nash 16
Chương 2 Bài toán cân bằng Nash trong không gian có thứ
tự 19
2.1. Định lý điểm bất động của ánh xạ đơn trị 19
2.2. Định lý điểm bất động của ánh xạ đa trị . 23
2.3. Định lý điểm bất động trong không gian tích 25
2.4. Bài toán cân bằng Nash trong không gian có thứ tự . 33
Kết luận 38
Tài liệu tham khảo 393
Mở đầu
1. Lý do chọn đề tài
Lý thuyết phương trình toán tử trong không gian có thứ tự ra đời từ những năm
1950 và được hoàn thiện cho đến ngày nay. Chúng tìm được những ứng dụng rộng
rãi trong việc giải quyết các bài toán xuất phát từ Vật lý, Sinh học, Kinh tế .Trong
lý thuyết này việc chứng minh sự tồn tại nghiệm của phương trình dựa chủ yếu vào
phương pháp điểm bất động. Việc sử dụng các định lý điểm bất động trong không
gian có thứ tự vào các bài toán trong kinh tế mới chỉ được nghiên cứu gần đây. Đây là
hướng nghiên cứu mới, có ý nghĩa. Mục đích của luận văn là trình bày ứng dụng các
định lý điểm bất động của ánh xạ đa trị trong không gian có thứ tự vào bài toán cân
bằng Nash xuất phát từ lĩnh vực kinh tế.
2. Mục đích nghiên cứu
Cân bằng Nash (Nash Equilibrium) là một khái niệm của lý thuyết trò chơi (Game
Theory) được John Nash đưa ra với mô hình trò chơi của n đối thủ. Cân bằng Nash
xác định một chiến lược tối ưu cho các trò chơi khi chưa có một điều kiện tối ưu nào
được xác định trước đó. Định nghĩa cơ bản của cân bằng Nash là: Nếu tồn tại một
tập hợp các chiến lược cho một trò chơi với đặc tính là không một đối thủ nào có
thể hưởng lợi bằng cách thay đổi chiến lược hiện tại của mình khi các đối thủ khác
không thay đổi, tập hợp các chiến lược đó và phần thu nhận tương ứng tạo nên cân
bằng Nash. Mô hình này trong toán học được định nghĩa như sau: Xét không gian
tích X =
Q
i∈I Xi và họ các hàm fi
: X → (ư∞, +∞)(i ∈ I). Điểm x
∗ = (x
∗
i
, xˆ
∗
i
) ∈ X
được gọi là điểm cân bằng Nash của họ hàm trên nếu
fi(x
∗
i
, xˆ
∗
i
) = max
ui∈Xi
fi(ui, xˆ
∗
i
)4
trong đó x
∗
i ∈ Xi và xˆ
∗
i ∈ Xˆ
i =
Q
j∈I\i Xj . Để tiếp cận bài toán trên có nhiều phương
pháp khác nhau. Trong luận văn này chúng tôi tiếp cận bằng cách sử dụng các định lý
điểm bất động của ánh xạ đa trị trong không gian có thứ tự để chứng minh sự tồn tại
của điểm cân bằng Nash.
3. Đối tượng và nội dung nghiên cứu
Sử dụng các kết quả về tôpô, giải tích hàm, không gian có thứ tự và các định lý về
điểm bất động trong không gian có thứ tự vào bài toán cân bằng Nash trong không
gian có thứ tự.
4. ý nghĩa khoa học thực tiễn
Cân bằng Nash là khái niệm quan trọng đối với các bài toán trong kinh tế. Việc
mô hình hóa nó thành một bài toán lý thuyết và để giải quyết nó đã đòi hỏi các nhà
toán học tìm ra những phương pháp nghiên cứu mới và các kết quả mới tổng quát, có
ý nghĩa khoa học và có thể áp dụng cho nhiều bài toán khác.
5. Cấu trúc luận văn
Luận văn được phân làm hai chương.
Chương 1. Bài toán cân bằng Nash trong nửa dàn
Chương này trình bày các kết quả mở rộng của định lý KKM, định lý tách Ky Fan,
bổ đề Ky Fan, định lý điểm bất động Fan-Browder và định lý điểm yên ngựa trong
không gian có thứ tự. Sử dụng các kết quả thu được vào việc chứng minh sự tồn tại
của điểm cân bằng Nash trong nửa dàn.5
Chương 2. Bài toán cân bằng Nash trong không gian có thứ tự
Chương này trình bày phương pháp lặp đơn điệu trong không gian có thứ tự. Từ kết
quả trên ta thu được các kết quả về định lý điểm bất động đối với ánh xạ đơn trị và
ánh xạ đa trị. Các kết quả về lý thuyết thu được được sử dụng vào việc khảo sát bài
toán cân bằng Nash trong không gian có thứ tự.6
Chương 1
Bài toán cân bằng Nash trong nửa
dàn
1.1 Định lý Knaster-Kuratowski-Mazurkiewiez và định lý
tách Ky Fan
Định lý KKM cổ điển được ứng dụng trong nhiều lĩnh vực khác nhau của toán
học lý thuyết và ứng dụng. Trong phần này chúng tôi trình bày một mở rộng cho định
lý KKM trong không gian có thứ tự. Kết quả này thu được dựa vào định lý 1.1 trong
[4](C.D. Horvath and J.V.Llinares Ciscar).
Định nghĩa 1.1.1. Cho (X, ≤) là không gian có thứ tự. X gọi là semilattice nếu với mỗi cặp
(x,x
′
) ∈ X ì X đều có một chặn trên nhỏ nhất, kí hiệu x ∨ x
′
.
Định nghĩa 1.1.2. Cho (X, ≤) là không gian có thứ tự semilattice và A ⊆ X là tập hợp hữu
hạn khác rỗng. Tập ∆(A) =
S
a∈A
[a,supA] gọi là bao lồi thứ tự của A. Trong đó, supA là
chặn trên nhỏ nhất của A.
Định nghĩa 1.1.3. Tập E ⊆ X gọi là ∆ưlồi nếu với mỗi A ⊆ E hữu hạn khác rỗng ta có
∆(A) ⊆ E.7
Ví dụ 1.1.1. Đặt X = {(x, 1) : 0 ≤ x ≤ 1}
S
{(x,y) : 0 ≤ y ≤ 1,x ≥ 1,y ≥ x ư 1}. Trên
R2
ta xét quan hệ thứ tự (a,b); (c,d) ∈ R2
: (a,b) ≤ (c,d) ⇔ 0 ≤ d ư b ≤ c ư a. Khi đó X
là ∆-lồi.
Chứng minh. Ta thấy rằng R2
với thứ tự được định nghĩa trên là semilattice. Để chứng minh
X là ∆-lồi ta chỉ cần chứng minh
+ a1,a2 ∈ X ⇒ a1 ∨ a2 ∈ X
+ a1,a2 ∈ X,a1 ≤ a2 ⇒ [a1,a2] ⊆ X
Giả sử a1 = (x1,y1) và a2 = (x2,y2) là hai phần tử bất kỳ thuộc X.
Trường hợp 1. Hai phần tử a1,a2 so sánh được.
Không mất tính tổng quát ta giả sử a1 ≤ a2. Khi đó a1 ∨ a2 = a2 ∈ X. Ta kiểm tra
[a1,a2] ⊆ X. Thật vậy, lấy a = (x,y) là phần tử bất kỳ thuộc [a1,a2]. Khi đó



0 ≤ y1 ≤ y ≤ y2 ≤ 1
0 ≤ x1 ≤ x ≤ x2
y2 ư x2 ≤ y ư x ≤ y1 ư x1
+ Nếu 0 ≤ x < 1 thì 0 ≤ x1 < 1. Do a1 = (x1,y1) ∈ X nên y1 = 1. Khi đó y = 1 và a ∈ X.
+ Nếu x ≥ 1 thì a ∈ X. (Do y ư x + 1 ≥ y2 ư x2 + 1 ≥ 0 và 0 ≤ y ≤ 1).
Trường hợp 2. Hai phần tử a1,a2 không so sánh được.
Đặt a = a1 ∨ a2. Ta kiểm tra a ∈ X.
+ Nếu y2 ư x2 ≥ y1 ư x1 và y2 ≥ y1 thì a = (x1 ư y1 + y2,y2).
+ Nếu y2 ư x2 ≤ y1 ư x1 và y1 ≥ y2 thì a = (x2 ư y2 + y1,y1).
Trong cả hai trường hợp trên ta đều kiểm tra được a ∈ X.
Định nghĩa 1.1.4. Cho X,Y là hai tập hợp bất kỳ. Trên X ì Y ta xét quan hệ hai
ngôi R. Với mỗi x ∈ X và y ∈ Y ta định nghĩa R(x) = {y ∈ Y : (x,y) ∈ R} và
Rư1
(y) = {x ∈ X : (x,y) ∈ R}.
Định lý 1.1.1. Cho X là không gian tôpô semilattice liên thông đường, X0 ⊆ X là tập con
khác rỗng của X và R ⊆ X0 ì X là quan hệ hai ngôi thỏa8
(i) Với mỗi x ∈ X0 tập hợp R(x) là khác rỗng và đóng trong R(X0) =
S
z∈X0
R(z).
(ii) Tồn tại x0 ∈ X0 sao cho R(x0) là compact.
(iii) Với mỗi tập hữu hạn khác rỗng A ⊆ X0
[
x∈A
[x,supA] ⊆
[
x∈A
R(x)
.
Khi đó tập hợp
T
x∈X0
R(x) là khác rỗng.
Chứng minh. Tham khảo [4].
Định nghĩa 1.1.5. Cho X,Y là các không gian tôpô, ánh xạ đa trị G : X → 2
Y
được gọi là
transfer closed nếu với mỗi x ∈ X và y /∈ G(x) tồn tại x
′
∈ X và một lân cận mở N(y) của
y trong Y sao cho y
′
∈/ G(x
′
) với mỗi y
′
∈ N(y).
Nhận xét 1.1.1. G : X → 2
Y
là transfer closed khi và chỉ khi
T
x∈X G(x) =
T
x∈X
clG(x).
Chứng minh. Giả sử G là transfer closed, ta chứng minh
T
x∈X G(x) =
T
x∈X clG(x). Thật
vậy, nếu tồn tại y ∈ X và x
′
∈ X sao cho y ∈ clG(x) với mỗi x ∈ X và y /∈ G(x
′
) thì theo
tính transfer closed của G tồn tại x
′′
∈ X sao cho y /∈ clG(x
′′
). Điều này là mâu thuẫn.
Giả sử
T
x∈X G(x) =
T
x∈X
clG(x). Lấy y ∈ Y và x ∈ X sao cho y /∈ G(x). Khi đó
y /∈
T
x∈X G(x) hay y /∈
T
x∈X clG(x). Nghĩa là tồn tại x
′
∈ X sao cho y /∈ clG(x
′
).
Định lý 1.1.2. Cho X là không gian tôpô semilattice liên thông đường, X0 ⊆ X là tập con
khác rỗng của X và R ⊆ X0 ì X là quan hệ hai ngôi thỏa
(i) G : X0 → 2
X
là transfer closed, trong đó G(x) = {y ∈ X : (x,y) ∈ R} với mỗi
x ∈ X0.
(ii) Tồn tại x0 ∈ X0 sao cho clG(x0) là compact.9
(iii) Với mỗi tập hữu hạn khác rỗng A ⊆ X0
[
x∈A
[x,supA] ⊆
[
x∈A
G(x)
.
Khi đó tập hợp
T
x∈X0
G(x) là khác rỗng.
Chứng minh. Do clG(x) thỏa các điều kiện của định lý 1.1.1 nên
T
x∈X0
clG(x) là khác
rỗng. Mặt khác, do G là transfer closed nên
T
x∈X0 G(x) =
T
x∈X0
clG(x). Từ đó ta suy ra
điều phải chứng minh.
Định lý 1.1.3. Cho X là tập con khác rỗng, ∆-lồi của không gian tôpô semilattice liên thông
đường M và C ⊆ X ì X.
(1) Với mỗi y ∈ X tập hợp {x ∈ X : (x,y) ∈/ C} là ∆-lồi hoặc rỗng.
(2) Hàm x 7→ {y ∈ X : (x,y) ∈ C} là transfer closed.
(3) Với mỗi x ∈ X,(x,x) ∈ C.
(4) Tồn tại x0 ∈ X sao cho tập cl{y ∈ X : (x0,y) ∈ C} là compact.
Khi đó tồn tại y
∗
∈ X sao cho X ì {y
∗
} ⊂ C.
Chứng minh. Xét G : X → 2
X
cho bởi
G(x) = {y ∈ X : (x,y) ∈ C} với mỗi x ∈ X.
Khi đó, clG(x0) là compact.
Giả sử tồn tại tập hữu hạn A0 = {x1,x2, .,xn} sao cho
∆(A0) *
[n
i=1
G(xi)
nghĩa là tồn tại z ∈ ∆(A0) và z /∈
Sn
i=1 G(xi). Khi đó với mỗi i = 1, 2, .,n,z /∈
G(xi),(xi
,z) ∈/ C. Suy ra A0 ⊂ {x ∈ X : (x,z) ∈/ C}, theo (1) ∆(A0) ⊂ {x ∈ X : (x,z) ∈/