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

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ánh 2Mụ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ônggian 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 thamkhảo 39 3Mở đầ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 = ∏ 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 ) 4trong đó x∗i ∈ Xi và xˆ∗i ∈ Xˆi = ∏ 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. 5Chương 2. Bài toán cân bằng Nash trong khônggian 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ự. 6Chươ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) = ⋃ 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. 7Ví dụ 1.1.1. Đặt X = {(x, 1) : 0 ≤ x ≤ 1}⋃{(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ỏa 8(i) Với mỗi x ∈ X0 tập hợp R(x) là khác rỗng và đóng trong R(X0) = ⋃ 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 ⋂ 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 → 2Y đượ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 → 2Y là transfer closed khi và chỉ khi⋂x∈X G(x) = ⋂x∈X clG(x). Chứng minh. Giả sử G là transfer closed, ta chứng minh ⋂ x∈X G(x) = ⋂ 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ử ⋂ x∈X G(x) = ⋂ x∈X clG(x). Lấy y ∈ Y và x ∈ X sao cho y /∈ G(x). Khi đó y /∈ ⋂x∈X G(x) hay y /∈ ⋂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 → 2X 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 ⋂ 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 ⋂ x∈X0 clG(x) là khác rỗng. Mặt khác, do G là transfer closed nên ⋂ x∈X0 G(x) = ⋂ x∈X0 clG(x). Từ đó ta suy ra điều phải chứng minh. Định lý 1.1.3. ChoX 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 → 2X 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 /∈ ⋃n 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) /∈ 10 C} và vì vậy z ∈ ∆(A0) ⊂ {x ∈ X : (x, z) /∈ C}, (z, z) ∈ C . Điều này là mâu thuẫn. Do đó với mỗi tập hữu hạn A ⊂ X ta có ∆(A) ⊆ ⋃ x∈A G(x). Theo định lý 1.1.2 ta thu được ⋂ x∈X G(x) khác rỗng. Lấy y ∗ ∈ ⋂x∈X G(x) ⊂ X ta có X ì {y∗} ⊂ C Nhận xét 1.1.2. Nếu X là compact thì (4) trong định lý 1.1.3 luôn đúng. 1.2 Bổ đề Ky Fan và định lý điểm bất động Fan-Browder Bằng cách sử dụng định lý 1.1.3 và khái niệm ánh xạ đa trị có tính chất giao địa phương chúng ta thu được bổ đề Ky Fan và định lý điểm bất động Fan-Browder. Định nghĩa 1.2.1. Cho X,Y là hai không gian tôpô, F : X → 2Y được gọi là có tính chất giao địa phương nếu với mỗi x ∈ X sao cho F (x) 6= ∅ tồn tại lân cận mở N(x) của x sao cho ⋂ z∈N(x) F (z) 6= ∅. Nhận xét 1.2.1. F : X → 2Y có tính chất giao địa phương khi và chỉ khi X \F−1 là transfer closed, nghĩa là ⋃ y∈Y F −1y = ⋃ y∈Y int(F −1y). Chứng minh. X \ F−1 là transfer closed khi và chỉ khi ⋂y∈Y X \ F−1(y) = ⋂y∈Y cl(X \ F−1(y)). Điều này nghĩa là ⋃ y∈Y F −1y = ⋃ y∈Y int(F −1y). Giả sử ⋃ y∈Y F −1y = ⋃ y∈Y intF −1(y) ta chứng minh F : X → 2Y có tính chất giao địa phương. Thật vậy, lấy x ∈ X sao cho F (x) 6= ∅. Khi đó tồn tại y ∈ F (x) hay x ∈ F−1(y). Theo tính chất transfer closed tồn tại y′ ∈ Y sao cho x ∈ intF−1(y′). Suy ra tồn tại lân cận mở N(x) của x sao cho z ∈ F−1(y′) với mọi z ∈ N(x) hay ⋂z∈N(x) F (z) 6= ∅. Giả sử F : X → 2Y có tính chất giao địa phương. Lấy x ∈ X và y ∈ Y sao cho x ∈ F−1(y) hay y ∈ F (x). Theo tính chất giao địa phương, tồn tại lân cận mở N(x) của x sao cho⋂ z∈N(x)F (z) 6= ∅. Nghĩa là tồn tại y′ ∈ Y sao cho z ∈ F−1(y′) với mọi z ∈ N(x). Suy ra x ∈ int(F−1(y′)). Vậy⋃y∈Y F−1y = ⋃y∈Y int(F−1y). 11 Định lý 1.2.1. Cho X là tập con compact, khác rỗng và ∆-lồi của không gian tôpô semilattice, liên thông đường M , và B ⊂ X ìX . (i) Với mỗi y ∈ X , tập hợp {x ∈ X : (x, y) ∈ B} là ∆-lồi khác rỗng. (ii) Hàm y 7→ {x ∈ X : (x, y) ∈ B} có tính chất giao địa phương khác rỗng. Khi đó tồn tại x∗ ∈ X sao cho (x∗, x∗) ∈ B Chứng minh. Đặt C = X ìX \B và F (x) = {y ∈ X : (x, y) ∈ B} với mỗi x ∈ X . Khi đó {y ∈ X : (x, y) ∈ C} = {y ∈ X : (x, y) /∈ B} = X \ {y ∈ X : (x, y) ∈ B} = X \ F (x) Theo (ii) F−1(y) = {x ∈ X : (x, y) ∈ B} có tính chất giao địa phương khác rỗng nên X \ F (x) là transfer closed. Với mỗi y ∈ X, {x ∈ X : (x, y) /∈ C} = {x ∈ X : (x, y) ∈ B} là ∆-lồi và khác rỗng. Giả sử (x, x) /∈ B với mỗi x ∈ X . Khi đó (x, x) ∈ C , theo định lý 1.1.3 tồn tại y∗ ∈ X sao cho X ì {y∗} ⊂ C . Điều này nghĩa là với mỗi x ∈ X, (x, y∗) ∈ C, (x, y∗) /∈ B. Do đó tập hợp {x ∈ X : (x, y∗) ∈ B} là rỗng và dẫn đến mâu thuẫn với (i). Vậy tồn tại x∗ ∈ X sao cho (x∗, x∗) ∈ B. Chứng minh kết thúc. Sử dụng kết quả vừa thu được ta suy ra định lý điểm bất động Fan-Browder suy rộng. Định lý 1.2.2. Cho X là tập con khác rỗng, compact và ∆-lồi của không gian tôpô semilattice, liên thông đường M , F : X → 2X có tính chất giao địa phương và có giá trị ∆-lồi. Khi đó F có điểm bất động, nghĩa là tồn tại x∗ ∈ X sao cho x∗ ∈ F (x∗). Chứng minh. Đặt B = {(x, y) ∈ X ìX : x ∈ F (y)}. Với mỗi y ∈ X {x ∈ X : (x, y) ∈ B} = {x ∈ X : x ∈ F (y)} = F (y) là ∆-lồi và khác rỗng. Mặt khác, ánh xạ y 7→ {x ∈ X : (x, y) ∈ B} = F (y) có tính chất giao địa phương. Theo định lý 1.2.1 tồn tại x∗ ∈ X sao cho x∗ ∈ F (x∗). 12 Hệ quả 1.2.1. Cho X là tập con khác rỗng, compact và ∆-lồi của không gian tôpô semilattice, liên thông đường M , F : X → 2X có giá trị ∆-lồi, khác rỗng và với mỗi y ∈ X,F−1(y) là tập mở. Khi đó F có điểm bất động. Chứng minh. Ta chỉ cần chứng minh F có tính chất giao địa phương. Với mỗi x ∈ X với F (x) 6= ∅, lấy y ∈ F (x) hay x ∈ F−1(y). Do F−1(y) là mở nên tồn tại lân cận mở N(x) của x trong X sao cho N(x) ⊂ F−1(y). Khi đó, với mỗi z ∈ N(x), z ∈ F−1(y), y ∈ F (z). Vì vậy y ∈ ⋂z∈N(x) F (z) hay ⋂z∈N(x) F (z) 6= ∅. Theo định lý 1.2.2 F có điểm bất động. 1.3 Định lý điểm yên ngựa Sử dụng định lý điểm bất động Fan-Browder ta thu được định lý điểm yên ngựa và hệ quả của nó trong không gian có thứ tự. Định nghĩa 1.3.1. Cho X,Y là các không gian tôpô, ϕ(x, y) : X ì Y → (−∞,+∞) được gọi là strongly path transfer nửa liên tục dưới đối với x (gọi vắn tắt, SPT nửa liên tục dưới) nếu với mỗi (x, y) ∈ X ìY và  > 0, tồn tại một lân cận mở N(x) của x trong X và y0 ∈ Y sao cho với mọi x′ ∈ N(x) ϕ(x, y) < ϕ(x′, y0) +  Nếu −ϕ(x, y) là SPT nửa liên tục dưới đối với x thì ϕ(x, y) gọi là strongly path transfer nửa liên tục trên (gọi vắn tắt, SPT nửa liên tục trên). Nhận xét 1.3.1. Ta dễ dàng kiểm tra được nếu với mỗi y ∈ Y, ϕ(., y) là nửa liên tục dưới thì ϕ(x, y) là SPT nửa liên tục dưới theo biến x. Điều ngược lại là không đúng. Ví dụ 1.3.1. Xét X = [0, 1], Y = [0, 1] và hàm ϕ(x, y) xác định trên X ì Y cho bởi ϕ(x, y) =  1, x = y, 2, y = 0, x 6= 0, 0, ortherwise. . Khi đó ϕ(., y) không nửa liên tục dưới trên X , ϕ(x, y) là SPT nửa liên tục dưới theo x. 13 Chứng minh. Lấy (x, y) bất kỳ thuộc X ì Y và  > 0. Ta xét hai trường hợp: Trường hợp 1. y = 0 ϕ(x, y) = ϕ(x, 0) = 1, x = 0,2, x 6= 0 . Trường hợp 2. y 6= 0 ϕ(x, y) = 1, x = y,0, x 6= y . Trong cả hai trường hợp trên ta đều chỉ ra được lân cận mở N(x) của x trong X và y0 ∈ Y sao cho ϕ(x, y) < ϕ(x′, y0) + , ∀x′ ∈ N(x) Điều này nghĩa là ϕ(x, y) là SPT nửa liên tục dưới theo x. Hơn nữa ta dễ dàng kiểm tra được ϕ(., 1) không nửa liên tục dưới tại x = 1 hay ϕ(., y) không nửa liên tục dưới trên X . Định nghĩa 1.3.2. Cho X là không gian tôpô hoặc tập con ∆-lồi của không gian tôpô semilattice. Hàm f : X → (−∞,+∞) gọi là ∆-tựa lõm nếu với mỗi tập con hữu hạn khác rỗng A = {x1, x2, ..., xn} ⊆ X và y ∈ ∆(A) f(y) ≥ min{f(x1), f(x2), ..., f(xn)}. Nếu −f là ∆-tựa lõm thì f gọi là ∆-tựa lồi. Nhận xét 1.3.2. f : X → (−∞,+∞) là∆-tựa lõmkhi và chỉ khi tập hợp {y ∈ X : f(y) > λ} hoặc {y ∈ X : f(y) ≥ λ} là ∆-lồi với mọi λ ∈ (−∞,+∞). Nhận xét 1.3.3. f : X → (−∞,+∞) là∆-tựa lõmkhi và chỉ khi tập hợp {y ∈ X : f(y) < λ} hoặc {y ∈ X : f(y) ≤ λ} là ∆-lồi với mọi λ ∈ (−∞,+∞). Chứng minh. Ta chỉ chứng minh nhận xét 1.3.2, nhận xét 1.3.3 được chứng minh tương tự. + Giả sử f : X → (−∞,+∞) là ∆-tựa lõm. Lấy λ ∈ (−∞,+∞) bất kỳ, ta chứng minh {y ∈ X : f(y) ≥ λ} là ∆-lồi. Xét A = {x1, x2, ..., xn} là tập hợp hữu hạn, khác rỗng trong {y ∈ X : f(y) ≥ λ} và y ∈ ∆(A). Theo tính chất ∆-tựa lõm ta có f(y) ≥ min{f(x1), f(x2), ..., f(xn)} ≥ λ. 14 Suy ra y ∈ {y ∈ X : f(y) ≥ λ} hay {y ∈ X : f(y) ≥ λ} là ∆-lồi. + Giả sử {y ∈ X : f(y) ≥ λ} là ∆-lồi với mọi λ ∈ (−∞,+∞). Ta chứng minh f : X → (−∞,+∞) là ∆-tựa lõm. Thật vậy, lấy A = {x1, x2, ..., xn} là tập hữu hạn trong X và y ∈ ∆(A). Do {y ∈ X : f(y) ≥ λ} là ∆-lồi với λ = min{f(x1), f(x2), ..., f(xn)} và A là tập con của tập hợp trên nên y ∈ ∆(A) ⊂ {y ∈ X : f(y) ≥ λ}. Suy ra f : X → (−∞,+∞) là ∆-tựa lõm. Ví dụ 1.3.2. Xét X = {(x, 1) : 0 ≤ x ≤ 1}⋃{(1, y) : 0 ≤ y ≤ 1} ⊂ R2 với quan hệ thứ tự (a, b), (c, d) ∈ R2 : (a, b) ≤ (c, d) ⇔ a ≤ b va` c ≤ d. Khi đó hàm f : X → (−∞,+∞) định bởi f(x, y) = x2 + y2 là ∆-tựa lõm. Chứng minh. Thật vậy, lấy λ ∈ (−∞,+∞), ta có {(x, y) ∈ X : f(x, y) > λ} =  X λ < 1 Xλ ⋃ Yλ 1 ≤ λ < 2 ∅ λ > 2 Trong đó, Xλ = {(x, 1) : λ ≤ x ≤ 1} và Yλ = {(1, y) : λ ≤ y ≤ 1}. Từ đây ta suy ra {(x, y) ∈ X : f(x, y) > λ} là tập ∆-lồi hay f : X → (−∞,+∞) là ∆-tựa lõm. Định lý 1.3.1. Cho X,Y là hai tập con khác rỗng, compact và ∆-lồi của hai không gian tôpô semilattice liên thông đường M và E, f : X ì Y → (−∞,+∞). (i) Với mỗi x ∈ X , f(x, .) : Y → (−∞,+∞) là ∆-tựa lồi. (ii) Với mỗi y ∈ Y , f(., y) : X → (−∞,+∞) là ∆-tựa lõm. (iii) Hàm f(x, y) là SPT nửa liên tục dưới theo biến y và SPT nửa liên tục trên theo biến x. Khi đó, inf y∈Y sup x∈X f(x, y) = sup x∈X inf y∈Y f(x, y) 15 Chứng minh. Ta dễ dàng kiểm tra được sup x∈X inf y∈Y f(x, y) ≤ inf y∈Y sup x∈X f(x, y) Giả sử sup x∈X inf y∈Y f(x, y) < inf y∈Y sup x∈X f(x, y) Khi đó, tồn tại r ∈ (−∞,+∞) sao cho sup x∈X inf y∈Y f(x, y) < r < inf y∈Y sup x∈X f(x, y) Theo (i) và (ii), với mỗi x ∈ X , G(x) = {y ∈ Y : f(x, y) < r} là tập ∆-lồi khác rỗng, với mỗi y ∈ Y , K(y) = {x ∈ X : f(x, y) > r} = {x ∈ X : −f(x, y) < −r} là tập ∆-lồi khác rỗng. Với mỗi x ∈ X sao cho G(x) 6= ∅, lấy y0 ∈ G(x), f(x, y0) < r. Theo (iii) với  = r − f(x, y0) > 0 tồn tại lân cận N(x) của x trong X và y1 ∈ Y sao cho −f(x, y0) < −f(x′, y1) +  = −f(x′, y1)− f(x, y0) + r với mỗi x′ ∈ X . Nghĩa là f(x′, y1) < r hay y1 ∈ G(x′) với mọi x′ ∈ N(x). Suy ra⋂ x′∈N(x) G(x′) 6= ∅ và G có tính chất giao địa phương. Chứng minh tương tự ta suy ra K có tính chất giao địa phương. Đặt C = X ì Y và xét F : C → 2Ccho bởi F (u) = K(y)ìG(x) với mỗi u = (x, y) ∈ C. Theo định lý điểm bất động Fan-Browder F có điểm bất động, nghĩa là tồn tại u∗ = (x∗, y∗) ∈ C sao cho u∗ = (x∗, y∗) ∈ K(y∗)ìG(x∗) Suy ra f(x∗, y∗) > r và f(x∗, y∗) < r. Điều này là mâu thuẫn. Do đó inf y∈Y sup x∈X f(x, y) = sup x∈X inf y∈Y f(x, y) 16 Hệ quả 1.3.1. Cho X,Y là hai tập con khác rỗng, compact và ∆-lồi của hai không gian tôpô semilattice liên thông đường M và E, f : X ì Y → (−∞,+∞). (i) Với mỗi x ∈ X , f(x, .) : Y → (−∞,+∞) là ∆-tựa lồi và nửa liên tục dưới. (ii) Với mỗi y ∈ Y , f(., y) : X → (−∞,+∞) là ∆-tựa lõm và nửa liên tục trên. Khi đó tồn tại (x∗, y∗) ∈ X ì Y sao cho f(x, y∗) ≤ f(x∗, y∗) ≤ f(x∗, y) với mỗi (x, y) ∈ X ì Y . Chứng minh. Do f(x, .) : Y → (−∞,+∞) là nửa liên tục dưới nên f(x, y) là SPT nửa liên tục dưới theo biến y, f(., y) : X → (−∞,+∞) là nửa liên tục trên nên f(x, y) là SPT nửa liên tục trên theo biến x. Sử dụng định lý 1.3.1 ta thu được kết quả trên. 1.4 Định lý về sự tồn tại của điểm cân bằng Nash Xét (Xi,≤i), i ∈ I là họ các không gian tôpô semilattice, X và X̂i là các không gian tôpô tích, nghĩa là X = ∏ i∈I Xi, X̂i = ∏ j∈I\i Xj Với mỗi x, x′ ∈ X ta định nghĩa x ≤ x′ khi và chỉ khi xi ≤i x′i với mỗi i ∈ I . Khi đó, (X,≤) là không gian tôpô semilattice với (x ∨ x′)i = xi ∨i x′i, (i ∈ I). Với bất kỳ x ∈ X ta đặt x = (xi, xˆi) trong đó xi ∈ Xi, xˆi ∈ X̂i. Điểm x∗ ∈ X được gọi là điểm cân bằng Nash đối với họ hàm fi : X → (−∞,+∞) nếu với mỗi i ∈ I , fi(x ∗ i , xˆ ∗ i ) = max ui∈Xi fi(ui, xˆ ∗ i ). Sử dụng định lý điểm bất động Fan-Browder ta thu được định lý về sự tồn tại của điểm cân bằng Nash. 17 Định lý 1.4.1. Cho N = {1, 2, ..., n}, với mỗi i ∈ N , Xi là các tập con khác rỗng, compact, compact theo dãy và ∆-lồi của không gian tôpô semilattice liên thông đường, X = ∏ i∈N Xi và fi : X → (−∞,+∞) thỏa (i) Với mỗi i ∈ N ,xˆi ∈ X̂i hàm ui 7→ fi(ui, xˆi) là ∆-tựa lõm. (ii) Với mỗi i ∈ N , fi là nửa liên tục trên. (iii) Với mỗi i ∈ N , fi(ui, xˆi) là SPT nửa liên tục dưới theo biến xˆi. Khi đó, tồn tại điểm x∗ ∈ X sao cho với mỗi i ∈ N fi(x ∗ i , xˆ ∗ i ) = max ui∈Xi fi(ui, xˆ ∗ i ). Chứng minh. Với mỗi k = 1, 2, 3, ... xét Wk : X → 2X ,Wk(x) = ∏ i∈N Ti(x) với mỗi x ∈ X , trong đó Ti : X → 2Xi định bởi, Ti(x) = {yi ∈ Xi : fi(yi, xˆi) > max ui∈Xi fi(ui, xˆ)i − 1 k } Do các Ti(x) là khác rỗng và ∆-lồi (theo (i) và (ii)) nên Wk(x) 6= ∅ và ∆-lồi. Tiếp theo ta chứngminhWk(x) có tính chất giao địa phương, nghĩa là nếuWk(x) 6= ∅ ta sẽ chỉ ra một lân cận O(x) của x trong X sao cho ⋂ u∈O(x)Wk(u) 6= ∅. Do ⋂ u∈O(x) ∏ i∈N Ti(u) =∏ i∈N ⋂ u∈O(x) Ti(u) nên ta chỉ cần chứng minh Ti(i ∈ N) có tính chất giao địa phương. Giả sử Ti(x 0) 6= ∅, lấy y0 ∈ Ti(x0), nghĩa là, fi(y 0 i , xˆ 0 i ) > max ui∈Xi fi(ui, xˆ 0 i )− 1 k . (1) Với bất kỳ  > 0 thỏa, 2 < fi(y 0 i , xˆ 0 i )− (max ui∈Xi fi(ui, xˆ 0 i )− 1 k ) theo (iii) tồn tại một lân cận mở O1(xˆ0i ) của xˆ 0 i trong X̂i và tồn tại y ∗ i ∈ Xi sao cho fi(y 0 i , xˆ 0 i ) < fi(y ∗ i , xˆ ′ i) +  ∀xˆ′i ∈ O1(xˆ0i ). (2) 18 Do maxui∈Xi fi(ui, xˆi) là liên tục tại xˆ 0 i nên tồn tại một lân cận mở O2(xˆ 0 i ) của xˆ 0 i trong X sao cho với mỗi xˆ′i ∈ O2(xˆ0i ) max ui∈xi fi(ui, xˆ 0 i )−  < max ui∈Xi fi(ui, xˆ ′ i) < max ui∈Xi fi(ui, xˆ 0 i ) + . (3) Chọn O(x0) = O(x0i )ì (O2(xˆ0i ) ⋂ O1(xˆ 0 i )) trong đó O(x 0 i ) là một lân cận mở của x 0 i trong Xi. Theo (1), (2) và (3), với mỗi x′ ∈ O(x0) ta có, fi(y ∗ i , xˆ ′ i) > fi(y 0 i , xˆ 0 i )−  > max ui∈Xi fi(ui, xˆ 0 i )− 1 k +  > max ui∈Xi fi(ui, xˆ ′ i)− 1 k . Khi đó y∗i ∈ ⋂ u∈O(x0) Ti(u) và vì vậy ⋂ u∈O(x0) Ti(u) 6= ∅. Do đó Ti có tính chất giao địa phương và Wk có tính chất giao địa phương. Theo định lý điểm bất động Fan-Browder tồn tại xk ∈ X sao cho xk ∈ Wk(xk). Mặt khác, X là compact theo dãy nên {xk}∞k=1 có điểm tụ x∗ ∈ X . Không mất tính tổng quát ta giả sử limk→∞ xk = x∗, nghĩa là với mỗi i ∈ N , fi(x k i , xˆ k i ) > max ui∈Xi fi(ui, xˆ k i )− 1 k , và vì vậy fi(x ∗ i , xˆ ∗ i ) ≥ lim sup k→∞ fi(x k i , xˆ k i ) ≥ lim k→∞ (max ui∈Xi fi(ui, xˆ k i )− 1 k ) = max ui∈Xi fi(ui, xˆ ∗ i ). Do đó tồn tại điểm x∗ ∈ X sao cho với mỗi i ∈ N , fi(x ∗ i , xˆ ∗ i ) = max ui∈Xi fi(ui, xˆ ∗ i ). Ví dụ 1.4.1. Xét X = [0, 1]ì [0, 1] và f1(x, y) = x2 − 11+y và f2(x, y) = y2 − 11+x . Khi đó với mỗi y ∈ [0, 1], f1(., y) là ∆-tựa lõm, với mỗi x ∈ [0, 1], f2(x, .) là ∆-tựa lõm. Khi đó bộ hàm f1, f2 thỏa các điều kiện của định lý 1.4.1. Điểm x∗ = (1, 1) ∈ X chính là điểm yên ngựa của bộ hàm f1, f2. 19 Chương 2 Bài toán cân bằng Nash trong không gian có thứ tự 2.1 Định lý điểm bất động của ánh xạ đơn trị Trong phần này chúng tôi trình bày các kết quả về điểm bất động đối với ánh xạ đơn trị trong tập hợp có thứ tự. Định nghĩa 2.1.1. Tập hợp có thứ tự (P,≤) được gọi là lattice nếu sup{x, y} và inf{x, y} tồn tại với mọi x, y ∈ P . Định nghĩa 2.1.2. Tập C ⊆ P được gọi là một xích (thứ tự toàn phần) nếu x ≤ y hay y ≤ x với mọi x, y ∈ C . Định nghĩa 2.1.3. Tập C ⊆ P được gọi là sắp tốt (thuận) nếu mọi tập con khác rỗng của C đều có phần tử nhỏ nhất. Tập C ⊆ P được gọi là sắp tốt đảo nếu mọi tập con khác rỗng của C đều có phần tử lớn nhất. Định nghĩa 2.1.4. Tập hợp P với quan hệ ≤ có các tính chất phản xạ và bắt cầu được gọi là định hướng nếu với mỗi cặp (x, y) ∈ P ì P tồn tại z ∈ P sao cho x ≤ z và y ≤ z. 20 Định lý sau trình bày nguyên lý đệ qui. Trong phần chứng minh chúng tôi chỉ sử dụng các công cụ sơ cấp của lý thuyết tập hợp. Định lý 2.1.1. Cho (P,≤) là tập hợp có thứ tự và D ⊂ 2P là họ chứa tập ∅ và f : D → P . Khi đó tồn tại duy nhất một tập sắp tốtC sao cho x ∈ C khi và chỉ khi x = f{y ∈ C : y < x}. Hơn nữa, nếu f(C) tồn tại thì f(C) không là chặn trên ngặt của C . Chứng minh. Ta kí hiệu C<x = {y ∈ C : y < x} với mỗi x ∈ P và C ⊆ P . Xích C ⊆ P được gọi là đồng dạng nếu C là sắp tốt và x = f(C<x) với mọi x ∈ C . Đặc biệt tập {f(∅)} là đồng dạng. Ta đưa ra một số tính chất của xích đồng dạng. (a) Nếu A và B là đồng dạng và A * B thì B = A<x với x = min(A \B). (b) Hợp C của tất cả các xích đồng dạng là sắp tốt và thỏa x ∈ C khi và chỉ khi x = f{y ∈ C : y < x}. Để chỉ ra sự tồn tại duy nhất tập sắp tốt C trong định lý ta chỉ cần chứng minh các tính chất (a) và (b) của xích đồng dạng và tính duy nhất của tập C . + Chứng minh tính chất (a). Do x = min(A \B) nên A<x ⊆ B. Thật vậy, nếu tồn tại y ∈ A<x và y /∈ B thì y ∈ A \B và y < x. Điều này là mâu thuẫn với cách chọn x. Để chứng minh B = A<x ta chỉ cần chứng minh B \ A<x là tập rỗng. Giả sử ngược lại, B \ A<x là tập khác rỗng. Khi đó tồn tại y = min(B \ A<x) sao cho B<y ⊆ A<x. Hơn nữa B<y là tập con thực sự của A<x, nếu không y = f(B<y) = f(A<x = x), điều này là không xảy ra vì y ∈ B và x /∈ B. Đặt z = min(A<x \ B<y), khi đó A<z ⊆ B<y . Do z ∈ A<x ⊆ B, z /∈ B<y và y ∈ B nên y ≤ z < x. Mặt khác B<y ⊆ A<x nên B<y ⊆ A<y ⊆ A<z . Do đó B<y = A<z và y = f(B<y) = f(A<z) = z. Suy ra y = z ∈ A<x, điều này mâu thuẫn với cách chọn y. + Chứng minh tính chất (b). Lấy Y là tập con khác rỗng của C . Gọi B là một xích đồng dạng sao cho Y ⋂ B là tập khác rỗng và đặt y = min(Y ⋂ B). Ta chứng minh y là phần tử nhỏ nhất của Y . Lấy x bất kỳ thuộc Y . Nếu x ∈ B thì x ∈ Y ⋂B và y ≤ x. Ngược lại, chọn một xích đồng dạng A chứa x. Theo chứng minh ở tính chất (a) ta có B ⊆ A<x hay y < x. Vậy y ≤ x với mọi x ∈ Y hay y = minY . Suy ra C là sắp tốt. 21 Lấy x bất kỳ thuộc C . Chọn B là xích đồng dạng sao cho x ∈ B. Theo chứng minh tính chất (a) ta suy ra B<x = C<x. Do B là đồng dạng nên x = f(B<x) = f(C<x). Nếu x ∈ P và x = f(C<x) thì C<x⋃{x} là đồng dạng hay x ∈ C . Do đó x ∈ C khi và chỉ khi x = f(C<x). + Chứng minh tính duy nhất của tập C . Giả sử B là xích sắp tốt trong P thỏa x ∈ B khi và chỉ khi x = f(B<x). Do B là xích đồng dạng nên B ⊆ C . Nếu B 6= C thì theo chứng minh (a) B = C<x với x = min(C \B). Khi đó f(B<x) = f(C<x) = x và x /∈ B. Điều này là mâu thuẫn với tính chất của B. Do đó B = C và xích sắp tốt C là duy nhất. Nếu f(C) tồn tại thì f(C) không thể là chặn trên ngặt của C . Thật vậy, trong trường hợp ngược lại ta có C ⋃{f(C)} là một xích đồng dạng không nằm trong C . Điều này là mâu thuẫn với cách xây dựng C . Sử dụng nguyên lý đệ qui vừa trình bày ta thu được phương pháp lặp đơn điệu suy rộng. Định lý 2.1.2. Cho (P,≤) là tập hợp có thứ tự, G : P → P và a ∈ P . Khi đó tồn tại duy nhất xích sắp tốt C , gọi là xích sắp tốt của phép lặp G đối với a, trong P thỏa a = minC và nếu x ∈ X,x > a thì x ∈ C khi và chỉ khi x = supG[C<x] Hơn nữa, nếu x∗ = supG[C] tồn tại và a ≤ x∗ ≤ Gx∗ thì x∗ = maxC và G(x∗) = x∗. Chứng minh. GọiD là lớp tất cả các tập con khác rỗng U ⊆ P sao cho supG[U ] tồn tại. Xét ánh xạ f : D⋃{∅} → P cho bởi f(∅) = a và f(U) = supG[U ] với U ⊆ D. Theo nguyên lý đệ qui tồn tại duy nhất xích sắp tốt C trong P sao cho a = minC và a < x ∈ C khi và chỉ khi x = supG[C<x] Giả sử x∗ = supG[C] tồn tại và a ≤ x∗ ≤ G(x∗). Nếu x ∈ C và x 6= a thì x = supG[C<x] ≤ supG[C = x∗]. Mặt khác x∗ ≤ G(x∗), suy ra x∗ = G(x∗). 22 Sử dụng phương pháp lặp đơn điệu suy rộng chúng ta thu được định lý điểm bất động đối với ánh xạ tăng. Định nghĩa 2.1.5. Cho (P,≤) là tập hợp có thứ tự. Ta định nghĩa: + [a) = {x ∈ P : a ≤ x} với mỗi a ∈ P . + (b] = {x ∈ P : x ≤ b} với mỗi b ∈ P . + Hàm G : P → P gọi là không giảm (tăng) trong W ⊆ P nếu Gx ≤ Gy (Gy ≤ Gx) với mọi x, y ∈ W và x ≤ y. Định lý 2.1.3. Cho (P,≤) là tập hợp có thứ tự, G : P → P và a ∈ P . Giả sử x∗ = supG[C] tồn tại vớiC là xích sắp tốt của phép lặpG đối với a. Nếu a ≤ Ga vàG là không giảm trong [a) thì x∗ là điểm bất động nhỏ nhất của G trong [a) và x∗ = maxC = min{y ∈ [a) : Gy ≤ y}. Chứng minh. Vì a = minC và supG(C<x) ≤ supG[C] nên a ≤ x ≤ x∗ với mỗi x ∈ C . Do G là không giảm trong [a) nên Gx ≤ Gx∗ với mỗi x ∈ C . Do đó x∗ = supG[C] ≤ Gx∗. Theo phương pháp lặp đơn điệu suy rộng ta suy ra x∗ là điểm bất động của ánh xạ G trong [a) và x∗ = maxC . Ta chứng minh x∗ = min{y ∈ [a) : Gy ≤ y}. Lấy y ∈ [a) và Gy ≤ y. Do G là không giảm trong [a) nên G[a, y] ⊆ [a, y]. Lấy x bất kỳ trong C . Ta kiểm tra x ∈ [a, y]. Thật vậy, nếu x /∈ [a, y] thì C \ [a, y] 6= ∅. Đặt x¯ = min(C \ [a, y]), khi đó C<x¯ ⊆ [a, y] hay G[C<x¯] ⊆ G[a, y] ⊆ [a, y]. Suy ra x¯ = supG[C<x¯] ∈ [a, y]. Điều này là mâu thuẫn. Vậy x ∈ [a, y] với mọi x ∈ C hayC ⊆ [a, y]. Do đó x∗ = maxC ≤ y với mọi y ∈ [a) và Gy ≤ y. Đặc biệt, x∗ là điểm bất động nhỏ nhất của G trong [a). Ta phát biểu kết quả đối ngẫu cho định lý 2.1.3 Định lý 2.1.4. Cho (P,≤) là tập hợp có thứ tự, G : P → P và b ∈ P . Giả sử x∗ = inf G[D] tồn tại với D là xích sắp tốt đảo của phép lặp G đối với b, nghĩa là b = maxD và nếu x ∈ X,x > b thì x ∈ D khi và chỉ khi x = inf G[{y ∈ D : y > x}] Khi đó, nếu Gb ≤ b và G là không giảm trong (b] thì x∗ là điểm bất động lớn nhất của G 23 trong (b] và x∗ = minD = max{y ∈ (b] : y ≤ Gy} và x∗ là điểm bất động nhỏ nhất của G trong (b]. 2.2 Định lý điểm bất động của ánh xạ đa trị Các kết quả về điểm bất động đối với ánh xạ đơn trị sẽ sử dụng vào trường hợp đa trị. Định nghĩa 2.2.1. Hàm S : Y → X được gọi là selection của ánh xạ đa trị F : Y → 2X \ ∅ nếu S(x) ∈ F (x) với mỗi x ∈ Y . Nếu X là tập hợp có thứ tự và S(x) là phần tử nhỏ nhất (lớn nhất) của F (x) với mỗi x ∈ Y thì ta nói S là selection nhỏ nhất (lớn nhất) của ánh xạ đa trị F . Định nghĩa 2.2.2. Phần tử x ∈ X gọi là điểm bất động của ánh xạ F : X → 2X \ ∅ nếu x ∈ F (x). Nếu tập Z gồm tất cả các điểm bất động của ánh xạ F có phần tử ._.