Luận văn Thạc sĩ Toán học: Bài toán cân bằng Nash trong không gian có thứ tự

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

178
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Toán học: Bài toán cân bằng Nash trong không gian có thứ tự giới thiệu tới các bạn về bài toán cân bằng Nash trong nửa dàn, bài toán cân bằng Nash trong không gian có thứ tự. Luận văn phục vụ cho các bạn chuyên ngành Toán học và những ngành có liên quan.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Bài toán cân bằng Nash trong không gian có thứ tự

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH ------------------------- Phạm Duy Khánh BÀI TOÁN CÂN BẰNG NASH TRONG KHÔNG GIAN CÓ THỨ TỰ Chuyên ngành: Toán Giải Tích Mã số: 60 46 01 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NGUYỄN BÍCH HUY Thành phố Hồ Chí Minh – 2008
1 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¸nh
2 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 39
3 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 Q 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 fi (ui , x ˆ∗i ) ui ∈Xi
4 Q trong ®ã 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.
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, x0) ∈ X × X ®Òu cã mét chÆn trªn nhá nhÊt, kÝ hiÖu x ∨ x0. §Þ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 S 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.
7 S VÝ 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 S (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, supA] ⊆ R(x) x∈A x∈A . T 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µ / G(x) tån t¹i x0 ∈ X vµ mét l©n cËn më N (y) cña transfer closed nÕu víi mçi x ∈ X vµ y ∈ y trong Y sao cho y 0 ∈ / G(x0 ) víi mçi y 0 ∈ N (y). T T 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). T T 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µ x0 ∈ X sao cho y ∈ clG(x) víi mçi x ∈ X vµ y ∈ / G(x0 ) th× theo tÝnh transfer closed cña G tån t¹i x00 ∈ X sao cho y ∈ / clG(x00). §iÒu nµy lµ m©u thuÉn. T T Gi¶ sö x∈X G(x) = x∈X clG(x). LÊy y ∈ Y vµ x ∈ X sao cho y ∈ / G(x). Khi ®ã T T y∈ / x∈X G(x) hay y ∈ / x∈X clG(x). NghÜa lµ tån t¹i x0 ∈ X sao cho y ∈ / clG(x0 ). §Þ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, supA] ⊆ G(x) x∈A x∈A . T Khi ®ã tËp hîp x∈X0 G(x) lµ kh¸c rçng. T 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 T T 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. 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 → 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 [ n ∆(A0) * G(xi ) i=1 Sn nghÜa lµ tån t¹i z ∈ ∆(A0) vµ z ∈ / 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) ⊆ G(x). x∈A T T 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 T 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 S S closed, nghÜa lµ y∈Y F −1 y = y∈Y int(F −1y). T T Chøng minh. X \ F −1 lµ transfer closed khi vµ chØ khi y∈Y X \ F −1(y) = y∈Y cl(X \ S S F −1 (y)). §iÒu nµy nghÜa lµ y∈Y F −1y = y∈Y int(F −1y). S S 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 0 ∈ Y sao cho x ∈ intF −1(y 0 ). Suy ra tån t¹i l©n cËn T më N (x) cña x sao cho z ∈ F −1(y 0) 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 T 0 −1 0 z∈N (x) F (z) 6= ∅. NghÜa lµ tån t¹i y ∈ Y sao cho z ∈ F (y ) víi mäi z ∈ N (x). Suy ra S S x ∈ int(F −1(y 0)). 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. / B víi mçi x ∈ X. Khi ®ã (x, x) ∈ C, theo ®Þnh lý 1.1.3 tån t¹i y ∗ ∈ X sao Gi¶ sö (x, x) ∈ 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× T T 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µ y 0 ∈ Y sao cho víi mäi x0 ∈ N (x) ϕ(x, y) < ϕ(x0, y 0) + 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      1, x = y,   ϕ(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   1, x = 0, ϕ(x, y) = ϕ(x, 0) = .  2, x 6= 0 Tr-êng hîp 2. y 6= 0   1, x = y, ϕ(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µ y 0 ∈ Y sao cho ϕ(x, y) < ϕ(x0 , y 0) + , ∀x0 ∈ 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âm khi 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âm khi 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. S 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 v`a c ≤ d. Khi ®ã hµm f : X → (−∞, +∞) ®Þnh bëi f (x, y) = x2 + y 2 lµ ∆-tùa lâm. Chøng minh. ThËt vËy, lÊy λ ∈ (−∞, +∞), ta cã      X λ λ} = Xλ Yλ 1≤λ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 sup f (x, y) = sup inf f (x, y) y∈Y x∈X x∈X y∈Y
15 Chøng minh. Ta dÔ dµng kiÓm tra ®-îc sup inf f (x, y) ≤ inf sup f (x, y) x∈X y∈Y y∈Y x∈X Gi¶ sö sup inf f (x, y) < inf sup f (x, y) x∈X y∈Y y∈Y x∈X Khi ®ã, tån t¹i r ∈ (−∞, +∞) sao cho sup inf f (x, y) < r < inf sup f (x, y) x∈X y∈Y y∈Y x∈X 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 (x0 , y1) + = −f (x0 , y1) − f (x, y0) + r víi mçi x0 ∈ X. NghÜa lµ f (x0 , y1 ) < r hay y1 ∈ G(x0) víi mäi x0 ∈ N (x). Suy ra \ G(x0 ) 6= ∅ x0 ∈N (x) 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 → 2C cho 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 sup f (x, y) = sup inf f (x, y) y∈Y x∈X x∈X y∈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 bi lµ c¸c kh«ng XÐt (Xi , ≤i ), i ∈ I lµ hä c¸c kh«ng gian t«p« semilattice, X vµ X gian t«p« tÝch, nghÜa lµ Y Y X= Xi , bi = X Xj i∈I j∈I\i Víi mçi x, x0 ∈ X ta ®Þnh nghÜa x ≤ x0 khi vµ chØ khi xi ≤i x0i víi mçi i ∈ I . Khi ®ã, (X, ≤) lµ kh«ng gian t«p« semilattice víi (x ∨ x0)i = xi ∨i x0i , (i ∈ I). bi . Víi bÊt kú x ∈ X ta ®Æt x = (xi, xˆi ) trong ®ã xi ∈ Xi , xˆi ∈ X §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 fi (ui , x ˆ∗i ). ui ∈Xi 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, Q 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 ,ˆ bi hµm ui 7→ fi (ui , x xi ∈ X ˆi ) lµ ∆-tùa lâm. (ii) Víi mçi i ∈ N , fi lµ nöa liªn tôc trªn. ˆi ) lµ SPT nöa liªn tôc d-íi theo biÕn x (iii) Víi mçi i ∈ N , fi (ui , 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 fi (ui , x ˆ∗i ). ui ∈Xi Q 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, 1 Ti (x) = {yi ∈ Xi : fi (yi , x ˆ )i − } ˆi) > max fi (ui , x ui ∈Xi 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øng minh Wk (x) cã tÝnh chÊt giao ®Þa ph-¬ng, nghÜa lµ nÕu Wk (x) 6= ∅ ta sÏ chØ T T Q 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) = Q T 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(x0 ) 6= ∅, lÊy y 0 ∈ Ti(x0 ), nghÜa lµ, 1 fi (yi0, x ˆ0i ) > max fi (ui , x ˆ0i ) − . (1) ui ∈Xi k Víi bÊt kú > 0 tháa, 1 2 < fi (yi0, x ˆ0i ) − (max fi (ui , x ˆ 0i ) − ) ui ∈Xi k x0i ) cña x theo (iii) tån t¹i mét l©n cËn më O1 (ˆ bi vµ tån t¹i y ∗ ∈ Xi sao cho ˆ0i trong X i fi (yi0 , x ˆ 0i ) < fi (yi∗, x ˆ0i) + x0i ∈ O1 (ˆ ∀ˆ x0i ). (2)
18 Do maxui ∈Xi fi (ui , x ˆ0i nªn tån t¹i mét l©n cËn më O2 (ˆ ˆ i) lµ liªn tôc t¹i x x0i ) cña x ˆ0i trong X ˆ0i ∈ O2 (ˆ sao cho víi mçi x x0i ) ˆ0i ) − < max fi (ui , x max fi (ui , x ˆ0i ) < max fi (ui , x ˆ0i ) + . (3) ui ∈xi ui ∈Xi ui ∈Xi T Chän O(x0 ) = O(x0i ) × (O2 (ˆ x0i ) x0i )) trong ®ã O(x0i ) lµ mét l©n cËn më cña x0i trong O1 (ˆ Xi . Theo (1), (2) vµ (3), víi mçi x0 ∈ O(x0 ) ta cã, 1 1 fi (yi∗, x ˆ0i ) > fi (yi0 , x ˆ 0i ) − > max fi (ui , x ˆ 0i ) − ˆ0i) − . + > max fi (ui , x ui ∈Xi k ui ∈Xi k T T Khi ®ã yi∗ ∈ 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 , 1 fi (xki , x ˆki ) > max fi (ui , x ˆki ) − , ui ∈Xi k vµ v× vËy 1 fi (x∗i , x ˆ∗i ) ≥ lim sup fi (xki , x ˆki ) ≥ lim (max fi (ui , x ˆki ) − ) = max fi (ui , x ˆ ∗i ). k→∞ k→∞ u i ∈X i k u i ∈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 fi (ui , x ˆ∗i ). ui ∈Xi 1 1 VÝ dô 1.4.1. XÐt X = [0, 1] × [0, 1] vµ f1 (x, y) = x2 − 1+y vµ f2 (x, y) = y 2 − 1+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.