´ ´ NEM VEGLEGES VALTOZAT D¨ ont´ esi rendszerek 1.
Bevezet´ es
Az ´elet¨ unk, munk´ ank sor´ an ´alland´oan d¨ont´esek meghozatal´ara van lehet˝os´eg¨ unk vagy ´eppen k´enyszer¨ ul¨ unk. A t´argy ´es a jegyzet c´elja, hogy megvizsg´alja a k¨ ozben felmer¨ ul˝ o probl´em´ak, megk¨ozel´ıt´esek ´es megold´asok egy r´esz´et ´es seg´ıtsen a megalapozottabb d¨ont´esek meghozatal´aban. A d¨ ont´esekkel sz´ amos tudom´any foglalkozik, a teljess´eg ig´enye n´elk¨ ul ilyen a mikro¨ okon´ omia, statisztika, line´aris ´es nem linearis valamint sztochasztikus programoz´ as, j´at´ekelm´elet, t¨obb t´enyez˝os d¨ont´es t´amogat´as, pszichol´ ogia stb. A d¨ ont´esi helyzet alapj´ aban valami konfliktussal, bizonytalans´aggal j´ar, k¨ ul¨ onben nem is okozna gondot. A bizonytalans´ag oka sok oka lehet. Nem mindig tudjuk a pontos adatokat, az egyes alternat´ıv´ak kimenetel´et, ´ert´ek´et, az esetleges vet´elyt´ arsak l´ep´eseit, vagy ak´ar a l´et´et. Racionalit´ as. Szoci´ alis fogalom, kb. elmagyar´azhat´os´ag. (A matematika ´ is az, amit el tudunk fogadtatni.) Altal´ anos s´ema (Kem´eny-Snell, plusz kisz´ am´ıthat´ os´ ag, numerikus stabilit´as, sebess´eg) ¨ Osszehasonl´ ıt´ as, pszichikai vonatkoz´asok (j´o-j´o, j´o-rossz, rossz-rossz, Knight ” takes pawn”). Korl´ atlanul oszthat´o vs eg´esz mennyis´egek. Utilit´ as (hasznoss´ ag). Alma-k¨orte, egy M.L. vs k´et M.L. Cs¨okken˝o hozad´ek (diminishing return). Alma-ban´ an. Neumann t´etel, Edgeworth dobozok. Pareto optimumok. Determinisztikus vs v´eletlen. Optimaliz´al´as vs verseny.
1
2.
Line´ aris programoz´ as
A line´ aris programoz´ as az egyik legk´ezenfekv˝obb eszk¨oz er˝oforr´asok hat´ekony felhaszn´ al´ as´ anak, vagy ´eppen k¨ovetelm´enyek teljes´ıt´es´enek modellez´es´eben. Akkor folyamodhatunk hozz´a, ha a probl´em´ank line´aris, determinisztikus ´es a mennyis´egeink korl´ atlanul oszthat´oak.
2.1.
A di´ eta probl´ ema
C´elunk egy olyan ´etrend ¨ ossze´all´ıt´asa, ami fedezi a napi minim´alis sz¨ uks´egleteinket, de lehet˝ oleg min´el olcs´obb. Minim´alis sz¨ uks´eglet: 2000 kCal, 55 g feh´erje, 800 mg kalcium, jel¨ol´esben Ca. Ezeket az adatokat p´eld´aul t´ apl´ alkoz´ as tudom´ anyi szakk¨onyvekb˝ol nyerhetj¨ uk; az ´ert´ekek f¨ ugghetnek az nemt˝ ol, ´eletkort´ ol, a v´egzett fizikai aktivit´ast´ol, ´eghajlatt´ol ´es a tudom´any pillanatnyi ´ all´ as´ at´ ol.1 N´eh´ any ´etel becs¨ ult adagja, t´ap´ert´eke ´es ´ara. ´ Etel Zabpehely Csirke Toj´ as Tej Meggyes lep´eny Diszn´ oh´ us babbal
Adag 28 g 100 g 2 db 2,37 dl 170 g 260 g
T´apanyag Energia (kCal) 110 205 160 160 420 260
tartalom Feh´erje (g) 4 32 13 8 4 14
Ca (mg) 2 12 54 285 22 80
´ Ar (cent) 3 24 13 9 20 19
A felt´eteleknek p´eld´ aul 10 adag diszn´oh´ us babbal megfelelne ´es csak 1,9 doll´ arba ker¨ ul. Ez a gyomor sz´am´ara megterhel˝o t˝ unik, ez´ert bevezet¨ unk adag/nap korl´ atokat. (Igaz´ab´ol azt szeretn´enk, hogy a majdani modell¨ unk k´epes legyen kezelni az ilyen t´ıpus´ u megszor´ıt´asokat.) ´ Etel Zabpehely Csirke Toj´ as Tej Meggyes lep´eny Diszn´oh´ us babbal 1
Adag/nap 4 3 2 8 2 2
Az ´elet fenntart´ as´ ahoz sz¨ uks´eges energi´ at az elm´ ult 50 ´evben t´ ulbecs¨ ult´ek; ez a hiba a kering´esi probl´em´ ak ´es a cukorbetegs´eg el˝ ofordul´ as´ anak n¨ oveked´es´evel j´ art.
2
A legl´enyegesebb minden probl´em´an´al a v´altoz´ok kijel¨ol´ese. Most a v´altoz´ oinkat az ´etelekhez rendelj¨ uk ´es a v´altoz´o ´ert´eke az elfogyasztand´o ´etel mennyis´eg´et (adagban) jelenti majd. Jel¨olje x1 az elfogyasztand´o zabpehely, x2 a csirke, x3 a toj´ as, x4 a tej, x5 a meggyes lep´eny, x6 a diszn´oh´ us babbal adagok sz´ am´ at! Az ´etrendnek a k¨ovetkez˝o felt´eteleket kell kiel´eg´ıtenie: • Adag/nap korl´ at szerint 0 ≤ x1 ≤ 4 0 ≤ x2 ≤ 3 0 ≤ x3 ≤ 2 0 ≤ x4 ≤ 8 0 ≤ x5 ≤ 2 0 ≤ x6 ≤ 2 • Napi sz¨ uks´eglet szerint 110x1 +205x2 +160x3 +160x4 +420x5 +260x6 ≥ 2000 4x1 +32x2 +13x3 +8x4 +4x5 +14x6 ≥ 55 2x1 +12x2 +54x3 +285x4 +22x5 +80x6 ≥ 800 Itt figyelembe vett¨ uk, hogy egy ´etelb˝ol nem fogyaszthatunk negat´ıv mennyis´eget vagy t´ ul sokat, illetve ¨osszegezt¨ uk a benn¨ uk l´ v˝o t´ap´ert´eket. V´eg¨ ul pedig az ´etrend k¨olts´eg´et is kifejezhetj¨ uk a bevezetett v´altoz´okkal ´es megadott konstansokkal: 3x1 +24x2 +13x3 +9x4 +20x5 +19x6 Ezek ut´ an a di´eta probl´ema matematikai le´ır´asa a k¨ovetkez˝o: min
3x1
+24x2
+13x3
+9x4
+20x5
+19x6
110x1 +205x2 +160x3 +160x4 +420x5 +260x6 4x1 +32x2 +13x3 +8x4 +4x5 +14x6 2x1 +12x2 +54x3 +285x4 +22x5 +80x6 x1 x2 x3 x4 x5 x6 x1 , x2 , x3 , x4 , x5 , x6
3
≥ 2000 ≥ 55 ≥ 800 ≤ 4 ≤ 3 ≤ 2 ≤ 8 ≤ 2 ≤ 2 ≥ 0
2.2.
Dualit´ as
Vizsg´ aljuk meg az al´ abbi standard LP-t! max
4x1 +
x2 + 5x3 + 3x4
x1 − x2 − x3 + 3x4 5x1 + x2 + 3x3 + 8x4 −x1 + 2x2 + 3x3 − 5x4 x1 , x2 , x3 , x4
≤ 1 ≤ 55 ≤ 3 ≥ 0
(1) (2) (3)
A feladat megold´ asa helyett adjunk fels˝o becsl´est a c´elf¨ uggv´eny z ∗ ´ert´ek´ere! A (2) egyenl˝ otlens´eget 5/3-dal megszorozva egy fels˝o korl´atot kapunk z ∗ -ra. 5 (5x1 + x2 + 3x3 + 8x4 ≤ 55) 3 5 40 275 25 4x1 + x2 + 5x3 + 3x4 ≤ x1 + x2 + 5x3 + x4 ≤ 3 3 3 3 275 z∗ ≤ 3 A (2) + (3) egy jobb fels˝ o korl´atot ad: 5x1 + x2 + 3x3 + 8x4 ≤ 55 −x1 + 2x2 + 3x3 − 5x4 ≤ 3 4x1 + 3x2 + 6x3 + 3x4 ≤ 58 4x1 + x2 + 5x3 + 3x4 ≤ 4x1 + 3x2 + 6x3 + 3x4 ≤ 58 z ∗ ≤ 58 Tov´ abbvive a gondolatot, vegy¨ uk az egyenl˝otlens´egek nemnegat´ıv line´aris kombin´ aci´ oj´ at, azaz az els˝ ot szorozzuk meg y1 -gyel a m´asodikat y2 -vel, a harmadikat y3 -mal, majd adjuk ¨ossze ˝oket! (Nyilv´anval´oan teljes¨ ul a v´egs˝o egyenl˝ otlens´eg, ha y1 , y2 , y3 nemnegat´ıv.) (y1 + 5y2 − y3 )x1 + (−y1 + y2 + 2y3 )x2 + (−y1 + 3y2 + 3y3 )x3 + +(3y1 + 8y2 − 5y3 )x4 ≤ y1 + 55y2 + 3y3
4
Ha a k¨ ovetkez˝ o felt´etelek teljes¨ ulnek, akkor y1 + 55y2 + 3y3 egy fels˝o korl´atot ad a c´elf¨ uggv´eny ´ert´ek´ere: y1 −y1 −y1 3y1
+ 5y2 + y2 + 3y2 + 8y2
− y3 + 2y3 − 3y3 − 5y3
≥ ≥ ≥ ≥
4 1 5 3
A fentiek teljes¨ ul´ese mellett kapjuk: 4x1 + x2 + 5x3 + 3x4 ≤ y1 + 55y2 + 3y3 z ∗ ≤ y1 + 55y2 + 3y3 Ezzel a m´ odszerrel fels˝ o korl´atot keresve a k¨ovetkez˝o LP feladathoz jutunk: min
y1 y1 −y1 −y1 3y1 y1 ,
+ 55y2 + 5y2 + y2 + 3y2 + 8y2 y2 ,
+ y3 − y3 + 2y3 − 3y3 − 5y3 y3
≥ ≥ ≥ ≥ ≥
4 1 5 3 0
Az eredeti feladatot prim´ al, a fent kapottat pedig du´ al vagy du´ alis feladatnak nevezz¨ uk. Egy standard form´ aban l´ev˝o LP ´es a du´alisa ´altal´anosan: Prim´ al max
n P
Du´ al
cj xj
min
j=1 n P
m P
bi yi
i=1
aij xj
≤
bi
m P
i = 1, . . . , m
j=1
aij yi
≥ cj
j = 1, . . . , n
yi
≥ 0
i = 1, . . . , m
i=1
xj
≥
0
j = 1, . . . , n
1. T´ etel. (Gyenge dualit´ as) Ha (x1 , . . . , xn ) a prim´ al feladatnak, az (y1 , . . . , ym ) pedig a du´ al feladatnak egy lehets´eges megold´ asa, akkor n X
cj xj ≤
j=1
m X i=1
5
bi yi
Bizony´ıt´ as. A du´ alis probl´ema konstrukci´oj´ab´ol nyilv´anval´o. Form´alisan: n X j=1
cj xj ≤
n m X X j=1
!
aij yi xj =
i=1
m X
n X
i=1
aij xj yi ≤
hiszen i=1 aij yi ≥ cj , xj ≥ 0 (j = 1, . . . , n) ´es (i = 1, . . . , m).
bi yi ,
i=1
j=1
Pm
m X
Pn
j=1 aij xj
≤ bi , yi ≥ 0 2
Miel˝ ott kimondan´ ank ´es bizony´ıtan´ank az u ´n. er˝ os dualit´ as t´etelt vizsg´ aljuk meg egy LP feladat utols´o sz´ot´ar´at. A k¨ovetkez˝o, nagyon meglep˝o tulajdons´ agot vehetj¨ uk ´eszre: Az eredeti feladat utols´o sz´ot´ar´ab´ol kiolvashat´o a du´ alis feladat megold´ asa. Ha az eredeti megold´as optim´alis volt, akkor ez is az lesz. P´eld´ aul, ha a prim´al feladat utols´o sz´ot´ara: x2 = 14 − 2x1 − 4x3 − x4 = 5 − x1 − x3 − x6 = 1 + 5x1 + 9x3 + z = 29 −
x1 − 2x3
− − +
5x5 2x5 21x5 - 11 x5
+ 0 x6
x5 ←→ y1
y1 = 11
x6 ←→ y2
y2 = 0
x7 ←→ y3
y3 = 6
3x7 x7 11x7 - 6 x7
A megfeleltet´es: a du´ alis v´altoz´ok valamilyen ´ertelemben az eredeti LP mesters´eges v´ altoz´ oihoz rendelhet˝ok. A du´alis v´altoz´ok ´ert´eke pedig ´eppen a mesters´eges v´ altoz´ ok pillanatnyi c´elf¨ uggv´eny egy¨ utthat´oinak −1-szerese. Ez a hamarosan igazolt, tulajdons´ag rendk´ıv¨ ul hasznos mind a dualit´as t´etel bizony´ıt´ as´ an´ al, mind a gyakorlati probl´em´ak megold´as´an´al. 2. T´ etel. (Er˝ os dualit´ as) Ha a prim´ al feladatnak van egy optim´ alis (x∗1 , . . . , x∗n ) megold´ asa, akkor a ∗ ∗ du´ al feladatnak van olyan (y1 , . . . , ym ) optim´ alis megold´ asa, amelyekre n X
cj x∗j =
j=1
m X i=1
6
bi yi∗
Bizony´ıt´ as. Az el˝ obb lel´ atott gyenge dualit´as t´etel miatt el´eg, ha tal´alunk egy olyan (y1∗ , y2∗ , . . . ,yn∗ ) lehets´eges megold´ast a du´alis feladatra, amelyre a Pn Pm ∗ ∗ os´eg teljes¨ ul. A prim´al feladat megold´as´an´al j=1 cj xj = i=1 bi yi egyenl˝ bevezetj¨ uk a xn+i = bi −
n X
aij xj
(i = 1, . . . , m)
j=1
mesters´eges v´ altoz´ okat. Tegy¨ uk fel, hogy el´erkezt¨ unk az utols´o sz´ot´arhoz: z = z∗ +
n+m X
c¯k ≤ 0, (k = 1, . . . , n + m),
c¯k xk
k=1 ∗
z =
n X
cj x∗j
j=1
Ahogy eml´ıtett¨ uk, pr´ ob´ aljuk meg az yi∗ = −¯ cn+i (i = 1, . . . , m) behelyettes´ıt´est! Azt ´ all´ıtjuk, hogy ez a du´alis lehets´eges megold´asa, a t¨obbi sz´amol´as k´erd´ese csak. xn+i
z=
n X
cj xj = z ∗ +
c¯j xj −
cj xj =
∗
z −
m X
!
bi yi∗
+
}|
z
yi∗ bi −
n X
n X
{
aij xj
j=1
c¯j +
j=1
i=1
j=1
m X i=1
j=1
j=1 n X
n X
m X
!
aij yi∗
xj
i=1
Ezt az egyenl˝ os´eget egyszer˝ u algebrai manipul´aci´oval kaptuk az el˝oz˝ob˝ol, azaz minden x1 , x2 , . . ., xn ´ert´ekre igaznak kell lennie. Ebb˝ol ad´odnak a ⇒ z∗ =
m X
bi yi∗ ,
cj = c¯j +
i=1
m X
aij yi∗
i=1
egyenl˝ os´egek. Mivel c¯k ≤ 0 minden k = 1, . . . , n + m eset´en, ´ıgy m X
aij yi∗ ≥ cj
(j = 1, . . . , n)
yi∗ ≥ 0
(i = 1, . . . , m)
i=1
7
Teh´ at az yi∗ = −¯ cn+i (i = 1, . . . , m) a du´alis lehets´eges megold´asa, tov´abb´a Pm ∗ = Pn c x∗ , ´ b y attuk a t´etelt. 2 i i=1 j=1 j j es ezzel bel´ i A matematik´ aban egy oper´atort akkor nevez¨ unk dualiz´al´asnak, ha egym´as ut´ an k´etszer alkalmazva az eredeti probl´em´ahoz jutunk vissza. Az elnevez´es¨ unk jogoss´ ag´ at igazolja, hogy a du´alis feladat du´alisa a prim´al feladat. A du´ al feladat
max
m X
(−bi )yi
i=1 m X
(−aij )yi ≤ −cj
(j = 1, . . . , n)
i=1
yi ≥ 0
(i = 1, . . . , m)
A du´ alis feladat du´ alisa
min
n X
(−cj )xj
j=1 n X
(−aij )xj
≥ −bi
(i = 1, . . . , m)
j=1
xj
≥ 0
(j = 1, . . . , n)
Ez pedig nyilv´ anval´ oan ekvivalens a prim´al feladattal: max
n X
cj xj
j=1 n X
aij xj
≤ bi
(i = 1, . . . , m)
xj
≥ 0
(j = 1, . . . , n)
j=1
Kapcsolat a prim´ al ´ es a du´ al feladat k¨ oz¨ ott A dualit´ as t´etel megmutatja, hogy a prim´al ´es du´al feladat nem lehet tetsz˝ oleges kapcsolatban. A k¨ ul¨onb¨oz˝o vari´aci´ok (optimum, nincs lehets´eges megold´ as, nem korl´ atos a c´elf¨ uggv´eny) lehet˝os´eg´et az al´abbi t´abl´azat ¨osszegzi. 8
´ PRIMAL
Optim´ alis N.L.M.O. Nem korl´ atos
Optim´alis lehet nem lehet nem lehet
´ DUAL N.L.M.O. nem lehet lehet lehet
Nem korl´atos nem lehet lehet nem lehet
A t´ abl´ azat kilenc elem´eb˝ ol nyolcat k¨ozvetlen¨ ul megkaphatunk a gyenge, illetve er˝ os dualit´ as t´etelekb˝ ol. A kilencedik (a prim´alnak ´es a du´alnak nincs lehets´eges megold´ asa) pedig egy k¨onny˝ u feladat. Megjegyz´ es: A dualit´ as fogalma rendk´ıv¨ ul hasznos, mert rugalmas hozz´aa´ll´ ast tesz lehet˝ ov´e az LP feladatokhoz. H´arom ilyen lehet˝os´eget sorolunk fel itt: 1. A szimplex algoritmus v´egrehajt´as´an´al a l´ep´esek sz´ama k¨ozel´ıt˝oleg a sorok sz´ am´ aval ar´ anyos. ´Igy az olyan feladatok megold´as´an´al, melyek sok egyenl˝ otlens´eget ´es kev´es v´altoz´ot tartalmaznak, ´erdemes ´att´erni a du´ alis feladatra. 2. Akkor is c´elszer˝ u´ att´erni, ha a du´alis feladatban nincs sz¨ uks´eg, m´ıg az eredetiben lenne, az els˝o f´azisra. (P´eld´aul a di´eta probl´em´aban egy minimum feladat adott ´es a c´elf¨ uggv´eny egy¨ utthat´oi mind pozit´ıvak. A standardiz´ al´ as ut´ an ezek negat´ıvak lesznek, ´ıgy a du´alis jobboldala egy negat´ıv komponens˝ u vektor, amely a standardiz´al´asn´al pozit´ıvv´a v´ alik.) 3. Egy gyakorlati feladatn´al nem ritka, hogy menet k¨ozben u ´j felt´eteleket kell hozz´ avenni az LP-hez. Ekkor u ´jra kell kezdeni a megold´ast, t¨obbnyire ism´etelve a szimplex m´odszer els˝o f´azis´at. Ez elker¨ ulhet˝o a du´al feladattal dolgozva, hiszen ekkor az u ´j felt´etel csak mint egy u ´j, nem b´ azis v´ altoz´ o jelenik meg. Ekkor hozz´avehetj¨ uk a sz´ot´arunkhoz ´es folytathatjuk az elj´ ar´ ast az ´eppen aktu´alis b´azisb´ol.
2.3.
A du´ alis v´ altoz´ ok gazdas´ agi ´ ertelmez´ ese
A dualit´ as elm´elet egyik legszebb ´es leghasznosabb k¨ovetkezm´enye, hogy a du´ alis v´ altoz´ oknak szeml´eletes jelent´se tulajdon´ıthat´o. Az ´erthet˝os´eg
9
kedv´e´ert egy motiv´ aci´ oval el˝ozz¨ uk meg a t´etel kimond´as´at. max
n P
cj xj
min
j=1 n P
m P
bi yi
i=1
aij xj
≤
bi
i = 1, . . . , m
j=1
m P
aij yi
≥ cj
j = 1, . . . , n
yi
≥ 0
i = 1, . . . , m
i=1
xj
≥
0
j = 1, . . . , n
Egy, tal´ an a k¨ oz´episkolai fizik´ab´ol m´eg ismer˝os fogalommal ´el¨ unk, ´es u ´n. dimenzi´ o anal´ızist” hajtunk v´egre. Tegy¨ uk fel, hogy a LP feladatunk egy ” maxim´ alis nyeres´eget c´elz´ o, korl´atozott er˝oforr´asok mellett fel´ırt gy´art´asi folyamat modellje: m: er˝ oforr´ asok sz´ ama n: term´ekf´eles´egek sz´ama xj : a j-edik term´ekf´eles´egb˝ol gy´art´asra ker¨ ul˝o mennyis´eg aij : a j-edik term´ekf´ele egys´egnyi mennyis´eg´enek el˝o´all´ıt´as´ahoz sz¨ uks´eges mennyis´eg az i. er˝oforr´asb´ol bi : az i-edik er˝ oforr´ asb´ol rendelkez´esre ´all´o mennyis´eg cj : a j-edik term´ekf´ele egys´egnyi el˝o´al´ıt´as´aval keletkez˝o haszon Tegy¨ uk fel p´eld´ aul, hogy az xj -t kg-ban m´ert¨ uk (jelben dim(xj )=kg), m´ıg bi er˝ oforr´st m3 -ben, akkor az aij nyilv´an m3 /kg-ban m´erend˝o. Hasonl´oan term´esztes u ´gy venni, hogy a cj -t viszont Ft/kg-ban adjuk meg, ´ıgy a du´alis feladat bal oldal´ an egy aij yi mennyis´eg dimenzi´oja a cj dimenzi´oj´aval kell egyezzen. Azaz, ha dim(yi ) jel¨oli a m´ert´ekegys´eget, melyben az yi du´alis v´ altoz´ ot m´erni szeretn´enk, akkor dim(aij )dim(yi ) = dim(cj ) dim(yi ) = (F t/kg)(kg/m3 ) = F t/m3 ´Igy arra gondolhatunk, hogy yi nem m´as, mint az i-edik er˝oforr´as ´ ara (vagy ink´ abb ´ert´eke), amit a k¨ ovetkez˝o, bizony´ıt´as n´elk¨ ul kimondott t´etel formaliz´ al. 3. T´ etel. Ha egy LP feladatnak van legal´ abb egy nem degener´ alt optim´ alis megold´ asa, akkor van olyan pozit´ıv , ha |ti | ≤ minden i = 1, . . . , m-re, akkor a max
n X
cj xj
j=1
10
n X
aij xj
≤ bi + ti
(i = 1, 2, . . . , m)
j=1
xj
≥ 0
(j = 1, 2, . . . , n)
LP feladatseregnek is van optim´ alis megold´ asa, ´es az optimum ´ert´ek z ∗ (t1 , . . . , tm ) = z ∗ +
m X
yi∗ ti ,
i=1 ∗ pedig a du´ ahol z ∗ az eredeti LP feladat optimuma, y1∗ , . . . , ym al feladat (DP) optim´ alis megold´ asa.
A LP optim´ alis megold´ as´ ahoz tartoz´o yi∗ az u ´n. margin´alis ´ar”, vagy ” ∗ arny´ek ´ ´ ar”. Val´ oban yi nem m´as, mint az i-edik er˝oforr´asnak az LP ” megold´ oj´ anak a szempontj´ ab´ol n´ezett ´ert´eke, hisz az er˝oforr´as mennyis´eg´enek egys´egnyi n¨ ovel´es´evel (bizonyos hat´arokon bel¨ ul) ´eppen yi∗ -gal n¨ovekszik a nyeres´eg. Azaz yi∗ -n´ al nagyobb ´arat m´ar nem ´erdemes fizetni az i-edik forr´ as´ert, m´ıg kisebbet igen.2 Megjegyz´ es: A komplementarit´as t´etelnek szint´en van szeml´eletes jelent´ese. Tegy¨ uk fel, hogy az optim´ alis megold´asn´al vagyunk. A vagy kik¨ot´es szerint ha p´eld´ aul a prim´ al i-edik sor´aban szigor´ u egyenl˝otlens´eg teljes¨ ul, akkor az yi∗ = 0, azaz ha az i-edik er˝oforr´as nem fogyott el, akkor annak az ´ert´eke (sz´ amunkra) nulla. P´ elda: Erd˝ om˝ uvel´es 100 acre erd˝ o ter¨ ulet egy r´esz´et kiv´agj´ak ´es regener´al´odni hagyj´ak, m´asik r´esz´et kiv´ agj´ ak, de ut´ ana be¨ ultetik feny˝of´akkal. Az els˝o m´odszer acre-enk´ent 10 doll´ arba ker¨ ul ´es 50 doll´ art hoz, m´ıg a m´asikn´al ezek az ´ert´ekek 50 doll´ar, illetve 120 doll´ ar. Befektet´esre sz´ant ¨osszes t˝ok´enk 4000 doll´ar. K´erd´es, mekkora ter¨ uletet hagyjunk regener´al´odni ´es mennyit u ¨ltess¨ unk be, hogy a lehet˝ o legnagyobb profithoz jussunk? Optimum sz´ am´ıt´ asi modell: x1 : kiv´ ag´ asra, majd regener´al´od´asra sz´ant ter¨ ulet nagys´aga acre-ban x2 : kiv´ ag´ asra, majd be¨ ultet´esre sz´ant ter¨ ulet nagys´aga acre-ban 2 Az er˝ oforr´ asok ´ert´ek´et teh´ at egyfajta hasznoss´ ag alapj´ an alap´ıtottuk meg ´es ez nemcsak az LP a ´ltal k´ odolt k¨ ornyezett˝ ol f¨ ugg, hanem a v´ alasztott optim´ alis megold´ ast´ ol is.
11
1. m´ odszer 2. m´ odszer
befektet´es $10 $50
bev´etel $50 $120
hozam $40 $70
max 40x1 + 70x2 x1 + x2 ≤ 100 10x1 + 50x2 ≤ 4000 x1 , x2 ≥ 0 Optim´ alis megold´ as: x∗1 = 25, x∗2 = 75, z ∗ = 6250. A dualit´ as elm´elet´enek ereje azonban a probl´ema sokkal finomabb elemz´es´ere is k´epes. Nagyon k´ezenfekv˝ oen felmer¨ ulnek az al´abbi k´erd´esek: Mekkora kamat mellett ´erdemes k¨ olcs¨ ont felvenni a nagyobb hasznot hajt´o tev´ekenys´eg kiterjeszt´es´ere ? Mekkora k´ar ´eri a tulajdonost, ha le´eg egy acre erd˝o? A du´ alis megold´ as y1∗ = 32,5 ´es y2∗ =0,75. Az y2∗ a t˝oke ´ert´eke, azaz $1 plusz t˝ okebefektet´es 75 centet hoz. Ha enn´el olcs´obban megszerezhet˝o, akkor ´erdemes belev´ agni. M´asr´eszt, ha egy m´as tev´ekenys´egre ford´ıtva enn´el t¨ obb hasznot hoz, akkor ink´abb arra ford´ıtand´o. Sokkal meglep˝ obb els˝ o pillant´asra az egys´egnyi ter¨ uleten l´ev˝o fa ´ert´eke”, ” pontosabban az elveszt´es´evel j´ar´o k´ar. M´ıg a biztos´ıt´o alighanem valamely 40 ´es 70 doll´ ar k¨ oz´e es˝ o ¨ osszeget ´ıt´elne meg (hisz ennyi hasznot hozna az els˝ o, illetve a m´ asodik kitermel´es szerint) a gazda j¨ovedelme csak y1∗ = 32,5 doll´ arral cs¨ okken. A l´ atsz´ olagos paradoxon felold´asa, hogy akkor a t˝oke felszabadul´ o r´esze a nagyobb hasznot hoz´o tev´ekenys´egre ford´ıthat´o, ´ıgy m´ers´ekl˝ odik a k´ ar. Ez a jelens´eg figyelmeztet´esk´ent szolg´al: az ´arny´ek ´ar f¨ ugg a tev´ekenys´eg eg´esz´et˝ ol. Neh´ez t´ ulbecs¨ ulni ennek az egyszer˝ u ´all´ıt´asnak az implik´aci´oit. Sz´amtalanszor el˝ ofordul, hogy egy be´allt” komplex rendszer r´eszeinek pusztul´asa ” ut´ an gyorsan helyre´ all, s az eredetin´el gyorsabban fejl˝odik.
3.
Sztochasztikus Programoz´ as
Az optim´ alis ´es d¨ ont´esi modellekben sz´amos, a v´eletlent˝ol f¨ ugg˝o v´altoz´o szerepelhet. Illusztr´ aci´ ok´eppen n´eh´any p´elda: 1. Di´eta probl´ema 12
A probl´em´ at a min
cx Ax ≥ b x ≥ 0
alakban modellezt¨ uk, ahol az x vektor komponensei a k¨ ul¨onb¨oz˝o t´apl´ al´ekok fogyasztand´ o mennyis´eg´et a c komponensei ezek egys´eg´ar´at, az A m´ atrix aij eleme a j-edik t´apl´al´ek egys´egnyi mennyis´eg´enek iedik t´ ap´ert´eke (energia, feh´erje, k¨ ul¨onb¨oz˝o ´asv´anyi anyag, vitamin, stb.), m´ıg a bi az ig´enyelt t´ap´ert´ek. A val´os´agban az A, b ´es c egyes kompenensei lehetnek val´osz´ın˝ us´egi v´altoz´ok, melyeknek eloszl´as´ar´ol t¨ obb-kevesebb inform´ aci´onk van. 2. Portfoli´ o probl´ema Tegy¨ uk fel, hogy n k¨ ul¨onb¨oz˝o tev´ekenys´egbe/r´eszv´enybe fektethet¨ unk be x1 , x2 , . . . , xn t˝ ok´et, ´es ξ1 , ξ2 , . . . , ξn az egys´egnyi t˝oke v´eletlent˝ol f¨ ugg˝ o hozama az adott befektet´es mellett. Feltehetj¨ uk tov´abb´a, hogy Pn Pn ξ x . x = 1, x ≥ 0, ´ e s a nyeres´ e g¨ u nk i i i i i=1 i=1 3. G´ atmagas´ıt´ as Egy g´ at x egs´egnyivel t¨ort´en˝o magas´ıt´as´anak a k¨olts´eg´et jel¨olj¨ uk I(x)szel, tov´ abb´ a annak a val´osz´ın˝ us´eg´et, hogy a v´ızszint t´ ull´epi H-t P (H)val. Ha a v´ızszint magasabb, mint a g´at, akkor az ´arad´as k¨ovetkezt´eben V k´ ar keletkezik. ´ ag´ 4. Ujs´ arus probl´ema Ez egy klasszikus beruh´az´asi probl´ema. A kereslet egy u ´js´agra (esetleg kar´ acsonyf´ ara) egy ismert eloszl´as ξ val´osz´ın˝ us´egi v´altoz´o. Az u ´js´agos c egys´eg p´enz´ert veszi ´es (d > c) egys´eg´ert adja el. Ha x darabot vesz, akkor ξ ≤ x eset´en dξ − cx = −c(x − ξ) + (d − c)ξ, m´ıg ξ > x dx − cx = −(d − c)(ξ − x) + (d − c)ξ lesz a haszna. Sz´ and´ekosan nem feszegett¨ uk, mi is a c´el a felsorolt modellekben. L´atni fogjuk, hogy ezt igen alaposan meg kell fontolni ´es nem mindig hat´arozhat´o meg egy´ertelm˝ uen. 13
A di´eta probl´em´ ar´ ol azt l´athatjuk, hogy esetleg b´armekkora r´aford´ıt´as mellett sem el´eg´ıthet˝ o ki egy val´osz´ın˝ us´eggel az Ax ≥ b felt´etel. Szerencs´es esetben meg tudjuk becs¨ ulni a felt´etel s´er¨ ul´es´eb˝ol sz´armaz´o k´art, ´es ezt hozz´ aadva a cx c´elf¨ uggv´enyhez ´athidalhat´o ez a probl´ema. A m´ asik megk¨ ozel´ıt´es, hogy az Ax ≥ b teljes¨ ul´es´et egy el˝ore megadott, lehet˝ oleg nagy p val´ osz´ın˝ us´eggel k¨ovetelj¨ uk meg. Ez a p a rendszer¨ unk megb´ızhat´ os´ agi szintje, amely f¨ ugghet p´eld´aul a m˝ uszaki szabv´anyokt´ol.3 Bizonyos esetekben a val´osz´ın˝ us´egi v´altoz´ok helyettes´ıt´ese a v´arhat´o ´ert´ek¨ ukkel elfogadhat´ o megold´ashoz vezet. Tulajdonk´eppen ´ıgy j´artunk el a kor´ abbiakban. N´ezz¨ uk meg e helyett egy m´as ¨otletet ´es a hollandiai g´ atmagas´ıt´ as probl´em´ aj´ at, amelyet van Dantzig vizsg´alt 1956-ban. A k¨ ovetkez˝ okben n´eh´ any speci´alis optimaliz´al´asi illetve megb´ızhat´os´agi feladatot vizsg´ alunk. K¨ oz¨ os tulajdons´aguk csup´an a v´eletlen esem´enyekt˝ol val´ o f¨ ugg´es illetve a Bernoulli elv haszn´alata lesz.
A Bernoulli elv A Bernoulli elv szerint egy sztochasztikus rendszerben defini´alunk egy hasznoss´ agi f¨ uggv´enyt ´es ennek v´arhat´o ´ert´ek´et maximaliz´aljuk. (Ekvivalensen kock´ azat f¨ uggv´enyt ´es ennek v´arhat´o ´ert´ek´et minimaliz´aljuk.) Jelen esetben a kock´ azati f¨ uggv´eny nem m´as, mint a k¨olts´eg. G´ atmagas´ıt´ as Legyen H0 a g´ at jelenlegi, H az elegend˝o magass´aga; ezzel az x magas´ıt´as x = H − H0 . Nincs k´ ar, ha a tengerszint H alatt marad, k¨ ul¨onben az ´arad´as okozta k´ar V . A statisztik´ akb´ ol ismerj¨ uk a tengerszint eloszl´as f¨ uggv´eny´et. Ennek alapj´an annak az esem´enynek a p(H) val´osz´ın˝ us´ege, hogy egy ´even bel¨ ul meghaladja a H magass´ agot p(H) = p0 e−α(H−H0 ) , p0 = e−αH0 , 3
Term´eszetesen a di´eta probl´ema alkalmas lehet er˝ om˝ uvek, energiaszolg´ altat´ o rendszerek, v´ızgazd´ alkod´ asi probl´em´ ak stb. modellez´es´ere. Mindazon´ altal ezek a probl´em´ ak matematikai szempontb´ ol nagyon neh´ezek. B´ ar t¨ obb fontos speci´ alis esetben hat´ekonyan megoldhat´ o, de ezekkel itt nem foglalkozhatunk.
14
ahol p0 a H0 szint meghalad´as´anak val´osz´ın˝ us´ege, α pedig egy pozit´ıv konstans. Legyen I(x) a g´ at x-szel t¨ ort´en˝o emel´es´enek teljes k¨olts´ege, ´es tegy¨ uk fel, hogy ez I(x) = 0 ha x=0, m´ıg, I0 +kx, ha x > 0, ahol I0 ´es k pozit´ıv konstansok. (Az I0 interpret´ alhat´ o felvonul´asi k¨olts´egk´ent, az ´ep´ıt´es k¨olts´ege pedig line´ aris f¨ uggv´enye a magas´ıt´asnak.) A jelenlegi k¨olts´eg v´arhat´o ´ert´ek´enek kisz´ am´ıt´ as´ an´ al k´et dolgot kell figyelembe venn¨ unk: (i) az I(H − H0 ) determinisztikus ´ep´ıt´esi k¨olts´eget (ii) az 1., 2., . . . ´evekben bek¨ovetkez˝o esetleges k´ar ´altal okozott k¨olts´egeknek a jelenre visszavet´ıtett k¨olts´eg´et. Mivel ez ut´obbi a j-edik ´evben p(H)V (1 + 0, 01δ)−j , ahol δ az ´ alland´ onak felt´etelezett kamatl´ab, az ¨osszeg: I(H − H0 ) + p(H)V
∞ X
(1 + 0, 01δ)−j ≈ I(x) + 100p(H)V /δ.
j=1
A minimum meghat´ aroz´as´ahoz vegy¨ uk a d (I(x) + 100p0 e−αx V /δ) = 0 dx egyenlet gy¨ ok´et, amely a x =
1 α
log 100pδk0 V α megold´ast adja.
Biztos´ıt´ asok ´ es a kock´ azatker¨ ul´ es ´ Erdekes paradoxonokra bukkanhatunk, a biztos´ıt´asok racionalit´as´at ´es a Bernoulli elvet vetj¨ uk ¨ ossze. A Bernoulli elv tiszt´ an: A biztos´ıt´onak akkor fog szerz˝od´est k¨otni, ha a v´ arhat´ o nyeres´ege pozit´ıv (a k¨olts´egeit lesz´am´ıtva). Az u ¨gyf´elnek akkor ´eri meg biztos´ıt´ ast k¨ otni, ha a v´arhat´o vesztes´ege a biztos´ıt´as ideje alatt nagyobb, mint a biztos´ıt´ as d´ıja. Mindkett˝ o nem teljes¨ ulhet, azaz a biztos´ıt´as irracion´alisnak t˝ unhet. A paradoxon felold´ as´ ahoz a vagyon logaritmikus hasznoss´aga vezethet.4 4
B´ armely utilit´ as f¨ uggv´eny megfelel, ami figyelembe veszi a cs¨ okken˝ o hozad´ekot, azaz konk´ av.
15
Jelentse V egy szem´ely vagyon´anak nagys´ag´at, K a k´art, ami p val´osz´ın˝ us´eggel ´erheti ´es d az ezt megt´er´ıt˝o biztos´ıt´as d´ıj´at. Ekkor a d´ıj kifizet´es´enek k´enyelmetlens´ege: log(1 + V ) + log(1 + V − d) ≈
d V
m´ıg a baleset okozta (v´ arhat´o) utilit´as cs¨okken´es 1+V p(log(1+V )+log(1+V −K)) = p log 1+V −K
K = p log 1 + 1+V −K
Teh´ at akkor ´eri meg biztos´ıt´ast k¨otni, ha d K ≤ p log 1 + V 1+V −K
.
N´ezz¨ unk meg n´eh´ any speci´alis esetet: K << V , azaz az u ¨gyf´el nagyon gazdag. Haszn´aljuk a log(1 + x) = ´ x − x2 /2 + x3 /3 − x4 + ... Taylor sor els˝o elem´et. Atrendezve kapjuk a d ≤ pK felt´etelt, vagyis csak akkor racion´alis a biztos´ıt´as megk¨ot´ese, ha a v´ arhat´ o k´ ar nagyobb a d´ıjn´al. V = K/2, teh´ fele van vesz´elyben. Ezzel a biztos´ıt´as d´ıj´ara at a vagyon K a d ≤ 2pK log 1 + 1+K ≈ 2pK felt´etelt kapjuk. Itt teh´at a v´arhat´o k´ar k´etszeres´enek kifizet´ese sem indokolatlan. V = K, az eg´esz vagyon r´amehet a balesetre. Itt a d ≤ pK log(1 + K), azaz a v´ arhat´ o k´ ar sokszorosa is lehet a d´ıj. Ez viszont a vagyonnal n¨ovekszik ´es akkor ´erv´enyes, ha d << V , k¨ ul¨onben a log(1 + V ) + log(1 + V − d) ≈ Vd m´ ar pontatlan. Ekkor a d ≤ pK log(1 + K)/(1 + p log(1 + K)) ad´odik, azaz a teljes vagyont sosem ´erdemes a biztos´ıt´asra k¨olteni. Az u ´ js´ ag´ arus probl´ ema Amint m´ ar kor´ abban defini´altuk egy u ´js´agos c egys´eg p´enz´ert veszi ´es (d > c) egys´eg´ert ad el egy u ´js´agot. Ha x darabot vesz, akkor ξ ≤ x eset´en dξ − cx = −c(x − ξ) + (d − c)ξ, m´ıg ha ξ > x dx − cx = −(d − c)(ξ − x) + (d − c)ξ lesz a haszna. Term´eszetesen csak akkor v´arhat´o ´ertelmes v´alasz, ha van valamilyen felt´etelez´es¨ unk a kereslet eloszl´as´ar´ol. Legyen ez az eloszl´as el˝ osz¨ or diszkr´et, ´es jel¨ olj¨ uk a ξ = i esem´eny val´osz´ın˝ us´eg´et pi -vel, azaz P r(ξ = i) = pi . A v´ arhat´ o haszon ´ıgy a k¨ovetkez˝o lesz: 16
.
(d − c)Eξ −
X
c(x − i)pi −
i<x
X
(d − c)(i − x)pi ,
i>x
amely akkor maxim´ alis, ha a X
c(x − i)pi +
i<x
X
(d − c)(i − x)pi
i>x
¨osszeg minim´ alis. Ez ´ertelmezhet˝o u ´gy, mint egy v´arhat´o b¨ untet´es, ha a ξ aktu´ alis ´ert´eke elt´er x-t˝ ol; c egys´eget kell fizetni a ξ < x ´es d − c egys´eget az x < ξ esetben. Az els˝o esetben az eladatlan u ´js´ag ´ara jelenik meg, a m´ asodikban az elszalasztott lehet˝os´eget kell megfizetni.” Pszichikailag ” a k´et k¨ olts´eg k¨ oz¨ ott nagy k¨ ul¨onbs´eg lehet, az optimaliz´al´as szempontj´ab´ol ellenben semmi. Ennek megfelel˝oen egy d¨ont´es lehet˝oleg az ut´obbi alapj´an hozand´ o. Ha a v´eletlen ig´eny folytonos eloszl´ast k¨ovet, amelynek s˝ ur˝ us´egf¨ uggv´enye f , akkor az x v´ altoz´ ot is c´elszer˝ u folytonosnak tekinteni. Ekkor, az el˝oz˝ovel anal´ og m´ odon, a minimaliz´ aland´o kifejez´es¨ unk Z x
g(x) = c
(x − z)f (z)dz + (d − c)
Z ∞
−∞
(z − x)f (z)dz.
x
A sz´ amol´ as kedv´e´ert ´ at´ırva a g(x) f¨ uggv´enyt Z x
(x − z)f (z)dz + c
g(x) = c −∞
Z ∞
= cx
Z ∞
(x − z)f (z)dz + d
f (z)dz − c
−∞
(z − x)f (z)dz =
x
x
Z ∞
Z ∞
zf (z)dz − dx
−∞
Z ∞
Z ∞
zf (z)dz.
f (z)dz + d x
x
Ezt x szerint deriv´ alva kapjuk g 0 (x) = c − d
Z ∞
f (z)dz + dxf (x) − dxf (x) = d(F (x) − 1) + c,
x x ahol F (x) = −∞ f (z)dz, a ξ v´altoz´o eloszl´as f¨ uggv´enye. A g f¨ uggv´eny 0 minimum helye a g (x) = 0 egyenlet megold´as´aval kaphat´o meg, mely az x0 = F −1 ((d − c)/d) ´ert´eket adja az el˝obbiek szerint.
R
P´ elda: Legyen egy u ´js´ ag kiskereskedelmi ´ara c = 50, az elad´asi ´ara pedig d = 70. A megfigyel´esek szerint egy el´arus´ıt´o helyen a ξ kereslet egyenletes eloszl´ ast k¨ ovet 40 ´es 60 k¨ oz¨ ott. (Az egyszer˝ us´eg kedv´e´ert folytonos modellel 17
sz´ amolunk, b´ ar k¨ onnyen l´ athat´o, hogy a diszkr´et modell most ugyanezt az ´ert´eket adja.) ´Igy az eloszl´ as f¨ uggv´eny F (z) = P r(ξ < z), 0
ha − ∞ < z ≤ 40 z/20 − 2 ha 40 < z ≤ 60 F (z) = 1 ha 60 < z < ∞. Az F a (40, 60) intervallumon invert´alhat´o, ´es F −1 (z) = 20z + 40. Ezzel F −1 ((d − c)/d) = F −1 (2/7) = 45 eg´esz ´es 5/7, azaz durv´an 46 u ´js´agot c´elszer˝ u rendelni, mellyel a v´arhat´o nyeres´eg (d − c)E − c
Z x
(x − z)f (z)dz − (d − c)
Z ∞
−∞
Z 60
20
z/20dz − 50
(z − x)f (z)dz =
x
Z 46
(46 − z)/20dz − 20
Z 60
(z − 46)/20dz =
46
40
40
= 1000 − 45 − 98 = 857. P´ elda: Legyen most d = 3, c = 2 ´es a ξ kereslet k¨ovessen λ param´eter˝ u Pois5 son eloszl´ ast. Ekkor az optim´alis x ´ert´ek meghat´aroz´as´an´al minimaliz´aland´o X
c(x − i)pi +
X
(d − c)(i − x)pi
i>x
i<x
a k¨ ovetkez˝ o alakot ¨ olti f (x) :=
X
2(x − i)
i<x
λi e−λ X λi e−λ + (i − x) . i! i! i>x
Tekints¨ uk x-et folytonos v´ altoz´onak; ekkor f -et differenci´alva” a ” X λi e−λ X λi e−λ d f (x) ≈ 2 − =0 dx i! i! i<x i>x
egyenlet gy¨ ok´et kell megkeresn¨ unk. Minden diszkr´et eloszl´asra P i e−λ /i! = 1, azaz λ ´ıgy speci´ alisan ∞ i=0 X λi e−λ
2
i<x
i!
=2−2
x −λ λ e
x!
5
−
X λi e−λ i>x
i!
P
i pi
= 1,
.
A Poisson eloszl´ as nagyon sok v´eletlen folyamatban, pl. bolyong´ asok ill. telefonh´ıv´ asok stb. felbukkan, ´ıgy sokkal term´eszetesebb a felt´etelez´ese ebben az esetben, mint az egyenletes eloszl´ asnak.
18
Vegy¨ uk ´eszre, hogy i>x λi e−λ /i! sokkal kisebb, mint λx e−λ /x!, ha x nem t´ ul kicsi λ-hoz k´epest, ´ıgy az egyenlet nagyj´ab´ol √ λx e−λ 2πx(eλ)x e−λ 0=1− ≈1− , x! xx √ ahol az n! ≈ ( 2πn)(n/e)n k¨ozel´ıt´est, azaz a Stirling formul´at haszn´altuk. Ezzel x √ eλ = 2πxeλ , x P
amelynek e alap´ u logaritmus´at v´eve x(log λ + 1) − x log x = λ +
1 log(2πx). 2
Ha λ ´es x k¨ ozel van egym´ ashoz, akkor log λ ≈ log x, melyet az el˝oz˝o egyenletbe ´ırva az x∗ = λ + log λ +
1 log(2π) ≈ λ + log λ + 1 2
megold´ as ad´ odik. H´ al´ ozati megb´ızhat´ os´ ag Egy kor´ abban t´ argyalt modellhez hasonl´oan adott egy ir´any´ıtatlan G gr´ af az s ´es t kit¨ untetett pontokkal, tov´abb´a G ´eleihez val´osz´ın˝ us´egeket ren´ del¨ unk. Ertelmez´ es¨ unk szerint egy ´elhez rendelt sz´am az ´el j´arhat´os´ag´anak (tkp. l´etez´es´enek) a val´ osz´ın˝ us´ege, ´es az ´elek l´etez´esei f¨ uggetlen esem´enyek. L´ attuk, hogy ekkor p´eld´ aul a legnagyobb val´osz´ın˝ us´eggel l´etez˝o s − t u ´t keres´ese a legr¨ ovidebb u ´t probl´em´ara vezethet˝o vissza. Sokkal nehezebb probl´ema kisz´amolni azt, milyen val´osz´ın˝ us´eggel juthatunk el s-b˝ ol t-be. Ez olyannyira neh´ez, hogy hat´ekony algoritmus nem ismert r´ a ez id˝ o szerint, mi t¨obb, nem is rem´elt. Ez ann´al ink´abb szomor´ u, mert a probl´ema kezelhet˝ os´ege lenne az el˝ofelt´etele olyan d¨ont´esek vizsg´alat´ ahoz, hogy melyik ´el val´ osz´ın˝ us´eg´et ´erdemes n¨ovelni ´es mennyivel, vagy ´eppen mit okozna a hi´ anya. Nem t´ ul nagy feladatok azonban megoldhat´ok a lehets´eges esetek megfelel˝ o csoportos´ıt´as´aval. A gondolat egy rekurz´ıv algoritmus, amely az adatok sz´ am´anak f¨ uggv´eny´eben exponenci´ alis id˝ot ig´enyel. Legyen G a kiindul´ asi gr´af ´es v´alasszunk ki egy e ∈ E(G) ´elt, melynek val´ osz´ın˝ us´eg´et jel¨ olj¨ uk p(e)-vel. Jel¨olje tov´abb´a G \ e ´es G/e rendre azokat a gr´ afokat amelyekb˝ ol elhagytuk az e ´elt, illetve ahol az e ´el k´et v´egpontj´at egybeejtj¨ uk, azaz ¨ osszeh´ uzzuk e-t. Ekkor P r(G)-vel jel¨olve az s − t el´erhet˝os´eg val´ osz´ın˝ us´eg´et 19
P r(G) = (1 − p(e))P r(G \ e) + p(e)P r(G/e), ´es ´ıgy az eredeti feladatot k´et kisebb probl´em´ara vezett¨ uk vissza. P´ elda:
r 0, 5
s
r
r @ 0, 8 0, 9 @r t
0, 8
0, 8
r
0, 5
0, 5
r 0, 8 HH H
0, 5×
Hr
r 0, 8
0, 9×
r
0, 8
@ 0, 1× @ R 0, 5 @ r
0, 8
0, 8
r
r 0, 96
r 0, 864 0, 9
r
0, 5
r @ 0, 8 @r r
@ 0, 5× R @
r 0, 8 HHr 0, 9 r 0, 576 r0, 8
-
0, 501
@
0, 5
Vegy¨ uk ´eszre, hogy egy p´arhuzamos ´elp´ar, melyeknek val´osz´ın˝ us´ege p1 ´es p2 , helyettes´ıthet˝ o egy p1 + p2 − p1 p2 val´osz´ın˝ us´eg˝ u ´ellel. Az als´o ´ag kisz´ amol´ asa hason´ oan megy, illetve ha olyan r´eszgr´afra jutunk, amit m´ar kisz´ amoltunk, az felhaszn´ alhat´o. ´Igy P r(G) = 0, 72 × 0, 9 + 0, 501 × 0, 1 = ¨ 0, 6981. Osszehasonl´ıtva ezt a legnagyobb val´osz´ın˝ us´eg˝ uu ´ttal l´athat´o, hogy m´ıg az csak 0, 516 val´ osz´ın˝ us´eg˝ u, az ¨osszef¨ ugg˝os´egre enn´el sokkal nagyobb az es´ely. F¨ uggetlen alkatr´ eszek megb´ızhat´ os´ aga Tegy¨ uk fel, hogy egy n alkatr´eszb˝ol ´all´o szerkezet m˝ uk¨od´es´ehez mindnek a m˝ uk¨ od´ese sz¨ uks´eges, ´es ezek egym´ast´ol f¨ uggetlen¨ ul mennek t¨onkre. A szerkezet meg´ep´ıt´es´en´el az i-edik alkatr´eszre k´et k¨ ul¨onb¨oz˝o megb´ızhat´os´ag´ u ´es ´ ar´ u v´ alaszt´ asi lehet˝ os´eg¨ unk van: egy qi val´osz´ın˝ us´eggel m˝ uk¨od˝o, si ´ar´ u ´es egy pi val´ osz´ın˝ us´eggel m˝ uk¨ od˝o, ri ´ar´ u, ahol qi < pi ´es si < ri , 1 ≤ i ≤ n. A m˝ uszaki el˝ o´ır´ as szerint a szerkezetnek p val´osz´ın˝ us´eggel m˝ uk¨odnie kell. A c´el az alkatr´eszek olyan kiv´alaszt´asa, amely a szabv´anynak megfelel ´es minim´ alis k¨ olts´eg˝ u. Haszn´ aljuk az xi ∈ {0, 1} v´altoz´ot a modellben a qi , ekkor xi = 0, illetve a pi , ekkor xi = 1, val´osz´ın˝ us´eggel m˝ uk¨od˝o alkatr´esz alkalmaz´as´anak k´ odol´ as´ ara. Ekkor a m˝ uk¨ od´esi val´osz´ın˝ us´eg pontosan n Y i=1
qi
n xi Y pi i=1
lesz, m´ıg a k¨ olts´eg
20
qi
n X
ci xi +
n X
i=1
si ,
i=1
ha ci := ri − si , 1 ≤ i ≤ n eset´en. A c´el teh´at a n X
min
ci xi
i=1 n Y i=1
qi
n xi Y pi i=1
qi
≥p
xi ∈ {0, 1}, 1 ≤ i ≤ n feladat megold´ asa. Bevezetve a b := log(p/ ni=1 qi ) ´es az ai := log(pi /qi ) jel¨ ol´est ez ekvivalens az al´ abbi eg´esz ´ert´ek˝ u LP feladattal: Q
n X
min
ci xi
i=1 n X
ai xi ≥ b
i=1
xi ∈ {0, 1}, 1 ≤ i ≤ n. ez a kor´ abban ismertetett h´atizs´ak probl´em´ahoz hasonl´oan oldhat´o meg; p´eld´ aul a korl´ atoz´ as ´es sz´etv´alaszt´as (branch and bound) m´odszer´evel. A portfoli´ o probl´ ema Mint eml´ıtett¨ uk, az x1 + x2 + . . . + xn = 1, xi ≥ 0 felt´etelek mellett keres¨ unk P megold´ ast, a nyeres´eg¨ unk pedig a v´eletlent˝ol f¨ ugg˝o ni=1 ξi xi ¨osszeg. Ha helyettes´ıten´enk6 a ξi -t a µi = E(ξi ) v´arhat´o ´ert´ek´evel, egy trivi´alis h´atizs´ak feladathoz jutn´ ank: max
n P
µi x i
i=1
n P
xi = 1 (∗)
i=1
xi ≥ 0 Ha µ1 ≥ µ2 ≥ . . . ≥ µn , akkor a (∗) optim´alis megold´asa x∗1 = 1, x∗i = 0, ha 1 < i ≤ n. K¨ onnyen l´athat´o azonban, hogy ´altal´aban, ha ism´etelj¨ uk 6
Ez a Bernoulli elv alkalmaz´ asa lenne jelen esetben.
21
ezt a strat´egi´ at, az egy val´ osz´ın˝ us´eggel cs˝odh¨oz vezet. Sokf´ele pr´ob´alkoz´as t¨ ort´ent elfogadhat´ o megold´ as keres´es´ere, amely egyszerre ´ıg´er j´o befektet´est ´es v´edelmet a cs˝ od ellen. Az els˝ o¨ otlet Markowitz u ´n. hat´ekony portfoli´ oi.7 Tegy¨ uk fel, hogy nemcsak a ξ1 , . . . , ξn v´altoz´ok µi = E(ξi ) v´arhat´o ´ert´ekei, hanem a v´ altoz´ ok C kovariancia m´atrixa is rendelkez´esre ´all, ahol cij = E[(ξi − µi )(ξj − µj )]. Ennek seg´ıts´eg´evel kifejezhetj¨ uk egy x = (x1 , x2 , . . . , xn ) portfoli´o (megold´as) varianci´ aj´ at n X
V ar(
n X
ξi xi ) = E[(
i=1
(ξi − µi )xi )2 ] = xT Cx.
i=1
P
Egy x portfoli´ o hat´ekony, ha v´arhat´o hozama, E[ i ξi xi ], nem n¨ovelhet˝o a variancia n¨ ovel´ese n´elk¨ ul, ´es varianci´aja nem cs¨okkenthet˝o a v´arhat´o hozam cs¨ okkent´ese n´elk¨ ul. A hat´ekony portfoli´o teh´at egyfajta optimum: adott nyeres´eget felt´etelezve a minim´ alis kock´azattal j´ar, illetve egy r¨ogz´ıtett kock´azati szint mellett maxim´ alis nyeres´eget ig´er. Ha ρ > 1 hozam el´er´ese a c´elunk, akkor a k¨ ovetkez˝ ou ´n. kvadratikus programoz´ asi probl´ema megold´asa a v´alasz. min
xT Cx n P
µj x j
≥ ρ
j=1
n P
xj
= 1
xj
≥ 0 j = 1, . . . , n.
j=1
A feladat egy x∗ megold´ as´ at optim´ alis portfoli´ onak nevezz¨ uk. Nyilv´anval´oan egy optim´ alis portfoli´ o egyben hat´ekony portfoli´o is. Megjegyz´ esek: A feladat c´elf¨ uggv´enye ebben az esetben az ismeretlenek P Pn kvadratikus (n´egyzetes) f¨ uggv´enye, m u, azaz nem lesz i=1 j=1 cij xj xi alak´ line´ aris. Ezeknek a megold´ as´aval nem foglalkozhatunk, de utalunk r´a, hogy sz´ amos hat´ekony algoritmust fejlesztettek ki, melyek a kvadratikus programoz´ asi feladatok megold´ as´ara is alkalmasak. A m´asik felmer¨ ul˝o neh´ezs´eg 7
Ezeket Markowitz 1952-ben kezdte vizsg´ alni, ´es 1990-ben k¨ ozgazdas´ agi Nobel-d´ıjjal ismert´ek el az eredm´enyeit.
22
a szimmetrikus C m´ atrix n(n + 1)/2 elem´enek kisz´am´ıt´asa. (Ezeket term´eszetesen a kor´ abbi megfigyel´esekb˝ol kell meghat´aroznunk.) Mindk´et neh´ezs´eget ´ athidalhatjuk, ha a kovariancia minimaliz´al´asa helyett megel´egsz¨ unk P az ´ atlagos abszol´ ut elt´er´es E[| j (ξj − µj )xj |] mennyis´eg minimaliz´al´as´aval.8 A Konno-Yamazaki-f´ ele MAD modell Konno ´es Yamazaki 1990-ben javasolt m´odszere ´ıgy j´ar el, valamint a µi v´ arhat´ o ´ert´ekek ´es cij kovariancia egy¨ utthat´ok kisz´am´ıt´as´at elker¨ uli; k¨ ozvetlen¨ ul haszn´ alja a megfigyelt adatokat. (Az ´atlagos abszol´ ut elt´er´es angol neve ut´ an, mean absolute deviation, a modell neve MAD.) Ha T megfigyel´est v´egezt¨ unk a m´ ultban, rjt jel¨oli a j-edik befektet´es hozam´ at a t-edik megfigyel´esn´el ´es rj =
T 1X rjt , ajt = rjt − rj , T t=1
akkor a portfoli´ o optimaliz´ al´as a k¨ovetkez˝o alakban ´ırhat´o fel: min
1 T
T P P n
|
j=1 ajt xj |
t=1 n P
(∗)
≥ ρ
rj xj
j=1 n P
xj
= 1
i=1
≥ 0 j = 1, . . . , n.
xj
A (∗) probl´ema nem LP, de hasonl´oan a m´atrixj´at´ekokn´al alkalmazott gondolathoz LP feladatra reduk´alhat´o: min
−yt ≤
1 T
T P
yt
t=1
n P
ajt xt ≤ yt t = 1, . . . , T
j=1 n P
rj xj j=1 n P xj i=1
≥
ρ (∗∗)
=
1
xj
≥
0 j = 1, . . . , n.
8
Val´ oj´ aban a legfontosabb esetben, a t¨ obbv´ altoz´ os norm´ alis eloszl´ as eset´eben, a k´et m´ odszer ekvivalens.
23
Ezzel a modellel lehet˝ ov´e v´ alik eg´eszen nagy, val´o ´eletbeli probl´em´ak megold´ asa. Nem szabad elfelejten¨ unk azonban, hogy a kapott megold´as csak egy javaslat: egy t´enyleges portfoli´o kiv´alaszt´as´an´al sz´amtalan egy´eb szempont is figyelembe vehet˝ o. A szemi-MAD modell ´ Erdemes meggondolnunk a MAD modellt, ´es egy kicsit v´altoztatni rajta. P Id´ezz¨ uk fel, hogy a nj=1 ajt xj kifejez´es adja a (becs¨ ult) v´arhat´o hozamt´ol val´ o el˝ ojeles elt´er´est a j-edik id˝opontban. K´ezenfekv˝o, hogy ne ezek abszol´ ut ´ert´ekeinek ¨ osszeg´et minimaliz´aljuk, hanem csak azon tagoknak az abszol´ ut ´ert´ek ¨ osszeg´et, amelyek negat´ıvak. (Val´oban, hiszen ha v´arhat´o hozam becsl´es´en´el jobban teljes´ıt a a j-edik id˝opontban a portf´oli´o, az nem kellemetlen, hanem ´eppen kedvez˝o esem´eny.) Bevezetve az |x|− := x, ha x ≤ 0 ´es |x|− := 0, ha x > 0 jel¨ol´est, a probl´ema a k¨ovetkez˝o alakot ¨olti: max
1 T
T P P n
− j=1 ajt xj |
|
t=1 n P
≥ ρ
rj xj
j=1 n P
xj
= 1
i=1
≥ 0 j = 1, . . . , n.
xj
Ennek a probl´em´ anak az LP alakja k¨onnyen megadhat´o, ´es a MAD modelln´el is egyszer˝ ubb: max
1 T
T P
yt
t=1
n P j=1 n P
ajt xt ≥ yt t = 1, . . . , T
rj xj j=1 n P xj i=1
≥
ρ
=
1
yt ≤ xj ≥
0 t = 1, . . . , T 0 j = 1, . . . , n.
Megjegyz´ es: A MAD ´es a szemi-MAD m´odszerek nagyj´ab´ol ekivivalensek, ha az optim´ alis portf´ oli´ ok hozamainak eloszl´asa megk¨ozel´ıt˝oen szimmetrikus. 24
Ez nem sz¨ uks´egk´eppen ´ all fenn, ´ıgy a jelen vizsg´alatok szerint hasznosabbnak t˝ unik a szemi-MAD modell haszn´alata, hiszen a v´arhat´o sz´am´ıt´asi ideje mindenk´eppen kisebb.
25
4.
M´ atrix j´ at´ ekok
A matematika ´es a j´ at´ekok elm´elete gyakran ¨osszekapcsol´odik. Eml´ekezhet¨ unk de M`er`e lovag probl´em´aj´ara, melyet Fermat ´es Pascal egyid˝oben oldott meg, ´es a felt´eteles val´osz´ın˝ us´eg fogalm´at helyesen ragadva meg, hozz´ aj´ arult a val´ osz´ın˝ us´egsz´am´ıt´as megalapoz´as´ahoz. A j´at´ekok fogalma az´ ota is sz´ amtalan alkalommal felbukkan a matematika k¨ ul¨onb¨oz˝o ter¨ uletein, a halmazelm´eletben, kombinatorik´aban, bonyolults´agelm´eletben. Az anyagiasabb XX. sz´ azadban a k¨ozgazdas´agtudom´any ig´enye szint´en ´eletre h´ıvott n´eh´ any modellt. Ezek egyik´et, az u ´n. teljes inform´ aci´ os, v´eges, k´etszem´elyes, z´erus¨ ossszeg˝ u j´at´ekokat vizsg´aljuk r´eszletesen. Ebben az esetben a j´ at´ekosok strat´egi´ ai felsorolhat´ok ´es egy (i, j) p´arhoz hozz´arendelhet˝o az aij sz´ am, amit a sorj´ at´ekos nyer, az oszlopj´at´ekos pedig vesz´ıt, ha rendre az i-edik, illetve a j-edik strat´egi´ajukat j´atsz´ak. ´Igy a t¨om¨ors´eg kedv´e´ert h´ıvhatjuk ezeket a j´ at´ekokat m´ atrix j´ at´eknak. A m´ atrix j´ at´ekok le´ır´ as´anak els˝o l´ep´eseit Emil Borel tette meg 1921 ´es 1927 k¨ oz¨ ott. Jelent˝ os halad´ast ´ert el Neumann J´anos: 1928-ban bebizony´ıtotta az az´ ota h´ıress´e v´alt minimax t´etel´et ´es ezzel megmutatta hol kell keresni a megold´ asokat. K¨or¨ ulbel¨ ul 20 ´evvel k´es˝obb ˝o adott v´alaszt a hogyan k´erd´esre is, r´ amutatva a m´atrix j´at´ekok ´es a line´aris programoz´as kapcsolat´ ara. K´es˝ obb Dantzig, Gale, Kuhn ´es Tucker munk´aja nyom´an a m´ atrix j´ at´ekok elm´elete teljesen bele´ep¨ ult a line´aris programoz´as elm´elet´ebe. Ezt a fel´ep´ıt´est k¨ ovetj¨ uk mi is. Kezdj¨ uk egy p´eld´ aval, az u ´n. Morra j´at´ekkal. J´anos ´es Emil a k¨ovetkez˝ok szerint j´ atszik: egy fordul´ oban elrejtenek egy vagy k´et forintot, majd tippelnek, mennyit dugott az ellenf´el. Ha pontosan egy j´at´ekos tippel j´ol, akkor annyit nyer, amennyit k¨ oz¨ osen elrejtettek. Az ¨osszes t¨obbi esetben d¨ontetlen lesz, p´enz¨ ukn´el maradnak. Nyilv´anval´o, hogy egy-egy j´at´ekban mindketten a k¨ ovetkez˝ o n´egy strat´egia k¨ oz¨ ul v´alaszthatnak: Rejts k-t ´es tippelj l-et (r¨oviden [k,l]), ahol k = 1, 2 ´es l = 1, 2. Ezek J´anos ´es Emil tiszta strat´egi´ ai, a hozz´ ajuk tartoz´ o A m´ atrix pedig: Emil tiszta strat´egi´ai [1,1] [1,2] [2,1] [2,2] [1,1] 0 2 -3 0 J´ anos tiszta [1,2] -2 0 0 3 strat´egi´ ai [2,1] 3 0 0 -4 [2,2] 0 -3 4 0 Minden A val´ os m´ atrix defini´al egy j´at´ekot, ahol a sorj´at´ekos az egyik sort, az oszlopj´ at´ekos az egyik oszlopot v´alasztja minden fordul´oban, ´es a sorj´at´ekos
26
nyerem´enye a v´ alasztott sor ´es oszlop tal´alkoz´as´aban lev˝o aij elem. Az A m´ atrixot kifizet´esi m´ atrixnak, sorait/oszlopait pedig a sor/oszlop j´at´ekos tiszta strat´egi´ ainak nevezz¨ uk. Visszat´erve a p´eld´ ara azt tapasztaljuk, hogy nem tudunk egy´ertelm˝ uen j´ o sort tan´ acsolni J´ anos sz´ am´ara b´armelyikhez ragaszkodik is, vesz´ıteni fog. Az az ¨ otlete t´ amadhat (´es ez bek¨ovetkezett), hogy keverje tiszta strat´egi´ait, v´eletlenszer˝ uen hol ezt j´ atsza, hol azt. J´atszon pl. [1,2]-t ´es [2,1]-et 1/2 1/2 val´ osz´ın˝ us´eggel! Tegy¨ uk fel tov´abb´a, hogy egy j´at´ek sorozatban Emil c1 -szer v´ alasztotta az [1,1], c2 -sz¨or az [1,2], c3 -szor a [2,1] ´es c4 -szer a [2,2] tiszta strat´egi´ at (c1 + c2 + c3 + c4 = N ). Ha J´anos v´eletlen v´alaszt´asai f¨ uggetlenek voltak, akkor v´ arhat´oan fele-fele esetben tal´alkozott az [1,2] ´es [2,1] strat´egi´ aja Emil b´ armely tiszta strat´egi´aj´aval. Azaz c1 /2-sz¨or az [1,1]-t, ¨ c2 /2-sz¨ or az [1,2]-t ´es ´ıgy tov´abb. Osszevetve ezeket az A m´atrixszal, J´anos ´ v´ arhat´ o nyeres´ege (c1 − c4 )/2 forint. Igy a legrosszabb esetben (ha c1 =0 ´es c4 =N), akkor j´ atszm´ ank´ent ´atlagosan 50 fill´ert vesz´ıt J´anos, de nem t¨obbet. ´ Altal´ aban tegy¨ uk fel, hogy a sorj´at´ekos egy x = (x1 , . . . , xm ) vektor seg´ıts´eg´evel, m´ıg az oszlopj´ at´ekos egy y = (y1 , . . . , yn ) vektorral v´alasztja meg a j´ at´ek´ at, azaz a sorj´ at´ekos xi val´osz´ın˝ us´eggel v´alasztja meg az i-edik sort, m´ıg az oszlopj´ at´ekos yj -vel a j-edik oszlopot. Ekkor a sorj´at´ekos v´arhat´o nyerem´enye: m X n X
aij xi yj = xAy.
i=1 j=1
Term´eszetesen xi ≥ 0 ´es yj ≥ 0, ha i = 1, . . . , m ´es j = 1, . . . , n, valamint P Pm es nj=1 yj = 1. i=1 xi = 1 ´ Defin´ıci´ o. A nemnegat´ıv komponensekb˝ol ´all´o vektort sztochasztikusnak nevezz¨ uk, ha a komponenseinek ¨osszege egy. Egy sztochasztikus vektor ´altal defini´ alt strat´egi´ at (azaz fordul´or´ol fordul´ora f¨ uggetlen v´alaszt´ast a komponensek, mint val´ osz´ın˝ us´egek szerint) h´ıvunk kevert strat´egi´ anak. J´ anos el˝ obbi kevert strat´egi´aja nem m´as, mint x=(0, 1/2, 1/2, 0). Az el˝ obbiekb˝ ol nyilv´ anval´o, hogy egy x kevert strat´egi´at v´alasztva a sorj´ at´ekos v´ arhat´ o nyerem´enye legal´abb miny xAy, ahol y sztochasztikus vektor. A sorj´ at´ekos term´eszetesen egy olyan x∗ sztochasztikus vektort igyekszik tal´ alni, melyre az el˝oz˝o ´ert´ek a lehet˝o legnagyobb. Hasonl´oan egy y kevert strat´egia mellett az oszlopj´at´ekos garant´altan nem vesz´ıt t¨obbet ´atlagosan, mint maxx xAy, ahol x sztochasztikus vektor, c´elja pedig ezen ´ert´ek minimaliz´ al´ asa. A k´et ´ert´ek jelent´es´eb˝ol nyilv´anval´o, hogy min xAy ≤ max xAy y
x
27
Sokkal meglep˝ obb, hogy az egyenl˝os´eg is el´erhet˝o, azaz vannak olyan x∗ , y ∗ sztochasztikus vektorok, melyekre min x∗ Ay = max xAy ∗ . y
x
Ez az egyenl˝ os´eg az u ´n. minimax t´etel. x∗ ´es y ∗ rendre a sor ´es az oszlopj´ at´ekos optim´ alis strat´egi´aja, hisz az ´altaluk garant´altn´al jobb eredm´eny nem ´erhet˝ o el. Az ´ all´ıt´ as form´aja eml´ekeztethet benn¨ unket a dualit´asra, ´es val´ oban, igaz´ ab´ ol ekvivalensek, b´ar ez t´avolr´ol sem nyilv´anval´o. 4. T´ etel. (Minimax t´etel) Minden m×n-es A m´ atrixra van olyan x∗ m-dimenzi´ os sztochasztikus sorvek∗ tor ´es olyan y n-dimenzi´ os sztochasztikus oszlopvektor, melyekre min xAy = max xAy, y
x
ahol a minimumot az ¨ osszes n-dimenzi´ os sztochasztikus oszlopvektoron, m´ıg a maximumot az ¨ osszes m-dimenzi´ os sztochasztikus sorvektoron vessz¨ uk. Bizony´ıt´ as. Az els˝ o ´eszrev´etel, hogy miny xAy = minj m i=1 aij xi . Szavakban ez azt jelenti, hogy a sorj´at´ekos egy x kevert strat´egi´aj´ara van az oszlopj´ at´ekosnak olyan tiszta strat´egi´aja, amely optim´alis sz´am´ara. Ezt a k¨oP oleges vetkez˝ ok´epp l´ athatjuk be: Legyen t = minj m i=1 aij xi . Ha y tetsz˝ m-dimenzi´ os sztochasztikus oszlopvektor, akkor P
xAy =
n X
m X
y
!
aij xi
≥
i=1
j=1
n X
yj t = t
j=1
n X
yj = t,
j=1
´ıgy persze a miny xAy ≥ t is igaz. M´asr´eszt mivel azok az y vektorok, amelyeknek egy komponense egy, a t¨obbi nulla, sztochasztikus vektorok is egyben, ´ıgy min xAy ≤ y
m X
aij xi
i=1
minden j = 1, 2, . . . , n eset´en ´es ez adja az ´all´ıt´as m´asik ir´any´at. (HaP sonl´ ok´epp bel´ athat´ o, hogy maxx xAy = maxi nj=1 aij yj .) A fenti ´eszrev´etel nagyban egyszer˝ us´ıti a dolgunkat, mert a sorj´at´ekos optim´ alis strat´egi´ aj´ anak meghat´aroz´as´an´al csak az oszlopj´at´ekos tiszta strat´egi´ ait kell figyelembe venn¨ unk. Azaz max min j
m X
aij xi
(j = 1, 2, . . . , n)
i=1
28
m X
xi = 1
(∗)
i=1
xi ≥ 0
(i = 1, 2, . . . , m)
A d¨ ont˝ o ´eszrev´etel, hogy b´ ar ez a probl´ema nem LP, de ekvivalens egy LPvel. max z z −
m P
aij xi ≤ 0
i=1
m P
(j = 1, 2, . . . , n)
xi = 1
(∗∗)
i=1
xi ≥ 0
(i = 1, 2, . . . , m)
Val´ oban, a (∗∗) probl´ema b´armely z ∗ , x∗1 , . . . , x∗m optim´alis megold´asa leP gal´ abb egy z − aij xi ≤ 0 egyenl˝otlens´egnek egyenl˝os´eggel tesz eleget, ´ıgy P az LP optimuma z ∗ = min aij xj . Anal´ og m´ odon, az oszlopj´at´ekos optim´alis strat´egi´aj´at le´ır´o
min max i
n X
aij yj
(i = 1, 2, . . . , m)
j=1 n X
yj
= 1
yj
≥ 0
j=1
(j = 1, 2, . . . , n)
ekvivalens a min w w −
n P j=1
aij yj
≥ 0
m P
yj
= 1
yj
≥ 0
(i = 1, 2, . . . , m) (∗ ∗ ∗)
i=1
(j = 1, 2, . . . , n)
LP feladattal. Vegy¨ uk ´eszre, hogy a (∗∗) ´es (∗ ∗ ∗) egym´as du´alisai, ´es mindkett˝ onek van lehets´eges megold´asa. ´Igy a dualit´asi t´etel szerint a (∗∗)nak van egy z ∗ , x∗1 , . . . , x∗m optim´alis megold´asa, a (∗ ∗ ∗)-nak van egy w∗ , y1∗ , . . . , yn∗ optim´ alis megold´asa u ´gy, hogy z ∗ = w∗ . Mivel z ∗ = miny x∗ Ay, w∗ = maxx xAy ∗ , a t´etelt bel´attuk. 2 29
Defin´ıci´ o. A k¨ oz¨ os z ∗ = w∗ ´ert´eke az A m´atrix j´at´ek ´ ert´ eke. Az A m´atrix j´ at´ek igazs´ agos, ha z ∗ = w∗ = 0, szimmetrikus, ha aij = −aij . Nyilv´ an egy szimmetrikus j´at´ek (a szerepek felcser´elhet˝os´ege miatt) igazs´ agos. ´Igy joggal v´ arhatjuk, hogy a Morr´aban J´anos (´es persze Emil is) elker¨ ulheti a veszt´est. Val´ oban, a Morr´ahoz tartoz´o LP max z z + 2x2 − 3x3 z − 2x1 z + 3x1 z − 3x2 + 4x3 x1 + x2 + x3 x1 , x2 , x3 ,
+ 3x4 − 4x4 + + x4 x4
≤ ≤ ≤ ≤ = ≥
0 0 0 0 1 0
J´ anos egy optim´ alis megold´asa x∗ = (0, 3/5, 2/5, 0), a j´at´ek ´ert´eke pedig ∗ term´eszetesen z =0. Megjegyz´ es: Vegy¨ uk ´eszre, hogy a minimax t´etel bizony´ıt´asa egyben algoritmust is ad az optim´ alis strat´egi´ak kisz´amol´as´ara. (Neumann eredeti bizony´ıt´ asa egy m´ely topol´ ogiai eredm´enyt, az u ´n. Brouwer fixpont t´etelt haszn´ alta, ami nem konstrukt´ıv.) Borel 3×3-as ´es 5×5-¨os m´atrixokra bel´atta a minimax t´etelt, de nem tudta t´ ultenni mag´at azon a paradox jelens´egen, hogy a j´ at´ekosnak nem sz´ armazik el˝onye abb´ol, ha a kevert strat´egi´aj´at ´ persze h´atr´anya sem abb´ol, ha ezt k¨ozli.) Val´osz´ın˝ titokban tartja. (Es uleg ez a t´enyleg meglep˝ o eredm´eny g´atolta meg abban, hogy bizony´ıtsa a t´etelt ´altal´ anosan is.
M´ odos´ıtott Morra A j´ at´ekok elm´elete (´es a matematika) tele van meglepet´essel, ´es l´atsz´olagos ellentmond´ asokkal. Tegy¨ uk fel, hogy J´anos ´es Emil v´altoztattak egy kicsit a Morra szab´ alyain, mert p´eld´aul nem tudj´ak egyszerre deklar´alni a tippjeiket, el˝ ore le´ırni pedig nincs kedv¨ uk. A j´ozan ´esz azt s´ ugja, erre nincs is sz¨ uks´eg, hisz Emil azzal, hogy a saj´at tippj´et bejelenti, semmit sem mond el arr´ol, ami a kez´eben van. Term´eszetes h´at azt gondolni, hogy a m´odos´ıtott Morra is igazs´ agos. Alkalmazzuk r´ a az elm´elet¨ unket. J´anos az eddigieken k´ıv¨ ul n´egy u ´j tiszta strat´egi´ aval rendelkezik: [k, S] ´es [k, D] k=1, 2, ahol az els˝o koordin´ata azt 30
mondja meg, h´ anyat rejtsen, a m´asodik, hogy ugyanazt (S) vagy ellenkez˝o (D) tippet mondja be, mint Emil. Az u ´j m´atrix a k¨ovetkez˝o:
J´ anos tiszta strat´egi´ ai
[1,1] [1,2] [2,1] [2,2] [1,S] [1,D] [2,S] [2,D]
Emil tiszta strat´egi´ai [1,1] [1,2] [2,1] [2,2] 0 2 -3 0 -2 0 0 3 3 0 0 -4 0 -3 4 0 0 0 -3 3 -2 2 0 0 3 -3 0 0 0 0 4 -4
Megoldva a hozz´ atartoz´ o LP-t egy optim´alis strat´egia J´anos sz´am´ara p´eld´aul az x∗ =(0, 56/99, 40/99, 0, 0, 2/99, 0, 1/99). Emil optim´alis strat´egi´aja y ∗ =(28/99, 30/99, 21/99, 20/99). A j´at´ek ´ert´eke pedig z ∗ = w∗ = 4/99. Azaz a j´ at´ek hat´ arozottan el˝ony¨osebb J´anos sz´am´ara, ami els˝o pillant´asra nehezen ´erthet˝ o. Felold´ odik a paradoxon, ha arra gondolunk, hogy b´ar Emil nem ad inform´ aci´ ot a kez´eben l´ev˝o p´enzr˝ol, de ad inform´aci´ot az ´eppen megj´ atszott strat´egi´ aj´ar´ol. ´Igy az m´ar nem teljesen ismeretlen J´anos sz´ am´ ara, k¨ ovetkez´esk´epp ˝ o ki is haszn´alhatja ezt.
Bl¨ off ´ es alullicit´ al´ as
K´ artyaj´ at´ekban gyakran el˝ofordul, hogy a j´at´ekosok bl¨off¨olnek, holott a lap bemutat´ asa eset´en vesz´ıten´enek. (Hozz´atehetj¨ uk, nemcsak k´artyaj´ at´ekban van ez ´ıgy.) M´ asr´eszt nem mindig kezdem´enyeznek licitet (azaz konfront´ aci´ ot), hab´ ar azt biztosan nyern´ek. Ezt a viselked´est az emberi intuici´ ora hivatkoz´ assal szokt´ak kezelni, mely u ´gymond fel¨ ulemelkedik a h´etk¨ oznapi logik´ an. Egy, Kuhn ´altal 1950-ben vizsg´alt egyszer˝ u j´at´ekkal illusztr´ aljuk, hogy ez nem ´ıgy van, s a p´okerj´at´ekos viselked´ese t¨ok´eletesen racion´ alis. A j´ at´ekot 3 lappal (1, 2, 3) j´atsz´ak, mindk´et j´at´ekos egys´egnyi p´enzt tesz be ´es kap egy lapot. Ezut´an felv´altva licit´alnak/fogadnak, emelnek egys´egnyivel vagy passzolnak. A j´at´ek akkor fejez˝odik be, ha egy emel´esre emel´es, passzra passz, vagy emel´esre passz hangzik el. Az els˝o k´et esetben 31
megn´ezik a lapokat, ´es a nagyobb lapot tart´o viszi az ¨osszes t´etet, amit az ellenf´el fogadott. A harmadik esetben a passzol´o j´at´ekos elveszti a j´at´ek elej´en betett alapj´ at. Az al´ abbi ¨ ot kimenetel lehets´eges ezek alapj´an (A ´es B a j´at´ekosok, a fogad, illetve passzol pedig ´ertelemszer˝ uen ´ertend˝o) A passzol, B passzol 1 a magasabb lapot birtokl´onak A passzol, B fogad, A passzol 1 B-nek A passzol, B fogad, A fogad 2 a magasabb lapot birtokl´onak A fogad, B passzol 1 A-nak A fogad, B fogad 2 a magasabb lapot birtokl´onak A lapok leoszt´ asa ut´ an A-nak h´arom lehet˝ os´ege van. (Ezek m´eg nem A tiszta strat´egi´ ai, azokba be kell foglalni azt is, hogy A ismeri saj´at lapj´at.) 1. Passz, ´es ha B fogad, u ´jra passz 2. Passz, ´es ha B fogad, fogad 3. Fogad Egy teljes utas´ıt´ as k´eszletet, amely A sz´am´ara egy´ertelm˝ uen megmondja mit tegyen egy x1 x2 x3 h´ armassal ´ırhatunk le u ´gy, hogy az xj lehet˝os´eget j´atsza, ha a j lapot kapta. P´eld´ aul a 312 szerint A fogad, ha 1 van a kez´eben, mindig passzol, ha a 2-¨ ot kapta, m´ıg passzol az els˝o fordul´oban a 3-ra, a m´asodikban pedig fogad r´ a. Ezek a h´ armasok teh´at A tiszta strat´egi´ai. Hasonl´oan B-nek n´egy lehet˝ os´ege van. 1. Passz, b´ armit csin´ al A 2. Ha A passzol, passz; ha A fogad, fogad 3. Ha A passzol, fogad; ha A fogad, passz 4. Fogad, b´ armit csin´ al A. B tiszta strat´egi´ ai az y1 y2 y3 h´armasokkal ´ırhat´ok le u ´gy, hogy az yj a j lap birtokl´ asakor j´ atszand´ o lehet˝os´eg. A tiszta strat´egia p´arok kimenetel´et annak figyelembe v´etel´evel sz´am´ıtjuk ki, hogy a lehets´eges hat leoszt´as egyforma val´ osz´ın˝ us´eg˝ u. P´eld´ aul ha A a 312, B pedig az 124 tiszta strat´egi´at haszn´ alja, akkor a hat lehets´eges kimenetel:
32
A kez´eben 1 1 2 2 3 3
B kez´eben 2 3 1 3 1 2
j´at´ek menete A fogad, B fogad A fogad, B fogad A passzol, B passzol A passzol, B fogad, A passzol A passzol, B passzol A passzol, B passzol
A nyerem´enye -2 -2 +1 -1 +1 +1
´Igy A v´ arhat´ o nyerem´enye = 1/6 (-2-2+1-2+1+1) = -1/3. Hasonl´o m´odon kisz´ am´ıthatjuk a t¨ obbi lehet˝os´eget is. A 3 × 3 × 3 = 27, m´ıg B 4 × 4 × 4 = 64 tiszta strat´egi´ aval rendelkezik, ami egy 27 × 64-es m´atrix vizsg´alat´at ´ırja el˝o. Ennek k¨ ozvetlen vizsg´ alata, b´ar lehets´eges, meglehet˝osen komplik´alt lenne. Megpr´ ob´ alkozunk h´ at redukci´oval, amely jelent˝osen cs¨okkenti a probl´ema m´ert´ek´et, de szolg´ altat egy-egy optim´alis kevert strat´egi´at, illetve ezeken kereszt¨ ul a j´ at´ek ´ert´ek´et is. Kezdj¨ uk azzal, hogy az 1 lapot birtokolva b´armely j´at´ekos f¨ol¨oslegesen vesz´ıtene egy egys´eget, ha egy fogad´asra fogad´assal v´alaszolna, nem pedig passzal. Ugyan´ıgy, ha a 3-as lap van a kez´eben, ´ertelmetlen lenne egy fogad´ asra passzal v´ alaszolni, tov´abb´a egy paszt k¨ovet˝oen nyugodtan fogadhat. Kijelenthetj¨ uk teh´ at, hogy A-nak van legal´abb egy optim´alis kevert strat´egi´ aja, amelyben: (i) Ha 1 van a kez´eben, nem j´atsza a 2. lehet˝os´eget. (ii) Ha 3 van a kez´eben, nem j´atsza az 1. lehet˝os´eget. Ugyan´ıgy B-nek van olyan optim´alis kevert strat´egi´aja, amelyben: (i) Ha 1 van a kez´eben, nem j´atsza a 2. ´es 4. lehet˝os´eget. (ii) Ha 3 van a kez´eben, nem j´atsza az 1., 2. ´es 3. lehet˝os´eg´et. ´ Ugy k´epzelj¨ uk ezt, hogy a 2x2 x3 ´es az x1 x2 1 tiszta strat´egi´ak egyszer˝ uen el´erhetetlenek A sz´ am´ ara, csak u ´gy, mint B sz´am´ara a 2y2 y3 , 4y2 y3 , y1 y2 1, y1 y2 2 ´es az y1 y2 3 tiszta strat´egi´ak. Elk´epzelhet˝o, hogy ezzel elvesz´ıtj¨ uk az optim´ alis strat´egi´ ak egy r´esz´et, de bizonnyal marad legal´abb egy optim´alis kevert strat´egi´ aja mind A-nak, mind B-nek. Ebb˝ol k¨ovetkez˝oen a reduk´alt j´ at´ek ´ert´eke megegyezik az eredetivel. A fenti tiszta strat´egi´ ak kik¨ usz¨ob¨ol´ese ut´an A-nak 12, B-nek 8 tiszta strat´egi´ aja marad. Mi t¨ obb, tov´abbi egyszer˝ ut´esre ad´odik alkalom. Ha Anak 2 van a kez´eben, ak´ ar passzolhat is az els˝o fordul´oban, hisz B tart´ozkodik 33
a 2. lehet˝ os´egt˝ ol, ha 1-et birtokol, illetve az 1. ´es 3. lehet˝os´egt˝ol, ha 3. tart a kez´eben. ´Igy viszont A m´ asodik lehet˝os´ege pont olyan j´o, mint a 3. Eldobhatjuk h´ at A tiszta strat´egi´ai k¨oz¨ ul az x1 3x3 -at. Hasonl´oan, ha B a 2 lapot kapta, akkor az 1. lehet˝ os´ege ugyan olyan j´o, mint a 3., ´es 2. se rosszabb, mint a 4. Ezek alapj´ an B tiszta strat´egi´ai k¨oz¨ ul elhagyhat´o az y1 3y3 ´es az y1 4y3 . Ezek ut´ an A-nak m´ ar csak 8, B-nek pedig 4 tiszta strat´egi´aja marad, a reduk´ alt j´ at´ek m´ atrix pedig ´ attekinthet˝obb (s c´eljainknak megfelel).
112 113 122 123 312 313 322 323
114 0 0 −1/6 −1/6 1/6 1/6 0 0
124 314 324 0 −1/6 −1/6 1/6 −1/3 −1/6 −1/6 1/6 1/6 0 0 1/6 −1/3 0 −1/2 −1/6 −1/6 −1/2 −1/2 1/3 −1/6 −1/3 1/6 −1/6
Az ebb˝ ol keletkez˝ o LP feladatokat megoldva A sz´am´ara egy optim´alis kevert strat´egia az (1/3, 0, 0, 1/2, 1/6, 0, 0, 0), B sz´am´ara a (2/3, 0, 0, 1/3), a j´ at´ek ´ert´eke pedig -1/18. A j´at´ek, ahogy sejtett¨ uk, nem igazs´agos. A optim´ alis strat´egi´ aj´ at c´elszer˝ u egyszer˝ ubb utas´ıt´asokk´a konvert´alni: (i) Ha 1 van a kez´eben, akkor keverje az 1. ´es 3. lehet˝os´eget 5 : 1 ar´ anyban. (ii) Ha 2 van a kez´eben, akkor keverje az 1. ´es 2. lehet˝os´eget 1 : 1 ar´ anyban. (iii) Ha 3 van a kez´eben, akkor keverje a 2. ´es 3. lehet˝os´eget 1 : 1 ar´anyban. Vegy¨ uk ´eszre, hogy az istrukci´o bl¨offre buzd´ıt (azaz fogad´asra az els˝o menetben, mikor a legkisebb lapot - 1-et - kapta A) hat esetb˝ol egyszer, ´es tart´ozkod´ asra a t´et emel´es´et˝ ol (azaz passzra az els˝o menetben a legnagyobb lap birtokl´ asakor) az esetek fel´eben. Hasonl´ok´epp fogalmazhat´o B optim´alis strat´egi´ aja: (i) Ha 1 van a kez´eben, akkor keverje az 1. ´es 3. lehet˝os´eget 2 : 1 ar´ anyban. (ii) Ha 2 van a kez´eben, akkor keverje az 1. ´es 2. lehet˝os´eget 2 : 1 ar´ anyban. 34
(iii) Ha 3 van a kez´eben, akkor v´alassza mindig a 4. lehet˝os´eget. Ezzel B kis lapot (1, 2) tartva az esetek egyharmad´aban bl¨off¨ol, a licitt˝ol viszont nem tart´ ozkodik sohasem.
Egyszer˝ us´ıt´ esi lehet˝ os´ egek Dominancia: Az el˝ oz˝ o j´ at´ek elemz´es´eben haszn´alt gondolatmenetet k¨onnyen ´altal´anos´ıt´ hatjuk. Igy sz´ amos j´ at´ekban j´ol k¨ovethet˝o m´odon cs¨okkenthetj¨ uk a j´at´ekosok tiszta strat´egi´ ainak sz´ am´ at, m´ıg a j´at´ek l´enyege” nem v´altozik. ” Defin´ıci´ o. Az A kifizet´esi m´atrix egy r sora domin´ alja az s sort, ha arj ≥ asj minden j=1, 2, . . ., n eset´en. Hasonl´oan egy r oszlop domin´ alja az s oszlopot, ha air ≥ ais minden i=1, 2, . . ., m-re. 5. T´ etel. Egy m´ atrix j´ at´ekra az al´ abbiak igazak: (i) Ha egy r sort domin´ al egy m´ asik sor, akkor a sorj´ at´ekosnak van olyan ∗ ∗ x optim´ alis strat´egi´ aja, ahol xr = 0. Speci´ alisan, ha az r sort t¨ or¨ olj¨ uk a m´ atrixb´ ol, akkor nem v´ altozik a j´ at´ek ´ert´eke. (ii) Ha egy s oszlop domin´ al egy m´ asik oszlopot, akkor az oszlopj´ at´ekosnak van olyan y ∗ optim´ alis strat´egi´ aja, amelyben ys∗ = 0. Speci´ alisan, ha az s oszlopot t¨ or¨ olj¨ uk a m´ atrixb´ ol, akkor nem v´ altozik a j´ at´ek ´ert´eke. Bizony´ıt´ as. Tegy¨ uk fel, hogy az r sort domin´alja az s sor. (Hasonl´oan j´ arhatunk el akkor, ha az s oszlop domin´alja az r oszlopot.) A minimax t´etel miatt l´etezik egy x∗ , y ∗ optim´alis strat´egia p´ar a j´at´ekra. M´odos´ıtsuk az x∗ strat´egi´ at (¯ x) u ´gy, hogy x¯i := x∗i , ha i6=r, s, x¯r := 0 ´es x¯s := x∗s + ∗ xr . (Szavakban: mikor a strat´egia az r-edik sort j´atszan´a, akkor j´atszuk helyette az s-ediket.) A dominancia miatt nyilv´anval´o, hogy a sorj´at´ekos v´ arhat´ o nyerem´enye nem cs¨okken. 2
P´elda: −2 3 0 −4 A = A1 = 6 −2 7 −3
0 −6 3 2 7 4 8 3
A1 -ben a 3. oszlop domin´ alja a 4. oszlopot. 35
−3 1 5 2
−2 0 A1 = 6 7
3 −4 −2 −3
−6 2 4 3
−3 1 5 2
3 −2 −3
−6 4 3
−3 5 2
A2 -ben a 3. sor domin´ alja a 2. sort: −2 A3 = 6 7
A3 -ban az 1. oszlop domin´alja a 3. oszlopot: 3 A4 = −2 −3
−6 −3 4 5 3 2
A4 -ben a 2. sor domin´ alja a 3. sort:
3 A5 = −2
−6 −3 4 5
A5 -ben a 3. oszlop domin´alja a 2. oszlopot:
A6 =
3 −2
−6 4
Tov´ abbi egyszer˝ us´ıt´es m´ar nem lehets´eges, marad teh´at az eredeti A m´ atrix 1. ´es 3. sora, illetve 2. ´es 4. oszlopa, mint tiszta strat´egia. A probl´ema innen k¨ onnyen megoldhat´o. Nyeregpont: Jelentse mi az i-edik sor minimum´at, Mj pedig a j-edik oszlop maximum´at, azaz mi := minj aij , Mj := maxi aij . Legyen tov´abb´a m = maxi minj aij , M := minj maxi aij . K¨ onnyen bel´athat´ok az al´abbiak: (i) n ≤ M (ii) Ha m = M , akkor van olyan r ´es s, hogy ars = m = M . Defin´ıci´ o. Ha m = M, akkor az ars = m elemet az A m´atrix nyeregpontj´ anak nevezz¨ uk.
36
6. T´ etel. Ha az A m´ atrixnak van egy ars nyeregpontja, akkor az r-edik sor v´ alaszt´ asa a sorj´ at´ekos sz´ am´ ara, illetve az s-edik oszlop v´ alaszt´ asa az oszlopj´ at´ekos sz´ am´ ara egy optim´ alis strat´egia p´ art alkot. Tov´ abb´ a a j´ at´ek ´ert´eke v = ars . Bizony´ıt´ as. A sorj´ at´ekos nyerem´enye az i-edik sort v´alasztva legal´abb az oszlopj´ at´ekos vesztes´ege a j-edik oszlopot v´alasztva legal´abb Mj . r-edik sort, illetve az s-edik oszlopot v´alasztva a sorj´at´ekos m = ars erem´enyt garant´ alhat mag´ anak, m´ıg az oszlopj´at´ekos legfeljebb M = egys´egnyit vesz´ıt.
mi , Az nyars 2
P´elda: (i) 0 A = 3 1
m1 =-1 m2 =1 m3 =0 pont a23 .
M1 =3 0 3 1
M2 =2 -1 2 2
−1 2 2
M3 =1 0 1 0
0 3 1 2 0 1
M4 =3 3 2 1
m = 1 = M , a nyereg-
A j´ at´ek ´ert´eke v = 1, az optim´alis strat´egi´ak x∗ = (0,1,0), y ∗ = (0,0,1,0). (ii) A nyeregpont ´es a dominancia seg´ıts´eg´evel v´egrehajtott egyszer˝ us´ıt´esek f¨ uggetlenek egym´ ast´ ol, elk´epzelhet˝o, hogy az egyik m˝ uk¨odik, a m´asik nem. 4 A= 0 3
0 4 3
1 1 2
Az a33 =2 nyilv´ anval´ oan nyeregpont, de nincs a m´atrixban sor vagy oszlop dominancia.
37
Megjegyz´ es: Az optim´ alis kevert strat´egi´ak a nyeregpont ´altal´anos´ıt´asainak foghat´ ok fel. Ugyanis ha nem l´etezik nyeregpont, akkor ki kell l´epni” ” egy magasabb dimenzi´ os t´erbe (az eloszl´asok ter´ebe) ´es ott keresni nyeregpontot. Neumann eredeti bizony´ıt´asa ezen a gondolaton alapult, ´es az u ´n. Brouwer fixpont t´etelt alkalmazva megmutatta az ´altal´anos´ıtott nyeregpont l´etez´es´et.
5.
Nem z´ erus o ¨sszeg˝ u j´ at´ ekok
Az ´eletben el˝ ofordul´ o j´ at´ekoknak csak kis r´esze z´erus ¨osszeg˝ u, a legt¨obb esetben nem ez a helyzet. Ezekkel a j´at´ekokkal hihetetlen¨ ul sokf´ele probl´em´at modellezhet¨ unk. Sajnos ennek ´ara van. A z´erus ¨osszeg˝ u j´at´ekok elm´elet´eben oly hasznosnak bizonyult kevert strat´egi´ak ´altal´aban nem adnak j´o v´alaszt, mi t¨ obb, m´ ar azt sem k¨ onny˝ u megfogalmazni mit ´erts¨ unk optim´alis megold´as alatt. Nem ´ all m´ odunkban az ¨osszes koncepci´o ismertet´ese, m´eg kev´esb´e r´eszletes elemz´ese. Ehelyett v´azolunk n´eh´any l´enyeges ¨otletet, els˝osorban olyanokat, melyek beleillenek az eddigi t´argyal´asm´odunkban. P´ elda 1. K´et ´ asv´ anyvizet forgalmaz´o v´allalat (Appolinaris ´es Perrier) versenyeznek a piacon. A lehets´eges strat´egi´ak egy, illetve k´et doll´ar´ert adni az ´ asv´ anyv´ız palackj´ at. Az egyes strat´egi´ak alkalmaz´asa mellett keletkez˝o hasznot t´ abl´ azatban foglaltuk ¨ossze. A m´atrixba ´ırt sz´amp´ar els˝o eleme a sor-, a m´ asodik az oszlopj´ at´ekos haszna az adott strat´egia p´ar mellett. Perrier
Apollinaris
1$ 2$
1$ 0, 0 -5000, 5000
2$ 5000, -5000 0, 0
K¨ onnyen l´ athat´ o, hogy palackonk´ent 1 doll´ar´ert kell adni az ´asv´anyvizet. Ez ak´ ar a nyeregpont l´etez´es´ere val´o hivatkoz´assal, ak´ar az els˝o sor (oszlop) dominanci´ aj´ anak megmutat´as´aval a m´asodik sor (oszlop) felett t¨ort´enhet. ´ Altal´ aban is kimondhatjuk: a dominancia a z´erus ¨osszeg˝ u j´at´ekokn´al l´ atott m´ odszerrel anal´ og m´odon haszn´alhat´o. (Vegy¨ uk ´eszre, hogy a fenti j´ at´ek igaz´ ab´ ol felfoghat´ o z´erus ¨osszeg˝ u j´at´ekk´ent.) P´ elda 2. Egy hasonl´ o, b´ ar kicsit komplik´altabb esetben k´et v´allalat, a T¨ ok´eletes ´es a Var´ azslatos, m¨ uty¨ ur¨oket ´arulhat 1, 2 vagy 3 doll´aros ´aron. A lehet˝ os´egeket a kor´ abbiak szerint rendezt¨ uk t´abl´azatba; a nyeres´eg/vesztes´eg m´ert´ek´et az elad´ asi ´ ar ´es a piaci r´eszesed´es v´altoz´asai miatt v´altoz´o termel´esi 38
k¨ olts´egek szabj´ ak meg. T¨ok´eletes 1 2 3 1 0, 0 50, -10 40, -20 2 -10, 50 20, 20 90, 10 3 -20, 40 10, 90 50, 50 ´ Ez a j´ at´ek nem z´erus o¨sszeg˝ u, ´es nincs domin´ans strat´egia sem. Uj 9 gondolatra van sz¨ uks´eg, ez az u ´n. Nash egyens´ uly vagy Nash equilibrium. Var´ azslatos
Defin´ıci´ o. Egy strat´egia p´ar Nash egyens´ ulyi helyzet, ha egyik j´at´ekos sem tudja strat´egia v´ altoztat´ssal n¨ovelni nyerem´eny´et, amennyiben a m´asik nem v´ altoztat a strat´egi´ aj´ an. A p´eld´ ankban a (3,3) strat´egia p´ar nem Nash equilibrium, hisz a Var´ azslatos ´ att´erve a 2 doll´ aros strat´egi´ara n¨ovelheti haszn´at. Hasonl´oan bel´ athatjuk, hogy az (1,1) strat´egi´an k´ıv¨ ul nincs Nash egyens´ ulyi helyzet, ´ıgy a mindk´et c´eg ´ altal felsz´am´ıtott 1 doll´aros ´ar a re´alis” ´ar. N´emely ” k¨ ozgazd´ asz u ´gy v´eli, a piacgazdas´ag versenyhelyzet´enek hat´as´at siker¨ ult ´ıgy le´ırni: az alacsony ´ arakat. Ha a verseny nem lehets´eges (pl. nem egy doll´aros m¨ uty¨ ur¨ ok, hanem csak n´eh´ any c´eg ´altal gy´artott harci rep¨ ul˝o a t´et), akkor ez a mechanizmus nem k´epes alacsony ´arakat garant´alni. A Nash egyens´ ulyi helyzet a dominanci´ at haszn´al´o megold´asok kiterjeszt´ese, ´es a bemutatottn´al j´ oval ´ altal´ anosabb felt´etelek mellett is l´etezik. Az al´abbi p´elda szerint nem ad egy´ertelm˝ u megold´ ast. P´ elda 3. K´et r´ adi´ o´ allom´ as (L¨ok¨ott ´es Laza) h´arom profilb´ol v´alaszthat. Sug´ arozhatnak rockot (R), komolyzen´et (K) ´es h´ıreket (H). Az adott programok hallgat´ os´ aga 50, 30 ´es 20 sz´azal´ek. Ha egy ´allom´as egyed¨ ul fed le egy programot, akkor megszerzi annak a hallgat´os´ag´at (´es a vele ar´anyos rekl´ ambev´etelt), ha a m´ asikkal egy¨ utt, akkor fele-fele ar´anyban osztoznak. M´ atrix form´ aban: Laza 9
A fogalmat ´es a vele kapcsolatos legfontosabb t´eteleket John Forbes Nash alkotta meg az 50-es ´evek elej´en. K´es˝ obb a n´emet Reinhard Selten ´es a magyar Hars´ anyi J´ anos ´ert el jelent˝ os eredm´enyeket ebben az ir´ anyban, amit 1994-ben a h´ arm´ ojuk k¨ oz¨ ott megosztott k¨ ozgazdas´ agi Nobel-d´ıjjal ismertek el.
39
L¨ ok¨ ott
R K H
R 25, 25 30, 50 20, 50
K 50, 30 15, 15 20, 30
H 50, 20 30, 20 10, 10
K¨ onnyen ellen˝ orizhet˝ o, hogy csak a (K,R) ´es az (R,K) strat´egiap´ar Nash egyens´ ulyi helyzet. Nehezebb eld¨onteni, mit jelent ez a megold´as. Melyik ´ t˝ val´ osul majd meg, ´es milyen strat´egi´at v´alasszanak a j´at´ekosok ? Ugy unik, a Nash equilibriumok meghat´aroz´asa t´avolr´ol sem ad v´alaszt k´erd´eseinkre. Egy lehets´eges tov´ abbl´ep´esi ir´any annak vizsg´alata, mit hozhat a koordin´ aci´ o j´ at´ekosok egyes csoportjai k¨ oz¨ott, illetve hogyan oszhat´ o el a k¨oz¨osen szerzett haszon. Ez a motiv´ aci´ oja az u ´n. n-szem´elyes j´ at´ekok tanulm´anyoz´as´anak. Miel˝ ott r´ at´ern´enk erre, megeml´ıt¨ unk m´eg egy p´eld´at, amely azt sugallja, hogy a Nash egyens´ ulyi helyzet valamilyen ´ertelemben j´o megold´as, ´es ha probl´em´ aink is vannak vele az az ´elet ´es nem a modell meghat´arozatlans´ag´ ab´ ol ered. P´ elda 4. Mely oldal´ an haladjunk az u ´tnak” j´at´ek. K´et aut´o halad egym´as” sal szemben ´es a tal´ alkoz´ asn´al d¨onteni¨ uk kell az u ´t jobb vagy bal sz´el´ere h´ uz´ odjanak. A kiss´e fikt´ıv 10 ´ert´eket rendelve a biztons´agos tov´abbhalad´ashoz, illetve az ¨ ossze¨ utk¨ oz´eshez az al´abbi m´atrixot kapjuk: Honda
Fiat
Bal Jobb
Bal 1, 1 -10, -10
Jobb -10, -10 1, 1
Mind a (Bal, Bal), mind a (Jobb, Jobb) Nash egyens´ ulyi helyzet, de ez nem sokat seg´ıt rajtunk, ha belek´enyszer¨ ul¨ unk egy ilyen j´at´ekba. A t´ arsadalmi konvenci´ okkal szok´as koordin´alni az eff´ele szitu´aci´okat, s mint tudjuk a konkr´et esetre mindk´et megold´asra van p´elda. ´Igy azt´an nem is baj, hogy a modell¨ unk megold´asa nem egy´ertelm˝ u. Ha az lenne, akkor m´ar nem az ´eletet ´ırn´ a le, hanem az el˝o´ıt´eleteinket. P´ elda 5. Az evol´ uci´ o biol´ ogi´aban nagyon fontos szerepet kaptak egyes nem z´erus¨ osszeg˝ u j´ at´ekok. Az al´abbi p´elda az u ´n. Galamb-H´eja modell, amellyel egy popul´ aci´ o evol´ uci´ osan stabil strat´egi´ ait (ESS) szeml´eltethetj¨ uk. Egy galambfajon bel¨ ul - talalkoz´as eset´en - k´et egyed k¨oz¨ott k´etf´ele viselked´es lehets´eges: kit´ernek egym´ as el˝ol vagy harcba kezdenek. A kit´er´essel esetleg elvesztenek egy er˝ oforr´ ast (p´ar, ´elelem, f´eszkel˝ohely stb), m´ıg a konfliktus s´er¨ ul´essel, energia vagy id˝ o pocs´ekl´assal j´ar. Ha mindk´et galamb kit´erne, 40
akkor az egyik¨ uk megszerzi az er˝oforr´ast, legyen ez egyenl˝o es´ely˝ u. Egy galamb” azaz b´ek´es egyed tal´alkozik egy h´ej´aval” azaz egy harcias egyed” ” del, akkor a galamb” kit´er, elker¨ uli a s´er¨ ul´est, de elveszti az er˝oforr´ast, ” ami ´ıgy a h´eja” zs´ akm´ anya lesz. K´et h´eja” tal´alkoz´asa mindkett˝ore n´ezve ” ” jelent˝ os h´ atr´ annyal j´ ar. Az egyedek vagy egyik, vagy a m´asik viselked´est k¨ovetik; k´erdes, melyik a jobb? K¨ onnyen l´ athat´ o, ak´ ar egyik, ak´ar m´asik viselked´es v´alik kiz´ar´olagoss´a, egy olyan egyed, amely ett˝ ol a norm´at´ol el´er jelent˝os el˝onybe ker¨ ul. Teh´ at a c´el egy olyan stabil helyzet megtal´al´asa, melyben az egyed sz´ am´ ara nincs ok v´ altoztatni a viselked´es´en. Oldjuk meg ezt egy fikt´ıv kifizet´esi m´ atrix eset´en. galamb h´eja galamb 2, 2 -1, 5 h´eja 5, -1 -9, -9 Az galamb-h´eja” eloszl´as x ´es 1 − x, azaz x val´osz´ın˝ us´eggel b´ek´es egy ” egyed, 1−x-szel agressz´ıv. Felt´eve, hogy a popul´aci´o el´eg nagy, egy galamb” ” v´ arhat´ oan 2x − 1(1 − x) = 3x − 1, egy h´eja” pedig 5x − 9(1 − x) = 14x − 9 ” nyeres´eget k¨ onyvelhet el. Egyens´ uly, azaz ESS akkor van, ha 3x0 − 1 = 15x0 −9, vagyis x0 = 2/3. Teh´at a popul´aci´o el˝ore meghat´arozhat´o ar´anyban mutat b´ek´es vagy harcias viselked´est. Nem meglep˝o, ha cs¨okkentj¨ uk az er˝ oforr´ as ´ert´ek´et (ami 3 volt a p´eld´aban) illetve az id˝o´et, akkor a b´ek´es, m´ıg ha a s´er¨ ul´es kock´ azat´ at (8), akkor a harcias viselked´es terjed a popul´aci´oban. Az al´ abbi fel´ all´ asban x0 = 9/10. galamb h´eja
galamb 1, 1 2, 0
h´eja 0, 2 -9, -9
Ezt az apr´ ocska modellt neh´ez t´ ul´ert´ekelni: meglep˝oen sz´eles a jelens´egek k¨ ore, melyre k´epes magyar´ azatot adni. P´ elda 6. Sz´eles k¨ orben ismert az u ´n. Prisoner Paradox, azaz az fogoly dilemma. Ez a v´ adalku lassan n´alunk is meghonosod´o int´ezm´enye ´altal keletkez˝ o j´ at´ek”, egy klasszikus m´atrixa: ” vall tagad vall -5, -5 0, -10 tagad -10, 0 -1, -1 Ebben a k¨ oz¨ os optimum” a tagad-tagad, ami nyilv´an nem Nash egyens´ ulyi ” helyzet, hisz a vall-vall az egyed¨ uli ilyen. 41
6.
n-szem´ elyes j´ at´ ekok
Az n-szem´elyes j´ at´ekok vizsg´alat´at Neumann J´anos ´es Oskar Morgenstern kezdte el. Mint kor´ abban utaltunk r´a, nem valamif´ele h´arom szem´elyes ” sakk”, vagy a futball le´ır´ asa a c´el, hanem a racion´alis osztozkod´as t¨orv´enyeinek tanulm´ anyoz´ asa abban az esetben, mikor a j´at´ekosok egy tetsz˝oleges csoportj´ anak ereje” ismert. ” Defin´ıci´ o. Egy n-szem´elyes j´at´ek alatt a k¨ovetkez˝o rendszert ´ertj¨ uk: Adott az I = {1, 2, . . . , n}, a j´at´ekosok halmaza. Egy S ⊆ I halmazt koal´ıci´ onak nevezz¨ uk, ´es adott egy v : 2I → R (a koal´ıci´okhoz egy val´os sz´ amot rendel˝ o) u ´n. karakterisztikus f¨ uggv´ eny u ´gy, hogy (1.) v(∅) = 0 (2.) v(S ∪ T ) ≥ v(S) + v(T ), ha S, T ⊆ I ´es S ∩ T = ∅. A v(S) jelenti szeml´eletesen azt a hasznot (kifizet´est, hatalmat stb.), amit az S-ben l´ev˝ o j´ at´ekosok egym´assal ¨osszefogva egy¨ uttesen el´erhetnek (ak´ ar a t¨ obbiek ellen´ere is). A v(S ∪ T ) ≥ v(S) + v(T ) az S ∩ T = ∅ eset´en azt fejezi ki, hogy a k´et csoport ¨osszefogva legal´abb annyit el´er, mint a k¨ ul¨on 10 szerzett haszon ¨ osszege. Ezt szuperaddit´ıv tulajdons´ agnak h´ıvjuk. P´ elda 1. Ingatlan fejleszt´es (k´et v´ as´ arl´ os piac) Egy f¨ oldm˝ uves ´ altal birtokolt f¨old mez˝ogazdas´agi ´ert´eke 100 ezer doll´ar. K´et vev˝ o p´ aly´ azik r´ a, az egyik lak´as´ep´ıt´essel 200 ezer, a m´asik bev´as´arl´o k¨ ozpont l´etrehoz´ as´ aval 300 ezer doll´ar hasznot ´erhet el a f¨old felhaszn´al´as´aval. Vegy¨ uk ´eszre, hogy m´ıg a f¨oldm˝ uves egymag´aban is k´epes haszn´at venni a f¨ oldj´enek, addig az ´ep´ıt˝ ok nem. Ez a k¨ovetkez˝o 3-szem´elyes j´at´eknak felel meg: I = {1, 2, 3}, ahol 1: f¨ oldm˝ uves, 2, 3 pedig a k´et vev˝ojel¨olt. v(∅) = 0 v({1,2}) = 200000 v({1}) = 100000 v({1,3}) = 300000 v({2}) = v({3}) = 0 v({2,3}) = 0 v({1,2,3}) = 300000 ´ Altal´ aban az ´ert´ek a k¨ ul¨ onb¨oz˝o tulajdonosok felhaszn´al´as´aban a, b ´es c, ahol a < b < c. 10
Az o ¨sszefog´ assal ezt el is tudj´ ak ´erni, hisz megtehetn´ek, hogy k¨ ul¨ on-k¨ ul¨ on j´ atszanak v(S) illetve v(T ) nyerem´enyt szerezve, majd ut´ anna egyes´ıten´ek a nyerem´eny¨ uket.
42
P´ elda 2. A t¨ obbs´egi j´ at´ekok Ez a klasszikus 50%+1 szavazattal megval´osul´o d¨ont´eseket modellezi. I = {1, . . . , n} (
v(S) =
1 eset´en S nyer” ” 0 eset´en S vesz´ıt” ” (
v(S) =
1 ha |S| > n/2 0 k¨ ul¨onben.
P´ elda 3. A s´ ulyozott t¨ obbs´egi j´ at´ekok Az i-edik j´ at´ekosnak wi szavazata van ´es q szavazat kell a gy˝ozelemhez. I = {1, . . . , n} P 1 ha wi ≥ q i∈S v(S) = 0 k¨ ul¨onben Jel¨ olj¨ uk ezt a j´ at´ekot a r¨ovidebb (q; w1 , w2 , . . . , wn ) form´aval. Vegy¨ uk ´eszre, hogy p´eld´ aul a (3; 2, 2, 2, 2) j´at´ek” nem j´at´ek a defin´ıci´onk szerint, ” mert a v f¨ uggv´eny nem szuperaddit´ıv. Defin´ıci´ o. Egy n-szem´elyes j´at´ek egyszer˝ u, ha a v karakterisztikus f¨ uggv´eny csak 0 ´es 1 ´ert´eket vesz fel. P´ elda 4. Az ENSZ Biztons´ agi Tan´ acs m˝ uk¨ od´ese. A BT-nek 5 ´ alland´ o ´es 10 ideiglenes tagja van. Egy hat´arozat ´eletbe l´ep, ha mind az ¨ ot ´ alland´ o ´es legal´abb n´egy ideiglenes tag megszavazza. Ez fel´ırhat´ o, mint (39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1) s´ ulyozott t¨obbs´egi j´at´ek. Imput´ aci´ ok (kifizet´ esek) Az n-szem´elyes j´ at´ekokban a j´at´ekosoknak jut´o ´esszer˝ u kifizet´eseket akarjuk meghat´ arozni. Egy kifizet´est egy x = (x1 , x2 , . . . , xn ) n-dimenzi´os val´os vektorral ´ırhatunk le, ahol xi az i-edik j´at´ekos r´esze. Aesophus mes´ej´evel ellent´etben feltessz¨ uk, hogy az osztozkod´ast csak a v karakterisztikus f¨ uggv´eny befoly´ asolja, valamint a j´ at´ekosok tiszt´aban vannak az ´erdekeikkel ´es megv´edik azokat.11 Sz´ oba j¨ on az al´abbi k´et szempont: 1. xi ≥ v({i}), i = 1, . . . , n, sz´oban Egy´eni racionalit´as” ” Pn 2. i=1 xi = v(I), avagy Pareto optimalit´as.” ” 11
Val´ oj´ an ez el´eg er˝ os ´es az ´eletben ritk´ an teljes¨ ul˝ o felt´etel.
43
Az 1. pont azt fejezi ki, hogy az egyik j´at´ekos sem fogad el olyan kifizet´est, amelyn´el jobbat (mindenf´ele koal´ıci´o n´elk¨ ul) egymaga is k´epes el´erni. A Pn x ≤ v(I) annyit tesz: nem oszthat´ o t¨obb, mint amennyi van. Az i=1 i egyenl˝ os´eg viszont megk¨ oveteli, hogy a j´at´ekosok ´altal megszerezhet˝o maxim´ alis ¨ osszeget osszuk sz´et. (Azaz egyfajta kooper´aci´ora k´enyszer´ıthetj¨ uk” ” a j´ at´ekosokat.) Defin´ıci´ o. Az olyan x ∈ Rn vektorokat, amelyekre teljes¨ ulnek az 1. ´es 2. felt´etelek, imput´ aci´ oknak h´ıvjuk, az ¨osszes imput´aci´o halmaz´at pedig A(v)-vel jel¨ olj¨ uk. P´ elda 4. I = {1, 2, 3}, v(S) = 0, ha |S| < 2, m´ıg v(S) = |S|/3 k¨ ul¨onben. Ekkor az imput´ aci´ ok halmaza A(v) = {x ∈ R3 : xi ≥ 0,
3 X
xi = 1}.
i=1
Az imput´ aci´ ok A(v) halmaza t´ ul nagy”, ´ıgy ´altal´aban nem tekinthet˝o ” megold´ asnak. K¨ ul¨ onb¨ oz˝ o, t¨obb´e-kev´esb´e ´esszer˝ u felt´etelekkel szok´as sz˝ uk´ıteni az A(v)-t, ´es a kapott r´eszhalmazt deklar´alni a l´etrej¨ohet˝o megold´asok halmaz´ anak. A sokf´ele megk¨ozel´ıt´es sz´amos vit´ara adott alkalmat ´es a mai napig sem lehet egy´ertelm˝ u gy˝oztest hirdetni. Mi h´arom koncepci´ot fogunk v´ azolni, a mag (core), a stabil halmaz ´es a Shapley ´ert´ek fogalm´at. Ezek mindegyike nagyon tanuls´ agos. Defin´ıci´ o. Ha x, y ∈ A(v), akkor egy ∅ = 6 S ⊆ I hat´ ekonyan prefer´ alja P x-et y-nal szemben, ha xi > yi minden i ∈ S eset´en ´es i∈S xi ≤ v(S). Jelben x S y. Az elnevez´es ´es a motiv´aci´o nyilv´anval´o. Az xi > yi i ∈ S miatt az SP beli j´ at´ekosok jobban kedvelik x-et, mint y-t. A i∈S ≤ v(S) a hat´ekonys´ag, ugyanis az S koal´ıci´ o kik´enyszer´ıtheti az y elvet´es´et ´es a sz´am´ara el˝ony¨osebb xi (i ∈ S) kifizet´est garant´ alhatja tagjainak. P´ elda 5. Vegy¨ uk a 4. p´eld´aban szerepl˝o j´at´ekot ´es az x = (1/3, 5/12, 1/4), y = (1/2, 1/3, 1/6) ´es z = (9/24, 1/3, 7/24) vektorokat. L´athat´o, hogy x, y, z ∈ A(v), tov´ abb´ a x {2,3} y (x2 = 5/12 > 1/3 = y2 , x3 = 1/4 > 1/6 = y3 , ´es x2 + x3 = 5/12 + 1/4 ≤ v({2, 3}) = 2/3). Hasonl´oan bel´athat´o a z {1,3} x rel´ aci´ o; ugyanakkor nincs olyan ∅ 6⊆ {1, 2, 3}, amelyre z S y. (Ez azt jelenti, hogy m´ıg egy r¨ ogz´ıtett S-re a S ” rel´aci´o tranzit´ıv. Ezzel ” szemben ha u ´gy defini´ alunk egy ” rel´aci´ot, hogy x y akkor ´es csak ” akkor, ha l´etezik olyan ∅ 6= S ⊆ I, melyre x S y, akkor ez a ” rel´aci´o ” nem tranzit´ıv.)
44
Defin´ıci´ o. Egy n-szem´elyes j´at´ek magja azon x imput´aci´okb´ol ´all, amelyekkel szemben egyetlen y imput´aci´ot sem prefer´al hat´ekonyan valamely nem u ¨res S koal´ıci´ o. Jelben a mag C(v) := {x ∈ A(v) : nem l´etezik olyan y ∈ A(v) ´es ∅ = 6 S ⊆ I, hogy y S x}. P´ elda 6. Vegy¨ uk a (7; 8, 1, 1) s´ ulyozott t¨obbs´egi j´at´ekot. Itt v(S) = 1, ha 1 ∈ S ´es v(S) = 0, ha 1 6∈ S. Ez´ert A(v) = {x : x1 ≥ 1, x2 ≥ 0, x3 ≥ 0 ´es P3 aci´o van csak, i=1 xi = 1} = {(1, 0, 0)}, azaz |A(v)| = 1. Mivel egy imput´ A(v) = C(v), ´es ´ıgy C(v) = {(1, 0, 0)}. Mint v´arhat´o volt, az 1 viszi az ” eg´eszet.”
45
n-szem´ elyes j´ at´ ekok, a mag kisz´ am´ıt´ asa Egy v karakterisztikus f¨ uggv´eny˝ u j´at´ek C(v) magj´aban l´ev˝o vektorok joggal tekinthet˝ ok ´esszer˝ u megold´asoknak. Ezzel azonban nem ´ert¨ unk a probl´em´ ak v´eg´ere. P´ elda 1. Sz´ amoljuk ki a (2; 1, 1, 1) s´ ulyozott t¨obbs´eg˝ u j´at´ek magj´at. Tegy¨ uk fel, hogy y ∈ A(v). Ekkor valamely 1 ≤ i < j ≤ 3 eset´en yi + yj < 1, hisz y1 +y2 +y3 = 1. Megmutatjuk, hogy van olyan z ∈ A(v) ´es ∅ = 6 S ⊆ {1, 2, 3}, amelyre z S y. Az indexek cser´ej´evel feltehetj¨ uk, hogy y1 + y2 < 1, s mintegy a marad´ekot” (y3 -at) sz´etosztjuk az els˝o ´es m´asodik j´at´ekos k¨oz¨ott: ” z1 := y1 + y3 /2, z2 := y2 + y3 /2. ´Igy persze z {1,2} y. M´assz´oval b´ armely y ∈ A(v)-re l´etezik olyan z ∈ A(v) ´es nem u ¨res S ⊆ {1, 2, 3} halmaz, hogy z S y. Ez persze azt jelenti, hogy a mag az u ¨res halmaz, vagyis nem tudunk j´ o megold´ ast javasolni. Sz¨ uks´eg¨ unk van teh´ at egyr´eszt a mag szerkezet´enek jobb meg´ert´es´ere a k´enyelmesebb kisz´ am´ıt´ as ´erdek´eben, m´asr´eszt tenn¨ unk kell valamit, ha a mag u ¨res. Az els˝ o probl´em´ara vonatkozik a mag le´ır´asa, mint konvex poli´eder. 7. T´ etel. Egy v karakterisztikus f¨ uggv´eny˝ u n-szem´elyes j´ at´ekban az x imput´ aci´ o eleme a magnak akkor ´es csak akkor, ha minden S koal´ıci´ ora a P x ≥ v(S) egyenl˝ o tlens´ e g teljes¨ u l. i∈S i Bizony´ıt´ as. Vegy¨ unk egy olyan x vektort, amelyre teljes¨ ul az ¨osszes, a felt´etelben lev˝ o egyenl˝ otlens´eg. Tegy¨ uk fel, hogy van olyan y ∈ A(v) ´es nem P u ¨res S ⊂ I, hogy y S x. Ekkor yi > xi minden i ∈ S ´es i∈S yi ≤ v(S) a hat´ekony preferencia miatt, amib˝ol a X i∈S
yi ≤ v(S) ≤
X i∈S
xi <
X
yi
i∈S
ellentmond´ as ad´ odik. A m´ asik ir´ any bizony´ıt´as´ahoz tekints¨ unk egy, a felt´etel valamelyik egyenl˝ otlens´eg´et megs´ert˝ o x ∈ A(v) vektort, ´es legyen ∅ = 6 S ⊂ I, amelyre P s´er¨ ul; azaz i∈S xi < v(S). Tal´alni akarunk egy olyan y ∈ A(v) vektort ´es P ∅= 6 T ⊂ I halmazt, amelyre y T x. Az el˝obbiek miatt v(S) = i∈S xi + , ahol > 0. Az y-t u ´gy ´ all´ıtjuk el˝o, hogy az -t felosztjuk” az S koal´ıci´o ” tagjai k¨ oz¨ ott, azaz yi := xi + /|S|, ha i ∈ S. K´erd´es, mi legyen yi , ha i 6∈ S ? Az y vektornak benne kell lennie A(v)-ben, ´ıgy az egy´eni racionalit´as felt´eteleit nem s´ertheti, azaz yi ≥ v({i}) minden i ∈ I. Ezek automatikusan teljes¨ ulnek, ha i ∈ S, hiszen x ∈ A(v) ´es yi > xi ≥ v({i}) ha i ∈ S. 46
Teljes¨ ulnie kell tov´ abb´ a a Pareto optimalit´asnak, vagyis Keress¨ uk h´ at az yi -ket i 6∈ S-re a k¨ovetkez˝o alakban:
Pn
i=1 yi
= v(I).
yi = v({i}) + δi , ahol δi ≥ 0. Ezzel n X
yi =
i=1
amib˝ ol a
P
i∈S
X
xi + +
v({i}) +
i6∈S
i∈S
xi + = v(S) ´es
X
Pn
i=1 yi
v(I) = v(S) +
X
X
δi ,
i6∈S
= v(I) miatt k¨ovetkezik a v({i}) +
i6∈S
X
δi .
i6∈S
´ Atrendezve a δi -kre az al´ abbi felt´etel ad´odik: X
δi = v(I) − v(S) −
i6∈S
X
v({i}).
i6∈S
Nevezz¨ uk a fenti egyenlet jobboldal´at δ-nak, ´es defin´aljuk majd a δi -ket a δi := δ/(n − |S|) formul´ aval. Ekkor az y imput´aci´o lesz, amennyiben δ ≥ 0. P ul δ nem neg(Val´ oban, hisz ni=1 yi = v(I) ´es yi ≥ v({i}) i ∈ I-re.) V´eg¨ ativit´ as´ anak megmutat´ as´ ara haszn´aljuk a v f¨ uggv´eny szuperadditivit´as´at; P ´Igy v({i}) ≤ v(I \ S). i6∈S δ = v(I) − v(S) −
X
v({i}) ≥ v(I) − v(S) − v(I \ S) ≥ v(I) − v(I) = 0,
i6∈S
ahol az utols´ o egyenl˝ otlens´egben (v(I) ≥ v(S) + v(I \ S)) ism´et a szuperadditivit´ ast haszn´ altuk, ´es ezzel k´esz vagyunk. 2 P´ elda 2. A t´etel seg´ıts´eg´evel kisz´am´ıthatjuk a kor´abban ismertetett ingatlan fejleszt´es j´ at´ek magj´ at. v v({1}) = 100000 v({2}) = v({3}) = 0 v({1, 2}) = 20000 v({1, 3}) = 30000 v({2, 3}) = 0 v({1, 2, 3}) = 300000
A(v) x1 ≥ 100000 x2 ≥ 0 x3 ≥ 0 P (ii) 3i=1 xi = 300000
47
C(v) A(v) elemei, melyekre (iii) x1 + x2 ≥ 200000 (i) x1 + x3 ≥ 300000 x2 + x3 ≥ 0
(i) ´es (ii) ⇒ x2 = 0, (iii) ⇒ x1 ≥ 200000, azaz a mag a k¨ovetkez˝o: C(v) = {x : 200000 ≤ x1 ≤ 300000, x2 = 0, x3 = 30000 − x1 }. A v´ arakoz´ asnak megfelel˝ oen a 2. j´at´ekos kiz´ar´odik az u ¨zletb˝ol, ´es a f¨oldet a 3. veszi meg egy 200 ´es 300 ezer doll´ar k¨ozti ¨osszeg´ert. Enn´el t¨obbet nem tudunk mondani, de ez term´eszetes, hiszen a val´os´agban sem d¨onthet˝o el el˝ ore, mi lesz az ´ ar. (Az f¨ ugghet az alkufolyamatt´ol.) Stabil megold´ asok Amennyiben a j´ at´ek magja u ¨res, nem tudunk ´esszer˝ u megold´ast javasolni, ´es ez is hasznos inform´aci´o. Elk´epzelhet˝o m´as, stabilit´ast figyelembe vev˝ o szempont alapj´ an t¨ ort´en˝o v´alaszt´as A(v)-b˝ol. Ez volt Neumann ´es Morgenstern eredeti gondolata. Egy kor´ abbi defin´ıci´ onk egy G ir´any´ıtott gr´afban egy f¨ uggetlen ´es domin´al´o S ⊆ V ponthalmaz mag vagy stabil halmaz. (Sajnos a magyar terminol´ ogia k¨ onnyen zavart okozhat, mivel ez a mag az angolban kernel, m´ıg az el˝ oz˝ o t´etellel karakteriz´alt mag az core.) Egy n-szem´elyes j´at´ek imput´ aci´ oinak A(v) halmaza felfoghat´o egy Gv gr´afk´ent; V (Gv ) = A(v), ´es (x, y) ∈ E(Gv ) ⇔ x S y valamely S ⊆ I-re. Defin´ıci´ o. Egy B ⊆ A(v) halmaz stabil megold´ as a v karakterisztikus f¨ uggv´ennyel meghat´ arozott j´at´ekban, ha B mag (kernel, stabil halmaz) a Gv gr´ afban. Megjegyz´ es: A m´ asik” mag (core) is le´ırhat´o a Gv gr´af seg´ıts´eg´evel: C(v) ” azon pontok halmaza A(v)-ben, amelyekbe nem fut be ´el, ha mint Gv -beli pontk´ent tekintj¨ uk ˝ oket. Az els˝ o pillant´ asra nem nyilv´anval´o, mi ´ertelme van a stabil halmazokat megold´ asnak tekinteni. Az egyik motiv´aci´o lehet a stabil p´aros´ıt´asi probl´ema, amelynek a megold´asai ´eppen egy gr´af stabil halmazai. Tov´abb´a stabil halmaz l´etezhet akkor is, ha a mag (core) u ¨res. P´ elda 3. A (2; 1, 1, 1) s´ ulyozott t¨obbs´egi j´at´ekra l´attuk, hogy C(v) = ∅. Legyen B = {(1/2, 1/2, 0), (1/2, 0, 1/2), (0, 1/2, 1/2)}, ekkor B stabil halmaz. B f¨ uggetlen halmaz: Ha pl. (1/2, 1/2, 0) S (1/2, 0, 1/2) ⇒ S = {2}, de 1/2 ≤ v({2}) = 0 nem teljes¨ ul; ellentmond´as. A t¨obbi eset bizony´ıt´asa teljesen hasonl´ o m´ odon t¨ ort´enhet. B domin´ al´ o halmaz: Legyen x ∈ A(v), x = (x1 , x2 , x3 ). Ha x1 > 1/2, akkor x2 , x3 < 1/2, de ekkor (0, 1/2, 1/2) {2,3} (x1 , x2 , x3 ). A szimmetria miatt feltehet˝ o, hogy x1 ≥ max{x2 , x3 }, ´ıgy az el˝oz˝o megjegyz´es miatt x2 , x3 ≤ 1/2. Ha x2 vagy ´eppen x3 1/2, akkor x ∈ B. Ha viszont 48
mindkett˝ o kisebb, mint 1/2, akkor (0, 1/2, 1/2) {2,3} (x1 , x2 , x3 ). Hasonl´ o megfontol´ assal ad´ odik, hogy kontinuum sok stabil halmaz van: minden c ∈ (0, 1/2) eset´en a Bc := {(x1 , 1 − c − x1 , c) : 0 ≤ x1 ≤ 1 − c} halmaz stabil. P´ elda 4. A 2. p´eld´ aban kisz´amoltuk az ingatlanfejleszt´es j´at´ek magj´at. B´ armely n-szem´elyes j´ at´ekra, ha B egy stabil halmaz, akkor C(v) ⊆ B. Eset¨ unkben egy B stabil halmaz felt´etlen¨ ul b˝ovebb C(v)-n´el (B\C(v) 6= ∅), hiszen az x = (100000, 100000, 100000) ∈ A(v) imput´aci´ora nem l´etezik olyan y ∈ C(v) ´es S ⊆ {1, 2, 3}, amelyre y S x. Megmutatjuk, hogy B := {(x1 , x2 , x3 ) : 100000 ≤ x1 ≤ 300000, x2 = 0, x3 = 300000 − x1 } egy stabil halmaz. B f¨ uggetlen: Legyen x, y ∈ B ´es x S y. Mivel x2 = y2 = 0, az x1 > y1 , akkor ´es csak akkor, ha x3 < y3 , illetve x3 > y3 ⇒ x1 < y1 . Teh´ at S = {1} vagy S = {3}, ami lehetetlen. B domin´ al´ o: Tegy¨ uk fel, hogy egy y ∈ B-re y2 > 0. Legyen ekkor x = (x1 , x2 , x3 ) := (y1 + y2 /2, 0, y3 + y2 /2). Nyilv´anval´oan x ∈ B ´es x {1,3} y. Egy stabil halmaz teh´ at a mag ´altal sugallt´ol elt´er˝o megold´asokat is ´ megenged. Erdekes tulajdons´aga, hogy osztozkod´ast” ´ırhat el˝o egy j´at´ekban, ” amelynek u ¨res a magja (l´ asd 3. p´elda). Sajnos nem puszt´an a nehezen kisz´ am´ıthat´ os´ agban hasonl´ıt a magra; 1969-ben Lucas bebizony´ıtotta, van olyan j´ at´ek, melynek nincs stabil halmaza. Egy karakter´eben k¨ ul¨onb¨oz˝o megk¨ ozel´ıt´est jelent a Shapley ´ert´ek, amely a j´at´ekosok erej´et”, alkupoz´ıci” ´oj´ at hivatott modellezni.
7.
Stabil P´ aros´ıt´ asok
A stabil p´ aros´ıt´ as vagy stabil h´azass´ag probl´ema kiv´al´o p´elda mind a gyakorlat ´es elm´elet viszony´ anak szeml´eltet´es´ere, mind a moh´o algoritmus egy u ´jabb illussztr´ aci´ oj´ ara. A probl´emak¨ort eredetileg az USA-ban a 40-es ´evek k¨ ozep´en kulmin´ al´ o orvos gyakornok hi´any, illetve eloszt´asi zavar motiv´alta. A v´egz˝ os orvosok ezreit kellett a k´orh´azak ´altal meghirdetett helyekre beosztani; r´ aad´ asul mindk´et f´el (orvos vs. k´orh´az) a saj´at preferenci´ait igyekezett ´erv´enyes´ıteni. Az eredetileg alkalmazott technik´ak teljesen alkalmatlann´a v´ altak 1947-re, mikoris egy radik´alisan u ´j rendszert vezzettek be helyett¨ uk. ´ Erdekes m´ odon ennek elm´eleti vizsg´alat´at csak 1962-ben tette meg D. Gale ´es L. S. Shapley, s igaz´ ab´ ol ˝ok nem tudtak a probl´em´ar´ol: az egyetemi felv´eteli rendszert illetve a h´azass´agok stabilit´as´at akart´ak modellezni.12 12
N´eh´ any ´eve a magyar fels˝ ooktat´ asi felv´eteli rendszere is hasonl´ o algoritmust haszn´ al.
49
Mi az ´ altaluk vizsg´ alt legegyszer˝ ubb modellt ismertetj¨ uk, utalva r´a, hogy igen sok ´ altal´ anos´ıt´ as sz¨ uletett az´ota. A stabil h´azass´ag probl´em´aban adott n f´erfi, n n˝ o ´es mindegyik¨ uk valahogyan rangsorolja az ellent´etes nem tagjait; ez az illet˝ o szem´ely preferencia list´ aja. A f´erfiakat g¨or¨og, a n˝oket latin bet˝ ukkel jel¨ olj¨ uk majd. ´Igy p´eld´aul akkor mondjuk, hogy az α (f´erfi) jobban kedveli vagy prefer´ alja A-t B-hez k´epest, ha α preferencia list´aj´an A el˝or´ebb van, mint B. A szem´elyeket ´es preferenci´aikat le´ırhatjuk (dupl´an) s´ ulyozott p´ aros gr´ afokkal, vagy m´ atrixokkal is az al´abbiaknak megfelel˝oen: P´ elda: α β γ
α
A 1, 3 3, 1 2, 2
B 2, 2 1, 3 3, 1
C 3, 1 2, 2 1, 3
β
γ
3 r r 1 A H 1 @H2H 2 3@ H H @ H HH 2 3@ H 3 Hr 1 r @ B HH @ 1 2 H @ HH @ H HH 1 @3 H 2 H 3 r @r C 1 2
A m´ atrix egy elem´enek els˝o koordin´at´aja a megfelel˝o oszlop ´altal reprezent´ alt n˝ o helyez´ese a sorhoz tartoz´o f´erfi ranglist´aj´an, m´ıg a m´asodik koordin´ ata a ford´ıtott helyez´es. A feladat egy olyan n-elem˝ u M p´aros´ıt´as megad´asa, amely, legal´abbis valamely ´ertelemben, elk´epzelhet˝o. Gyakorlati ´es elm´eleti megfontol´asok alapj´ an az al´ abbi defin´ıci´ o t˝ unik ´esszer˝ unek: Defin´ıci´ o. Egy M p´ aros´ıt´as instabil ha vannak olyan α, β f´erfiak ´es A, B n˝ ok, hogy (α, A) ∈ M , (β, B) ∈ M , de β prefer´alja A-t B-hez k´epest, ´es A prefer´ alja β-t α-hoz k´epest. Egy M p´aros´ıt´as stabil, ha nem instabil. A defin´ıci´ o motiv´ aci´ oja k´ezenfekv˝o: feltehet˝o, hogy az instabil esetben β illetve A felbontja pillanatnyi kapcsolat´at, ´es egym´assal l´ep kapcsolatra. A c´elunk egy stabil M p´aros´ıt´as keres´ese lesz majd, m´ar ha van ilyen egy´ altal´ an. (A kor´ abban eml´ıtett Halmos-Vaughan modell glob´alis optimumra t¨ orekedett, nem v´eve figyelembe a lok´alis ´erdekeket, lehet˝os´egeket. Ez´ert legfeljebb kik´enyszer´ıthet˝o, m´ıg a fenti stabilit´as szerint egy M teljes p´ aros´ıt´ as nem bomlik fel, ha mag´ara hagyjuk a rendszert.) K´erd´es persze, van-e egy´altal´an megold´as? A fenti p´eld´aban h´arom megold´ as van: M1 = {(α, A), (β, B), (γ, C)}, M2 = {(α, C), (β, A), (γ, B)} 50
´es M3 = {(α, B), (β, C), (γ, A)}.
αr
βr
γr
M1
rA
rB
rC
M2
αr A A
βr
rA
M3
αr @
rA
@ @
A A A
rB
A A A A A A
γr
@ @ @r B
βr @
@ @ @ γ r
Ar C
@ @r C
P´ elda: A stabil h´ azass´ ag mint´aja alapj´an defini´alhatjuk az u ´n. szobat´ ars probl´em´ at. Itt adott 2n ember, akiket k´etszem´elyes szob´akba kell telep´ıteni ´es az el˝ oz˝ oekhez hasonl´ oan preferenci´akkal rendelkeznek. Nyilv´anval´o, ha adott n´egy szem´ely (α, β, γ, δ) u ´gy, hogy α, β ´es γ preferencia list´aj´an δ az 1o, akkor nincs stabil 2 utols´ o, α-´en β, β-´en γ ´es γ-´en α az aros´ıt´as. β r els˝ r γ p´ 2
1
@ 3 @
3
@ @ @ @ @ 1
α
@
2
r
3
@ @r
δ
A p´elda f´eny´eben kellemes meglepet´es az al´abbi t´etel. 8. T´ etel. (Gale-Shapley) A stabil h´ azass´ ag probl´em´ anak mindig van megold´ asa. Bizony´ıt´ as. Val´ oj´ aban egy nagyon hat´ekony, moh´o t´ıpus´ u algoritmust adunk, melynek v´egeredm´enye bizonyosan stabil p´aros´ıt´as. Trad´ıcion´alisan, hisz ez igencsak trad´ıcion´ alis elj´ar´as, a megfelel˝o k¨oznapi kifejez´eseket haszn´ aljuk a le´ır´ as sor´ an. A elj´ ar´ as els˝ o l´ep´es´eben minden f´erfi aj´anlatot tesz a kedvenc´enek. Minden n˝ o a legjobb aj´ anlatot fogadja el, de ez csak annyit jelent, hogy v´arakoz´o ” list´ ara” helyezi a k´er˝ ot. A m´asodik l´ep´esben az elutas´ıtott k´er˝ok u ´jra aj´anlatot tesznek, ez´ uttal a preferencia list´ajukon 2. helyezett h¨olgynek. A n˝ok 51
ism´et a pillanatnyilag legjobb aj´anlatot fogadj´ak el; esetlegesen lecser´elve a v´ arakoz´ o list´ an l´ev˝ o k´er˝ ot. Hasonl´oan folytat´odik ez a k´es˝obbiekben is: egy elutas´ıtott (vagy egy v´ arakoz´o list´ar´ol leker¨ ult) f´erfi a soron k¨ovetkez˝o jel¨ olttel pr´ ob´ alkozik, m´ıg a n˝ok a lehet˝o legjobb jel¨oltet tartj´ak meg. Legk´es˝ obb n2 − 2n + 2 l´ep´es eltelt´evel minden h¨olgy kap legal´abb egy k´er˝ ot, ´ıgy a v´ arakoz´ o list´ aj´ an is lesz majd valaki. (Ugyanis ha egy l´ep´esben van olyan n˝ o, aki nem kapott m´eg aj´anlatot, akkor lennie kell elutas´ıt´asnak is ebben a l´ep´esben, illetve egy f´erfi csak egyszer tesz aj´anlatot egy n˝onek.) Mikor minden n˝ o kapott aj´anlatot, akkor v´eget vet¨ unk az elj´ar´asnak, ´es a pillanatnyi p´ arokat v´eglegesnek ki´altjuk ki. Megmutatjuk, hogy az ´ıgy kapott M p´ aros´ıt´ as stabil. Tegy¨ uk fel, hogy van olyan α ´es A, melyre (α, A) 6∈ M , de α prefer´ alja a p´arj´ahoz k´epest. Ekkor viszont α valamikor aj´ anlatot tett A-nak ´es A elutas´ıtotta ˝ot, azaz a v´arakoz´o list´aj´an α-n´al jobb” szem´ely volt, s ha cser´el˝od¨ott is az´ota, csak m´eg jobb lehet k´es˝obb. ´”Igy A a p´ arj´ at jobban kedveli, mint α-t, azaz nincs instabilit´as. 2 P´ elda: α β γ δ
A 1, 3 1, 4 2, 2 4, 1
B 2, 3 4, 1 1, 4 2, 2
C 3, 2 3, 3 3, 4 3, 0
D 4, 3 2, 2 4, 1 1, 4
Az algoritmus v´egrehajt´as´at egy t´abl´azaton k¨ovethetj¨ uk. Egy cella baloldali eleme az adott l´ep´esben a sor ´altal k´odolt szem´elyt˝ol aj´anlatot kap´o, a jobboldali elem pedig a sor aj´anlat´at elfogadott szem´ely.
α β γ δ
1. l´ep´es A, A A, ∅ B, B D, D
2. l´ep´es ∅, A D, D ∅, B ∅, ∅
3. l´ep´es ∅, A ∅, D ∅, ∅ B, B
4. l´ep´es ∅, ∅ ∅, D A, A ∅, B
5. l´ep´es B, ∅ ∅, D ∅, A ∅, B
6. l´ep´es C, C ∅, D ∅, A ∅, B
A k¨ ovethet˝ os´eg kedv´e´ert felvett¨ uk a f´erfiak preferencia list´ait, ahol fel¨ ulvon´ assal jelezt¨ uk, ha m´ ar t¨ ort´ent aj´anlat: ¯ B, ¯ C, ¯ D) α(A, ¯ ¯ β(A, D, C, B) ¯ A, ¯ C, D) γ(B, ¯ ¯ δ(D, B, C, A) A megold´ ast az utols´ o oszlop jobboldal´ar´ol olvashatjuk le: 52
M = {(α, C), (β, D), (γ, A), (δ, B)}. Felmer¨ ul a k´erd´es, tudunk-e valami k¨ozelebbit mondani a stabil p´aros´ıt´ asok szerkezet´er˝ ol, ¨ osszehasonl´ıthat´ok-e stb. Vegy¨ unk k´et stabil p´aros´ıt´ast, M1 -et ´es M2 -˝ ot. Az M1 f´erfi szempontb´ ol jobb, mint M2 , ha minden f´erfi legal´ abb olyan j´ o p´ art kap M1 -ben, mint M2 -ben; jel¨ol´esben M1 ≥F M2 . Nem lehet b´ armely k´et stabil p´aros´ıt´ast ¨osszehasonl´ıtani, de az ¨osszes stabil p´ aros´ıt´ as, mint azt J. H. Conway megmutatta, u ´n. disztribut´ıv vagy m´as sz´ oval geometriai h´ al´ ot alkot.13 Speci´ alisan van legnagyobb ´es legkisebb eleme. (Ha a n˝ok szempontj´ab´ol n´ezz¨ uk, ugyanazt a h´ al´ ot kapjuk, csak megford´ıtva. Azaz ami az egyik nemnek a legjobb, a m´ asiknak a legrosszabb.) Ez ut´obbit egyszer˝ uen bel´athatjuk. P´ elda: Az els˝ o p´eld´ aban szerepl˝o stabil p´aros´ıt´asok az al´abbi h´al´ot alkotj´ak: M1 r
Az M1 -ben j´ arnak legjobban a f´erfiak.
M3 r
Az M3 a f´erfiaknak jobb, mint M2 ´es a n˝oknek jobb, mint M1 .
M2 r
Az M2 -ben j´ arnak legjobban a n˝ok.
Egy A h¨ olgy lehets´eges az α f´erfi sz´am´ara, ha van olyan M stabil p´aros´ıt´as, amelyre (α, A) ∈ M . 9. T´ etel. Az el˝ oz˝ o algoritmus minden f´erfinek a legjobb lehets´eges p´ art adja, m´ıg minden n˝ onek a legrosszabbat. Bizony´ıt´ as. Az els˝ o´ all´ıt´ ast a l´ep´esek szerinti indukci´oval l´atjuk be. Tegy¨ uk fel, hogy a soron k¨ ovetkez˝ o l´ep´esig egyetlen f´erfit sem utas´ıtott el olyan n˝o, aki lehets´eges lett volna sz´ am´ara. Tegy¨ uk fel tov´abb´a, hogy ebben a l´ep´esben A elutas´ıtja α-t. Azt ´ all´ıtjuk, hogy ekkor A nem lehets´eges α sz´am´ara. Val´ oban, ha A pillanatnyi p´arja β, akkor β prefer´alja A-t az ¨osszes n˝oh¨oz k´epest, kiv´eve akik kor´ abban visszautas´ıtott´ak. Ezek azonban, az indukci´os 13
Egy L h´ al´ o, ha van k´et k´etv´ altoz´ os m˝ uvelete, ∨ ´es ∧, ´es ezek idempotensek x ∨ x = x, x∧x = x, kommutat´ıtvak, x∨y = y ∨x, x∧y = y ∧x, asszociat´ıvak, x∨(y ∨z) = (x∨y)∨z, x ∧ (y ∧ z) = (x ∧ y) ∧ z ´es elnyel˝ ok, azaz x ∨ (x ∧ y) = x ´es x ∧ (x ∨ y) = x minden x, y, z ∈ L eset´en. Disztribut´ıv a h´ al´ o, ha teljes¨ ul m´eg az x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) egyenl˝ os´eg is.
53
felt´etel miatt, nem lehets´egesek β sz´am´ara. Ha teh´at l´etezne egy olyan M stabil p´ aros´ıt´ as, amelyre (α, A) ∈ M , ebben β a p´arj´at (nevezz¨ uk B-nek) kev´esb´e kedveln´e, mint A-t, hiszen mind A ´es B lehets´eges β sz´am´ara. Ekkor viszont az (α, A), (β, B) instabilit´ast okoz, azaz A nem lehets´eges α sz´am´ara, s ezzel bel´ attuk a t´etel els˝ o fel´et. Legyen M ∗ az algoritmusunk ´altal adott f´erfi optim´ alis megold´asa, M pedig egy tetsz˝ oleges stabil p´aros´ıt´as. Bel´atjuk, hogy b´armely A n˝o eset´en az ˝ o M -beli p´ arja nem rosszabb, mint az M ∗ -beli p´arja. (Igaz´ab´ol pontosan akkor nem rosszabb, ha ugyanaz a p´arja a k´et p´aros´ıt´asban, ´es hat´arozottan jobb, ha nem.) Ha (α, A) ∈ M ∗ , (β, A) ∈ M ´es α 6= β, akkor (α, B) ∈ M valamely B 6= A h¨ olgyre. A t´etel els˝o fele miatt persze α prefer´alja A-t Bhez k´epest. M´ asr´eszt az M p´aros´ıt´as stabil, ´ıgy speci´alisan az (α, B), (β, A) p´ arok stabilit´ asa az jelenti, hogy A prefer´alja β-t α-hoz k´epest; s pont ezt akartuk bizony´ıtani. 2 Megjegyz´ esek: Az algoritmus eredeti felhaszn´al´as´an´al a k´orh´azak tett´ek az aj´ anlatokat, ´es azt hangoztatt´ak (term´eszetesen bizony´ıt´as n´elk¨ ul), hogy ez az orvosok jav´ ara v´ alik. Sz´amos tanuls´ag vonhat´o itt le, s ezekb˝ol csak az egyik, hogy nem ´ art meggondolni nyilv´anval´onak t˝ un˝o (vagy annak be´all´ıtott) ´all´ıt´ asokat, mint azt Gale ´es Shapley tett´ek volt. A m´ asik, hasonl´ oan fontos ´eszrev´etel a d¨ont´esi helyzetek illetve strat´egi´ak buktat´ oira vonatkozik. A modell azt sugallja, el´ebe kell menni” az esem´e” nyeknek ´es kishit˝ us´eg n´elk¨ ul megpr´ob´alni a legjobbnak t˝ un˝o megold´asokat a s¨ ult galambra v´ ar´ as” helyett. ” A stabil p´ aros´ıt´ as mint mag Kor´ abban defini´ altuk egy ir´any´ıtott G gr´af magj´at; ez egy olyan S ⊂ V (G) halmaz volt, amely f¨ uggetlen ´es domin´al´o egyben. Ez a fogalom k¨ ul¨ on¨ osen fontos a j´ at´ekelm´eletben, hisz a megold´asok stabilit´as´at fogalmazza meg matematikai form´aban. A stabil p´aros´ıt´as motiv´alhatja ezt a defin´ıci´ ot, ugyanis egy r¨ ogz´ıtett probl´ema stabil p´aros´ıt´asai tulajdonk´eppen magok egy megfelel˝ oen alkotott gr´afban. Defini´ aljuk egy G gr´ af vonalgr´ afj´ at, L(G)-t, a k¨ovetkez˝ok´eppen: L(G) pontjai G ´elei lesznek, azaz V (L(G)) := E(G), ´es L(G) k´et pontja, e ´es f , k¨ oz¨ ott van ´el, ha G-ben tekintve az e ´es f ´eleknek van k¨oz¨os pontja. Ha G pontjaihoz preferencia list´ ak vannak rendelve, ir´any´ıtsuk az (e, f ) ´elt L(G)ben u ´gy, hogy az a prefer´ alt pontb´ol indul ´es a kev´esb´e kedvelt pontra mutat k¨ oz¨ os ponthoz tartoz´ o lista szerint. ´ ıt´ All´ as: A fenti defin´ıci´ okkal a G gr´af stabil p´aros´ıt´asai ´eppen az L(G) gr´af magjainak felelnek meg. 54
P´ elda: Az els˝ o p´elda G gr´ afj´ahoz tartoz´o L(G): (α,r B)
(α, A) r
z
j
r(α, C)
9
(γ, C) r
U i
N
r (β, C)
? 6 r
K
W
(γ, B)
z ] r (γ, A)
i
r (β, A)
r (β, B)
*
A Shapley ´ ert´ ek A c´el egy olyan Φ f¨ uggv´eny defini´al´asa, amely minden v karakterisztikus f¨ uggv´ennyel le´ırt j´ at´ekhoz hozz´arendel egy Φ(v) ∈ Rn vektort. Az i-edik j´ at´ekos Shapley ´ert´eke Φi (v), ha Φ(v) = (Φ1 (v), . . . , Φn (v)) ´es az al´abbi axi´ om´ ak teljes¨ ulnek Φ-re: 1. Legyen π az I = {1, . . . , n} halmaz egy permut´aci´oja, ´es w(S) = v(π(S)) minden S ⊆ I-re. Ekkor Φi (w) = Φπ(i) (v). 2.
n P
Φi (v) = v(I).
i=1
3. Ha v(S\{i}) = v(S) minden S ⊆ I-re, akkor Φi (v) = 0. 4. Additivit´ as. Ha v ´es v 0 karakterisztikus f¨ uggv´enyek az I halmazon ´es w = v + v 0 , akkor Φ(w) = Φ(v) + Φ(v 0 ). Megjegyz´ es: Az els˝ o axi´ oma azt fejezi ki, hogy a j´at´ekosok ereje f¨ uggetlen az elnevez´es¨ ukt˝ ol. A m´ asodik a Pareto optimalit´as analogonja, a megszerezhet˝ o haszon teljes feloszt´asa. A harmadik szerint nulla az ´ert´eke” annak ” a j´ at´ekosnak, akinek l´enyeg´eben nincs befoly´asa a j´at´ek menet´ere. V´eg¨ ul a negyedik azt k¨ oveteli meg, ha k´et f¨ uggetlen j´at´ekot j´atszanak ugyanazon j´ at´ekosok, akkor a nyerem´eny¨ uk a k´et j´at´ek ¨osszege lesz. Az igaz´an meglep˝o, hogy van, r´ aad´ asul pontosan egy, Φ f¨ uggv´eny, amely eleget tesz ezeknek a szigor´ u felt´eteleknek. 55
10. T´ etel. (Shapley) A karakterisztikus f¨ uggv´enyek halmaz´ an l´etezik egy egy´ertelm˝ uen meghat´ arozott Φ f¨ uggv´eny, amely eleget tesz az 1-4 axi´ om´ aknak. Tov´ abb´ a X Φi (v) = γ(|S|)(v(S) − v(S\{i}), i∈S⊆I
ahol γ(k) =
(k − 1)!(n − k)! . n!
P´ elda 5. (51; 49, 48, 3)
Φi (v) =
X
γ(|S|)(v(S) − v(S\{i}) =
i∈S⊆I
1 1 1 (1 − 0) = · 2 = , 3! 6 3 i∈S,|S|=2 X
azaz Φ(v) = (1/3, 1/3, 1/3). P´ elda 6. Ingatlanfejleszt´es Φ1 (v) =
1 2! (v({1}) − v(∅)) + [(v({1, 2}) − v({1})) + (v({1, 3}) − v({1}))]+ 3! 3!
2 2 + (v({1, 2, 3}) − v({2, 3})) = 216666 3! 3 1 2 2 Φ2 (v) = [(v({1, 2}) − v({2})) + (v({1, 2, 3}) − v({1, 3})) = 16666 3! 3! 3 1 2 2 Φ3 (v) = [(v({1, 3}) − v({1})) + (v({1, 2, 3}) − v({1, 2})) = 66666 3! 3! 3 P´ elda 7. ENSZ, Biztons´ agi Tan´acs: (39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1) Egy nem ´ alland´ o i tagra azon S minim´alis koal´ıci´ok eset´en nem nulla a v(S) − v(S\{i}), amelyek mind az ¨ot ´alland´o tagot ´es pontosan h´ arom 9 ideiglenes tagot tartalmaznak az i-edik tagon k´ıv¨ ul. Ezek sz´ama 2 , m´ıg γ(9) = 8! 6!/15!, azaz !
Φi (v) =
9 8! 6! 4 = ≈ 0, 001865 2 15! 5 · 7 · 11 · 13
Az els˝ o ´es m´ asodik axi´ oma miatt ha j egy ´alland´o tagja a BT-nek, akkor Φj (v) =
8 1 − 7·11·13 1 − 10Φi (v) = ≈ 0, 1963. 5 5
Az ¨ ot ´ alland´ o tag birtokolja teh´at a d¨ont´eshozatal t¨obb, mint 98%-´at, m´ıg az ideiglenes tagok befoly´ asa a 2%-ot sem ´eri el. 56
J´ at´ ekok ´ es d¨ ont´ esek A Shapley t´ etel k¨ ovetkezm´ enyei Az egyszer˝ u j´ at´ekokra (azaz, melyekben a v(S) = 0 vagy 1 minden S koal´ıci´ ora) a Shapley ´ert´ek kisz´am´ıt´asa egyszer˝ us¨odik. Φi (v) =
X
γ(|S|)(v(S) − v(S\{i}),
i∈S⊆I
´es most, v(S) − v(S\{i}) = 1 pontosan akkor, ha v(S) = 1 ´es v(S\{i}) = 0 k¨ ul¨ onben. Legyen Si (i ∈ S ⊆ I) az i-t tartalmaz´o nyer˝o koal´ıci´ok halmaza, melyek az i-t elhagyva m´ ar nem nyer˝ ok. ´Igy Φi (v) =
X
γ(|S|).
i∈S∈Si
P´ elda 1. ENSZ Biztons´ agi Tan´acs Mint l´attuk a d¨ont´eshozatal itt egy (39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1) s´ ulyozott t¨obbs´egi j´at´ek. Ha i egy nem ´alland´o tag ´es S 3 i minim´ alis nyer˝o koal´ıci´o, akkor S pontosan 5 ´alland´o ´es 4 ideiglenes tagb´ ol ´ all. Ezen S halmazok sz´ama 93 , ´ıgy !
Φi (v) =
X i∈S∈Si
γ(|S|) =
X
γ(9) =
i∈S∈Si
9 4 γ(9) = ≈ 0, 001865. 3 3 · 5 · 11 · 13
A szimmetria miatt, ha j egy ´alland´o tag, akkor 1 − 10Φi (v) ≈ 0, 1963, 5 m´ıg az 5 ´ alland´ o tag egyes´ıtett ereje ≈ 0,98153. A p´elda mutatja, hogy egy s´ ulyozott t¨ obbs´egi j´ at´ekban a j´at´ekosok val´odi ereje ´es a szavazataik sz´ ama k¨ oz¨ ott messze nem line´aris a kapcsolat, illetve a gyeng´ebb j´at´ekosok ´erdek´erv´enyes´ıt˝ o k´epess´ege tragikusan kicsi. Elk´epzelhet˝o viszont, hogy 7 ideiglenes tag ¨ osszefog ´es mindig egy¨ utt szavaz. Ekkor egy¨ uttes erej¨ uk 1/6, csak u ´gy, mint az ´ alland´ o tagok´e ebben az esetben, m´ıg a kimarad´o 3 nem ´alland´ o tag ereje nulla! A r´egi tan´acs, divide et impera, matematikailag is al´ at´ amaszthat´ o.14 Φj (v) =
Egyszer˝ u j´ at´ekok eset´eben eleg´ans val´osz´ın˝ us´egi interpret´aci´oja adhat´o meg a Shapley ´ert´eknek. Egy π permut´aci´oj´ara I-nek egy i elem pivot´ alis, 14
Ez´ert is ideiglenesek a tagorsz´ agok, ´ıgy val´ osz´ın˝ utlen az o ¨sszefog´ asuk, illetve k¨ onnyebben befoly´ asolhat´ ok.
57
ha az i-t π-ben megel˝ oz˝ o elemek ´altal vesztes, de i-t hozz´av´eve gy˝oztes koal´ıci´ ot alkotnak. Ha egy S nyer˝o, S\ {i} veszt˝o koal´ıci´o, akkor S-re n´ezve (s − 1)!(n − s)! sz´ am´ u permut´aci´oban lesz i pivot´alis, ahol s = |S|. 11. T´ etel. Egy v karakterisztikus f¨ uggv´eny˝ u j´ at´ekban Φi (v) egyenl˝ o annak a val´ osz´ın˝ us´eg´evel, hogy i pivot´ alis, amennyiben az I b´ armely permut´ aci´ oj´ at azonos val´ osz´ın˝ us´eggel v´ alasztjuk. P´ elda 2. Az ausztr´ al parlamenti rendszer m˝ uk¨od´ese Az orsz´ ag hat sz¨ ovets´egi ´ allamb´ol ´all, ´es t¨orv´enyeket ezek k´epvisel˝oi, illetve a sz¨ ovets´egi korm´ anyzat hozza. Az elfogad´as felt´etele, hogy legal´abb ¨ot ´allam, vagy k´et ´ allam ´es a sz¨ ovets´egi korm´anyzat t´amogassa az adott t¨orv´enyt. Egy permut´ aci´ oban a sz¨ ovets´egi korm´anyzat pivot´alis, ha a harmadik, a negyedik vagy ¨ ot¨ odik helyen ´ all. Ezek egym´ast kiz´ar´o esem´enyek, val´osz´ın˝ us´eg¨ uk 1/7 + 1/7 + 1/7 = 3/7. Az egyes ´allamok Shapley ´ert´eke egyenl˝o, 4/7 · 1/6 = 2/21, ami a sz¨ ovets´egi korm´anyzat erej´enek k´et kilencede. Felmer¨ ul a k´erd´es, mi a Shapley ´ert´ek ´es az imput´aci´ok kapcsolata. 12. T´ etel. Minden n-szem´elyes j´ at´ekra a Φ(v) vektor eleme az imput´ aci´ ok A(v) halmaz´ anak. Bizony´ıt´ as. A 2. axi´ oma szerint ni=1 Φi (v) = v(I), ´ıgy a Pareto optimalit´ as teljes¨ ul. Az egy´eni racionalit´as Φi ≥ v({i}) egyenl˝otlens´egei a k¨ ovetkez˝ ok miatt ´ allnak. El˝osz¨or is a v(S) − v(S \ {i}) ≥ v({i}) a szuperadditivit´ as miatt. Ezzel P
X
Φi (v) ≥
γ(|S|)v({i}) = v({i})
i∈S⊂I
X
γ(|S|) = v({i}),
i∈S⊂I
hiszen X i∈S⊂I
γ(|S|) =
n X n−1 i=1
k−1
!
γ(|k|) =
n X (n − 1)!(k − 1)!(n − k)! i=1
(n − k)!(k − 1)!n!
=
n X 1 i=1
n
= 1.
2 ¨ Osszefoglalva az eddigieket, egy n-szem´elyes j´at´ek elk´epzelhet˝o megold´asai (kifizet´esei) az imput´ aci´ ok A(v) halmaza. Mivel A(v)-t n X
xi = v(I) egyenlet ´es az xi ≥ v({i}) (i ∈ I)
i=1
egyenl˝ otlens´egek hat´ arozz´ ak meg, A(v) egy konvex poli´eder. A C(v) meg az A(v)-nek r´esze, ´es szint´en poli´eder, hiszen 58
C(v) = {x ∈ Rn :
X
xi ≥ v(S), S ⊆ I},
i∈S
m´ıg egy stabil B halmazr´ ol tudjuk, hogy C(v) ⊆ B ⊆ A(v). V´eg¨ ul a Shapley ´ert´ek Φ(v) vektora szint´en A(v)-ben van. P´ elda 3. Az ingatlanfejleszt´es megold´asai” (a koordin´at´akat ezer doll´arban ” m´erve). 300
x2 6 @ @
@ @ @ A(v) @ Φ(v) = (217, 16, 67) @ @ @ 0 @ b 300 x1 C(v)
x3
300
Csoportok d¨ ont´ eshozatala Az ´eletben gyakran felmer¨ ul, hogy emberek egy csoportj´anak egy probl´ema megold´ as´ anak k¨ ul¨ onb¨ oz˝o alternativ´ait sorba kell rendeznie. P´ elda 1. Egy csal´ ad aut´ ot v´as´arol, ´es a keresked˝o a k¨ovetkez˝o extr´akat aj´ anlja: blokkol´ asg´ atl´ o (ABS), l´egzs´ak (L), l´egkondicion´al´o (AC) ´es sztereo r´ adi´ o (S). Mivel mindet nem engedhetik meg maguknak, mindenki egy fontoss´ agi list´ at ´ all´ıt fel. f´erj
feles´eg
1. gyerek
2. gyerek
ABS AC S L
AC L S ABS
S AC L ABS
AC L ABS-S
59
A k´erd´es ezek ut´ an: mi legyen a k¨oz¨os sorrend? (Az ABS-S jel¨ol´essel az ´erz´ekeltetj¨ uk, hogy megengedj¨ uk a d¨ontetlent k´et alternat´ıva ¨osszehasonl´ıt´ as´ an´ al.) ´ Altal´ anosan: Adott egy t elem˝ u I halmaz (az egy´enek csoportja) ´es egy A, az alternat´ıv´ ak halmaza. Jel¨olje P az A sorrendjeinek (d¨ontetlent megengedve) a halmaz´ at, ekkor P ×. . .×P = P t a lehets´eges inputok tere, elemei az u ´n. profilok, jel¨ uk (P1 , . . . , Pt ). Egy F : P t → P f¨ uggv´enyt konszenzus f¨ uggv´enynek (social welfare function) h´ıvunk. A c´elunk term´eszetesen a valamely szempontb´ ol ´esszer˝ u konszenzus f¨ uggv´enyek vizsg´alata. P´ elda 1. Az egyszer˝ u t¨ obbs´eg szab´alya Az a, b ∈ A alternat´ıv´ akra a csoport a-t b fel´e helyezi, ha az egy´enek t¨ obbs´ege ezt tette. Sajnos ez a szab´aly nem vezet konszenzus f¨ uggv´enyhez, mint azt az al´ abbi u ´n. szavaz´ oi vagy Condorcet paradoxon mutatja. Legyen I = {1, 2, 3}, A = {a, b, c}. P1 a b c
P2 b c a
P3 c a b
A szab´ aly szerint a megel˝ozi b-t, b megel˝ozi c-t ´es c megel˝ozi a-t, ami a rendez´es tranzitivit´ asa miatt nem lehets´eges. P´ elda 2. Borda ´ert´ek Egy (P1 , . . . , Pt ) ∈ P t -re ´es a ∈ A-ra defini´aljuk a bi (a) ´ert´eket (bi : A → N f¨ uggv´eny) az al´ abbi formul´aval: bi (a) := Pi -ben az a m¨og´e helyezett P alternat´ıv´ ak sz´ ama. A Borda ´ert´ek pedig b(a) := ti=1 bi (a), ´es a csoport xet y el´e helyezi, ha b(x) > b(y). ´Igy val´oban ad´odik egy konszenzus f¨ uggv´eny; tulajdonk´eppen pl. a pontoz´asra alapul´o sport´agakban hasonl´o t¨ort´enik. Egy s´ ulyos ellenvet´es a m´ odszer ellen az al´abbi profil ki´ert´ekel´ese: P1 P2 . . . Pt−1 Pt x x x y .. y y y . .. .. .. . . . x Nyilv´ anval´ oan b(y) − b(x) = |A| − 1 − (t − 1) = |A| − t, azaz ha az alternat´ıv´ ak sz´ ama nagyobb, mint a csoport m´erete, akkor az y alternat´ıv´at a csoport x el´e helyezi. ´Igy az ´ert´ekel´es, ha m´as nem, nagyon ´erz´ekeny a hib´ akra, elfogults´ agokra, esetlegesen manipul´aci´okra. P´ elda 3. Lexikografikus rendez´es 60
Helyezz¨ uk x ∈ A-t y ∈ A el´e, ha P1 -ben x megel˝ozi y-t. Ha P1 -ben x ´es y esetleg azonos helyen van, n´ezz¨ uk P2 -t ´es ´ıgy tov´abb. Ez nyilv´anval´oan konszenzus f¨ uggv´eny, s ´ıgy matematikai szempontb´ol semmi baj sincs vele. A sz´ o k¨ oznapi ´ertelm´eben persze sz´o sincs konszenzusr´ol, az egyes j´at´ekos dikt´ ator. Nem k¨ onny˝ u teh´ at minden ig´enynek eleget tev˝o konszenzus f¨ uggv´enyt tal´ alni. Hasonl´ o megk¨ ozel´ıt´est alkalmazunk, mint a Shapley ´ert´ek defin´ıci´oj´ an´ al; megpr´ ob´ alunk axi´ om´akat adni egy megfelel˝o konszenzus f¨ uggv´enyre. Az al´ abbi n´egy axi´ om´ at 1951-ben Arrow fogalmazta meg. Arrow axi´ om´ ak 1. (A konszenzus f¨ uggv´eny ´es az egy´eni ´ert´ekel´esek pozit´ıv asszoci´aci´oja) Ha egy adott profilra a konszenzus f¨ uggv´eny a-t b el´e helyezi, akkor ezt teszi a profil al´ abbi m´odos´ıt´asa ut´an is: (a) Az egy´enek ´ert´ekel´es´eben az alternat´ıv´ak sorrendje a-t kiv´eve nem v´ altozik. (b) Minden ´ert´ekel´esben az a alternat´ıva ´es b´armely m´as alternat´ıva sorrendje v´ altozatlan marad, vagy a jav´ara v´altozik. 2. (F¨ uggetlens´eg az irrevel´ans alternat´ıv´at´ol) Legyen A1 egy tetsz˝oleges r´eszhalmaza az alternat´ıv´aknak. Ha egy profilt u ´gy m´odos´ıtunk, hogy minden egy´en sorrendje az A1 elemei k¨oz¨ott v´altozatlan, akkor a konszenzus f¨ uggv´eny ugyanazt a sorrendet adja A1 elemei k¨oz¨ott az eredeti ´es a m´ odos´ıtott profil eset´eben. 3. (A polg´ arok szuverenit´asa) B´ armely a ´es b alternat´ıv´akra van olyan profil, melyre a konszenzus f¨ uggv´eny a-t b el´e helyezi. 4. (Nincs dikt´ ator) Nincs olyan egy´en, aki ha a-t b el´e helyezi, akkor a konszenzus f¨ uggv´eny is ezt teszi, f¨ uggetlen¨ ul a t¨obbi egy´en ´ert´ekel´es´et˝ol. Az Arrow axi´ om´ ak az igazs´agoss´agot ´es az ´esszer˝ us´eget pr´ob´alj´ak megragadni. Ez´ert azt´ an el´egg´e meglep˝o ´es n´emileg tal´an ki´abr´and´ıt´o a k¨ovetkez˝o t´etel. 13. T´ etel. (Arrow) Ha t > 1 ´es |A| > 2, akkor nem l´etezik az 1-4 axi´ om´ aknak eleget tev˝ o konszenzus f¨ uggv´eny. 61
Megjegyz´ es: Arrow t´etele r´avil´ag´ıt d¨ont´eshelyzetek bizonyos csapd´aira. Egyik, gyakran megval´ osul´ o megold´as a dikt´ator, egy m´asik v´alaszt´asi lehet˝ os´egek sz˝ uk´ıt´ese kett˝ ore, rossz esetben egyre. A harmadik pedig, hogy felk´esz¨ ul¨ unk a csapd´ akra, ´es megpr´ob´aljuk feloldani a probl´em´at minim´alis igazs´ agtalans´ ag ´ ar´ an.
Hivatkoz´ asok [1] Vaˇsek Chv´ atal, Linear programming. A Series of Books in the Mathematical Sciences. W. H. Freeman and Company, New York, 1983. [2] Forg´ o Ferenc ´es Sz´ep Jen˝o, Bevezet´es a j´at´ekelm´eletbe. [3] David Gale, Lloyd S. Shapley, College Admissions and the Stability of Marriage. Amer. Math. Monthly 69 (1962), no. 1, 9–15. [4] Seth Godin, Unleashing the IdeaVirus. www.ideavirus.com. [5] Robert Nau, Seminar in Choice Theory. www.gametheory.net [6] Fred Roberts, Discrete mathematical models with applications to social, biological, and environmental problems. Prentice-Hall, Englewood Cliffs, 1976.
62
