Б. Кооперативни игри
Припомнете си отново, че кооперативната игра е игра с ненулева сума, в която на играчите е позволено да обсъждат своите стратегии и да се споразумеят за съвместни действия преди играта. Основната цел в тази игра е да се поделят общите печалби между членовете на коалицията.
Помислете първо за кооперативна иградвама душина пример.
Пример 2. Нека е дадена матрицата на кооперативна игра
.
Отбелязваме и точкатаТ= (T1,T2) – точката на заплаха, къдетоT1,T2 са печалбите на играчите без влизане в коалицията. В нашия примерT =(1, 1).
Североизточната граница на региона се нарича оптимален набор на Парето. Частта от Парето-оптималното множество, която е над и вдясно от точката на заплаха, се наричапреговорно множество.В този случай Парето-оптималното множество съвпада с преговорното множество (AB). Най-общо казано, когато решаваме кооперативна игра, е достатъчно да се ограничим до намирането на преговорното множество. Тук обаче можем да посочим и равновесната точка на Наш. За това обозначаваме
Равновесната точка на Наш отговаря на условието:
.
Намерете най-голямата стойност на функцията върху AB. От уравнението на правата AB -L1 +L2 = 5, изразявамеL2 = 5 –L1 и заместваме в (*):
f(L1) = (L1 – 1)(5 – L1 – 1) = и намерете най-голямата стойност на функцията на една променлива в сегмента:
. Следователно = 2,5; = 2,5.
Това са стойностите, които максимизират функцията ƒ(L1,L2) в набора за преговори. На фигура 1 точката N = (2,5; 2,5) е равновесната точка на Наш.
Нека сега се докоснем дообщите въпроси на кооперациятаигри.
Да предположим, че има набор от играчиN= n>. НекаKе някакво подмножествоN, състоящо се отr £ nиграчи. След това ще има броя на възможните коалиции от играчи, които се споразумяват за съвместни действия.
Дефиниция 1.Функцията V , която поставя най-голямата печалба в съответствие с всяка коалиция K, се нарича характеристична функция на играта.
Дефиниция 2.Характерна функция V(K) се нарича проста, ако приема две стойности: 0 и 1.
Дефиниция 3.Ако характеристичната функция V е проста, тогава коалициите K, за които V(K) = 1, се наричат печеливши, а коалициите K, за които V(K) = 0, се наричат губещи.
Свойствана характеристичната функция.
1)личност (коалиция, която не съдържа нито един играч, не печели нищо).
Означете сXiпечалбата наi-тия играч. И разгледайте следните двеусловия:
1) индивидуална рационалност
2) колективна рационалност
Дефиниция 4.Векторът на печалба X = (X1, ¼, Xn), който отговаря на условия 1 и 2, се нарича дял при условията на характеристичната функция V.
Дефиниция 5.Множество, удовлетворяващо условия 1 и 2, се нарича класическа кооперативна игра.
Теорема 1.За да бъде X = (X1, ¼, Xn) деление в класическа кооперативна игра, е необходимо и достатъчно
Дефиниция 6.Кооперативните игри се наричат съществени, ако за всякакви коалиции K и L е в сила следното неравенство: V(K) +V(L) Yi, iÎ K е свойството за предпочитание.
Коефициентът на доминиране не е възможен за всяка коалиция. Например коалиционното господство е невъзможно,състоящ се от един играч или всички играчи.
Във всяка несъществена игра има само едно разделение, така че тук няма доминация.
Тъй като има много опции за разделяне, е необходимо да изберете раздели, които не са доминирани от други раздели. Такива разделения се наричат напълно стабилни, а наборът от такива разделения се наричаC-ядро.
Теорема 2.За да принадлежи дивизията X към C-ядрото на играта, е необходимо и достатъчно за всяка коалиция K да е изпълнено неравенството
Забележки:
1) в несъществена играC-ядро съществува и се състои от едно разделение на тази игра;
2) във всяка основна игра с постоянна сумаC-ядрото е празно.
Класиците на теорията на игрите J. von Neumann и O. Morgenstern предлагат следното решение за кооперативна игра.
Дефиниция 8.Решение на Нойман-Моргенщерн на кооперативна игра R е набор от деления, който отговаря на условията:
1) вътрешна стабилност (разделенията от решението не могат да се противопоставят едно на друго);
2) външна стабилност (възможно е да се противодейства на всяко отклонение от решението с някакво разделение, принадлежащо на решението).
Теорема 3.Ако една кооперативна игра има C-ядро C и решение R, тогава C /иV //, тогава
Когато играчите участват в две игри, техните печалби в отделните игри трябва да се добавят.
Дефиниция 10.Векторът на цената (вектор на Шапли) на игра с характеристична функция V е n-мерен вектор, който удовлетворява аксиомите на Шепли.
Терема 4. (Shapley)Има уникална функцияj, дефинирана за всички игри и удовлетворяваща аксиомите на Shapley.
Определение11.Характерна функция WS(T), дефинирана за всяка коалиция S, се нарича най-простата, ако
Некаji(V) са компонентите на вектора на Шепли,tе броят на елементите на множествотоT.
Векторът на Шепли се тълкува по следния начин: пределната стойност, коятоi-ият играч допринася заTкоалицията, се изразява чрезV(T) –V(T\i>), и се счита за печалба наi-тия играч. Ако означим с gi(T) вероятносттаi-ият играч да се присъедини към коалицията, тогава печалбата наi-ия играч ще бъде:
Сумирането се извършва за всички печеливши коалицииT, при условие че коалициятаT\i> не печели.
Пример. Да разгледаме корпорация от четирима акционери с дялове в следните количества:a1=10;a2=20;a3=30;a4=40. Да приемем, че всяко решение е одобрено от акционери, които имат мнозинство от акциите общо, и това решение се счита за печалба, равна на 1. Можем да разглеждаме тази ситуация като игра на четирима участници, в която следните коалиции ще бъдат победители:
.
Нека дефинираме компонентите на вектора на Шепли. При намирането отчитаме, че има само една коалицияT=, която печели, а коалициятаT\ = не печели. В тази коалиция има трима играчи, т.е.t= 3, така че
Сега нека дефинираме всички печеливши коалиции, но не и победа без втория играч. Има три такива коалиции: , , . Ето защо .
По същия начин получаваме това. Така векторът на Шепли изглежда така: .
Забележка. Ако приемем, че тежестта на гласа на акционера е пропорционална на броя акции, които той притежава, тогава получаваме вектора за гласуване (0,1; 0,2; 0,3; 0,4), който очевидно се различава от вектора на Шепли.
Проблеми за §14
14.1. Нека ученикът предложи да премине теста на учителя. За да получи кредит, студентът трябва да отговори правилно на поне два от трите въпроса. Формулирайте проблема като игра с ненулева сума, намерете решение.
14.3. На петима предприемачи беше предложено да инвестират в проект на стойност 1100 долара. Предприемачите имат съответно $200, $300, $500, $600 и $800. Проектът ще бъде даден на онези предприемачи, които разполагат с необходимата сума за финансирането му. Намерете вектора на Шепли.
14.4. Инвеститорите решават въпроса за насочване на средства към определени сектори на държава N. След дискусии мнозинството от инвеститорите решиха да изберат трите най-атрактивни инвестиционни опции от различни инвестиционни опции и да ги обсъдят поотделно. Едновременно с тази дискусия правителството на свое заседание разглежда няколко алтернативни стратегии за икономическо развитие за следващите години. Инвеститорите са изправени пред избор между инвестиране в петролната, дървената и автомобилната промишленост. Едновременно със закритото им заседание има и закрито заседание на правителството, на което то трябва да направи избор между преобладаващото развитие на петролодобив, железници, електричество или жилищно строителство. Формулирайте проблема като игра с ненулева сума, съставяйки матрицата на играта.
14 май. Търговската фирма има два камиона, които се връщат от различни градове. Компанията трябва спешно да изпрати товар до град N. Ако шофьорите пристигнат точно по график или по-рано и отидат в спешна командировка, тогава всеки от тях ще има двудневен престой. Ако и двамата водачи закъснеят, всеки от тях ще има по един ден престой. Ако някой от тях пристигне навреме или по-рано и отиде приград N, тогава той няма да има престой, а другият ще има престой от пет дни. Формулирайте проблема като игра с ненулева сума, намерете решение.
Не намерихте това, което търсихте? Използвайте търсачката: