Kauno Technologijos Universitetas
Programinės įrangos katedra

Studentai: R.Jasinevičiūtė, E.Krušinskas

Konkurencinis modelis (Nash'o pusiausvyra)

Turinys:

1. Užduotis

Darbe turi būti atliktas konkurencinio modelio optimizavimo tyrimas. Šį modelį sudaro grupė serverių ir klientų eilė. Serveriai teikia paslaugas už tam tikrą kainą yi. Suteikdami paslaugą, serveriai sunaudoja xi resursų. Abu šie parametrai taip pat apsprendžia ir ateinančių klientų išlaidas. Keliama sąlyga, kad klientas pasirenka tą serverį, kuris aptarnaus jį kaip galima pigiau. Tuo tarpu serveris siekia maksimizuoti savo pelną.

Uždavinio modeliavimas atliekamas naudojantis paketu "Global Optimization".

2. Teorinė dalis

Kiekvienas serveris pasirenka savo strategiją ( xi, yi ). Tačiau jo gautas pelnas taip pat priklauso ir nuo kitų serverių pasirinktų strategijų. Pelnas aprašomas tokia funkcija:

ui = aiyi - xi , čia

ai - pas i-ąjį serverį atėjusių klientų skaičius;
yi - i-ojo serverio kaina už paslaugą;
xi - i-ojo serverio išlaidos, atsirandančios suteikiant paslaugą.

Kliento aptarnavimo išlaidos kiekvienam serveriui skaičiuojamos taip:

ci = yi + gi , čia

gi - laukimo i-ojo serverio eilėje trukmė.

Tarp serverių galimos ir koalicijos. Jos būna tada, kai keli serveriai susijungia ir bendrai aptarnauja klientų eilę. Šiuo atveju kliento elgesys nekinta, tačiau jeigu sudarytą koaliciją laikyti vienu serveriu, tai labai išauga jo pajėgumas, nes jis turi daugiau resursų aptarnauti tą pačią klientų eilę.

3. Darbo eiga

Buvo modeliuojami du atvejai:

3.1. Modeliavimo parametrai

Modeliavimui buvo parinkti tokie parametrai:

3.2. Nepriklausomas serverių darbas

Nepriklausomas serverių darbas buvo modeliuojamas metodais Bayes1 ir Mig1. 1-ame pav. pavaizduoti gauti rezultatai Bayes1 metodu, atlikus 200 iteracijų.


1 pav. Bayes1 - 200 iteracijų

Geriausia funkcijos f(x) reikšmė - 0.263816222
x1 y1 x2 y2 x3 y3
0.2856 1.70128 0.20434 1.54968 0.0769 1.76734

1 lentelė. Bayes1 - 200 iteracijų

Po 200 iteracijų gauta paklaida dar neatitiko reikalavimų. Ji buvo lygi maždaug 8.67%. Paklaidą gali sumažinti didesnis iteracijų skaičius. 2-ame pav. pavaizduoti rezultatai, gauti Bayes1 metodu po 400 iteracijų.


2 pav. Bayes1 - 400 iteracijų

Geriausia funkcijos f(x) reikšmė - 0.1103716704
x1 y1 x2 y2 x3 y3
0.08554 1.7839 0.00414 1.68044 0.29384 1.7963

2 lentelė. Bayes1 - 400 iteracijų

Šių skaičiavimų paklaida yra apytikriai lygi 3.67%.
Palyginimui serverių uždavinys buvo sumodeliuotas Mig1 metodu, atliekant 200 iteracijų. Gauti rezultatai pavaizduoti 3-ame pav.


3 pav. Mig1 - 200 iteracijų

Geriausia funkcijos f(x) reikšmė - 0.4497481504
x1 y1 x2 y2 x3 y3
0.10152 1.7199 0.3595 1.34026 0.0474 1.34718

3 lentelė. Mig1 - 200 iteracijų

Optimizavus metodu Mig1 su šiuo iteracijų skaičiumi gauta maždaug 7.5% paklaida. Padidinus iteracijų skaičių, paklaidos labai sumažinti nepavyko.

3.3. Kelių serverių koalicija

Toliau buvo modeliuojamas atvejis, kai serveriai yra sudarę koaliciją. Koaliciją šiuo atveju sudaro 1-as ir 2-as serveris. Bayes1 metodu su 400 iteracijų gauti rezultatai parodyti 4-ame pav.


4 pav. Bayes1 - 400 iteracijų

Geriausia funkcijos f(x) reikšmė - 0.0578243936
x1 y1 x2 y2 x3 y3
0.07132 0.47168 0.06992 0.58024 0.7085 1.87012

4 lentelė. Bayes1 - 400 iteracijų

Mig1 metodu su 400 iteracijų gauti rezultatai parodyti 5-ame pav.


5 pav. Mig1 - 400 iteracijų

Geriausia funkcijos f(x) reikšmė - 0.1710276144
x1 y1 x2 y2 x3 y3
0.0275 0.36076 0.0275 0.36076 0.18434 0.18894

5 lentelė. Mig1 - 400 iteracijų

3.4. Koalicijos stabilumas

Tyrimo metu paaiškėjo, kad pirmo ir antro serverio koalicijos stabilumas labai priklauso nuo H0 reikšmės, t.y. nuo maksimalaus laukimo laiko, kurį viršijus, klientas nelaukia eilėje ir "pabėga". Modeliavimas buvo atliktas, naudojant Mig1 metodą su 400 iteracijų. Serverių koalicija buvo stabili, jei H0 yra lygus 0.6. Šiuo atveju buvo gauti tokie rezultatai:

Pirmo serverio pelnas, dirbant be koalicijos: 23.78266
Antro serverio pelnas, dirbant be koalicijos: 21.97886
Koalicijos pelnas: 63.5
Pelno dalis, tenkanti vienam koalicijos nariui: 31.75
Kaip matome, vienam koalicjos nariui tenkanti pelno dalis yra didesnė už pelną, kurį gautų pirmas ar antras serveris, dirbdamas atskirai. Todėl galima teigti, kad ir pirmam, ir antram serveriui apsimoka jungtis į koaliciją ir ji yra stabili.

Jei slenkstį H0 truputį sumažintumėm (0.5) arba padidintumėm (0.7), tai koalicija taptų nestabili, nes pusiausvyros padėtyje serveriai, dirbdami atskirai, gautų didesnį pelną negu dirbdami koalicijoje. Kai H0 = 0.5, buvo gauti tokie rezultatai:

Pirmo serverio pelnas, dirbant be koalicijos: 75.42054
Antro serverio pelnas, dirbant be koalicijos: 75.42054
Koalicijos pelnas: 120
Pelno dalis, tenkanti vienam koalicijos nariui: 60
Koalicija nestabili.

Keičiant kitus parametrus, pavyzdžiui didinant bendrą klientų skaičių, didesnių pokyčių nebuvo pastebėta. Tai reiškia, kad jie koalicijos stabilumui turi nedidelę įtaką.

4. Išvados

Nei Bayes1, nei Mig1 metodui 200 iteracijų neužteko, kad minimali vidutinė kvadratinė paklaida tenkintų 5% reikalavimą. Pirmuoju atveju ji buvo lygi 8.67%, antruoju - 7.5%. Tačiau padidinus iteracijų skaičių iki 400, Bayes1 metodu buvo gauta 3.67% paklaida. Tai reiškia, kad tarp serverių surastas "kompromisas", kai neapsimoka sutartines strategijas keisti į apgavines.

Kai iteracijų skaičius palyginti mažas, vienareikšmiai atsakyti, kuris optimizavimo metodas duoda geresnius rezultatus, negalima. Abiem metodais rezultatai labai panašūs. Tačiau padidinus iteracijų skaičių (šiuo atveju iki 400), matyti, kad Bayes1 metodas skaičiuoja žymiai tiksliau.

Kiti metodai dėl skaičiavimų brangumo nebuvo panaudoti.

Koalicijos stabilumui didžiausią įtaką turi slenksčio H0 reikšmė. Pavyko nustatyti tokią jo reikšmę (0.6), prie kurios pirmo ir antro serverių koalicija buvo stabili.


1997