Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

Оптимальность по Парето. Множество. Метод идеальной точки

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

Содержательные представления об устойчивости, выгодности и справедливости многообразны. Выше мы рассматривали проявление устойчивости через равновесие. Существует и иной вариант устойчивости ситуации, в большей степени, чем равновесность, отражающий черты ее выгодности. Это оптимальность по Парето. 5.1. Множество Парето Рассмотрим на плоскости (U, V) множество ft (рис.8).

Каждая его точка обладает одним из следующих свойств: либо все точки, ближайшие к ней, принадлежат множеству ft (такая точка называется внутренней точкой множества ft), либо сколь угодно близко от нее расположены как точки множества ft, так и точки, множеству ft не принадлежащие (такие точки называются граничными точками множества ft).

Граничная точка может как принадлежать множеству ft, так и не принадлежать. Здесь мы будем рассматривать только такие множества, которым принадлежат все точки границы. Множество всех граничных точек множества называется его границей. Обозначение: 0ft. Пусть М — произвольная точка множества ft, внутренняя или граничная, и (U, V)— ее координаты. Поставим следующий вопрос: можно ли, оставаясь во множестве ft, переместиться източки М в близкую точку так, чтобы при этом увеличились обе ее координаты. Если М — внутренняя точка, то это бесспорно возможно.

Если же М — граничная точка, то такое возможно не всегда (рис. 9). Из точек М\, М2, Л#з это сделать можно, но уже из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата U при этом остается неизменной). Перемещая точку горизонтального отрезка PQ вправо, мы увеличиваем координату U (при этом координата V сохраняет свое значение). Что же касается дуги BQy то перемещение вдоль нее способно увеличить лишь одну из координат при одновременном уменьшении другой.

Тем самым, точки множества ft можно разбить на три класса: в первый класс относятся точки, которые, оставаясь во множестве ft, можно сдвинуть так, чтобы одновременно увеличились обе координаты (в этот класс попадают все внутренние точки множества ft и часть его граничных точек), второй класс образуют точки, перемещением которых по множеству П можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезок PQ на границе множества ft), в третий класс попадут точки, перемещение которых по множеству Q способно лишь уменьшить либо одну из координат, либо обе (дуга BQ границы дП) (рис. 10).

Множество точек третьего класса называется множествам Парето, или границей Парето данного множества Q (выделено на рис. 10). 5.2. Метод идеальной точки Пусть на плоскости (х, у) задано множество и (рис. 11) и в каждой точке этого множества определены две непрерывные функции Рассмотрим следующую задачу. Во множестве и) найти точку у,), в которой Обычно это записывается так Сразу же отметим, что в общем случае поставленная задача решения не имеет.

В самом деле, нарисуем на плоскости (С/, V) все точки, координаты которых вычисляются по формулам Из рис. 12 видно, что наибольшее значение U - Umax — и наибольше значение V - Vmax — достигаются в разных точках, а точка с координатами лежит вне множества Q. Тем самым, в исходной постановке задача, вообще говоря, неразрешима — удовлетворить обоим требованиями одновременно невозможно. И, следовательно, нужно искать какое-то компромиссное решение.

