Постановка задачи. Основные понятия
Аксиома Парето и эффективные варианты
Методы сравнения векторных оценок с использованием дополнительной информации
Предмет и задачи теории игр
Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы
Основные понятия и определения
Аффинно-эквивалентные игры
Доминирование дележей
С - ядро (core)
Вектор Шепли
Игры с природой в условиях определенности
Критерий пессимизма-оптимизма Гурвица
Критерий Лапласа
Навигация
Вектор Шепли
Теория принятий решений
93693
знака
17
таблиц
1
изображение
7. Вектор Шепли.
До сих пор были рассмотрены решения игр, отвечающие принципам оптимальности в смысле выгодности и устойчивости ( maxmin в чистых или смешанных стратегиях ) или только устойчивости ( C-ядро и Н-М решение в кооперативных играх ). Рассмотрим решения, оптимальные в смысле справедливости.
Задача состоит в том, чтобы найти вектор распределения общего выигрыша между участниками игры: Ф(v) = ( Ф1(v), Ф2(v),... Фn(v))
При этом необходимо, чтобы Ф(v) был дележом в условиях кооперативной игры, то есть отвечал бы требованиям игдивидуальной и групповой рациональности.
Предлагаемое решение носит аксиоматический характер, то есть выводится формальным образом из некоторой полной и непротиворечивой системы аксиом. Эта система включает в себя: аксиому эффективности, аксиому симметрии и аксиому агрегации.
Аксиома эффективности: распределение выигрыша носителя игры ( N ) происходит только между игроками, входящими в носитель. Иными словами, все приращение выигрыша, достигаемое только за счет обьединения в коалицию (эффект супераддитивности), распределяется только между теми, кто его обеспечил. С другой стороны, все болваны получают только то, что они выиграли бы в одиночку или в составе коалиции.
Формально эти условия выражаеюся в том, что å Фi(v) = v (N), iÎN, и Фj(v) = v(j), jÎ I\N.
Аксиома симметрии: игроки, входящие в игру симметрично, должны получать одинаковый доход. Здесь симметричность понимается как одинаковое влияние на характеристическую функцию. Это утверждение равносильно тому, что доход игрока не зависит от его номера или "имени".
Формально Фj(v) = Фpj(v), где p - целое положительное число.
Аксиома агрегации: если игрок принимает участие в двух играх с характеристическими функциями v’ и v”, то причитающаяся ему доля:
Ф(v’ + v”) = Ф(v’) + Ф(v”), если множества игроков в обоих играх совпадают.
Совокупность аксиом является непротиворечивой и полной: для всякой характеристической функции v вектор Ф(v) существует и является единственным (вектор Шепли). Непротиворечивость обеспечивает существование, а полнота его единственность.
Теорема. Для любой характеристической функции v над I={1,2,...n} компоненты вектора Шепли определяются по формуле
Пример. Для кооперативной игры трех лиц в 0-1 редуцированной форме эта формула имеет вид: Фi(v) = 1/6 (2 - 2Ci + Cj + Cf).
Следовательно, координаты вектора Шепли:
Ф1(v) = 1/6 (2 - 2C1 + C2 + C3), где C1 = v(2,3);
Ф2(v) = 1/6 (2 - 2C2 + C1 + C3), где C2 = v(1,3);
Ф3(v) = 1/6 (2 - 2C3 + C1 + C2), где C3 = v(1,2).
Для того, чтобы вектор Шепли принадлежал к С-ядру необходимо и достаточно, чтобы выполнялось неравенство: 4Ci + Cj + Cf £ 4 для всех i, j,f.
8. Примеры классических кооперативных игр.
Задача "Джаз-оркестр".
Условие. Владелец клуба в Париже обещает 1000 $ певцу (S), пианисту (P) и ударнику (D) за совместную игру в клубе. Выступление дуэта певца и пианиста он расценивает в 800 $, ударника и пианиста - в 650 $, а одного пианиста в 300 $. Другие дуэты и солисты не рассматриваются , а присутствие пианиста владелец считает обязательным.
Дуэт певец - ударник зарабатывает 500 $ за вечер в одной удобно расположеной станции метро, певец зарабатывает в среднем 200 $ за вечер в открытом кафе. Ударник один ничего не может заработать.
Стоит ли музыкантам соглашаться на приглашение владельца клуба и как поделить общий заработок ?
Решение. Обозначим S, P,D - 1 игрок, 2 игрок и 3 игрок соответственно.
Найдем 0-1 редуцированную форму исходной игры:
|
Коалиция
| 123 SPD | 12 SP | 13 SD | 23 PD | 1 S | 2 P | 3 D |
| v | 1000 | 800 | 500 | 650 | 200 | 300 | 0 |
| v(0-1) | 1 | 0,6 | 0,6 | 0,7 | 0 | 0 | 0 |
| Условие эффективности дележей | Условие неэффективности (принадлежности к С-ядру) |
| Для редуцированной формы | |
| x1 ³ 1 - v(2,3) = 0,3 | x1 £ 0,3 |
| x2 ³ 1 - v(1,3) = 0,4 | x2 £ 0,4 |
| x3 ³ 1 - v(1,2) = 0,4 | x3 £ 0,4 |
| Для нередуцированной формы | |
| xS + xP £ 800 , xD ³ 200 | xS + xP ³ 800, xD £ 200 |
| xS + xD £ 500 , xP ³ 500 | xS + xD ³ 500, xP £ 500 |
| xD + xP £ 650 , xS ³ 350 | xD + xP ³ 650, xS £ 350 |
Найдем вектор Шепли для этой игры. В нередуцированной форме n=3, коалиции могут быть из одного, двух и трех игроков.
ФS = (3-3)!2! (1000 -650)/ 3! + 1!1![(800 - 300) + (500 - 0)] / 3! + 2!0! 200 / 3! = 350;
ФP = 475;
ФD = 175.
Нетрудно видеть, что, ФS + ФP + ФD = 1000, то есть условие коллективной рациональности выполняется. С другой стороны:
ФS = 350 > v(S) = 200;
ФP = 475 > v(P) = 300;
ФD = 175 > v(D) = 0, то есть условия индивидуальной рациональности так же выполняются. Таким образом, в данном случае вектор Шепли является дележом, кроме того, он входит в С-ядро :
xD = ФD=175 < 200, xP = ФP=475 < 500, xS = ФS=350 = 350 (выплата певцу оказалась максимальной).
Для 0-1 редуцированной формы:
Ф1(v) = 1/6 (2 - 2C1 + C2 + C3) = (2 - 1,4 + 1,2)/ 6 = 0,3;
Ф2(v) = 1/6 (2 - 2C2 + C1 + C3) = (2 - 1,2 + 1,3)/ 6 = 0,35;
Ф3(v) = 1/6 (2 - 2C3 + C1 + C2) = (2 - 1,2 + 1,3)/ 6 = 0,35.
Вектор Шепли Ф(v) = ( 0,3; 0,35; 0,35) входит в С-ядро игры:
4Ci + Cj + Cf = 2,8 + 0,6 + 0,6 = 4 ( £ 4), то есть условие соблюдается на границе для первого игрока. Для других двух игроков:
4Ci + Cj + Cf = 2,4 + 0,7 + 0,6 = 3,7 < 4, то есть условие вхождения в С-ядро тоже соблюдается.
Ответ. Музыкантам выгодно предложение владельца клуба, так как они заработают за этот вечер не менее, чем обычно. Общий заработок в 1000 $ они должны поделить следующим образом: певцу 350 $, пианисту 435 $, ударнику 175 $.
Глава . Принятие решений в условиях частичной неопределенности.
Элементы теории статистических решений.
Предметом рассмотрения данного раздела служат статистические модели приянятия решений, трактуемые как статистические игры или игры с природой при использовании дополнительной статистической информации о ее стратегиях. Характерная черта статистической игры - возможность получения информации в результате некоторого статистического эксперимента для оценки распределения вероятностей стратегий природы. Исследование механизма случайного выбора стратегии природой позволяет принять оптимальное решение, которое будет наилучшей стратегией в игре с неантагонистическим противником человека - природой.
В рассмотренных разделах теории игр предполагалось, что оба противника (или больше двух) активно противодействуют друг другу, что оба они достаточно умны, чтобы искать и найти свою оптимальную стратегию, и осторожны, чтобы не отступать от нее. Такое положение дает возможность предсказывать поведение игроков. Неопределенность была лишь в выборе противником конкретной чистой стратегии в каждой отдельной партии.
Но возможен случай, когда неопределенность в игре вызвана не сознательным противодейтсвием противника, а незнанием условий, в которых будет приниматься решение, случайных обстоятельств. Такие игры называются "играми с природой".
Игра человека с природой тоже отражает конфликтную ситуацию, возникающую при столкновении интересов в выборе решения. Но "стихийным силам природы" нельзя приписать разумные действия, направленные против человека и тем более какой-либо "злой умысел". Таким образом, корректнее говорить о конфликтной ситуации, вызванной столкновением интересов человека и неопределенностью действий природы.
Действия природы могут как наносить ущерб, так и приносить прибыль. Поведение природы можно оценить статистическими методами, определить присущие ей закономерности. В зависимости от степени знания этих закономерностей, определяющих поведение природы, различаются игры с природой в условиях определенности и игры с природой в условиях неопределенности.
В первых поведение природы известно полностью (заданы вероятностями). Во вторых - действия природы не известны, или изучены частично.
К явлениям природы, влияющим на результат решения относят не только погодные и сезонные явления (дождь, засуху, урожай, неурожай), но и проявление любых, не зависящих от нас обстоятельств: например, задержки на транспорте.
Поиском решений в таких ситуациях и занимается теория статистических решений.
Человек, играя с природой, стремиться максимизировать свой выигрыш, поэтому, если он осторожный игрок ( а теория игр рассматривает именно таких игроков), он должен при выборе своей стратегии руководствоваться тем, что неизвестные или известные ему закономерные действия природы приведут к наименее благоприятным последствиям. Именно поэтому такие игры можно рассматривать как игры двух лиц с нулевой суммой, которые были уже нами рассмотрены.
Формализация задачи происходит следующим образом: у активного игрока (человека) возможные действия по прежнему называются стратегиями, а возможные действия пассивного игрока (природы) - состояниями или условиями природы.
В качестве первого игрока всегда выступает человек, поэтому в матрице записывается его выигрыш. Так как нас интересует оптимальная стратегия человека и его гарантированный выигрыш, то в игру достаточно определить максиминную стратегию первого игрока и нижнюю цену игры. Определение верхней цены игры имеет смысл, если даная игра повторяется многократно и оптимальная стратегия может быть смешанной.
Похожие работы
митационной модели , проведение экспериментов на этих моделях Обработка результатов экспериментов с целью выбора наилучшего варианта модернизации или реорганизации сети Проведение работы по модернизации и реорганизации сети Требования к специалисту на должность администратора сети Приведем некоторые примеры требований: Работодатель №1: Опыт построения и сопровождения программных/аппаратных ...
... максимизирующий выделенный критерий на множестве исходов, оценки которых по остальным критериям не ниже назначенных. Всякие задачи принятия решения является: Альтернативы (варианты, планы, допустимые альтернативы) Исходы (Результаты) Оптимальные решения (Наилучшие решения) Математическая модель ЗПР включает в себя формальное описание этих компонентов. X - множество допустимых альтернатив A ...
... условиях определенности математическое программирование дает точное решение поставленной задачи. Поэтому необходимости выбирать из нескольких вариантов попросту нет. Таким образом, в условиях определенности "Теория принятия решений" не используется, такими задачами занимается математическое программирование. 2) ЛПР знает вероятность реакции окружающей среды на выбор им той или иной альтернативы. ...
... , среднее распределение процентных отношений, дисперсия, стандартные отклонения, коэффициенты вариации Коэффициенты – j, c2, Чупрова, Спирмена, коэффициент корреляции Пирсона 2. Теория принятия решений Выбор любого управленческого решения всегда ограничен. Это объясняется необходимостью следовать определённым нормам поведения, которые и ориентируют руководителя. В зависимости от ...
0 комментариев