Опишем один из путей, использующий множество Парето. точка утопии идеальная точка . Сначала на плоскости (U, V) задается целевая точка, в качеств координат которой часто выбирается сочетание наилучших значений обоих критериев U и V. В данном случае это точка ((7тм, Vmax). Вследствие того, что обычно такая точка при заданных ограничениях не реализуется, ее называют тонкой утопии. Затем строится множество Парето и на нем ищется точка, ближайшая к точке утопии — идеальная точка (рис. 13). 5.3.

Оптимальность по Парето в биматричной игре Рассмотрим биматричную игру с 2 х 2-матрицами Пусть средние выифыши игроков А и В.

Ситуация (р», q.) в биматричной игре А и В наказывается оптимальной по Парето, если из того, что вытекают равенства Иными словами, в оптимальной по Парето ситуации игроки не могут совместными усилиями увеличить выигрыш одного из игроков, не уменьшив при этом выигрыш другого. Различие ситуации равновесия от ситуации, оптимальной по Парето, состоите следующем: в ситуации равновесия ни один из игроков, действуя в одиночку, не может увеличить своего собственного выигрыша; в ситуации, оптимальной по Парето, игроки, действуя совместно, не могут (даже нестрого) увеличить выигрыш каждого.

Обратившись к игре «Дилемма узников», покажем, как практически отыскиваются оптимальные по Парето ситуации. Напомним, что соответствующие платежные матрицы в этой игре имели следующий вид Тем самым, на единичном квадрате (рис. 14) возможных значений вероятностей р и д заданы две функции Точки с координатами (U, 7), вычисленными по приведенным формулам, на плоскости (U, V) заполняют четырехугольник с вершинами Граница Парето этого множества — ломаная NKL.

Возможно вам будут полезны данные страницы:

Линии применяемые на чертеже
Схема построения графика функции
Координаты и компоненты вектора
Сечение цилиндра плоскостью

Каждый из игроков заинтересован в наибольшем значении своего среднего выигрыша Оптимальность по Парето Множество Метод идеальной точки Нетрудно заметить, что в данном случае Тем самым, точкой утопии в этой задаче является начальная точка 0(0, 0). Ближайшая к ней точка множества Парето — К(-1, -1) (рис. 16). Идеальная точка К(-1, -1) — точка с наибольшими выигрышами для каждого из игроков — оказывается лучше, чем равновесная точка М(-6, -6), и ей соответствуют чистые стратегии обоих игроков Несколько слов в заключение На анализе полученных результатов стоит остановиться чуть подробнее.

Из приведенных примеров видно, что числа С и D из соотношений (#*) на с. 273 могут быть как положительными, так и отрицательными. Они могут, в частности, даже обращаться в нуль. Рассмотрим однако наиболее интересный в приложениях случай, когда ни С ни D нулю не равны, Тогда, как нетрудно видеть, точка равновесия определяется парой Эти формулы являются весьма примечательными: в равновесной ситуации выбор игрока А полностью определяется элементами платежной матрицы игрока В, (и не зависит от элементов его собственной платежной матрицы), а выбор игрока В в равновесной ситуации полностью определяется элементами платежной матрицы игрока А, (и не зависит от элементов его собственной платежной матрицы).

Иными словами, равновесная ситуация обоих игроков определяется не столько стремлением увеличить собственный выигрыш, сколько желанием держать под контролем выигрыш другого игрока (минимизировать этот выигрыш). И если, например, заменить в биматричной игре матрицу выплат игроку А, а матрицу выплат игроку В оставить прежней, то игрок А никак не изменит своего «равновесного» поведения (просто не обратит внимания на эту замену), в то время как игрок В изменит свою стратегию на новую, равновесную. Оптимальность по Парето Множество Метод идеальной точки Таким образом, в биматричной (неантагонистичсской) игре мы вновь встречаемся с антагонизмом.

Правда, теперь это уже не антагонизм интересов (как это было в антагонистической, матричной игре), а антагонизм поведения. Отметим, что в биматричными играх (в отличие от матричных) при наличии нескольких ситуаций равновесия средний выигрыш игрока в разных равновесных ситуациях различен (напомним, что в матричной игре выигрыш игрока один и тот же вне зависимости от количества точек равновесия). Но если средние выигрыши разнятся, то какую равновесную ситуацию следует считать оптимальной?

Наконец, сше одно, не менее

интересное. Вспомним, с какими трудностями мы столкнулись, пытаясь перевести эмоциональные оценки результатов общения студент-преподаватель в количественные показатели. В целом сохраняя основные соотношения, эти количественные оценки могут, конечно, изменяться как от студента к студенту, так и от преподавателя к преподавателю.

Однако, если эти изменения будут не слишком значительными — элементы платежной матрицы пошевельнутся «слегка» — то слегка пошевелятся и зигзаги, не изменяя ни своей обшей формы, ни взаимного расположения, а, значит, число равновесных ситуаций не изменится. Впрочем, сказанное относится лишь к случае, когда множество ситуаций равновесия конечно и состоит из нечетного числа точек (одной или трех).

Как принято говорить в подобных случаях, это число устойчиво относительно малых шевелений. Конечно, в некоторых биматричных играх равновесные ситуации случаются и вчи-стых стратегиях (в последнем из разобранных примеров таких ситуаций даже две). И (в принципе это совсем нетрудно) можно дать определение ситуации равновесия в чистых стратегиях. Найти ее (если она, конечно, существует) — дело довольно простое. Но, как показывают приведенные примеры, во-первых, чистой ситуации равновесия может вовсе не быть, а, во-вторых, даже при ее наличии не исключено существование равновесных ситуаций в смешанных стратегиях.

И желая найти их все, неизбежно приходится обращаться к описанному выше подходу. Реальные конфликтные ситуации приводят к разным видам игр. Различны и способы их анализа и разрешения. Мы остановились лишь на трех видах игр — матричных, позиционных и бима-тричных. Сделанный выбор обусловлен тем, что уже здесь можно наглядно показать, какой смысл вкладывается в термин игра и чем именно занимается теория игр, а также познакомить с относительно несложным математическим инструментарии, опирающимся на ключевые понятия вероятности, матрицы и координаты и позволяющим разрешать простейшие из этих видов игр.

Вместе с тем, нам не хотелось бы, чтобы у читателя сложилось впечатление, что доступными анализу могут быть только игры, описанные выше. Существует обширный, содержательный и интересный, привлекающий неослабевающее внимание исследователей класс игр, в которых хотя бы один из игроков имеет бесконечное множество возможных стратегий — бесконечные игры.

В этом — заключительном — разделе мы приведем три примера бесконечных игр: непрерывной игры на единичном квадрате (непрерывными называются бесконечные игры, в которых функции выигрышей непрерывно зависят от стратегий, выбираемых игроками), дуэли (играми с выбором момента времени, или играми типа дуэли, называются игры, характеризующиеся моментом выбора хода и вероятностями получения выигрыша в зависимости от времени, прошедшего от начала игры до момента выбора) и дифференциальной игры поиска (в дифференциальных играх допускается делать ходы непрерывно и связывать поведение игроков условиями, описываемыми дифференциальными уравнениями).

При этом мы ограничимся, как и ранее, играми двух лиц и проведем лишь постановку задач (описание возможностей в поведении игроков и построение функций выигрышей), хотя для каждой из приводимых игр разработаны достаточно эффективные подходы к построению их решения. Борьба за рынки (игра на единичном квадрате) Одна из конкурирующих фирм (игрок А) пытается вытеснить другую фирму (ифока В) с одного из двух рынков сбыта. Предположим, что общая сумма средств, выделенная на это игроком А, равна 1. Типичной стратегией игрока А является разделение выделенной суммы на две части: х (0 ^ х ^ 1) для первого рынка и 1 - х для второго.

Подобным образом выглядят и стратегии игрока В: выделение им части у (0 ^ у ^ 1) своей суммы на первый рынок и 1 - у на второй. Будем считать, что если игрок А добился превосходства на одном из рынков (на другом превосходства автоматически добивается игрок В), то он вытесняет противника с этого рынка и получает выигрыш, пропорциональный избытку вложенных средств с коэффициентом, характеризующим важность рынка (этот коэффициент равен к| для первого рынка и кг для второго).

Тогда функция выигрыша Н(х, у) игрока А определяется формулой Ясно, что функция выигрыша игрока В равна -Я(ж, у Дуэль Два дуэлянта (игроки А и #) начинают сходиться в момент времени t = 0. У каждого пистолет заряжен одной пулей. Они встретятся в момент времени t = 1 (если только ни один из них не застрелит другого раньше). Каждый из дуэлянтов может выстрелить, когда пожелает. Если при этом одному из них удастся поразить противника, а самому остаться невредимым, то он становится победителем (его выигрыш равен 1) и дуэль тут же прекращается. Если оба промахнутся, дуэль закончится вничью (выигрыш каждого из игроков равен 0).

Если оба выстрелят одновременно и каждый поразит противника, то дуэль также считаете я окончившейся вничью. Если игрок А произведет выстрел в момент времени , то его выстрел будет успешным с вероятностью р{х). Подобным же образом, выстрел игрока В в момент времени будет успешным с вероятностью q(y). При условии игрок А выиграете вероятностью р{х), а проиграет с вероятностью Тем самым, его средний выигрыш при будет равен С другой стороны, если х> у, его средний выигрыш будет равен

При х = у средний выигрыш Оптимальность по Парето Множество Метод идеальной точки Таким образом, функция выигрыша Н(х, у) игрока А имеет вид и антагонистическая игра задана. В частности, если игроки стреляют без промаха, р(х) = q(y) = 1, Дифференциальная игра поиска Ищущий (игрок А) стремится обнаружить уклоняющегося (игрока В). Оба игрока перемещаются с постоянными скалярными скоростями (а и /? соответственно) по плоскости внутри некоторой поисковой области П. В любой момент времени каждый из игроков управляет своим перемещением, задавая направление вектора скорости.

Пусть (хл, уА) и (хв, у в) — координаты игроков. Тогда имеем dt Игра поиска заканчивается в тот момент, когда игроки сблизятся на расстояние I > О, иными словами, когда будет выполнено неравенство В случае успешного обнаружения выигрыш игрока А считается равным I. Построение решения в этой игре существенно зависит от характера и степени информированности игроков. Все, о чем говорилось в этой книге, — примеры бескоалиционных игр, когда любые соглашения, обмен информацией, побочные платежи, совместный выбор стратегий запрещены. Другой важный класс составляют кооперативные игры, в которых разрешены самые разнообразные формы сотрудничества.

Возможность соглашений между игроками оказывает существенное влияние на исход игры. Если допустить, например, в игре «Дилемма узников» совместный выбор стратегий, то исход игры может оказаться совсем иным. При наличии побочных платежей по-иному окончится и «Семейный спор». Вне поля наших рассмотрений остались игры с одним участником, а также игры с участием трех и более игроков; последние особенно интересны, но они и трудны. Задачи к разделу 1.

Найдите нижнюю цену игры, верхнюю цену игры, определите седловые точки, оптимальные чистые стратегии и цену игры (если они существуют): а) 2. Найдите решения следующих матричных игр: 3. Найдите точные и приближенные решения следующих матричных игр: а) 1-й ход делает игрок А: он выбирает число х из множества двух чисел {1, 2}. 2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число у из множества двух чисел {1,2}. 3-й ход делает игрок А: он выбирает число z из множества двух чисел {1, 2}, зная значение у, выбранное игроком В на 2-м ходе, но не помня собственного выбора х на 1-м ходе.

б) /-йход делает игрок А: он выбирает число х из множества двух чисел {1, 2}. 2-йход делает игрок В: зная выбор игрока А на 1-м ходе, он выбираетчисло у из множества двух чисел {1, 2}. 3-й ход делает игрок А: он выбираетчисло z из множества двух чисел {1, 2}, не зная значения у, выбранного игроком В на 2-м ходе, но помня собственный выбор х на 1-м ходе. в) 1-й ход производится случайно: игрок О выбирает число х, равное 1 с вероятностью 0,3 и равное 2 с вероятностью 0,7. 2-й ход делает игрок А:

он выбирает число у из множества двух чисел {1, 2}, зная результат случайного выбора на 1-м ходе. 3-й ход делает игрок В\ он выбирает число z из множества двух чисел {1,2}, зная выбор у игрока А на 2-м ходе, но не зная случайного выбора х на 1-м холе. 4. Дайте графическое предстаааение, приведите к нормальной форме и найдите точное решение позиционной игры со следующей функцией выигрышей W(iу, z): Найдите решение биматричной игры: Найдите ситуации равновесия в каждом из двух случаев: Ответы